244 lines · c
1//===- InterferenceCache.h - Caching per-block interference ----*- C++ -*--===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// InterferenceCache remembers per-block interference from LiveIntervalUnions,10// fixed RegUnit interference, and register masks.11//12//===----------------------------------------------------------------------===//13 14#ifndef LLVM_LIB_CODEGEN_INTERFERENCECACHE_H15#define LLVM_LIB_CODEGEN_INTERFERENCECACHE_H16 17#include "llvm/ADT/SmallVector.h"18#include "llvm/CodeGen/LiveInterval.h"19#include "llvm/CodeGen/LiveIntervalUnion.h"20#include "llvm/CodeGen/SlotIndexes.h"21#include "llvm/Support/Compiler.h"22#include <cassert>23#include <cstddef>24#include <cstdlib>25 26namespace llvm {27 28class LiveIntervals;29class MachineFunction;30class TargetRegisterInfo;31 32class LLVM_LIBRARY_VISIBILITY InterferenceCache {33 /// BlockInterference - information about the interference in a single basic34 /// block.35 struct BlockInterference {36 unsigned Tag = 0;37 SlotIndex First;38 SlotIndex Last;39 40 BlockInterference() = default;41 };42 43 /// Entry - A cache entry containing interference information for all aliases44 /// of PhysReg in all basic blocks.45 class Entry {46 /// PhysReg - The register currently represented.47 MCRegister PhysReg = 0;48 49 /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions50 /// change.51 unsigned Tag = 0;52 53 /// RefCount - The total number of Cursor instances referring to this Entry.54 unsigned RefCount = 0;55 56 /// MF - The current function.57 MachineFunction *MF = nullptr;58 59 /// Indexes - Mapping block numbers to SlotIndex ranges.60 SlotIndexes *Indexes = nullptr;61 62 /// LIS - Used for accessing register mask interference maps.63 LiveIntervals *LIS = nullptr;64 65 /// PrevPos - The previous position the iterators were moved to.66 SlotIndex PrevPos;67 68 /// RegUnitInfo - Information tracked about each RegUnit in PhysReg.69 /// When PrevPos is set, the iterators are valid as if advanceTo(PrevPos)70 /// had just been called.71 struct RegUnitInfo {72 /// Iterator pointing into the LiveIntervalUnion containing virtual73 /// register interference.74 LiveIntervalUnion::SegmentIter VirtI;75 76 /// Tag of the LIU last time we looked.77 unsigned VirtTag;78 79 /// Fixed interference in RegUnit.80 LiveRange *Fixed = nullptr;81 82 /// Iterator pointing into the fixed RegUnit interference.83 LiveInterval::iterator FixedI;84 85 RegUnitInfo(LiveIntervalUnion &LIU) : VirtTag(LIU.getTag()) {86 VirtI.setMap(LIU.getMap());87 }88 };89 90 /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have91 /// more than 4 RegUnits.92 SmallVector<RegUnitInfo, 4> RegUnits;93 94 /// Blocks - Interference for each block in the function.95 SmallVector<BlockInterference, 8> Blocks;96 97 /// update - Recompute Blocks[MBBNum]98 void update(unsigned MBBNum);99 100 public:101 Entry() = default;102 103 void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {104 assert(!hasRefs() && "Cannot clear cache entry with references");105 PhysReg = MCRegister::NoRegister;106 MF = mf;107 Indexes = indexes;108 LIS = lis;109 }110 111 MCRegister getPhysReg() const { return PhysReg; }112 113 void addRef(int Delta) { RefCount += Delta; }114 115 bool hasRefs() const { return RefCount > 0; }116 117 void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);118 119 /// valid - Return true if this is a valid entry for physReg.120 bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);121 122 /// reset - Initialize entry to represent physReg's aliases.123 void reset(MCRegister physReg, LiveIntervalUnion *LIUArray,124 const TargetRegisterInfo *TRI, const MachineFunction *MF);125 126 /// get - Return an up to date BlockInterference.127 BlockInterference *get(unsigned MBBNum) {128 if (Blocks[MBBNum].Tag != Tag)129 update(MBBNum);130 return &Blocks[MBBNum];131 }132 };133 134 // We don't keep a cache entry for every physical register, that would use too135 // much memory. Instead, a fixed number of cache entries are used in a round-136 // robin manner.137 enum { CacheEntries = 32 };138 139 const TargetRegisterInfo *TRI = nullptr;140 LiveIntervalUnion *LIUArray = nullptr;141 MachineFunction *MF = nullptr;142 143 // Point to an entry for each physreg. The entry pointed to may not be up to144 // date, and it may have been reused for a different physreg.145 unsigned char* PhysRegEntries = nullptr;146 size_t PhysRegEntriesCount = 0;147 148 // Next round-robin entry to be picked.149 unsigned RoundRobin = 0;150 151 // The actual cache entries.152 Entry Entries[CacheEntries];153 154 // get - Get a valid entry for PhysReg.155 Entry *get(MCRegister PhysReg);156 157public:158 InterferenceCache() = default;159 InterferenceCache &operator=(const InterferenceCache &other) = delete;160 InterferenceCache(const InterferenceCache &other) = delete;161 ~InterferenceCache() {162 free(PhysRegEntries);163 }164 165 void reinitPhysRegEntries();166 167 /// init - Prepare cache for a new function.168 void init(MachineFunction *mf, LiveIntervalUnion *liuarray,169 SlotIndexes *indexes, LiveIntervals *lis,170 const TargetRegisterInfo *tri);171 172 /// getMaxCursors - Return the maximum number of concurrent cursors that can173 /// be supported.174 unsigned getMaxCursors() const { return CacheEntries; }175 176 /// Cursor - The primary query interface for the block interference cache.177 class Cursor {178 Entry *CacheEntry = nullptr;179 const BlockInterference *Current = nullptr;180 static const BlockInterference NoInterference;181 182 void setEntry(Entry *E) {183 Current = nullptr;184 // Update reference counts. Nothing happens when RefCount reaches 0, so185 // we don't have to check for E == CacheEntry etc.186 if (CacheEntry)187 CacheEntry->addRef(-1);188 CacheEntry = E;189 if (CacheEntry)190 CacheEntry->addRef(+1);191 }192 193 public:194 /// Cursor - Create a dangling cursor.195 Cursor() = default;196 197 Cursor(const Cursor &O) {198 setEntry(O.CacheEntry);199 }200 201 Cursor &operator=(const Cursor &O) {202 setEntry(O.CacheEntry);203 return *this;204 }205 206 ~Cursor() { setEntry(nullptr); }207 208 /// setPhysReg - Point this cursor to PhysReg's interference.209 void setPhysReg(InterferenceCache &Cache, MCRegister PhysReg) {210 // Release reference before getting a new one. That guarantees we can211 // actually have CacheEntries live cursors.212 setEntry(nullptr);213 if (PhysReg.isValid())214 setEntry(Cache.get(PhysReg));215 }216 217 /// moveTo - Move cursor to basic block MBBNum.218 void moveToBlock(unsigned MBBNum) {219 Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;220 }221 222 /// hasInterference - Return true if the current block has any interference.223 bool hasInterference() {224 return Current->First.isValid();225 }226 227 /// first - Return the starting index of the first interfering range in the228 /// current block.229 SlotIndex first() {230 return Current->First;231 }232 233 /// last - Return the ending index of the last interfering range in the234 /// current block.235 SlotIndex last() {236 return Current->Last;237 }238 };239};240 241} // end namespace llvm242 243#endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H244