1 cananian 1.1.2.1 // BasicCSE.java, created Sat Sep 26 04:27:12 1998 by marinov
2 cananian 1.1.2.1 // Copyright (C) 1998 Darko Marinov <marinov@lcs.mit.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.2 import harpoon.IR.Quads.CONST;
7 cananian 1.1.2.2 import harpoon.IR.Quads.Edge;
8 cananian 1.1.2.2 import harpoon.IR.Quads.MOVE;
9 cananian 1.1.2.2 import harpoon.IR.Quads.OPER;
10 cananian 1.1.2.2 import harpoon.IR.Quads.Qop;
11 cananian 1.1.2.2 import harpoon.IR.Quads.Quad;
12 cananian 1.1.2.2 import harpoon.ClassFile.HClass;
13 cananian 1.1.2.2 import harpoon.ClassFile.HCode;
14 cananian 1.1.2.2 import harpoon.Temp.Temp;
15 cananian 1.3 import net.cscott.jutil.UniqueVector;
16 cananian 1.1.2.1 import java.util.Vector;
17 cananian 1.1.2.1 import java.util.Hashtable;
18 cananian 1.1.2.1
19 cananian 1.1.2.1 /**
20 cananian 1.1.2.1 * <code>BasicCSE</code> is an attempt to perform
21 cananian 1.1.2.1 * common subexpression elemination, but only within basic blocks.
22 cananian 1.1.2.1 *
23 cananian 1.1.2.1 * @author Darko Marinov <marinov@lcs.mit.edu>
24 cananian 1.3 * @version $Id: BasicCSE.java,v 1.3 2004/02/08 01:53:14 cananian Exp $
25 cananian 1.1.2.1 */
26 cananian 1.1.2.1
27 cananian 1.1.2.1 public class BasicCSE {
28 cananian 1.1.2.1
29 cananian 1.1.2.1 private BasicCSE() { }
30 cananian 1.1.2.1
31 cananian 1.1.2.1 /** <code>BasicBlock</code> represents sequence of quadruples. */
32 cananian 1.1.2.1 private static class BasicBlock {
33 cananian 1.1.2.1 private Quad start,end;
34 cananian 1.1.2.1 public Quad getStart() {return start;}
35 cananian 1.1.2.1 public Quad getEnd() {return end;}
36 cananian 1.1.2.1 public BasicBlock(Quad start, Quad end) {
37 cananian 1.1.2.1 this.start=start; this.end=end;
38 cananian 1.1.2.1 }
39 cananian 1.1.2.1 /** Returns quadruples of the basic block in execution order. */
40 cananian 1.1.2.1 public Quad[] executionOrder() {
41 cananian 1.1.2.1 Vector c = new Vector();
42 cananian 1.1.2.1 for (Quad q=start; ;q=q.next(0)) {
43 cananian 1.1.2.1 c.addElement(q);
44 cananian 1.1.2.1 if (q==end) break;
45 cananian 1.1.2.1 }
46 cananian 1.1.2.1 Quad[] r=new Quad[c.size()];
47 cananian 1.1.2.1 c.copyInto(r); return r;
48 cananian 1.1.2.1 }
49 cananian 1.1.2.1 }
50 cananian 1.1.2.1
51 cananian 1.1.2.1 /** Returns array of basic blocks in code starting with quad start. */
52 cananian 1.1.2.1 private static BasicBlock[] findBasicBlocks (Quad start) {
53 cananian 1.1.2.1 Vector c = new Vector();
54 cananian 1.1.2.1 UniqueVector b = new UniqueVector(1);
55 cananian 1.1.2.1 b.addElement(start);
56 cananian 1.1.2.1 for (int i=0; i<b.size(); i++) {
57 cananian 1.1.2.1 Quad s=(Quad)b.elementAt(i);
58 cananian 1.1.2.1 Quad t=s;
59 cananian 1.1.2.1 while ((t.nextEdge().length==1)&&(t.next(0).prevEdge().length==1))
60 cananian 1.1.2.1 t=t.next(0);
61 cananian 1.1.2.1 c.addElement(new BasicBlock(s,t));
62 cananian 1.1.2.1 Quad[] n=t.next();
63 cananian 1.1.2.1 for (int j=0; j<n.length; j++)
64 cananian 1.1.2.1 b.addElement(n[j]);
65 cananian 1.1.2.1 }
66 cananian 1.1.2.1 BasicBlock[] r=new BasicBlock[c.size()];
67 cananian 1.1.2.1 c.copyInto(r); return r;
68 cananian 1.1.2.1 }
69 cananian 1.1.2.1
70 cananian 1.1.2.1 /** Eliminates common subexpression within basic blocks
71 cananian 1.1.2.1 * in quad-ssi <code>HCode</code>. Uses value numbering algorithm. */
72 cananian 1.1.2.1 public static void optimize (HCode hc) {
73 cananian 1.1.2.1 BasicBlock[] bbs=findBasicBlocks((Quad)hc.getRootElement());
74 cananian 1.1.2.1 // for all basic blocks
75 cananian 1.1.2.1 for (int i=0; i<bbs.length; i++) {
76 cananian 1.1.2.1 Hashtable var2val = new Hashtable(); // variable to value map
77 cananian 1.1.2.1 Hashtable exp2val = new Hashtable(); // expression to value
78 cananian 1.1.2.1 Hashtable exp2var = new Hashtable(); // expression to variable
79 cananian 1.1.2.1 Hashtable con2val = new Hashtable(); // constant to value
80 cananian 1.1.2.1 int virtval = 0;
81 cananian 1.1.2.1 Quad[] in = bbs[i].executionOrder();
82 cananian 1.1.2.1 // for all instructions
83 cananian 1.1.2.1 for (int j=0; j<in.length; j++) {
84 cananian 1.1.2.1 // if instruction is (n-ary) operation dst=op(src1...srcn)
85 cananian 1.1.2.1 if (in[j] instanceof OPER) {
86 cananian 1.1.2.1 OPER ins=(OPER) in[j];
87 cananian 1.1.2.1 Vector exp = new Vector(1);
88 cananian 1.1.2.1 exp.addElement(Qop.toString(ins.opcode()));
89 cananian 1.1.2.1 // for all src
90 cananian 1.1.2.1 for (int k=0; k<ins.operandsLength(); k++) {
91 cananian 1.1.2.1 Integer v=(Integer)var2val.get(ins.operands(k));
92 cananian 1.1.2.1 // if var2val(src)==no value than var2val=new value
93 cananian 1.1.2.1 if (v==null) {
94 cananian 1.1.2.1 virtval++; Integer vv=new Integer(virtval);
95 cananian 1.1.2.1 var2val.put(ins.operands(k),vv);
96 cananian 1.1.2.1 exp.addElement(vv);
97 cananian 1.1.2.1 } else exp.addElement(v);
98 cananian 1.1.2.1 }
99 cananian 1.1.2.1 String str=exp.toString();
100 cananian 1.1.2.1 Integer v=(Integer) exp2val.get(str);
101 cananian 1.1.2.1 // if exp2val(op(var2val(src1)...var2val(srcn)))==no value
102 cananian 1.1.2.1 if (v==null) {
103 cananian 1.1.2.1 Temp t = new Temp(ins.dst());
104 cananian 1.1.2.1 // insert MOVE t,dst quad
105 cananian 1.1.2.1 Quad[] q=ins.next();
106 cananian 1.1.2.1 if ((q.length==1)&&(q[0].prev().length==1)) {
107 cananian 1.1.2.1 MOVE m=new MOVE(ins.getFactory(),ins,t,ins.dst());
108 cananian 1.1.2.1 Quad.addEdge(m,0,q[0],0);
109 cananian 1.1.2.1 Quad.addEdge(ins,0,m,0);
110 cananian 1.1.2.1 exp2var.put(str,t);
111 cananian 1.1.2.1 }
112 cananian 1.1.2.1 virtval++; Integer vv=new Integer(virtval);
113 cananian 1.1.2.1 exp2val.put(str,vv);
114 cananian 1.1.2.1 var2val.put(ins.dst(),vv);
115 cananian 1.1.2.1 } else {
116 cananian 1.1.2.1 Temp t=(Temp) exp2var.get(str);
117 cananian 1.1.2.1 // change OPER quad to a MOVE one
118 cananian 1.1.2.1 if (ins.edges().length==2) {
119 cananian 1.1.2.1 MOVE m=new MOVE(ins.getFactory(),ins,ins.dst(),t);
120 cananian 1.1.2.1 Quad next=ins.next(0); Quad prev=ins.prev(0);
121 cananian 1.1.2.1 if ((prev.next(0)==ins)&&(next.prev(0)==ins)) {
122 cananian 1.1.2.1 Quad.addEdge(m,0,next,0);
123 cananian 1.1.2.1 Quad.addEdge(prev,0,m,0);
124 cananian 1.1.2.1 }
125 cananian 1.1.2.1 }
126 cananian 1.1.2.1 var2val.put(ins.dst(),v);
127 cananian 1.1.2.1 }
128 cananian 1.1.2.1 // if instruction is move, just set var2val for src and dst
129 cananian 1.1.2.1 } else if (in[j] instanceof MOVE) {
130 cananian 1.1.2.1 MOVE ins = (MOVE) in[j];
131 cananian 1.1.2.1 Integer v=(Integer) var2val.get(ins.src());
132 cananian 1.1.2.1 if (v==null) {
133 cananian 1.1.2.1 virtval++; Integer vv=new Integer(virtval);
134 cananian 1.1.2.1 var2val.put(ins.src(),vv);
135 cananian 1.1.2.1 var2val.put(ins.dst(),vv);
136 cananian 1.1.2.1 }
137 cananian 1.1.2.1 else var2val.put(ins.dst(),v);
138 cananian 1.1.2.1 // if instruction is const, set var2val for dst, but also con2val for src
139 cananian 1.1.2.1 } else if (in[j] instanceof CONST) {
140 cananian 1.1.2.1 CONST ins = (CONST) in[j];
141 cananian 1.1.2.1 String str=ins.type().toString() +
142 cananian 1.1.2.1 ((ins.value()==null)?"null":ins.value().toString());
143 cananian 1.1.2.1 Integer v=(Integer) con2val.get(str);
144 cananian 1.1.2.1 if (v==null) {
145 cananian 1.1.2.1 virtval++; Integer vv=new Integer(virtval);
146 cananian 1.1.2.1 con2val.put(str,vv);
147 cananian 1.1.2.1 var2val.put(ins.dst(),vv);
148 cananian 1.1.2.1 }
149 cananian 1.1.2.1 else var2val.put(ins.dst(),v);
150 cananian 1.1.2.1 }
151 cananian 1.1.2.1 } //for all instructions
152 cananian 1.1.2.1 } //foreach basic block
153 cananian 1.1.2.1 } //optimize
154 cananian 1.1.2.1
155 cananian 1.2 }