1
2
3
4 package joeq.Compiler.Quad.SSA;
5
6 import java.util.Collection;
7 import java.util.HashMap;
8 import java.util.HashSet;
9 import java.util.Iterator;
10 import java.util.Map;
11 import java.util.Set;
12 import java.util.Stack;
13 import joeq.Class.jq_Primitive;
14 import joeq.Class.jq_Type;
15 import joeq.Class.jq_Reference.jq_NullType;
16 import joeq.Compiler.Dataflow.LivenessAnalysis;
17 import joeq.Compiler.Quad.BasicBlock;
18 import joeq.Compiler.Quad.ControlFlowGraph;
19 import joeq.Compiler.Quad.ControlFlowGraphVisitor;
20 import joeq.Compiler.Quad.Dominators;
21 import joeq.Compiler.Quad.ExceptionHandler;
22 import joeq.Compiler.Quad.ExceptionHandlerList;
23 import joeq.Compiler.Quad.Operand;
24 import joeq.Compiler.Quad.Quad;
25 import joeq.Compiler.Quad.QuadIterator;
26 import joeq.Compiler.Quad.BytecodeToQuad.jq_ReturnAddressType;
27 import joeq.Compiler.Quad.Dominators.DominatorNode;
28 import joeq.Compiler.Quad.Operand.RegisterOperand;
29 import joeq.Compiler.Quad.Operator.Move;
30 import joeq.Compiler.Quad.Operator.Phi;
31 import joeq.Compiler.Quad.Operator.Special;
32 import joeq.Compiler.Quad.RegisterFactory.Register;
33 import joeq.Runtime.TypeCheck;
34 import jwutil.collections.GenericMultiMap;
35 import jwutil.collections.MultiMap;
36 import jwutil.collections.Pair;
37 import jwutil.math.BitString;
38 import jwutil.math.BitString.BitStringIterator;
39 import jwutil.util.Assert;
40
41 /***
42 * Transform IR into SSA form.
43 * Adapted from some code I found somewhere on the net...
44 *
45 * @author jwhaley
46 * @version $Id: EnterSSA.java 2465 2006-06-07 23:03:17Z joewhaley $
47 */
48 public class EnterSSA implements ControlFlowGraphVisitor {
49
50 static boolean DEBUG = false;
51 static boolean PRINT_SSA = false;
52 private ControlFlowGraph ir;
53 private LivenessAnalysis live;
54 /***
55 * The set of scalar phi functions inserted
56 */
57 private Set scalarPhis = new HashSet();
58 /***
59 * For each basic block, the number of predecessors that have been
60 * processed.
61 */
62 private int[] numPredProcessed;
63
64 BasicBlock[] basic_blocks;
65 Dominators dominators;
66
67 public void visitCFG(ControlFlowGraph ir) {
68 this.ir = ir;
69 this.basic_blocks = new BasicBlock[ir.getNumberOfBasicBlocks()];
70 for (Iterator i = ir.reversePostOrderIterator(); i.hasNext(); ) {
71 BasicBlock bb = (BasicBlock) i.next();
72 this.basic_blocks[bb.getID()] = bb;
73 }
74 this.dominators = new Dominators(true);
75 dominators.visitMethod(ir.getMethod());
76 DominatorNode n = dominators.computeTree();
77 dominators.calculateDominanceFrontier(n);
78 this.link_registers = new HashMap();
79 this.register_uses = new GenericMultiMap();
80 prepare();
81 patchPEIgeneratedValues();
82 computeSSA(ir);
83 }
84
85 /***
86 * Perform some calculations to prepare for SSA construction.
87 */
88 private void prepare() {
89 live = LivenessAnalysis.solve(ir);
90 }
91
92 /***
93 * Work around some problems with PEI-generated values and handlers.
94 * Namely, if a PEI has a return value, rename the result register before
95 * and after the PEI in order to reflect the fact that the PEI may not
96 * actually assign the result register.
97 */
98 private void patchPEIgeneratedValues() {
99
100 if (ir.getExceptionHandlers().isEmpty())
101 return;
102 Set needed = new HashSet(4);
103 Iterator blocks = ir.reversePostOrderIterator();
104 while (blocks.hasNext()) {
105 BasicBlock block = (BasicBlock) blocks.next();
106 ExceptionHandlerList ehl = block.getExceptionHandlers();
107 if (!ehl.isEmpty()) {
108 Quad pei = block.getLastQuad();
109 if (pei != null && !pei.getThrownExceptions().isEmpty() && Special.getOp1(pei) instanceof RegisterOperand) {
110 boolean copyNeeded = false;
111 RegisterOperand v = (RegisterOperand) Special.getOp1(pei);
112 Register orig = v.getRegister();
113 Iterator out = ehl.mayCatch(pei.getThrownExceptions()).iterator();
114 while (out.hasNext()) {
115 ExceptionHandler eh = (ExceptionHandler) out.next();
116 BasicBlock exp = eh.getEntry();
117 if (live.isLiveAtIn(exp, orig)) {
118 copyNeeded = true;
119 break;
120 }
121 }
122 if (copyNeeded) {
123 Iterator out2 = ehl.mayCatch(pei.getThrownExceptions()).iterator();
124 while (out2.hasNext()) {
125 ExceptionHandler eh = (ExceptionHandler) out2.next();
126 BasicBlock exp = eh.getEntry();
127 needed.add(new Pair(exp, v));
128 }
129 }
130 }
131 }
132 }
133
134 Iterator copies = needed.iterator();
135 while (copies.hasNext()) {
136 Pair copy = (Pair) copies.next();
137 BasicBlock inBlock = (BasicBlock) copy.left;
138 RegisterOperand registerOp = (RegisterOperand) copy.right;
139 jq_Type type = registerOp.getType();
140 Register register = registerOp.getRegister();
141 Register temp = ir.getRegisterFactory().makeReg(register);
142 inBlock.addQuad(0, Move.create(ir.getNewQuadID(), register, temp, type));
143 live.setLiveAtIn(inBlock, temp);
144 Iterator outBlocks = inBlock.getPredecessors().iterator();
145 while (outBlocks.hasNext()) {
146 BasicBlock outBlock = (BasicBlock) outBlocks.next();
147 Quad x = Move.create(ir.getNewQuadID(), temp, register, type);
148 outBlock.addAtEnd(ir, x);
149 live.setKilledAtIn(outBlock, temp);
150 }
151 }
152 }
153
154 /***
155 * Calculate SSA form for an IR. This routine holds the guts of the
156 * transformation.
157 */
158 private void computeSSA(ControlFlowGraph ir) {
159
160 if (DEBUG)
161 System.out.println("Computing register lists...");
162
163 markSSARegisterFlags(ir);
164
165
166
167 if (DEBUG)
168 System.out.println("Find defs for each register...");
169 BitString[] defSets = getDefSets();
170
171 if (DEBUG)
172 System.out.println("Insert phi functions...");
173 insertPhiFunctions(ir, defSets);
174
175 if (DEBUG)
176 System.out.println("Before renaming...");
177 if (DEBUG)
178 System.out.println(ir.fullDump());
179 if (DEBUG)
180 System.out.println("Renaming...");
181 renameSymbolicRegisters();
182 if (DEBUG)
183 System.out.println("SSA done.");
184 if (PRINT_SSA)
185 System.out.println(ir.fullDump());
186 }
187
188 /***
189 * Calculate the set of blocks that contain defs for each symbolic register
190 * in an IR. <em> Note: </em> This routine skips registers marked already
191 * having a single static definition, physical registers, and guard
192 * registers.
193 *
194 * @return an array of BitVectors, where element <em>i</em> represents
195 * the basic blocks that contain defs for symbolic register <em>i</em>
196 */
197 private BitString[] getDefSets() {
198 int nBlocks = ir.getNumberOfBasicBlocks();
199 BitString[] result = new BitString[ir.getRegisterFactory().size()];
200 for (int i = 0; i < result.length; i++)
201 result[i] = new BitString(nBlocks);
202
203 for (Iterator e = ir.reversePostOrderIterator(); e.hasNext();) {
204 BasicBlock bb = (BasicBlock) e.next();
205 if (DEBUG) System.out.println("Visiting "+bb);
206 int bbNumber = bb.getID();
207
208 for (Iterator ie = bb.iterator(); ie.hasNext(); ) {
209 Quad s = (Quad) ie.next();
210
211
212 for (Iterator j = s.getDefinedRegisters().iterator(); j.hasNext(); ) {
213 RegisterOperand operand = (RegisterOperand) j.next();
214 if (operand.getRegister().isSSA()) continue;
215 if (operand.getRegister().isPhysical()) continue;
216 if (operand.getRegister().isGuard()) continue;
217 int reg = operand.getRegister().getNumber();
218 result[reg].set(bbNumber);
219 }
220 }
221 }
222 return result;
223 }
224
225 /***
226 * Insert the necessary phi functions into an IR.
227 * <p>
228 * Algorithm:
229 * <p>
230 * For register r, let S be the set of all blocks that contain defs of r.
231 * Let D be the iterated dominance frontier of S. Each block in D needs a
232 * phi-function for r.
233 *
234 * <p>
235 * Special Java case: if node N dominates all defs of r, then N does not
236 * need a phi-function for r
237 */
238 private void insertPhiFunctions(ControlFlowGraph ir, BitString[] defs) {
239 for (Iterator it = ir.getRegisterFactory().iterator(); it.hasNext(); ) {
240 Register reg = (Register) it.next();
241 int r = reg.getNumber();
242 if (reg.isSSA()) continue;
243 if (reg.isPhysical()) continue;
244 if (reg.isGuard()) continue;
245 if (DEBUG)
246 System.out.println("Inserting phis for register " + r);
247 if (DEBUG)
248 System.out.println("Start iterated frontier...");
249 BitString needsPhi = dominators.getIteratedDominanceFrontier(defs[r]);
250 if (DEBUG)
251 System.out.println("Iterated frontier = "+needsPhi);
252 removePhisThatDominateAllDefs(needsPhi, ir, defs[r]);
253 if (DEBUG)
254 System.out.println("Done.");
255 for (BitStringIterator i = needsPhi.iterator(); i.hasNext(); ) {
256 int b = i.nextIndex();
257 BasicBlock bb = basic_blocks[b];
258 if (live.isLiveAtIn(bb, reg)) {
259 if (DEBUG)
260 System.out.println("Inserting phi at "+bb);
261 insertPhi(bb, reg);
262 } else {
263 if (DEBUG)
264 System.out.println(reg+" not live at "+bb);
265 }
266 }
267 }
268 }
269
270 /***
271 * If node N dominates all defs of a register r, then N does not need a phi
272 * function for r; this function removes such nodes N from a Bit Set.
273 *
274 * @param needsPhi
275 * representation of set of nodes that need phi functions
276 * for a register r
277 * @param defs
278 * set of nodes that define register r
279 */
280 private void removePhisThatDominateAllDefs(BitString needsPhi, ControlFlowGraph ir, BitString defs) {
281 for (BitStringIterator i = needsPhi.iterator(); i.hasNext(); ) {
282 int index = i.nextIndex();
283 if (dominators.dominates(index, defs)) {
284 if (DEBUG)
285 System.out.println(index+" dominates all defs, so phi is not needed.");
286 needsPhi.clear(index);
287 }
288 }
289 }
290
291 /***
292 * Insert a phi function for a symbolic register at the head of a basic
293 * block.
294 *
295 * @param bb
296 * the basic block
297 * @param r
298 * the symbolic register that needs a phi function
299 */
300 private void insertPhi(BasicBlock bb, Register r) {
301 Quad s = makePhiInstruction(r, bb);
302 bb.addQuad(0, s);
303 scalarPhis.add(s);
304 }
305
306 /***
307 * Create a phi-function instruction
308 *
309 * @param r
310 * the symbolic register
311 * @param bb
312 * the basic block holding the new phi function
313 * @return the instruction r = PHI null,null,..,null
314 */
315 private Quad makePhiInstruction(Register r, BasicBlock bb) {
316 int n = bb.getNumberOfPredecessors();
317 Iterator in = bb.getPredecessors().iterator();
318 jq_Type type = null;
319 Quad s = Phi.create(ir.getNewQuadID(), Phi.PHI.INSTANCE, new RegisterOperand(r, type), n);
320 for (int i = 0; i < n; i++) {
321 RegisterOperand junk = new RegisterOperand(r, type);
322 Phi.setSrc(s, i, junk);
323 BasicBlock pred = (BasicBlock) in.next();
324 Phi.setPred(s, i, pred);
325 }
326
327
328 return s;
329 }
330
331 /***
332 * Rename the symbolic registers so that each register has only one
333 * definition.
334 */
335 private void renameSymbolicRegisters() {
336 int n = ir.getRegisterFactory().size();
337 Stack[] S = new Stack[n];
338 for (int i = 0; i < S.length; i++) {
339 S[i] = new Stack();
340 }
341
342
343 jq_Type[] paramTypes = ir.getMethod().getParamTypes();
344 for (int i = 0, j = 0; i < paramTypes.length; ++i, ++j) {
345 jq_Type t = paramTypes[i];
346 Register r = ir.getRegisterFactory().getOrCreateLocal(j, t);
347 if (DEBUG) System.out.println("Param "+i+" local "+j+" type "+t+" register "+r);
348 if (t.getReferenceSize() == 8) ++j;
349 S[r.getNumber()].push(new RegisterOperand(r, t));
350 }
351 for (int i = 0; i < S.length; i++) {
352
353
354 if (S[i].isEmpty()) S[i].push(null);
355 }
356 BasicBlock entry = ir.entry();
357 numPredProcessed = new int[ir.getNumberOfBasicBlocks()];
358 search(entry, S);
359 markSSARegisterFlags(ir);
360 rectifyPhiTypes();
361 }
362
363 MultiMap register_uses;
364
365 Map link_registers;
366
367 /***
368 *
369 * @param X
370 * basic block to search dominator tree from
371 * @param S
372 * stack of names for each register
373 */
374 private void search(BasicBlock X, Stack[] S) {
375 if (DEBUG)
376 System.out.println("SEARCH " + X);
377 for (Iterator ie = X.iterator(); ie.hasNext(); ) {
378 Quad A = (Quad) ie.next();
379 if (!(A.getOperator() instanceof Phi)) {
380
381 for (Iterator u = A.getUsedRegisters().iterator(); u.hasNext(); ) {
382 RegisterOperand rop = (RegisterOperand) u.next();
383 Register r1 = rop.getRegister();
384 if (r1.isSSA()) continue;
385 if (r1.isPhysical()) continue;
386 if (r1.isGuard()) continue;
387 RegisterOperand r2 = (RegisterOperand) S[r1.getNumber()].peek();
388 if (DEBUG)
389 System.out.println("REPLACE NORMAL USE " + r1
390 + " with " + r2);
391 if (r2 != null) {
392 rop.setRegister(r2.getRegister());
393 register_uses.add(rop.getRegister(), rop);
394 }
395 }
396 }
397
398 for (Iterator d = A.getDefinedRegisters().iterator(); d.hasNext(); ) {
399 RegisterOperand rop = (RegisterOperand) d.next();
400 Register r1 = rop.getRegister();
401 if (r1.isSSA()) continue;
402 if (r1.isPhysical()) continue;
403 if (r1.isGuard()) continue;
404 Register r2 = ir.getRegisterFactory().makeReg(r1);
405 if (DEBUG)
406 System.out.println("PUSH " + r2 + " FOR " + r1 + " BECAUSE " + A);
407 S[r1.getNumber()].push(new RegisterOperand(r2, rop.getType()));
408 rop.setRegister(r2);
409 link_registers.put(r2, r1);
410 }
411 }
412 if (DEBUG)
413 System.out.println("SEARCH (second loop) " + X);
414 for (Iterator y = X.getSuccessors().iterator(); y.hasNext();) {
415 BasicBlock Y = (BasicBlock) y.next();
416 if (DEBUG)
417 System.out.println(" Successor: " + Y);
418 int j = numPredProcessed[Y.getID()]++;
419 if (Y.isExit())
420 continue;
421 Iterator ss = Y.iterator();
422 if (!ss.hasNext()) continue;
423
424 if (DEBUG)
425 System.out.println(" Predecessor: " + j);
426 while (ss.hasNext()) {
427 Quad s = (Quad) ss.next();
428 if (!(s.getOperator() instanceof Phi)) break;
429 Operand val = Phi.getSrc(s, j);
430 if (val instanceof RegisterOperand) {
431 Register r1 = ((RegisterOperand) Phi.getSrc(s, j)).getRegister();
432
433 if (!r1.isSSA()) {
434 RegisterOperand r2 = (RegisterOperand) S[r1.getNumber()].peek();
435 if (r2 == null) {
436
437
438
439 Phi.setSrc(s, j, null);
440 } else {
441 RegisterOperand rop = (RegisterOperand) r2.copy();
442 Phi.setSrc(s, j, rop);
443 register_uses.add(rop.getRegister(), rop);
444 }
445 Phi.setPred(s, j, X);
446 if (DEBUG) System.out.println("Set "+j+": "+s);
447 }
448 }
449 }
450 }
451 if (DEBUG)
452 System.out.println("SEARCH (third loop) " + X);
453 for (Iterator c = dominators.getDominatorNode(X).getChildren().iterator(); c.hasNext(); ) {
454 DominatorNode v = (DominatorNode) c.next();
455 if (DEBUG) System.out.println(" Dominator Node " + v);
456 search(v.getBasicBlock(), S);
457 }
458 if (DEBUG)
459 System.out.println("SEARCH (fourth loop) " + X);
460 for (Iterator a = X.iterator(); a.hasNext(); ) {
461 Quad A = (Quad) a.next();
462
463 for (Iterator d = A.getDefinedRegisters().iterator(); d.hasNext(); ) {
464 RegisterOperand newOp = (RegisterOperand) d.next();
465 Register newReg = newOp.getRegister();
466 if (newReg.isSSA()) continue;
467 if (newReg.isPhysical()) continue;
468 if (newReg.isGuard()) continue;
469 Register r1 = (Register) link_registers.get(newReg);
470 S[r1.getNumber()].pop();
471 if (DEBUG)
472 System.out.println("POP " + r1);
473 }
474 }
475 if (DEBUG)
476 System.out.println("FINISHED SEARCH " + X);
477 }
478
479 /***
480 * Compute type information for operands in each phi instruction.
481 */
482 private void rectifyPhiTypes() {
483 if (DEBUG)
484 System.out.println("Rectify phi types.");
485 removeAllUnreachablePhis(scalarPhis);
486 while (!scalarPhis.isEmpty()) {
487 boolean didSomething = false;
488 for (Iterator i = scalarPhis.iterator(); i.hasNext(); ) {
489 Quad phi = (Quad) i.next();
490 if (DEBUG)
491 System.out.println("PHI: " + phi);
492 jq_Type meet = meetPhiType(phi);
493 if (DEBUG)
494 System.out.println("MEET: " + meet);
495 if (meet != null) {
496 didSomething = true;
497 i.remove();
498 RegisterOperand result = (RegisterOperand) Phi.getDest(phi);
499 result.setType(meet);
500 for (Iterator e = register_uses.getValues(result.getRegister()).iterator(); e.hasNext();) {
501 RegisterOperand rop = (RegisterOperand) e.next();
502 rop.setType(meet);
503 }
504 }
505 }
506 if (!didSomething) {
507
508 return;
509 }
510 }
511 }
512
513 /***
514 * Remove all phis that are unreachable
515 */
516 private void removeAllUnreachablePhis(Set scalarPhis) {
517 boolean iterateAgain = false;
518 do {
519 iterateAgain = false;
520 outer : for (Iterator i = scalarPhis.iterator(); i.hasNext();) {
521 Quad phi = (Quad) i.next();
522 for (int j = 0; j < Phi.getSrcs(phi).length(); j++) {
523 Operand op = Phi.getSrc(phi, j);
524 if (op != null) {
525 continue outer;
526 }
527 }
528 RegisterOperand result = Phi.getDest(phi);
529 i.remove();
530 Register resultReg = result.getRegister();
531 Collection values = register_uses.getValues(resultReg);
532 for (Iterator e = values.iterator(); e.hasNext(); ) {
533 RegisterOperand use = (RegisterOperand) e.next();
534 Quad s = use.getQuad();
535 if (s.getOperator() instanceof Phi) {
536 for (int k = 0; k < Phi.getSrcs(phi).length(); k++) {
537 Operand op = Phi.getSrc(phi, k);
538 if (op != null && op.isSimilar(result)) {
539 Phi.setSrc(phi, k, null);
540 if (DEBUG) System.out.println("Set src "+k+": "+phi);
541 iterateAgain = true;
542 }
543 }
544 }
545 }
546 }
547 } while (iterateAgain);
548 }
549
550 /***
551 * Return the meet of the types on the rhs of a phi instruction
552 */
553 private jq_Type meetPhiType(Quad s) {
554 jq_Type result = null;
555 for (int i = 0; i < Phi.getSrcs(s).length(); i++) {
556 Operand val = Phi.getSrc(s, i);
557 if (val == null) continue;
558 jq_Type t = ((RegisterOperand)val).getType();
559 if (t == jq_NullType.NULL_TYPE) {
560 continue;
561 }
562 if (result == null) {
563 result = t;
564 continue;
565 }
566 if (t == null) {
567 continue;
568 }
569 if (result == jq_ReturnAddressType.INSTANCE ||
570 t == jq_ReturnAddressType.INSTANCE) {
571
572 continue;
573 }
574 jq_Type meet = TypeCheck.findCommonSuperclass(result, t, false);
575 if (meet == null) {
576 if ((result.isIntLike() && (t.isReferenceType() || t.getReferenceSize() == 4))
577 || ((result.isReferenceType() || result.getReferenceSize() == 4) && t.isIntLike())) {
578 meet = jq_Primitive.INT;
579 } else if (result.isReferenceType() && t.getReferenceSize() == 4) {
580 meet = t;
581 } else if (result.getReferenceSize() == 4 && t.isReferenceType()) {
582 meet = result;
583 }
584 }
585 if (meet == null) {
586 Assert.UNREACHABLE(result + " and " + t + " meet to null");
587 }
588 result = meet;
589 }
590 return result;
591 }
592
593 public static void markSSARegisterFlags(ControlFlowGraph cfg) {
594 Set defined = new HashSet();
595 for (Iterator i = cfg.getRegisterFactory().iterator(); i.hasNext(); ) {
596 Register r = (Register) i.next();
597 r.setSSA();
598 }
599 for (QuadIterator i = new QuadIterator(cfg); i.hasNext(); ) {
600 Quad q = i.nextQuad();
601 for (Iterator j = q.getDefinedRegisters().iterator(); j.hasNext(); ) {
602 RegisterOperand rop = (RegisterOperand) j.next();
603 Register r = rop.getRegister();
604 boolean change = defined.add(r);
605 if (!change) r.clearSSA();
606 }
607 }
608 if (DEBUG) {
609 System.out.println("Defined registers: "+defined);
610 System.out.print("SSA registers: ");
611 for (Iterator i = cfg.getRegisterFactory().iterator(); i.hasNext(); ) {
612 Register r = (Register) i.next();
613 if (r.isSSA()) System.out.print(" "+r);
614 }
615 System.out.println();
616 System.out.print("Non-SSA registers: ");
617 for (Iterator i = cfg.getRegisterFactory().iterator(); i.hasNext(); ) {
618 Register r = (Register) i.next();
619 if (!r.isSSA()) System.out.print(" "+r);
620 }
621 System.out.println();
622 }
623 }
624 }