blob: 2e613ae09593bea3d4a76627344c42635fafbcbb [file] [log] [blame]
Jakob Stoklund Olesen5907d862011-04-02 06:03:35 +00001//===-- 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#ifndef LLVM_CODEGEN_INTERFERENCECACHE
15#define LLVM_CODEGEN_INTERFERENCECACHE
16
17#include "LiveIntervalUnion.h"
18
19namespace llvm {
20
21class InterferenceCache {
22 const TargetRegisterInfo *TRI;
23 LiveIntervalUnion *LIUArray;
24 SlotIndexes *Indexes;
25 MachineFunction *MF;
26
27 /// BlockInterference - information about the interference in a single basic
28 /// block.
29 struct BlockInterference {
30 BlockInterference() : Tag(0) {}
31 unsigned Tag;
32 SlotIndex First;
33 SlotIndex Last;
34 };
35
36 /// Entry - A cache entry containing interference information for all aliases
37 /// of PhysReg in all basic blocks.
38 class Entry {
39 /// PhysReg - The register currently represented.
40 unsigned PhysReg;
41
42 /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
43 /// change.
44 unsigned Tag;
45
46 /// Indexes - Mapping block numbers to SlotIndex ranges.
47 SlotIndexes *Indexes;
48
49 /// PrevPos - The previous position the iterators were moved to.
50 SlotIndex PrevPos;
51
52 /// AliasTags - A LiveIntervalUnion pointer and tag for each alias of
53 /// PhysReg.
54 SmallVector<std::pair<LiveIntervalUnion*, unsigned>, 8> Aliases;
55
56 typedef LiveIntervalUnion::SegmentIter Iter;
57
58 /// Iters - an iterator for each alias
59 SmallVector<Iter, 8> Iters;
60
61 /// Blocks - Interference for each block in the function.
62 SmallVector<BlockInterference, 8> Blocks;
63
64 /// update - Recompute Blocks[MBBNum]
65 void update(unsigned MBBNum);
66
67 public:
68 Entry() : PhysReg(0), Tag(0), Indexes(0) {}
69
70 void clear(SlotIndexes *indexes) {
71 PhysReg = 0;
72 Indexes = indexes;
73 }
74
75 unsigned getPhysReg() const { return PhysReg; }
76
77 void revalidate();
78
79 /// valid - Return true if this is a valid entry for physReg.
80 bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
81
82 /// reset - Initialize entry to represent physReg's aliases.
83 void reset(unsigned physReg,
84 LiveIntervalUnion *LIUArray,
85 const TargetRegisterInfo *TRI,
86 const MachineFunction *MF);
87
88 /// get - Return an up to date BlockInterference.
89 BlockInterference *get(unsigned MBBNum) {
90 if (Blocks[MBBNum].Tag != Tag)
91 update(MBBNum);
92 return &Blocks[MBBNum];
93 }
94 };
95
96 // We don't keep a cache entry for every physical register, that would use too
97 // much memory. Instead, a fixed number of cache entries are used in a round-
98 // robin manner.
99 enum { CacheEntries = 32 };
100
101 // Point to an entry for each physreg. The entry pointed to may not be up to
102 // date, and it may have been reused for a different physreg.
103 SmallVector<unsigned char, 2> PhysRegEntries;
104
105 // Next round-robin entry to be picked.
106 unsigned RoundRobin;
107
108 // The actual cache entries.
109 Entry Entries[CacheEntries];
110
111 // get - Get a valid entry for PhysReg.
112 Entry *get(unsigned PhysReg);
113
114public:
115 InterferenceCache() : TRI(0), LIUArray(0), Indexes(0), MF(0), RoundRobin(0) {}
116
117 /// init - Prepare cache for a new function.
118 void init(MachineFunction*, LiveIntervalUnion*, SlotIndexes*,
119 const TargetRegisterInfo *);
120
121 /// Cursor - The primary query interface for the block interference cache.
122 class Cursor {
123 Entry *CacheEntry;
124 BlockInterference *Current;
125 public:
126 /// Cursor - Create a cursor for the interference allocated to PhysReg and
127 /// all its aliases.
128 Cursor(InterferenceCache &Cache, unsigned PhysReg)
129 : CacheEntry(Cache.get(PhysReg)), Current(0) {}
130
131 /// moveTo - Move cursor to basic block MBBNum.
132 void moveToBlock(unsigned MBBNum) {
133 Current = CacheEntry->get(MBBNum);
134 }
135
136 /// hasInterference - Return true if the current block has any interference.
137 bool hasInterference() {
138 return Current->First.isValid();
139 }
140
141 /// first - Return the starting index of the first interfering range in the
142 /// current block.
143 SlotIndex first() {
144 return Current->First;
145 }
146
147 /// last - Return the ending index of the last interfering range in the
148 /// current block.
149 SlotIndex last() {
150 return Current->Last;
151 }
152 };
153
154 friend class Cursor;
155};
156
157} // namespace llvm
158
159#endif