InterferenceCache.cpp revision 5907d863659eb972ebb2afe07bc863a4c616f0ef 
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
18using namespace llvm;
19
20void 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
32InterferenceCache::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.
49void 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
58void 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
80bool 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
93void 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.isValid() || Start < PrevPos)
103    for (unsigned i = 0, e = Iters.size(); i != e; ++i)
104      Iters[i].find(Start);
105  else
106    for (unsigned i = 0, e = Iters.size(); i != e; ++i)
107      Iters[i].advanceTo(Start);
108  PrevPos = Start;
109
110  // Check for first interference.
111  for (unsigned i = 0, e = Iters.size(); i != e; ++i) {
112    Iter &I = Iters[i];
113    if (!I.valid())
114      continue;
115    SlotIndex StartI = I.start();
116    if (StartI >= Stop)
117      continue;
118    if (!BI->First.isValid() || StartI < BI->First)
119      BI->First = StartI;
120  }
121
122  // No interference in block.
123  if (!BI->First.isValid())
124    return;
125
126  // Check for last interference.
127  for (unsigned i = 0, e = Iters.size(); i != e; ++i) {
128    Iter &I = Iters[i];
129    if (!I.valid() || I.start() >= Stop)
130      continue;
131    I.advanceTo(Stop);
132    if (!I.valid() || I.start() >= Stop)
133      --I;
134    SlotIndex StopI = I.stop();
135    if (!BI->Last.isValid() || StopI > BI->Last)
136      BI->Last = StopI;
137  }
138  PrevPos = Stop;
139}
140