source: src/Concurrency/Waituntil.cpp @ 16e0dcb

Last change on this file since 16e0dcb was 16e0dcb, checked in by caparson <caparson@…>, 5 months ago

fixed error where order of argument eval in compiler could cause different code to be generated

  • Property mode set to 100644
File size: 58.2 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// WaitforNew.cpp -- Expand waitfor clauses into code.
8//
9// Author           : Andrew Beach
10// Created On       : Fri May 27 10:31:00 2022
11// Last Modified By : Andrew Beach
12// Last Modified On : Tue Jun 13 13:30:00 2022
13// Update Count     : 0
14//
15
16#include "Waituntil.hpp"
17
18#include <string>
19
20#include "AST/Copy.hpp"
21#include "AST/Expr.hpp"
22#include "AST/Pass.hpp"
23#include "AST/Print.hpp"
24#include "AST/Stmt.hpp"
25#include "AST/Type.hpp"
26#include "Common/UniqueName.h"
27
28using namespace ast;
29using namespace std;
30
31/* So this is what this pass dones:
32{
33    when ( condA ) waituntil( A ){ doA(); }
34    or when ( condB ) waituntil( B ){ doB(); }
35    and when ( condC ) waituntil( C ) { doC(); }
36}
37                 ||
38                 ||
39                \||/
40                 \/
41
42Generates these two routines:
43static inline bool is_full_sat_1( int * clause_statuses ) {
44    return clause_statuses[0]
45        || clause_statuses[1]
46        && clause_statuses[2];
47}
48
49static inline bool is_done_sat_1( int * clause_statuses ) {
50    return has_run(clause_statuses[0])
51        || has_run(clause_statuses[1])
52        && has_run(clause_statuses[2]);
53}
54
55Replaces the waituntil statement above with the following code:
56{
57    // used with atomic_dec/inc to get binary semaphore behaviour
58    int park_counter = 0;
59
60    // status (one for each clause)
61    int clause_statuses[3] = { 0 };
62
63    bool whenA = condA;
64    bool whenB = condB;
65    bool whenC = condC;
66
67    if ( !whenB ) clause_statuses[1] = __SELECT_RUN;
68    if ( !whenC ) clause_statuses[2] = __SELECT_RUN;
69
70    // some other conditional settors for clause_statuses are set here, see genSubtreeAssign and related routines
71
72    // three blocks
73    // for each block, create, setup, then register select_node
74    select_node clause1;
75    select_node clause2;
76    select_node clause3;
77
78    try {
79        if ( whenA ) { register_select(A, clause1); setup_clause( clause1, &clause_statuses[0], &park_counter ); }
80        ... repeat ^ for B and C ...
81
82        // if else clause is defined a separate branch can occur here to set initial values, see genWhenStateConditions
83
84        // loop & park until done
85        while( !is_full_sat_1( clause_statuses ) ) {
86           
87            // binary sem P();
88            if ( __atomic_sub_fetch( &park_counter, 1, __ATOMIC_SEQ_CST) < 0 )
89                park();
90           
91            // execute any blocks available with status set to 0
92            for ( int i = 0; i < 3; i++ ) {
93                if (clause_statuses[i] == __SELECT_SAT) {
94                    switch (i) {
95                        case 0:
96                            try {
97                                    on_selected( A, clause1 );
98                                    doA();
99                            }
100                            finally { clause_statuses[i] = __SELECT_RUN; unregister_select(A, clause1); }
101                            break;
102                        case 1:
103                            ... same gen as A but for B and clause2 ...
104                            break;
105                        case 2:
106                            ... same gen as A but for C and clause3 ...
107                            break;
108                    }
109                }
110            }
111        }
112
113        // ensure that the blocks that triggered is_full_sat_1 are run
114        // by running every un-run block that is SAT from the start until
115        // the predicate is SAT when considering RUN status = true
116        for ( int i = 0; i < 3; i++ ) {
117            if (is_done_sat_1( clause_statuses )) break;
118            if (clause_statuses[i] == __SELECT_SAT)
119                ... Same if body here as in loop above ...
120        }
121    } finally {
122        // the unregister and on_selected calls are needed to support primitives where the acquire has side effects
123        // so the corresponding block MUST be run for those primitives to not lose state (example is channels)
124        if ( !has_run(clause_statuses[0]) && whenA && unregister_select(A, clause1) )
125            on_selected( A, clause1 )
126            doA();
127        ... repeat if above for B and C ...
128    }
129}
130
131*/
132
133namespace Concurrency {
134
135class GenerateWaitUntilCore final {
136    vector<FunctionDecl *> & satFns;
137        UniqueName namer_sat = "__is_full_sat_"s;
138    UniqueName namer_run = "__is_run_sat_"s;
139        UniqueName namer_park = "__park_counter_"s;
140        UniqueName namer_status = "__clause_statuses_"s;
141        UniqueName namer_node = "__clause_"s;
142    UniqueName namer_target = "__clause_target_"s;
143    UniqueName namer_when = "__when_cond_"s;
144    UniqueName namer_label = "__waituntil_label_"s;
145
146    string idxName = "__CFA_clause_idx_";
147
148    struct ClauseData {
149        string nodeName;
150        string targetName;
151        string whenName;
152        int index;
153        string & statusName;
154        ClauseData( int index, string & statusName ) : index(index), statusName(statusName) {}
155    };
156
157    const StructDecl * selectNodeDecl = nullptr;
158
159    // This first set of routines are all used to do the complicated job of
160    //    dealing with how to set predicate statuses with certain when_conds T/F
161    //    so that the when_cond == F effectively makes that clause "disappear"
162    void updateAmbiguousWhen( WaitUntilStmt::ClauseNode * currNode, bool andAbove, bool orAbove, bool andBelow, bool orBelow );
163    void paintWhenTree( WaitUntilStmt::ClauseNode * currNode, bool andAbove, bool orAbove, bool & andBelow, bool & orBelow );
164    bool paintWhenTree( WaitUntilStmt::ClauseNode * currNode );
165    void collectWhens( WaitUntilStmt::ClauseNode * currNode, vector<pair<int, WaitUntilStmt::ClauseNode *>> & ambigIdxs, vector<int> & andIdxs, int & index, bool parentAmbig, bool parentAnd );
166    void collectWhens( WaitUntilStmt::ClauseNode * currNode, vector<pair<int, WaitUntilStmt::ClauseNode *>> & ambigIdxs, vector<int> & andIdxs );
167    void updateWhenState( WaitUntilStmt::ClauseNode * currNode );
168    void genSubtreeAssign( const WaitUntilStmt * stmt, WaitUntilStmt::ClauseNode * currNode, bool status, int & idx, CompoundStmt * retStmt, vector<ClauseData *> & clauseData );
169    void genStatusAssign( const WaitUntilStmt * stmt, WaitUntilStmt::ClauseNode * currNode, int & idx, CompoundStmt * retStmt, vector<ClauseData *> & clauseData );
170    CompoundStmt * getStatusAssignment( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData );
171    Stmt * genWhenStateConditions( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData, vector<pair<int, WaitUntilStmt::ClauseNode *>> & ambigClauses, vector<pair<int, WaitUntilStmt::ClauseNode *>>::size_type ambigIdx );
172
173    // These routines are just code-gen helpers
174    void addPredicates( const WaitUntilStmt * stmt, string & satName, string & runName );
175    void setUpClause( const WhenClause * clause, ClauseData * data, string & pCountName, CompoundStmt * body );
176    CompoundStmt * genStatusCheckFor( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData, string & predName );
177    Expr * genSelectTraitCall( const WhenClause * clause, const ClauseData * data, string fnName );
178    CompoundStmt * genStmtBlock( const WhenClause * clause, const ClauseData * data );
179    Stmt * genElseClauseBranch( const WaitUntilStmt * stmt, string & runName, string & arrName, vector<ClauseData *> & clauseData );
180    Stmt * genNoElseClauseBranch( const WaitUntilStmt * stmt, string & runName, string & arrName, string & pCountName, vector<ClauseData *> & clauseData );
181    void genClauseInits( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData, CompoundStmt * body, string & statusName, string & elseWhenName );
182    Stmt * recursiveOrIfGen( const WaitUntilStmt * stmt, vector<ClauseData *> & data, vector<ClauseData*>::size_type idx, string & elseWhenName );
183    Stmt * buildOrCaseSwitch( const WaitUntilStmt * stmt, string & statusName, vector<ClauseData *> & data );
184    Stmt * genAllOr( const WaitUntilStmt * stmt );
185
186  public:
187    void previsit( const StructDecl * decl );
188        Stmt * postvisit( const WaitUntilStmt * stmt );
189    GenerateWaitUntilCore( vector<FunctionDecl *> & satFns ): satFns(satFns) {}
190};
191
192// Finds select_node decl
193void GenerateWaitUntilCore::previsit( const StructDecl * decl ) {
194    if ( !decl->body ) {
195                return;
196        } else if ( "select_node" == decl->name ) {
197                assert( !selectNodeDecl );
198                selectNodeDecl = decl;
199        }
200}
201
202void GenerateWaitUntilCore::updateAmbiguousWhen( WaitUntilStmt::ClauseNode * currNode, bool andAbove, bool orAbove, bool andBelow, bool orBelow ) {
203    // all children when-ambiguous
204    if ( currNode->left->ambiguousWhen && currNode->right->ambiguousWhen )
205        // true iff an ancestor/descendant has a different operation
206        currNode->ambiguousWhen = (orAbove || orBelow) && (andBelow || andAbove);
207    // ambiguousWhen is initially false so theres no need to set it here
208}
209
210// Traverses ClauseNode tree and paints each AND/OR node as when-ambiguous true or false
211// This tree painting is needed to generate the if statements that set the initial state
212//    of the clause statuses when some clauses are turned off via when_cond
213// An internal AND/OR node is when-ambiguous if it satisfies all of the following:
214// - It has an ancestor or descendant that is a different operation, i.e. (AND has an OR ancestor or vice versa)
215// - All of its descendent clauses are optional, i.e. they have a when_cond defined on the WhenClause
216void GenerateWaitUntilCore::paintWhenTree( WaitUntilStmt::ClauseNode * currNode, bool andAbove, bool orAbove, bool & andBelow, bool & orBelow ) {
217    bool aBelow = false; // updated by child nodes
218    bool oBelow = false; // updated by child nodes
219    switch (currNode->op) {
220        case WaitUntilStmt::ClauseNode::AND:
221            paintWhenTree( currNode->left, true, orAbove, aBelow, oBelow );
222            paintWhenTree( currNode->right, true, orAbove, aBelow, oBelow );
223
224            // update currNode's when flag based on conditions listed in fn signature comment above
225            updateAmbiguousWhen(currNode, true, orAbove, aBelow, oBelow );
226
227            // set return flags to tell parents which decendant ops have been seen
228            andBelow = true;
229            orBelow = oBelow;
230            return;
231        case WaitUntilStmt::ClauseNode::OR:
232            paintWhenTree( currNode->left, andAbove, true, aBelow, oBelow );
233            paintWhenTree( currNode->right, andAbove, true, aBelow, oBelow );
234
235            // update currNode's when flag based on conditions listed in fn signature comment above
236            updateAmbiguousWhen(currNode, andAbove, true, aBelow, oBelow );
237
238            // set return flags to tell parents which decendant ops have been seen
239            andBelow = aBelow;
240            orBelow = true;
241            return;
242        case WaitUntilStmt::ClauseNode::LEAF:
243            if ( currNode->leaf->when_cond )
244                currNode->ambiguousWhen = true;
245            return;
246        default:
247            assertf(false, "Unreachable waituntil clause node type. How did you get here???");
248    }
249}
250
251// overloaded wrapper for paintWhenTree that sets initial values
252// returns true if entire tree is OR's (special case)
253bool GenerateWaitUntilCore::paintWhenTree( WaitUntilStmt::ClauseNode * currNode ) {
254    bool aBelow = false, oBelow = false; // unused by initial call
255    paintWhenTree( currNode, false, false, aBelow, oBelow );
256    return !aBelow;
257}
258
259// Helper: returns Expr that represents arrName[index]
260Expr * genArrAccessExpr( const CodeLocation & loc, int index, string arrName ) {
261    return new UntypedExpr ( loc, 
262        new NameExpr( loc, "?[?]" ),
263        {
264            new NameExpr( loc, arrName ),
265            ConstantExpr::from_int( loc, index )
266        }
267    );
268}
269
270// After the ClauseNode AND/OR nodes are painted this routine is called to traverses the tree and does the following:
271// - collects a set of indices in the clause arr that refer whenclauses that can have ambiguous status assignments (ambigIdxs)
272// - collects a set of indices in the clause arr that refer whenclauses that have a when() defined and an AND node as a parent (andIdxs)
273// - updates LEAF nodes to be when-ambiguous if their direct parent is when-ambiguous.
274void GenerateWaitUntilCore::collectWhens( WaitUntilStmt::ClauseNode * currNode, vector<pair<int, WaitUntilStmt::ClauseNode *>> & ambigIdxs, vector<int> & andIdxs, int & index, bool parentAmbig, bool parentAnd ) {
275    switch (currNode->op) {
276        case WaitUntilStmt::ClauseNode::AND:
277            collectWhens( currNode->left, ambigIdxs, andIdxs, index, currNode->ambiguousWhen, true );
278            collectWhens( currNode->right,  ambigIdxs, andIdxs, index, currNode->ambiguousWhen, true );
279            return;
280        case WaitUntilStmt::ClauseNode::OR:
281            collectWhens( currNode->left,  ambigIdxs, andIdxs, index, currNode->ambiguousWhen, false );
282            collectWhens( currNode->right,  ambigIdxs, andIdxs, index, currNode->ambiguousWhen, false );
283            return;
284        case WaitUntilStmt::ClauseNode::LEAF:
285            if ( parentAmbig ) {
286                ambigIdxs.push_back(make_pair(index, currNode));
287            }
288            if ( parentAnd && currNode->leaf->when_cond ) {
289                currNode->childOfAnd = true;
290                andIdxs.push_back(index);
291            }
292            index++;
293            return;
294        default:
295            assertf(false, "Unreachable waituntil clause node type. How did you get here???");
296    }
297}
298
299// overloaded wrapper for collectWhens that sets initial values
300void GenerateWaitUntilCore::collectWhens( WaitUntilStmt::ClauseNode * currNode, vector<pair<int, WaitUntilStmt::ClauseNode *>> & ambigIdxs, vector<int> & andIdxs ) {
301    int idx = 0;
302    collectWhens( currNode, ambigIdxs, andIdxs, idx, false, false );
303}
304
305// recursively updates ClauseNode whenState on internal nodes so that next pass can see which
306//    subtrees are "turned off"
307// sets whenState = false iff both children have whenState == false.
308// similar to paintWhenTree except since paintWhenTree also filtered out clauses we don't need to consider based on op
309// since the ambiguous clauses were filtered in paintWhenTree we don't need to worry about that here
310void GenerateWaitUntilCore::updateWhenState( WaitUntilStmt::ClauseNode * currNode ) {
311    if ( currNode->op == WaitUntilStmt::ClauseNode::LEAF ) return;
312    updateWhenState( currNode->left );
313    updateWhenState( currNode->right );
314    if ( !currNode->left->whenState && !currNode->right->whenState )
315        currNode->whenState = false;
316    else 
317        currNode->whenState = true;
318}
319
320// generates the minimal set of status assignments to ensure predicate subtree passed as currNode evaluates to status
321// assumes that this will only be called on subtrees that are entirely whenState == false
322void GenerateWaitUntilCore::genSubtreeAssign( const WaitUntilStmt * stmt, WaitUntilStmt::ClauseNode * currNode, bool status, int & idx, CompoundStmt * retStmt, vector<ClauseData *> & clauseData ) {
323    if ( ( currNode->op == WaitUntilStmt::ClauseNode::AND && status )
324        || ( currNode->op == WaitUntilStmt::ClauseNode::OR && !status ) ) {
325        // need to recurse on both subtrees if && subtree needs to be true or || subtree needs to be false
326        genSubtreeAssign( stmt, currNode->left, status, idx, retStmt, clauseData );
327        genSubtreeAssign( stmt, currNode->right, status, idx, retStmt, clauseData );
328    } else if ( ( currNode->op == WaitUntilStmt::ClauseNode::OR && status )
329        || ( currNode->op == WaitUntilStmt::ClauseNode::AND && !status ) ) {
330        // only one subtree needs to evaluate to status if && subtree needs to be true or || subtree needs to be false
331        CompoundStmt * leftStmt = new CompoundStmt( stmt->location );
332        CompoundStmt * rightStmt = new CompoundStmt( stmt->location );
333
334        // only one side needs to evaluate to status so we recurse on both subtrees
335        //    but only keep the statements from the subtree with minimal statements
336        genSubtreeAssign( stmt, currNode->left, status, idx, leftStmt, clauseData );
337        genSubtreeAssign( stmt, currNode->right, status, idx, rightStmt, clauseData );
338       
339        // append minimal statements to retStmt
340        if ( leftStmt->kids.size() < rightStmt->kids.size() ) {
341            retStmt->kids.splice( retStmt->kids.end(), leftStmt->kids );
342        } else {
343            retStmt->kids.splice( retStmt->kids.end(), rightStmt->kids );
344        }
345       
346        delete leftStmt;
347        delete rightStmt;
348    } else if ( currNode->op == WaitUntilStmt::ClauseNode::LEAF ) {
349        const CodeLocation & loc = stmt->location;
350        if ( status && !currNode->childOfAnd ) {
351            retStmt->push_back(
352                new ExprStmt( loc, 
353                    UntypedExpr::createAssign( loc,
354                        genArrAccessExpr( loc, idx, clauseData.at(idx)->statusName ),
355                        new NameExpr( loc, "__SELECT_RUN" )
356                    )
357                )
358            );
359        } else if ( !status && currNode->childOfAnd ) {
360            retStmt->push_back(
361                new ExprStmt( loc, 
362                    UntypedExpr::createAssign( loc,
363                        genArrAccessExpr( loc, idx, clauseData.at(idx)->statusName ),
364                        new NameExpr( loc, "__SELECT_UNSAT" )
365                    )
366                )
367            );
368        }
369
370        // No need to generate statements for the following cases since childOfAnd are always set to true
371        //    and !childOfAnd are always false
372        // - status && currNode->childOfAnd
373        // - !status && !currNode->childOfAnd
374        idx++;
375    }
376}
377
378void GenerateWaitUntilCore::genStatusAssign( const WaitUntilStmt * stmt, WaitUntilStmt::ClauseNode * currNode, int & idx, CompoundStmt * retStmt, vector<ClauseData *> & clauseData ) {
379    switch (currNode->op) {
380        case WaitUntilStmt::ClauseNode::AND:
381            // check which subtrees have all whenState == false (disabled)
382            if (!currNode->left->whenState && !currNode->right->whenState) {
383                // this case can only occur when whole tree is disabled since otherwise
384                //    genStatusAssign( ... ) isn't called on nodes with whenState == false
385                assert( !currNode->whenState ); // paranoidWWW
386                // whole tree disabled so pass true so that select is SAT vacuously
387                genSubtreeAssign( stmt, currNode, true, idx, retStmt, clauseData );
388            } else if ( !currNode->left->whenState ) {
389                // pass true since x && true === x
390                genSubtreeAssign( stmt, currNode->left, true, idx, retStmt, clauseData );
391                genStatusAssign( stmt, currNode->right, idx, retStmt, clauseData );
392            } else if ( !currNode->right->whenState ) {
393                genStatusAssign( stmt, currNode->left, idx, retStmt, clauseData );
394                genSubtreeAssign( stmt, currNode->right, true, idx, retStmt, clauseData );
395            } else { 
396                // if no children with whenState == false recurse normally via break
397                break;
398            }
399            return;
400        case WaitUntilStmt::ClauseNode::OR:
401            if (!currNode->left->whenState && !currNode->right->whenState) {
402                assert( !currNode->whenState ); // paranoid
403                genSubtreeAssign( stmt, currNode, true, idx, retStmt, clauseData );
404            } else if ( !currNode->left->whenState ) {
405                // pass false since x || false === x
406                genSubtreeAssign( stmt, currNode->left, false, idx, retStmt, clauseData );
407                genStatusAssign( stmt, currNode->right, idx, retStmt, clauseData );
408            } else if ( !currNode->right->whenState ) {
409                genStatusAssign( stmt, currNode->left, idx, retStmt, clauseData );
410                genSubtreeAssign( stmt, currNode->right, false, idx, retStmt, clauseData );
411            } else { 
412                break;
413            }
414            return;
415        case WaitUntilStmt::ClauseNode::LEAF:
416            idx++;
417            return;
418        default:
419            assertf(false, "Unreachable waituntil clause node type. How did you get here???");
420    }
421    genStatusAssign( stmt, currNode->left, idx, retStmt, clauseData );
422    genStatusAssign( stmt, currNode->right, idx, retStmt, clauseData );
423}
424
425// generates a minimal set of assignments for status arr based on which whens are toggled on/off
426CompoundStmt * GenerateWaitUntilCore::getStatusAssignment( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData ) {
427    updateWhenState( stmt->predicateTree );
428    CompoundStmt * retval = new CompoundStmt( stmt->location );
429    int idx = 0;
430    genStatusAssign( stmt, stmt->predicateTree, idx, retval, clauseData );
431    return retval;
432}
433
434// generates nested if/elses for all possible assignments of ambiguous when_conds
435// exponential size of code gen but linear runtime O(n), where n is number of ambiguous whens()
436Stmt * GenerateWaitUntilCore::genWhenStateConditions( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData, 
437    vector<pair<int, WaitUntilStmt::ClauseNode *>> & ambigClauses, vector<pair<int, WaitUntilStmt::ClauseNode *>>::size_type ambigIdx ) {
438    // I hate C++ sometimes, using vector<pair<int, WaitUntilStmt::ClauseNode *>>::size_type for size() comparison seems silly.
439    //    Why is size_type parameterized on the type stored in the vector?????
440
441    const CodeLocation & loc = stmt->location;
442    int clauseIdx = ambigClauses.at(ambigIdx).first;
443    WaitUntilStmt::ClauseNode * currNode = ambigClauses.at(ambigIdx).second;
444    Stmt * thenStmt;
445    Stmt * elseStmt;
446   
447    if ( ambigIdx == ambigClauses.size() - 1 ) { // base case
448        currNode->whenState = true;
449        thenStmt = getStatusAssignment( stmt, clauseData );
450        currNode->whenState = false;
451        elseStmt = getStatusAssignment( stmt, clauseData );
452    } else {
453        // recurse both with when enabled and disabled to generate all possible cases
454        currNode->whenState = true;
455        thenStmt = genWhenStateConditions( stmt, clauseData, ambigClauses, ambigIdx + 1 );
456        currNode->whenState = false;
457        elseStmt = genWhenStateConditions( stmt, clauseData, ambigClauses, ambigIdx + 1 );
458    }
459
460    // insert first recursion result in if ( __when_cond_ ) { ... }
461    // insert second recursion result in else { ... }
462    return new CompoundStmt ( loc,
463        {
464            new IfStmt( loc,
465                new NameExpr( loc, clauseData.at(clauseIdx)->whenName ),
466                thenStmt,
467                elseStmt
468            )
469        }
470    );
471}
472
473// typedef a fn ptr so that we can reuse genPredExpr
474// genLeafExpr is used to refer to one of the following two routines
475typedef Expr * (*GenLeafExpr)( const CodeLocation & loc, int & index );
476
477// return Expr that represents clause_statuses[index]
478// mutates index to be index + 1
479Expr * genSatExpr( const CodeLocation & loc, int & index ) {
480    return genArrAccessExpr( loc, index++, "clause_statuses" );
481}
482
483// return Expr that represents has_run(clause_statuses[index])
484Expr * genRunExpr( const CodeLocation & loc, int & index ) {
485    return new UntypedExpr ( loc, 
486        new NameExpr( loc, "__CFA_has_clause_run" ),
487        { genSatExpr( loc, index ) }
488    );
489}
490
491// Takes in the ClauseNode tree and recursively generates
492// the predicate expr used inside the predicate functions
493Expr * genPredExpr( const CodeLocation & loc, WaitUntilStmt::ClauseNode * currNode, int & idx, GenLeafExpr genLeaf ) {
494    Expr * leftExpr, * rightExpr;
495    switch (currNode->op) {
496        case WaitUntilStmt::ClauseNode::AND:
497            leftExpr = genPredExpr( loc, currNode->left, idx, genLeaf );
498            rightExpr = genPredExpr( loc, currNode->right, idx, genLeaf );
499            return new LogicalExpr( loc, 
500                new CastExpr( loc, leftExpr, new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast ),
501                new CastExpr( loc, rightExpr, new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast ), 
502                LogicalFlag::AndExpr
503            );
504            break;
505        case WaitUntilStmt::ClauseNode::OR:
506            leftExpr = genPredExpr( loc, currNode->left, idx, genLeaf );
507            rightExpr = genPredExpr( loc, currNode->right, idx, genLeaf );
508            return new LogicalExpr( loc,
509                new CastExpr( loc, leftExpr, new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast ),
510                new CastExpr( loc, rightExpr, new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast ), 
511                LogicalFlag::OrExpr );
512            break;
513        case WaitUntilStmt::ClauseNode::LEAF:
514            return genLeaf( loc, idx );
515            break;
516        default:
517            assertf(false, "Unreachable waituntil clause node type. How did you get here???");\
518            return nullptr;
519            break;
520    }
521    return nullptr;
522}
523
524
525// Builds the predicate functions used to check the status of the waituntil statement
526/* Ex:
527{
528    waituntil( A ){ doA(); }
529    or waituntil( B ){ doB(); }
530    and waituntil( C ) { doC(); }
531}
532generates =>
533static inline bool is_full_sat_1( int * clause_statuses ) {
534    return clause_statuses[0]
535        || clause_statuses[1]
536        && clause_statuses[2];
537}
538
539static inline bool is_done_sat_1( int * clause_statuses ) {
540    return has_run(clause_statuses[0])
541        || has_run(clause_statuses[1])
542        && has_run(clause_statuses[2]);
543}
544*/
545// Returns a predicate function decl
546// predName and genLeaf determine if this generates an is_done or an is_full predicate
547FunctionDecl * buildPredicate( const WaitUntilStmt * stmt, GenLeafExpr genLeaf, string & predName ) {
548    int arrIdx = 0;
549    const CodeLocation & loc = stmt->location;
550    CompoundStmt * body = new CompoundStmt( loc );
551    body->push_back( new ReturnStmt( loc, genPredExpr( loc,  stmt->predicateTree, arrIdx, genLeaf ) ) );
552
553    return new FunctionDecl( loc,
554        predName,
555        {},                     // forall
556        {
557            new ObjectDecl( loc,
558                "clause_statuses",
559                new PointerType( new BasicType( BasicType::Kind::LongUnsignedInt ) )
560            )
561        },
562        { 
563            new ObjectDecl( loc,
564                "sat_ret",
565                new BasicType( BasicType::Kind::Bool )
566            )
567        },
568        body,               // body
569        { Storage::Static },    // storage
570        Linkage::Cforall,       // linkage
571        {},                     // attributes
572        { Function::Inline }
573    );
574}
575
576// Creates is_done and is_full predicates
577void GenerateWaitUntilCore::addPredicates( const WaitUntilStmt * stmt, string & satName, string & runName ) {
578    if ( !stmt->else_stmt || stmt->else_cond ) // don't need SAT predicate when else variation with no else_cond
579        satFns.push_back( Concurrency::buildPredicate( stmt, genSatExpr, satName ) ); 
580    satFns.push_back( Concurrency::buildPredicate( stmt, genRunExpr, runName ) );
581}
582
583// Adds the following to body:
584// if ( when_cond ) { // this if is omitted if no when() condition
585//      setup_clause( clause1, &clause_statuses[0], &park_counter );
586//      register_select(A, clause1);
587// }
588void GenerateWaitUntilCore::setUpClause( const WhenClause * clause, ClauseData * data, string & pCountName, CompoundStmt * body ) {   
589    CompoundStmt * currBody = body;
590    const CodeLocation & loc = clause->location;
591
592    // If we have a when_cond make the initialization conditional
593    if ( clause->when_cond )
594        currBody = new CompoundStmt( loc );
595
596    // Generates: setup_clause( clause1, &clause_statuses[0], &park_counter );
597    currBody->push_back( new ExprStmt( loc,
598        new UntypedExpr ( loc,
599            new NameExpr( loc, "setup_clause" ),
600            {
601                new NameExpr( loc, data->nodeName ),
602                new AddressExpr( loc, genArrAccessExpr( loc, data->index, data->statusName ) ),
603                new AddressExpr( loc, new NameExpr( loc, pCountName ) )
604            }
605        )
606    ));
607
608    // Generates: register_select(A, clause1);
609    currBody->push_back( new ExprStmt( loc, genSelectTraitCall( clause, data, "register_select" ) ) );
610
611    // generates: if ( when_cond ) { ... currBody ... }
612    if ( clause->when_cond )
613        body->push_back( 
614            new IfStmt( loc,
615                new NameExpr( loc, data->whenName ),
616                currBody
617            )
618        );
619}
620
621// Used to generate a call to one of the select trait routines
622Expr * GenerateWaitUntilCore::genSelectTraitCall( const WhenClause * clause, const ClauseData * data, string fnName ) {
623    const CodeLocation & loc = clause->location;
624    return new UntypedExpr ( loc,
625        new NameExpr( loc, fnName ),
626        {
627            new NameExpr( loc, data->targetName ),
628            new NameExpr( loc, data->nodeName )
629        }
630    );
631}
632
633// Generates:
634/* on_selected( target_1, node_1 ); ... corresponding body of target_1 ...
635*/
636CompoundStmt * GenerateWaitUntilCore::genStmtBlock( const WhenClause * clause, const ClauseData * data ) {
637    const CodeLocation & cLoc = clause->location;
638    return new CompoundStmt( cLoc,
639        {
640            new IfStmt( cLoc,
641                genSelectTraitCall( clause, data, "on_selected" ),
642                ast::deepCopy( clause->stmt )
643            )
644        }
645    );
646}
647
648// this routine generates and returns the following
649/*for ( int i = 0; i < numClauses; i++ ) {
650    if ( predName(clause_statuses) ) break;
651    if (clause_statuses[i] == __SELECT_SAT) {
652        switch (i) {
653            case 0:
654                try {
655                    on_selected( target1, clause1 );
656                    dotarget1stmt();
657                }
658                finally { clause_statuses[i] = __SELECT_RUN; unregister_select(target1, clause1); }
659                break;
660            ...
661            case N:
662                ...
663                break;
664        }
665    }
666}*/
667CompoundStmt * GenerateWaitUntilCore::genStatusCheckFor( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData, string & predName ) {
668    CompoundStmt * ifBody = new CompoundStmt( stmt->location );
669    const CodeLocation & loc = stmt->location;
670
671    string switchLabel = namer_label.newName();
672
673    /* generates:
674    switch (i) {
675        case 0:
676            try {
677                on_selected( target1, clause1 );
678                dotarget1stmt();
679            }
680            finally { clause_statuses[i] = __SELECT_RUN; unregister_select(target1, clause1); }
681            break;
682            ...
683        case N:
684            ...
685            break;
686    }*/
687    std::vector<ptr<CaseClause>> switchCases;
688    int idx = 0;
689    for ( const auto & clause: stmt->clauses ) {
690        const CodeLocation & cLoc = clause->location;
691        switchCases.push_back(
692            new CaseClause( cLoc,
693                ConstantExpr::from_int( cLoc, idx ),
694                {
695                    new CompoundStmt( cLoc,
696                        {
697                            new ast::TryStmt( cLoc,
698                                genStmtBlock( clause, clauseData.at(idx) ),
699                                {},
700                                new ast::FinallyClause( cLoc, 
701                                    new CompoundStmt( cLoc,
702                                        {
703                                            new ExprStmt( loc,
704                                                new UntypedExpr ( loc,
705                                                    new NameExpr( loc, "?=?" ),
706                                                    {
707                                                        new UntypedExpr ( loc, 
708                                                            new NameExpr( loc, "?[?]" ),
709                                                            {
710                                                                new NameExpr( loc, clauseData.at(0)->statusName ),
711                                                                new NameExpr( loc, idxName )
712                                                            }
713                                                        ),
714                                                        new NameExpr( loc, "__SELECT_RUN" )
715                                                    }
716                                                )
717                                            ),
718                                            new ExprStmt( loc, genSelectTraitCall( clause, clauseData.at(idx), "unregister_select" ) )
719                                        }
720                                    )
721                                )
722                            ),
723                            new BranchStmt( cLoc, BranchStmt::Kind::Break, Label( cLoc, switchLabel ) )
724                        }
725                    )
726                }
727            )
728        );
729        idx++;
730    }
731
732    ifBody->push_back(
733        new SwitchStmt( loc,
734            new NameExpr( loc, idxName ),
735            std::move( switchCases ),
736            { Label( loc, switchLabel ) }
737        )
738    );
739
740    // gens:
741    // if (clause_statuses[i] == __SELECT_SAT) {
742    //      ... ifBody  ...
743    // }
744    IfStmt * ifSwitch = new IfStmt( loc,
745        new UntypedExpr ( loc,
746            new NameExpr( loc, "?==?" ),
747            {
748                new UntypedExpr ( loc, 
749                    new NameExpr( loc, "?[?]" ),
750                    {
751                        new NameExpr( loc, clauseData.at(0)->statusName ),
752                        new NameExpr( loc, idxName )
753                    }
754                ),
755                new NameExpr( loc, "__SELECT_SAT" )
756            }
757        ),      // condition
758        ifBody  // body
759    );
760
761    string forLabel = namer_label.newName();
762
763    // we hoist init here so that this pass can happen after hoistdecls pass
764    return new CompoundStmt( loc,
765        {
766            new DeclStmt( loc,
767                new ObjectDecl( loc,
768                    idxName,
769                    new BasicType( BasicType::Kind::SignedInt ),
770                    new SingleInit( loc, ConstantExpr::from_int( loc, 0 ) )
771                )
772            ),
773            new ForStmt( loc,
774                {},  // inits
775                new UntypedExpr ( loc,
776                    new NameExpr( loc, "?<?" ),
777                    {
778                        new NameExpr( loc, idxName ),
779                        ConstantExpr::from_int( loc, stmt->clauses.size() )
780                    }
781                ),  // cond
782                new UntypedExpr ( loc,
783                    new NameExpr( loc, "?++" ),
784                    { new NameExpr( loc, idxName ) }
785                ),  // inc
786                new CompoundStmt( loc,
787                    {
788                        new IfStmt( loc,
789                            new UntypedExpr ( loc,
790                                new NameExpr( loc, predName ),
791                                { new NameExpr( loc, clauseData.at(0)->statusName ) }
792                            ),
793                            new BranchStmt( loc, BranchStmt::Kind::Break, Label( loc, forLabel ) )
794                        ),
795                        ifSwitch
796                    }
797                ),   // body
798                { Label( loc, forLabel ) }
799            )
800        }
801    );
802}
803
804// Generates: !is_full_sat_n() / !is_run_sat_n()
805Expr * genNotSatExpr( const WaitUntilStmt * stmt, string & satName, string & arrName ) {
806    const CodeLocation & loc = stmt->location;
807    return new UntypedExpr ( loc,
808        new NameExpr( loc, "!?" ),
809        {
810            new UntypedExpr ( loc,
811                new NameExpr( loc, satName ),
812                { new NameExpr( loc, arrName ) }
813            )
814        }
815    );
816}
817
818// Generates the code needed for waituntils with an else ( ... )
819// Checks clauses once after registering for completion and runs them if completes
820// If not enough have run to satisfy predicate after one pass then the else is run
821Stmt * GenerateWaitUntilCore::genElseClauseBranch( const WaitUntilStmt * stmt, string & runName, string & arrName, vector<ClauseData *> & clauseData ) {
822    return new CompoundStmt( stmt->else_stmt->location,
823        {
824            genStatusCheckFor( stmt, clauseData, runName ),
825            new IfStmt( stmt->else_stmt->location,
826                genNotSatExpr( stmt, runName, arrName ),
827                ast::deepCopy( stmt->else_stmt )
828            )
829        }
830    );
831}
832
833Stmt * GenerateWaitUntilCore::genNoElseClauseBranch( const WaitUntilStmt * stmt, string & runName, string & arrName, string & pCountName, vector<ClauseData *> & clauseData ) {
834    CompoundStmt * whileBody = new CompoundStmt( stmt->location );
835    const CodeLocation & loc = stmt->location;
836
837    // generates: __CFA_maybe_park( &park_counter );
838    whileBody->push_back(
839        new ExprStmt( loc,
840            new UntypedExpr ( loc,
841                new NameExpr( loc, "__CFA_maybe_park" ),
842                { new AddressExpr( loc, new NameExpr( loc, pCountName ) ) }
843            )
844        )
845    );
846
847    whileBody->push_back( genStatusCheckFor( stmt, clauseData, runName ) );
848
849    return new CompoundStmt( loc,
850        {
851            new WhileDoStmt( loc,
852                genNotSatExpr( stmt, runName, arrName ),
853                whileBody,  // body
854                {}          // no inits
855            )
856        }
857    );
858}
859
860// generates the following decls for each clause to ensure the target expr and when_cond is only evaluated once
861// typeof(target) & __clause_target_0 = target;
862// bool __when_cond_0 = when_cond; // only generated if when_cond defined
863// select_node clause1;
864void GenerateWaitUntilCore::genClauseInits( const WaitUntilStmt * stmt, vector<ClauseData *> & clauseData, CompoundStmt * body, string & statusName, string & elseWhenName ) {
865    ClauseData * currClause;
866    for ( vector<ClauseData*>::size_type i = 0; i < stmt->clauses.size(); i++ ) {
867        currClause = new ClauseData( i, statusName );
868        currClause->nodeName = namer_node.newName();
869        currClause->targetName = namer_target.newName();
870        currClause->whenName = namer_when.newName();
871        clauseData.push_back(currClause);
872        const CodeLocation & cLoc = stmt->clauses.at(i)->location;
873
874        // typeof(target) & __clause_target_0 = target;
875        body->push_back(
876            new DeclStmt( cLoc,
877                new ObjectDecl( cLoc,
878                    currClause->targetName,
879                    new ReferenceType( 
880                        new TypeofType( new UntypedExpr( cLoc,
881                            new NameExpr( cLoc, "__CFA_select_get_type" ),
882                            { ast::deepCopy( stmt->clauses.at(i)->target ) }
883                        ))
884                    ),
885                    new SingleInit( cLoc, ast::deepCopy( stmt->clauses.at(i)->target ) )
886                )
887            )
888        );
889
890        // bool __when_cond_0 = when_cond; // only generated if when_cond defined
891        if ( stmt->clauses.at(i)->when_cond )
892            body->push_back(
893                new DeclStmt( cLoc,
894                    new ObjectDecl( cLoc,
895                        currClause->whenName,
896                        new BasicType( BasicType::Kind::Bool ),
897                        new SingleInit( cLoc, ast::deepCopy( stmt->clauses.at(i)->when_cond ) )
898                    )
899                )
900            );
901       
902        // select_node clause1;
903        body->push_back(
904            new DeclStmt( cLoc,
905                new ObjectDecl( cLoc,
906                    currClause->nodeName,
907                    new StructInstType( selectNodeDecl )
908                )
909            )
910        );
911    }
912
913    if ( stmt->else_stmt && stmt->else_cond ) {
914        body->push_back(
915            new DeclStmt( stmt->else_cond->location,
916                new ObjectDecl( stmt->else_cond->location,
917                    elseWhenName,
918                    new BasicType( BasicType::Kind::Bool ),
919                    new SingleInit( stmt->else_cond->location, ast::deepCopy( stmt->else_cond ) )
920                )
921            )
922        );
923    }
924}
925
926/*
927if ( clause_status == &clause1 ) ... clause 1 body ...
928...
929elif ( clause_status == &clausen ) ... clause n body ...
930*/
931Stmt * GenerateWaitUntilCore::buildOrCaseSwitch( const WaitUntilStmt * stmt, string & statusName, vector<ClauseData *> & data ) {
932    const CodeLocation & loc = stmt->location;
933
934    IfStmt * outerIf = nullptr;
935        IfStmt * lastIf = nullptr;
936
937        //adds an if/elif clause for each select clause address to run the corresponding clause stmt
938        for ( long unsigned int i = 0; i < data.size(); i++ ) {
939        const CodeLocation & cLoc = stmt->clauses.at(i)->location;
940
941                IfStmt * currIf = new IfStmt( cLoc,
942                        new UntypedExpr( cLoc, 
943                new NameExpr( cLoc, "?==?" ), 
944                {
945                    new NameExpr( cLoc, statusName ),
946                    new CastExpr( cLoc, 
947                        new AddressExpr( cLoc, new NameExpr( cLoc, data.at(i)->nodeName ) ),
948                        new BasicType( BasicType::Kind::LongUnsignedInt ), GeneratedFlag::ExplicitCast
949                    )
950                }
951            ),
952            genStmtBlock( stmt->clauses.at(i), data.at(i) )
953                );
954               
955                if ( i == 0 ) {
956                        outerIf = currIf;
957                } else {
958                        // add ifstmt to else of previous stmt
959                        lastIf->else_ = currIf;
960                }
961
962                lastIf = currIf;
963        }
964
965    return new CompoundStmt( loc,
966        {
967            new ExprStmt( loc, new UntypedExpr( loc, new NameExpr( loc, "park" ) ) ),
968            outerIf
969        }
970    );
971}
972
973Stmt * GenerateWaitUntilCore::recursiveOrIfGen( const WaitUntilStmt * stmt, vector<ClauseData *> & data, vector<ClauseData*>::size_type idx, string & elseWhenName ) {
974    if ( idx == data.size() ) {   // base case, gen last else
975        const CodeLocation & cLoc = stmt->else_stmt->location;
976        if ( !stmt->else_stmt ) // normal non-else gen
977            return buildOrCaseSwitch( stmt, data.at(0)->statusName, data );
978
979        Expr * raceFnCall = new UntypedExpr( stmt->location,
980            new NameExpr( stmt->location, "__select_node_else_race" ),
981            { new NameExpr( stmt->location, data.at(0)->nodeName ) }
982        );
983
984        if ( stmt->else_stmt && stmt->else_cond ) { // return else conditional on both when and race
985            return new IfStmt( cLoc,
986                new LogicalExpr( cLoc,
987                    new CastExpr( cLoc,
988                        new NameExpr( cLoc, elseWhenName ),
989                        new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
990                    ),
991                    new CastExpr( cLoc,
992                        raceFnCall,
993                        new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
994                    ),
995                    LogicalFlag::AndExpr
996                ),
997                ast::deepCopy( stmt->else_stmt ),
998                buildOrCaseSwitch( stmt, data.at(0)->statusName, data )
999            );
1000        }
1001
1002        // return else conditional on race
1003        return new IfStmt( stmt->else_stmt->location,
1004            raceFnCall,
1005            ast::deepCopy( stmt->else_stmt ),
1006            buildOrCaseSwitch( stmt, data.at(0)->statusName, data )
1007        );
1008    }
1009    const CodeLocation & cLoc = stmt->clauses.at(idx)->location;
1010
1011    Expr * baseCond = genSelectTraitCall( stmt->clauses.at(idx), data.at(idx), "register_select" );
1012    Expr * ifCond;
1013
1014    // If we have a when_cond make the register call conditional on it
1015    if ( stmt->clauses.at(idx)->when_cond ) {
1016        ifCond = new LogicalExpr( cLoc,
1017            new CastExpr( cLoc,
1018                new NameExpr( cLoc, data.at(idx)->whenName ), 
1019                new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
1020            ),
1021            new CastExpr( cLoc,
1022                baseCond,
1023                new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
1024            ),
1025            LogicalFlag::AndExpr
1026        );
1027    } else ifCond = baseCond;
1028
1029    return new CompoundStmt( cLoc,
1030        {   // gens: setup_clause( clause1, &status, 0p );
1031            new ExprStmt( cLoc,
1032                new UntypedExpr ( cLoc,
1033                    new NameExpr( cLoc, "setup_clause" ),
1034                    {
1035                        new NameExpr( cLoc, data.at(idx)->nodeName ),
1036                        new AddressExpr( cLoc, new NameExpr( cLoc, data.at(idx)->statusName ) ),
1037                        ConstantExpr::null( cLoc, new PointerType( new BasicType( BasicType::Kind::SignedInt ) ) )
1038                    }
1039                )
1040            ),
1041            // gens: if (__when_cond && register_select()) { clause body } else { ... recursiveOrIfGen ... }
1042            new IfStmt( cLoc,
1043                ifCond,
1044                genStmtBlock( stmt->clauses.at(idx), data.at(idx) ),
1045                recursiveOrIfGen( stmt, data, idx + 1, elseWhenName )
1046            )
1047        }
1048    );
1049}
1050
1051// This gens the special case of an all OR waituntil:
1052/*
1053int status = 0;
1054
1055typeof(target) & __clause_target_0 = target;
1056bool __when_cond_0 = when_cond; // only generated if when_cond defined
1057select_node clause1;
1058... generate above for rest of clauses ...
1059
1060try {
1061    setup_clause( clause1, &status, 0p );
1062    if ( __when_cond_0 && register_select( 1 ) ) {
1063        ... clause 1 body ...
1064    } else {
1065        ... recursively gen for each of n clauses ...
1066        setup_clause( clausen, &status, 0p );
1067        if ( __when_cond_n-1 && register_select( n ) ) {
1068            ... clause n body ...
1069        } else {
1070            if ( else_when ) ... else clause body ...
1071            else {
1072                park();
1073
1074                // after winning the race and before unpark() clause_status is set to be the winning clause index + 1
1075                if ( clause_status == &clause1) ... clause 1 body ...
1076                ...
1077                elif ( clause_status == &clausen ) ... clause n body ...
1078            }
1079        }
1080    }
1081}
1082finally {
1083    if ( __when_cond_1 && clause1.status != 0p) unregister_select( 1 ); // if registered unregister
1084    ...
1085    if ( __when_cond_n && clausen.status != 0p) unregister_select( n );
1086}
1087*/
1088Stmt * GenerateWaitUntilCore::genAllOr( const WaitUntilStmt * stmt ) {
1089    const CodeLocation & loc = stmt->location;
1090    string statusName = namer_status.newName();
1091    string elseWhenName = namer_when.newName();
1092    int numClauses = stmt->clauses.size();
1093    CompoundStmt * body = new CompoundStmt( stmt->location );
1094
1095    // Generates: unsigned long int status = 0;
1096    body->push_back( new DeclStmt( loc,
1097        new ObjectDecl( loc,
1098            statusName,
1099            new BasicType( BasicType::Kind::LongUnsignedInt ),
1100            new SingleInit( loc, ConstantExpr::from_int( loc, 0 ) )
1101        )
1102    ));
1103
1104    vector<ClauseData *> clauseData;
1105    genClauseInits( stmt, clauseData, body, statusName, elseWhenName );
1106
1107    vector<int> whenIndices; // track which clauses have whens
1108
1109    CompoundStmt * unregisters = new CompoundStmt( loc );
1110    Expr * ifCond;
1111    for ( int i = 0; i < numClauses; i++ ) {
1112        const CodeLocation & cLoc = stmt->clauses.at(i)->location;
1113        // Gens: node.status != 0p
1114        UntypedExpr * statusPtrCheck = new UntypedExpr( cLoc, 
1115            new NameExpr( cLoc, "?!=?" ), 
1116            {
1117                ConstantExpr::null( cLoc, new PointerType( new BasicType( BasicType::Kind::LongUnsignedInt ) ) ),
1118                new UntypedExpr( cLoc, 
1119                    new NameExpr( cLoc, "__get_clause_status" ), 
1120                    { new NameExpr( cLoc, clauseData.at(i)->nodeName ) } 
1121                ) 
1122            }
1123        );
1124
1125        // If we have a when_cond make the unregister call conditional on it
1126        if ( stmt->clauses.at(i)->when_cond ) {
1127            whenIndices.push_back(i);
1128            ifCond = new LogicalExpr( cLoc,
1129                new CastExpr( cLoc,
1130                    new NameExpr( cLoc, clauseData.at(i)->whenName ), 
1131                    new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
1132                ),
1133                new CastExpr( cLoc,
1134                    statusPtrCheck,
1135                    new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
1136                ),
1137                LogicalFlag::AndExpr
1138            );
1139        } else ifCond = statusPtrCheck;
1140       
1141        unregisters->push_back(
1142            new IfStmt( cLoc,
1143                ifCond,
1144                new ExprStmt( cLoc, genSelectTraitCall( stmt->clauses.at(i), clauseData.at(i), "unregister_select" ) ) 
1145            )
1146        );
1147    }
1148
1149    if ( whenIndices.empty() || whenIndices.size() != stmt->clauses.size() ) {
1150        body->push_back(
1151                new ast::TryStmt( loc,
1152                new CompoundStmt( loc, { recursiveOrIfGen( stmt, clauseData, 0, elseWhenName ) } ),
1153                {},
1154                new ast::FinallyClause( loc, unregisters )
1155            )
1156        );
1157    } else { // If all clauses have whens, we need to skip the waituntil if they are all false
1158        Expr * outerIfCond = new NameExpr( loc, clauseData.at( whenIndices.at(0) )->whenName );
1159        Expr * lastExpr = outerIfCond;
1160
1161        for ( vector<int>::size_type i = 1; i < whenIndices.size(); i++ ) {
1162            outerIfCond = new LogicalExpr( loc,
1163                new CastExpr( loc,
1164                    new NameExpr( loc, clauseData.at( whenIndices.at(i) )->whenName ), 
1165                    new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
1166                ),
1167                new CastExpr( loc,
1168                    lastExpr,
1169                    new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
1170                ),
1171                LogicalFlag::OrExpr
1172            );
1173            lastExpr = outerIfCond;
1174        }
1175
1176        body->push_back(
1177                new ast::TryStmt( loc,
1178                new CompoundStmt( loc, 
1179                    {
1180                        new IfStmt( loc,
1181                            outerIfCond,
1182                            recursiveOrIfGen( stmt, clauseData, 0, elseWhenName )
1183                        )
1184                    }
1185                ),
1186                {},
1187                new ast::FinallyClause( loc, unregisters )
1188            )
1189        );
1190    }
1191
1192    for ( ClauseData * datum : clauseData )
1193        delete datum;
1194
1195    return body;
1196}
1197
1198Stmt * GenerateWaitUntilCore::postvisit( const WaitUntilStmt * stmt ) {
1199    if ( !selectNodeDecl )
1200        SemanticError( stmt, "waituntil statement requires #include <waituntil.hfa>" );
1201
1202    // Prep clause tree to figure out how to set initial statuses
1203    // setTreeSizes( stmt->predicateTree );
1204    if ( paintWhenTree( stmt->predicateTree ) ) // if this returns true we can special case since tree is all OR's
1205        return genAllOr( stmt );
1206
1207    CompoundStmt * tryBody = new CompoundStmt( stmt->location );
1208    CompoundStmt * body = new CompoundStmt( stmt->location );
1209    string statusArrName = namer_status.newName();
1210    string pCountName = namer_park.newName();
1211    string satName = namer_sat.newName();
1212    string runName = namer_run.newName();
1213    string elseWhenName = namer_when.newName();
1214    int numClauses = stmt->clauses.size();
1215    addPredicates( stmt, satName, runName );
1216
1217    const CodeLocation & loc = stmt->location;
1218
1219    // Generates: int park_counter = 0;
1220    body->push_back( new DeclStmt( loc,
1221        new ObjectDecl( loc,
1222            pCountName,
1223            new BasicType( BasicType::Kind::SignedInt ),
1224            new SingleInit( loc, ConstantExpr::from_int( loc, 0 ) )
1225        )
1226    ));
1227
1228    // Generates: int clause_statuses[3] = { 0 };
1229    body->push_back( new DeclStmt( loc,
1230        new ObjectDecl( loc,
1231            statusArrName,
1232            new ArrayType( new BasicType( BasicType::Kind::LongUnsignedInt ), ConstantExpr::from_int( loc, numClauses ), LengthFlag::FixedLen, DimensionFlag::DynamicDim ),
1233            new ListInit( loc,
1234                {
1235                    new SingleInit( loc, ConstantExpr::from_int( loc, 0 ) )
1236                }
1237            )
1238        )
1239    ));
1240
1241    vector<ClauseData *> clauseData;
1242    genClauseInits( stmt, clauseData, body, statusArrName, elseWhenName );
1243
1244    vector<pair<int, WaitUntilStmt::ClauseNode *>> ambiguousClauses;       // list of ambiguous clauses
1245    vector<int> andWhenClauses;    // list of clauses that have an AND op as a direct parent and when_cond defined
1246
1247    collectWhens( stmt->predicateTree, ambiguousClauses, andWhenClauses );
1248
1249    // This is only needed for clauses that have AND as a parent and a when_cond defined
1250    // generates: if ( ! when_cond_0 ) clause_statuses_0 = __SELECT_RUN;
1251    for ( int idx : andWhenClauses ) {
1252        const CodeLocation & cLoc = stmt->clauses.at(idx)->location;
1253        body->push_back( 
1254            new IfStmt( cLoc,
1255                new UntypedExpr ( cLoc,
1256                    new NameExpr( cLoc, "!?" ),
1257                    { new NameExpr( cLoc, clauseData.at(idx)->whenName ) }
1258                ),  // IfStmt cond
1259                new ExprStmt( cLoc,
1260                    new UntypedExpr ( cLoc,
1261                        new NameExpr( cLoc, "?=?" ),
1262                        {
1263                            new UntypedExpr ( cLoc, 
1264                                new NameExpr( cLoc, "?[?]" ),
1265                                {
1266                                    new NameExpr( cLoc, statusArrName ),
1267                                    ConstantExpr::from_int( cLoc, idx )
1268                                }
1269                            ),
1270                            new NameExpr( cLoc, "__SELECT_RUN" )
1271                        }
1272                    )
1273                )  // IfStmt then
1274            )
1275        );
1276    }
1277
1278    // Only need to generate conditional initial state setting for ambiguous when clauses
1279    if ( !ambiguousClauses.empty() ) {
1280        body->push_back( genWhenStateConditions( stmt, clauseData, ambiguousClauses, 0 ) );
1281    }
1282
1283    // generates the following for each clause:
1284    // setup_clause( clause1, &clause_statuses[0], &park_counter );
1285    // register_select(A, clause1);
1286    for ( int i = 0; i < numClauses; i++ ) {
1287        setUpClause( stmt->clauses.at(i), clauseData.at(i), pCountName, tryBody );
1288    }
1289
1290    // generate satisfy logic based on if there is an else clause and if it is conditional
1291    if ( stmt->else_stmt && stmt->else_cond ) { // gen both else/non else branches
1292        tryBody->push_back(
1293            new IfStmt( stmt->else_cond->location,
1294                new NameExpr( stmt->else_cond->location, elseWhenName ),
1295                genElseClauseBranch( stmt, runName, statusArrName, clauseData ),
1296                genNoElseClauseBranch( stmt, runName, statusArrName, pCountName, clauseData )
1297            )
1298        );
1299    } else if ( !stmt->else_stmt ) { // normal gen
1300        tryBody->push_back( genNoElseClauseBranch( stmt, runName, statusArrName, pCountName, clauseData ) );
1301    } else { // generate just else
1302        tryBody->push_back( genElseClauseBranch( stmt, runName, statusArrName, clauseData ) );
1303    }
1304
1305    // Collection of unregister calls on resources to be put in finally clause
1306    // for each clause:
1307    // if ( !__CFA_has_clause_run( clause_statuses[i] )) && unregister_select( ... , clausei ) ) { ... clausei stmt ... }
1308    // OR if when( ... ) defined on resource
1309    // if ( when_cond_i && (!__CFA_has_clause_run( clause_statuses[i] )) && unregister_select( ... , clausei ) ) { ... clausei stmt ... }
1310    CompoundStmt * unregisters = new CompoundStmt( loc );
1311
1312    Expr * statusExpr; // !__CFA_has_clause_run( clause_statuses[i] )
1313    for ( int i = 0; i < numClauses; i++ ) {
1314        const CodeLocation & cLoc = stmt->clauses.at(i)->location;
1315
1316        // Generates: !__CFA_has_clause_run( clause_statuses[i] )
1317        statusExpr = new UntypedExpr ( cLoc,
1318            new NameExpr( cLoc, "!?" ),
1319            {
1320                new UntypedExpr ( cLoc, 
1321                    new NameExpr( cLoc, "__CFA_has_clause_run" ),
1322                    {
1323                        genArrAccessExpr( cLoc, i, statusArrName )
1324                    }
1325                )
1326            }
1327        );
1328       
1329        // Generates:
1330        // (!__CFA_has_clause_run( clause_statuses[i] )) && unregister_select( ... , clausei );
1331        statusExpr = new LogicalExpr( cLoc,
1332            new CastExpr( cLoc,
1333                statusExpr, 
1334                new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
1335            ),
1336            new CastExpr( cLoc,
1337                genSelectTraitCall( stmt->clauses.at(i), clauseData.at(i), "unregister_select" ),
1338                new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
1339            ),
1340            LogicalFlag::AndExpr
1341        );
1342       
1343        // if when cond defined generates:
1344        // when_cond_i && (!__CFA_has_clause_run( clause_statuses[i] )) && unregister_select( ... , clausei );
1345        if ( stmt->clauses.at(i)->when_cond )
1346            statusExpr = new LogicalExpr( cLoc,
1347                new CastExpr( cLoc,
1348                    new NameExpr( cLoc, clauseData.at(i)->whenName ), 
1349                    new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
1350                ),
1351                new CastExpr( cLoc,
1352                    statusExpr,
1353                    new BasicType( BasicType::Kind::Bool ), GeneratedFlag::ExplicitCast
1354                ),
1355                LogicalFlag::AndExpr
1356            );
1357
1358        // generates:
1359        // if ( statusExpr ) { ... clausei stmt ... }
1360        unregisters->push_back( 
1361            new IfStmt( cLoc,
1362                statusExpr,
1363                new CompoundStmt( cLoc,
1364                    {
1365                        new IfStmt( cLoc,
1366                            genSelectTraitCall( stmt->clauses.at(i), clauseData.at(i), "on_selected" ),
1367                            ast::deepCopy( stmt->clauses.at(i)->stmt )
1368                        )
1369                    }
1370                )
1371            )
1372        );
1373
1374        // // generates:
1375        // // if ( statusExpr ) { ... clausei stmt ... }
1376        // unregisters->push_back(
1377        //     new IfStmt( cLoc,
1378        //         statusExpr,
1379        //         genStmtBlock( stmt->clauses.at(i), clauseData.at(i) )
1380        //     )
1381        // );
1382    }
1383
1384    body->push_back( 
1385        new ast::TryStmt(
1386            loc,
1387            tryBody,
1388            {},
1389            new ast::FinallyClause( loc, unregisters )
1390        )
1391    );
1392
1393    for ( ClauseData * datum : clauseData )
1394        delete datum;
1395
1396    return body;
1397}
1398
1399// To add the predicates at global scope we need to do it in a second pass
1400// Predicates are added after "struct select_node { ... };"
1401class AddPredicateDecls final : public WithDeclsToAdd<> {
1402    vector<FunctionDecl *> & satFns;
1403    const StructDecl * selectNodeDecl = nullptr;
1404
1405  public:
1406    void previsit( const StructDecl * decl ) {
1407        if ( !decl->body ) {
1408            return;
1409        } else if ( "select_node" == decl->name ) {
1410            assert( !selectNodeDecl );
1411            selectNodeDecl = decl;
1412            for ( FunctionDecl * fn : satFns )
1413                declsToAddAfter.push_back(fn);           
1414        }
1415    }
1416    AddPredicateDecls( vector<FunctionDecl *> & satFns ): satFns(satFns) {}
1417};
1418
1419void generateWaitUntil( TranslationUnit & translationUnit ) {
1420    vector<FunctionDecl *> satFns;
1421        Pass<GenerateWaitUntilCore>::run( translationUnit, satFns );
1422    Pass<AddPredicateDecls>::run( translationUnit, satFns );
1423}
1424
1425} // namespace Concurrency
1426
1427// Local Variables: //
1428// tab-width: 4 //
1429// mode: c++ //
1430// compile-command: "make install" //
1431// End: //
Note: See TracBrowser for help on using the repository browser.