Auto generated proc for loop has duplicate paramters

[CaviarChen]

I am working on another test case for gloabl CTGC (using explicit setter). Here is the program:

type drone_info { pub drone_info(x:int, y:int, z:int, count:int) }

def drone_init():drone_info = drone_info(0, 0, 0, 0)

def print_info(d:drone_info) use !io {
    !print("(")
    !print(x(d))
    !print(", ")
    !print(y(d))
    !print(", ")
    !print(z(d))
    !print(") #")
    !print(count(d))
    !nl
}

def do_action(!d:drone_info, action:char, ?success:bool) {
    ?success = true
    if { action = 'n' ::
        y(!d, y(d)-1)
    | action = 's' ::
        y(!d, y(d)+1)
    | action = 'w' ::
        x(!d, x(d)-1)
    | action = 'e' ::
        x(!d, x(d)+1)
    | action = 'u' ::
        z(!d, z(d)+1)
    | action = 'd' ::
        z(!d, z(d)-1)
    | otherwise ::
        ?success = false
    }
    if { success ::
        count(!d, count(d)+1)
    }
}

?d = drone_init()
do {
    !read(?ch:char)
    until ch = eof
    if { ch /= ' ' && ch /= '\n' ::
        if { ch = 'p' ::
            !print_info(d)
        | otherwise ::
            do_action(!d, ch, ?success)
            if { success = false ::
                !println("invalid action!")
            }
        }
    }
}

!malloc_count(?mc)
!println(mc)

Note that the variable d should be unaliased. However, the prototype of the generated procedure for the loop is like this:

