10b57cec5SDimitry Andric //===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // This file implements the BasicBlock class for the IR library.
100b57cec5SDimitry Andric //
110b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
120b57cec5SDimitry Andric
130b57cec5SDimitry Andric #include "llvm/IR/BasicBlock.h"
140b57cec5SDimitry Andric #include "SymbolTableListTraitsImpl.h"
150b57cec5SDimitry Andric #include "llvm/ADT/STLExtras.h"
161fd87a68SDimitry Andric #include "llvm/ADT/Statistic.h"
170b57cec5SDimitry Andric #include "llvm/IR/CFG.h"
180b57cec5SDimitry Andric #include "llvm/IR/Constants.h"
195f757f3fSDimitry Andric #include "llvm/IR/DebugProgramInstruction.h"
200b57cec5SDimitry Andric #include "llvm/IR/Instructions.h"
210b57cec5SDimitry Andric #include "llvm/IR/IntrinsicInst.h"
220b57cec5SDimitry Andric #include "llvm/IR/LLVMContext.h"
230b57cec5SDimitry Andric #include "llvm/IR/Type.h"
245f757f3fSDimitry Andric #include "llvm/Support/CommandLine.h"
255f757f3fSDimitry Andric
265f757f3fSDimitry Andric #include "LLVMContextImpl.h"
270b57cec5SDimitry Andric
280b57cec5SDimitry Andric using namespace llvm;
290b57cec5SDimitry Andric
30349cc55cSDimitry Andric #define DEBUG_TYPE "ir"
31349cc55cSDimitry Andric STATISTIC(NumInstrRenumberings, "Number of renumberings across all blocks");
32349cc55cSDimitry Andric
335f757f3fSDimitry Andric cl::opt<bool>
345f757f3fSDimitry Andric UseNewDbgInfoFormat("experimental-debuginfo-iterators",
355f757f3fSDimitry Andric cl::desc("Enable communicating debuginfo positions "
365f757f3fSDimitry Andric "through iterators, eliminating intrinsics"),
375f757f3fSDimitry Andric cl::init(false));
385f757f3fSDimitry Andric
createMarker(Instruction * I)395f757f3fSDimitry Andric DPMarker *BasicBlock::createMarker(Instruction *I) {
405f757f3fSDimitry Andric assert(IsNewDbgInfoFormat &&
415f757f3fSDimitry Andric "Tried to create a marker in a non new debug-info block!");
425f757f3fSDimitry Andric if (I->DbgMarker)
435f757f3fSDimitry Andric return I->DbgMarker;
445f757f3fSDimitry Andric DPMarker *Marker = new DPMarker();
455f757f3fSDimitry Andric Marker->MarkedInstr = I;
465f757f3fSDimitry Andric I->DbgMarker = Marker;
475f757f3fSDimitry Andric return Marker;
485f757f3fSDimitry Andric }
495f757f3fSDimitry Andric
createMarker(InstListType::iterator It)505f757f3fSDimitry Andric DPMarker *BasicBlock::createMarker(InstListType::iterator It) {
515f757f3fSDimitry Andric assert(IsNewDbgInfoFormat &&
525f757f3fSDimitry Andric "Tried to create a marker in a non new debug-info block!");
535f757f3fSDimitry Andric if (It != end())
545f757f3fSDimitry Andric return createMarker(&*It);
555f757f3fSDimitry Andric DPMarker *DPM = getTrailingDPValues();
565f757f3fSDimitry Andric if (DPM)
575f757f3fSDimitry Andric return DPM;
585f757f3fSDimitry Andric DPM = new DPMarker();
595f757f3fSDimitry Andric setTrailingDPValues(DPM);
605f757f3fSDimitry Andric return DPM;
615f757f3fSDimitry Andric }
625f757f3fSDimitry Andric
convertToNewDbgValues()635f757f3fSDimitry Andric void BasicBlock::convertToNewDbgValues() {
645f757f3fSDimitry Andric // Is the command line option set?
655f757f3fSDimitry Andric if (!UseNewDbgInfoFormat)
665f757f3fSDimitry Andric return;
675f757f3fSDimitry Andric
685f757f3fSDimitry Andric IsNewDbgInfoFormat = true;
695f757f3fSDimitry Andric
705f757f3fSDimitry Andric // Iterate over all instructions in the instruction list, collecting dbg.value
715f757f3fSDimitry Andric // instructions and converting them to DPValues. Once we find a "real"
725f757f3fSDimitry Andric // instruction, attach all those DPValues to a DPMarker in that instruction.
735f757f3fSDimitry Andric SmallVector<DPValue *, 4> DPVals;
745f757f3fSDimitry Andric for (Instruction &I : make_early_inc_range(InstList)) {
755f757f3fSDimitry Andric assert(!I.DbgMarker && "DbgMarker already set on old-format instrs?");
765f757f3fSDimitry Andric if (DbgVariableIntrinsic *DVI = dyn_cast<DbgVariableIntrinsic>(&I)) {
775f757f3fSDimitry Andric // Convert this dbg.value to a DPValue.
785f757f3fSDimitry Andric DPValue *Value = new DPValue(DVI);
795f757f3fSDimitry Andric DPVals.push_back(Value);
805f757f3fSDimitry Andric DVI->eraseFromParent();
815f757f3fSDimitry Andric continue;
825f757f3fSDimitry Andric }
835f757f3fSDimitry Andric
845f757f3fSDimitry Andric // Create a marker to store DPValues in. Technically we don't need to store
855f757f3fSDimitry Andric // one marker per instruction, but that's a future optimisation.
865f757f3fSDimitry Andric createMarker(&I);
875f757f3fSDimitry Andric DPMarker *Marker = I.DbgMarker;
885f757f3fSDimitry Andric
895f757f3fSDimitry Andric for (DPValue *DPV : DPVals)
905f757f3fSDimitry Andric Marker->insertDPValue(DPV, false);
915f757f3fSDimitry Andric
925f757f3fSDimitry Andric DPVals.clear();
935f757f3fSDimitry Andric }
945f757f3fSDimitry Andric }
955f757f3fSDimitry Andric
convertFromNewDbgValues()965f757f3fSDimitry Andric void BasicBlock::convertFromNewDbgValues() {
975f757f3fSDimitry Andric invalidateOrders();
985f757f3fSDimitry Andric IsNewDbgInfoFormat = false;
995f757f3fSDimitry Andric
1005f757f3fSDimitry Andric // Iterate over the block, finding instructions annotated with DPMarkers.
1015f757f3fSDimitry Andric // Convert any attached DPValues to dbg.values and insert ahead of the
1025f757f3fSDimitry Andric // instruction.
1035f757f3fSDimitry Andric for (auto &Inst : *this) {
1045f757f3fSDimitry Andric if (!Inst.DbgMarker)
1055f757f3fSDimitry Andric continue;
1065f757f3fSDimitry Andric
1075f757f3fSDimitry Andric DPMarker &Marker = *Inst.DbgMarker;
1085f757f3fSDimitry Andric for (DPValue &DPV : Marker.getDbgValueRange())
1095f757f3fSDimitry Andric InstList.insert(Inst.getIterator(),
1105f757f3fSDimitry Andric DPV.createDebugIntrinsic(getModule(), nullptr));
1115f757f3fSDimitry Andric
1125f757f3fSDimitry Andric Marker.eraseFromParent();
1135f757f3fSDimitry Andric };
1145f757f3fSDimitry Andric
1155f757f3fSDimitry Andric // Assume no trailing DPValues: we could technically create them at the end
1165f757f3fSDimitry Andric // of the block, after a terminator, but this would be non-cannonical and
1175f757f3fSDimitry Andric // indicates that something else is broken somewhere.
1185f757f3fSDimitry Andric assert(!getTrailingDPValues());
1195f757f3fSDimitry Andric }
1205f757f3fSDimitry Andric
validateDbgValues(bool Assert,bool Msg,raw_ostream * OS)1215f757f3fSDimitry Andric bool BasicBlock::validateDbgValues(bool Assert, bool Msg, raw_ostream *OS) {
1225f757f3fSDimitry Andric bool RetVal = false;
1235f757f3fSDimitry Andric if (!OS)
1245f757f3fSDimitry Andric OS = &errs();
1255f757f3fSDimitry Andric
1265f757f3fSDimitry Andric // Helper lambda for reporting failures: via assertion, printing, and return
1275f757f3fSDimitry Andric // value.
1285f757f3fSDimitry Andric auto TestFailure = [Assert, Msg, &RetVal, OS](bool Val, const char *Text) {
1295f757f3fSDimitry Andric // Did the test fail?
1305f757f3fSDimitry Andric if (Val)
1315f757f3fSDimitry Andric return;
1325f757f3fSDimitry Andric
1335f757f3fSDimitry Andric // If we're asserting, then fire off an assertion.
1345f757f3fSDimitry Andric if (Assert)
1355f757f3fSDimitry Andric llvm_unreachable(Text);
1365f757f3fSDimitry Andric
1375f757f3fSDimitry Andric if (Msg)
1385f757f3fSDimitry Andric *OS << Text << "\n";
1395f757f3fSDimitry Andric RetVal = true;
1405f757f3fSDimitry Andric };
1415f757f3fSDimitry Andric
1425f757f3fSDimitry Andric // We should have the same debug-format as the parent function.
1435f757f3fSDimitry Andric TestFailure(getParent()->IsNewDbgInfoFormat == IsNewDbgInfoFormat,
1445f757f3fSDimitry Andric "Parent function doesn't have the same debug-info format");
1455f757f3fSDimitry Andric
1465f757f3fSDimitry Andric // Only validate if we are using the new format.
1475f757f3fSDimitry Andric if (!IsNewDbgInfoFormat)
1485f757f3fSDimitry Andric return RetVal;
1495f757f3fSDimitry Andric
1505f757f3fSDimitry Andric // Match every DPMarker to every Instruction and vice versa, and
1515f757f3fSDimitry Andric // verify that there are no invalid DPValues.
1525f757f3fSDimitry Andric for (auto It = begin(); It != end(); ++It) {
1535f757f3fSDimitry Andric if (!It->DbgMarker)
1545f757f3fSDimitry Andric continue;
1555f757f3fSDimitry Andric
1565f757f3fSDimitry Andric // Validate DebugProgramMarkers.
1575f757f3fSDimitry Andric DPMarker *CurrentDebugMarker = It->DbgMarker;
1585f757f3fSDimitry Andric
1595f757f3fSDimitry Andric // If this is a marker, it should match the instruction and vice versa.
1605f757f3fSDimitry Andric TestFailure(CurrentDebugMarker->MarkedInstr == &*It,
1615f757f3fSDimitry Andric "Debug Marker points to incorrect instruction?");
1625f757f3fSDimitry Andric
1635f757f3fSDimitry Andric // Now validate any DPValues in the marker.
1645f757f3fSDimitry Andric for (DPValue &DPV : CurrentDebugMarker->getDbgValueRange()) {
1655f757f3fSDimitry Andric // Validate DebugProgramValues.
1665f757f3fSDimitry Andric TestFailure(DPV.getMarker() == CurrentDebugMarker,
1675f757f3fSDimitry Andric "Not pointing at correct next marker!");
1685f757f3fSDimitry Andric
1695f757f3fSDimitry Andric // Verify that no DbgValues appear prior to PHIs.
1705f757f3fSDimitry Andric TestFailure(
1715f757f3fSDimitry Andric !isa<PHINode>(It),
1725f757f3fSDimitry Andric "DebugProgramValues must not appear before PHI nodes in a block!");
1735f757f3fSDimitry Andric }
1745f757f3fSDimitry Andric }
1755f757f3fSDimitry Andric
1765f757f3fSDimitry Andric // Except transiently when removing + re-inserting the block terminator, there
1775f757f3fSDimitry Andric // should be no trailing DPValues.
1785f757f3fSDimitry Andric TestFailure(!getTrailingDPValues(), "Trailing DPValues in block");
1795f757f3fSDimitry Andric return RetVal;
1805f757f3fSDimitry Andric }
1815f757f3fSDimitry Andric
1825f757f3fSDimitry Andric #ifndef NDEBUG
dumpDbgValues() const1835f757f3fSDimitry Andric void BasicBlock::dumpDbgValues() const {
1845f757f3fSDimitry Andric for (auto &Inst : *this) {
1855f757f3fSDimitry Andric if (!Inst.DbgMarker)
1865f757f3fSDimitry Andric continue;
1875f757f3fSDimitry Andric
1885f757f3fSDimitry Andric dbgs() << "@ " << Inst.DbgMarker << " ";
1895f757f3fSDimitry Andric Inst.DbgMarker->dump();
1905f757f3fSDimitry Andric };
1915f757f3fSDimitry Andric }
1925f757f3fSDimitry Andric #endif
1935f757f3fSDimitry Andric
setIsNewDbgInfoFormat(bool NewFlag)1945f757f3fSDimitry Andric void BasicBlock::setIsNewDbgInfoFormat(bool NewFlag) {
1955f757f3fSDimitry Andric if (NewFlag && !IsNewDbgInfoFormat)
1965f757f3fSDimitry Andric convertToNewDbgValues();
1975f757f3fSDimitry Andric else if (!NewFlag && IsNewDbgInfoFormat)
1985f757f3fSDimitry Andric convertFromNewDbgValues();
1995f757f3fSDimitry Andric }
2005f757f3fSDimitry Andric
getValueSymbolTable()2010b57cec5SDimitry Andric ValueSymbolTable *BasicBlock::getValueSymbolTable() {
2020b57cec5SDimitry Andric if (Function *F = getParent())
2030b57cec5SDimitry Andric return F->getValueSymbolTable();
2040b57cec5SDimitry Andric return nullptr;
2050b57cec5SDimitry Andric }
2060b57cec5SDimitry Andric
getContext() const2070b57cec5SDimitry Andric LLVMContext &BasicBlock::getContext() const {
2080b57cec5SDimitry Andric return getType()->getContext();
2090b57cec5SDimitry Andric }
2100b57cec5SDimitry Andric
invalidateParentIListOrdering(BasicBlock * BB)2115ffd83dbSDimitry Andric template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
2125ffd83dbSDimitry Andric BB->invalidateOrders();
2135ffd83dbSDimitry Andric }
2145ffd83dbSDimitry Andric
2150b57cec5SDimitry Andric // Explicit instantiation of SymbolTableListTraits since some of the methods
2160b57cec5SDimitry Andric // are not in the public header file...
2175f757f3fSDimitry Andric template class llvm::SymbolTableListTraits<Instruction,
2185f757f3fSDimitry Andric ilist_iterator_bits<true>>;
2190b57cec5SDimitry Andric
BasicBlock(LLVMContext & C,const Twine & Name,Function * NewParent,BasicBlock * InsertBefore)2200b57cec5SDimitry Andric BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
2210b57cec5SDimitry Andric BasicBlock *InsertBefore)
2225f757f3fSDimitry Andric : Value(Type::getLabelTy(C), Value::BasicBlockVal),
2235f757f3fSDimitry Andric IsNewDbgInfoFormat(false), Parent(nullptr) {
2240b57cec5SDimitry Andric
2250b57cec5SDimitry Andric if (NewParent)
2260b57cec5SDimitry Andric insertInto(NewParent, InsertBefore);
2270b57cec5SDimitry Andric else
2280b57cec5SDimitry Andric assert(!InsertBefore &&
2290b57cec5SDimitry Andric "Cannot insert block before another block with no function!");
2300b57cec5SDimitry Andric
2310b57cec5SDimitry Andric setName(Name);
2325f757f3fSDimitry Andric if (NewParent)
2335f757f3fSDimitry Andric setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat);
2340b57cec5SDimitry Andric }
2350b57cec5SDimitry Andric
insertInto(Function * NewParent,BasicBlock * InsertBefore)2360b57cec5SDimitry Andric void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
2370b57cec5SDimitry Andric assert(NewParent && "Expected a parent");
2380b57cec5SDimitry Andric assert(!Parent && "Already has a parent");
2390b57cec5SDimitry Andric
2400b57cec5SDimitry Andric if (InsertBefore)
241bdd1243dSDimitry Andric NewParent->insert(InsertBefore->getIterator(), this);
2420b57cec5SDimitry Andric else
243bdd1243dSDimitry Andric NewParent->insert(NewParent->end(), this);
2447a6dacacSDimitry Andric
2457a6dacacSDimitry Andric setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat);
2460b57cec5SDimitry Andric }
2470b57cec5SDimitry Andric
~BasicBlock()2480b57cec5SDimitry Andric BasicBlock::~BasicBlock() {
2495ffd83dbSDimitry Andric validateInstrOrdering();
2505ffd83dbSDimitry Andric
2510b57cec5SDimitry Andric // If the address of the block is taken and it is being deleted (e.g. because
2520b57cec5SDimitry Andric // it is dead), this means that there is either a dangling constant expr
2530b57cec5SDimitry Andric // hanging off the block, or an undefined use of the block (source code
2540b57cec5SDimitry Andric // expecting the address of a label to keep the block alive even though there
2550b57cec5SDimitry Andric // is no indirect branch). Handle these cases by zapping the BlockAddress
2560b57cec5SDimitry Andric // nodes. There are no other possible uses at this point.
2570b57cec5SDimitry Andric if (hasAddressTaken()) {
2580b57cec5SDimitry Andric assert(!use_empty() && "There should be at least one blockaddress!");
2590b57cec5SDimitry Andric Constant *Replacement =
2600b57cec5SDimitry Andric ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
2610b57cec5SDimitry Andric while (!use_empty()) {
2620b57cec5SDimitry Andric BlockAddress *BA = cast<BlockAddress>(user_back());
2630b57cec5SDimitry Andric BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
2640b57cec5SDimitry Andric BA->getType()));
2650b57cec5SDimitry Andric BA->destroyConstant();
2660b57cec5SDimitry Andric }
2670b57cec5SDimitry Andric }
2680b57cec5SDimitry Andric
2690b57cec5SDimitry Andric assert(getParent() == nullptr && "BasicBlock still linked into the program!");
2700b57cec5SDimitry Andric dropAllReferences();
2715f757f3fSDimitry Andric for (auto &Inst : *this) {
2725f757f3fSDimitry Andric if (!Inst.DbgMarker)
2735f757f3fSDimitry Andric continue;
2745f757f3fSDimitry Andric Inst.DbgMarker->eraseFromParent();
2755f757f3fSDimitry Andric }
2760b57cec5SDimitry Andric InstList.clear();
2770b57cec5SDimitry Andric }
2780b57cec5SDimitry Andric
setParent(Function * parent)2790b57cec5SDimitry Andric void BasicBlock::setParent(Function *parent) {
2800b57cec5SDimitry Andric // Set Parent=parent, updating instruction symtab entries as appropriate.
2810b57cec5SDimitry Andric InstList.setSymTabObject(&Parent, parent);
2820b57cec5SDimitry Andric }
2830b57cec5SDimitry Andric
2840b57cec5SDimitry Andric iterator_range<filter_iterator<BasicBlock::const_iterator,
2850b57cec5SDimitry Andric std::function<bool(const Instruction &)>>>
instructionsWithoutDebug(bool SkipPseudoOp) const286e8d8bef9SDimitry Andric BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) const {
287e8d8bef9SDimitry Andric std::function<bool(const Instruction &)> Fn = [=](const Instruction &I) {
288e8d8bef9SDimitry Andric return !isa<DbgInfoIntrinsic>(I) &&
289e8d8bef9SDimitry Andric !(SkipPseudoOp && isa<PseudoProbeInst>(I));
2900b57cec5SDimitry Andric };
2910b57cec5SDimitry Andric return make_filter_range(*this, Fn);
2920b57cec5SDimitry Andric }
2930b57cec5SDimitry Andric
294e8d8bef9SDimitry Andric iterator_range<
295e8d8bef9SDimitry Andric filter_iterator<BasicBlock::iterator, std::function<bool(Instruction &)>>>
instructionsWithoutDebug(bool SkipPseudoOp)296e8d8bef9SDimitry Andric BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) {
297e8d8bef9SDimitry Andric std::function<bool(Instruction &)> Fn = [=](Instruction &I) {
298e8d8bef9SDimitry Andric return !isa<DbgInfoIntrinsic>(I) &&
299e8d8bef9SDimitry Andric !(SkipPseudoOp && isa<PseudoProbeInst>(I));
3000b57cec5SDimitry Andric };
3010b57cec5SDimitry Andric return make_filter_range(*this, Fn);
3020b57cec5SDimitry Andric }
3030b57cec5SDimitry Andric
3048bcb0991SDimitry Andric filter_iterator<BasicBlock::const_iterator,
3058bcb0991SDimitry Andric std::function<bool(const Instruction &)>>::difference_type
sizeWithoutDebug() const3068bcb0991SDimitry Andric BasicBlock::sizeWithoutDebug() const {
3078bcb0991SDimitry Andric return std::distance(instructionsWithoutDebug().begin(),
3088bcb0991SDimitry Andric instructionsWithoutDebug().end());
3098bcb0991SDimitry Andric }
3108bcb0991SDimitry Andric
removeFromParent()3110b57cec5SDimitry Andric void BasicBlock::removeFromParent() {
3120b57cec5SDimitry Andric getParent()->getBasicBlockList().remove(getIterator());
3130b57cec5SDimitry Andric }
3140b57cec5SDimitry Andric
eraseFromParent()3150b57cec5SDimitry Andric iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
3160b57cec5SDimitry Andric return getParent()->getBasicBlockList().erase(getIterator());
3170b57cec5SDimitry Andric }
3180b57cec5SDimitry Andric
moveBefore(SymbolTableList<BasicBlock>::iterator MovePos)31906c3fb27SDimitry Andric void BasicBlock::moveBefore(SymbolTableList<BasicBlock>::iterator MovePos) {
32006c3fb27SDimitry Andric getParent()->splice(MovePos, getParent(), getIterator());
3210b57cec5SDimitry Andric }
3220b57cec5SDimitry Andric
moveAfter(BasicBlock * MovePos)3230b57cec5SDimitry Andric void BasicBlock::moveAfter(BasicBlock *MovePos) {
324bdd1243dSDimitry Andric MovePos->getParent()->splice(++MovePos->getIterator(), getParent(),
3250b57cec5SDimitry Andric getIterator());
3260b57cec5SDimitry Andric }
3270b57cec5SDimitry Andric
getModule() const3280b57cec5SDimitry Andric const Module *BasicBlock::getModule() const {
3290b57cec5SDimitry Andric return getParent()->getParent();
3300b57cec5SDimitry Andric }
3310b57cec5SDimitry Andric
getTerminatingMustTailCall() const3320b57cec5SDimitry Andric const CallInst *BasicBlock::getTerminatingMustTailCall() const {
3330b57cec5SDimitry Andric if (InstList.empty())
3340b57cec5SDimitry Andric return nullptr;
3350b57cec5SDimitry Andric const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
3360b57cec5SDimitry Andric if (!RI || RI == &InstList.front())
3370b57cec5SDimitry Andric return nullptr;
3380b57cec5SDimitry Andric
3390b57cec5SDimitry Andric const Instruction *Prev = RI->getPrevNode();
3400b57cec5SDimitry Andric if (!Prev)
3410b57cec5SDimitry Andric return nullptr;
3420b57cec5SDimitry Andric
3430b57cec5SDimitry Andric if (Value *RV = RI->getReturnValue()) {
3440b57cec5SDimitry Andric if (RV != Prev)
3450b57cec5SDimitry Andric return nullptr;
3460b57cec5SDimitry Andric
3470b57cec5SDimitry Andric // Look through the optional bitcast.
3480b57cec5SDimitry Andric if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
3490b57cec5SDimitry Andric RV = BI->getOperand(0);
3500b57cec5SDimitry Andric Prev = BI->getPrevNode();
3510b57cec5SDimitry Andric if (!Prev || RV != Prev)
3520b57cec5SDimitry Andric return nullptr;
3530b57cec5SDimitry Andric }
3540b57cec5SDimitry Andric }
3550b57cec5SDimitry Andric
3560b57cec5SDimitry Andric if (auto *CI = dyn_cast<CallInst>(Prev)) {
3570b57cec5SDimitry Andric if (CI->isMustTailCall())
3580b57cec5SDimitry Andric return CI;
3590b57cec5SDimitry Andric }
3600b57cec5SDimitry Andric return nullptr;
3610b57cec5SDimitry Andric }
3620b57cec5SDimitry Andric
getTerminatingDeoptimizeCall() const3630b57cec5SDimitry Andric const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
3640b57cec5SDimitry Andric if (InstList.empty())
3650b57cec5SDimitry Andric return nullptr;
3660b57cec5SDimitry Andric auto *RI = dyn_cast<ReturnInst>(&InstList.back());
3670b57cec5SDimitry Andric if (!RI || RI == &InstList.front())
3680b57cec5SDimitry Andric return nullptr;
3690b57cec5SDimitry Andric
3700b57cec5SDimitry Andric if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
3710b57cec5SDimitry Andric if (Function *F = CI->getCalledFunction())
3720b57cec5SDimitry Andric if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
3730b57cec5SDimitry Andric return CI;
3740b57cec5SDimitry Andric
3750b57cec5SDimitry Andric return nullptr;
3760b57cec5SDimitry Andric }
3770b57cec5SDimitry Andric
getPostdominatingDeoptimizeCall() const3785ffd83dbSDimitry Andric const CallInst *BasicBlock::getPostdominatingDeoptimizeCall() const {
3795ffd83dbSDimitry Andric const BasicBlock* BB = this;
3805ffd83dbSDimitry Andric SmallPtrSet<const BasicBlock *, 8> Visited;
3815ffd83dbSDimitry Andric Visited.insert(BB);
3825ffd83dbSDimitry Andric while (auto *Succ = BB->getUniqueSuccessor()) {
3835ffd83dbSDimitry Andric if (!Visited.insert(Succ).second)
3845ffd83dbSDimitry Andric return nullptr;
3855ffd83dbSDimitry Andric BB = Succ;
3865ffd83dbSDimitry Andric }
3875ffd83dbSDimitry Andric return BB->getTerminatingDeoptimizeCall();
3885ffd83dbSDimitry Andric }
3895ffd83dbSDimitry Andric
getFirstMayFaultInst() const39006c3fb27SDimitry Andric const Instruction *BasicBlock::getFirstMayFaultInst() const {
39106c3fb27SDimitry Andric if (InstList.empty())
39206c3fb27SDimitry Andric return nullptr;
39306c3fb27SDimitry Andric for (const Instruction &I : *this)
39406c3fb27SDimitry Andric if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallBase>(I))
39506c3fb27SDimitry Andric return &I;
39606c3fb27SDimitry Andric return nullptr;
39706c3fb27SDimitry Andric }
39806c3fb27SDimitry Andric
getFirstNonPHI() const3990b57cec5SDimitry Andric const Instruction* BasicBlock::getFirstNonPHI() const {
4000b57cec5SDimitry Andric for (const Instruction &I : *this)
4010b57cec5SDimitry Andric if (!isa<PHINode>(I))
4020b57cec5SDimitry Andric return &I;
4030b57cec5SDimitry Andric return nullptr;
4040b57cec5SDimitry Andric }
4050b57cec5SDimitry Andric
getFirstNonPHIIt() const4065f757f3fSDimitry Andric BasicBlock::const_iterator BasicBlock::getFirstNonPHIIt() const {
4075f757f3fSDimitry Andric const Instruction *I = getFirstNonPHI();
4085f757f3fSDimitry Andric BasicBlock::const_iterator It = I->getIterator();
4095f757f3fSDimitry Andric // Set the head-inclusive bit to indicate that this iterator includes
4105f757f3fSDimitry Andric // any debug-info at the start of the block. This is a no-op unless the
4115f757f3fSDimitry Andric // appropriate CMake flag is set.
4125f757f3fSDimitry Andric It.setHeadBit(true);
4135f757f3fSDimitry Andric return It;
4145f757f3fSDimitry Andric }
4155f757f3fSDimitry Andric
getFirstNonPHIOrDbg(bool SkipPseudoOp) const416e8d8bef9SDimitry Andric const Instruction *BasicBlock::getFirstNonPHIOrDbg(bool SkipPseudoOp) const {
417e8d8bef9SDimitry Andric for (const Instruction &I : *this) {
418e8d8bef9SDimitry Andric if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
419e8d8bef9SDimitry Andric continue;
420e8d8bef9SDimitry Andric
421e8d8bef9SDimitry Andric if (SkipPseudoOp && isa<PseudoProbeInst>(I))
422e8d8bef9SDimitry Andric continue;
423e8d8bef9SDimitry Andric
4240b57cec5SDimitry Andric return &I;
425e8d8bef9SDimitry Andric }
4260b57cec5SDimitry Andric return nullptr;
4270b57cec5SDimitry Andric }
4280b57cec5SDimitry Andric
429e8d8bef9SDimitry Andric const Instruction *
getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp) const430e8d8bef9SDimitry Andric BasicBlock::getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp) const {
4310b57cec5SDimitry Andric for (const Instruction &I : *this) {
4320b57cec5SDimitry Andric if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
4330b57cec5SDimitry Andric continue;
4340b57cec5SDimitry Andric
4350b57cec5SDimitry Andric if (I.isLifetimeStartOrEnd())
4360b57cec5SDimitry Andric continue;
4370b57cec5SDimitry Andric
438e8d8bef9SDimitry Andric if (SkipPseudoOp && isa<PseudoProbeInst>(I))
439e8d8bef9SDimitry Andric continue;
440e8d8bef9SDimitry Andric
4410b57cec5SDimitry Andric return &I;
4420b57cec5SDimitry Andric }
4430b57cec5SDimitry Andric return nullptr;
4440b57cec5SDimitry Andric }
4450b57cec5SDimitry Andric
getFirstInsertionPt() const4460b57cec5SDimitry Andric BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
4470b57cec5SDimitry Andric const Instruction *FirstNonPHI = getFirstNonPHI();
4480b57cec5SDimitry Andric if (!FirstNonPHI)
4490b57cec5SDimitry Andric return end();
4500b57cec5SDimitry Andric
4510b57cec5SDimitry Andric const_iterator InsertPt = FirstNonPHI->getIterator();
4520b57cec5SDimitry Andric if (InsertPt->isEHPad()) ++InsertPt;
4535f757f3fSDimitry Andric // Set the head-inclusive bit to indicate that this iterator includes
4545f757f3fSDimitry Andric // any debug-info at the start of the block. This is a no-op unless the
4555f757f3fSDimitry Andric // appropriate CMake flag is set.
4565f757f3fSDimitry Andric InsertPt.setHeadBit(true);
4570b57cec5SDimitry Andric return InsertPt;
4580b57cec5SDimitry Andric }
4590b57cec5SDimitry Andric
getFirstNonPHIOrDbgOrAlloca() const460bdd1243dSDimitry Andric BasicBlock::const_iterator BasicBlock::getFirstNonPHIOrDbgOrAlloca() const {
461bdd1243dSDimitry Andric const Instruction *FirstNonPHI = getFirstNonPHI();
462bdd1243dSDimitry Andric if (!FirstNonPHI)
463bdd1243dSDimitry Andric return end();
464bdd1243dSDimitry Andric
465bdd1243dSDimitry Andric const_iterator InsertPt = FirstNonPHI->getIterator();
466bdd1243dSDimitry Andric if (InsertPt->isEHPad())
467bdd1243dSDimitry Andric ++InsertPt;
468bdd1243dSDimitry Andric
469bdd1243dSDimitry Andric if (isEntryBlock()) {
470bdd1243dSDimitry Andric const_iterator End = end();
471bdd1243dSDimitry Andric while (InsertPt != End &&
472bdd1243dSDimitry Andric (isa<AllocaInst>(*InsertPt) || isa<DbgInfoIntrinsic>(*InsertPt) ||
473bdd1243dSDimitry Andric isa<PseudoProbeInst>(*InsertPt))) {
474bdd1243dSDimitry Andric if (const AllocaInst *AI = dyn_cast<AllocaInst>(&*InsertPt)) {
475bdd1243dSDimitry Andric if (!AI->isStaticAlloca())
476bdd1243dSDimitry Andric break;
477bdd1243dSDimitry Andric }
478bdd1243dSDimitry Andric ++InsertPt;
479bdd1243dSDimitry Andric }
480bdd1243dSDimitry Andric }
481bdd1243dSDimitry Andric return InsertPt;
482bdd1243dSDimitry Andric }
483bdd1243dSDimitry Andric
dropAllReferences()4840b57cec5SDimitry Andric void BasicBlock::dropAllReferences() {
4850b57cec5SDimitry Andric for (Instruction &I : *this)
4860b57cec5SDimitry Andric I.dropAllReferences();
4870b57cec5SDimitry Andric }
4880b57cec5SDimitry Andric
getSinglePredecessor() const4890b57cec5SDimitry Andric const BasicBlock *BasicBlock::getSinglePredecessor() const {
4900b57cec5SDimitry Andric const_pred_iterator PI = pred_begin(this), E = pred_end(this);
4910b57cec5SDimitry Andric if (PI == E) return nullptr; // No preds.
4920b57cec5SDimitry Andric const BasicBlock *ThePred = *PI;
4930b57cec5SDimitry Andric ++PI;
4940b57cec5SDimitry Andric return (PI == E) ? ThePred : nullptr /*multiple preds*/;
4950b57cec5SDimitry Andric }
4960b57cec5SDimitry Andric
getUniquePredecessor() const4970b57cec5SDimitry Andric const BasicBlock *BasicBlock::getUniquePredecessor() const {
4980b57cec5SDimitry Andric const_pred_iterator PI = pred_begin(this), E = pred_end(this);
4990b57cec5SDimitry Andric if (PI == E) return nullptr; // No preds.
5000b57cec5SDimitry Andric const BasicBlock *PredBB = *PI;
5010b57cec5SDimitry Andric ++PI;
5020b57cec5SDimitry Andric for (;PI != E; ++PI) {
5030b57cec5SDimitry Andric if (*PI != PredBB)
5040b57cec5SDimitry Andric return nullptr;
5050b57cec5SDimitry Andric // The same predecessor appears multiple times in the predecessor list.
5060b57cec5SDimitry Andric // This is OK.
5070b57cec5SDimitry Andric }
5080b57cec5SDimitry Andric return PredBB;
5090b57cec5SDimitry Andric }
5100b57cec5SDimitry Andric
hasNPredecessors(unsigned N) const5110b57cec5SDimitry Andric bool BasicBlock::hasNPredecessors(unsigned N) const {
5120b57cec5SDimitry Andric return hasNItems(pred_begin(this), pred_end(this), N);
5130b57cec5SDimitry Andric }
5140b57cec5SDimitry Andric
hasNPredecessorsOrMore(unsigned N) const5150b57cec5SDimitry Andric bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const {
5160b57cec5SDimitry Andric return hasNItemsOrMore(pred_begin(this), pred_end(this), N);
5170b57cec5SDimitry Andric }
5180b57cec5SDimitry Andric
getSingleSuccessor() const5190b57cec5SDimitry Andric const BasicBlock *BasicBlock::getSingleSuccessor() const {
5205ffd83dbSDimitry Andric const_succ_iterator SI = succ_begin(this), E = succ_end(this);
5210b57cec5SDimitry Andric if (SI == E) return nullptr; // no successors
5220b57cec5SDimitry Andric const BasicBlock *TheSucc = *SI;
5230b57cec5SDimitry Andric ++SI;
5240b57cec5SDimitry Andric return (SI == E) ? TheSucc : nullptr /* multiple successors */;
5250b57cec5SDimitry Andric }
5260b57cec5SDimitry Andric
getUniqueSuccessor() const5270b57cec5SDimitry Andric const BasicBlock *BasicBlock::getUniqueSuccessor() const {
5285ffd83dbSDimitry Andric const_succ_iterator SI = succ_begin(this), E = succ_end(this);
5290b57cec5SDimitry Andric if (SI == E) return nullptr; // No successors
5300b57cec5SDimitry Andric const BasicBlock *SuccBB = *SI;
5310b57cec5SDimitry Andric ++SI;
5320b57cec5SDimitry Andric for (;SI != E; ++SI) {
5330b57cec5SDimitry Andric if (*SI != SuccBB)
5340b57cec5SDimitry Andric return nullptr;
5350b57cec5SDimitry Andric // The same successor appears multiple times in the successor list.
5360b57cec5SDimitry Andric // This is OK.
5370b57cec5SDimitry Andric }
5380b57cec5SDimitry Andric return SuccBB;
5390b57cec5SDimitry Andric }
5400b57cec5SDimitry Andric
phis()5410b57cec5SDimitry Andric iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
5420b57cec5SDimitry Andric PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin());
5430b57cec5SDimitry Andric return make_range<phi_iterator>(P, nullptr);
5440b57cec5SDimitry Andric }
5450b57cec5SDimitry Andric
removePredecessor(BasicBlock * Pred,bool KeepOneInputPHIs)5460b57cec5SDimitry Andric void BasicBlock::removePredecessor(BasicBlock *Pred,
5470b57cec5SDimitry Andric bool KeepOneInputPHIs) {
5485ffd83dbSDimitry Andric // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
549e8d8bef9SDimitry Andric assert((hasNUsesOrMore(16) || llvm::is_contained(predecessors(this), Pred)) &&
5505ffd83dbSDimitry Andric "Pred is not a predecessor!");
5510b57cec5SDimitry Andric
5525ffd83dbSDimitry Andric // Return early if there are no PHI nodes to update.
553e8d8bef9SDimitry Andric if (empty() || !isa<PHINode>(begin()))
5545ffd83dbSDimitry Andric return;
5550b57cec5SDimitry Andric
556e8d8bef9SDimitry Andric unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues();
557e8d8bef9SDimitry Andric for (PHINode &Phi : make_early_inc_range(phis())) {
558e8d8bef9SDimitry Andric Phi.removeIncomingValue(Pred, !KeepOneInputPHIs);
559e8d8bef9SDimitry Andric if (KeepOneInputPHIs)
560e8d8bef9SDimitry Andric continue;
561e8d8bef9SDimitry Andric
562e8d8bef9SDimitry Andric // If we have a single predecessor, removeIncomingValue may have erased the
563e8d8bef9SDimitry Andric // PHI node itself.
564e8d8bef9SDimitry Andric if (NumPreds == 1)
565e8d8bef9SDimitry Andric continue;
566e8d8bef9SDimitry Andric
567e8d8bef9SDimitry Andric // Try to replace the PHI node with a constant value.
568e8d8bef9SDimitry Andric if (Value *PhiConstant = Phi.hasConstantValue()) {
569e8d8bef9SDimitry Andric Phi.replaceAllUsesWith(PhiConstant);
570e8d8bef9SDimitry Andric Phi.eraseFromParent();
5710b57cec5SDimitry Andric }
5720b57cec5SDimitry Andric }
5735ffd83dbSDimitry Andric }
5740b57cec5SDimitry Andric
canSplitPredecessors() const5750b57cec5SDimitry Andric bool BasicBlock::canSplitPredecessors() const {
5760b57cec5SDimitry Andric const Instruction *FirstNonPHI = getFirstNonPHI();
5770b57cec5SDimitry Andric if (isa<LandingPadInst>(FirstNonPHI))
5780b57cec5SDimitry Andric return true;
5790b57cec5SDimitry Andric // This is perhaps a little conservative because constructs like
5800b57cec5SDimitry Andric // CleanupBlockInst are pretty easy to split. However, SplitBlockPredecessors
5810b57cec5SDimitry Andric // cannot handle such things just yet.
5820b57cec5SDimitry Andric if (FirstNonPHI->isEHPad())
5830b57cec5SDimitry Andric return false;
5840b57cec5SDimitry Andric return true;
5850b57cec5SDimitry Andric }
5860b57cec5SDimitry Andric
isLegalToHoistInto() const5870b57cec5SDimitry Andric bool BasicBlock::isLegalToHoistInto() const {
5880b57cec5SDimitry Andric auto *Term = getTerminator();
5890b57cec5SDimitry Andric // No terminator means the block is under construction.
5900b57cec5SDimitry Andric if (!Term)
5910b57cec5SDimitry Andric return true;
5920b57cec5SDimitry Andric
5930b57cec5SDimitry Andric // If the block has no successors, there can be no instructions to hoist.
5940b57cec5SDimitry Andric assert(Term->getNumSuccessors() > 0);
5950b57cec5SDimitry Andric
5965f757f3fSDimitry Andric // Instructions should not be hoisted across special terminators, which may
5975f757f3fSDimitry Andric // have side effects or return values.
5985f757f3fSDimitry Andric return !Term->isSpecialTerminator();
5990b57cec5SDimitry Andric }
6000b57cec5SDimitry Andric
isEntryBlock() const601fe6060f1SDimitry Andric bool BasicBlock::isEntryBlock() const {
602fe6060f1SDimitry Andric const Function *F = getParent();
603fe6060f1SDimitry Andric assert(F && "Block must have a parent function to use this API");
604fe6060f1SDimitry Andric return this == &F->getEntryBlock();
605fe6060f1SDimitry Andric }
606fe6060f1SDimitry Andric
splitBasicBlock(iterator I,const Twine & BBName,bool Before)607e8d8bef9SDimitry Andric BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName,
608e8d8bef9SDimitry Andric bool Before) {
609e8d8bef9SDimitry Andric if (Before)
610e8d8bef9SDimitry Andric return splitBasicBlockBefore(I, BBName);
611e8d8bef9SDimitry Andric
6120b57cec5SDimitry Andric assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
6130b57cec5SDimitry Andric assert(I != InstList.end() &&
6140b57cec5SDimitry Andric "Trying to get me to create degenerate basic block!");
6150b57cec5SDimitry Andric
6160b57cec5SDimitry Andric BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
6170b57cec5SDimitry Andric this->getNextNode());
6180b57cec5SDimitry Andric
6190b57cec5SDimitry Andric // Save DebugLoc of split point before invalidating iterator.
6205f757f3fSDimitry Andric DebugLoc Loc = I->getStableDebugLoc();
6210b57cec5SDimitry Andric // Move all of the specified instructions from the original basic block into
6220b57cec5SDimitry Andric // the new basic block.
623bdd1243dSDimitry Andric New->splice(New->end(), this, I, end());
6240b57cec5SDimitry Andric
6250b57cec5SDimitry Andric // Add a branch instruction to the newly formed basic block.
6260b57cec5SDimitry Andric BranchInst *BI = BranchInst::Create(New, this);
6270b57cec5SDimitry Andric BI->setDebugLoc(Loc);
6280b57cec5SDimitry Andric
6290b57cec5SDimitry Andric // Now we must loop through all of the successors of the New block (which
6300b57cec5SDimitry Andric // _were_ the successors of the 'this' block), and update any PHI nodes in
6310b57cec5SDimitry Andric // successors. If there were PHI nodes in the successors, then they need to
6320b57cec5SDimitry Andric // know that incoming branches will be from New, not from Old (this).
6330b57cec5SDimitry Andric //
6340b57cec5SDimitry Andric New->replaceSuccessorsPhiUsesWith(this, New);
6350b57cec5SDimitry Andric return New;
6360b57cec5SDimitry Andric }
6370b57cec5SDimitry Andric
splitBasicBlockBefore(iterator I,const Twine & BBName)638e8d8bef9SDimitry Andric BasicBlock *BasicBlock::splitBasicBlockBefore(iterator I, const Twine &BBName) {
639e8d8bef9SDimitry Andric assert(getTerminator() &&
640e8d8bef9SDimitry Andric "Can't use splitBasicBlockBefore on degenerate BB!");
641e8d8bef9SDimitry Andric assert(I != InstList.end() &&
642e8d8bef9SDimitry Andric "Trying to get me to create degenerate basic block!");
643e8d8bef9SDimitry Andric
644e8d8bef9SDimitry Andric assert((!isa<PHINode>(*I) || getSinglePredecessor()) &&
645e8d8bef9SDimitry Andric "cannot split on multi incoming phis");
646e8d8bef9SDimitry Andric
647e8d8bef9SDimitry Andric BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(), this);
648e8d8bef9SDimitry Andric // Save DebugLoc of split point before invalidating iterator.
649e8d8bef9SDimitry Andric DebugLoc Loc = I->getDebugLoc();
650e8d8bef9SDimitry Andric // Move all of the specified instructions from the original basic block into
651e8d8bef9SDimitry Andric // the new basic block.
652bdd1243dSDimitry Andric New->splice(New->end(), this, begin(), I);
653e8d8bef9SDimitry Andric
654e8d8bef9SDimitry Andric // Loop through all of the predecessors of the 'this' block (which will be the
655e8d8bef9SDimitry Andric // predecessors of the New block), replace the specified successor 'this'
656e8d8bef9SDimitry Andric // block to point at the New block and update any PHI nodes in 'this' block.
657e8d8bef9SDimitry Andric // If there were PHI nodes in 'this' block, the PHI nodes are updated
658e8d8bef9SDimitry Andric // to reflect that the incoming branches will be from the New block and not
659e8d8bef9SDimitry Andric // from predecessors of the 'this' block.
660bdd1243dSDimitry Andric // Save predecessors to separate vector before modifying them.
661bdd1243dSDimitry Andric SmallVector<BasicBlock *, 4> Predecessors;
662bdd1243dSDimitry Andric for (BasicBlock *Pred : predecessors(this))
663bdd1243dSDimitry Andric Predecessors.push_back(Pred);
664bdd1243dSDimitry Andric for (BasicBlock *Pred : Predecessors) {
665e8d8bef9SDimitry Andric Instruction *TI = Pred->getTerminator();
666e8d8bef9SDimitry Andric TI->replaceSuccessorWith(this, New);
667e8d8bef9SDimitry Andric this->replacePhiUsesWith(Pred, New);
668e8d8bef9SDimitry Andric }
669e8d8bef9SDimitry Andric // Add a branch instruction from "New" to "this" Block.
670e8d8bef9SDimitry Andric BranchInst *BI = BranchInst::Create(this, New);
671e8d8bef9SDimitry Andric BI->setDebugLoc(Loc);
672e8d8bef9SDimitry Andric
673e8d8bef9SDimitry Andric return New;
674e8d8bef9SDimitry Andric }
675e8d8bef9SDimitry Andric
erase(BasicBlock::iterator FromIt,BasicBlock::iterator ToIt)676bdd1243dSDimitry Andric BasicBlock::iterator BasicBlock::erase(BasicBlock::iterator FromIt,
677bdd1243dSDimitry Andric BasicBlock::iterator ToIt) {
678bdd1243dSDimitry Andric return InstList.erase(FromIt, ToIt);
679bdd1243dSDimitry Andric }
680bdd1243dSDimitry Andric
replacePhiUsesWith(BasicBlock * Old,BasicBlock * New)6810b57cec5SDimitry Andric void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) {
6820b57cec5SDimitry Andric // N.B. This might not be a complete BasicBlock, so don't assume
6830b57cec5SDimitry Andric // that it ends with a non-phi instruction.
6840eae32dcSDimitry Andric for (Instruction &I : *this) {
6850eae32dcSDimitry Andric PHINode *PN = dyn_cast<PHINode>(&I);
6860b57cec5SDimitry Andric if (!PN)
6870b57cec5SDimitry Andric break;
6880b57cec5SDimitry Andric PN->replaceIncomingBlockWith(Old, New);
6890b57cec5SDimitry Andric }
6900b57cec5SDimitry Andric }
6910b57cec5SDimitry Andric
replaceSuccessorsPhiUsesWith(BasicBlock * Old,BasicBlock * New)6920b57cec5SDimitry Andric void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old,
6930b57cec5SDimitry Andric BasicBlock *New) {
6940b57cec5SDimitry Andric Instruction *TI = getTerminator();
6950b57cec5SDimitry Andric if (!TI)
6960b57cec5SDimitry Andric // Cope with being called on a BasicBlock that doesn't have a terminator
6970b57cec5SDimitry Andric // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
6980b57cec5SDimitry Andric return;
699fe6060f1SDimitry Andric for (BasicBlock *Succ : successors(TI))
7000b57cec5SDimitry Andric Succ->replacePhiUsesWith(Old, New);
7010b57cec5SDimitry Andric }
7020b57cec5SDimitry Andric
replaceSuccessorsPhiUsesWith(BasicBlock * New)7030b57cec5SDimitry Andric void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
7040b57cec5SDimitry Andric this->replaceSuccessorsPhiUsesWith(this, New);
7050b57cec5SDimitry Andric }
7060b57cec5SDimitry Andric
isLandingPad() const7070b57cec5SDimitry Andric bool BasicBlock::isLandingPad() const {
7080b57cec5SDimitry Andric return isa<LandingPadInst>(getFirstNonPHI());
7090b57cec5SDimitry Andric }
7100b57cec5SDimitry Andric
getLandingPadInst() const7110b57cec5SDimitry Andric const LandingPadInst *BasicBlock::getLandingPadInst() const {
7120b57cec5SDimitry Andric return dyn_cast<LandingPadInst>(getFirstNonPHI());
7130b57cec5SDimitry Andric }
7140b57cec5SDimitry Andric
getIrrLoopHeaderWeight() const715bdd1243dSDimitry Andric std::optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
7160b57cec5SDimitry Andric const Instruction *TI = getTerminator();
7170b57cec5SDimitry Andric if (MDNode *MDIrrLoopHeader =
7180b57cec5SDimitry Andric TI->getMetadata(LLVMContext::MD_irr_loop)) {
7190b57cec5SDimitry Andric MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0));
7200b57cec5SDimitry Andric if (MDName->getString().equals("loop_header_weight")) {
7210b57cec5SDimitry Andric auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1));
722bdd1243dSDimitry Andric return std::optional<uint64_t>(CI->getValue().getZExtValue());
7230b57cec5SDimitry Andric }
7240b57cec5SDimitry Andric }
725bdd1243dSDimitry Andric return std::nullopt;
7260b57cec5SDimitry Andric }
7270b57cec5SDimitry Andric
skipDebugIntrinsics(BasicBlock::iterator It)7280b57cec5SDimitry Andric BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
7290b57cec5SDimitry Andric while (isa<DbgInfoIntrinsic>(It))
7300b57cec5SDimitry Andric ++It;
7310b57cec5SDimitry Andric return It;
7320b57cec5SDimitry Andric }
7335ffd83dbSDimitry Andric
renumberInstructions()7345ffd83dbSDimitry Andric void BasicBlock::renumberInstructions() {
7355ffd83dbSDimitry Andric unsigned Order = 0;
7365ffd83dbSDimitry Andric for (Instruction &I : *this)
7375ffd83dbSDimitry Andric I.Order = Order++;
7385ffd83dbSDimitry Andric
7395ffd83dbSDimitry Andric // Set the bit to indicate that the instruction order valid and cached.
7405ffd83dbSDimitry Andric BasicBlockBits Bits = getBasicBlockBits();
7415ffd83dbSDimitry Andric Bits.InstrOrderValid = true;
7425ffd83dbSDimitry Andric setBasicBlockBits(Bits);
743349cc55cSDimitry Andric
744349cc55cSDimitry Andric NumInstrRenumberings++;
7455ffd83dbSDimitry Andric }
7465ffd83dbSDimitry Andric
flushTerminatorDbgValues()7475f757f3fSDimitry Andric void BasicBlock::flushTerminatorDbgValues() {
7485f757f3fSDimitry Andric // If we erase the terminator in a block, any DPValues will sink and "fall
7495f757f3fSDimitry Andric // off the end", existing after any terminator that gets inserted. With
7505f757f3fSDimitry Andric // dbg.value intrinsics we would just insert the terminator at end() and
7515f757f3fSDimitry Andric // the dbg.values would come before the terminator. With DPValues, we must
7525f757f3fSDimitry Andric // do this manually.
7535f757f3fSDimitry Andric // To get out of this unfortunate form, whenever we insert a terminator,
7545f757f3fSDimitry Andric // check whether there's anything trailing at the end and move those DPValues
7555f757f3fSDimitry Andric // in front of the terminator.
7565f757f3fSDimitry Andric
7575f757f3fSDimitry Andric // Do nothing if we're not in new debug-info format.
7585f757f3fSDimitry Andric if (!IsNewDbgInfoFormat)
7595f757f3fSDimitry Andric return;
7605f757f3fSDimitry Andric
7615f757f3fSDimitry Andric // If there's no terminator, there's nothing to do.
7625f757f3fSDimitry Andric Instruction *Term = getTerminator();
7635f757f3fSDimitry Andric if (!Term)
7645f757f3fSDimitry Andric return;
7655f757f3fSDimitry Andric
7665f757f3fSDimitry Andric // Are there any dangling DPValues?
7675f757f3fSDimitry Andric DPMarker *TrailingDPValues = getTrailingDPValues();
7685f757f3fSDimitry Andric if (!TrailingDPValues)
7695f757f3fSDimitry Andric return;
7705f757f3fSDimitry Andric
7715f757f3fSDimitry Andric // Transfer DPValues from the trailing position onto the terminator.
7725f757f3fSDimitry Andric Term->DbgMarker->absorbDebugValues(*TrailingDPValues, false);
7735f757f3fSDimitry Andric TrailingDPValues->eraseFromParent();
7745f757f3fSDimitry Andric deleteTrailingDPValues();
7755f757f3fSDimitry Andric }
7765f757f3fSDimitry Andric
spliceDebugInfoEmptyBlock(BasicBlock::iterator Dest,BasicBlock * Src,BasicBlock::iterator First,BasicBlock::iterator Last)7775f757f3fSDimitry Andric void BasicBlock::spliceDebugInfoEmptyBlock(BasicBlock::iterator Dest,
7785f757f3fSDimitry Andric BasicBlock *Src,
7795f757f3fSDimitry Andric BasicBlock::iterator First,
7805f757f3fSDimitry Andric BasicBlock::iterator Last) {
7815f757f3fSDimitry Andric // Imagine the folowing:
7825f757f3fSDimitry Andric //
7835f757f3fSDimitry Andric // bb1:
7845f757f3fSDimitry Andric // dbg.value(...
7855f757f3fSDimitry Andric // ret i32 0
7865f757f3fSDimitry Andric //
7875f757f3fSDimitry Andric // If an optimisation pass attempts to splice the contents of the block from
7885f757f3fSDimitry Andric // BB1->begin() to BB1->getTerminator(), then the dbg.value will be
7895f757f3fSDimitry Andric // transferred to the destination.
7905f757f3fSDimitry Andric // However, in the "new" DPValue format for debug-info, that range is empty:
7915f757f3fSDimitry Andric // begin() returns an iterator to the terminator, as there will only be a
7925f757f3fSDimitry Andric // single instruction in the block. We must piece together from the bits set
7935f757f3fSDimitry Andric // in the iterators whether there was the intention to transfer any debug
7945f757f3fSDimitry Andric // info.
7955f757f3fSDimitry Andric
7965f757f3fSDimitry Andric // If we're not in "new" debug-info format, do nothing.
7975f757f3fSDimitry Andric if (!IsNewDbgInfoFormat)
7985f757f3fSDimitry Andric return;
7995f757f3fSDimitry Andric
8005f757f3fSDimitry Andric assert(First == Last);
8015f757f3fSDimitry Andric bool InsertAtHead = Dest.getHeadBit();
8025f757f3fSDimitry Andric bool ReadFromHead = First.getHeadBit();
8035f757f3fSDimitry Andric
8045f757f3fSDimitry Andric // If the source block is completely empty, including no terminator, then
8055f757f3fSDimitry Andric // transfer any trailing DPValues that are still hanging around. This can
8065f757f3fSDimitry Andric // occur when a block is optimised away and the terminator has been moved
8075f757f3fSDimitry Andric // somewhere else.
8085f757f3fSDimitry Andric if (Src->empty()) {
8095f757f3fSDimitry Andric assert(Dest != end() &&
8105f757f3fSDimitry Andric "Transferring trailing DPValues to another trailing position");
8115f757f3fSDimitry Andric DPMarker *SrcTrailingDPValues = Src->getTrailingDPValues();
8125f757f3fSDimitry Andric if (!SrcTrailingDPValues)
8135f757f3fSDimitry Andric return;
8145f757f3fSDimitry Andric
8155f757f3fSDimitry Andric DPMarker *M = Dest->DbgMarker;
8165f757f3fSDimitry Andric M->absorbDebugValues(*SrcTrailingDPValues, InsertAtHead);
8175f757f3fSDimitry Andric SrcTrailingDPValues->eraseFromParent();
8185f757f3fSDimitry Andric Src->deleteTrailingDPValues();
8195f757f3fSDimitry Andric return;
8205f757f3fSDimitry Andric }
8215f757f3fSDimitry Andric
8225f757f3fSDimitry Andric // There are instructions in this block; if the First iterator was
8235f757f3fSDimitry Andric // with begin() / getFirstInsertionPt() then the caller intended debug-info
8247a6dacacSDimitry Andric // at the start of the block to be transferred. Return otherwise.
8257a6dacacSDimitry Andric if (Src->empty() || First != Src->begin() || !ReadFromHead)
8267a6dacacSDimitry Andric return;
8277a6dacacSDimitry Andric
8287a6dacacSDimitry Andric // Is there actually anything to transfer?
8297a6dacacSDimitry Andric if (!First->hasDbgValues())
8307a6dacacSDimitry Andric return;
8317a6dacacSDimitry Andric
8327a6dacacSDimitry Andric createMarker(Dest)->absorbDebugValues(*First->DbgMarker, InsertAtHead);
8335f757f3fSDimitry Andric
8345f757f3fSDimitry Andric return;
8355f757f3fSDimitry Andric }
8365f757f3fSDimitry Andric
spliceDebugInfo(BasicBlock::iterator Dest,BasicBlock * Src,BasicBlock::iterator First,BasicBlock::iterator Last)8375f757f3fSDimitry Andric void BasicBlock::spliceDebugInfo(BasicBlock::iterator Dest, BasicBlock *Src,
8385f757f3fSDimitry Andric BasicBlock::iterator First,
8395f757f3fSDimitry Andric BasicBlock::iterator Last) {
8405f757f3fSDimitry Andric /* Do a quick normalisation before calling the real splice implementation. We
8415f757f3fSDimitry Andric might be operating on a degenerate basic block that has no instructions
8425f757f3fSDimitry Andric in it, a legitimate transient state. In that case, Dest will be end() and
8435f757f3fSDimitry Andric any DPValues temporarily stored in the TrailingDPValues map in LLVMContext.
8445f757f3fSDimitry Andric We might illustrate it thus:
8455f757f3fSDimitry Andric
8465f757f3fSDimitry Andric Dest
8475f757f3fSDimitry Andric |
8485f757f3fSDimitry Andric this-block: ~~~~~~~~
8495f757f3fSDimitry Andric Src-block: ++++B---B---B---B:::C
8505f757f3fSDimitry Andric | |
8515f757f3fSDimitry Andric First Last
8525f757f3fSDimitry Andric
8535f757f3fSDimitry Andric However: does the caller expect the "~" DPValues to end up before or after
8545f757f3fSDimitry Andric the spliced segment? This is communciated in the "Head" bit of Dest, which
8555f757f3fSDimitry Andric signals whether the caller called begin() or end() on this block.
8565f757f3fSDimitry Andric
8575f757f3fSDimitry Andric If the head bit is set, then all is well, we leave DPValues trailing just
8585f757f3fSDimitry Andric like how dbg.value instructions would trail after instructions spliced to
8595f757f3fSDimitry Andric the beginning of this block.
8605f757f3fSDimitry Andric
8615f757f3fSDimitry Andric If the head bit isn't set, then try to jam the "~" DPValues onto the front
8625f757f3fSDimitry Andric of the First instruction, then splice like normal, which joins the "~"
8635f757f3fSDimitry Andric DPValues with the "+" DPValues. However if the "+" DPValues are supposed to
8645f757f3fSDimitry Andric be left behind in Src, then:
8655f757f3fSDimitry Andric * detach the "+" DPValues,
8665f757f3fSDimitry Andric * move the "~" DPValues onto First,
8675f757f3fSDimitry Andric * splice like normal,
8685f757f3fSDimitry Andric * replace the "+" DPValues onto the Last position.
8695f757f3fSDimitry Andric Complicated, but gets the job done. */
8705f757f3fSDimitry Andric
8715f757f3fSDimitry Andric // If we're inserting at end(), and not in front of dangling DPValues, then
8725f757f3fSDimitry Andric // move the DPValues onto "First". They'll then be moved naturally in the
8735f757f3fSDimitry Andric // splice process.
8745f757f3fSDimitry Andric DPMarker *MoreDanglingDPValues = nullptr;
8755f757f3fSDimitry Andric DPMarker *OurTrailingDPValues = getTrailingDPValues();
8765f757f3fSDimitry Andric if (Dest == end() && !Dest.getHeadBit() && OurTrailingDPValues) {
8775f757f3fSDimitry Andric // Are the "+" DPValues not supposed to move? If so, detach them
8785f757f3fSDimitry Andric // temporarily.
8795f757f3fSDimitry Andric if (!First.getHeadBit() && First->hasDbgValues()) {
8805f757f3fSDimitry Andric MoreDanglingDPValues = Src->getMarker(First);
8815f757f3fSDimitry Andric MoreDanglingDPValues->removeFromParent();
8825f757f3fSDimitry Andric }
8835f757f3fSDimitry Andric
8845f757f3fSDimitry Andric if (First->hasDbgValues()) {
8855f757f3fSDimitry Andric DPMarker *CurMarker = Src->getMarker(First);
8865f757f3fSDimitry Andric // Place them at the front, it would look like this:
8875f757f3fSDimitry Andric // Dest
8885f757f3fSDimitry Andric // |
8895f757f3fSDimitry Andric // this-block:
8905f757f3fSDimitry Andric // Src-block: ~~~~~~~~++++B---B---B---B:::C
8915f757f3fSDimitry Andric // | |
8925f757f3fSDimitry Andric // First Last
8935f757f3fSDimitry Andric CurMarker->absorbDebugValues(*OurTrailingDPValues, true);
8945f757f3fSDimitry Andric OurTrailingDPValues->eraseFromParent();
8955f757f3fSDimitry Andric } else {
8965f757f3fSDimitry Andric // No current marker, create one and absorb in. (FIXME: we can avoid an
8975f757f3fSDimitry Andric // allocation in the future).
8985f757f3fSDimitry Andric DPMarker *CurMarker = Src->createMarker(&*First);
8995f757f3fSDimitry Andric CurMarker->absorbDebugValues(*OurTrailingDPValues, false);
9005f757f3fSDimitry Andric OurTrailingDPValues->eraseFromParent();
9015f757f3fSDimitry Andric }
9025f757f3fSDimitry Andric deleteTrailingDPValues();
9035f757f3fSDimitry Andric First.setHeadBit(true);
9045f757f3fSDimitry Andric }
9055f757f3fSDimitry Andric
9065f757f3fSDimitry Andric // Call the main debug-info-splicing implementation.
9075f757f3fSDimitry Andric spliceDebugInfoImpl(Dest, Src, First, Last);
9085f757f3fSDimitry Andric
9095f757f3fSDimitry Andric // Do we have some "+" DPValues hanging around that weren't supposed to move,
9105f757f3fSDimitry Andric // and we detached to make things easier?
9115f757f3fSDimitry Andric if (!MoreDanglingDPValues)
9125f757f3fSDimitry Andric return;
9135f757f3fSDimitry Andric
9145f757f3fSDimitry Andric // FIXME: we could avoid an allocation here sometimes.
9155f757f3fSDimitry Andric DPMarker *LastMarker = Src->createMarker(Last);
9165f757f3fSDimitry Andric LastMarker->absorbDebugValues(*MoreDanglingDPValues, true);
9175f757f3fSDimitry Andric MoreDanglingDPValues->eraseFromParent();
9185f757f3fSDimitry Andric }
9195f757f3fSDimitry Andric
spliceDebugInfoImpl(BasicBlock::iterator Dest,BasicBlock * Src,BasicBlock::iterator First,BasicBlock::iterator Last)9205f757f3fSDimitry Andric void BasicBlock::spliceDebugInfoImpl(BasicBlock::iterator Dest, BasicBlock *Src,
9215f757f3fSDimitry Andric BasicBlock::iterator First,
9225f757f3fSDimitry Andric BasicBlock::iterator Last) {
9235f757f3fSDimitry Andric // Find out where to _place_ these dbg.values; if InsertAtHead is specified,
9245f757f3fSDimitry Andric // this will be at the start of Dest's debug value range, otherwise this is
9255f757f3fSDimitry Andric // just Dest's marker.
9265f757f3fSDimitry Andric bool InsertAtHead = Dest.getHeadBit();
9275f757f3fSDimitry Andric bool ReadFromHead = First.getHeadBit();
9285f757f3fSDimitry Andric // Use this flag to signal the abnormal case, where we don't want to copy the
9295f757f3fSDimitry Andric // DPValues ahead of the "Last" position.
9305f757f3fSDimitry Andric bool ReadFromTail = !Last.getTailBit();
9315f757f3fSDimitry Andric bool LastIsEnd = (Last == Src->end());
9325f757f3fSDimitry Andric
9335f757f3fSDimitry Andric /*
9345f757f3fSDimitry Andric Here's an illustration of what we're about to do. We have two blocks, this
9355f757f3fSDimitry Andric and Src, and two segments of list. Each instruction is marked by a capital
9365f757f3fSDimitry Andric while potential DPValue debug-info is marked out by "-" characters and a few
9375f757f3fSDimitry Andric other special characters (+:=) where I want to highlight what's going on.
9385f757f3fSDimitry Andric
9395f757f3fSDimitry Andric Dest
9405f757f3fSDimitry Andric |
9415f757f3fSDimitry Andric this-block: A----A----A ====A----A----A----A---A---A
9425f757f3fSDimitry Andric Src-block ++++B---B---B---B:::C
9435f757f3fSDimitry Andric | |
9445f757f3fSDimitry Andric First Last
9455f757f3fSDimitry Andric
9465f757f3fSDimitry Andric The splice method is going to take all the instructions from First up to
9475f757f3fSDimitry Andric (but not including) Last and insert them in _front_ of Dest, forming one
9485f757f3fSDimitry Andric long list. All the DPValues attached to instructions _between_ First and
9495f757f3fSDimitry Andric Last need no maintenence. However, we have to do special things with the
9505f757f3fSDimitry Andric DPValues marked with the +:= characters. We only have three positions:
9515f757f3fSDimitry Andric should the "+" DPValues be transferred, and if so to where? Do we move the
9525f757f3fSDimitry Andric ":" DPValues? Would they go in front of the "=" DPValues, or should the "="
9535f757f3fSDimitry Andric DPValues go before "+" DPValues?
9545f757f3fSDimitry Andric
9555f757f3fSDimitry Andric We're told which way it should be by the bits carried in the iterators. The
9565f757f3fSDimitry Andric "Head" bit indicates whether the specified position is supposed to be at the
9575f757f3fSDimitry Andric front of the attached DPValues (true) or not (false). The Tail bit is true
9585f757f3fSDimitry Andric on the other end of a range: is the range intended to include DPValues up to
9595f757f3fSDimitry Andric the end (false) or not (true).
9605f757f3fSDimitry Andric
9615f757f3fSDimitry Andric FIXME: the tail bit doesn't need to be distinct from the head bit, we could
9625f757f3fSDimitry Andric combine them.
9635f757f3fSDimitry Andric
9645f757f3fSDimitry Andric Here are some examples of different configurations:
9655f757f3fSDimitry Andric
9665f757f3fSDimitry Andric Dest.Head = true, First.Head = true, Last.Tail = false
9675f757f3fSDimitry Andric
9685f757f3fSDimitry Andric this-block: A----A----A++++B---B---B---B:::====A----A----A----A---A---A
9695f757f3fSDimitry Andric | |
9705f757f3fSDimitry Andric First Dest
9715f757f3fSDimitry Andric
9725f757f3fSDimitry Andric Wheras if we didn't want to read from the Src list,
9735f757f3fSDimitry Andric
9745f757f3fSDimitry Andric Dest.Head = true, First.Head = false, Last.Tail = false
9755f757f3fSDimitry Andric
9765f757f3fSDimitry Andric this-block: A----A----AB---B---B---B:::====A----A----A----A---A---A
9775f757f3fSDimitry Andric | |
9785f757f3fSDimitry Andric First Dest
9795f757f3fSDimitry Andric
9805f757f3fSDimitry Andric Or if we didn't want to insert at the head of Dest:
9815f757f3fSDimitry Andric
9825f757f3fSDimitry Andric Dest.Head = false, First.Head = false, Last.Tail = false
9835f757f3fSDimitry Andric
9845f757f3fSDimitry Andric this-block: A----A----A====B---B---B---B:::A----A----A----A---A---A
9855f757f3fSDimitry Andric | |
9865f757f3fSDimitry Andric First Dest
9875f757f3fSDimitry Andric
9885f757f3fSDimitry Andric Tests for these various configurations can be found in the unit test file
9895f757f3fSDimitry Andric BasicBlockDbgInfoTest.cpp.
9905f757f3fSDimitry Andric
9915f757f3fSDimitry Andric */
9925f757f3fSDimitry Andric
9935f757f3fSDimitry Andric // Detach the marker at Dest -- this lets us move the "====" DPValues around.
9945f757f3fSDimitry Andric DPMarker *DestMarker = nullptr;
9955f757f3fSDimitry Andric if (Dest != end()) {
9965f757f3fSDimitry Andric DestMarker = getMarker(Dest);
9975f757f3fSDimitry Andric DestMarker->removeFromParent();
9985f757f3fSDimitry Andric createMarker(&*Dest);
9995f757f3fSDimitry Andric }
10005f757f3fSDimitry Andric
10015f757f3fSDimitry Andric // If we're moving the tail range of DPValues (":::"), absorb them into the
10025f757f3fSDimitry Andric // front of the DPValues at Dest.
10035f757f3fSDimitry Andric if (ReadFromTail && Src->getMarker(Last)) {
10045f757f3fSDimitry Andric DPMarker *OntoDest = getMarker(Dest);
10055f757f3fSDimitry Andric DPMarker *FromLast = Src->getMarker(Last);
10065f757f3fSDimitry Andric OntoDest->absorbDebugValues(*FromLast, true);
10075f757f3fSDimitry Andric if (LastIsEnd) {
10085f757f3fSDimitry Andric FromLast->eraseFromParent();
10095f757f3fSDimitry Andric Src->deleteTrailingDPValues();
10105f757f3fSDimitry Andric }
10115f757f3fSDimitry Andric }
10125f757f3fSDimitry Andric
10135f757f3fSDimitry Andric // If we're _not_ reading from the head of First, i.e. the "++++" DPValues,
10145f757f3fSDimitry Andric // move their markers onto Last. They remain in the Src block. No action
10155f757f3fSDimitry Andric // needed.
10165f757f3fSDimitry Andric if (!ReadFromHead && First->hasDbgValues()) {
10175f757f3fSDimitry Andric DPMarker *OntoLast = Src->createMarker(Last);
10185f757f3fSDimitry Andric DPMarker *FromFirst = Src->createMarker(First);
10195f757f3fSDimitry Andric OntoLast->absorbDebugValues(*FromFirst,
10205f757f3fSDimitry Andric true); // Always insert at head of it.
10215f757f3fSDimitry Andric }
10225f757f3fSDimitry Andric
10235f757f3fSDimitry Andric // Finally, do something with the "====" DPValues we detached.
10245f757f3fSDimitry Andric if (DestMarker) {
10255f757f3fSDimitry Andric if (InsertAtHead) {
10265f757f3fSDimitry Andric // Insert them at the end of the DPValues at Dest. The "::::" DPValues
10275f757f3fSDimitry Andric // might be in front of them.
10285f757f3fSDimitry Andric DPMarker *NewDestMarker = getMarker(Dest);
10295f757f3fSDimitry Andric NewDestMarker->absorbDebugValues(*DestMarker, false);
10305f757f3fSDimitry Andric } else {
10315f757f3fSDimitry Andric // Insert them right at the start of the range we moved, ahead of First
10325f757f3fSDimitry Andric // and the "++++" DPValues.
10335f757f3fSDimitry Andric DPMarker *FirstMarker = getMarker(First);
10345f757f3fSDimitry Andric FirstMarker->absorbDebugValues(*DestMarker, true);
10355f757f3fSDimitry Andric }
10365f757f3fSDimitry Andric DestMarker->eraseFromParent();
10375f757f3fSDimitry Andric } else if (Dest == end() && !InsertAtHead) {
10385f757f3fSDimitry Andric // In the rare circumstance where we insert at end(), and we did not
10395f757f3fSDimitry Andric // generate the iterator with begin() / getFirstInsertionPt(), it means
10405f757f3fSDimitry Andric // any trailing debug-info at the end of the block would "normally" have
10415f757f3fSDimitry Andric // been pushed in front of "First". Move it there now.
10425f757f3fSDimitry Andric DPMarker *FirstMarker = getMarker(First);
10435f757f3fSDimitry Andric DPMarker *TrailingDPValues = getTrailingDPValues();
10445f757f3fSDimitry Andric if (TrailingDPValues) {
10455f757f3fSDimitry Andric FirstMarker->absorbDebugValues(*TrailingDPValues, true);
10465f757f3fSDimitry Andric TrailingDPValues->eraseFromParent();
10475f757f3fSDimitry Andric deleteTrailingDPValues();
10485f757f3fSDimitry Andric }
10495f757f3fSDimitry Andric }
10505f757f3fSDimitry Andric }
10515f757f3fSDimitry Andric
splice(iterator Dest,BasicBlock * Src,iterator First,iterator Last)10525f757f3fSDimitry Andric void BasicBlock::splice(iterator Dest, BasicBlock *Src, iterator First,
10535f757f3fSDimitry Andric iterator Last) {
10545f757f3fSDimitry Andric assert(Src->IsNewDbgInfoFormat == IsNewDbgInfoFormat);
10555f757f3fSDimitry Andric
10565f757f3fSDimitry Andric #ifdef EXPENSIVE_CHECKS
10575f757f3fSDimitry Andric // Check that First is before Last.
10585f757f3fSDimitry Andric auto FromBBEnd = Src->end();
10595f757f3fSDimitry Andric for (auto It = First; It != Last; ++It)
10605f757f3fSDimitry Andric assert(It != FromBBEnd && "FromBeginIt not before FromEndIt!");
10615f757f3fSDimitry Andric #endif // EXPENSIVE_CHECKS
10625f757f3fSDimitry Andric
10635f757f3fSDimitry Andric // Lots of horrible special casing for empty transfers: the dbg.values between
10645f757f3fSDimitry Andric // two positions could be spliced in dbg.value mode.
10655f757f3fSDimitry Andric if (First == Last) {
10665f757f3fSDimitry Andric spliceDebugInfoEmptyBlock(Dest, Src, First, Last);
10675f757f3fSDimitry Andric return;
10685f757f3fSDimitry Andric }
10695f757f3fSDimitry Andric
10705f757f3fSDimitry Andric // Handle non-instr debug-info specific juggling.
10715f757f3fSDimitry Andric if (IsNewDbgInfoFormat)
10725f757f3fSDimitry Andric spliceDebugInfo(Dest, Src, First, Last);
10735f757f3fSDimitry Andric
10745f757f3fSDimitry Andric // And move the instructions.
10755f757f3fSDimitry Andric getInstList().splice(Dest, Src->getInstList(), First, Last);
10765f757f3fSDimitry Andric
10775f757f3fSDimitry Andric flushTerminatorDbgValues();
10785f757f3fSDimitry Andric }
10795f757f3fSDimitry Andric
insertDPValueAfter(DPValue * DPV,Instruction * I)10805f757f3fSDimitry Andric void BasicBlock::insertDPValueAfter(DPValue *DPV, Instruction *I) {
10815f757f3fSDimitry Andric assert(IsNewDbgInfoFormat);
10825f757f3fSDimitry Andric assert(I->getParent() == this);
10835f757f3fSDimitry Andric
10845f757f3fSDimitry Andric iterator NextIt = std::next(I->getIterator());
10855f757f3fSDimitry Andric DPMarker *NextMarker = getMarker(NextIt);
10865f757f3fSDimitry Andric if (!NextMarker)
10875f757f3fSDimitry Andric NextMarker = createMarker(NextIt);
10885f757f3fSDimitry Andric NextMarker->insertDPValue(DPV, true);
10895f757f3fSDimitry Andric }
10905f757f3fSDimitry Andric
insertDPValueBefore(DPValue * DPV,InstListType::iterator Where)10915f757f3fSDimitry Andric void BasicBlock::insertDPValueBefore(DPValue *DPV,
10925f757f3fSDimitry Andric InstListType::iterator Where) {
10935f757f3fSDimitry Andric // We should never directly insert at the end of the block, new DPValues
10945f757f3fSDimitry Andric // shouldn't be generated at times when there's no terminator.
10955f757f3fSDimitry Andric assert(Where != end());
10965f757f3fSDimitry Andric assert(Where->getParent() == this);
10975f757f3fSDimitry Andric if (!Where->DbgMarker)
10985f757f3fSDimitry Andric createMarker(Where);
10995f757f3fSDimitry Andric bool InsertAtHead = Where.getHeadBit();
11005f757f3fSDimitry Andric Where->DbgMarker->insertDPValue(DPV, InsertAtHead);
11015f757f3fSDimitry Andric }
11025f757f3fSDimitry Andric
getNextMarker(Instruction * I)11035f757f3fSDimitry Andric DPMarker *BasicBlock::getNextMarker(Instruction *I) {
11045f757f3fSDimitry Andric return getMarker(std::next(I->getIterator()));
11055f757f3fSDimitry Andric }
11065f757f3fSDimitry Andric
getMarker(InstListType::iterator It)11075f757f3fSDimitry Andric DPMarker *BasicBlock::getMarker(InstListType::iterator It) {
11085f757f3fSDimitry Andric if (It == end()) {
11095f757f3fSDimitry Andric DPMarker *DPM = getTrailingDPValues();
11105f757f3fSDimitry Andric return DPM;
11115f757f3fSDimitry Andric }
11125f757f3fSDimitry Andric return It->DbgMarker;
11135f757f3fSDimitry Andric }
11145f757f3fSDimitry Andric
reinsertInstInDPValues(Instruction * I,std::optional<DPValue::self_iterator> Pos)11155f757f3fSDimitry Andric void BasicBlock::reinsertInstInDPValues(
11165f757f3fSDimitry Andric Instruction *I, std::optional<DPValue::self_iterator> Pos) {
11175f757f3fSDimitry Andric // "I" was originally removed from a position where it was
11185f757f3fSDimitry Andric // immediately in front of Pos. Any DPValues on that position then "fell down"
11195f757f3fSDimitry Andric // onto Pos. "I" has been re-inserted at the front of that wedge of DPValues,
11205f757f3fSDimitry Andric // shuffle them around to represent the original positioning. To illustrate:
11215f757f3fSDimitry Andric //
11225f757f3fSDimitry Andric // Instructions: I1---I---I0
11235f757f3fSDimitry Andric // DPValues: DDD DDD
11245f757f3fSDimitry Andric //
11255f757f3fSDimitry Andric // Instruction "I" removed,
11265f757f3fSDimitry Andric //
11275f757f3fSDimitry Andric // Instructions: I1------I0
11285f757f3fSDimitry Andric // DPValues: DDDDDD
11295f757f3fSDimitry Andric // ^Pos
11305f757f3fSDimitry Andric //
11315f757f3fSDimitry Andric // Instruction "I" re-inserted (now):
11325f757f3fSDimitry Andric //
11335f757f3fSDimitry Andric // Instructions: I1---I------I0
11345f757f3fSDimitry Andric // DPValues: DDDDDD
11355f757f3fSDimitry Andric // ^Pos
11365f757f3fSDimitry Andric //
11375f757f3fSDimitry Andric // After this method completes:
11385f757f3fSDimitry Andric //
11395f757f3fSDimitry Andric // Instructions: I1---I---I0
11405f757f3fSDimitry Andric // DPValues: DDD DDD
11415f757f3fSDimitry Andric
11425f757f3fSDimitry Andric // This happens if there were no DPValues on I0. Are there now DPValues there?
11435f757f3fSDimitry Andric if (!Pos) {
11445f757f3fSDimitry Andric DPMarker *NextMarker = getNextMarker(I);
11455f757f3fSDimitry Andric if (!NextMarker)
11465f757f3fSDimitry Andric return;
11475f757f3fSDimitry Andric if (NextMarker->StoredDPValues.empty())
11485f757f3fSDimitry Andric return;
11495f757f3fSDimitry Andric // There are DPMarkers there now -- they fell down from "I".
11505f757f3fSDimitry Andric DPMarker *ThisMarker = createMarker(I);
11515f757f3fSDimitry Andric ThisMarker->absorbDebugValues(*NextMarker, false);
11525f757f3fSDimitry Andric return;
11535f757f3fSDimitry Andric }
11545f757f3fSDimitry Andric
11555f757f3fSDimitry Andric // Is there even a range of DPValues to move?
11565f757f3fSDimitry Andric DPMarker *DPM = (*Pos)->getMarker();
11575f757f3fSDimitry Andric auto Range = make_range(DPM->StoredDPValues.begin(), (*Pos));
11585f757f3fSDimitry Andric if (Range.begin() == Range.end())
11595f757f3fSDimitry Andric return;
11605f757f3fSDimitry Andric
11615f757f3fSDimitry Andric // Otherwise: splice.
11625f757f3fSDimitry Andric DPMarker *ThisMarker = createMarker(I);
11635f757f3fSDimitry Andric assert(ThisMarker->StoredDPValues.empty());
11645f757f3fSDimitry Andric ThisMarker->absorbDebugValues(Range, *DPM, true);
11655f757f3fSDimitry Andric }
11665f757f3fSDimitry Andric
11675ffd83dbSDimitry Andric #ifndef NDEBUG
11685ffd83dbSDimitry Andric /// In asserts builds, this checks the numbering. In non-asserts builds, it
11695ffd83dbSDimitry Andric /// is defined as a no-op inline function in BasicBlock.h.
validateInstrOrdering() const11705ffd83dbSDimitry Andric void BasicBlock::validateInstrOrdering() const {
11715ffd83dbSDimitry Andric if (!isInstrOrderValid())
11725ffd83dbSDimitry Andric return;
11735ffd83dbSDimitry Andric const Instruction *Prev = nullptr;
11745ffd83dbSDimitry Andric for (const Instruction &I : *this) {
11755ffd83dbSDimitry Andric assert((!Prev || Prev->comesBefore(&I)) &&
11765ffd83dbSDimitry Andric "cached instruction ordering is incorrect");
11775ffd83dbSDimitry Andric Prev = &I;
11785ffd83dbSDimitry Andric }
11795ffd83dbSDimitry Andric }
11805ffd83dbSDimitry Andric #endif
11815f757f3fSDimitry Andric
setTrailingDPValues(DPMarker * foo)11825f757f3fSDimitry Andric void BasicBlock::setTrailingDPValues(DPMarker *foo) {
11835f757f3fSDimitry Andric getContext().pImpl->setTrailingDPValues(this, foo);
11845f757f3fSDimitry Andric }
11855f757f3fSDimitry Andric
getTrailingDPValues()11865f757f3fSDimitry Andric DPMarker *BasicBlock::getTrailingDPValues() {
11875f757f3fSDimitry Andric return getContext().pImpl->getTrailingDPValues(this);
11885f757f3fSDimitry Andric }
11895f757f3fSDimitry Andric
deleteTrailingDPValues()11905f757f3fSDimitry Andric void BasicBlock::deleteTrailingDPValues() {
11915f757f3fSDimitry Andric getContext().pImpl->deleteTrailingDPValues(this);
11925f757f3fSDimitry Andric }
11935f757f3fSDimitry Andric
1194