36#define DEBUG_TYPE "regalloc"
62void LiveRangeCalc::updateFromLiveIns() {
64 for (
const LiveInBlock &
I : LiveIn) {
68 assert(
I.Value &&
"No live-in value found");
82 Updater.
add(Start,
End,
I.Value);
89 assert(
Use.isValid() &&
"Invalid SlotIndex");
90 assert(Indexes &&
"Missing SlotIndexes");
91 assert(DomTree &&
"Missing dominator tree");
94 assert(UseMBB &&
"No MBB at Use");
98 if (EP.first !=
nullptr || EP.second)
105 if (findReachingDefs(LR, *UseMBB,
Use, PhysReg, Undefs))
116 assert(Indexes &&
"Missing SlotIndexes");
117 assert(DomTree &&
"Missing dominator tree");
128 if (UndefOnEntry[BN])
133 DefOnEntry[S->getNumber()] =
true;
134 DefOnEntry[BN] =
true;
142 WorkList.
insert(
P->getNumber());
144 for (
unsigned i = 0; i != WorkList.
size(); ++i) {
146 unsigned N = WorkList[i];
150 if (LOB.first !=
nullptr && LOB.first != &
UndefVNI)
151 return MarkDefined(
B);
160 if (UB != LR.
begin()) {
162 if (Seg.
end > Begin) {
169 return MarkDefined(
B);
176 UndefOnEntry[
N] =
true;
180 return MarkDefined(
B);
184 WorkList.
insert(
P->getNumber());
187 UndefOnEntry[BN] =
true;
200 bool UniqueVNI =
true;
203 bool FoundUndef =
false;
206 for (
unsigned i = 0; i != WorkList.
size(); ++i) {
213 <<
" does not have a corresponding definition on every path:\n";
225 <<
", but is missing from the live-in list.\n";
233 if (Seen.
test(Pred->getNumber())) {
234 if (
VNInfo *VNI = Map[Pred].first) {
235 if (TheVNI && TheVNI != VNI)
249 FoundUndef |= EP.second;
252 if (TheVNI && TheVNI != VNI)
256 if (VNI || EP.second)
261 WorkList.push_back(Pred->getNumber());
269 FoundUndef |= (TheVNI ==
nullptr || TheVNI == &
UndefVNI);
270 if (!Undefs.
empty() && FoundUndef)
275 if (WorkList.
size() > 4)
282 for (
unsigned BN : WorkList) {
286 if (BN == UseMBBNum &&
Use.isValid())
290 Updater.
add(Start,
End, TheVNI);
298 std::tie(Entry, DidInsert) = EntryInfos.
insert(
303 Entry->second.first.resize(
N);
304 Entry->second.second.resize(
N);
306 BitVector &DefOnEntry = Entry->second.first;
307 BitVector &UndefOnEntry = Entry->second.second;
311 LiveIn.reserve(WorkList.size());
312 for (
unsigned BN : WorkList) {
314 if (!Undefs.
empty() &&
315 !isDefOnEntry(LR, Undefs, *
MBB, DefOnEntry, UndefOnEntry))
319 LiveIn.back().Kill =
Use;
327void LiveRangeCalc::updateSSA() {
328 assert(Indexes &&
"Missing SlotIndexes");
329 assert(DomTree &&
"Missing dominator tree");
337 for (LiveInBlock &
I : LiveIn) {
348 bool needPHI = !IDom || !Seen.
test(IDom->
getBlock()->getNumber());
357 if (IDomValue.first && IDomValue.first != &
UndefVNI &&
359 Map[IDom->
getBlock()].second = IDomValue.second =
365 if (!
Value.first ||
Value.first == IDomValue.first)
395 assert(Alloc &&
"Need VNInfo allocator to create PHI-defs");
405 if (
I.Kill.isValid()) {
413 }
else if (IDomValue.first && IDomValue.first != &
UndefVNI) {
415 I.Value = IDomValue.first;
418 if (
I.Kill.isValid())
423 if (LOP.first == IDomValue.first)
442 for (
unsigned i = 0; i != PredQueue.
size(); ++i) {
443 unsigned BN = PredQueue[i];
448 PredQueue.
insert(
P->getNumber());
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static VNInfo UndefVNI(0xbad, SlotIndex())
static VNInfo UndefVNI(0xbad, SlotIndex())
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool empty() const
empty - Check if the array is empty.
bool test(unsigned Idx) const
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
void clear()
clear - Removes all bits from the bitvector.
Allocate memory in an ever growing pool, as if by bump-pointer.
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Base class for the actual dominator tree node.
void resize(typename StorageT::size_type s)
static LLVM_ATTRIBUTE_UNUSED bool isJointlyDominated(const MachineBasicBlock *MBB, ArrayRef< SlotIndex > Defs, const SlotIndexes &Indexes)
A diagnostic function to check if the end of the block MBB is jointly dominated by the blocks corresp...
void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill=SlotIndex())
addLiveInBlock - Add a block with an unknown live-in value.
void resetLiveOutMap()
Reset Map and Seen fields.
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
void calculateValues()
calculateValues - Calculate the value that will be live-in to each block added with addLiveInBlock.
void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)
setLiveOutValue - Indicate that VNI is live out from MBB.
Helper class for performant LiveRange bulk updates.
void setDest(LiveRange *lr)
Select a different destination live range.
void add(LiveRange::Segment)
Add a segment to LR and coalesce when possible, just like LR.addSegment().
This class represents the liveness of a register, stack slot, etc.
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
bool isUndefIn(ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const
Returns true if there is an explicit "undef" between Begin End.
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< pred_iterator > predecessors()
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
bool verify(Pass *p=nullptr, const char *Banner=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use.
Representation of each machine instruction.
const TargetRegisterInfo * getTargetRegisterInfo() const
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
iterator begin()
Get an iterator to the beginning of the SetVector.
iterator end()
Get an iterator to the end of the SetVector.
SlotIndex - An opaque wrapper around machine indexes.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A Use represents the edge between a Value definition and its users.
VNInfo - Value Number Information.
LLVM Value Representation.
This is an optimization pass for GlobalISel generic memory operations.
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
This represents a simple continuous liveness interval for a value.