source: src/ControlStruct/LabelFixer.cc@ 893256d

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay gc_noraii jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since 893256d was 0a0a65b, checked in by Rob Schluntz <rschlunt@…>, 10 years ago

fix duplicate label definitions across functions
  • Property mode set to 100644
File size: 7.7 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// LabelFixer.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 : Wed Jul 08 12:36:46 2015
13// Update Count : 145
14//
15
16#include <list>
17#include <cassert>
18
19#include "LabelFixer.h"
20#include "MLEMutator.h"
21#include "SynTree/Expression.h"
22#include "SynTree/Statement.h"
23#include "SynTree/Declaration.h"
24#include "utility.h"
25
26#include <iostream>
27
28namespace ControlStruct {
29 LabelFixer::Entry::Entry( Statement *to, Statement *from ) : definition ( to ) {
30 if ( from != 0 ) {
31 UsageLoc loc; loc.stmt = from;
32 usage.push_back( loc );
33 }
34 }
35
36 LabelFixer::Entry::Entry( Statement *to, Expression *from ) : definition ( to ) {
37 if ( from != 0 ) {
38 UsageLoc loc; loc.expr = from;
39 usage.push_back( loc );
40 }
41 }
42
43
44 bool LabelFixer::Entry::insideLoop() {
45 return ( dynamic_cast< ForStmt * > ( definition ) ||
46 dynamic_cast< WhileStmt * > ( definition ) );
47 }
48
49 void LabelFixer::Entry::UsageLoc::accept( Visitor & visitor ) {
50 if ( dynamic_cast< Statement * >( stmt ) ) {
51 stmt->accept( visitor );
52 } else {
53 expr->accept( visitor );
54 }
55 }
56
57 LabelFixer::LabelFixer( LabelGenerator *gen ) : generator ( gen ) {
58 if ( generator == 0 )
59 generator = LabelGenerator::getGenerator();
60 }
61
62 void LabelFixer::visit( FunctionDecl *functionDecl ) {
63 // need to go into a nested function in a fresh state
64 std::map < Label, Entry *> oldLabelTable = labelTable;
65 labelTable.clear();
66
67 maybeAccept( functionDecl->get_statements(), *this );
68
69 MLEMutator mlemut( resolveJumps(), generator );
70 functionDecl->acceptMutator( mlemut );
71
72 // and remember the outer function's labels when
73 // returning to it
74 labelTable = oldLabelTable;
75 }
76
77 // prune to at most one label definition for each statement
78 void LabelFixer::visit( Statement *stmt ) {
79 currentStatement = stmt;
80 std::list< Label > &labels = stmt->get_labels();
81
82 if ( ! labels.empty() ) {
83 // only remember one label for each statement
84 Label current = setLabelsDef( labels, stmt );
85 labels.clear();
86 labels.push_front( current );
87 } // if
88 }
89
90 void LabelFixer::visit( BranchStmt *branchStmt ) {
91 visit ( ( Statement * )branchStmt );
92
93 // for labeled branches, add an entry to the label table
94 Label target = branchStmt->get_target();
95 if ( target != "" ) {
96 setLabelsUsg( target, branchStmt );
97 }
98 }
99
100 void LabelFixer::visit( UntypedExpr *untyped ) {
101 if ( NameExpr * func = dynamic_cast< NameExpr * >( untyped->get_function() ) ) {
102 if ( func->get_name() == "&&" ) {
103 NameExpr * arg = dynamic_cast< NameExpr * >( untyped->get_args().front() );
104 Label target = arg->get_name();
105 assert( target != "" );
106 setLabelsUsg( target, untyped );
107 } else {
108 Visitor::visit( untyped );
109 }
110 }
111 }
112
113
114 // sets the definition of the labelTable entry to be the provided
115 // statement for every label in the list parameter. Happens for every kind of statement
116 Label LabelFixer::setLabelsDef( std::list< Label > &llabel, Statement *definition ) {
117 assert( definition != 0 );
118 assert( llabel.size() > 0 );
119
120 Entry * e = new Entry( definition );
121
122 for ( std::list< Label >::iterator i = llabel.begin(); i != llabel.end(); i++ ) {
123 if ( labelTable.find( *i ) == labelTable.end() ) {
124 // all labels on this statement need to use the same entry, so this should only be created once
125 // undefined and unused until now, add an entry
126 labelTable[ *i ] = e;
127 } else if ( labelTable[ *i ]->defined() ) {
128 // defined twice, error
129 throw SemanticError( "Duplicate definition of label: " + *i );
130 } else {
131 // used previously, but undefined until now -> link with this entry
132 Entry * oldEntry = labelTable[ *i ];
133 e->add_uses( *oldEntry );
134 labelTable[ *i ] = e;
135 } // if
136 } // for
137
138 // produce one of the labels attached to this statement to be
139 // temporarily used as the canonical label
140 return labelTable[ llabel.front() ]->get_label();
141 }
142
143 // Remember all uses of a label.
144 template< typename UsageNode >
145 void LabelFixer::setLabelsUsg( Label orgValue, UsageNode *use ) {
146 assert( use != 0 );
147
148 if ( labelTable.find( orgValue ) != labelTable.end() ) {
149 // the label has been defined or used before
150 labelTable[ orgValue ]->add_use( use );
151 } else {
152 labelTable[ orgValue ] = new Entry( 0, use );
153 }
154 }
155
156 class LabelGetter : public Visitor {
157 public:
158 LabelGetter( Label &label ) : label( label ) {}
159
160 virtual void visit( BranchStmt * branchStmt ) {
161 label = branchStmt->get_target();
162 }
163
164 virtual void visit( UntypedExpr * untyped ) {
165 NameExpr * name = dynamic_cast< NameExpr * >( untyped->get_function() );
166 assert( name );
167 assert( name->get_name() == "&&" );
168 NameExpr * arg = dynamic_cast< NameExpr * >( untyped->get_args().front() );
169 assert( arg );
170 label = arg->get_name();
171 }
172
173 private:
174 Label &label;
175 };
176
177 class LabelSetter : public Visitor {
178 public:
179 LabelSetter( Label label ) : label( label ) {}
180
181 virtual void visit( BranchStmt * branchStmt ) {
182 branchStmt->set_target( label );
183 }
184
185 virtual void visit( UntypedExpr * untyped ) {
186 NameExpr * name = dynamic_cast< NameExpr * >( untyped->get_function() );
187 assert( name );
188 assert( name->get_name() == "&&" );
189 NameExpr * arg = dynamic_cast< NameExpr * >( untyped->get_args().front() );
190 assert( arg );
191 arg->set_name( label );
192 }
193
194 private:
195 Label label;
196 };
197
198 // Ultimately builds a table that maps a label to its defining statement.
199 // In the process,
200 std::map<Label, Statement * > *LabelFixer::resolveJumps() throw ( SemanticError ) {
201 std::map< Statement *, Entry * > def_us;
202
203 // combine the entries for all labels that target the same location
204 for ( std::map< Label, Entry *>::iterator i = labelTable.begin(); i != labelTable.end(); ++i ) {
205 Entry *e = i->second;
206
207 if ( def_us.find ( e->get_definition() ) == def_us.end() ) {
208 def_us[ e->get_definition() ] = e;
209 } else if ( e->used() ) {
210 def_us[ e->get_definition() ]->add_uses( *e );
211 }
212 }
213
214 // create a unique label for each target location.
215 for ( std::map< Statement *, Entry * >::iterator i = def_us.begin(); i != def_us.end(); ++i ) {
216 Statement *to = (*i).first;
217 Entry * entry = (*i).second;
218 std::list< Entry::UsageLoc > &from = entry->get_uses();
219
220 // no label definition found
221 if ( to == 0 ) {
222 Label undef;
223 LabelGetter getLabel( undef );
224 from.back().accept( getLabel );
225 // Label undef = getLabel( from.back()->get_target() );
226 throw SemanticError ( "'" + undef + "' label not defined");
227 } // if
228
229 // generate a new label, and attach it to its defining statement as the only label on that statement
230 Label finalLabel = generator->newLabel( to->get_labels().back() );
231 entry->set_label( finalLabel );
232
233 to->get_labels().clear();
234 to->get_labels().push_back( finalLabel );
235
236 // redirect each of the source branch statements to the new target label
237 for ( std::list< Entry::UsageLoc >::iterator j = from.begin(); j != from.end(); ++j ) {
238 LabelSetter setLabel( finalLabel );
239 (*j).accept( setLabel );
240 // setLabel( *j, finalLabel );
241
242 // BranchStmt *jump = *j;
243 // assert( jump != 0 );
244 // jump->set_target( finalLabel );
245 } // for
246 } // for
247
248 // create a table where each label maps to its defining statement
249 std::map< Label, Statement * > *ret = new std::map< Label, Statement * >();
250 for ( std::map< Statement *, Entry * >::iterator i = def_us.begin(); i != def_us.end(); ++i ) {
251 (*ret)[ (*i).second->get_label() ] = (*i).first;
252 }
253
254 return ret;
255 }
256} // namespace ControlStruct
257
258// Local Variables: //
259// tab-width: 4 //
260// mode: c++ //
261// compile-command: "make install" //
262// End: //
Note: See TracBrowser for help on using the repository browser.