InterferenceCache.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338 
1//===-- InterferenceCache.cpp - Caching per-block interference ---------*--===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// InterferenceCache remembers per-block interference in LiveIntervalUnions.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "regalloc"
15#include "InterferenceCache.h"
16#include "llvm/CodeGen/LiveIntervalAnalysis.h"
17#include "llvm/Support/ErrorHandling.h"
18#include "llvm/Target/TargetRegisterInfo.h"
19
20using namespace llvm;
21
22// Static member used for null interference cursors.
23InterferenceCache::BlockInterference InterferenceCache::Cursor::NoInterference;
24
25// Initializes PhysRegEntries (instead of a SmallVector, PhysRegEntries is a
26// buffer of size NumPhysRegs to speed up alloc/clear for targets with large
27// reg files). Calloced memory is used for good form, and quites tools like
28// Valgrind too, but zero initialized memory is not required by the algorithm:
29// this is because PhysRegEntries works like a SparseSet and its entries are
30// only valid when there is a corresponding CacheEntries assignment. There is
31// also support for when pass managers are reused for targets with different
32// numbers of PhysRegs: in this case PhysRegEntries is freed and reinitialized.
33void InterferenceCache::reinitPhysRegEntries() {
34  if (PhysRegEntriesCount == TRI->getNumRegs()) return;
35  free(PhysRegEntries);
36  PhysRegEntriesCount = TRI->getNumRegs();
37  PhysRegEntries = (unsigned char*)
38    calloc(PhysRegEntriesCount, sizeof(unsigned char));
39}
40
41void InterferenceCache::init(MachineFunction *mf,
42                             LiveIntervalUnion *liuarray,
43                             SlotIndexes *indexes,
44                             LiveIntervals *lis,
45                             const TargetRegisterInfo *tri) {
46  MF = mf;
47  LIUArray = liuarray;
48  TRI = tri;
49  reinitPhysRegEntries();
50  for (unsigned i = 0; i != CacheEntries; ++i)
51    Entries[i].clear(mf, indexes, lis);
52}
53
54InterferenceCache::Entry *InterferenceCache::get(unsigned PhysReg) {
55  unsigned E = PhysRegEntries[PhysReg];
56  if (E < CacheEntries && Entries[E].getPhysReg() == PhysReg) {
57    if (!Entries[E].valid(LIUArray, TRI))
58      Entries[E].revalidate(LIUArray, TRI);
59    return &Entries[E];
60  }
61  // No valid entry exists, pick the next round-robin entry.
62  E = RoundRobin;
63  if (++RoundRobin == CacheEntries)
64    RoundRobin = 0;
65  for (unsigned i = 0; i != CacheEntries; ++i) {
66    // Skip entries that are in use.
67    if (Entries[E].hasRefs()) {
68      if (++E == CacheEntries)
69        E = 0;
70      continue;
71    }
72    Entries[E].reset(PhysReg, LIUArray, TRI, MF);
73    PhysRegEntries[PhysReg] = E;
74    return &Entries[E];
75  }
76  llvm_unreachable("Ran out of interference cache entries.");
77}
78
79/// revalidate - LIU contents have changed, update tags.
80void InterferenceCache::Entry::revalidate(LiveIntervalUnion *LIUArray,
81                                          const TargetRegisterInfo *TRI) {
82  // Invalidate all block entries.
83  ++Tag;
84  // Invalidate all iterators.
85  PrevPos = SlotIndex();
86  unsigned i = 0;
87  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units, ++i)
88    RegUnits[i].VirtTag = LIUArray[*Units].getTag();
89}
90
91void InterferenceCache::Entry::reset(unsigned physReg,
92                                     LiveIntervalUnion *LIUArray,
93                                     const TargetRegisterInfo *TRI,
94                                     const MachineFunction *MF) {
95  assert(!hasRefs() && "Cannot reset cache entry with references");
96  // LIU's changed, invalidate cache.
97  ++Tag;
98  PhysReg = physReg;
99  Blocks.resize(MF->getNumBlockIDs());
100
101  // Reset iterators.
102  PrevPos = SlotIndex();
103  RegUnits.clear();
104  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
105    RegUnits.push_back(LIUArray[*Units]);
106    RegUnits.back().Fixed = &LIS->getRegUnit(*Units);
107  }
108}
109
110bool InterferenceCache::Entry::valid(LiveIntervalUnion *LIUArray,
111                                     const TargetRegisterInfo *TRI) {
112  unsigned i = 0, e = RegUnits.size();
113  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units, ++i) {
114    if (i == e)
115      return false;
116    if (LIUArray[*Units].changedSince(RegUnits[i].VirtTag))
117      return false;
118  }
119  return i == e;
120}
121
122void InterferenceCache::Entry::update(unsigned MBBNum) {
123  SlotIndex Start, Stop;
124  std::tie(Start, Stop) = Indexes->getMBBRange(MBBNum);
125
126  // Use advanceTo only when possible.
127  if (PrevPos != Start) {
128    if (!PrevPos.isValid() || Start < PrevPos) {
129      for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
130        RegUnitInfo &RUI = RegUnits[i];
131        RUI.VirtI.find(Start);
132        RUI.FixedI = RUI.Fixed->find(Start);
133      }
134    } else {
135      for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
136        RegUnitInfo &RUI = RegUnits[i];
137        RUI.VirtI.advanceTo(Start);
138        if (RUI.FixedI != RUI.Fixed->end())
139          RUI.FixedI = RUI.Fixed->advanceTo(RUI.FixedI, Start);
140      }
141    }
142    PrevPos = Start;
143  }
144
145  MachineFunction::const_iterator MFI = MF->getBlockNumbered(MBBNum);
146  BlockInterference *BI = &Blocks[MBBNum];
147  ArrayRef<SlotIndex> RegMaskSlots;
148  ArrayRef<const uint32_t*> RegMaskBits;
149  for (;;) {
150    BI->Tag = Tag;
151    BI->First = BI->Last = SlotIndex();
152
153    // Check for first interference from virtregs.
154    for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
155      LiveIntervalUnion::SegmentIter &I = RegUnits[i].VirtI;
156      if (!I.valid())
157        continue;
158      SlotIndex StartI = I.start();
159      if (StartI >= Stop)
160        continue;
161      if (!BI->First.isValid() || StartI < BI->First)
162        BI->First = StartI;
163    }
164
165    // Same thing for fixed interference.
166    for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
167      LiveInterval::const_iterator I = RegUnits[i].FixedI;
168      LiveInterval::const_iterator E = RegUnits[i].Fixed->end();
169      if (I == E)
170        continue;
171      SlotIndex StartI = I->start;
172      if (StartI >= Stop)
173        continue;
174      if (!BI->First.isValid() || StartI < BI->First)
175        BI->First = StartI;
176    }
177
178    // Also check for register mask interference.
179    RegMaskSlots = LIS->getRegMaskSlotsInBlock(MBBNum);
180    RegMaskBits = LIS->getRegMaskBitsInBlock(MBBNum);
181    SlotIndex Limit = BI->First.isValid() ? BI->First : Stop;
182    for (unsigned i = 0, e = RegMaskSlots.size();
183         i != e && RegMaskSlots[i] < Limit; ++i)
184      if (MachineOperand::clobbersPhysReg(RegMaskBits[i], PhysReg)) {
185        // Register mask i clobbers PhysReg before the LIU interference.
186        BI->First = RegMaskSlots[i];
187        break;
188      }
189
190    PrevPos = Stop;
191    if (BI->First.isValid())
192      break;
193
194    // No interference in this block? Go ahead and precompute the next block.
195    if (++MFI == MF->end())
196      return;
197    MBBNum = MFI->getNumber();
198    BI = &Blocks[MBBNum];
199    if (BI->Tag == Tag)
200      return;
201    std::tie(Start, Stop) = Indexes->getMBBRange(MBBNum);
202  }
203
204  // Check for last interference in block.
205  for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
206    LiveIntervalUnion::SegmentIter &I = RegUnits[i].VirtI;
207    if (!I.valid() || I.start() >= Stop)
208      continue;
209    I.advanceTo(Stop);
210    bool Backup = !I.valid() || I.start() >= Stop;
211    if (Backup)
212      --I;
213    SlotIndex StopI = I.stop();
214    if (!BI->Last.isValid() || StopI > BI->Last)
215      BI->Last = StopI;
216    if (Backup)
217      ++I;
218  }
219
220  // Fixed interference.
221  for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
222    LiveInterval::iterator &I = RegUnits[i].FixedI;
223    LiveRange *LR = RegUnits[i].Fixed;
224    if (I == LR->end() || I->start >= Stop)
225      continue;
226    I = LR->advanceTo(I, Stop);
227    bool Backup = I == LR->end() || I->start >= Stop;
228    if (Backup)
229      --I;
230    SlotIndex StopI = I->end;
231    if (!BI->Last.isValid() || StopI > BI->Last)
232      BI->Last = StopI;
233    if (Backup)
234      ++I;
235  }
236
237  // Also check for register mask interference.
238  SlotIndex Limit = BI->Last.isValid() ? BI->Last : Start;
239  for (unsigned i = RegMaskSlots.size();
240       i && RegMaskSlots[i-1].getDeadSlot() > Limit; --i)
241    if (MachineOperand::clobbersPhysReg(RegMaskBits[i-1], PhysReg)) {
242      // Register mask i-1 clobbers PhysReg after the LIU interference.
243      // Model the regmask clobber as a dead def.
244      BI->Last = RegMaskSlots[i-1].getDeadSlot();
245      break;
246    }
247}
248