X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FCodeGen%2FMachineBasicBlock.cpp;h=354bd3ef3e8b061ddfac0a420114161dc7eed682;hp=98359b198545cd5ab71aff46e62f9cf6c5c3b93e;hb=70477058aa03c697a654b708e41da95870358139;hpb=9656d2d2bc38f78a0be73b3bbba8c60d231e7a75 diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 98359b19854..354bd3ef3e8 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -24,6 +24,7 @@ #include "llvm/CodeGen/SlotIndexes.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/DataLayout.h" +#include "llvm/IR/ModuleSlotTracker.h" #include "llvm/MC/MCAsmInfo.h" #include "llvm/MC/MCContext.h" #include "llvm/Support/Debug.h" @@ -37,23 +38,22 @@ using namespace llvm; #define DEBUG_TYPE "codegen" -MachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb) - : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false), - AddressTaken(false), CachedMCSymbol(nullptr) { +MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B) + : BB(B), Number(-1), xParent(&MF) { Insts.Parent = this; } MachineBasicBlock::~MachineBasicBlock() { } -/// getSymbol - Return the MCSymbol for this basic block. -/// +/// Return the MCSymbol for this basic block. MCSymbol *MachineBasicBlock::getSymbol() const { if (!CachedMCSymbol) { const MachineFunction *MF = getParent(); MCContext &Ctx = MF->getContext(); const char *Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix(); - CachedMCSymbol = Ctx.GetOrCreateSymbol(Twine(Prefix) + "BB" + + assert(getNumber() >= 0 && "cannot get label for unreachable MBB"); + CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" + Twine(MF->getFunctionNumber()) + "_" + Twine(getNumber())); } @@ -67,9 +67,9 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineBasicBlock &MBB) { return OS; } -/// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the -/// parent pointer of the MBB, the MBB numbering, and any instructions in the -/// MBB to be on the right operand list for registers. +/// When an MBB is added to an MF, we need to update the parent pointer of the +/// MBB, the MBB numbering, and any instructions in the MBB to be on the right +/// operand list for registers. /// /// MBBs start out as #-1. When a MBB is added to a MachineFunction, it /// gets the next available unique MBB number. If it is removed from a @@ -90,10 +90,8 @@ void ilist_traits::removeNodeFromList(MachineBasicBlock *N) { N->Number = -1; } - -/// addNodeToList (MI) - When we add an instruction to a basic block -/// list, we update its parent pointer and add its operands from reg use/def -/// lists if appropriate. +/// When we add an instruction to a basic block list, we update its parent +/// pointer and add its operands from reg use/def lists if appropriate. void ilist_traits::addNodeToList(MachineInstr *N) { assert(!N->getParent() && "machine instruction already in a basic block"); N->setParent(Parent); @@ -104,9 +102,8 @@ void ilist_traits::addNodeToList(MachineInstr *N) { N->AddRegOperandsToUseLists(MF->getRegInfo()); } -/// removeNodeFromList (MI) - When we remove an instruction from a basic block -/// list, we update its parent pointer and remove its operands from reg use/def -/// lists if appropriate. +/// When we remove an instruction from a basic block list, we update its parent +/// pointer and remove its operands from reg use/def lists if appropriate. void ilist_traits::removeNodeFromList(MachineInstr *N) { assert(N->getParent() && "machine instruction not in a basic block"); @@ -117,23 +114,22 @@ void ilist_traits::removeNodeFromList(MachineInstr *N) { N->setParent(nullptr); } -/// transferNodesFromList (MI) - When moving a range of instructions from one -/// MBB list to another, we need to update the parent pointers and the use/def -/// lists. +/// When moving a range of instructions from one MBB list to another, we need to +/// update the parent pointers and the use/def lists. void ilist_traits:: -transferNodesFromList(ilist_traits &fromList, - ilist_iterator first, - ilist_iterator last) { - assert(Parent->getParent() == fromList.Parent->getParent() && +transferNodesFromList(ilist_traits &FromList, + ilist_iterator First, + ilist_iterator Last) { + assert(Parent->getParent() == FromList.Parent->getParent() && "MachineInstr parent mismatch!"); // Splice within the same MBB -> no change. - if (Parent == fromList.Parent) return; + if (Parent == FromList.Parent) return; // If splicing between two blocks within the same function, just update the // parent pointers. - for (; first != last; ++first) - first->setParent(Parent); + for (; First != Last; ++First) + First->setParent(Parent); } void ilist_traits::deleteNode(MachineInstr* MI) { @@ -171,9 +167,8 @@ MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() { return I; } -MachineBasicBlock::const_iterator -MachineBasicBlock::getFirstTerminator() const { - const_iterator B = begin(), E = end(), I = E; +MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() { + instr_iterator B = instr_begin(), E = instr_end(), I = E; while (I != B && ((--I)->isTerminator() || I->isDebugValue())) ; /*noop */ while (I != E && !I->isTerminator()) @@ -181,11 +176,10 @@ MachineBasicBlock::getFirstTerminator() const { return I; } -MachineBasicBlock::instr_iterator MachineBasicBlock::getFirstInstrTerminator() { - instr_iterator B = instr_begin(), E = instr_end(), I = E; - while (I != B && ((--I)->isTerminator() || I->isDebugValue())) - ; /*noop */ - while (I != E && !I->isTerminator()) +MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() { + // Skip over begin-of-block dbg_value instructions. + iterator I = begin(), E = end(); + while (I != E && I->isDebugValue()) ++I; return I; } @@ -204,31 +198,23 @@ MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() { return end(); } -MachineBasicBlock::const_iterator -MachineBasicBlock::getLastNonDebugInstr() const { - // Skip over end-of-block dbg_value instructions. - const_instr_iterator B = instr_begin(), I = instr_end(); - while (I != B) { - --I; - // Return instruction that starts a bundle. - if (I->isDebugValue() || I->isInsideBundle()) - continue; - return I; - } - // The block is all debug values. - return end(); -} - const MachineBasicBlock *MachineBasicBlock::getLandingPadSuccessor() const { // A block with a landing pad successor only has one other successor. if (succ_size() > 2) return nullptr; for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) - if ((*I)->isLandingPad()) + if ((*I)->isEHPad()) return *I; return nullptr; } +bool MachineBasicBlock::hasEHPadSuccessor() const { + for (const_succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I) + if ((*I)->isEHPad()) + return true; + return false; +} + #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void MachineBasicBlock::dump() const { print(dbgs()); @@ -250,7 +236,7 @@ std::string MachineBasicBlock::getFullName() const { if (getBasicBlock()) Name += getBasicBlock()->getName(); else - Name += (Twine("BB") + Twine(getNumber())).str(); + Name += ("BB" + Twine(getNumber())).str(); return Name; } @@ -261,6 +247,20 @@ void MachineBasicBlock::print(raw_ostream &OS, SlotIndexes *Indexes) const { << " is null\n"; return; } + const Function *F = MF->getFunction(); + const Module *M = F ? F->getParent() : nullptr; + ModuleSlotTracker MST(M); + print(OS, MST, Indexes); +} + +void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST, + SlotIndexes *Indexes) const { + const MachineFunction *MF = getParent(); + if (!MF) { + OS << "Can't print out MachineBasicBlock because parent MachineFunction" + << " is null\n"; + return; + } if (Indexes) OS << Indexes->getMBBStartIdx(this) << '\t'; @@ -270,10 +270,10 @@ void MachineBasicBlock::print(raw_ostream &OS, SlotIndexes *Indexes) const { const char *Comma = ""; if (const BasicBlock *LBB = getBasicBlock()) { OS << Comma << "derived from LLVM BB "; - LBB->printAsOperand(OS, /*PrintType=*/false); + LBB->printAsOperand(OS, /*PrintType=*/false, MST); Comma = ", "; } - if (isLandingPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; } + if (isEHPad()) { OS << Comma << "EH LANDING PAD"; Comma = ", "; } if (hasAddressTaken()) { OS << Comma << "ADDRESS TAKEN"; Comma = ", "; } if (Alignment) OS << Comma << "Align " << Alignment << " (" << (1u << Alignment) @@ -285,8 +285,11 @@ void MachineBasicBlock::print(raw_ostream &OS, SlotIndexes *Indexes) const { if (!livein_empty()) { if (Indexes) OS << '\t'; OS << " Live Ins:"; - for (livein_iterator I = livein_begin(),E = livein_end(); I != E; ++I) - OS << ' ' << PrintReg(*I, TRI); + for (const auto &LI : make_range(livein_begin(), livein_end())) { + OS << ' ' << PrintReg(LI.PhysReg, TRI); + if (LI.LaneMask != ~0u) + OS << ':' << PrintLaneMask(LI.LaneMask); + } OS << '\n'; } // Print the preds of this block according to the CFG. @@ -300,14 +303,14 @@ void MachineBasicBlock::print(raw_ostream &OS, SlotIndexes *Indexes) const { for (const_instr_iterator I = instr_begin(); I != instr_end(); ++I) { if (Indexes) { - if (Indexes->hasIndex(I)) - OS << Indexes->getInstructionIndex(I); + if (Indexes->hasIndex(&*I)) + OS << Indexes->getInstructionIndex(&*I); OS << '\t'; } OS << '\t'; if (I->isInsideBundle()) OS << " * "; - I->print(OS); + I->print(OS, MST); } // Print the successors of this block according to the CFG. @@ -323,28 +326,56 @@ void MachineBasicBlock::print(raw_ostream &OS, SlotIndexes *Indexes) const { } } -void MachineBasicBlock::printAsOperand(raw_ostream &OS, bool /*PrintType*/) const { +void MachineBasicBlock::printAsOperand(raw_ostream &OS, + bool /*PrintType*/) const { OS << "BB#" << getNumber(); } -void MachineBasicBlock::removeLiveIn(unsigned Reg) { - std::vector::iterator I = - std::find(LiveIns.begin(), LiveIns.end(), Reg); - if (I != LiveIns.end()) +void MachineBasicBlock::removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) { + LiveInVector::iterator I = std::find_if( + LiveIns.begin(), LiveIns.end(), + [Reg] (const RegisterMaskPair &LI) { return LI.PhysReg == Reg; }); + if (I == LiveIns.end()) + return; + + I->LaneMask &= ~LaneMask; + if (I->LaneMask == 0) LiveIns.erase(I); } -bool MachineBasicBlock::isLiveIn(unsigned Reg) const { - livein_iterator I = std::find(livein_begin(), livein_end(), Reg); - return I != livein_end(); +bool MachineBasicBlock::isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask) const { + livein_iterator I = std::find_if( + LiveIns.begin(), LiveIns.end(), + [Reg] (const RegisterMaskPair &LI) { return LI.PhysReg == Reg; }); + return I != livein_end() && (I->LaneMask & LaneMask) != 0; +} + +void MachineBasicBlock::sortUniqueLiveIns() { + std::sort(LiveIns.begin(), LiveIns.end(), + [](const RegisterMaskPair &LI0, const RegisterMaskPair &LI1) { + return LI0.PhysReg < LI1.PhysReg; + }); + // Liveins are sorted by physreg now we can merge their lanemasks. + LiveInVector::const_iterator I = LiveIns.begin(); + LiveInVector::const_iterator J; + LiveInVector::iterator Out = LiveIns.begin(); + for (; I != LiveIns.end(); ++Out, I = J) { + unsigned PhysReg = I->PhysReg; + LaneBitmask LaneMask = I->LaneMask; + for (J = std::next(I); J != LiveIns.end() && J->PhysReg == PhysReg; ++J) + LaneMask |= J->LaneMask; + Out->PhysReg = PhysReg; + Out->LaneMask = LaneMask; + } + LiveIns.erase(Out, LiveIns.end()); } unsigned -MachineBasicBlock::addLiveIn(unsigned PhysReg, const TargetRegisterClass *RC) { +MachineBasicBlock::addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC) { assert(getParent() && "MBB must be inserted in function"); assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) && "Expected physreg"); assert(RC && "Register class is required"); - assert((isLandingPad() || this == &getParent()->front()) && + assert((isEHPad() || this == &getParent()->front()) && "Only the entry block and landing pads can have physreg live ins"); bool LiveIn = isLiveIn(PhysReg); @@ -372,12 +403,11 @@ MachineBasicBlock::addLiveIn(unsigned PhysReg, const TargetRegisterClass *RC) { } void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) { - getParent()->splice(NewAfter, this); + getParent()->splice(NewAfter->getIterator(), getIterator()); } void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) { - MachineFunction::iterator BBI = NewBefore; - getParent()->splice(++BBI, this); + getParent()->splice(++NewBefore->getIterator(), getIterator()); } void MachineBasicBlock::updateTerminator() { @@ -387,7 +417,7 @@ void MachineBasicBlock::updateTerminator() { MachineBasicBlock *TBB = nullptr, *FBB = nullptr; SmallVector Cond; - DebugLoc dl; // FIXME: this is nowhere + DebugLoc DL; // FIXME: this is nowhere bool B = TII->AnalyzeBranch(*this, TBB, FBB, Cond); (void) B; assert(!B && "UpdateTerminators requires analyzable predecessors!"); @@ -402,7 +432,7 @@ void MachineBasicBlock::updateTerminator() { // its layout successor, insert a branch. First we have to locate the // only non-landing-pad successor, as that is the fallthrough block. for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) { - if ((*SI)->isLandingPad()) + if ((*SI)->isEHPad()) continue; assert(!TBB && "Found more than one non-landing-pad successor!"); TBB = *SI; @@ -416,7 +446,7 @@ void MachineBasicBlock::updateTerminator() { // Finally update the unconditional successor to be reached via a branch // if it would not be reached by fallthrough. if (!isLayoutSuccessor(TBB)) - TII->InsertBranch(*this, TBB, nullptr, Cond, dl); + TII->InsertBranch(*this, TBB, nullptr, Cond, DL); } } else { if (FBB) { @@ -427,10 +457,10 @@ void MachineBasicBlock::updateTerminator() { if (TII->ReverseBranchCondition(Cond)) return; TII->RemoveBranch(*this); - TII->InsertBranch(*this, FBB, nullptr, Cond, dl); + TII->InsertBranch(*this, FBB, nullptr, Cond, DL); } else if (isLayoutSuccessor(FBB)) { TII->RemoveBranch(*this); - TII->InsertBranch(*this, TBB, nullptr, Cond, dl); + TII->InsertBranch(*this, TBB, nullptr, Cond, DL); } } else { // Walk through the successors and find the successor which is not @@ -438,7 +468,7 @@ void MachineBasicBlock::updateTerminator() { // as the fallthrough successor. MachineBasicBlock *FallthroughBB = nullptr; for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) { - if ((*SI)->isLandingPad() || *SI == TBB) + if ((*SI)->isEHPad() || *SI == TBB) continue; assert(!FallthroughBB && "Found more than one fallthrough successor."); FallthroughBB = *SI; @@ -447,14 +477,14 @@ void MachineBasicBlock::updateTerminator() { // We fallthrough to the same basic block as the conditional jump // targets. Remove the conditional jump, leaving unconditional // fallthrough. - // FIXME: This does not seem like a reasonable pattern to support, but it - // has been seen in the wild coming out of degenerate ARM test cases. + // FIXME: This does not seem like a reasonable pattern to support, but + // it has been seen in the wild coming out of degenerate ARM test cases. TII->RemoveBranch(*this); // Finally update the unconditional successor to be reached via a branch // if it would not be reached by fallthrough. if (!isLayoutSuccessor(TBB)) - TII->InsertBranch(*this, TBB, nullptr, Cond, dl); + TII->InsertBranch(*this, TBB, nullptr, Cond, DL); return; } @@ -463,45 +493,60 @@ void MachineBasicBlock::updateTerminator() { if (TII->ReverseBranchCondition(Cond)) { // We can't reverse the condition, add an unconditional branch. Cond.clear(); - TII->InsertBranch(*this, FallthroughBB, nullptr, Cond, dl); + TII->InsertBranch(*this, FallthroughBB, nullptr, Cond, DL); return; } TII->RemoveBranch(*this); - TII->InsertBranch(*this, FallthroughBB, nullptr, Cond, dl); + TII->InsertBranch(*this, FallthroughBB, nullptr, Cond, DL); } else if (!isLayoutSuccessor(FallthroughBB)) { TII->RemoveBranch(*this); - TII->InsertBranch(*this, TBB, FallthroughBB, Cond, dl); + TII->InsertBranch(*this, TBB, FallthroughBB, Cond, DL); } } } } -void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ, uint32_t weight) { +void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, uint32_t Weight) { + // Weight list is either empty (if successor list isn't empty, this means + // disabled optimization) or has the same size as successor list. + if (!(Weights.empty() && !Successors.empty())) + Weights.push_back(Weight); + Successors.push_back(Succ); + Succ->addPredecessor(this); +} - // If we see non-zero value for the first time it means we actually use Weight - // list, so we fill all Weights with 0's. - if (weight != 0 && Weights.empty()) - Weights.resize(Successors.size()); +void MachineBasicBlock::addSuccessorWithoutWeight(MachineBasicBlock *Succ) { + // We need to make sure weight list is either empty or has the same size of + // successor list. When this function is called, we can safely delete all + // weight in the list. + Weights.clear(); + Successors.push_back(Succ); + Succ->addPredecessor(this); +} - if (weight != 0 || !Weights.empty()) - Weights.push_back(weight); +void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, + BranchProbability Prob) { + // Probability list is either empty (if successor list isn't empty, this means + // disabled optimization) or has the same size as successor list. + if (!(Probs.empty() && !Successors.empty())) + Probs.push_back(Prob); + Successors.push_back(Succ); + Succ->addPredecessor(this); +} - Successors.push_back(succ); - succ->addPredecessor(this); - } +void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) { + // We need to make sure probability list is either empty or has the same size + // of successor list. When this function is called, we can safely delete all + // probability in the list. + Probs.clear(); + Successors.push_back(Succ); + Succ->addPredecessor(this); +} -void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) { - succ->removePredecessor(this); - succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); +void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ) { + succ_iterator I = std::find(Successors.begin(), Successors.end(), Succ); assert(I != Successors.end() && "Not a current successor!"); - - // If Weight list is empty it means we don't use it (disabled optimization). - if (!Weights.empty()) { - weight_iterator WI = getWeightIterator(I); - Weights.erase(WI); - } - - Successors.erase(I); + removeSuccessor(I); } MachineBasicBlock::succ_iterator @@ -514,6 +559,13 @@ MachineBasicBlock::removeSuccessor(succ_iterator I) { Weights.erase(WI); } + // If probability list is empty it means we don't use it (disabled + // optimization). + if (!Probs.empty()) { + probability_iterator WI = getProbabilityIterator(I); + Probs.erase(WI); + } + (*I)->removePredecessor(this); return Successors.erase(I); } @@ -539,10 +591,10 @@ void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, } } assert(OldI != E && "Old is not a successor of this block"); - Old->removePredecessor(this); // If New isn't already a successor, let it take Old's place. if (NewI == E) { + Old->removePredecessor(this); New->addPredecessor(this); *OldI = New; return; @@ -550,60 +602,61 @@ void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, // New is already a successor. // Update its weight instead of adding a duplicate edge. - if (!Weights.empty()) { - weight_iterator OldWI = getWeightIterator(OldI); - *getWeightIterator(NewI) += *OldWI; - Weights.erase(OldWI); - } - Successors.erase(OldI); + if (!Weights.empty()) + *getWeightIterator(NewI) += *getWeightIterator(OldI); + // Update its probability instead of adding a duplicate edge. + if (!Probs.empty()) + *getProbabilityIterator(NewI) += *getProbabilityIterator(OldI); + + removeSuccessor(OldI); } -void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { - Predecessors.push_back(pred); +void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) { + Predecessors.push_back(Pred); } -void MachineBasicBlock::removePredecessor(MachineBasicBlock *pred) { - pred_iterator I = std::find(Predecessors.begin(), Predecessors.end(), pred); +void MachineBasicBlock::removePredecessor(MachineBasicBlock *Pred) { + pred_iterator I = std::find(Predecessors.begin(), Predecessors.end(), Pred); assert(I != Predecessors.end() && "Pred is not a predecessor of this block!"); Predecessors.erase(I); } -void MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB) { - if (this == fromMBB) +void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) { + if (this == FromMBB) return; - while (!fromMBB->succ_empty()) { - MachineBasicBlock *Succ = *fromMBB->succ_begin(); + while (!FromMBB->succ_empty()) { + MachineBasicBlock *Succ = *FromMBB->succ_begin(); uint32_t Weight = 0; // If Weight list is empty it means we don't use it (disabled optimization). - if (!fromMBB->Weights.empty()) - Weight = *fromMBB->Weights.begin(); + if (!FromMBB->Weights.empty()) + Weight = *FromMBB->Weights.begin(); addSuccessor(Succ, Weight); - fromMBB->removeSuccessor(Succ); + FromMBB->removeSuccessor(Succ); } } void -MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB) { - if (this == fromMBB) +MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) { + if (this == FromMBB) return; - while (!fromMBB->succ_empty()) { - MachineBasicBlock *Succ = *fromMBB->succ_begin(); + while (!FromMBB->succ_empty()) { + MachineBasicBlock *Succ = *FromMBB->succ_begin(); uint32_t Weight = 0; - if (!fromMBB->Weights.empty()) - Weight = *fromMBB->Weights.begin(); + if (!FromMBB->Weights.empty()) + Weight = *FromMBB->Weights.begin(); addSuccessor(Succ, Weight); - fromMBB->removeSuccessor(Succ); + FromMBB->removeSuccessor(Succ); // Fix up any PHI nodes in the successor. for (MachineBasicBlock::instr_iterator MI = Succ->instr_begin(), ME = Succ->instr_end(); MI != ME && MI->isPHI(); ++MI) for (unsigned i = 2, e = MI->getNumOperands()+1; i != e; i += 2) { MachineOperand &MO = MI->getOperand(i); - if (MO.getMBB() == fromMBB) + if (MO.getMBB() == FromMBB) MO.setMBB(this); } } @@ -623,14 +676,14 @@ bool MachineBasicBlock::isLayoutSuccessor(const MachineBasicBlock *MBB) const { } bool MachineBasicBlock::canFallThrough() { - MachineFunction::iterator Fallthrough = this; + MachineFunction::iterator Fallthrough = getIterator(); ++Fallthrough; // If FallthroughBlock is off the end of the function, it can't fall through. if (Fallthrough == getParent()->end()) return false; // If FallthroughBlock isn't a successor, no fallthrough is possible. - if (!isSuccessor(Fallthrough)) + if (!isSuccessor(&*Fallthrough)) return false; // Analyze the branches, if any, at the end of the block. @@ -668,11 +721,11 @@ MachineBasicBlock * MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { // Splitting the critical edge to a landing pad block is non-trivial. Don't do // it in this generic function. - if (Succ->isLandingPad()) + if (Succ->isEHPad()) return nullptr; MachineFunction *MF = getParent(); - DebugLoc dl; // FIXME: this is nowhere + DebugLoc DL; // FIXME: this is nowhere // Performance might be harmed on HW that implements branching using exec mask // where both sides of the branches are always executed. @@ -721,7 +774,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { if (LV) for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); I != E; ++I) { - MachineInstr *MI = I; + MachineInstr *MI = &*I; for (MachineInstr::mop_iterator OI = MI->operands_begin(), OE = MI->operands_end(); OI != OE; ++OI) { if (!OI->isReg() || OI->getReg() == 0 || @@ -741,7 +794,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { if (LIS) { for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); I != E; ++I) { - MachineInstr *MI = I; + MachineInstr *MI = &*I; for (MachineInstr::mop_iterator OI = MI->operands_begin(), OE = MI->operands_end(); OI != OE; ++OI) { @@ -763,7 +816,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { if (Indexes) { for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); I != E; ++I) - Terminators.push_back(I); + Terminators.push_back(&*I); } updateTerminator(); @@ -772,7 +825,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { SmallVector NewTerminators; for (instr_iterator I = getFirstInstrTerminator(), E = instr_end(); I != E; ++I) - NewTerminators.push_back(I); + NewTerminators.push_back(&*I); for (SmallVectorImpl::iterator I = Terminators.begin(), E = Terminators.end(); I != E; ++I) { @@ -786,17 +839,16 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { NMBB->addSuccessor(Succ); if (!NMBB->isLayoutSuccessor(Succ)) { Cond.clear(); - MF->getSubtarget().getInstrInfo()->InsertBranch(*NMBB, Succ, nullptr, Cond, - dl); + TII->InsertBranch(*NMBB, Succ, nullptr, Cond, DL); if (Indexes) { for (instr_iterator I = NMBB->instr_begin(), E = NMBB->instr_end(); I != E; ++I) { // Some instructions may have been moved to NMBB by updateTerminator(), // so we first remove any instruction that already has an index. - if (Indexes->hasIndex(I)) - Indexes->removeMachineInstrFromMaps(I); - Indexes->insertMachineInstrInMaps(I); + if (Indexes->hasIndex(&*I)) + Indexes->removeMachineInstrFromMaps(&*I); + Indexes->insertMachineInstrInMaps(&*I); } } } @@ -810,9 +862,8 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { i->getOperand(ni+1).setMBB(NMBB); // Inherit live-ins from the successor - for (MachineBasicBlock::livein_iterator I = Succ->livein_begin(), - E = Succ->livein_end(); I != E; ++I) - NMBB->addLiveIn(*I); + for (const auto &LI : Succ->liveins()) + NMBB->addLiveIn(LI); // Update LiveVariables. const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); @@ -824,7 +875,7 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false)) continue; if (TargetRegisterInfo::isVirtualRegister(Reg)) - LV->getVarInfo(Reg).Kills.push_back(I); + LV->getVarInfo(Reg).Kills.push_back(&*I); DEBUG(dbgs() << "Restored terminator kill: " << *I); break; } @@ -836,10 +887,10 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { if (LIS) { // After splitting the edge and updating SlotIndexes, live intervals may be // in one of two situations, depending on whether this block was the last in - // the function. If the original block was the last in the function, all live - // intervals will end prior to the beginning of the new split block. If the - // original block was not at the end of the function, all live intervals will - // extend to the end of the new split block. + // the function. If the original block was the last in the function, all + // live intervals will end prior to the beginning of the new split block. If + // the original block was not at the end of the function, all live intervals + // will extend to the end of the new split block. bool isLastMBB = std::next(MachineFunction::iterator(NMBB)) == getParent()->end(); @@ -863,7 +914,8 @@ MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) { LiveInterval &LI = LIS->getInterval(Reg); VNInfo *VNI = LI.getVNInfoAt(PrevIndex); - assert(VNI && "PHI sources should be live out of their predecessors."); + assert(VNI && + "PHI sources should be live out of their predecessors."); LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI)); } } @@ -943,7 +995,7 @@ static void unbundleSingleMI(MachineInstr *MI) { MachineBasicBlock::instr_iterator MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) { - unbundleSingleMI(I); + unbundleSingleMI(&*I); return Insts.erase(I); } @@ -966,25 +1018,22 @@ MachineBasicBlock::insert(instr_iterator I, MachineInstr *MI) { return Insts.insert(I, MI); } -/// removeFromParent - This method unlinks 'this' from the containing function, -/// and returns it, but does not delete it. +/// This method unlinks 'this' from the containing function, and returns it, but +/// does not delete it. MachineBasicBlock *MachineBasicBlock::removeFromParent() { assert(getParent() && "Not embedded in a function!"); getParent()->remove(this); return this; } - -/// eraseFromParent - This method unlinks 'this' from the containing function, -/// and deletes it. +/// This method unlinks 'this' from the containing function, and deletes it. void MachineBasicBlock::eraseFromParent() { assert(getParent() && "Not embedded in a function!"); getParent()->erase(this); } - -/// ReplaceUsesOfBlockWith - Given a machine basic block that branched to -/// 'Old', change the code and CFG so that it branches to 'New' instead. +/// Given a machine basic block that branched to 'Old', change the code and CFG +/// so that it branches to 'New' instead. void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New) { assert(Old != New && "Cannot replace self with self!"); @@ -1006,46 +1055,44 @@ void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, replaceSuccessor(Old, New); } -/// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the -/// CFG to be inserted. If we have proven that MBB can only branch to DestA and -/// DestB, remove any other MBB successors from the CFG. DestA and DestB can be -/// null. +/// Various pieces of code can cause excess edges in the CFG to be inserted. If +/// we have proven that MBB can only branch to DestA and DestB, remove any other +/// MBB successors from the CFG. DestA and DestB can be null. /// /// Besides DestA and DestB, retain other edges leading to LandingPads /// (currently there can be only one; we don't check or require that here). /// Note it is possible that DestA and/or DestB are LandingPads. bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, MachineBasicBlock *DestB, - bool isCond) { + bool IsCond) { // The values of DestA and DestB frequently come from a call to the // 'TargetInstrInfo::AnalyzeBranch' method. We take our meaning of the initial // values from there. // // 1. If both DestA and DestB are null, then the block ends with no branches // (it falls through to its successor). - // 2. If DestA is set, DestB is null, and isCond is false, then the block ends + // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends // with only an unconditional branch. - // 3. If DestA is set, DestB is null, and isCond is true, then the block ends + // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends // with a conditional branch that falls through to a successor (DestB). - // 4. If DestA and DestB is set and isCond is true, then the block ends with a + // 4. If DestA and DestB is set and IsCond is true, then the block ends with a // conditional branch followed by an unconditional branch. DestA is the // 'true' destination and DestB is the 'false' destination. bool Changed = false; - MachineFunction::iterator FallThru = - std::next(MachineFunction::iterator(this)); + MachineFunction::iterator FallThru = std::next(getIterator()); if (!DestA && !DestB) { // Block falls through to successor. - DestA = FallThru; - DestB = FallThru; + DestA = &*FallThru; + DestB = &*FallThru; } else if (DestA && !DestB) { - if (isCond) + if (IsCond) // Block ends in conditional jump that falls through to successor. - DestB = FallThru; + DestB = &*FallThru; } else { - assert(DestA && DestB && isCond && + assert(DestA && DestB && IsCond && "CFG in a bad state. Cannot correct CFG edges"); } @@ -1056,7 +1103,7 @@ bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, while (SI != succ_end()) { const MachineBasicBlock *MBB = *SI; if (!SeenMBBs.insert(MBB).second || - (MBB != DestA && MBB != DestB && !MBB->isLandingPad())) { + (MBB != DestA && MBB != DestB && !MBB->isEHPad())) { // This is a superfluous edge, remove it. SI = removeSuccessor(SI); Changed = true; @@ -1068,8 +1115,8 @@ bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA, return Changed; } -/// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping -/// any DBG_VALUE instructions. Return UnknownLoc if there is none. +/// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE +/// instructions. Return UnknownLoc if there is none. DebugLoc MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { DebugLoc DL; @@ -1085,8 +1132,7 @@ MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { return DL; } -/// getSuccWeight - Return weight of the edge from this block to MBB. -/// +/// Return weight of the edge from this block to MBB. uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const { if (Weights.empty()) return 0; @@ -1094,15 +1140,38 @@ uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const { return *getWeightIterator(Succ); } +/// Return probability of the edge from this block to MBB. If probability list +/// is empty, return a default probability which is 1/N, where N is the number +/// of successors. If the probability of the given successor is unknown, then +/// sum up all known probabilities and return the complement of the sum divided +/// by the number of unknown probabilities. +BranchProbability +MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const { + if (Probs.empty()) + return BranchProbability(1, succ_size()); + + auto Prob = *getProbabilityIterator(Succ); + assert(!Prob.isUnknown()); + return Prob; +} + /// Set successor weight of a given iterator. -void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t weight) { +void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t Weight) { if (Weights.empty()) return; - *getWeightIterator(I) = weight; + *getWeightIterator(I) = Weight; } -/// getWeightIterator - Return wight iterator corresonding to the I successor -/// iterator +/// Set successor probability of a given iterator. +void MachineBasicBlock::setSuccProbability(succ_iterator I, + BranchProbability Prob) { + assert(!Prob.isUnknown()); + if (Probs.empty()) + return; + *getProbabilityIterator(I) = Prob; +} + +/// Return wight iterator corresonding to the I successor iterator. MachineBasicBlock::weight_iterator MachineBasicBlock:: getWeightIterator(MachineBasicBlock::succ_iterator I) { assert(Weights.size() == Successors.size() && "Async weight list!"); @@ -1111,8 +1180,7 @@ getWeightIterator(MachineBasicBlock::succ_iterator I) { return Weights.begin() + index; } -/// getWeightIterator - Return wight iterator corresonding to the I successor -/// iterator +/// Return wight iterator corresonding to the I successor iterator. MachineBasicBlock::const_weight_iterator MachineBasicBlock:: getWeightIterator(MachineBasicBlock::const_succ_iterator I) const { assert(Weights.size() == Successors.size() && "Async weight list!"); @@ -1121,6 +1189,25 @@ getWeightIterator(MachineBasicBlock::const_succ_iterator I) const { return Weights.begin() + index; } +/// Return probability iterator corresonding to the I successor iterator. +MachineBasicBlock::probability_iterator +MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) { + assert(Probs.size() == Successors.size() && "Async probability list!"); + const size_t index = std::distance(Successors.begin(), I); + assert(index < Probs.size() && "Not a current successor!"); + return Probs.begin() + index; +} + +/// Return probability iterator corresonding to the I successor iterator +MachineBasicBlock::const_probability_iterator +MachineBasicBlock::getProbabilityIterator( + MachineBasicBlock::const_succ_iterator I) const { + assert(Probs.size() == Successors.size() && "Async probability list!"); + const size_t index = std::distance(Successors.begin(), I); + assert(index < Probs.size() && "Not a current successor!"); + return Probs.begin() + index; +} + /// Return whether (physical) register "Reg" has been ined and not ed /// as of just before "MI". /// @@ -1129,21 +1216,19 @@ getWeightIterator(MachineBasicBlock::const_succ_iterator I) const { /// instructions after (searching just for defs) MI. MachineBasicBlock::LivenessQueryResult MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI, - unsigned Reg, MachineInstr *MI, - unsigned Neighborhood) { + unsigned Reg, const_iterator Before, + unsigned Neighborhood) const { unsigned N = Neighborhood; - MachineBasicBlock *MBB = MI->getParent(); - - // Start by searching backwards from MI, looking for kills, reads or defs. - MachineBasicBlock::iterator I(MI); + // Start by searching backwards from Before, looking for kills, reads or defs. + const_iterator I(Before); // If this is the first insn in the block, don't search backwards. - if (I != MBB->begin()) { + if (I != begin()) { do { --I; MachineOperandIteratorBase::PhysRegInfo Analysis = - MIOperands(I).analyzePhysReg(Reg, TRI); + ConstMIOperands(I).analyzePhysReg(Reg, TRI); if (Analysis.Defines) // Outputs happen after inputs so they take precedence if both are @@ -1158,15 +1243,15 @@ MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI, // Defined or read without a previous kill - live. return Analysis.Reads ? LQR_Live : LQR_OverlappingLive; - } while (I != MBB->begin() && --N > 0); + } while (I != begin() && --N > 0); } // Did we get to the start of the block? - if (I == MBB->begin()) { + if (I == begin()) { // If so, the register's state is definitely defined by the live-in state. for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid(); ++RAI) { - if (MBB->isLiveIn(*RAI)) + if (isLiveIn(*RAI)) return (*RAI == Reg) ? LQR_Live : LQR_OverlappingLive; } @@ -1175,13 +1260,13 @@ MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI, N = Neighborhood; - // Try searching forwards from MI, looking for reads or defs. - I = MachineBasicBlock::iterator(MI); + // Try searching forwards from Before, looking for reads or defs. + I = const_iterator(Before); // If this is the last insn in the block, don't search forwards. - if (I != MBB->end()) { - for (++I; I != MBB->end() && N > 0; ++I, --N) { + if (I != end()) { + for (++I; I != end() && N > 0; ++I, --N) { MachineOperandIteratorBase::PhysRegInfo Analysis = - MIOperands(I).analyzePhysReg(Reg, TRI); + ConstMIOperands(I).analyzePhysReg(Reg, TRI); if (Analysis.ReadsOverlap) // Used, therefore must have been live. @@ -1197,3 +1282,17 @@ MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI, // At this point we have no idea of the liveness of the register. return LQR_Unknown; } + +const uint32_t * +MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const { + // EH funclet entry does not preserve any registers. + return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr; +} + +const uint32_t * +MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const { + // If we see a return block with successors, this must be a funclet return, + // which does not preserve any registers. If there are no successors, we don't + // care what kind of return it is, putting a mask after it is a no-op. + return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr; +}