0: gen$1(argc#0:wybe.int, argv#0:wybe.int, d#0:drone.drone_info, exit_code#0:wybe.int, io#0:wybe.phantom, tmp$0#0:drone.drone_info, ?argc#1:wybe.int, ?argv#1:wybe.int, ?exit_code#1:wybe.int, ?io#3:wybe.phantom):

The d#0 and tmp$0#0 in it are the same thing, according to the call site:

    foreign lpvm alloc(32:wybe.int, ?tmp$13#0:drone.drone_info)
    foreign lpvm mutate(~tmp$13#0:drone.drone_info, ?tmp$14#0:drone.drone_info, 0:wybe.int, 1:wybe.int, 32:wybe.int, 0:wybe.int, 0:wybe.int)
    foreign lpvm mutate(~tmp$14#0:drone.drone_info, ?tmp$15#0:drone.drone_info, 8:wybe.int, 1:wybe.int, 32:wybe.int, 0:wybe.int, 0:wybe.int)
    foreign lpvm mutate(~tmp$15#0:drone.drone_info, ?tmp$16#0:drone.drone_info, 16:wybe.int, 1:wybe.int, 32:wybe.int, 0:wybe.int, 0:wybe.int)
    foreign lpvm mutate(~tmp$16#0:drone.drone_info, ?tmp$0#0:drone.drone_info, 24:wybe.int, 1:wybe.int, 32:wybe.int, 0:wybe.int, 0:wybe.int)
    drone.gen$1<0>(~argc#0:wybe.int, ~argv#0:wybe.int, ~tmp$0#0:drone.drone_info, ~exit_code#0:wybe.int, ~io#0:wybe.phantom, ~tmp$0#0:drone.drone_info, ?argc#1:wybe.int, ?argv#1:wybe.int, ?exit_code#1:wybe.int, ?io#1:wybe.phantom) #1 @drone:42:1

It stops the specialized version of gen$1<0> to be used.

[pschachte]

Interesting.... I'm not sure why this is happening. I suspect it's because when I create recursive procs to implement loops (in Unbranch) I just make every variable in scope an argument, and only later (in BodyBuilder) do I get rid of definite aliases. I'll look into this, but I don't think it's going to be easy to fix.

On 4/9/20 16:59, Zed(Zijun) Chen wrote:

I am working on another test case for gloabl CTGC (using explicit setter). Here is the program:

type drone_info { pub drone_info(x:int, y:int, z:int, count:int) }

def drone_init():drone_info = drone_info(0, 0, 0, 0)

def print_info(d:drone_info) use !io { !print("(") !print(x(d)) !print(", ") !print(y(d)) !print(", ") !print(z(d)) !print(") #") !print(count(d)) !nl }

def do_action(!d:drone_info, action:char, ?success:bool) { ?success = true if { action = 'n' :: y(!d, y(d)-1) | action = 's' :: y(!d, y(d)+1) | action = 'w' :: x(!d, x(d)-1) | action = 'e' :: x(!d, x(d)+1) | action = 'u' :: z(!d, z(d)+1) | action = 'd' :: z(!d, z(d)-1) | otherwise :: ?success = false } if { success :: count(!d, count(d)+1) } }

?d = drone_init() do { !read(?ch:char) until ch = eof if { ch /= ' ' && ch /= '\n' :: if { ch = 'p' :: !print_info(d) | otherwise :: do_action(!d, ch, ?success) if { success = false :: !println("invalid action!") } } } }

!malloc_count(?mc) !println(mc)

Note that the variable d should be unaliased. However, the prototype of the generated procedure for the loop is like this:

0: gen$1(argc#0:wybe.int, argv#0:wybe.int, d#0:drone.drone_info, exit_code#0:wybe.int, io#0:wybe.phantom, tmp$0#0:drone.drone_info, ?argc#1:wybe.int, ?argv#1:wybe.int, ?exit_code#1:wybe.int, ?io#3:wybe.phantom):

The d#0 and tmp$0#0 in it are the same thing, according to the call site:

foreign lpvm alloc(32:wybe.int, ?tmp$13#0:drone.drone_info)
foreign lpvm mutate(~tmp$13#0:drone.drone_info, ?tmp$14#0:drone.drone_info, 0:wybe.int, 1:wybe.int, 32:wybe.int, 0:wybe.int, 0:wybe.int)
foreign lpvm mutate(~tmp$14#0:drone.drone_info, ?tmp$15#0:drone.drone_info, 8:wybe.int, 1:wybe.int, 32:wybe.int, 0:wybe.int, 0:wybe.int)
foreign lpvm mutate(~tmp$15#0:drone.drone_info, ?tmp$16#0:drone.drone_info, 16:wybe.int, 1:wybe.int, 32:wybe.int, 0:wybe.int, 0:wybe.int)
foreign lpvm mutate(~tmp$16#0:drone.drone_info, ?tmp$0#0:drone.drone_info, 24:wybe.int, 1:wybe.int, 32:wybe.int, 0:wybe.int, 0:wybe.int)
drone.gen$1<0>(~argc#0:wybe.int, ~argv#0:wybe.int, ~tmp$0#0:drone.drone_info, ~exit_code#0:wybe.int, ~io#0:wybe.phantom, ~tmp$0#0:drone.drone_info, ?argc#1:wybe.int, ?argv#1:wybe.int, ?exit_code#1:wybe.int, ?io#1:wybe.phantom) #1 @drone:42:1

It stops the specialized version of gen$1<0> to be used.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/pschachte/wybe/issues/87, or unsubscribehttps://github.com/notifications/unsubscribe-auth/ACLLL3AARZPHPXCEP6YBYDLSECF45ANCNFSM4QXOXYYQ.

-- Peter Schachte Assistant Director, Infrastructure - IT Melbourne School of Engineering Senior Lecturer, School of Computing and Information Systems University of Melbourne http://bit.ly/peterschachte

We promote flexible working at the Melbourne School of Engineering. I am currently working hours remotely. If you wish to contact me, my most preferred contact method is email.

I’m sending this message now because it suits me, but I don’t expect that you will read, respond or action it outside of your working hours.

[CaviarChen]

Once fixed, need to update #91 and #88.

[CaviarChen]

I think it might be better to handle this instead of including every variables in that scope when generating the auto generated procedures.

Identifying and removing unused parameters is really tricky.

I am working on extending the BodyBuilder to handle the following case:

def foo(a, b) {
    ?a = a + 1
    foo(a, b)
}

The paramter b will be marked as unused. It is almost done, except that I still need to fix the final use marking. Final use marking and unused paramter makring are executed at the same time and that makes things a little bit tricky.

However, this enhancement does not cover most of the cases.

A common case is that there are multiple mutually recursive procedures, such as:

def gen$1(a, b) {
    case:
    0:
        # some operations
        gen$2(a, b)
    1:
        # some operations
        gen$2(a, b)
}

def gen$2(a, b) {
    # a lot of opertaions, so it cannot be inlined.
    gen$1(a, b)
}

Handling this requires a fix point process for the optimization(expansion) pass.

Another common case is this:

# top-level code
gen$1(something, argc#0, argv#0, exit_code#0, ?argc#1, ?argv#1, ?exit_code#1)

def gen$1(something, argc#0, argv#0, exit_code#0, ?argc#1, ?argv#1, ?exit_code#1) {
    case:
    0:
        # some operations
        gen$2(something, argc#0, argv#0, exit_code#0, ?argc#1, ?argv#1, ?exit_code#1)
    1:
        # some operations
        gen$2(something, argc#0, argv#0, exit_code#0, ?argc#1, ?argv#1, ?exit_code#1)
}

def gen$2(something, argc#0, argv#0, exit_code#0, ?argc#1, ?argv#1, ?exit_code#1) {
    case:
    0:
        gen$1(something, argc#0, argv#0, exit_code#0, ?argc#1, ?argv#1, ?exit_code#1)
    1:
        move(argc#0, ?argc#1)
        move(argv#0, ?argv#1)
        move(exit_code#0, ?exit_code#1)
}

This is really annoying to handle.

[pschachte]

Yes, this is rather fiddly, and as far as I can see, requires processing to a fixed point if you want to be precise. I pushed a commit a few weeks ago that should help, but it doesn't process to a fixed point, so it won't be precise.

In essence, what we need to do is propagate "neededness" from the end to the beginning of each body, initially considering only the outputs to be needed, but marking every variable needed if it is an input to any call with some needed outputs. The fixed point processing should work by initially assuming all inputs of each proc are unneeded and all outputs are needed, and then repeatedly marking inputs as needed when they're used in any call whose output is needed, until we reach a fixed point. The fixed point is guaranteed because the only possible changes are marking a parameter needed, so the operation is monotonic.

This algorithm should work:

for each call graph scc in a module dependency scc, bottom-up:
    mark every input parameter for every proc in the SCC as unneeded
    do:
        done := true
        for each proc p in the scc:
            needed := process_body(the body of p, output params of p)
            for each input parameter i of p:
                if i is in needed and marked as unneeded:
                    mark i as needed
                    done := false
    until done

This code finds the variables needed in a proc body:

def process_body(body, needed):
    for each fork f in body:
        needed1 := needed
        for each body b in f:
        needed1 := union(needed1, process_body(b,  needed))
    for each call or foreign call c in the bodyPrims of body from end to beginning
            if any output of c is in needed1:
                needed1 := union(needed1, inputs of c that are marked as needed by c's proc)
    return needed1

After the fixed point is found, then the current code can be used to eliminate unneeded calls in the body.

One little optimisation is to omit all of this for non-recursive sccs, because the current code already does the right thing for them.

I'm sure I've made some mistakes here, but I think this is at least approximately correct. What it doesn't do, however, is mark outputs as unneeded if no callers actually need them. That requires a top-down pass, and would definitely benefit from multiple specialisation.

I hope that helps.

[jimbxb]

I agree with @CaviarChen here in that we should remove some definitely unneeded params from continuation procs. They arent that difficult to approximate, as they're inputs to whatever the continuation's statements are.