1 //===-- InterferenceCache.h - Caching per-block interference ---*- C++ -*--===//
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/Target/TargetRegisterInfo.h"
17 
18 using namespace llvm;
19 
20 void InterferenceCache::init(MachineFunction *mf,
21                              LiveIntervalUnion *liuarray,
22                              SlotIndexes *indexes,
23                             const TargetRegisterInfo *tri) {
24   MF = mf;
25   LIUArray = liuarray;
26   TRI = tri;
27   PhysRegEntries.assign(TRI->getNumRegs(), 0);
28   for (unsigned i = 0; i != CacheEntries; ++i)
29     Entries[i].clear(indexes);
30 }
31 
32 InterferenceCache::Entry *InterferenceCache::get(unsigned PhysReg) {
33   unsigned E = PhysRegEntries[PhysReg];
34   if (E < CacheEntries && Entries[E].getPhysReg() == PhysReg) {
35     if (!Entries[E].valid(LIUArray, TRI))
36       Entries[E].revalidate();
37     return &Entries[E];
38   }
39   // No valid entry exists, pick the next round-robin entry.
40   E = RoundRobin;
41   if (++RoundRobin == CacheEntries)
42     RoundRobin = 0;
43   Entries[E].reset(PhysReg, LIUArray, TRI, MF);
44   PhysRegEntries[PhysReg] = E;
45   return &Entries[E];
46 }
47 
48 /// revalidate - LIU contents have changed, update tags.
49 void InterferenceCache::Entry::revalidate() {
50   // Invalidate all block entries.
51   ++Tag;
52   // Invalidate all iterators.
53   PrevPos = SlotIndex();
54   for (unsigned i = 0, e = Aliases.size(); i != e; ++i)
55     Aliases[i].second = Aliases[i].first->getTag();
56 }
57 
58 void InterferenceCache::Entry::reset(unsigned physReg,
59                                      LiveIntervalUnion *LIUArray,
60                                      const TargetRegisterInfo *TRI,
61                                      const MachineFunction *MF) {
62   // LIU's changed, invalidate cache.
63   ++Tag;
64   PhysReg = physReg;
65   Blocks.resize(MF->getNumBlockIDs());
66   Aliases.clear();
67   for (const unsigned *AS = TRI->getOverlaps(PhysReg); *AS; ++AS) {
68     LiveIntervalUnion *LIU = LIUArray + *AS;
69     Aliases.push_back(std::make_pair(LIU, LIU->getTag()));
70   }
71 
72   // Reset iterators.
73   PrevPos = SlotIndex();
74   unsigned e = Aliases.size();
75   Iters.resize(e);
76   for (unsigned i = 0; i != e; ++i)
77     Iters[i].setMap(Aliases[i].first->getMap());
78 }
79 
80 bool InterferenceCache::Entry::valid(LiveIntervalUnion *LIUArray,
81                                      const TargetRegisterInfo *TRI) {
82   unsigned i = 0, e = Aliases.size();
83   for (const unsigned *AS = TRI->getOverlaps(PhysReg); *AS; ++AS, ++i) {
84     LiveIntervalUnion *LIU = LIUArray + *AS;
85     if (i == e ||  Aliases[i].first != LIU)
86       return false;
87     if (LIU->changedSince(Aliases[i].second))
88       return false;
89   }
90   return i == e;
91 }
92 
93 void InterferenceCache::Entry::update(unsigned MBBNum) {
94   BlockInterference *BI = &Blocks[MBBNum];
95   BI->Tag = Tag;
96   BI->First = BI->Last = SlotIndex();
97 
98   SlotIndex Start, Stop;
99   tie(Start, Stop) = Indexes->getMBBRange(MBBNum);
100 
101   // Use advanceTo only when possible.
102   if (PrevPos != Start) {
103     if (!PrevPos.isValid() || Start < PrevPos)
104       for (unsigned i = 0, e = Iters.size(); i != e; ++i)
105         Iters[i].find(Start);
106     else
107       for (unsigned i = 0, e = Iters.size(); i != e; ++i)
108         Iters[i].advanceTo(Start);
109     PrevPos = Start;
110   }
111 
112   // Check for first interference.
113   for (unsigned i = 0, e = Iters.size(); i != e; ++i) {
114     Iter &I = Iters[i];
115     if (!I.valid())
116       continue;
117     SlotIndex StartI = I.start();
118     if (StartI >= Stop)
119       continue;
120     if (!BI->First.isValid() || StartI < BI->First)
121       BI->First = StartI;
122   }
123 
124   // No interference in block.
125   if (!BI->First.isValid())
126     return;
127 
128   // Check for last interference.
129   for (unsigned i = 0, e = Iters.size(); i != e; ++i) {
130     Iter &I = Iters[i];
131     if (!I.valid() || I.start() >= Stop)
132       continue;
133     I.advanceTo(Stop);
134     bool Backup = !I.valid() || I.start() >= Stop;
135     if (Backup)
136       --I;
137     SlotIndex StopI = I.stop();
138     if (!BI->Last.isValid() || StopI > BI->Last)
139       BI->Last = StopI;
140     if (Backup)
141       ++I;
142   }
143   PrevPos = Stop;
144 }
145