diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h --- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h +++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h @@ -517,11 +517,13 @@ return getSectionID() == MBB->getSectionID(); } - /// Update the terminator instructions in block to account for changes to the - /// layout. If the block previously used a fallthrough, it may now need a - /// branch, and if it previously used branching it may now be able to use a - /// fallthrough. - void updateTerminator(); + /// Update the terminator instructions in block to account for changes to + /// block layout which may have been made. PreviousLayoutSuccessor should be + /// set to the block which may have been used as fallthrough before the block + /// layout was modified. If the block previously fell through to that block, + /// it may now need a branch. If it previously branched to another block, it + /// may now be able to fallthrough to the current layout successor. + void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor); // Machine-CFG mutators diff --git a/llvm/lib/CodeGen/BBSectionsPrepare.cpp b/llvm/lib/CodeGen/BBSectionsPrepare.cpp --- a/llvm/lib/CodeGen/BBSectionsPrepare.cpp +++ b/llvm/lib/CodeGen/BBSectionsPrepare.cpp @@ -180,7 +180,7 @@ MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch. if (TII->analyzeBranch(MBB, TBB, FBB, Cond)) continue; - MBB.updateTerminator(); + MBB.updateTerminator(FTMBB); } } diff --git a/llvm/lib/CodeGen/BranchRelaxation.cpp b/llvm/lib/CodeGen/BranchRelaxation.cpp --- a/llvm/lib/CodeGen/BranchRelaxation.cpp +++ b/llvm/lib/CodeGen/BranchRelaxation.cpp @@ -245,8 +245,7 @@ // Cleanup potential unconditional branch to successor block. // Note that updateTerminator may change the size of the blocks. - NewBB->updateTerminator(); - OrigBB->updateTerminator(); + OrigBB->updateTerminator(NewBB); // Figure out how large the OrigBB is. As the first half of the original // block, it cannot contain a tablejump. The size includes diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp --- a/llvm/lib/CodeGen/MachineBasicBlock.cpp +++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp @@ -559,7 +559,11 @@ getParent()->splice(++NewBefore->getIterator(), getIterator()); } -void MachineBasicBlock::updateTerminator() { +void MachineBasicBlock::updateTerminator( + MachineBasicBlock *PreviousLayoutSuccessor) { + LLVM_DEBUG(dbgs() << "Updating terminators on " << printMBBReference(*this) + << "\n"); + const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo(); // A block with no successors has no concerns with fall-through edges. if (this->succ_empty()) @@ -578,25 +582,21 @@ if (isLayoutSuccessor(TBB)) TII->removeBranch(*this); } else { - // The block has an unconditional fallthrough. If its successor is not 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)->isEHPad()) - continue; - assert(!TBB && "Found more than one non-landing-pad successor!"); - TBB = *SI; - } - - // If there is no non-landing-pad successor, the block has no fall-through - // edges to be concerned with. - if (!TBB) + // The block has an unconditional fallthrough, or the end of the block is + // unreachable. + + // Unfortunately, whether the end of the block is unreachable is not + // immediately obvious; we must fall back to checking the successor list, + // and assuming that if the passed in block is in the succesor list and + // not an EHPad, it must be the intended target. + if (!PreviousLayoutSuccessor || !isSuccessor(PreviousLayoutSuccessor) + || PreviousLayoutSuccessor->isEHPad()) return; - // 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); + // If the unconditional successor block is not the current layout + // successor, insert a branch to jump to it. + if (!isLayoutSuccessor(PreviousLayoutSuccessor)) + TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL); } return; } @@ -617,38 +617,19 @@ return; } - // Walk through the successors and find the successor which is not a landing - // pad and is not the conditional branch destination (in TBB) as the - // fallthrough successor. - MachineBasicBlock *FallthroughBB = nullptr; - for (succ_iterator SI = succ_begin(), SE = succ_end(); SI != SE; ++SI) { - if ((*SI)->isEHPad() || *SI == TBB) - continue; - assert(!FallthroughBB && "Found more than one fallthrough successor."); - FallthroughBB = *SI; - } - - if (!FallthroughBB) { - if (canFallThrough()) { - // 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. - 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); - return; - } + // We now know we're going to fallthrough to PreviousLayoutSuccessor. + assert(PreviousLayoutSuccessor); + assert(isSuccessor(PreviousLayoutSuccessor)); - // We enter here iff exactly one successor is TBB which cannot fallthrough - // and the rest successors if any are EHPads. In this case, we need to - // change the conditional branch into unconditional branch. + if (PreviousLayoutSuccessor == TBB) { + // We had a fallthrough to the same basic block as the conditional jump + // targets. Remove the conditional jump, leaving an unconditional + // fallthrough or an unconditional jump. TII->removeBranch(*this); - Cond.clear(); - TII->insertBranch(*this, TBB, nullptr, Cond, DL); + if (!isLayoutSuccessor(TBB)) { + Cond.clear(); + TII->insertBranch(*this, TBB, nullptr, Cond, DL); + } return; } @@ -657,14 +638,14 @@ 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, PreviousLayoutSuccessor, nullptr, Cond, DL); return; } TII->removeBranch(*this); - TII->insertBranch(*this, FallthroughBB, nullptr, Cond, DL); - } else if (!isLayoutSuccessor(FallthroughBB)) { + TII->insertBranch(*this, PreviousLayoutSuccessor, nullptr, Cond, DL); + } else if (!isLayoutSuccessor(PreviousLayoutSuccessor)) { TII->removeBranch(*this); - TII->insertBranch(*this, TBB, FallthroughBB, Cond, DL); + TII->insertBranch(*this, TBB, PreviousLayoutSuccessor, Cond, DL); } } @@ -908,6 +889,7 @@ return nullptr; MachineFunction *MF = getParent(); + MachineBasicBlock *PrevFallthrough = getNextNode(); DebugLoc DL; // FIXME: this is nowhere MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); @@ -978,7 +960,11 @@ Terminators.push_back(&*I); } - updateTerminator(); + // Since we replaced all uses of Succ with NMBB, that should also be treated + // as the fallthrough successor + if (Succ == PrevFallthrough) + PrevFallthrough = NMBB; + updateTerminator(PrevFallthrough); if (Indexes) { SmallVector NewTerminators; diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp --- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp +++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp @@ -2703,6 +2703,20 @@ assert(!BadFunc && "Detected problems with the block placement."); }); + // Remember original layout ordering, so we can update terminators after + // reordering to point to the original layout successor. + SmallVector OriginalLayoutSuccessors( + F->getNumBlockIDs()); + { + MachineBasicBlock *LastMBB = nullptr; + for (auto &MBB : *F) { + if (LastMBB != nullptr) + OriginalLayoutSuccessors[LastMBB->getNumber()] = &MBB; + LastMBB = &MBB; + } + OriginalLayoutSuccessors[F->back().getNumber()] = nullptr; + } + // Splice the blocks into place. MachineFunction::iterator InsertPos = F->begin(); LLVM_DEBUG(dbgs() << "[MBP] Function: " << F->getName() << "\n"); @@ -2760,15 +2774,18 @@ // TBB = FBB = nullptr; // } // } - if (!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond)) - PrevBB->updateTerminator(); + if (!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond)) { + PrevBB->updateTerminator(OriginalLayoutSuccessors[PrevBB->getNumber()]); + } } // Fixup the last block. Cond.clear(); MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch. - if (!TII->analyzeBranch(F->back(), TBB, FBB, Cond)) - F->back().updateTerminator(); + if (!TII->analyzeBranch(F->back(), TBB, FBB, Cond)) { + MachineBasicBlock *PrevBB = &F->back(); + PrevBB->updateTerminator(OriginalLayoutSuccessors[PrevBB->getNumber()]); + } BlockWorkList.clear(); EHPadWorkList.clear(); @@ -2802,7 +2819,6 @@ DebugLoc dl; // FIXME: this is nowhere TII->removeBranch(*ChainBB); TII->insertBranch(*ChainBB, FBB, TBB, Cond, dl); - ChainBB->updateTerminator(); } } } diff --git a/llvm/lib/CodeGen/TailDuplicator.cpp b/llvm/lib/CodeGen/TailDuplicator.cpp --- a/llvm/lib/CodeGen/TailDuplicator.cpp +++ b/llvm/lib/CodeGen/TailDuplicator.cpp @@ -813,6 +813,8 @@ LLVM_DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB) << '\n'); + bool ShouldUpdateTerminators = TailBB->canFallThrough(); + DenseSet UsedByPhi; getRegsUsedByPHIs(*TailBB, &UsedByPhi); @@ -885,6 +887,10 @@ for (MachineBasicBlock *Succ : TailBB->successors()) PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ)); + // Update branches in pred to jump to tail's layout successor if needed. + if (ShouldUpdateTerminators) + PredBB->updateTerminator(TailBB->getNextNode()); + Changed = true; ++NumTailDups; } @@ -943,6 +949,11 @@ PrevBB->removeSuccessor(PrevBB->succ_begin()); assert(PrevBB->succ_empty()); PrevBB->transferSuccessors(TailBB); + + // Update branches in PrevBB based on Tail's layout successor. + if (ShouldUpdateTerminators) + PrevBB->updateTerminator(TailBB->getNextNode()); + TDBBs.push_back(PrevBB); Changed = true; } diff --git a/llvm/lib/Target/AArch64/AArch64ConditionOptimizer.cpp b/llvm/lib/Target/AArch64/AArch64ConditionOptimizer.cpp --- a/llvm/lib/Target/AArch64/AArch64ConditionOptimizer.cpp +++ b/llvm/lib/Target/AArch64/AArch64ConditionOptimizer.cpp @@ -295,8 +295,6 @@ .add(BrMI.getOperand(1)); BrMI.eraseFromParent(); - MBB->updateTerminator(); - ++NumConditionsAdjusted; } diff --git a/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp b/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp --- a/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp +++ b/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp @@ -710,7 +710,7 @@ .add(CmpMI->getOperand(1)); // Branch target. } CmpMI->eraseFromParent(); - Head->updateTerminator(); + Head->updateTerminator(CmpBB->getNextNode()); RemovedBlocks.push_back(CmpBB); CmpBB->eraseFromParent(); diff --git a/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp b/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp --- a/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp +++ b/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp @@ -2361,6 +2361,7 @@ SmallVector CondPrior; MachineFunction::iterator BBi = BB->getIterator(); MachineFunction::iterator OldPrior = std::prev(BBi); + MachineFunction::iterator OldNext = std::next(BBi); // If the block terminator isn't analyzable, don't try to move the block bool B = TII->analyzeBranch(*BB, TBB, FBB, Cond); @@ -2371,8 +2372,8 @@ if (!B && Cond.empty() && BB != &MF->front() && !TII->analyzeBranch(*OldPrior, TBB, FBB, CondPrior)) { BB->moveAfter(JTBB); - OldPrior->updateTerminator(); - BB->updateTerminator(); + OldPrior->updateTerminator(BB); + BB->updateTerminator(OldNext != MF->end() ? &*OldNext : nullptr); // Update numbering to account for the block being moved. MF->RenumberBlocks(); ++NumJTMoved; diff --git a/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp b/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp --- a/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp +++ b/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp @@ -1017,18 +1017,20 @@ PredB->removeSuccessor(SuccB); PredB->splice(PredB->end(), SuccB, SuccB->begin(), SuccB->end()); PredB->transferSuccessorsAndUpdatePHIs(SuccB); + MachineBasicBlock *OldLayoutSuccessor = SuccB->getNextNode(); removeBlock(SuccB); if (!TermOk) - PredB->updateTerminator(); + PredB->updateTerminator(OldLayoutSuccessor); } void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) { + MachineBasicBlock *OldLayoutSuccessor = FP.SplitB->getNextNode(); if (FP.TrueB) removeBlock(FP.TrueB); if (FP.FalseB) removeBlock(FP.FalseB); - FP.SplitB->updateTerminator(); + FP.SplitB->updateTerminator(OldLayoutSuccessor); if (FP.SplitB->succ_size() != 1) return; diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp b/llvm/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp --- a/llvm/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp +++ b/llvm/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp @@ -159,8 +159,16 @@ } assert((AnyBarrier || AllAnalyzable) && "analyzeBranch needs to analyze any block with a fallthrough"); + + // Find the layout successor from the original block order. + MachineFunction *MF = MBB->getParent(); + MachineBasicBlock *OriginalSuccessor = + unsigned(MBB->getNumber() + 1) < MF->getNumBlockIDs() + ? MF->getBlockNumbered(MBB->getNumber() + 1) + : nullptr; + if (AllAnalyzable) - MBB->updateTerminator(); + MBB->updateTerminator(OriginalSuccessor); } namespace { @@ -247,9 +255,12 @@ static void sortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI, const MachineDominatorTree &MDT) { + // Remember original layout ordering, so we can update terminators after + // reordering to point to the original layout successor. + MF.RenumberBlocks(); + // Prepare for a topological sort: Record the number of predecessors each // block has, ignoring loop backedges. - MF.RenumberBlocks(); SmallVector NumPredsLeft(MF.getNumBlockIDs(), 0); for (MachineBasicBlock &MBB : MF) { unsigned N = MBB.pred_size();