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(mf, 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 SlotIndex Start, Stop; 95 tie(Start, Stop) = Indexes->getMBBRange(MBBNum); 96 97 // Use advanceTo only when possible. 98 if (PrevPos != Start) { 99 if (!PrevPos.isValid() || Start < PrevPos) 100 for (unsigned i = 0, e = Iters.size(); i != e; ++i) 101 Iters[i].find(Start); 102 else 103 for (unsigned i = 0, e = Iters.size(); i != e; ++i) 104 Iters[i].advanceTo(Start); 105 PrevPos = Start; 106 } 107 108 MachineFunction::const_iterator MFI = MF->getBlockNumbered(MBBNum); 109 BlockInterference *BI = &Blocks[MBBNum]; 110 for (;;) { 111 BI->Tag = Tag; 112 BI->First = BI->Last = SlotIndex(); 113 114 // Check for first interference. 115 for (unsigned i = 0, e = Iters.size(); i != e; ++i) { 116 Iter &I = Iters[i]; 117 if (!I.valid()) 118 continue; 119 SlotIndex StartI = I.start(); 120 if (StartI >= Stop) 121 continue; 122 if (!BI->First.isValid() || StartI < BI->First) 123 BI->First = StartI; 124 } 125 126 PrevPos = Stop; 127 if (BI->First.isValid()) 128 break; 129 130 // No interference in this block? Go ahead and precompute the next block. 131 if (++MFI == MF->end()) 132 return; 133 MBBNum = MFI->getNumber(); 134 BI = &Blocks[MBBNum]; 135 if (BI->Tag == Tag) 136 return; 137 tie(Start, Stop) = Indexes->getMBBRange(MBBNum); 138 } 139 140 // Check for last interference in block. 141 for (unsigned i = 0, e = Iters.size(); i != e; ++i) { 142 Iter &I = Iters[i]; 143 if (!I.valid() || I.start() >= Stop) 144 continue; 145 I.advanceTo(Stop); 146 bool Backup = !I.valid() || I.start() >= Stop; 147 if (Backup) 148 --I; 149 SlotIndex StopI = I.stop(); 150 if (!BI->Last.isValid() || StopI > BI->Last) 151 BI->Last = StopI; 152 if (Backup) 153 ++I; 154 } 155 } 156