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.LinkedList;
7   import java.util.Queue;
8   
9   import static jminusminus.NPhysicalRegister.*;
10  
11  /**
12   * Implements a naive register allocation method. Each interval is considered live for the entire
13   * cfg. Intervals are assigned physical registers on a first come basis. When we run out of
14   * registers, we reuse the ones already assigned and spill.
15   */
16  public class NNaiveRegisterAllocator extends NRegisterAllocator {
17      /**
18       * Constructs an NNaiveRegisterAllocator object.
19       *
20       * @param cfg an instance of a control flow graph.
21       */
22      public NNaiveRegisterAllocator(NControlFlowGraph cfg) {
23          super(cfg);
24      }
25  
26      /**
27       * {@inheritDoc}
28       */
29      public void allocation() {
30          // In this allocation scheme, each interval just has a single range spanning the entire cfg.
31          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          // Allocate registers.
40          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                      // Pull out (from a queue) a register that's already assigned to another
46                      // interval and re-assign it to this interval. But then we have a spill
47                      // situation, so create an offset for the spill.
48                      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                      // Allocate free register to interval.
62                      NPhysicalRegister pRegister = regInfo[T0 + j++];
63                      interval.pRegister = pRegister;
64                      cfg.pRegisters.add(pRegister);
65                  }
66                  assigned.add(interval);
67              }
68          }
69  
70          // Make sure that inputs of LIR instructions are not all assigned the same register.
71          // Also, handle spills (ie, generate loads and stores where needed).
72          for (int i = 1; i < cfg.basicBlocks.size(); i++) {
73              // We ignore block B0.
74              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                  // Loads.
91                  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                 // Stores.
101                 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