00001: package clogs.transform; 00002: 00003: import clogs.ast.*; 00004: import clogs.util.List; 00005: import clogs.util.Optional; 00006: 00007: 00008: public class IntroduceThreeAddressCode extends Phase 00009: { 00010: public List<ExtDecl> transform (List<ExtDecl> edecls) 00011: { 00012: List<ExtDecl> result = List.nil (); 00013: 00014: for (ExtDecl edecl : edecls) { 00015: if (edecl instanceof Decl) { 00016: Decl decl = (Decl) edecl; 00017: assert (decl.eo.isEmpty ()); 00018: result = result.snoc (decl); 00019: 00020: } else if (edecl instanceof FunDef) { 00021: FunDef fundef = (FunDef) edecl; 00022: result = result.snoc (new FunDef (fundef.type, fundef.name, fundef.params, transformBody (fundef.body))); 00023: 00024: } else { 00025: throw new RuntimeException ("Missing ExtDecl case: " + edecl.getClass ().getName ()); 00026: } 00027: } 00028: 00029: return result; 00030: } 00031: 00032: static class DeclsStats 00033: { 00034: final List<Decl> decls; 00035: final List<Stat> stats; 00036: 00037: DeclsStats (List<Decl> decls, List<Stat> stats) 00038: { 00039: this.decls = decls; 00040: this.stats = stats; 00041: } 00042: } 00043: 00044: 00045: static class DeclsStatsVariable 00046: { 00047: final List<Decl> decls; 00048: final List<Stat> stats; 00049: final Optional<Exp> oe; // A call to a function with void return type does not produce a result. 00050: 00051: DeclsStatsVariable (List<Decl> decls, List<Stat> stats, Optional<Exp> oe) 00052: { 00053: assert ((oe.isEmpty ()) || (oe.get () instanceof ExpInt) || (oe.get () instanceof ExpVar)); 00054: this.decls = decls; 00055: this.stats = stats; 00056: this.oe = oe; 00057: } 00058: } 00059: 00060: 00061: // Write compound statements as 00062: // { decls stats } 00063: // 00064: // Write instances of DeclsStats as 00065: // < decls | stats > 00066: // 00067: // Write instances of DeclsStatsVariable as 00068: // < decls | stats | Optional<v> > 00069: // If the exp must be present, then: 00070: // < decls | stats | v > 00071: // 00072: // The relevant functions are: 00073: // transformBody (({ decls stats })) = { decls' stats' } 00074: // transformStat (stat) = < decls | stats > 00075: // transformExp (exp) = < decls | stats | Optional<v> > 00076: // 00077: 00078: 00079: static StatCompound transformBody (StatCompound statC) { 00080: // transformStat (stat_0) = < decls_0 | stats_0 > 00081: // ... 00082: // transformStat (stat_n) = < decls_n | stats_n > 00083: // ----------------------------------------------------- 00084: // transformBody (({decls stat_0 ... stat_n})) 00085: // = { decls decls_0 ... decls_n stats_0 ... stats_m } 00086: // 00087: List<Decl> declsNew = List.nil (); 00088: List<Stat> statsNew = List.nil (); 00089: for (Stat stat : statC.stats) { 00090: DeclsStats ds = transformStat (stat); 00091: declsNew = declsNew.concat (ds.decls); 00092: statsNew = statsNew.concat (ds.stats); 00093: } 00094: return new StatCompound (statC.decls.concat (declsNew), statsNew); 00095: } 00096: 00097: 00098: static DeclsStats transformStat (Stat stat) { 00099: List<Decl> declsNew = List.nil (); 00100: List<Stat> statsNew = List.nil (); 00101: 00102: if (stat instanceof StatCompound) { 00103: // transformBody (statC) = statC' 00104: // ----------------------------------------------------- 00105: // transformStat (statC) = < nil | statC' > 00106: // 00107: StatCompound statC = (StatCompound) stat; 00108: for (Stat s : statC.stats) { 00109: DeclsStats ds = transformStat (s); 00110: declsNew = declsNew.concat (ds.decls); 00111: statsNew = statsNew.concat (ds.stats); 00112: } 00113: statsNew = List.singleton ((Stat)new StatCompound (statC.decls, statsNew)); 00114: statsNew = addLabelsToHead (statsNew, statC.labels); 00115: 00116: } else if (stat instanceof StatExp) { 00117: // transformExp (exp) = < decls | stats | ... > 00118: // ----------------------------------------------------- 00119: // transformStat ((exp;)) = < decls | stats > 00120: // 00121: StatExp statE = (StatExp) stat; 00122: DeclsStatsVariable sav = transformExp (statE.exp); 00123: declsNew = declsNew.concat (sav.decls); 00124: statsNew = statsNew.concat (sav.stats); 00125: if (!statE.labels.isNil()) { 00126: if (statsNew.isNil()) { 00127: statsNew = statsNew.snoc (new StatSkip()); 00128: } 00129: statsNew = addLabelsToHead (statsNew, statE.labels); 00130: } 00131: 00132: } else if (stat instanceof StatGoto) { 00133: // transformStat ((goto exp;)) = < nil | (goto exp;) > 00134: // 00135: statsNew = statsNew.snoc (stat); 00136: 00137: } else if (stat instanceof StatIf) { 00138: // transformExp (exp) = < decls | stats | v > 00139: // ----------------------------------------------------- 00140: // transformStat ((if (exp) goto l1; else goto l2;)) 00141: // = < decls | stats (if (v) goto l1; else goto l2;) > 00142: // 00143: StatIf statI = (StatIf) stat; 00144: assert (statI.statT instanceof StatGoto); 00145: assert (statI.statF instanceof StatGoto); 00146: DeclsStatsVariable sav = transformExp (statI.exp); 00147: declsNew = declsNew.concat (sav.decls); 00148: statsNew = statsNew.concat (sav.stats); 00149: statsNew = statsNew.snoc (new StatIf (sav.oe.get (), statI.statT, statI.statF)); 00150: statsNew = addLabelsToHead (statsNew, statI.labels); 00151: 00152: } else if (stat instanceof StatReturn) { 00153: // ----------------------------------------------------- 00154: // transformStat ((return;)) = < nil | (return;) > 00155: // 00156: // transformExp (exp) = < decls | stats | v > 00157: // ----------------------------------------------------------------- 00158: // transformStat ((return exp;)) = < decls | stats (return v;) > 00159: // 00160: StatReturn statR = (StatReturn) stat; 00161: if (statR.oe.isEmpty ()) { 00162: statsNew = statsNew.snoc (stat); 00163: } else { 00164: DeclsStatsVariable sav = transformExp (statR.oe.get ()); 00165: declsNew = declsNew.concat (sav.decls); 00166: statsNew = statsNew.concat (sav.stats); 00167: statsNew = statsNew.snoc (new StatReturn (new Optional<Exp> (sav.oe.get ()))); 00168: statsNew = addLabelsToHead (statsNew, statR.labels); 00169: } 00170: 00171: } else if (stat instanceof StatSkip) { 00172: // transformStat ((skip;)) = < nil | (skip;) > 00173: // 00174: statsNew = statsNew.snoc (stat); 00175: 00176: } else if (stat instanceof StatWhile) { 00177: assert (false); 00178: 00179: } else { 00180: throw new RuntimeException ("Missing Stat case: " + stat.getClass ().getName ()); 00181: } 00182: 00183: return new DeclsStats (declsNew, statsNew); 00184: } 00185: 00186: 00187: static List<Stat> addLabelsToHead (List<Stat> stats, List<String> labels) 00188: { 00189: Stat headNew = stats.head ().addLabels (labels); 00190: return stats.tail ().cons (headNew); 00191: } 00192: 00193: 00194: static DeclsStatsVariable transformExp (Exp exp) 00195: { 00196: if (exp instanceof ExpArrayAccess) { 00197: // transformExp (array) = < decls1 | stats1 | v1 > 00198: // transformExp (index) = < decls2 | stats2 | v2 > 00199: // ------------------------------------------------------------------------------ 00200: // transformExp ((array[index]) :: resultType) 00201: // = < decls1 decls2 (resultType x;) | stats1 stats2 (x = (v1[v2]);) | x > 00202: // 00203: ExpArrayAccess expA = (ExpArrayAccess) exp; 00204: DeclsStatsVariable sav1 = transformExp (expA.array); 00205: DeclsStatsVariable sav2 = transformExp (expA.index); 00206: List<Decl> declsNew = sav1.decls.concat (sav2.decls); 00207: List<Stat> statsNew = sav1.stats.concat (sav2.stats); 00208: String labelNew = Fresh.getVar () + "_array"; 00209: Exp expNew = new ExpVar (labelNew); 00210: declsNew = declsNew.snoc (new Decl (expA.to.get (), labelNew, new Optional<Exp> ())); 00211: statsNew = statsNew.snoc (new StatExp (new ExpAssign (expNew, new ExpArrayAccess (sav1.oe.get (), sav2.oe.get ())))); 00212: return new DeclsStatsVariable (declsNew, statsNew, new Optional<Exp> (expNew)); 00213: 00214: } else if (exp instanceof ExpAssign) { 00215: // transformExp (right) = < decls3 | stats3 | v3 > 00216: // ----------------------------------------------------- 00217: // transformExp ((x = right)) 00218: // = < decls3 | stats3 (x = v3;) | v3 > 00219: // 00220: // transformExp (array) = < decls1 | stats1 | v1 > 00221: // transformExp (index) = < decls2 | stats2 | v2 > 00222: // transformExp (right) = < decls3 | stats3 | v3 > 00223: // ------------------------------------------------------------------------------- 00224: // transformExp ((array[index] = right)) 00225: // = < decls1 decls2 decls3 | stats1 stats2 stats3 (v1[v2] = v3;) | v3 > 00226: // 00227: ExpAssign expA = (ExpAssign) exp; 00228: List<Decl> declsNew = List.nil (); 00229: List<Stat> statsNew = List.nil (); 00230: Exp left; 00231: if (expA.left instanceof ExpArrayAccess) { 00232: ExpArrayAccess expAA = (ExpArrayAccess) expA.left; 00233: DeclsStatsVariable sav1 = transformExp (expAA.array); 00234: declsNew = declsNew.concat (sav1.decls); 00235: statsNew = statsNew.concat (sav1.stats); 00236: DeclsStatsVariable sav2 = transformExp (expAA.index); 00237: declsNew = declsNew.concat (sav2.decls); 00238: statsNew = statsNew.concat (sav2.stats); 00239: left = new ExpArrayAccess (sav1.oe.get (), sav2.oe.get ()); 00240: } else if (expA.left instanceof ExpVar) { 00241: left = expA.left; 00242: } else { 00243: assert (false); // Impossible to reach this case in a well-typed program. 00244: left = null; 00245: } 00246: DeclsStatsVariable sav3 = transformExp (expA.right); 00247: declsNew = declsNew.concat (sav3.decls); 00248: statsNew = statsNew.concat (sav3.stats); 00249: statsNew = statsNew.snoc (new StatExp (new ExpAssign (left, sav3.oe.get ()))); 00250: return new DeclsStatsVariable (declsNew, statsNew, sav3.oe); 00251: 00252: } else if (exp instanceof ExpBinOp) { 00253: // transformExp (left) = < decls1 | stats1 | v1 > 00254: // transformExp (right) = < decls2 | stats2 | v2 > 00255: // ---------------------------------------------------------------------------------- 00256: // transformExp ((left op right) :: resultType) 00257: // = < decls1 decls2 (resultType x;) | stats1 stats2 (x = (v1 op v2);) | x > 00258: // 00259: ExpBinOp expB = (ExpBinOp) exp; 00260: DeclsStatsVariable sav1 = transformExp (expB.left); 00261: DeclsStatsVariable sav2 = transformExp (expB.right); 00262: List<Decl> declsNew = sav1.decls.concat (sav2.decls); 00263: List<Stat> statsNew = sav1.stats.concat (sav2.stats); 00264: String labelNew = Fresh.getVar () + "_binop"; 00265: Exp expNew = new ExpVar (labelNew); 00266: declsNew = declsNew.snoc (new Decl (expB.to.get (), labelNew, new Optional<Exp> ())); 00267: statsNew = statsNew.snoc (new StatExp (new ExpAssign (expNew, new ExpBinOp (expB.op, sav1.oe.get (), sav2.oe.get ())))); 00268: return new DeclsStatsVariable (declsNew, statsNew, new Optional<Exp> (expNew)); 00269: 00270: } else if (exp instanceof ExpComma) { 00271: // transformExp (left) = < decls1 | stats1 | Optional<exp1> > 00272: // transformExp (right) = < decls2 | stats2 | Optional<exp2> > 00273: // ----------------------------------------------------------- 00274: // transformExp ((left , right)) 00275: // = < decls1 decls2 | stats1 stats2 | Optional<exp2> > 00276: // 00277: ExpComma expC = (ExpComma) exp; 00278: DeclsStatsVariable sav1 = transformExp (expC.left); 00279: DeclsStatsVariable sav2 = transformExp (expC.right); 00280: List<Decl> declsNew = sav1.decls.concat (sav2.decls); 00281: List<Stat> statsNew = sav1.stats.concat (sav2.stats); 00282: return new DeclsStatsVariable (declsNew, statsNew, sav2.oe); 00283: 00284: } else if (exp instanceof ExpFunCall) { 00285: // transformExp (arg1) = < decls1 | stats1 | v1 > 00286: // ... 00287: // transformExp (argn) = < declsn | statsn | vn > 00288: // ------------------------------------------------------------------------- 00289: // transformExp ((name(arg1,...,argn)) :: void) 00290: // = < decls1 ... declsn | stats1 ... statsn (name(v1,...,vn)) | nil > 00291: // AND 00292: // transformExp ((name(arg1,...,argn)) :: resultType) 00293: // = < decls1 ... declsn (resultType x;) | stats1 ... statsn (x = (name(v1,...,vn))) | x > 00294: // 00295: ExpFunCall expF = (ExpFunCall) exp; 00296: List<Decl> declsNew = List.nil (); 00297: List<Stat> statsNew = List.nil (); 00298: List<Exp> argsNew = List.nil (); 00299: for (Exp exp2 : expF.args) { 00300: DeclsStatsVariable sav1 = transformExp (exp2); 00301: declsNew = declsNew.concat (sav1.decls); 00302: statsNew = statsNew.concat (sav1.stats); 00303: argsNew = argsNew.snoc (sav1.oe.get ()); 00304: } 00305: if (expF.to.get () instanceof TypeVoid) { 00306: statsNew = statsNew.snoc (new StatExp (new ExpFunCall (expF.name, argsNew))); 00307: return new DeclsStatsVariable (declsNew, statsNew, new Optional<Exp> ()); 00308: } else { 00309: String labelNew = Fresh.getVar () + "_funcall"; 00310: Exp expNew = new ExpVar (labelNew); 00311: declsNew = declsNew.snoc (new Decl (expF.to.get (), labelNew, new Optional<Exp> ())); 00312: statsNew = statsNew.snoc (new StatExp (new ExpAssign (expNew, new ExpFunCall (expF.name, argsNew)))); 00313: return new DeclsStatsVariable (declsNew, statsNew, new Optional<Exp> (expNew)); 00314: } 00315: 00316: } else if (exp instanceof ExpInt) { 00317: // ----------------------------------------------------- 00318: // transformExp (n) = < nil | nil | n > 00319: // 00320: return new DeclsStatsVariable (List.<Decl>nil (), List.<Stat>nil (), new Optional<Exp> (exp)); 00321: 00322: } else if (exp instanceof ExpNew) { 00323: // transformExp (size) = < decls | stats | v > 00324: // ----------------------------------------------------- 00325: // transformExp ((new contentType[size];)) 00326: // = < decls (contentType[] x;) | stats (x = (new contentType[v]);) | x > 00327: // 00328: ExpNew expN = (ExpNew) exp; 00329: DeclsStatsVariable sav = transformExp (expN.size); 00330: List<Decl> declsNew = sav.decls; 00331: List<Stat> statsNew = sav.stats; 00332: String labelNew = Fresh.getVar () + "_new"; 00333: Exp expNew = new ExpVar (labelNew); 00334: declsNew = declsNew.snoc (new Decl (new TypeArray (expN.contentType), labelNew, new Optional<Exp> ())); 00335: statsNew = statsNew.snoc (new StatExp (new ExpAssign (expNew, new ExpNew (expN.contentType, sav.oe.get ())))); 00336: return new DeclsStatsVariable (declsNew, statsNew, new Optional<Exp> (expNew)); 00337: 00338: } else if (exp instanceof ExpString) { 00339: // ----------------------------------------------------- 00340: // transformExp (("value")) 00341: // = < (int[] x;) | (x = ("value");) | x > 00342: // 00343: ExpString expS = (ExpString) exp; 00344: String labelNew = Fresh.getVar () + "_string_literal"; 00345: Exp expNew = new ExpVar (labelNew); 00346: List<Decl> declsNew = List.nil (); 00347: List<Stat> statsNew = List.nil (); 00348: declsNew = declsNew.snoc (new Decl (new TypeArray (new TypeInt ()), labelNew, new Optional<Exp> ())); 00349: statsNew = statsNew.snoc (new StatExp (new ExpAssign (expNew, new ExpString (expS.value)))); 00350: return new DeclsStatsVariable (declsNew, statsNew, new Optional<Exp> (expNew)); 00351: 00352: } else if (exp instanceof ExpUnOp) { 00353: // transformExp (exp) = < decls | stats | v > 00354: // ------------------------------------------------------------ 00355: // transformExp ((unop exp) :: resultType) 00356: // = < decls (resultType x;) | stats (x = (unop v);) | x > 00357: // 00358: ExpUnOp expU = (ExpUnOp) exp; 00359: DeclsStatsVariable sav = transformExp (expU.exp); 00360: List<Decl> declsNew = sav.decls; 00361: List<Stat> statsNew = sav.stats; 00362: String labelNew = Fresh.getVar () + "_unop"; 00363: Exp expNew = new ExpVar (labelNew); 00364: declsNew = declsNew.snoc (new Decl (expU.to.get (), labelNew, new Optional<Exp> ())); 00365: statsNew = statsNew.snoc (new StatExp (new ExpAssign (expNew, new ExpUnOp (expU.op, sav.oe.get ())))); 00366: return new DeclsStatsVariable (declsNew, statsNew, new Optional<Exp> (expNew)); 00367: 00368: } else if (exp instanceof ExpVar) { 00369: // ----------------------------------------------------- 00370: // transformExp (x) = < nil | nil | x > 00371: // 00372: return new DeclsStatsVariable (List.<Decl>nil (), List.<Stat>nil (), new Optional<Exp> (exp)); 00373: 00374: } else { 00375: throw new RuntimeException ("Missing Exp case: " + exp.getClass ().getName ()); 00376: } 00377: } 00378: } 00379: