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 | |
---|
31 | namespace 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: // |
---|