1 witchel 1.1.2.1 // BypassLatchSchedule.java, created Wed Sep 27 20:01:40 EDT 2000 by witchel
2 cananian 1.1.2.6 // Copyright (C) 1999 Emmett Witchel <witchel@mit.edu>
3 witchel 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 witchel 1.1.2.1 package harpoon.Backend.MIPS;
5 witchel 1.1.2.1
6 witchel 1.1.2.1 import harpoon.Analysis.DataFlow.LiveTemps;
7 witchel 1.1.2.1 import harpoon.Analysis.BasicBlock;
8 witchel 1.1.2.1 import harpoon.Backend.Generic.Frame;
9 witchel 1.1.2.1 import harpoon.Backend.Generic.Code;
10 witchel 1.1.2.1 import harpoon.Backend.Generic.RegUseDefer;
11 witchel 1.1.2.1 import harpoon.IR.Assem.Instr;
12 witchel 1.1.2.1 import harpoon.IR.Properties.UseDefer;
13 witchel 1.1.2.1 import harpoon.Temp.Temp;
14 witchel 1.1.2.1 import harpoon.Util.Util;
15 witchel 1.1.2.4 import java.util.Collections;
16 witchel 1.1.2.1 import java.util.Iterator;
17 witchel 1.1.2.1 import java.util.List;
18 witchel 1.1.2.1 import java.util.Set;
19 witchel 1.1.2.1
20 witchel 1.1.2.1 /**
21 witchel 1.1.2.1 * <code>BypassLatchSchedule</code> is a transformation on low level,
22 witchel 1.1.2.1 * register allocated assembly code that annotates opcode to indicate
23 witchel 1.1.2.1 * if a given use is the last use of a register. E.g.
24 witchel 1.1.2.1 * add t0, t1, t2
25 witchel 1.1.2.1 * xor t3, t0, t5
26 witchel 1.1.2.1 * If t0 is not live out of xor, then we replace the xor instruction with
27 witchel 1.1.2.1 * xor.l1 t3, t0, t5
28 witchel 1.1.2.1 * which says that this use of operand 1 (RS) is the last use. The
29 witchel 1.1.2.1 * assembler will use this information to not write the t0 value
30 witchel 1.1.2.1 * generated in the add instruction back to the register file.
31 cananian 1.1.2.6 * @author Emmett Witchel <witchel@mit.edu>
32 witchel 1.1.2.1 * @version $Id:
33 witchel 1.1.2.1 */
34 witchel 1.1.2.1
35 witchel 1.1.2.1 public class BypassLatchSchedule {
36 witchel 1.1.2.1
37 witchel 1.1.2.1 /** Returns a new <code>Instr</code> if this instr needs to be
38 witchel 1.1.2.1 * modified. Otherwise, it returns null.
39 witchel 1.1.2.1 */
40 witchel 1.1.2.1 private Instr lastUseInstr(Instr instr) {
41 witchel 1.1.2.1 Set lb = lt.getLiveBefore(instr);
42 witchel 1.1.2.1 Set la = lt.getLiveAfter(instr);
43 witchel 1.1.2.1 Temp[] tmp_use = instr.use();
44 witchel 1.1.2.4 Temp[] tmp_def = instr.def();
45 witchel 1.1.2.3 String assem = instr.getAssem();
46 witchel 1.1.2.3 // XXX omit compound instructions for now
47 witchel 1.1.2.4 if(assem.indexOf('\n') != -1) return null;
48 witchel 1.1.2.3
49 witchel 1.1.2.4 // Omit calls, and remnants of move coalescing
50 witchel 1.1.2.4 if(tmp_use.length > 0
51 witchel 1.1.2.1 && tmp_use.length <= 2
52 witchel 1.1.2.2 && instr.def().length <= 1 /* excludes jal _lookup_handler */
53 witchel 1.1.2.3 && assem.length() > 0
54 witchel 1.1.2.1 ) {
55 cananian 1.3.2.1 assert tmp_use.length <= 2 : " tmp_use.len=" + tmp_use.length
56 cananian 1.3.2.1 + " tmp_use=" + tmp_use + " isntr=" + instr;
57 witchel 1.1.2.1 List reg_use0 = null;
58 witchel 1.1.2.1 List reg_use1 = null;
59 witchel 1.1.2.4 List reg_def = tmp_def.length == 0 ? null
60 witchel 1.1.2.4 : code.getRegisters(instr, tmp_def[0]);
61 witchel 1.1.2.1 boolean oneLast = false;
62 witchel 1.1.2.1 if(tmp_use.length > 0) {
63 witchel 1.1.2.1 reg_use0 = code.getRegisters(instr, tmp_use[0]);
64 witchel 1.1.2.3 oneLast = lb.containsAll(reg_use0)
65 witchel 1.1.2.4 && (la.containsAll(reg_use0) == false
66 witchel 1.1.2.4 || (reg_def != null && reg_use0.containsAll(reg_def)));
67 witchel 1.1.2.1 }
68 witchel 1.1.2.1 boolean twoLast = false;
69 witchel 1.1.2.1 if(tmp_use.length > 1) {
70 witchel 1.1.2.1 reg_use1 = code.getRegisters(instr, tmp_use[1]);
71 witchel 1.1.2.3 twoLast = lb.containsAll(reg_use1)
72 witchel 1.1.2.4 && (la.containsAll(reg_use1) == false
73 witchel 1.1.2.4 || (reg_def != null && reg_use1.containsAll(reg_def)));
74 witchel 1.1.2.1 }
75 witchel 1.1.2.1 if(trace) {
76 witchel 1.1.2.1 System.out.println(instr + "\n\tlb=" + lb + "\n\tla=" + la);
77 witchel 1.1.2.4 if(tmp_def.length > 1) {
78 witchel 1.1.2.4 System.out.print("\tdef multiple");
79 witchel 1.1.2.4 for(int i = 0; i < tmp_def.length; ++i) {
80 witchel 1.1.2.4 System.out.print(" " + tmp_def[i] + " "
81 witchel 1.1.2.4 + code.getRegisters(instr, tmp_def[i]));
82 witchel 1.1.2.4 }
83 witchel 1.1.2.4 System.out.println();
84 witchel 1.1.2.4 }
85 witchel 1.1.2.4 if(tmp_def.length == 1) {
86 witchel 1.1.2.4 System.out.println("\tdef " + tmp_def[0] + " " + reg_def);
87 witchel 1.1.2.4 }
88 witchel 1.1.2.1 if(tmp_use.length == 2) {
89 witchel 1.1.2.1 System.out.println("\tuse(0) " + tmp_use[0]
90 witchel 1.1.2.1 + " " + reg_use0
91 witchel 1.1.2.1 + " use(1) " + tmp_use[1]
92 witchel 1.1.2.1 + " " + reg_use1
93 witchel 1.1.2.1 );
94 witchel 1.1.2.1 } else if (tmp_use.length == 1) {
95 witchel 1.1.2.1 System.out.println("\tuse(0) " + tmp_use[0]
96 witchel 1.1.2.1 + " " + reg_use0);
97 witchel 1.1.2.1 }
98 witchel 1.1.2.1 }
99 witchel 1.1.2.2 if( oneLast || twoLast ) {
100 witchel 1.1.2.1 int space = assem.indexOf(' ');
101 witchel 1.1.2.2 String opcode = assem.substring(0, space);
102 witchel 1.1.2.2 boolean reverse = false;
103 witchel 1.1.2.5 if(opcode.startsWith("sw")
104 witchel 1.1.2.5 || opcode.startsWith("sh")
105 witchel 1.1.2.5 || opcode.startsWith("sb")
106 witchel 1.1.2.5 || opcode.startsWith("sc")
107 witchel 1.1.2.5 || opcode.startsWith("sdc1")
108 witchel 1.1.2.5 || opcode.startsWith("sllv")
109 witchel 1.1.2.5 || opcode.startsWith("sll")
110 witchel 1.1.2.5 || opcode.startsWith("sra")
111 witchel 1.1.2.5 || opcode.startsWith("srav")
112 witchel 1.1.2.5 || opcode.startsWith("srl")
113 witchel 1.1.2.5 || opcode.startsWith("srlv")
114 witchel 1.1.2.5 || opcode.startsWith("negu")
115 witchel 1.1.2.2 ) {
116 witchel 1.1.2.2 reverse = true;
117 witchel 1.1.2.2 }
118 witchel 1.1.2.2 String suffix = "";
119 witchel 1.1.2.2 if( oneLast && twoLast ) {
120 witchel 1.1.2.2 suffix = ".l12";
121 witchel 1.1.2.2 } else if( oneLast ) {
122 witchel 1.1.2.2 if(reverse)
123 witchel 1.1.2.2 suffix = ".l2";
124 witchel 1.1.2.2 else
125 witchel 1.1.2.2 suffix = ".l1";
126 witchel 1.1.2.2 } else if( twoLast ) {
127 witchel 1.1.2.2 if(reverse)
128 witchel 1.1.2.2 suffix = ".l1";
129 witchel 1.1.2.2 else
130 witchel 1.1.2.2 suffix = ".l2";
131 witchel 1.1.2.2 }
132 witchel 1.1.2.2 String new_assem = opcode + suffix + assem.substring(space);
133 witchel 1.1.2.1
134 witchel 1.1.2.1 if(trace)
135 witchel 1.1.2.1 System.out.println(" " + instr.getAssem() + " ==> "+ new_assem);
136 witchel 1.1.2.5 Instr new_i = instr.cloneMutateAssem(new_assem);
137 witchel 1.1.2.2 // XXX This is a gross hack to manually copy register
138 witchel 1.1.2.2 // assignment information because the instr interface
139 witchel 1.1.2.2 // doesn't have a good copy method.
140 witchel 1.1.2.2 Temp[] refs = new_i.use();
141 witchel 1.1.2.2 for(int i = 0; i < refs.length; ++i) {
142 witchel 1.1.2.2 code.assignRegister(new_i, refs[i],
143 witchel 1.1.2.2 code.getRegisters(instr, refs[i]));
144 witchel 1.1.2.2 }
145 witchel 1.1.2.2 refs = new_i.def();
146 witchel 1.1.2.2 for(int i = 0; i < refs.length; ++i) {
147 witchel 1.1.2.2 code.assignRegister(new_i, refs[i],
148 witchel 1.1.2.2 code.getRegisters(instr, refs[i]));
149 witchel 1.1.2.2 }
150 witchel 1.1.2.1 return new_i;
151 witchel 1.1.2.1 }
152 witchel 1.1.2.1 }
153 witchel 1.1.2.1 return null;
154 witchel 1.1.2.1 }
155 witchel 1.1.2.1
156 witchel 1.1.2.1 public BypassLatchSchedule(Code _code, Frame _frame) {
157 witchel 1.1.2.1 code = _code;
158 witchel 1.1.2.1 frame = _frame;
159 witchel 1.1.2.1 RegUseDefer ud = new RegUseDefer(code);
160 witchel 1.1.2.1 lt = LiveTemps.make(code, ud,
161 witchel 1.1.2.1 frame.getRegFileInfo().liveOnExit());
162 witchel 1.1.2.1 BasicBlock.Factory bbFact = new BasicBlock.Factory(code);
163 witchel 1.1.2.1 for(Iterator bbIt = bbFact.blocksIterator(); bbIt.hasNext();) {
164 witchel 1.1.2.1 BasicBlock bb = (BasicBlock)bbIt.next();
165 witchel 1.1.2.1 List instrs = bb.statements();
166 witchel 1.1.2.1 for(int i = 0; i < instrs.size(); ++i) {
167 witchel 1.1.2.1 Instr instr = (Instr)instrs.get(i);
168 witchel 1.1.2.1 Instr new_instr = lastUseInstr(instr);
169 witchel 1.1.2.1 if(new_instr != null) {
170 witchel 1.1.2.1 Instr.replace(instr, new_instr);
171 witchel 1.1.2.1 }
172 witchel 1.1.2.1 }
173 witchel 1.1.2.1 }
174 witchel 1.1.2.1 }
175 witchel 1.1.2.1
176 witchel 1.1.2.1 private final Code code;
177 witchel 1.1.2.1 private final Frame frame;
178 witchel 1.1.2.1 private LiveTemps lt;
179 witchel 1.1.2.2 private boolean trace = false;
180 cananian 1.2 }