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:
|
