[51587aa] | 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 | // |
---|
[a08ba92] | 7 | // LabelFixer.cc -- |
---|
[51587aa] | 8 | // |
---|
[843054c2] | 9 | // Author : Rodolfo G. Esteves |
---|
[51587aa] | 10 | // Created On : Mon May 18 07:44:20 2015 |
---|
[1869adf] | 11 | // Last Modified By : Rob Schluntz |
---|
[0a0a65b] | 12 | // Last Modified On : Wed Jul 08 12:36:46 2015 |
---|
| 13 | // Update Count : 145 |
---|
[51587aa] | 14 | // |
---|
[a08ba92] | 15 | |
---|
[51b7345] | 16 | #include <list> |
---|
| 17 | #include <cassert> |
---|
| 18 | |
---|
| 19 | #include "LabelFixer.h" |
---|
| 20 | #include "MLEMutator.h" |
---|
[1869adf] | 21 | #include "SynTree/Expression.h" |
---|
[51b7345] | 22 | #include "SynTree/Statement.h" |
---|
| 23 | #include "SynTree/Declaration.h" |
---|
| 24 | #include "utility.h" |
---|
| 25 | |
---|
[46cbfe1] | 26 | #include <iostream> |
---|
| 27 | |
---|
[51b7345] | 28 | namespace ControlStruct { |
---|
[1869adf] | 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 | } |
---|
[a08ba92] | 41 | } |
---|
[d9a0e76] | 42 | |
---|
[1869adf] | 43 | |
---|
[a08ba92] | 44 | bool LabelFixer::Entry::insideLoop() { |
---|
| 45 | return ( dynamic_cast< ForStmt * > ( definition ) || |
---|
[46cbfe1] | 46 | dynamic_cast< WhileStmt * > ( definition ) ); |
---|
[a08ba92] | 47 | } |
---|
[d9a0e76] | 48 | |
---|
[1869adf] | 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 | |
---|
[a08ba92] | 57 | LabelFixer::LabelFixer( LabelGenerator *gen ) : generator ( gen ) { |
---|
| 58 | if ( generator == 0 ) |
---|
| 59 | generator = LabelGenerator::getGenerator(); |
---|
| 60 | } |
---|
[51b7345] | 61 | |
---|
[a08ba92] | 62 | void LabelFixer::visit( FunctionDecl *functionDecl ) { |
---|
[0a0a65b] | 63 | // need to go into a nested function in a fresh state |
---|
| 64 | std::map < Label, Entry *> oldLabelTable = labelTable; |
---|
| 65 | labelTable.clear(); |
---|
| 66 | |
---|
[be5aa1b] | 67 | maybeAccept( functionDecl->get_statements(), *this ); |
---|
[d9a0e76] | 68 | |
---|
[a08ba92] | 69 | MLEMutator mlemut( resolveJumps(), generator ); |
---|
| 70 | functionDecl->acceptMutator( mlemut ); |
---|
[0a0a65b] | 71 | |
---|
| 72 | // and remember the outer function's labels when |
---|
| 73 | // returning to it |
---|
| 74 | labelTable = oldLabelTable; |
---|
[a08ba92] | 75 | } |
---|
[51b7345] | 76 | |
---|
[46cbfe1] | 77 | // prune to at most one label definition for each statement |
---|
[a08ba92] | 78 | void LabelFixer::visit( Statement *stmt ) { |
---|
[1869adf] | 79 | currentStatement = stmt; |
---|
[a08ba92] | 80 | std::list< Label > &labels = stmt->get_labels(); |
---|
[51b7345] | 81 | |
---|
[a08ba92] | 82 | if ( ! labels.empty() ) { |
---|
[46cbfe1] | 83 | // only remember one label for each statement |
---|
[a08ba92] | 84 | Label current = setLabelsDef( labels, stmt ); |
---|
| 85 | labels.clear(); |
---|
| 86 | labels.push_front( current ); |
---|
| 87 | } // if |
---|
| 88 | } |
---|
[d9a0e76] | 89 | |
---|
[a08ba92] | 90 | void LabelFixer::visit( BranchStmt *branchStmt ) { |
---|
[46cbfe1] | 91 | visit ( ( Statement * )branchStmt ); |
---|
[d9a0e76] | 92 | |
---|
[46cbfe1] | 93 | // for labeled branches, add an entry to the label table |
---|
| 94 | Label target = branchStmt->get_target(); |
---|
| 95 | if ( target != "" ) { |
---|
[a08ba92] | 96 | setLabelsUsg( target, branchStmt ); |
---|
[46cbfe1] | 97 | } |
---|
[d9a0e76] | 98 | } |
---|
| 99 | |
---|
[1869adf] | 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 | |
---|
[46cbfe1] | 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 |
---|
[a08ba92] | 116 | Label LabelFixer::setLabelsDef( std::list< Label > &llabel, Statement *definition ) { |
---|
| 117 | assert( definition != 0 ); |
---|
[46cbfe1] | 118 | assert( llabel.size() > 0 ); |
---|
| 119 | |
---|
[954463b8] | 120 | Entry * e = new Entry( definition ); |
---|
| 121 | |
---|
[46cbfe1] | 122 | for ( std::list< Label >::iterator i = llabel.begin(); i != llabel.end(); i++ ) { |
---|
[954463b8] | 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 |
---|
[46cbfe1] | 125 | // undefined and unused until now, add an entry |
---|
[954463b8] | 126 | labelTable[ *i ] = e; |
---|
| 127 | } else if ( labelTable[ *i ]->defined() ) { |
---|
[46cbfe1] | 128 | // defined twice, error |
---|
| 129 | throw SemanticError( "Duplicate definition of label: " + *i ); |
---|
| 130 | } else { |
---|
[954463b8] | 131 | // used previously, but undefined until now -> link with this entry |
---|
| 132 | Entry * oldEntry = labelTable[ *i ]; |
---|
[1869adf] | 133 | e->add_uses( *oldEntry ); |
---|
[954463b8] | 134 | labelTable[ *i ] = e; |
---|
[46cbfe1] | 135 | } // if |
---|
| 136 | } // for |
---|
[a08ba92] | 137 | |
---|
[46cbfe1] | 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(); |
---|
[a08ba92] | 141 | } |
---|
| 142 | |
---|
[46cbfe1] | 143 | // Remember all uses of a label. |
---|
[1869adf] | 144 | template< typename UsageNode > |
---|
| 145 | void LabelFixer::setLabelsUsg( Label orgValue, UsageNode *use ) { |
---|
[a08ba92] | 146 | assert( use != 0 ); |
---|
| 147 | |
---|
[46cbfe1] | 148 | if ( labelTable.find( orgValue ) != labelTable.end() ) { |
---|
| 149 | // the label has been defined or used before |
---|
| 150 | labelTable[ orgValue ]->add_use( use ); |
---|
| 151 | } else { |
---|
[a08ba92] | 152 | labelTable[ orgValue ] = new Entry( 0, use ); |
---|
[46cbfe1] | 153 | } |
---|
[a08ba92] | 154 | } |
---|
| 155 | |
---|
[1869adf] | 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 | |
---|
[46cbfe1] | 198 | // Ultimately builds a table that maps a label to its defining statement. |
---|
| 199 | // In the process, |
---|
[a08ba92] | 200 | std::map<Label, Statement * > *LabelFixer::resolveJumps() throw ( SemanticError ) { |
---|
| 201 | std::map< Statement *, Entry * > def_us; |
---|
| 202 | |
---|
[46cbfe1] | 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 ) { |
---|
[a08ba92] | 205 | Entry *e = i->second; |
---|
| 206 | |
---|
[be5aa1b] | 207 | if ( def_us.find ( e->get_definition() ) == def_us.end() ) { |
---|
[1869adf] | 208 | def_us[ e->get_definition() ] = e; |
---|
[46cbfe1] | 209 | } else if ( e->used() ) { |
---|
[1869adf] | 210 | def_us[ e->get_definition() ]->add_uses( *e ); |
---|
[be5aa1b] | 211 | } |
---|
[a08ba92] | 212 | } |
---|
| 213 | |
---|
[46cbfe1] | 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 ) { |
---|
[a08ba92] | 216 | Statement *to = (*i).first; |
---|
[46cbfe1] | 217 | Entry * entry = (*i).second; |
---|
[1869adf] | 218 | std::list< Entry::UsageLoc > &from = entry->get_uses(); |
---|
[a08ba92] | 219 | |
---|
[46cbfe1] | 220 | // no label definition found |
---|
[a08ba92] | 221 | if ( to == 0 ) { |
---|
[1869adf] | 222 | Label undef; |
---|
| 223 | LabelGetter getLabel( undef ); |
---|
| 224 | from.back().accept( getLabel ); |
---|
| 225 | // Label undef = getLabel( from.back()->get_target() ); |
---|
[a08ba92] | 226 | throw SemanticError ( "'" + undef + "' label not defined"); |
---|
[de62360d] | 227 | } // if |
---|
[a08ba92] | 228 | |
---|
[de62360d] | 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() ); |
---|
[46cbfe1] | 231 | entry->set_label( finalLabel ); |
---|
| 232 | |
---|
[a08ba92] | 233 | to->get_labels().clear(); |
---|
| 234 | to->get_labels().push_back( finalLabel ); |
---|
| 235 | |
---|
[46cbfe1] | 236 | // redirect each of the source branch statements to the new target label |
---|
[1869adf] | 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 ); |
---|
[a08ba92] | 245 | } // for |
---|
| 246 | } // for |
---|
| 247 | |
---|
[46cbfe1] | 248 | // create a table where each label maps to its defining statement |
---|
[a08ba92] | 249 | std::map< Label, Statement * > *ret = new std::map< Label, Statement * >(); |
---|
[46cbfe1] | 250 | for ( std::map< Statement *, Entry * >::iterator i = def_us.begin(); i != def_us.end(); ++i ) { |
---|
[a08ba92] | 251 | (*ret)[ (*i).second->get_label() ] = (*i).first; |
---|
[46cbfe1] | 252 | } |
---|
[a08ba92] | 253 | |
---|
| 254 | return ret; |
---|
| 255 | } |
---|
[51b7345] | 256 | } // namespace ControlStruct |
---|
[a08ba92] | 257 | |
---|
[51587aa] | 258 | // Local Variables: // |
---|
| 259 | // tab-width: 4 // |
---|
| 260 | // mode: c++ // |
---|
| 261 | // compile-command: "make install" // |
---|
| 262 | // End: // |
---|