1   // Copyright 2013 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   /**
9    * A register allocator maps virtual registers (from LIR code) to physical
10   * registers on the target machine. That there are a limited number of physical
11   * registers makes this interesting.
12   */
13  
14  public abstract class NRegisterAllocator {
15  
16      /** The control flow graph for a method. */
17      protected NControlFlowGraph cfg;
18  
19      /**
20       * Construct an NRegisterAllocator object given the control flow graph for
21       * method.
22       * 
23       * @param cfg
24       *            control flow graph for a method.
25       */
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      /**
37       * The work horse that does the allocation, implemented in the concrete
38       * sub-classes of NRegisterAllocator.
39       */
40  
41      public abstract void allocation();
42  
43      /**
44       * Build the intervals for a control flow graph.
45       */
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      /**
84       * Iterate through a list of basic blocks in order, and sets their liveUse
85       * and liveDef BitSet fields to represent the appropriate virtual registers
86       * that are locally defined to each block. It works internally with the
87       * cfg's basicBlock structure.
88       */
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     /**
108      * Iterate through a list of basic blocks in reverse order, and sets their
109      * lliveIn and liveOut bit sets to reflect global use-def information. It
110      * works internally with the cfg's basicBlock structure.
111      */
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         // note: we only check for changes in liveOut.
120         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