Support definite-assignment (remote-init) using "at"

David Grove added a comment - 15/Dec/10 11:00 AM bulk move of all unresolved issues from 2.1.1 to 2.1.2

David Grove added a comment - 03/Feb/11 7:42 AM defer all non-critical 2.1.2 issues to 2.2.

Vijay Saraswat added a comment - 17/Feb/11 6:46 PM Implementation issue, not a language design issue.

Igor Peshansky added a comment - 11/Mar/11 12:24 PM - edited The test case now compiles, but fails to mark the variable as asynchronously-initialized, which causes the backends to generate incorrect code. The Java post-compiler catches the error: 1. ERROR in out/XTENLANG_1942.java (at line 33) $Closure$0(((int)(x)))))); ^^^ The local variable x may not have been initialized ---------- 2. ERROR in out/XTENLANG_1942.java (at line 37) x; ^ The local variable x may not have been initialized ---------- 2 problems (2 errors) and the C++ code will just silently fail at runtime. Bumping to critical.

Yoav Zibin added a comment - 11/Mar/11 5:06 PM In revision 20663: reporting an error for "val" that are assigned across "at" in a different place setting async-init for val and var that are assigned across an "at" However, the java backend still has post-compilation errors (even though both x_tmp1 and x_tmp2 are marked as setAsyncInit): class TestValInitUsingAt { static def testVal() { val x_tmp1:Int; val p = here; at (p.next()) at (p) x_tmp1 = 2; val x = x_tmp1; } static def testVar() { var x_tmp2:Int; val p = here; at (p.next()) at (p) x_tmp2 = 2; val x = x_tmp2; } } : ---------- 1. ERROR in C:\cygwin\home\Yoav\test\TestValInitUsingAt.java (at line 42) (( int )(x_tmp1)))))); ^^^^^^^^ The local variable x_tmp1 may not have been initialized ---------- 2. ERROR in C:\cygwin\home\Yoav\test\TestValInitUsingAt.java (at line 46) x_tmp1; ^^^^^^ The local variable x_tmp1 may not have been initialized ---------- 2 problems (2 errors)

Yoav Zibin added a comment - 14/Mar/11 1:53 PM The C++ backend doesn't crash, but it prints the Int as a pointer: $ X10_NPLACES=2 runx10 ./a.exe 11406832

David Grove added a comment - 15/Mar/11 4:55 PM setting asyncInit on the local def isn't enough information for the backend. We also need the asyncInitVal stuffed into the extension information somewhere. The reason is a piece of code like this: static def testVal() { val x_tmp1:Int; val p = here; at (p.next()) at (p) x_tmp1 = 2; val x = x_tmp1; Console.OUT.println(""+x); at (p.next()) at (p) Console.OUT.println( "There and back " +x_tmp1); } In the first at we have to capture the lval for x_tmp1 so that it can be initialized (mutated) within the at. In the second, we have to cature the rval for x_tmp1 so that it can be read within the at. And if x_tmp1 were an object type, then we would need it to be properly serialized in the second case, but not the first. Maybe I missed it, but I didn't see where this was being done. The setter for asyncInitVal is only being called in the lower in visitFinish. I think similar thing needs to be done for AtStmt and AtExpr.

David Grove added a comment - 15/Mar/11 4:57 PM - edited passing back to Yoav for clarification on whether or not initVals is being propagated for at's in the same way it is for finish in the Lowerer

