1
3 package jminusminus;
4
5 import java.util.ArrayList;
6 import java.util.LinkedList;
7 import java.util.Queue;
8 import static jminusminus.NPhysicalRegister.*;
9
10
16
17 public class NNaiveRegisterAllocator extends NRegisterAllocator {
18
19
25
26 public NNaiveRegisterAllocator(NControlFlowGraph cfg) {
27 super(cfg);
28 }
29
30
33
34 public void allocation() {
35 for (NInterval interval : cfg.intervals) {
38 NBasicBlock lastBlock = cfg.basicBlocks
39 .get(cfg.basicBlocks.size() - 1);
40 NLIRInstruction lastLir = lastBlock.lir
41 .get(lastBlock.lir.size() - 1);
42 interval.ranges.add(new NRange(0, lastLir.id));
43 }
44
45 for (int i = 0; i < 32; i++) {
49 if (cfg.registers.get(i) != null) {
50 cfg.intervals.get(i).pRegister = (NPhysicalRegister) cfg.registers
51 .get(i);
52 }
53 }
54
55 for (NBasicBlock block : cfg.basicBlocks) {
59 for (NLIRInstruction lir : block.lir) {
60 if (lir instanceof NLIRLoadLocal) {
61 NLIRLoadLocal loadLocal = (NLIRLoadLocal) lir;
62 if (loadLocal.local >= 4) {
63 NInterval interval = cfg.intervals
64 .get(((NVirtualRegister) loadLocal.write)
65 .number());
66 interval.spill = true;
67 interval.offset = loadLocal.local - 3;
68 interval.offsetFrom = OffsetFrom.FP;
69 }
70 }
71 }
72 }
73
74 Queue<NInterval> assigned = new LinkedList<NInterval>();
76 for (int i = 32, j = 0; i < cfg.intervals.size(); i++) {
77 NInterval interval = cfg.intervals.get(i);
78 if (interval.pRegister == null) {
79 if (j >= NPhysicalRegister.MAX_COUNT) {
80 NInterval spilled = assigned.remove();
86 spilled.spill = true;
87 if (spilled.offset == -1) {
88 spilled.offset = cfg.offset++;
89 spilled.offsetFrom = OffsetFrom.SP;
90 }
91 interval.pRegister = spilled.pRegister;
92 interval.spill = true;
93 if (interval.offset == -1) {
94 interval.offset = cfg.offset++;
95 interval.offsetFrom = OffsetFrom.SP;
96 }
97 } else {
98 NPhysicalRegister pRegister = NPhysicalRegister.regInfo[T0
100 + j++];
101 interval.pRegister = pRegister;
102 cfg.pRegisters.add(pRegister);
103 }
104 assigned.add(interval);
105 }
106 }
107
108 for (int i = 1; i < cfg.basicBlocks.size(); i++) { NBasicBlock block = cfg.basicBlocks.get(i);
117 ArrayList<NLIRInstruction> newLir = new ArrayList<NLIRInstruction>();
118 for (NLIRInstruction lir : block.lir) {
119 newLir.add(lir);
120 }
121 for (NLIRInstruction lir : block.lir) {
122 int id = lir.id;
123
124 if (lir.reads.size() == 2) {
125 NInterval input1 = cfg.intervals.get(
126 lir.reads.get(0).number()).childAt(id);
127 NInterval input2 = cfg.intervals.get(
128 lir.reads.get(1).number()).childAt(id);
129 if (input1.pRegister == input2.pRegister) {
130 input2.pRegister = NPhysicalRegister.regInfo[T0
131 + (input2.pRegister.number() + 1)
132 % NPhysicalRegister.MAX_COUNT];
133 }
134 }
135
136 for (int j = 0; j < lir.reads.size(); j++) {
138 NInterval input = cfg.intervals.get(
139 lir.reads.get(j).number()).childAt(id);
140 if (input.spill) {
141 NLIRLoad load = new NLIRLoad(block, id
142 - lir.reads.size() + j, input.offset,
143 input.offsetFrom, input.pRegister);
144 newLir.add(newLir.indexOf(lir), load);
145 }
146 }
147
148 if (lir.write != null) {
150 NInterval output = cfg.intervals.get(lir.write.number());
151 if (output.spill) {
152 NLIRStore store = new NLIRStore(block, id + 1,
153 output.offset, output.offsetFrom, lir.write);
154 newLir.add(newLir.indexOf(lir) + 1, store);
155 }
156 }
157 }
158 block.lir = newLir;
159 }
160 }
161
162 }