1
3 package jminusminus;
4
5 import java.util.ArrayList;
6 import java.util.LinkedList;
7 import java.util.Queue;
8
9 import static jminusminus.NPhysicalRegister.*;
10
11
16 public class NNaiveRegisterAllocator extends NRegisterAllocator {
17
22 public NNaiveRegisterAllocator(NControlFlowGraph cfg) {
23 super(cfg);
24 }
25
26
29 public void allocation() {
30 for (NInterval interval : cfg.intervals) {
32 NBasicBlock lastBlock = cfg.basicBlocks.get(cfg.basicBlocks.size() - 1);
33 NLIRInstruction lastLir = lastBlock.lir.get(lastBlock.lir.size() - 1);
34 interval.ranges.add(new NRange(0, lastLir.id));
35 }
36
37 preprocess();
38
39 Queue<NInterval> assigned = new LinkedList<NInterval>();
41 for (int i = 32, j = 0; i < cfg.intervals.size(); i++) {
42 NInterval interval = cfg.intervals.get(i);
43 if (interval.pRegister == null) {
44 if (j >= MAX_COUNT) {
45 NInterval spilled = assigned.remove();
49 spilled.spill = true;
50 if (spilled.offset == -1) {
51 spilled.offset = cfg.offset++;
52 spilled.offsetFrom = OffsetFrom.SP;
53 }
54 interval.pRegister = spilled.pRegister;
55 interval.spill = true;
56 if (interval.offset == -1) {
57 interval.offset = cfg.offset++;
58 interval.offsetFrom = OffsetFrom.SP;
59 }
60 } else {
61 NPhysicalRegister pRegister = regInfo[T0 + j++];
63 interval.pRegister = pRegister;
64 cfg.pRegisters.add(pRegister);
65 }
66 assigned.add(interval);
67 }
68 }
69
70 for (int i = 1; i < cfg.basicBlocks.size(); i++) {
73 NBasicBlock block = cfg.basicBlocks.get(i);
75 ArrayList<NLIRInstruction> newLir = new ArrayList<NLIRInstruction>();
76 for (NLIRInstruction lir : block.lir) {
77 newLir.add(lir);
78 }
79 for (NLIRInstruction lir : block.lir) {
80 int id = lir.id;
81 if (lir.reads.size() == 2) {
82 NInterval input1 = cfg.intervals.get(lir.reads.get(0).number()).childAt(id);
83 NInterval input2 = cfg.intervals.get(lir.reads.get(1).number()).childAt(id);
84 if (input1.pRegister == input2.pRegister) {
85 input2.pRegister =
86 regInfo[T0 + (input2.pRegister.number() + 1) % MAX_COUNT];
87 }
88 }
89
90 for (int j = 0; j < lir.reads.size(); j++) {
92 NInterval input = cfg.intervals.get(lir.reads.get(j).number()).childAt(id);
93 if (input.spill) {
94 NLIRLoad load = new NLIRLoad(block, id - lir.reads.size() + j, input.offset,
95 input.offsetFrom, input.pRegister);
96 newLir.add(newLir.indexOf(lir), load);
97 }
98 }
99
100 if (lir.write != null) {
102 NInterval output = cfg.intervals.get(lir.write.number());
103 if (output.spill) {
104 NLIRStore store = new NLIRStore(block, id + 1, output.offset,
105 output.offsetFrom, lir.write);
106 newLir.add(newLir.indexOf(lir) + 1, store);
107 }
108 }
109 }
110 block.lir = newLir;
111 }
112 }
113 }
114