1   // Copyright 2012- Bill Campbell, Swami Iyer and Bahar Akbal-Delibas
2   
3   package jminusminus;
4   
5   import java.util.ArrayList;
6   import java.util.BitSet;
7   
8   import static jminusminus.NPhysicalRegister.*;
9   
10  /**
11   * The abstract base class for a register allocator that maps virtual registers (from LIR code) to
12   * physical registers on the target (MIPS) machine.
13   */
14  public abstract class NRegisterAllocator {
15      /**
16       * The control flow graph for a method.
17       */
18      protected NControlFlowGraph cfg;
19  
20      /**
21       * Constructs an NRegisterAllocator object.
22       *
23       * @param cfg control flow graph for a method.
24       */
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      /**
35       * Builds the intervals for a control flow graph.
36       */
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      /**
70       * Preprocesses information needed for naive, linear, and graph register allocation schemes.
71       */
72      protected void preprocess() {
73          // Allocate any fixed registers (a0, a1, a2, a3 and v0) that were assigned during generation
74          // phase to the appropriate interval.
75          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          // Assign stack offset (relative to fp) for formal parameters fourth and above, and stack
82          // offset (relative to sp) for arguments fourth or above.
83          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      /**
100      * The work horse that does the allocation, implemented in the sub-classes of this class.
101      */
102     public abstract void allocation();
103 
104     /**
105      * Prints the local and global live sets to standard output.
106      *
107      * @param p for pretty printing with indentation.
108      */
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     // Iterates through a list of basic blocks in order, and sets their liveUse and liveDef
163     // fields to the appropriate virtual registers.
164     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     // Iterates through a list of basic blocks in reverse order, and sets their lliveIn and
182     // liveOut fields to reflect global use-def information.
183     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