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