Yoav Zibin added a comment - 17/Mar/11 2:39 PM Again I don't understand why this has anything to do with the type-checking phase. I actually reject the whole notion of asyncInit and I wish to remove it from the type-checking phase. I objected to it in the beginning, there was a big fight with Igor and Toshio, and I cave in. I really don't understand why I need to understand backend considerations in the front-end. This ping pong has to stop - I wish to remove this entire asyncInitVal from the front-end, because we do not use it, we do not test it, and I don't care about it. Reassigning back to Dave. This is old discussions/arguments we had on asyncInitVal (look how much time I wasted on this thing which has nothing to do with the front-end!): Yoav, We noticed that we need to generate the code of backing store from boxed variables to the original final variables just after the finish block, not after the async block, since from the semantics, the statements within the async block are not necessarily executed (completed) just after the async block. Also, if async blocks are executed within some conditional statements (as shown below), the only location we can generate the backing store code is after the enclosing finish block. val x : Int; finish { if (A) async { x = 10; } else async { x = 20; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); if (A) runAsync ( $x[0] = 10; ) else runAsync ( $x[0] = 20; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; Thus, it would be helpful if you can move the information of async-initialized vars (Set<VarDef>) currently attached in the async-node to the finish-node instead? If there are multiple such variables from several asyncs within a finish node, please include all those variables in the finish-node scope. If finish-async blocks are nested, One more question is about uncounted async. Is it possible that an uncounted async and a normal async are within a finish block and each initializes different variables, as shown below? Since the uncounted async will not be blocked at stopFinish(), either of the async block could be uncompleted yet after the finish block, and thus the backing store generated there could be ineffective. Could you please clarify that 1) can uncounted asyncs perform variable initialization? and 2) what is the execution behavior when the uncounted async is finished earlier than the normal async in the example below, i.e. the statements after the finish will be executed without waiting the normal async completion? val x : Int; val y: Int; finish { @Uncounted async { x = 10; } async { y = 20; } } Thank you, --Toshio ----- Forwarded by Toshio Suganuma/Japan/IBM on 2010/09/24 19:18 ----- From: Toshio Suganuma/Japan/IBM To: Yoav Zibin <yoav.zibin@gmail.com>, Igor Peshansky/Watson/IBM@IBMUS Cc: Mikio Takeuchi/Japan/IBM@IBMJP, Yuki Makino/Japan/IBM, David P Grove/Watson/IBM@IBMUS Date: 2010/09/14 02:01 Subject: Re: Fw: Question about finish-async initialization Yoav, Thank you for your quick reply. Since Async_c nodes are converted to closures in the desugarer phase, I will move this information to Closure_c nodes using Annotation. Igor, I'm not sure how you implement async initialization in the C++ backend, but are you going to use this information as well? Please let me know if you have any suggestion for better way to transfer the Async node information to the code generation phase. Thank you, --Toshio From: Yoav Zibin <yoav.zibin@gmail.com> To: Toshio Suganuma/Japan/IBM@IBMJP Date: 2010/09/11 04:52 Subject: Re: Fw: Question about finish-async initialization Sure, no problems. public class Async_c extends Stmt_c implements Async { /* For example: val x:Int; finish async { x = 42; } // "x" can either be boxed or be passed (to the async closure) by ref, because we need to assign to it. It cannot be passed by value. async { val y = x; } // "x" can be passed by value or be be boxed. It cannot be passed by ref because the async outlives the var "x" . */ public Set<VarDef> asyncInitVal = null ; // used by the backend to know whether to pass a var to an async closure by ref or by value If you want a boolean flag on the VarDef_c, let me know. 2010/9/10 Toshio Suganuma <SUGANUMA@jp.ibm.com> Hi Yoav, I will start working for the Java backend problem around the finish-async initialization. Can you please let me know how we can get the list of those variables at the async node that need to be initialized within the async block? Thank you, --Toshio ----- Forwarded by Yuki Makino/Japan/IBM on 2010/09/09 16:52 ----- From: Yoav Zibin <yoav.zibin@gmail.com> To: Yuki Makino/Japan/IBM@IBMJP Cc: Yoav Zibin <yzibin@us.ibm.com>, Igor Peshansky <igorp@us.ibm.com>, David P Grove <groved@us.ibm.com>, Mikio Takeuchi/Japan/IBM@IBMJP Date: 2010/09/04 01:58 Subject: Re: Question about finish-async initialization Consider this : Val x:Int; Finish Async x=1; async Val z =x; So x should not be marked, but instead I marked the first Async that it inits x. I can also mark it if you want :) Thanks, Yoav Zibin On 3 &#1489;&#1505;&#1508;&#1496; 2010, at 08:54, Yuki Makino <MAKINO@jp.ibm.com> wrote: Hi, Yoav. I'm implementing to handle finish-async initialization of local vals in the Java back-end. I'd like to know whether a local val is initialized asynchronously for the work. So, could you tell how to get the information that a local val is initialized inside async block. Is there any mark at the LocalDecl node? Yuki MAKINO / X10 Compiler , IM, Yamato Software Development Laboratory, IBM Japan Toshio Suganuma <SUGANUMA@jp.ibm.com> Fri, Sep 24, 2010 at 8:01 AM To: Yoav Zibin <yoav.zibin@gmail.com> Cc: Mikio Takeuchi <MTAKE@jp.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, David P Grove <groved@us.ibm.com>, Igor Peshansky <igorp@us.ibm.com> <Sorry, the previous mail was accidentally sent with a incomplete status> [Quoted text hidden] the finish-node scope. If finish-async blocks are nested, each finish node to be attached with those variables initialized at the current nest level. Could you please make these changes in the front-end? [Quoted text hidden] Igor Peshansky <igorp@us.ibm.com> Fri, Sep 24, 2010 at 9:56 AM To: Toshio Suganuma <SUGANUMA@jp.ibm.com> Cc: David P Grove <groved@us.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Yoav Zibin <yoav.zibin@gmail.com>, Yuki Makino <MAKINO@jp.ibm.com> Toshio, Unfortunately, you would need this information at every point of definite assignment (e.g., inside the async after the assignment itself, etc). Yoav, is it possible to add that set to every node where the definitely assigned variables first appear in the data flow info? Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Toshio Suganuma/Japan/IBM@IBMJP 09/24/2010 07:53 AM To Yoav Zibin <yoav.zibin@gmail.com> cc Mikio Takeuchi/Japan/IBM@IBMJP, Yuki Makino/Japan/IBM, David P Grove/Watson/IBM@IBMUS, Igor Peshansky/Watson/IBM@IBMUS Subject Fw: Question about finish-async initialization Yoav, We noticed that we need to generate the code of backing store from boxed variables to the original final variables just after the finish block, not after the async block, since from the semantics, the statements within the async block are not necessarily executed (completed) just after the async block. Also, if async blocks are executed within some conditional statements (as shown below), the only location we can generate the backing store code is after the enclosing finish block. val x : Int; finish { if (A) async { x = 10; } else async { x = 20; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); if (A) runAsync ( $x[0] = 10; ) else runAsync ( $x[0] = 20; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; Thus, it would be helpful if you can move the information of async-initialized vars (Set<VarDef>) currently attached in the async-node to the finish-node instead? If there are multiple such variables from several asyncs within a finish node, please include all those variables in the finish-node scope. If finish-async blocks are nested, [Quoted text hidden] Yoav Zibin <yoav.zibin@gmail.com> Fri, Sep 24, 2010 at 11:05 AM To: Igor Peshansky <igorp@us.ibm.com> Cc: Toshio Suganuma <SUGANUMA@jp.ibm.com>, David P Grove <groved@us.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com> No problem Toshio, I've committed it. How will you handle this kind of code: val x : Int; finish async { finish async { x = 10; val y = x+1; } val z = x+1; } val w = x+1; ? Which "finish" will have "x" in its set? Sadly from the dataflow perspective, there is no difference between the two "finishes" . The flow after: x = 10; or finish async x=10; is the same (in both cases "x" is initialized). Therefore these two finishes have exactly the same in&out flow: finish x=10; finish finish x=10; So, I've added "x" to both finishes. This should be enough: when you first see a Finish node for var "x" , then mark that var and emit the extra $x[] (so need to mark that var so you won't emit $x again for the second finish), and until you encounter that finish again, then every assignment and every access uses $x[0] instead. After that finish, emit "x = $x[0];" . Does it make sense? Igor, I don't think they need any extra info. They can only generate this code for accesses inside the async: val x : Int; finish { async { x = 10; val y = x+1; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); runAsync ( $x[0] = 10; final int y = $x[0]+1; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; [Quoted text hidden] Igor Peshansky <igorp@us.ibm.com> Fri, Sep 24, 2010 at 11:23 AM To: Yoav Zibin <yoav.zibin@gmail.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> Yoav, See my previous message. You need to add this set in *every place* where the dataflow determines that the variable is definitely assigned. Fortunately, it's possible to always insert the kind of code that Toshio wants to use in all of those places, because the scopes will never intersect. Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 11:05 AM To Igor Peshansky/Watson/IBM@IBMUS cc Toshio Suganuma <SUGANUMA@jp.ibm.com>, David P Grove/Watson/IBM@IBMUS, Mikio Takeuchi <MTAKE@jp.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization No problem Toshio, I've committed it. How will you handle this kind of code: val x : Int; finish async { finish async { x = 10; val y = x+1; } val z = x+1; } val w = x+1; ? Which "finish" will have "x" in its set? Sadly from the dataflow perspective, there is no difference between the two "finishes" . The flow after: x = 10; or finish async x=10; is the same (in both cases "x" is initialized). Therefore these two finishes have exactly the same in&out flow: finish x=10; finish finish x=10; So, I've added "x" to both finishes. This should be enough: when you first see a Finish node for var "x" , then mark that var and emit the extra $x[] (so need to mark that var so you won't emit $x again for the second finish), and until you encounter that finish again, then every assignment and every access uses $x[0] instead. After that finish, emit "x = $x[0];" . Does it make sense? Igor, I don't think they need any extra info. They can only generate this code for accesses inside the async: val x : Int; finish { async { x = 10; val y = x+1; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); runAsync ( $x[0] = 10; final int y = $x[0]+1; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; 2010/9/24 Igor Peshansky <igorp@us.ibm.com> Toshio, Unfortunately, you would need this information at every point of definite assignment (e.g., inside the async after the assignment itself, etc). Yoav, is it possible to add that set to every node where the definitely assigned variables first appear in the data flow info? Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Toshio Suganuma/Japan/IBM@IBMJP 09/24/2010 07:53 AM To Yoav Zibin <yoav.zibin@gmail.com> cc Mikio Takeuchi/Japan/IBM@IBMJP, Yuki Makino/Japan/IBM, David P Grove/Watson/IBM@IBMUS, Igor Peshansky/Watson/IBM@IBMUS Subject Fw: Question about finish-async initialization Yoav, We noticed that we need to generate the code of backing store from boxed variables to the original final variables just after the finish block, not after the async block, since from the semantics, the statements within the async block are not necessarily executed (completed) just after the async block. Also, if async blocks are executed within some conditional statements (as shown below), the only location we can generate the backing store code is after the enclosing finish block. val x : Int; finish { if (A) async { x = 10; } else async { x = 20; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); if (A) runAsync ( $x[0] = 10; ) else runAsync ( $x[0] = 20; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; Thus, it would be helpful if you can move the information of async-initialized vars (Set<VarDef>) currently attached in the async-node to the finish-node instead? If there are multiple such variables from several asyncs within a finish node, please include all those variables in the finish-node scope. If finish-async blocks are nested, One more question is about uncounted async. Is it possible that an uncounted async and a normal async are within a finish block and each initializes different variables, as shown below? Since the uncounted async will not be blocked at stopFinish(), either of the async block could be uncompleted yet after the finish block, and thus the backing store generated there could be ineffective. Could you please clarify that 1) can uncounted asyncs perform variable initialization? and 2) what is the execution behavior when the uncounted async is finished earlier than the normal async in the example below, i.e. the statements after the finish will be executed without waiting the normal async completion? val x : Int; val y: Int; finish { @Uncounted async { x = 10; } async { y = 20; } } Thank you, --Toshio ----- Forwarded by Toshio Suganuma/Japan/IBM on 2010/09/24 19:18 ----- From: Toshio Suganuma/Japan/IBM To: Yoav Zibin <yoav.zibin@gmail.com>, Igor Peshansky/Watson/IBM@IBMUS Cc: Mikio Takeuchi/Japan/IBM@IBMJP, Yuki Makino/Japan/IBM, David P Grove/Watson/IBM@IBMUS Date: 2010/09/14 02:01 Subject: Re: Fw: Question about finish-async initialization Yoav, Thank you for your quick reply. Since Async_c nodes are converted to closures in the desugarer phase, I will move this information to Closure_c nodes using Annotation. Igor, I'm not sure how you implement async initialization in the C++ backend, but are you going to use this information as well? Please let me know if you have any suggestion for better way to transfer the Async node information to the code generation phase. Thank you, --Toshio From: Yoav Zibin <yoav.zibin@gmail.com> To: Toshio Suganuma/Japan/IBM@IBMJP Date: 2010/09/11 04:52 Subject: Re: Fw: Question about finish-async initialization Sure, no problems. public class Async_c extends Stmt_c implements Async { /* For example: val x:Int; finish async { x = 42; } // "x" can either be boxed or be passed (to the async closure) by ref, because we need to assign to it. It cannot be passed by value. async { val y = x; } // "x" can be passed by value or be be boxed. It cannot be passed by ref because the async outlives the var "x" . */ public Set<VarDef> asyncInitVal = null ; // used by the backend to know whether to pass a var to an async closure by ref or by value If you want a boolean flag on the VarDef_c, let me know. 2010/9/10 Toshio Suganuma <SUGANUMA@jp.ibm.com> Hi Yoav, I will start working for the Java backend problem around the finish-async initialization. Can you please let me know how we can get the list of those variables at the async node that need to be initialized within the async block? Thank you, --Toshio ----- Forwarded by Yuki Makino/Japan/IBM on 2010/09/09 16:52 ----- From: Yoav Zibin <yoav.zibin@gmail.com> To: Yuki Makino/Japan/IBM@IBMJP Cc: Yoav Zibin <yzibin@us.ibm.com>, Igor Peshansky <igorp@us.ibm.com>, David P Grove <groved@us.ibm.com>, Mikio Takeuchi/Japan/IBM@IBMJP Date: 2010/09/04 01:58 Subject: Re: Question about finish-async initialization Consider this : Val x:Int; Finish Async x=1; async Val z =x; So x should not be marked, but instead I marked the first Async that it inits x. I can also mark it if you want :) Thanks, Yoav Zibin On 3 &#1489;&#1505;&#1508;&#1496; 2010, at 08:54, Yuki Makino <MAKINO@jp.ibm.com> wrote: Hi, Yoav. I'm implementing to handle finish-async initialization of local vals in the Java back-end. I'd like to know whether a local val is initialized asynchronously for the work. So, could you tell how to get the information that a local val is initialized inside async block. Is there any mark at the LocalDecl node? Yuki MAKINO / X10 Compiler , IM, Yamato Software Development Laboratory, IBM Japan Yoav Zibin <yoav.zibin@gmail.com> Fri, Sep 24, 2010 at 11:36 AM To: Igor Peshansky <igorp@us.ibm.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> I'm not sure I flow your proposal (see my previous message :) How will it help Toshio that I'll mark everything as definitely assigned? (every place "x" is used, then "x" is definitely assigned, or else we wouldn't proceed to code generation) Please send an example with the corresponding code generated by the Java backend (so I'll understand what you mean). [Quoted text hidden] Igor Peshansky <igorp@us.ibm.com> Fri, Sep 24, 2010 at 11:46 AM To: Yoav Zibin <yoav.zibin@gmail.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> Yoav, The point is: Toshio wants to insert a Java-level final variable declaration that will cache the assigned value of the X10 variable (instead of keeping it boxed). He needs to do this at the earliest point of definite assignment (i.e., after the assignment itself, and after every synchronization construct that guarantees the execution of that assignment, e.g., finish, next, etc). The dataflow analysis computes definite assignment results for every Stmt node. Whenever those results indicate that a variable has been definitely assigned (and it hasn't been prior to that node), that variable needs to be added to the definite assignment set * for that node* ( this uses the semantics "the variable is definitely assigned from this point on within this scope" for that set). Then, when Toshio is visiting the AST, he can query that set for any given node, and if the set is non-empty, insert a cached varaible declaration there. I hope this makes sense. Yes, they can generate boxed accesses within the async, but for programs that perform a lot of calculations in the body of the async this is not very optimal (and we have that info, so why not provide it?). Finally, when our dataflow starts considering, e.g., "next" statements, we would then have to add such sets to those as well. If you add this set to the extension node, no other code would need to change as the dataflow becomes more sophisticated. Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 11:36 AM To Igor Peshansky/Watson/IBM@IBMUS cc David P Grove/Watson/IBM@IBMUS, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization I'm not sure I flow your proposal (see my previous message :) How will it help Toshio that I'll mark everything as definitely assigned? (every place "x" is used, then "x" is definitely assigned, or else we wouldn't proceed to code generation) Please send an example with the corresponding code generated by the Java backend (so I'll understand what you mean). 2010/9/24 Igor Peshansky <igorp@us.ibm.com> Yoav, See my previous message. You need to add this set in *every place* where the dataflow determines that the variable is definitely assigned. Fortunately, it's possible to always insert the kind of code that Toshio wants to use in all of those places, because the scopes will never intersect. Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 11:05 AM To Igor Peshansky/Watson/IBM@IBMUS cc Toshio Suganuma <SUGANUMA@jp.ibm.com>, David P Grove/Watson/IBM@IBMUS, Mikio Takeuchi <MTAKE@jp.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization No problem Toshio, I've committed it. How will you handle this kind of code: val x : Int; finish async { finish async { x = 10; val y = x+1; } val z = x+1; } val w = x+1; ? Which "finish" will have "x" in its set? Sadly from the dataflow perspective, there is no difference between the two "finishes" . The flow after: x = 10; or finish async x=10; is the same (in both cases "x" is initialized). Therefore these two finishes have exactly the same in&out flow: finish x=10; finish finish x=10; So, I've added "x" to both finishes. This should be enough: when you first see a Finish node for var "x" , then mark that var and emit the extra $x[] (so need to mark that var so you won't emit $x again for the second finish), and until you encounter that finish again, then every assignment and every access uses $x[0] instead. After that finish, emit "x = $x[0];" . Does it make sense? Igor, I don't think they need any extra info. They can only generate this code for accesses inside the async: val x : Int; finish { async { x = 10; val y = x+1; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); runAsync ( $x[0] = 10; final int y = $x[0]+1; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; 2010/9/24 Igor Peshansky <igorp@us.ibm.com> Toshio, Unfortunately, you would need this information at every point of definite assignment (e.g., inside the async after the assignment itself, etc). Yoav, is it possible to add that set to every node where the definitely assigned variables first appear in the data flow info? Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Toshio Suganuma/Japan/IBM@IBMJP 09/24/2010 07:53 AM To Yoav Zibin <yoav.zibin@gmail.com> cc Mikio Takeuchi/Japan/IBM@IBMJP, Yuki Makino/Japan/IBM, David P Grove/Watson/IBM@IBMUS, Igor Peshansky/Watson/IBM@IBMUS Subject Fw: Question about finish-async initialization Yoav, We noticed that we need to generate the code of backing store from boxed variables to the original final variables just after the finish block, not after the async block, since from the semantics, the statements within the async block are not necessarily executed (completed) just after the async block. Also, if async blocks are executed within some conditional statements (as shown below), the only location we can generate the backing store code is after the enclosing finish block. val x : Int; finish { if (A) async { x = 10; } else async { x = 20; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); if (A) runAsync ( $x[0] = 10; ) else runAsync ( $x[0] = 20; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; Thus, it would be helpful if you can move the information of async-initialized vars (Set<VarDef>) currently attached in the async-node to the finish-node instead? If there are multiple such variables from several asyncs within a finish node, please include all those variables in the finish-node scope. If finish-async blocks are nested, One more question is about uncounted async. Is it possible that an uncounted async and a normal async are within a finish block and each initializes different variables, as shown below? Since the uncounted async will not be blocked at stopFinish(), either of the async block could be uncompleted yet after the finish block, and thus the backing store generated there could be ineffective. Could you please clarify that 1) can uncounted asyncs perform variable initialization? and 2) what is the execution behavior when the uncounted async is finished earlier than the normal async in the example below, i.e. the statements after the finish will be executed without waiting the normal async completion? val x : Int; val y: Int; finish { @Uncounted async { x = 10; } async { y = 20; } } Thank you, --Toshio ----- Forwarded by Toshio Suganuma/Japan/IBM on 2010/09/24 19:18 ----- From: Toshio Suganuma/Japan/IBM To: Yoav Zibin <yoav.zibin@gmail.com>, Igor Peshansky/Watson/IBM@IBMUS Cc: Mikio Takeuchi/Japan/IBM@IBMJP, Yuki Makino/Japan/IBM, David P Grove/Watson/IBM@IBMUS Date: 2010/09/14 02:01 Subject: Re: Fw: Question about finish-async initialization Yoav, Thank you for your quick reply. Since Async_c nodes are converted to closures in the desugarer phase, I will move this information to Closure_c nodes using Annotation. Igor, I'm not sure how you implement async initialization in the C++ backend, but are you going to use this information as well? Please let me know if you have any suggestion for better way to transfer the Async node information to the code generation phase. Thank you, --Toshio From: Yoav Zibin <yoav.zibin@gmail.com> To: Toshio Suganuma/Japan/IBM@IBMJP Date: 2010/09/11 04:52 Subject: Re: Fw: Question about finish-async initialization Sure, no problems. public class Async_c extends Stmt_c implements Async { /* For example: val x:Int; finish async { x = 42; } // "x" can either be boxed or be passed (to the async closure) by ref, because we need to assign to it. It cannot be passed by value. async { val y = x; } // "x" can be passed by value or be be boxed. It cannot be passed by ref because the async outlives the var "x" . */ public Set<VarDef> asyncInitVal = null ; // used by the backend to know whether to pass a var to an async closure by ref or by value If you want a boolean flag on the VarDef_c, let me know. 2010/9/10 Toshio Suganuma <SUGANUMA@jp.ibm.com> Hi Yoav, I will start working for the Java backend problem around the finish-async initialization. Can you please let me know how we can get the list of those variables at the async node that need to be initialized within the async block? Thank you, --Toshio ----- Forwarded by Yuki Makino/Japan/IBM on 2010/09/09 16:52 ----- From: Yoav Zibin <yoav.zibin@gmail.com> To: Yuki Makino/Japan/IBM@IBMJP Cc: Yoav Zibin <yzibin@us.ibm.com>, Igor Peshansky <igorp@us.ibm.com>, David P Grove <groved@us.ibm.com>, Mikio Takeuchi/Japan/IBM@IBMJP Date: 2010/09/04 01:58 Subject: Re: Question about finish-async initialization Consider this : Val x:Int; Finish Async x=1; async Val z =x; So x should not be marked, but instead I marked the first Async that it inits x. I can also mark it if you want :) Thanks, Yoav Zibin On 3 &#1489;&#1505;&#1508;&#1496; 2010, at 08:54, Yuki Makino <MAKINO@jp.ibm.com> wrote: Hi, Yoav. I'm implementing to handle finish-async initialization of local vals in the Java back-end. I'd like to know whether a local val is initialized asynchronously for the work. So, could you tell how to get the information that a local val is initialized inside async block. Is there any mark at the LocalDecl node? Yuki MAKINO / X10 Compiler , IM, Yamato Software Development Laboratory, IBM Japan Yoav Zibin <yoav.zibin@gmail.com> Fri, Sep 24, 2010 at 12:36 PM To: Igor Peshansky <igorp@us.ibm.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> No, it still doesn't make sense. I think you can do code generation with the set I stored in the Finish node. Let's look at an example: val x; blabla... finish { async { async { finish { async { blabla... if (foo) x=1; else x=2; for (...) val y=x; } } for (...) val z=x; } } } for (...) val w=x; Then the generated code should be: final int x; blabla... final int [] $x; // "x" is in the finish's set, so we create a box, and push it into some codegen stack startFinish(); runAsync( // in an anonymous class, so we need a new cache for everything in the codegen stack. final int $cache_x0; runAsync( // in an anonymous class, so ... final int $cache_x1; startFinish(); runAsync( // in an anonymous class, so ... final int $cache_x2; blabla... if (foo) $x[0]=$cache_x2=1; else $x[0]=$cache_x2=2; // points of the write for (...) val y=$cache_x2; ) stopFinish(); $cache_x1 = $x[0]; // write to current cache after every stopFinish() for (...) val z=$cache_x1; ) ) stopFinish(); x = $x[0]; // write to current cache after every stopFinish() for (...) val w=x; So $x[] is the box, and "x" and $cache_xN are the cached final value. You cache once after every stopFinish, and you start a new cache every scope (so at the declaration point and after every runAsync). Note how $cache_x0 is not used and not assigned (so javac will not complain, and will simply remove it). Hope that clears my understanding of the codegen :) [Quoted text hidden] Igor Peshansky <igorp@us.ibm.com> Fri, Sep 24, 2010 at 12:48 PM To: Yoav Zibin <yoav.zibin@gmail.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> How does the Java backend know where it should declare the various $cache_x* variables? How does it know that references to "x" need to be changed to use the $cache_x* variables (without complex bookkeeping)? If you provide the information I've requested, then the If statement and both Finish statements will have "x" in their "definitely assigned after this point" set, and so the Java backend can generate the following: final int [] $x; // "x" is marked as asynchronously initialized, so we create a box blabla... startFinish(); runAsync( runAsync( startFinish(); runAsync( blabla... if (foo) $x[0]=1; else $x[0]=2; // points of the write. Incidentally, those assignments live in Eval nodes, so if "x" is used within the branches of the " if " , the rules below also apply final int x = $x[0]; // "x" is in the set stored in the " if " statement node, so right after that node it can be cached in the variable with the real value for (...) val y=x; // no changes to codegen required here ) stopFinish(); final int x = $x[0]; // "x" is in the set stored in the "finish" statement node, so ... for (...) val z=x; // no changes to codegen required here ) ) stopFinish(); final int x = $x[0]; // "x" is in the set stored in the "finish" statement node, so ... for (...) val w=x; There is no need to declare " final int x" before it is definitely initialized. This is the scheme Takeuchi-san and I discussed during his visit. Igor P.S. I missed some other use cases -- this is needed not only for Eval statements, but also for If statements, Switch statements, and probably other control flow, e.g., Do/ while statements. Putting it in the X10Ext_c sounds more and more like the right thing to do . -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 12:36 PM To Igor Peshansky/Watson/IBM@IBMUS cc David P Grove/Watson/IBM@IBMUS, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization No, it still doesn't make sense. I think you can do code generation with the set I stored in the Finish node. Let's look at an example: val x; blabla... finish { async { async { finish { async { blabla... if (foo) x=1; else x=2; for (...) val y=x; } } for (...) val z=x; } } } for (...) val w=x; Then the generated code should be: final int x; blabla... final int [] $x; // "x" is in the finish's set, so we create a box, and push it into some codegen stack startFinish(); runAsync( // in an anonymous class, so we need a new cache for everything in the codegen stack. final int $cache_x0; runAsync( // in an anonymous class, so ... final int $cache_x1; startFinish(); runAsync( // in an anonymous class, so ... final int $cache_x2; blabla... if (foo) $x[0]=$cache_x2=1; else $x[0]=$cache_x2=2; // points of the write for (...) val y=$cache_x2; ) stopFinish(); $cache_x1 = $x[0]; // write to current cache after every stopFinish() for (...) val z=$cache_x1; ) ) stopFinish(); x = $x[0]; // write to current cache after every stopFinish() for (...) val w=x; So $x[] is the box, and "x" and $cache_xN are the cached final value. You cache once after every stopFinish, and you start a new cache every scope (so at the declaration point and after every runAsync). Note how $cache_x0 is not used and not assigned (so javac will not complain, and will simply remove it). Hope that clears my understanding of the codegen :) 2010/9/24 Igor Peshansky <igorp@us.ibm.com> Yoav, The point is: Toshio wants to insert a Java-level final variable declaration that will cache the assigned value of the X10 variable (instead of keeping it boxed). He needs to do this at the earliest point of definite assignment (i.e., after the assignment itself, and after every synchronization construct that guarantees the execution of that assignment, e.g., finish, next, etc). The dataflow analysis computes definite assignment results for every Stmt node. Whenever those results indicate that a variable has been definitely assigned (and it hasn't been prior to that node), that variable needs to be added to the definite assignment set * for that node* ( this uses the semantics "the variable is definitely assigned from this point on within this scope" for that set). Then, when Toshio is visiting the AST, he can query that set for any given node, and if the set is non-empty, insert a cached varaible declaration there. I hope this makes sense. Yes, they can generate boxed accesses within the async, but for programs that perform a lot of calculations in the body of the async this is not very optimal (and we have that info, so why not provide it?). Finally, when our dataflow starts considering, e.g., "next" statements, we would then have to add such sets to those as well. If you add this set to the extension node, no other code would need to change as the dataflow becomes more sophisticated. Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 11:36 AM To Igor Peshansky/Watson/IBM@IBMUS cc David P Grove/Watson/IBM@IBMUS, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization I'm not sure I flow your proposal (see my previous message :) How will it help Toshio that I'll mark everything as definitely assigned? (every place "x" is used, then "x" is definitely assigned, or else we wouldn't proceed to code generation) Please send an example with the corresponding code generated by the Java backend (so I'll understand what you mean). 2010/9/24 Igor Peshansky <igorp@us.ibm.com> Yoav, See my previous message. You need to add this set in *every place* where the dataflow determines that the variable is definitely assigned. Fortunately, it's possible to always insert the kind of code that Toshio wants to use in all of those places, because the scopes will never intersect. Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 11:05 AM To Igor Peshansky/Watson/IBM@IBMUS cc Toshio Suganuma <SUGANUMA@jp.ibm.com>, David P Grove/Watson/IBM@IBMUS, Mikio Takeuchi <MTAKE@jp.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization No problem Toshio, I've committed it. How will you handle this kind of code: val x : Int; finish async { finish async { x = 10; val y = x+1; } val z = x+1; } val w = x+1; ? Which "finish" will have "x" in its set? Sadly from the dataflow perspective, there is no difference between the two "finishes" . The flow after: x = 10; or finish async x=10; is the same (in both cases "x" is initialized). Therefore these two finishes have exactly the same in&out flow: finish x=10; finish finish x=10; So, I've added "x" to both finishes. This should be enough: when you first see a Finish node for var "x" , then mark that var and emit the extra $x[] (so need to mark that var so you won't emit $x again for the second finish), and until you encounter that finish again, then every assignment and every access uses $x[0] instead. After that finish, emit "x = $x[0];" . Does it make sense? Igor, I don't think they need any extra info. They can only generate this code for accesses inside the async: val x : Int; finish { async { x = 10; val y = x+1; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); runAsync ( $x[0] = 10; final int y = $x[0]+1; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; 2010/9/24 Igor Peshansky <igorp@us.ibm.com> Toshio, Unfortunately, you would need this information at every point of definite assignment (e.g., inside the async after the assignment itself, etc). Yoav, is it possible to add that set to every node where the definitely assigned variables first appear in the data flow info? Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Toshio Suganuma/Japan/IBM@IBMJP 09/24/2010 07:53 AM To Yoav Zibin <yoav.zibin@gmail.com> cc Mikio Takeuchi/Japan/IBM@IBMJP, Yuki Makino/Japan/IBM, David P Grove/Watson/IBM@IBMUS, Igor Peshansky/Watson/IBM@IBMUS Subject Fw: Question about finish-async initialization Yoav, We noticed that we need to generate the code of backing store from boxed variables to the original final variables just after the finish block, not after the async block, since from the semantics, the statements within the async block are not necessarily executed (completed) just after the async block. Also, if async blocks are executed within some conditional statements (as shown below), the only location we can generate the backing store code is after the enclosing finish block. val x : Int; finish { if (A) async { x = 10; } else async { x = 20; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); if (A) runAsync ( $x[0] = 10; ) else runAsync ( $x[0] = 20; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; Thus, it would be helpful if you can move the information of async-initialized vars (Set<VarDef>) currently attached in the async-node to the finish-node instead? If there are multiple such variables from several asyncs within a finish node, please include all those variables in the finish-node scope. If finish-async blocks are nested, One more question is about uncounted async. Is it possible that an uncounted async and a normal async are within a finish block and each initializes different variables, as shown below? Since the uncounted async will not be blocked at stopFinish(), either of the async block could be uncompleted yet after the finish block, and thus the backing store generated there could be ineffective. Could you please clarify that 1) can uncounted asyncs perform variable initialization? and 2) what is the execution behavior when the uncounted async is finished earlier than the normal async in the example below, i.e. the statements after the finish will be executed without waiting the normal async completion? val x : Int; val y: Int; finish { @Uncounted async { x = 10; } async { y = 20; } } Thank you, --Toshio ----- Forwarded by Toshio Suganuma/Japan/IBM on 2010/09/24 19:18 ----- From: Toshio Suganuma/Japan/IBM To: Yoav Zibin <yoav.zibin@gmail.com>, Igor Peshansky/Watson/IBM@IBMUS Cc: Mikio Takeuchi/Japan/IBM@IBMJP, Yuki Makino/Japan/IBM, David P Grove/Watson/IBM@IBMUS Date: 2010/09/14 02:01 Subject: Re: Fw: Question about finish-async initialization Yoav, Thank you for your quick reply. Since Async_c nodes are converted to closures in the desugarer phase, I will move this information to Closure_c nodes using Annotation. Igor, I'm not sure how you implement async initialization in the C++ backend, but are you going to use this information as well? Please let me know if you have any suggestion for better way to transfer the Async node information to the code generation phase. Thank you, --Toshio From: Yoav Zibin <yoav.zibin@gmail.com> To: Toshio Suganuma/Japan/IBM@IBMJP Date: 2010/09/11 04:52 Subject: Re: Fw: Question about finish-async initialization Sure, no problems. public class Async_c extends Stmt_c implements Async { /* For example: val x:Int; finish async { x = 42; } // "x" can either be boxed or be passed (to the async closure) by ref, because we need to assign to it. It cannot be passed by value. async { val y = x; } // "x" can be passed by value or be be boxed. It cannot be passed by ref because the async outlives the var "x" . */ public Set<VarDef> asyncInitVal = null ; // used by the backend to know whether to pass a var to an async closure by ref or by value If you want a boolean flag on the VarDef_c, let me know. 2010/9/10 Toshio Suganuma <SUGANUMA@jp.ibm.com> Hi Yoav, I will start working for the Java backend problem around the finish-async initialization. Can you please let me know how we can get the list of those variables at the async node that need to be initialized within the async block? Thank you, --Toshio ----- Forwarded by Yuki Makino/Japan/IBM on 2010/09/09 16:52 ----- From: Yoav Zibin <yoav.zibin@gmail.com> To: Yuki Makino/Japan/IBM@IBMJP Cc: Yoav Zibin <yzibin@us.ibm.com>, Igor Peshansky <igorp@us.ibm.com>, David P Grove <groved@us.ibm.com>, Mikio Takeuchi/Japan/IBM@IBMJP Date: 2010/09/04 01:58 Subject: Re: Question about finish-async initialization Consider this : Val x:Int; Finish Async x=1; async Val z =x; So x should not be marked, but instead I marked the first Async that it inits x. I can also mark it if you want :) Thanks, Yoav Zibin On 3 &#1489;&#1505;&#1508;&#1496; 2010, at 08:54, Yuki Makino <MAKINO@jp.ibm.com> wrote: Hi, Yoav. I'm implementing to handle finish-async initialization of local vals in the Java back-end. I'd like to know whether a local val is initialized asynchronously for the work. So, could you tell how to get the information that a local val is initialized inside async block. Is there any mark at the LocalDecl node? Yuki MAKINO / X10 Compiler , IM, Yamato Software Development Laboratory, IBM Japan Yoav Zibin <yoav.zibin@gmail.com> Fri, Sep 24, 2010 at 1:19 PM To: Igor Peshansky <igorp@us.ibm.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> Ok, I understand your proposal. Now please understand mine because it is more efficient (and requires less effort to implement). No need for any book keeping except asyncInitVal in Finish nodes, and a codegen stack that tracks what is the current cached value (the current cache is at the top of the stack). You declare "x" as normal, and you declare $cache_x* at the beginning of every async ( for every var in the codegen stack). At every stopFinish() you write to the current cached value (either $cached_x* or "x" ) ( if you haven't done so, in case someone uses the stupid pattern: finish finish ... Therefore we do the write only after the first stopFinish() we see for that var ) A var is placed on the codegen stack when you pass a finish with that var in asyncInitVal. That's it. Is there something wrong with the code I proposed? It does the maximal amount of caching with the minimal number of cached variables (one variable per scope. Unused variables will be removed by javac.) If I understand your proposal correctly, you want to cache the value after the "If_c" node? That is not efficient, e.g., if (...) if (...) x=1; else x=2; else if (...) x=3; else x=4; My code will be: if (...) if (...) $x[0] = $cache_x*=1; else $x[0] = $cache_x*=2; else if (...) $x[0] = $cache_x*=3; else $x[0] = $cache_x*=4; Your code will have a cached variable after every assignment, and after every If and after every Block. Another example (the blocks are there on purpose): val x:Int; finish async { { { x=1; for (...) foo(x); } for (...) foo(x); } for (...) foo(x); } Your code will create many cached vars, whereas my code will create a single one at the beginning of the async. Think of it as an X10 source level transformation as follows: val x:Int; finish async { ... } Is transformed to: val x:Int; finish async { val cached_x; ...[x/cached_x] x = cached_x; } If we had a way to refer to the outer scope, than we wouldn't even need alpha-renaming (we could just use hiding). [Quoted text hidden] Igor Peshansky <igorp@us.ibm.com> Fri, Sep 24, 2010 at 1:32 PM To: Yoav Zibin <yoav.zibin@gmail.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> Yoav, Your proposal requires the codegen to rewrite all accesses to local variables. They also have to keep the codegen stack, which is not as simple as you think. It would be best if the codegen was stateless, and driven entirely by the information already stored in the AST. My proposal will not have a cached value after every If and every Block -- only after those that will have definitely initialized the variable. So, for your first example, the only cached variable will be declared after the outer " if " . You are correct that for the second example, there will be a cached variable after every block. But, if it is unused, the JIT will easily eliminate it, and if it is used, it simplifies the job of the code generator, so I think it's a win. Also, your proposal requires the code generator to pre-declare all of the cache variables, which makes it a non-local transformation (you have to look ahead into the block to find out which variables are used). In my proposal, the information is only needed after the node has been visited, thus it can be done in a single pass. Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 01:19 PM To Igor Peshansky/Watson/IBM@IBMUS cc David P Grove/Watson/IBM@IBMUS, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization Ok, I understand your proposal. Now please understand mine because it is more efficient (and requires less effort to implement). No need for any book keeping except asyncInitVal in Finish nodes, and a codegen stack that tracks what is the current cached value (the current cache is at the top of the stack). You declare "x" as normal, and you declare $cache_x* at the beginning of every async ( for every var in the codegen stack). At every stopFinish() you write to the current cached value (either $cached_x* or "x" ) ( if you haven't done so, in case someone uses the stupid pattern: finish finish ... Therefore we do the write only after the first stopFinish() we see for that var ) A var is placed on the codegen stack when you pass a finish with that var in asyncInitVal. That's it. Is there something wrong with the code I proposed? It does the maximal amount of caching with the minimal number of cached variables (one variable per scope. Unused variables will be removed by javac.) If I understand your proposal correctly, you want to cache the value after the "If_c" node? That is not efficient, e.g., if (...) if (...) x=1; else x=2; else if (...) x=3; else x=4; My code will be: if (...) if (...) $x[0] = $cache_x*=1; else $x[0] = $cache_x*=2; else if (...) $x[0] = $cache_x*=3; else $x[0] = $cache_x*=4; Your code will have a cached variable after every assignment, and after every If and after every Block. Another example (the blocks are there on purpose): val x:Int; finish async { { { x=1; for (...) foo(x); } for (...) foo(x); } for (...) foo(x); } Your code will create many cached vars, whereas my code will create a single one at the beginning of the async. Think of it as an X10 source level transformation as follows: val x:Int; finish async { ... } Is transformed to: val x:Int; finish async { val cached_x; ...[x/cached_x] x = cached_x; } If we had a way to refer to the outer scope, than we wouldn't even need alpha-renaming (we could just use hiding). 2010/9/24 Igor Peshansky <igorp@us.ibm.com> How does the Java backend know where it should declare the various $cache_x* variables? How does it know that references to "x" need to be changed to use the $cache_x* variables (without complex bookkeeping)? If you provide the information I've requested, then the If statement and both Finish statements will have "x" in their "definitely assigned after this point" set, and so the Java backend can generate the following: final int [] $x; // "x" is marked as asynchronously initialized, so we create a box blabla... startFinish(); runAsync( runAsync( startFinish(); runAsync( blabla... if (foo) $x[0]=1; else $x[0]=2; // points of the write. Incidentally, those assignments live in Eval nodes, so if "x" is used within the branches of the " if " , the rules below also apply final int x = $x[0]; // "x" is in the set stored in the " if " statement node, so right after that node it can be cached in the variable with the real value for (...) val y=x; // no changes to codegen required here ) stopFinish(); final int x = $x[0]; // "x" is in the set stored in the "finish" statement node, so ... for (...) val z=x; // no changes to codegen required here ) ) stopFinish(); final int x = $x[0]; // "x" is in the set stored in the "finish" statement node, so ... for (...) val w=x; There is no need to declare " final int x" before it is definitely initialized. This is the scheme Takeuchi-san and I discussed during his visit. Igor P.S. I missed some other use cases -- this is needed not only for Eval statements, but also for If statements, Switch statements, and probably other control flow, e.g., Do/ while statements. Putting it in the X10Ext_c sounds more and more like the right thing to do . -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 12:36 PM To Igor Peshansky/Watson/IBM@IBMUS cc David P Grove/Watson/IBM@IBMUS, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization No, it still doesn't make sense. I think you can do code generation with the set I stored in the Finish node. Let's look at an example: val x; blabla... finish { async { async { finish { async { blabla... if (foo) x=1; else x=2; for (...) val y=x; } } for (...) val z=x; } } } for (...) val w=x; Then the generated code should be: final int x; blabla... final int [] $x; // "x" is in the finish's set, so we create a box, and push it into some codegen stack startFinish(); runAsync( // in an anonymous class, so we need a new cache for everything in the codegen stack. final int $cache_x0; runAsync( // in an anonymous class, so ... final int $cache_x1; startFinish(); runAsync( // in an anonymous class, so ... final int $cache_x2; blabla... if (foo) $x[0]=$cache_x2=1; else $x[0]=$cache_x2=2; // points of the write for (...) val y=$cache_x2; ) stopFinish(); $cache_x1 = $x[0]; // write to current cache after every stopFinish() for (...) val z=$cache_x1; ) ) stopFinish(); x = $x[0]; // write to current cache after every stopFinish() for (...) val w=x; So $x[] is the box, and "x" and $cache_xN are the cached final value. You cache once after every stopFinish, and you start a new cache every scope (so at the declaration point and after every runAsync). Note how $cache_x0 is not used and not assigned (so javac will not complain, and will simply remove it). Hope that clears my understanding of the codegen :) 2010/9/24 Igor Peshansky <igorp@us.ibm.com> Yoav, The point is: Toshio wants to insert a Java-level final variable declaration that will cache the assigned value of the X10 variable (instead of keeping it boxed). He needs to do this at the earliest point of definite assignment (i.e., after the assignment itself, and after every synchronization construct that guarantees the execution of that assignment, e.g., finish, next, etc). The dataflow analysis computes definite assignment results for every Stmt node. Whenever those results indicate that a variable has been definitely assigned (and it hasn't been prior to that node), that variable needs to be added to the definite assignment set * for that node* ( this uses the semantics "the variable is definitely assigned from this point on within this scope" for that set). Then, when Toshio is visiting the AST, he can query that set for any given node, and if the set is non-empty, insert a cached varaible declaration there. I hope this makes sense. Yes, they can generate boxed accesses within the async, but for programs that perform a lot of calculations in the body of the async this is not very optimal (and we have that info, so why not provide it?). Finally, when our dataflow starts considering, e.g., "next" statements, we would then have to add such sets to those as well. If you add this set to the extension node, no other code would need to change as the dataflow becomes more sophisticated. Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 11:36 AM To Igor Peshansky/Watson/IBM@IBMUS cc David P Grove/Watson/IBM@IBMUS, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Toshio Suganuma <SUGANUMA@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization I'm not sure I flow your proposal (see my previous message :) How will it help Toshio that I'll mark everything as definitely assigned? (every place "x" is used, then "x" is definitely assigned, or else we wouldn't proceed to code generation) Please send an example with the corresponding code generated by the Java backend (so I'll understand what you mean). 2010/9/24 Igor Peshansky <igorp@us.ibm.com> Yoav, See my previous message. You need to add this set in *every place* where the dataflow determines that the variable is definitely assigned. Fortunately, it's possible to always insert the kind of code that Toshio wants to use in all of those places, because the scopes will never intersect. Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 11:05 AM To Igor Peshansky/Watson/IBM@IBMUS cc Toshio Suganuma <SUGANUMA@jp.ibm.com>, David P Grove/Watson/IBM@IBMUS, Mikio Takeuchi <MTAKE@jp.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization No problem Toshio, I've committed it. How will you handle this kind of code: val x : Int; finish async { finish async { x = 10; val y = x+1; } val z = x+1; } val w = x+1; ? Which "finish" will have "x" in its set? Sadly from the dataflow perspective, there is no difference between the two "finishes" . The flow after: x = 10; or finish async x=10; is the same (in both cases "x" is initialized). Therefore these two finishes have exactly the same in&out flow: finish x=10; finish finish x=10; So, I've added "x" to both finishes. This should be enough: when you first see a Finish node for var "x" , then mark that var and emit the extra $x[] (so need to mark that var so you won't emit $x again for the second finish), and until you encounter that finish again, then every assignment and every access uses $x[0] instead. After that finish, emit "x = $x[0];" . Does it make sense? Igor, I don't think they need any extra info. They can only generate this code for accesses inside the async: val x : Int; finish { async { x = 10; val y = x+1; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); runAsync ( $x[0] = 10; final int y = $x[0]+1; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; 2010/9/24 Igor Peshansky <igorp@us.ibm.com> Toshio, Unfortunately, you would need this information at every point of definite assignment (e.g., inside the async after the assignment itself, etc). Yoav, is it possible to add that set to every node where the definitely assigned variables first appear in the data flow info? Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Toshio Suganuma/Japan/IBM@IBMJP 09/24/2010 07:53 AM To Yoav Zibin <yoav.zibin@gmail.com> cc Mikio Takeuchi/Japan/IBM@IBMJP, Yuki Makino/Japan/IBM, David P Grove/Watson/IBM@IBMUS, Igor Peshansky/Watson/IBM@IBMUS Subject Fw: Question about finish-async initialization Yoav, We noticed that we need to generate the code of backing store from boxed variables to the original final variables just after the finish block, not after the async block, since from the semantics, the statements within the async block are not necessarily executed (completed) just after the async block. Also, if async blocks are executed within some conditional statements (as shown below), the only location we can generate the backing store code is after the enclosing finish block. val x : Int; finish { if (A) async { x = 10; } else async { x = 20; } } ==> final int x; final int $x[] = new int [1]; try { startFinish(); if (A) runAsync ( $x[0] = 10; ) else runAsync ( $x[0] = 20; ) } catch ( ... ) { } finally { stopFinish(); } x = $x[0]; Thus, it would be helpful if you can move the information of async-initialized vars (Set<VarDef>) currently attached in the async-node to the finish-node instead? If there are multiple such variables from several asyncs within a finish node, please include all those variables in the finish-node scope. If finish-async blocks are nested, One more question is about uncounted async. Is it possible that an uncounted async and a normal async are within a finish block and each initializes different variables, as shown below? Since the uncounted async will not be blocked at stopFinish(), either of the async block could be uncompleted yet after the finish block, and thus the backing store generated there could be ineffective. Could you please clarify that 1) can uncounted asyncs perform variable initialization? and 2) what is the execution behavior when the uncounted async is finished earlier than the normal async in the example below, i.e. the statements after the finish will be executed without waiting the normal async completion? val x : Int; val y: Int; finish { @Uncounted async { x = 10; } async { y = 20; } } Thank you, --Toshio ----- Forwarded by Toshio Suganuma/Japan/IBM on 2010/09/24 19:18 ----- From: Toshio Suganuma/Japan/IBM To: Yoav Zibin <yoav.zibin@gmail.com>, Igor Peshansky/Watson/IBM@IBMUS Cc: Mikio Takeuchi/Japan/IBM@IBMJP, Yuki Makino/Japan/IBM, David P Grove/Watson/IBM@IBMUS Date: 2010/09/14 02:01 Subject: Re: Fw: Question about finish-async initialization Yoav, Thank you for your quick reply. Since Async_c nodes are converted to closures in the desugarer phase, I will move this information to Closure_c nodes using Annotation. Igor, I'm not sure how you implement async initialization in the C++ backend, but are you going to use this information as well? Please let me know if you have any suggestion for better way to transfer the Async node information to the code generation phase. Thank you, --Toshio From: Yoav Zibin <yoav.zibin@gmail.com> To: Toshio Suganuma/Japan/IBM@IBMJP Date: 2010/09/11 04:52 Subject: Re: Fw: Question about finish-async initialization Sure, no problems. public class Async_c extends Stmt_c implements Async { /* For example: val x:Int; finish async { x = 42; } // "x" can either be boxed or be passed (to the async closure) by ref, because we need to assign to it. It cannot be passed by value. async { val y = x; } // "x" can be passed by value or be be boxed. It cannot be passed by ref because the async outlives the var "x" . */ public Set<VarDef> asyncInitVal = null ; // used by the backend to know whether to pass a var to an async closure by ref or by value If you want a boolean flag on the VarDef_c, let me know. 2010/9/10 Toshio Suganuma <SUGANUMA@jp.ibm.com> Hi Yoav, I will start working for the Java backend problem around the finish-async initialization. Can you please let me know how we can get the list of those variables at the async node that need to be initialized within the async block? Thank you, --Toshio ----- Forwarded by Yuki Makino/Japan/IBM on 2010/09/09 16:52 ----- From: Yoav Zibin <yoav.zibin@gmail.com> To: Yuki Makino/Japan/IBM@IBMJP Cc: Yoav Zibin <yzibin@us.ibm.com>, Igor Peshansky <igorp@us.ibm.com>, David P Grove <groved@us.ibm.com>, Mikio Takeuchi/Japan/IBM@IBMJP Date: 2010/09/04 01:58 Subject: Re: Question about finish-async initialization Consider this : Val x:Int; Finish Async x=1; async Val z =x; So x should not be marked, but instead I marked the first Async that it inits x. I can also mark it if you want :) Thanks, Yoav Zibin On 3 &#1489;&#1505;&#1508;&#1496; 2010, at 08:54, Yuki Makino <MAKINO@jp.ibm.com> wrote: Hi, Yoav. I'm implementing to handle finish-async initialization of local vals in the Java back-end. I'd like to know whether a local val is initialized asynchronously for the work. So, could you tell how to get the information that a local val is initialized inside async block. Is there any mark at the LocalDecl node? Yuki MAKINO / X10 Compiler , IM, Yamato Software Development Laboratory, IBM Japan Toshio Suganuma <SUGANUMA@jp.ibm.com> Fri, Sep 24, 2010 at 2:47 PM To: Igor Peshansky <igorp@us.ibm.com>, Yoav Zibin <yoav.zibin@gmail.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com> Igor, Yoav, Thank you for your discussions. I understand that what Igor mentions is for code optimizations. From the code generation standpoint, I think we can generate code just with the init variable markings that Yoav now stored on finish node, based on boxed variable only (no cache). This could be a simple first step, but it should work. If the additional info becomes available for the definite assignment, we will be able to extend the AST node visitor to take advantage of the information for generating a better code (cache version). The first step code will be something like the following. In short , for nested finish-async, we create a boxed variable for each nest level and replace all occurrences of the variable in that scope with the boxed variable. At the synchrnization point (after stopFinish), we generate backing store into an outer level boxed variable or the outermost final variable. I think this could be done with a simple rule for the NodeVisitor. final int x; blabla... final int [] $x0 = new int [1]; // boxed var declaration for nest level 0 startFinish(); runAsync( runAsync( final int [] $x1 = new int [1]; // boxed var declaration for nest level 1 startFinish(); runAsync( blabla... if (foo) $x1[0]=1; else $x1[0]=2; for (...) val y=$x1[0]; ) stopFinish(); $x0[0] = $x1[0]; for (...) val z=$x0[0]; ) ) stopFinish(); final int x = $x0[0]; for (...) val w=x; Best Regards, --Toshio From: Igor Peshansky <igorp@us.ibm.com> To: Yoav Zibin <yoav.zibin@gmail.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino/Japan/IBM@IBMJP, Mikio Takeuchi/Japan/IBM@IBMJP, Toshio Suganuma/Japan/IBM@IBMJP Date: 2010/09/25 02:33 Subject: Re: Fw: Question about finish-async initialization Yoav, [Quoted text hidden] To Igor Peshansky/Watson/IBM@IBMUS 09/24/2010 cc 01:19 PM David P Grove/Watson/IBM@IBMUS, Yuki Makino [Quoted text hidden] To Igor Peshansky/Watson/IBM@IBMUS 09/24/2010 cc 12:36 PM David P Grove/Watson/IBM@IBMUS, Yuki Makino < [Quoted text hidden] To Igor Peshansky/Watson/IBM@IBMUS 09/24/2010 cc 11:36 AM David P Grove/Watson/IBM@IBMUS, Yuki Makino < [Quoted text hidden] To Igor Peshansky/Watson/IBM@IBMUS 09/24/2010 cc 11:05 AM Toshio Suganuma <SUGANUMA@jp.ibm.com>, David P [Quoted text hidden] To Yoav Zibin <yoav.zibin@gmail.com> 09/24/2010 07:53 cc AM Mikio Takeuchi/Japan/IBM@IBMJP, Yuki [Quoted text hidden] Igor Peshansky <igorp@us.ibm.com> Fri, Sep 24, 2010 at 3:20 PM To: Toshio Suganuma <SUGANUMA@jp.ibm.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Yoav Zibin <yoav.zibin@gmail.com> Toshio, If you plan to generate boxed accesses, there is no reason to create variables at each nest level. Simply turn the original declaration into a boxed declaration, and turn all references into references to the box. Because the boxed declaration is final , it can be easily captured in anonymous classes, not requiring any extra varaibles. Igor -- Igor Peshansky (note the spelling change!) IBM T.J. Watson Research Center X10: Parallel Productivity and Performance (http: //x10-lang.org/) XJ: No More Pain for XML's Gain (http: //www.research.ibm.com/xj/) "I hear and I forget. I see and I remember. I do and I understand" -- Confucius Toshio Suganuma <SUGANUMA@jp.ibm.com> 09/24/2010 02:47 PM To Igor Peshansky/Watson/IBM@IBMUS, Yoav Zibin <yoav.zibin@gmail.com> cc David P Grove/Watson/IBM@IBMUS, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com> Subject Re: Fw: Question about finish-async initialization [Quoted text hidden] Toshio Suganuma <SUGANUMA@jp.ibm.com> Mon, Sep 27, 2010 at 4:22 AM To: Igor Peshansky <igorp@us.ibm.com> Cc: David P Grove <groved@us.ibm.com>, Yuki Makino <MAKINO@jp.ibm.com>, Mikio Takeuchi <MTAKE@jp.ibm.com>, Yoav Zibin <yoav.zibin@gmail.com> Igor, Thank you for your advice. I have just committed the code generation for Java. This is an initial implementation based on boxed accesses, creating a box variable only for outermost finish (per your suggestion below). I will continue working for a more optimized version by privatizing those boxed variables in each async block using definite assignment info from Yoav. Regards, --Toshio From: Igor Peshansky <igorp@us.ibm.com> To: Toshio Suganuma/Japan/IBM@IBMJP Cc: David P Grove <groved@us.ibm.com>, Yuki Makino/Japan/IBM@IBMJP, Mikio Takeuchi/Japan/IBM@IBMJP, Yoav Zibin <yoav.zibin@gmail.com> Date: 2010/09/25 04:20 Subject: Re: Fw: Question about finish-async initialization Toshio, If you plan to generate boxed accesses, there is no reason to create variables at each nest level. Simply turn the original declaration into a boxed declaration, and turn all references into references to the box. Because the boxed declaration is final , it can be easily captured in anonymous classes, not requiring any extra varaibles. Igor

David Grove added a comment - 17/Mar/11 2:54 PM - edited ok. call it part of the lowerer and not part of the front-end. I don't care. At some point the compiler needs to figure out everything that is being captured by an at or an async and whether it is the lval or the rval that is being captured. Makes no sense to do that in the code-generator. For the same reason why computing lexical environment capture in the codegen pass makes no sense at all. It's an involved computation and we only want 1 copy of the code that does it, not two.

David Grove added a comment - 14/Apr/11 2:07 PM break/continue/return from at covered by different issue, so narrowed scope of this one to just definite assignment.

Igor Peshansky added a comment - 10/May/11 7:00 PM Defer to 2.2.1, along with XTENLANG-2469 .

David Grove added a comment - 13/Sep/11 7:27 AM bulk defer of open issues to 2.2.2.

David Grove added a comment - 24/Jan/12 9:06 AM bulk defer of issues to 2.2.3.

David Grove added a comment - 08/Oct/12 9:24 PM bulk defer of 2.3.0 open issues to 2.3.1.

David Grove added a comment - 12/Feb/13 7:22 AM bulk defer to 2.3.2