 |
C-Breeze C Compiler Infrastructure [ Project home page] |
localcopyprop.cc
Go to the documentation of this file.00001 // $Id: localcopyprop.cc,v 1.7 2003/08/07 23:14:17 pnav Exp $ 00002 // ---------------------------------------------------------------------- 00003 // 00004 // C-Breeze 00005 // C Compiler Framework 00006 // 00007 // Copyright (c) 2000 University of Texas at Austin 00008 // 00009 // Samuel Z. Guyer 00010 // Daniel A. Jimenez 00011 // Calvin Lin 00012 // 00013 // Permission is hereby granted, free of charge, to any person 00014 // obtaining a copy of this software and associated documentation 00015 // files (the "Software"), to deal in the Software without 00016 // restriction, including without limitation the rights to use, copy, 00017 // modify, merge, publish, distribute, sublicense, and/or sell copies 00018 // of the Software, and to permit persons to whom the Software is 00019 // furnished to do so, subject to the following conditions: 00020 // 00021 // The above copyright notice and this permission notice shall be 00022 // included in all copies or substantial portions of the Software. 00023 // 00024 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00025 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00026 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00027 // NONINFRINGEMENT. IN NO EVENT SHALL THE UNIVERSITY OF TEXAS AT 00028 // AUSTIN BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER 00029 // IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 00030 // OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 00031 // THE SOFTWARE. 00032 // 00033 // We acknowledge the C-to-C Translator from MIT Laboratory for 00034 // Computer Science for inspiring parts of the C-Breeze design. 00035 // 00036 // ---------------------------------------------------------------------- 00037 #include <stdio.h> 00038 #include <map> 00039 #include <string> 00040 #include "c_breeze.h" 00041 #include "ref_clone_changer.h" 00042 #include "localcopyprop.h" 00043 00044 Node * LocalCopyPropChanger::at_proc (procNode *p, Order) { 00045 int count = 0; 00046 for (stmt_list_p i = p->body()->stmts().begin(); i!=p->body()->stmts().end(); i++) { 00047 do { 00048 change = false; 00049 local_copy_prop ((basicblockNode *) *i); 00050 count++; 00051 } while (change && (count < 10)); 00052 } 00053 return p; 00054 } 00055 00056 void LocalCopyPropChanger::local_copy_prop (basicblockNode *p) { 00057 // copies maps targets to sources of copies. 00058 // initially, we clear it since we don't locally know 00059 // of any copies 00060 00061 copies.clear(); 00062 00063 // go through all the stmts in this basic block 00064 00065 for (stmt_list_p i=p->stmts().begin(); i!=p->stmts().end(); i++) { 00066 stmtNode *s = (stmtNode *) *i; 00067 00068 // if the stmt is an expression stmt, see if it 00069 // kills the copies map by assigning through 00070 // a pointer 00071 00072 if (s->typ() == Expr) { 00073 exprNode *e = (exprNode *) ((exprstmtNode *)s)->expr(); 00074 if (e->typ() == Binary) { 00075 binaryNode *b = (binaryNode *) e; 00076 if (b->op()->id() == '=') { 00077 exprNode *lhs = b->left(); 00078 if (lhs->typ() == Unary) { 00079 unaryNode *u = (unaryNode *) lhs; 00080 if (u->op()->id() == Operator::INDIR) { 00081 00082 // here we have *p = something; 00083 // this might kill some copy, so 00084 // we conservatively kill all copies 00085 00086 copies.clear(); 00087 continue; 00088 } 00089 } else if (lhs->typ() == Binary) { 00090 binaryNode *u = (binaryNode *) lhs; 00091 if (b->op()->id() == Operator::ARROW) { 00092 00093 // here we have p->id = something; 00094 // same idea as above 00095 00096 copies.clear(); 00097 continue; 00098 } 00099 if (b->op()->id() == Operator::Index) 00100 copies.clear(); 00101 } 00102 } 00103 } 00104 } 00105 00106 // propagate copies through this stmt 00107 00108 had_proc_call = false; 00109 prop (s); 00110 00111 // if the statement included a procedure call, 00112 // we kill all copies, since they could have 00113 // been wiped out. note that copies are propagated 00114 // in the arg list of the call, and that's OK 00115 // since the call hasn't been done yet. since 00116 // we have dismantled code, nothing in this 00117 // stmt can be affected by copies after the call 00118 // since the only thing that can happen is 00119 // an assignment to the return value 00120 00121 if (had_proc_call) copies.clear(); 00122 00123 // if this is a copy, record it in the map; 00124 // also, kill some copies because of new defs 00125 00126 if (s->typ() == Expr) { 00127 exprstmtNode *ex = (exprstmtNode *) s; 00128 exprNode *e = ex->expr(); 00129 if (e->typ() == Binary) { 00130 binaryNode *bn = (binaryNode *) e; 00131 if (bn->op()->id() == '=') { 00132 if (bn->left()->typ() == Id) { 00133 00134 // this is a def of this lhs, killing 00135 // any previous copies of it 00136 00137 string a = ((idNode *) bn->left())->name(); 00138 copies[a] = NULL; 00139 00140 // since lhs may have changed, anything that 00141 // maps to it is killed. this is a kludge. 00142 00143 list<string> l; 00144 for (map<string,idNode*>::iterator i=copies.begin(); 00145 i!=copies.end(); i++) { 00146 if ((*i).second) if ((*i).second->name() == a) 00147 l.push_back ((*i).first); 00148 } 00149 for (list<string>::iterator j=l.begin(); j!=l.end(); j++) { 00150 copies[*j] = NULL; 00151 } 00152 00153 // this stmt is a copy 00154 00155 if (bn->right()->typ() == Id) { 00156 idNode *b = (idNode *) bn->right(); 00157 idNode *c = b; 00158 // get the "earliest" copy of b 00159 do { 00160 b = c; 00161 c = copies[b->name()]; 00162 if (b == c) break; 00163 } while (c); 00164 copies[a] = b; 00165 } 00166 } 00167 } 00168 } 00169 } 00170 } 00171 } 00172 00173 // propagate copy information through a stmt 00174 00175 void LocalCopyPropChanger::prop (stmtNode *s) { 00176 if (s->typ() == If) { 00177 ifNode *i = (ifNode *) s; 00178 i->expr (prop_expr (i->expr())); 00179 } else if (s->typ() == Return) { 00180 returnNode *r = (returnNode *) s; 00181 r->expr (prop_expr (r->expr())); 00182 } else if (s->typ() == Expr) { 00183 exprstmtNode *e = (exprstmtNode *) s; 00184 e->expr (prop_expr (e->expr())); 00185 } 00186 } 00187 00188 // propagate copy information through an expression, 00189 // returning the resulting expression 00190 00191 exprNode *LocalCopyPropChanger::prop_expr (exprNode *e) { 00192 if (!e) return NULL; 00193 switch (e->typ()) { 00194 case Call: { 00195 callNode *c = (callNode *) e; 00196 for (expr_list_p i=c->args().begin(); i!=c->args().end(); i++) 00197 *i = prop_expr (*i); 00198 had_proc_call = true; 00199 break; 00200 } 00201 case Binary: { 00202 binaryNode *b = (binaryNode *) e; 00203 // if the lhs is being assigned into, 00204 // we'd better not try to copyprop it 00205 if (b->op()->id() != '=') 00206 b->left (prop_expr (b->left())); 00207 // the rhs is a tag, not a var 00208 if (b->op()->id() != Operator::ARROW) 00209 b->right (prop_expr (b->right())); 00210 break; 00211 } 00212 case Unary: { 00213 unaryNode *u = (unaryNode *) e; 00214 switch (u->op()->id()) { 00215 case Operator::SIZEOF: 00216 case Operator::ADDRESS: return e; 00217 default: ; 00218 } 00219 u->expr (prop_expr (u->expr())); 00220 break; 00221 } 00222 case Cast: { 00223 castNode *c = (castNode *) e; 00224 c->expr (prop_expr (c->expr())); 00225 break; 00226 } 00227 case Const: 00228 break; 00229 case Id: { 00230 idNode *i = (idNode *) e; 00231 idNode *j = copies[i->name()]; 00232 if (j) { 00233 change = true; 00234 return (idNode *) ref_clone_changer::clone(j, false); 00235 } 00236 break; 00237 } 00238 default: ; 00239 } 00240 return e; 00241 }