1
3 package jminusminus;
4
5 import java.util.ArrayList;
6 import java.util.BitSet;
7
8 import static jminusminus.NPhysicalRegister.*;
9
10
14 public abstract class NRegisterAllocator {
15
18 protected NControlFlowGraph cfg;
19
20
25 protected NRegisterAllocator(NControlFlowGraph cfg) {
26 this.cfg = cfg;
27 this.cfg.intervals = new ArrayList<NInterval>();
28 for (int i = 0; i < cfg.registers.size(); i++) {
29 this.cfg.intervals.add(new NInterval(i, cfg));
30 }
31 this.cfg.maxIntervals = this.cfg.intervals.size();
32 }
33
34
37 protected void buildIntervals() {
38 this.computeLocalLiveSets();
39 this.computeGlobalLiveSets();
40 for (int i = cfg.basicBlocks.size() - 1; i >= 0; i--) {
41 NBasicBlock currBlock = cfg.basicBlocks.get(i);
42 if (currBlock.lir.size() == 0) {
43 continue;
44 }
45 int blockStart = currBlock.lir.get(0).id;
46 int blockEnd = currBlock.lir.get(currBlock.lir.size() - 1).id;
47 BitSet liveOut = currBlock.liveOut;
48 for (int idx = liveOut.nextSetBit(0); idx >= 0; idx = liveOut.nextSetBit(idx + 1)) {
49 cfg.intervals.get(idx).addOrExtendNRange(new NRange(blockStart, blockEnd));
50 }
51 for (int j = currBlock.lir.size() - 1; j >= 0; j--) {
52 int currLIRid = currBlock.lir.get(j).id;
53 NRegister output = currBlock.lir.get(j).write;
54 if (output != null) {
55 cfg.intervals.get(output.number).newFirstRangeStart(currLIRid);
56 cfg.intervals.get(output.number).addUsePosition(currLIRid,
57 InstructionType.write);
58 }
59 ArrayList<NRegister> inputs = currBlock.lir.get(j).reads;
60 for (NRegister reg : inputs) {
61 cfg.intervals.get(reg.number).addOrExtendNRange(new NRange(blockStart,
62 currLIRid));
63 cfg.intervals.get(reg.number).addUsePosition(currLIRid, InstructionType.read);
64 }
65 }
66 }
67 }
68
69
72 protected void preprocess() {
73 for (int i = 0; i < 32; i++) {
76 if (cfg.registers.get(i) != null) {
77 cfg.intervals.get(i).pRegister = ((NPhysicalRegister) cfg.registers.get(i));
78 }
79 }
80
81 for (NBasicBlock block : cfg.basicBlocks) {
84 for (NLIRInstruction lir : block.lir) {
85 if (lir instanceof NLIRLoadLocal) {
86 NLIRLoadLocal loadLocal = (NLIRLoadLocal) lir;
87 if (loadLocal.getLocal() >= 4) {
88 NInterval interval = cfg.intervals.get(((NVirtualRegister)
89 loadLocal.write).number());
90 interval.spill = true;
91 interval.offset = loadLocal.getLocal() - 3;
92 interval.offsetFrom = OffsetFrom.FP;
93 }
94 }
95 }
96 }
97 }
98
99
102 public abstract void allocation();
103
104
109 public void writeLivenessInfoToStdOut(PrettyPrinter p) {
110 p.indentRight();
111 p.printf("[[ LOCAL LIVENESS INFORMATION ]]\n\n");
112 for (NBasicBlock block : cfg.basicBlocks) {
113 p.printf("%s\n", block.id());
114 String s = "";
115 BitSet use = block.liveUse;
116 for (int i = use.nextSetBit(0); i >= 0; i = use.nextSetBit(i + 1)) {
117 if (i < 32) {
118 s += regInfo[i] + " ";
119 } else {
120 s += "V" + i + " ";
121 }
122 }
123 p.println("liveUse: " + s);
124 s = "";
125 BitSet def = block.liveDef;
126 for (int i = def.nextSetBit(0); i >= 0; i = def.nextSetBit(i + 1)) {
127 if (i < 32) {
128 s += regInfo[i] + " ";
129 } else {
130 s += "V" + i + " ";
131 }
132 }
133 p.printf("liveDef: %s\n\n", s);
134 }
135 p.printf("[[ GLOBAL LIVENESS INFORMATION ]]\n\n");
136 for (int idx = cfg.basicBlocks.size() - 1; idx >= 0; idx--) {
137 p.printf("%s\n", cfg.basicBlocks.get(idx).id());
138 String s = "";
139 BitSet in = cfg.basicBlocks.get(idx).liveIn;
140 for (int i = in.nextSetBit(0); i >= 0; i = in.nextSetBit(i + 1)) {
141 if (i < 32) {
142 s += regInfo[i] + " ";
143 } else {
144 s += "V" + i + " ";
145 }
146 }
147 p.println("liveIn: " + s);
148 s = "";
149 BitSet out = cfg.basicBlocks.get(idx).liveOut;
150 for (int i = out.nextSetBit(0); i >= 0; i = out.nextSetBit(i + 1)) {
151 if (i < 32) {
152 s += regInfo[i] + " ";
153 } else {
154 s += "V" + i + " ";
155 }
156 }
157 p.printf("liveOut: %s\n\n", s);
158 }
159 p.indentLeft();
160 }
161
162 private void computeLocalLiveSets() {
165 for (NBasicBlock block : cfg.basicBlocks) {
166 block.liveUse = new BitSet(cfg.registers.size());
167 block.liveDef = new BitSet(cfg.registers.size());
168 for (NLIRInstruction inst : block.lir) {
169 for (NRegister reg : inst.reads) {
170 if (!(block.liveDef.get(reg.number()))) {
171 block.liveUse.set(reg.number());
172 }
173 }
174 if (inst.write != null) {
175 block.liveDef.set(inst.write.number());
176 }
177 }
178 }
179 }
180
181 private void computeGlobalLiveSets() {
184 boolean changed = false;
185 for (NBasicBlock b : cfg.basicBlocks) {
186 b.liveOut = new BitSet(cfg.registers.size());
187 }
188 do {
189 changed = false;
190 for (int i = cfg.basicBlocks.size() - 1; i >= 0; i--) {
191 NBasicBlock currBlock = cfg.basicBlocks.get(i);
192 BitSet newLiveOut = new BitSet(cfg.registers.size());
193 for (NBasicBlock successor : currBlock.successors) {
194 newLiveOut.or(successor.liveIn);
195 }
196 if (!currBlock.liveOut.equals(newLiveOut)) {
197 currBlock.liveOut = newLiveOut;
198 changed = true;
199 }
200 currBlock.liveIn = (BitSet) currBlock.liveOut.clone();
201 currBlock.liveIn.andNot(currBlock.liveDef);
202 currBlock.liveIn.or(currBlock.liveUse);
203 }
204 } while (changed);
205 }
206 }
207