lib/CodeGen/InterferenceCache.cpp

   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 }