source: src/ControlStruct/MLEMutator.cc @ e39aa0f

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsctordeferred_resndemanglerenumforall-pointer-decaygc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since e39aa0f was e39aa0f, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

overhaul MLE code, attach label to break/continue statements so it can be used to generate dtor calls, mutate continue statements into goto statements so dtor generation works correctly

  • Property mode set to 100644
File size: 9.2 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 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// MLEMutator.cc --
8//
9// Author           : Rodolfo G. Esteves
10// Created On       : Mon May 18 07:44:20 2015
11// Last Modified By : Rob Schluntz
12// Last Modified On : Mon Jul 20 13:58:35 2015
13// Update Count     : 176
14//
15
16// NOTE: There are two known subtle differences from the code that uC++
17// generates for the same input
18// -CFA puts the break label inside at the end of a switch, uC++ puts it after
19// -CFA puts the break label after a block, uC++ puts it inside at the end
20// we don't yet know if these differences are important, but if they are then
21// the fix would go in this file, since this is where these labels are generated.
22
23#include <cassert>
24#include <algorithm>
25
26#include "MLEMutator.h"
27#include "SynTree/Statement.h"
28#include "SynTree/Expression.h"
29#include "SynTree/Attribute.h"
30
31namespace ControlStruct {
32        MLEMutator::~MLEMutator() {
33                delete targetTable;
34                targetTable = 0;
35        }
36        namespace {
37                Statement * isLoop( Statement * stmt ) { return dynamic_cast< WhileStmt * >( stmt ) ? stmt : dynamic_cast< ForStmt * >( stmt ) ? stmt : 0; }
38        }
39
40        // break labels have to come after the statement they break out of,
41        // so mutate a statement, then if they inform us through the breakLabel field
42        // tha they need a place to jump to on a break statement, add the break label
43        // to the body of statements
44        void MLEMutator::fixBlock( std::list< Statement * > &kids ) {
45                for ( std::list< Statement * >::iterator k = kids.begin(); k != kids.end(); k++ ) {
46                        *k = (*k)->acceptMutator(*this);
47
48                        if ( ! get_breakLabel().empty() ) {
49                                std::list< Statement * >::iterator next = k+1;
50                                std::list<Label> ls; ls.push_back( get_breakLabel() );
51                                kids.insert( next, new NullStmt( ls ) );
52                                set_breakLabel("");
53                        } // if
54                } // for
55        }
56
57        CompoundStmt* MLEMutator::mutate( CompoundStmt *cmpndStmt ) {
58                bool labeledBlock = !(cmpndStmt->get_labels().empty());
59                if ( labeledBlock ) {
60                        Label brkLabel = generator->newLabel("blockBreak");
61                        enclosingControlStructures.push_back( Entry( cmpndStmt, brkLabel ) );
62                } // if
63
64                // a child statement may set the break label
65                // - if they do, attach it to the next statement
66                std::list< Statement * > &kids = cmpndStmt->get_kids();
67                fixBlock( kids );
68
69                if ( labeledBlock ) {
70                        assert( ! enclosingControlStructures.empty() );
71                        if ( ! enclosingControlStructures.back().useBreakExit().empty() ) {
72                                set_breakLabel( enclosingControlStructures.back().useBreakExit() );
73                        }
74                        enclosingControlStructures.pop_back();
75                } // if
76
77                return cmpndStmt;
78        }
79
80        template< typename LoopClass >
81        Statement *MLEMutator::handleLoopStmt( LoopClass *loopStmt ) {
82                // remember this as the most recent enclosing loop, then mutate
83                // the body of the loop -- this will determine whether brkLabel
84                // and contLabel are used with branch statements
85                // and will recursively do the same to nested loops
86                Label brkLabel = generator->newLabel("loopBreak");
87                Label contLabel = generator->newLabel("loopContinue");
88                enclosingControlStructures.push_back( Entry( loopStmt, brkLabel, contLabel ) );
89                loopStmt->set_body ( loopStmt->get_body()->acceptMutator( *this ) );
90
91                // sanity check that the enclosing loops have been popped correctly
92                Entry &e = enclosingControlStructures.back();
93                assert ( e == loopStmt );
94
95                // this will take the necessary steps to add definitions of the previous
96                // two labels, if they are used.
97                loopStmt->set_body( mutateLoop( loopStmt->get_body(), e ) );
98                enclosingControlStructures.pop_back();
99
100                return loopStmt;
101        }
102
103        Statement *MLEMutator::mutate( CaseStmt *caseStmt ) {
104                caseStmt->set_condition( maybeMutate( caseStmt->get_condition(), *this ) );
105                fixBlock( caseStmt->get_statements() );
106
107                return caseStmt;
108        }
109
110        template< typename SwitchClass >
111        Statement *MLEMutator::handleSwitchStmt( SwitchClass *switchStmt ) {
112                // generate a label for breaking out of a labeled switch
113                Label brkLabel = generator->newLabel("switchBreak");
114                enclosingControlStructures.push_back( Entry(switchStmt, brkLabel) );
115                mutateAll( switchStmt->get_branches(), *this );
116
117                Entry &e = enclosingControlStructures.back();
118                assert ( e == switchStmt );
119
120                // only generate break label if labeled break is used
121                if (e.isBreakUsed()) {
122                        // for the purposes of keeping switch statements uniform (i.e. all statements that are
123                        // direct children of a switch should be CastStmts), append the exit label + break to the
124                        // last case statement; create a default case if there are no cases
125                        std::list< Statement * > &branches = switchStmt->get_branches();
126                        if ( branches.empty() ) {
127                                branches.push_back( CaseStmt::makeDefault() );
128                        }
129
130                        if ( CaseStmt * c = dynamic_cast< CaseStmt * >( branches.back() ) ) {
131                                std::list<Label> temp; temp.push_back( brkLabel );
132                                c->get_statements().push_back( new BranchStmt( temp, Label("brkLabel"), BranchStmt::Break ) );
133                        } else assert(0); // as of this point, all branches of a switch are still CaseStmts
134                }
135
136                assert ( enclosingControlStructures.back() == switchStmt );
137                enclosingControlStructures.pop_back();
138                return switchStmt;
139        }
140
141        Statement *MLEMutator::mutate( BranchStmt *branchStmt ) throw ( SemanticError ) {
142                std::string originalTarget = branchStmt->get_originalTarget();
143
144                std::list< Entry >::reverse_iterator targetEntry;
145                if ( branchStmt->get_type() == BranchStmt::Goto ) {
146                        return branchStmt;
147                } else if ( branchStmt->get_type() == BranchStmt::Continue) {
148                        // continue target must be a loop
149                        if ( branchStmt->get_target() == "" ) {
150                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), [](Entry &e) { return isLoop( e.get_controlStructure() ); } );
151                        } else {
152                                // labelled continue - lookup label in table ot find attached control structure
153                                targetEntry = std::find( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), (*targetTable)[branchStmt->get_target()] );
154                        }
155                        if ( targetEntry == enclosingControlStructures.rend() || ! isLoop( targetEntry->get_controlStructure() ) ) {
156                                throw SemanticError( "'continue' target must be an enclosing loop: " + originalTarget );
157                        }
158                } else if ( branchStmt->get_type() == BranchStmt::Break ) {
159                        if ( enclosingControlStructures.empty() ) throw SemanticError( "'break' outside a loop, switch, or labelled block" );
160                        targetEntry = enclosingControlStructures.rbegin();
161                } else {
162                        assert( false );
163                }
164
165                if ( branchStmt->get_target() != "" && targetTable->find( branchStmt->get_target() ) == targetTable->end() ) {
166                        throw SemanticError("The label defined in the exit loop statement does not exist: " + originalTarget );  // shouldn't happen (since that's already checked)
167                }
168
169                // xxx - possibly remove this
170                // what about exiting innermost block or switch???
171                // if ( enclosingControlStructures.back() == (*targetEntry) )
172                //      return branchStmt;                              // exit the innermost loop (labels unnecessary)
173
174                // branch error checks, get the appropriate label name and create a goto
175                Label exitLabel;
176                switch ( branchStmt->get_type() ) {
177                  case BranchStmt::Break:
178                                assert( targetEntry->useBreakExit() != "");
179                                exitLabel = targetEntry->useBreakExit();
180                                break;
181                  case BranchStmt::Continue:
182                                assert( targetEntry->useContExit() != "");
183                                exitLabel = targetEntry->useContExit();
184                                break;
185                  default:
186                                assert(0);                                      // shouldn't be here
187                } // switch
188
189                if ( branchStmt->get_target() == "" && branchStmt->get_type() != BranchStmt::Continue ) {
190                        // unlabelled break/continue - can keep branch as break/continue for extra semantic information, but add
191                        // exitLabel as its destination so that label passes can easily determine where the break/continue goes to
192                        branchStmt->set_target( exitLabel );
193                        return branchStmt;
194                } else {
195                        // labelled break/continue - can't easily emulate this with break and continue, so transform into a goto
196                        delete branchStmt;
197                        return new BranchStmt( std::list<Label>(), exitLabel, BranchStmt::Goto );
198                }
199        }
200
201        Statement *MLEMutator::mutateLoop( Statement *bodyLoop, Entry &e ) {
202                // ensure loop body is a block
203                CompoundStmt *newBody;
204                if ( ! (newBody = dynamic_cast<CompoundStmt *>( bodyLoop )) ) {
205                        newBody = new CompoundStmt( std::list< Label >() );
206                        newBody->get_kids().push_back( bodyLoop );
207                } // if
208
209                // only generate these when needed
210
211                if ( e.isContUsed() ) {
212                        // continue label goes in the body as the last statement
213                        std::list< Label > labels; labels.push_back( e.useContExit() );
214                        newBody->get_kids().push_back( new NullStmt( labels ) );
215                }
216
217                if ( e.isBreakUsed() ) {
218                        // break label goes after the loop -- it'll get set by the
219                        // outer mutator if we do this
220                        set_breakLabel( e.useBreakExit() );
221                }
222
223                return newBody;
224        }
225
226        Statement *MLEMutator::mutate( WhileStmt *whileStmt ) {
227                return handleLoopStmt( whileStmt );
228        }
229
230        Statement *MLEMutator::mutate( ForStmt *forStmt ) {
231                return handleLoopStmt( forStmt );
232        }
233
234        Statement *MLEMutator::mutate( SwitchStmt *switchStmt ) {
235                return handleSwitchStmt( switchStmt );
236        }
237
238        Statement *MLEMutator::mutate( ChooseStmt *switchStmt ) {
239                return handleSwitchStmt( switchStmt );
240        }
241
242} // namespace ControlStruct
243
244// Local Variables: //
245// tab-width: 4 //
246// mode: c++ //
247// compile-command: "make install" //
248// End: //
Note: See TracBrowser for help on using the repository browser.