1
3 package jminusminus;
4
5 import java.util.ArrayList;
6 import java.util.BitSet;
7
8
13
14 public abstract class NRegisterAllocator {
15
16
17 protected NControlFlowGraph cfg;
18
19
26
27 protected NRegisterAllocator(NControlFlowGraph cfg) {
28 this.cfg = cfg;
29 this.cfg.intervals = new ArrayList<NInterval>();
30 for (int i = 0; i < cfg.registers.size(); i++) {
31 this.cfg.intervals.add(new NInterval(i, cfg));
32 }
33 this.cfg.maxIntervals = this.cfg.intervals.size();
34 }
35
36
40
41 public abstract void allocation();
42
43
46
47 protected void buildIntervals() {
48 this.computeLocalLiveSets();
49 this.computeGlobalLiveSets();
50 for (int i = cfg.basicBlocks.size() - 1; i >= 0; i--) {
51 NBasicBlock currBlock = cfg.basicBlocks.get(i);
52 if (currBlock.lir.size() == 0) {
53 continue;
54 }
55 int blockStart = currBlock.lir.get(0).id;
56 int blockEnd = currBlock.lir.get(currBlock.lir.size() - 1).id;
57 BitSet liveOut = currBlock.liveOut;
58 for (int idx = liveOut.nextSetBit(0); idx >= 0; idx = liveOut
59 .nextSetBit(idx + 1)) {
60 cfg.intervals.get(idx).addOrExtendNRange(
61 new NRange(blockStart, blockEnd));
62 }
63 for (int j = currBlock.lir.size() - 1; j >= 0; j--) {
64 int currLIRid = currBlock.lir.get(j).id;
65 NRegister output = currBlock.lir.get(j).write;
66 if (output != null) {
67 cfg.intervals.get(output.number).newFirstRangeStart(
68 currLIRid);
69 cfg.intervals.get(output.number).addUsePosition(currLIRid,
70 InstructionType.write);
71 }
72 ArrayList<NRegister> inputs = currBlock.lir.get(j).reads;
73 for (NRegister reg : inputs) {
74 cfg.intervals.get(reg.number).addOrExtendNRange(
75 new NRange(blockStart, currLIRid));
76 cfg.intervals.get(reg.number).addUsePosition(currLIRid,
77 InstructionType.read);
78 }
79 }
80 }
81 }
82
83
89
90 private void computeLocalLiveSets() {
91 for (NBasicBlock block : cfg.basicBlocks) {
92 block.liveUse = new BitSet(cfg.registers.size());
93 block.liveDef = new BitSet(cfg.registers.size());
94 for (NLIRInstruction inst : block.lir) {
95 for (NRegister reg : inst.reads) {
96 if (!(block.liveDef.get(reg.number()))) {
97 block.liveUse.set(reg.number());
98 }
99 }
100 if (inst.write != null) {
101 block.liveDef.set(inst.write.number());
102 }
103 }
104 }
105 }
106
107
112
113 private void computeGlobalLiveSets() {
114 boolean changed = false;
115 for (NBasicBlock b : cfg.basicBlocks) {
116 b.liveOut = new BitSet(cfg.registers.size());
117 }
118
119 do {
121 changed = false;
122 for (int i = cfg.basicBlocks.size() - 1; i >= 0; i--) {
123 NBasicBlock currBlock = cfg.basicBlocks.get(i);
124 BitSet newLiveOut = new BitSet(cfg.registers.size());
125 for (NBasicBlock successor : currBlock.successors) {
126 newLiveOut.or(successor.liveIn);
127 }
128 if (!currBlock.liveOut.equals(newLiveOut)) {
129 currBlock.liveOut = newLiveOut;
130 changed = true;
131 }
132 currBlock.liveIn = (BitSet) currBlock.liveOut.clone();
133 currBlock.liveIn.andNot(currBlock.liveDef);
134 currBlock.liveIn.or(currBlock.liveUse);
135 }
136 } while (changed);
137 }
138
139 }
140