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(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 }