Go to the documentation of this file.
36 #define DEBUG_TYPE "regalloc"
62 void LiveRangeCalc::updateFromLiveIns() {
64 for (
const LiveInBlock &
I : LiveIn) {
68 assert(
I.Value &&
"No live-in value found");
79 Map[
MBB] = LiveOutPair(
I.Value,
nullptr);
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];
149 const LiveOutPair &LOB = Map[&
B];
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);
175 if (UndefOnEntry[
N] || LR.
isUndefIn(Undefs, Begin, End)) {
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;
327 void LiveRangeCalc::updateSSA() {
328 assert(Indexes &&
"Missing SlotIndexes");
329 assert(DomTree &&
"Missing dominator tree");
337 for (LiveInBlock &
I : LiveIn) {
344 LiveOutPair IDomValue;
348 bool needPHI = !IDom || !Seen.
test(IDom->
getBlock()->getNumber());
357 if (IDomValue.first && IDomValue.first != &
UndefVNI &&
359 Map[IDom->
getBlock()].second = IDomValue.second =
364 LiveOutPair &
Value = Map[Pred];
365 if (!
Value.first ||
Value.first == IDomValue.first)
390 LiveOutPair &LOP = Map[
MBB];
395 assert(Alloc &&
"Need VNInfo allocator to create PHI-defs");
405 if (
I.Kill.isValid()) {
407 LR.
addSegment(LiveInterval::Segment(Start,
I.Kill, VNI));
410 LR.
addSegment(LiveInterval::Segment(Start, End, VNI));
411 LOP = LiveOutPair(VNI, Node);
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());
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
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...
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
void clear()
clear - Removes all bits from the bitvector.
size_type size() const
Determine the number of elements in the SetVector.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
const TargetRegisterInfo * getTargetRegisterInfo() const
This represents a simple continuous liveness interval for a value.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
static VNInfo UndefVNI(0xbad, SlotIndex())
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
void calculateValues()
calculateValues - Calculate the value that will be live-in to each block added with addLiveInBlock.
unsigned const TargetRegisterInfo * TRI
bool empty() const
empty - Check if the array is empty.
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
iterator begin()
Get an iterator to the beginning of the SetVector.
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Helper class for performant LiveRange bulk updates.
void resetLiveOutMap()
Reset Map and Seen fields.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
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.
void setDest(LiveRange *lr)
Select a different destination live range.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
SlotIndex - An opaque wrapper around machine indexes.
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Representation of each machine instruction.
void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill=SlotIndex())
addLiveInBlock - Add a block with an unknown live-in value.
This class represents the liveness of a register, stack slot, etc.
Allocate memory in an ever growing pool, as if by bump-pointer.
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StandardInstrumentations SI(Debug, VerifyEach)
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
iterator_range< pred_iterator > predecessors()
bool insert(const value_type &X)
Insert a new element into the SetVector.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Base class for the actual dominator tree node.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
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...
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
bool test(unsigned Idx) const
Segments::iterator iterator
void add(LiveRange::Segment)
Add a segment to LR and coalesce when possible, just like LR.addSegment().
VNInfo - Value Number Information.
iterator end()
Get an iterator to the end of the SetVector.
llvm::DenseMapBase< DenseMap< LiveRange *, std::pair< BitVector, BitVector >, DenseMapInfo< LiveRange * >, llvm::detail::DenseMapPair< LiveRange *, std::pair< BitVector, BitVector > > >, LiveRange *, std::pair< BitVector, BitVector >, DenseMapInfo< LiveRange * >, llvm::detail::DenseMapPair< LiveRange *, std::pair< BitVector, BitVector > > >::iterator DenseMapIterator< LiveRange *, std::pair< BitVector, BitVector >, DenseMapInfo< LiveRange * >, llvm::detail::DenseMapPair< LiveRange *, std::pair< BitVector, BitVector > > > iterator
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 setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)
setLiveOutValue - Indicate that VNI is live out from MBB.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
A vector that has set insertion semantics.
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.
bool isUndefIn(ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const
Returns true if there is an explicit "undef" between Begin End.
LLVM Value Representation.
void resize(typename StorageT::size_type s)
A Use represents the edge between a Value definition and its users.