1104 lines · cpp
1//===- TailDuplicator.cpp - Duplicate blocks into predecessors' tails -----===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This utility class duplicates basic blocks ending in unconditional branches10// into the tails of their predecessors.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/CodeGen/TailDuplicator.h"15#include "llvm/ADT/DenseMap.h"16#include "llvm/ADT/DenseSet.h"17#include "llvm/ADT/STLExtras.h"18#include "llvm/ADT/SetVector.h"19#include "llvm/ADT/SmallPtrSet.h"20#include "llvm/ADT/SmallVector.h"21#include "llvm/ADT/Statistic.h"22#include "llvm/CodeGen/MachineBasicBlock.h"23#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"24#include "llvm/CodeGen/MachineFunction.h"25#include "llvm/CodeGen/MachineInstr.h"26#include "llvm/CodeGen/MachineInstrBuilder.h"27#include "llvm/CodeGen/MachineOperand.h"28#include "llvm/CodeGen/MachineRegisterInfo.h"29#include "llvm/CodeGen/MachineSSAUpdater.h"30#include "llvm/CodeGen/MachineSizeOpts.h"31#include "llvm/CodeGen/TargetInstrInfo.h"32#include "llvm/CodeGen/TargetRegisterInfo.h"33#include "llvm/CodeGen/TargetSubtargetInfo.h"34#include "llvm/IR/DebugLoc.h"35#include "llvm/IR/Function.h"36#include "llvm/Support/CommandLine.h"37#include "llvm/Support/Debug.h"38#include "llvm/Support/ErrorHandling.h"39#include "llvm/Support/raw_ostream.h"40#include "llvm/Target/TargetMachine.h"41#include <cassert>42#include <iterator>43#include <utility>44 45using namespace llvm;46 47#define DEBUG_TYPE "tailduplication"48 49STATISTIC(NumTails, "Number of tails duplicated");50STATISTIC(NumTailDups, "Number of tail duplicated blocks");51STATISTIC(NumTailDupAdded,52 "Number of instructions added due to tail duplication");53STATISTIC(NumTailDupRemoved,54 "Number of instructions removed due to tail duplication");55STATISTIC(NumDeadBlocks, "Number of dead blocks removed");56STATISTIC(NumAddedPHIs, "Number of phis added");57 58// Heuristic for tail duplication.59static cl::opt<unsigned> TailDuplicateSize(60 "tail-dup-size",61 cl::desc("Maximum instructions to consider tail duplicating"), cl::init(2),62 cl::Hidden);63 64static cl::opt<unsigned> TailDupIndirectBranchSize(65 "tail-dup-indirect-size",66 cl::desc("Maximum instructions to consider tail duplicating blocks that "67 "end with indirect branches."), cl::init(20),68 cl::Hidden);69 70static cl::opt<unsigned>71 TailDupPredSize("tail-dup-pred-size",72 cl::desc("Maximum predecessors (maximum successors at the "73 "same time) to consider tail duplicating blocks."),74 cl::init(16), cl::Hidden);75 76static cl::opt<unsigned>77 TailDupSuccSize("tail-dup-succ-size",78 cl::desc("Maximum successors (maximum predecessors at the "79 "same time) to consider tail duplicating blocks."),80 cl::init(16), cl::Hidden);81 82static cl::opt<bool>83 TailDupVerify("tail-dup-verify",84 cl::desc("Verify sanity of PHI instructions during taildup"),85 cl::init(false), cl::Hidden);86 87static cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U),88 cl::Hidden);89 90void TailDuplicator::initMF(MachineFunction &MFin, bool PreRegAlloc,91 const MachineBranchProbabilityInfo *MBPIin,92 MBFIWrapper *MBFIin,93 ProfileSummaryInfo *PSIin,94 bool LayoutModeIn, unsigned TailDupSizeIn) {95 MF = &MFin;96 TII = MF->getSubtarget().getInstrInfo();97 TRI = MF->getSubtarget().getRegisterInfo();98 MRI = &MF->getRegInfo();99 MBPI = MBPIin;100 MBFI = MBFIin;101 PSI = PSIin;102 TailDupSize = TailDupSizeIn;103 104 assert(MBPI != nullptr && "Machine Branch Probability Info required");105 106 LayoutMode = LayoutModeIn;107 this->PreRegAlloc = PreRegAlloc;108}109 110static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {111 for (MachineBasicBlock &MBB : llvm::drop_begin(MF)) {112 SmallSetVector<MachineBasicBlock *, 8> Preds(MBB.pred_begin(),113 MBB.pred_end());114 MachineBasicBlock::iterator MI = MBB.begin();115 while (MI != MBB.end()) {116 if (!MI->isPHI())117 break;118 for (MachineBasicBlock *PredBB : Preds) {119 bool Found = false;120 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {121 MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB();122 if (PHIBB == PredBB) {123 Found = true;124 break;125 }126 }127 if (!Found) {128 dbgs() << "Malformed PHI in " << printMBBReference(MBB) << ": "129 << *MI;130 dbgs() << " missing input from predecessor "131 << printMBBReference(*PredBB) << '\n';132 llvm_unreachable(nullptr);133 }134 }135 136 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {137 MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB();138 if (CheckExtra && !Preds.count(PHIBB)) {139 dbgs() << "Warning: malformed PHI in " << printMBBReference(MBB)140 << ": " << *MI;141 dbgs() << " extra input from predecessor "142 << printMBBReference(*PHIBB) << '\n';143 llvm_unreachable(nullptr);144 }145 if (PHIBB->getNumber() < 0) {146 dbgs() << "Malformed PHI in " << printMBBReference(MBB) << ": "147 << *MI;148 dbgs() << " non-existing " << printMBBReference(*PHIBB) << '\n';149 llvm_unreachable(nullptr);150 }151 }152 ++MI;153 }154 }155}156 157/// Tail duplicate the block and cleanup.158/// \p IsSimple - return value of isSimpleBB159/// \p MBB - block to be duplicated160/// \p ForcedLayoutPred - If non-null, treat this block as the layout161/// predecessor, instead of using the ordering in MF162/// \p DuplicatedPreds - if non-null, \p DuplicatedPreds will contain a list of163/// all Preds that received a copy of \p MBB.164/// \p RemovalCallback - if non-null, called just before MBB is deleted.165bool TailDuplicator::tailDuplicateAndUpdate(166 bool IsSimple, MachineBasicBlock *MBB,167 MachineBasicBlock *ForcedLayoutPred,168 SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds,169 function_ref<void(MachineBasicBlock *)> *RemovalCallback,170 SmallVectorImpl<MachineBasicBlock *> *CandidatePtr) {171 // Save the successors list.172 SmallSetVector<MachineBasicBlock *, 8> Succs(MBB->succ_begin(),173 MBB->succ_end());174 175 SmallVector<MachineBasicBlock *, 8> TDBBs;176 SmallVector<MachineInstr *, 16> Copies;177 if (!tailDuplicate(IsSimple, MBB, ForcedLayoutPred,178 TDBBs, Copies, CandidatePtr))179 return false;180 181 ++NumTails;182 183 SmallVector<MachineInstr *, 8> NewPHIs;184 MachineSSAUpdater SSAUpdate(*MF, &NewPHIs);185 186 // TailBB's immediate successors are now successors of those predecessors187 // which duplicated TailBB. Add the predecessors as sources to the PHI188 // instructions.189 bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken();190 if (PreRegAlloc)191 updateSuccessorsPHIs(MBB, isDead, TDBBs, Succs);192 193 // If it is dead, remove it.194 if (isDead) {195 NumTailDupRemoved += MBB->size();196 removeDeadBlock(MBB, RemovalCallback);197 ++NumDeadBlocks;198 }199 200 // Update SSA form.201 if (!SSAUpdateVRs.empty()) {202 for (Register VReg : SSAUpdateVRs) {203 SSAUpdate.Initialize(VReg);204 205 // If the original definition is still around, add it as an available206 // value.207 MachineInstr *DefMI = MRI->getVRegDef(VReg);208 MachineBasicBlock *DefBB = nullptr;209 if (DefMI) {210 DefBB = DefMI->getParent();211 SSAUpdate.AddAvailableValue(DefBB, VReg);212 }213 214 // Add the new vregs as available values.215 DenseMap<Register, AvailableValsTy>::iterator LI =216 SSAUpdateVals.find(VReg);217 for (std::pair<MachineBasicBlock *, Register> &J : LI->second) {218 MachineBasicBlock *SrcBB = J.first;219 Register SrcReg = J.second;220 SSAUpdate.AddAvailableValue(SrcBB, SrcReg);221 }222 223 SmallVector<MachineOperand *> DebugUses;224 // Rewrite uses that are outside of the original def's block.225 for (MachineOperand &UseMO :226 llvm::make_early_inc_range(MRI->use_operands(VReg))) {227 MachineInstr *UseMI = UseMO.getParent();228 // Rewrite debug uses last so that they can take advantage of any229 // register mappings introduced by other users in its BB, since we230 // cannot create new register definitions specifically for the debug231 // instruction (as debug instructions should not affect CodeGen).232 if (UseMI->isDebugValue()) {233 DebugUses.push_back(&UseMO);234 continue;235 }236 if (UseMI->getParent() == DefBB && !UseMI->isPHI())237 continue;238 SSAUpdate.RewriteUse(UseMO);239 }240 for (auto *UseMO : DebugUses) {241 MachineInstr *UseMI = UseMO->getParent();242 UseMO->setReg(243 SSAUpdate.GetValueInMiddleOfBlock(UseMI->getParent(), true));244 }245 }246 247 SSAUpdateVRs.clear();248 SSAUpdateVals.clear();249 }250 251 // Eliminate some of the copies inserted by tail duplication to maintain252 // SSA form.253 for (MachineInstr *Copy : Copies) {254 if (!Copy->isCopy())255 continue;256 Register Dst = Copy->getOperand(0).getReg();257 Register Src = Copy->getOperand(1).getReg();258 if (MRI->hasOneNonDBGUse(Src) &&259 MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) {260 // Copy is the only use. Do trivial copy propagation here.261 MRI->replaceRegWith(Dst, Src);262 Copy->eraseFromParent();263 }264 }265 266 if (NewPHIs.size())267 NumAddedPHIs += NewPHIs.size();268 269 if (DuplicatedPreds)270 *DuplicatedPreds = std::move(TDBBs);271 272 return true;273}274 275/// Look for small blocks that are unconditionally branched to and do not fall276/// through. Tail-duplicate their instructions into their predecessors to277/// eliminate (dynamic) branches.278bool TailDuplicator::tailDuplicateBlocks() {279 bool MadeChange = false;280 281 if (PreRegAlloc && TailDupVerify) {282 LLVM_DEBUG(dbgs() << "\n*** Before tail-duplicating\n");283 VerifyPHIs(*MF, true);284 }285 286 for (MachineBasicBlock &MBB :287 llvm::make_early_inc_range(llvm::drop_begin(*MF))) {288 if (NumTails == TailDupLimit)289 break;290 291 bool IsSimple = isSimpleBB(&MBB);292 293 if (!shouldTailDuplicate(IsSimple, MBB))294 continue;295 296 MadeChange |= tailDuplicateAndUpdate(IsSimple, &MBB, nullptr);297 }298 299 if (PreRegAlloc && TailDupVerify)300 VerifyPHIs(*MF, false);301 302 return MadeChange;303}304 305static bool isDefLiveOut(Register Reg, MachineBasicBlock *BB,306 const MachineRegisterInfo *MRI) {307 for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {308 if (UseMI.isDebugValue())309 continue;310 if (UseMI.getParent() != BB)311 return true;312 }313 return false;314}315 316static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) {317 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2)318 if (MI->getOperand(i + 1).getMBB() == SrcBB)319 return i;320 return 0;321}322 323// Remember which registers are used by phis in this block. This is324// used to determine which registers are liveout while modifying the325// block (which is why we need to copy the information).326static void getRegsUsedByPHIs(const MachineBasicBlock &BB,327 DenseSet<Register> *UsedByPhi) {328 for (const auto &MI : BB) {329 if (!MI.isPHI())330 break;331 for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {332 Register SrcReg = MI.getOperand(i).getReg();333 UsedByPhi->insert(SrcReg);334 }335 }336}337 338/// Add a definition and source virtual registers pair for SSA update.339void TailDuplicator::addSSAUpdateEntry(Register OrigReg, Register NewReg,340 MachineBasicBlock *BB) {341 DenseMap<Register, AvailableValsTy>::iterator LI =342 SSAUpdateVals.find(OrigReg);343 if (LI != SSAUpdateVals.end())344 LI->second.push_back(std::make_pair(BB, NewReg));345 else {346 AvailableValsTy Vals;347 Vals.push_back(std::make_pair(BB, NewReg));348 SSAUpdateVals.insert(std::make_pair(OrigReg, Vals));349 SSAUpdateVRs.push_back(OrigReg);350 }351}352 353/// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the354/// source register that's contributed by PredBB and update SSA update map.355void TailDuplicator::processPHI(356 MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB,357 DenseMap<Register, RegSubRegPair> &LocalVRMap,358 SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies,359 const DenseSet<Register> &RegsUsedByPhi, bool Remove) {360 Register DefReg = MI->getOperand(0).getReg();361 unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB);362 assert(SrcOpIdx && "Unable to find matching PHI source?");363 Register SrcReg = MI->getOperand(SrcOpIdx).getReg();364 unsigned SrcSubReg = MI->getOperand(SrcOpIdx).getSubReg();365 const TargetRegisterClass *RC = MRI->getRegClass(DefReg);366 LocalVRMap.try_emplace(DefReg, SrcReg, SrcSubReg);367 368 // Insert a copy from source to the end of the block. The def register is the369 // available value liveout of the block.370 Register NewDef = MRI->createVirtualRegister(RC);371 Copies.push_back(std::make_pair(NewDef, RegSubRegPair(SrcReg, SrcSubReg)));372 if (isDefLiveOut(DefReg, TailBB, MRI) || RegsUsedByPhi.count(DefReg))373 addSSAUpdateEntry(DefReg, NewDef, PredBB);374 375 if (!Remove)376 return;377 378 MI->removePHIIncomingValueFor(*PredBB);379 380 if (MI->getNumOperands() == 1 && !TailBB->hasAddressTaken())381 MI->eraseFromParent();382 else if (MI->getNumOperands() == 1)383 MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));384}385 386/// Duplicate a TailBB instruction to PredBB and update387/// the source operands due to earlier PHI translation.388void TailDuplicator::duplicateInstruction(389 MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB,390 DenseMap<Register, RegSubRegPair> &LocalVRMap,391 const DenseSet<Register> &UsedByPhi) {392 // Allow duplication of CFI instructions.393 if (MI->isCFIInstruction()) {394 BuildMI(*PredBB, PredBB->end(), PredBB->findDebugLoc(PredBB->begin()),395 TII->get(TargetOpcode::CFI_INSTRUCTION))396 .addCFIIndex(MI->getOperand(0).getCFIIndex())397 .setMIFlags(MI->getFlags());398 return;399 }400 MachineInstr &NewMI = TII->duplicate(*PredBB, PredBB->end(), *MI);401 if (!PreRegAlloc)402 return;403 for (unsigned i = 0, e = NewMI.getNumOperands(); i != e; ++i) {404 MachineOperand &MO = NewMI.getOperand(i);405 if (!MO.isReg())406 continue;407 Register Reg = MO.getReg();408 if (!Reg.isVirtual())409 continue;410 if (MO.isDef()) {411 const TargetRegisterClass *RC = MRI->getRegClass(Reg);412 Register NewReg = MRI->createVirtualRegister(RC);413 MO.setReg(NewReg);414 LocalVRMap.try_emplace(Reg, NewReg, 0);415 if (isDefLiveOut(Reg, TailBB, MRI) || UsedByPhi.count(Reg))416 addSSAUpdateEntry(Reg, NewReg, PredBB);417 continue;418 }419 auto VI = LocalVRMap.find(Reg);420 if (VI == LocalVRMap.end())421 continue;422 // Need to make sure that the register class of the mapped register423 // will satisfy the constraints of the class of the register being424 // replaced.425 auto *OrigRC = MRI->getRegClass(Reg);426 auto *MappedRC = MRI->getRegClass(VI->second.Reg);427 const TargetRegisterClass *ConstrRC;428 if (VI->second.SubReg != 0) {429 ConstrRC =430 TRI->getMatchingSuperRegClass(MappedRC, OrigRC, VI->second.SubReg);431 if (ConstrRC) {432 // The actual constraining (as in "find appropriate new class")433 // is done by getMatchingSuperRegClass, so now we only need to434 // change the class of the mapped register.435 MRI->setRegClass(VI->second.Reg, ConstrRC);436 }437 } else {438 // For mapped registers that do not have sub-registers, simply439 // restrict their class to match the original one.440 441 // We don't want debug instructions affecting the resulting code so442 // if we're cloning a debug instruction then just use MappedRC443 // rather than constraining the register class further.444 ConstrRC = NewMI.isDebugInstr()445 ? MappedRC446 : MRI->constrainRegClass(VI->second.Reg, OrigRC);447 }448 449 if (ConstrRC) {450 // If the class constraining succeeded, we can simply replace451 // the old register with the mapped one.452 MO.setReg(VI->second.Reg);453 // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a454 // sub-register, we need to compose the sub-register indices.455 MO.setSubReg(456 TRI->composeSubRegIndices(VI->second.SubReg, MO.getSubReg()));457 } else {458 // The direct replacement is not possible, due to failing register459 // class constraints. An explicit COPY is necessary. Create one460 // that can be reused.461 Register NewReg = MRI->createVirtualRegister(OrigRC);462 BuildMI(*PredBB, NewMI, NewMI.getDebugLoc(), TII->get(TargetOpcode::COPY),463 NewReg)464 .addReg(VI->second.Reg, 0, VI->second.SubReg);465 LocalVRMap.erase(VI);466 LocalVRMap.try_emplace(Reg, NewReg, 0);467 MO.setReg(NewReg);468 // The composed VI.Reg:VI.SubReg is replaced with NewReg, which469 // is equivalent to the whole register Reg. Hence, Reg:subreg470 // is same as NewReg:subreg, so keep the sub-register index471 // unchanged.472 }473 // Clear any kill flags from this operand. The new register could474 // have uses after this one, so kills are not valid here.475 MO.setIsKill(false);476 }477}478 479/// After FromBB is tail duplicated into its predecessor blocks, the successors480/// have gained new predecessors. Update the PHI instructions in them481/// accordingly.482void TailDuplicator::updateSuccessorsPHIs(483 MachineBasicBlock *FromBB, bool isDead,484 SmallVectorImpl<MachineBasicBlock *> &TDBBs,485 SmallSetVector<MachineBasicBlock *, 8> &Succs) {486 for (MachineBasicBlock *SuccBB : Succs) {487 for (MachineInstr &MI : *SuccBB) {488 if (!MI.isPHI())489 break;490 MachineInstrBuilder MIB(*FromBB->getParent(), MI);491 unsigned Idx = 0;492 for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {493 MachineOperand &MO = MI.getOperand(i + 1);494 if (MO.getMBB() == FromBB) {495 Idx = i;496 break;497 }498 }499 500 assert(Idx != 0);501 MachineOperand &MO0 = MI.getOperand(Idx);502 Register Reg = MO0.getReg();503 if (isDead) {504 // Folded into the previous BB.505 // There could be duplicate phi source entries. FIXME: Should sdisel506 // or earlier pass fixed this?507 for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) {508 MachineOperand &MO = MI.getOperand(i + 1);509 if (MO.getMBB() == FromBB) {510 MI.removeOperand(i + 1);511 MI.removeOperand(i);512 }513 }514 } else515 Idx = 0;516 517 // If Idx is set, the operands at Idx and Idx+1 must be removed.518 // We reuse the location to avoid expensive removeOperand calls.519 520 DenseMap<Register, AvailableValsTy>::iterator LI =521 SSAUpdateVals.find(Reg);522 if (LI != SSAUpdateVals.end()) {523 // This register is defined in the tail block.524 for (const std::pair<MachineBasicBlock *, Register> &J : LI->second) {525 MachineBasicBlock *SrcBB = J.first;526 // If we didn't duplicate a bb into a particular predecessor, we527 // might still have added an entry to SSAUpdateVals to correcly528 // recompute SSA. If that case, avoid adding a dummy extra argument529 // this PHI.530 if (!SrcBB->isSuccessor(SuccBB))531 continue;532 533 Register SrcReg = J.second;534 if (Idx != 0) {535 MI.getOperand(Idx).setReg(SrcReg);536 MI.getOperand(Idx + 1).setMBB(SrcBB);537 Idx = 0;538 } else {539 MIB.addReg(SrcReg).addMBB(SrcBB);540 }541 }542 } else {543 // Live in tail block, must also be live in predecessors.544 for (MachineBasicBlock *SrcBB : TDBBs) {545 if (Idx != 0) {546 MI.getOperand(Idx).setReg(Reg);547 MI.getOperand(Idx + 1).setMBB(SrcBB);548 Idx = 0;549 } else {550 MIB.addReg(Reg).addMBB(SrcBB);551 }552 }553 }554 if (Idx != 0) {555 MI.removeOperand(Idx + 1);556 MI.removeOperand(Idx);557 }558 }559 }560}561 562/// Determine if it is profitable to duplicate this block.563bool TailDuplicator::shouldTailDuplicate(bool IsSimple,564 MachineBasicBlock &TailBB) {565 // When doing tail-duplication during layout, the block ordering is in flux,566 // so canFallThrough returns a result based on incorrect information and567 // should just be ignored.568 if (!LayoutMode && TailBB.canFallThrough())569 return false;570 571 // Don't try to tail-duplicate single-block loops.572 if (TailBB.isSuccessor(&TailBB))573 return false;574 575 // Set the limit on the cost to duplicate. When optimizing for size,576 // duplicate only one, because one branch instruction can be eliminated to577 // compensate for the duplication.578 unsigned MaxDuplicateCount;579 if (TailDupSize == 0)580 MaxDuplicateCount = TailDuplicateSize;581 else582 MaxDuplicateCount = TailDupSize;583 if (llvm::shouldOptimizeForSize(&TailBB, PSI, MBFI))584 MaxDuplicateCount = 1;585 586 // If the block to be duplicated ends in an unanalyzable fallthrough, don't587 // duplicate it.588 // A similar check is necessary in MachineBlockPlacement to make sure pairs of589 // blocks with unanalyzable fallthrough get layed out contiguously.590 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;591 SmallVector<MachineOperand, 4> PredCond;592 if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) &&593 TailBB.canFallThrough())594 return false;595 596 // If the target has hardware branch prediction that can handle indirect597 // branches, duplicating them can often make them predictable when there598 // are common paths through the code. The limit needs to be high enough599 // to allow undoing the effects of tail merging and other optimizations600 // that rearrange the predecessors of the indirect branch.601 602 bool HasIndirectbr = false;603 bool HasComputedGoto = false;604 if (!TailBB.empty()) {605 HasIndirectbr = TailBB.back().isIndirectBranch();606 HasComputedGoto = TailBB.terminatorIsComputedGotoWithSuccessors();607 }608 609 if (HasIndirectbr && PreRegAlloc)610 MaxDuplicateCount = TailDupIndirectBranchSize;611 612 // Allow higher limits when the block has computed-gotos and running after613 // register allocation. NB. This basically unfactors computed gotos that were614 // factored early on in the compilation process to speed up edge based data615 // flow. If we do not unfactor them again, it can seriously pessimize code616 // with many computed jumps in the source code, such as interpreters.617 // Therefore we do not restrict the computed gotos.618 if (HasComputedGoto && !PreRegAlloc)619 MaxDuplicateCount = std::max(MaxDuplicateCount, 10u);620 621 // Check the instructions in the block to determine whether tail-duplication622 // is invalid or unlikely to be profitable.623 unsigned InstrCount = 0;624 unsigned NumPhis = 0;625 for (MachineInstr &MI : TailBB) {626 // Non-duplicable things shouldn't be tail-duplicated.627 // CFI instructions are marked as non-duplicable, because Darwin compact628 // unwind info emission can't handle multiple prologue setups. In case of629 // DWARF, allow them be duplicated, so that their existence doesn't prevent630 // tail duplication of some basic blocks, that would be duplicated otherwise.631 if (MI.isNotDuplicable() &&632 (TailBB.getParent()->getTarget().getTargetTriple().isOSDarwin() ||633 !MI.isCFIInstruction()))634 return false;635 636 // Convergent instructions can be duplicated only if doing so doesn't add637 // new control dependencies, which is what we're going to do here.638 if (MI.isConvergent())639 return false;640 641 // Do not duplicate 'return' instructions if this is a pre-regalloc run.642 // A return may expand into a lot more instructions (e.g. reload of callee643 // saved registers) after PEI.644 if (PreRegAlloc && MI.isReturn())645 return false;646 647 // Avoid duplicating calls before register allocation. Calls presents a648 // barrier to register allocation so duplicating them may end up increasing649 // spills.650 if (PreRegAlloc && MI.isCall())651 return false;652 653 // TailDuplicator::appendCopies will erroneously place COPYs after654 // INLINEASM_BR instructions after 4b0aa5724fea, which demonstrates the same655 // bug that was fixed in f7a53d82c090.656 // FIXME: Use findPHICopyInsertPoint() to find the correct insertion point657 // for the COPY when replacing PHIs.658 if (MI.getOpcode() == TargetOpcode::INLINEASM_BR)659 return false;660 661 if (MI.isBundle())662 InstrCount += MI.getBundleSize();663 else if (!MI.isPHI() && !MI.isMetaInstruction())664 InstrCount += 1;665 666 if (InstrCount > MaxDuplicateCount)667 return false;668 NumPhis += MI.isPHI();669 }670 671 // Duplicating a BB which has both multiple predecessors and successors will672 // may cause huge amount of PHI nodes. If we want to remove this limitation,673 // we have to address https://github.com/llvm/llvm-project/issues/78578.674 if (PreRegAlloc && TailBB.pred_size() > TailDupPredSize &&675 TailBB.succ_size() > TailDupSuccSize) {676 // If TailBB or any of its successors contains a phi, we may have to add a677 // large number of additional phis with additional incoming values.678 if (NumPhis != 0 || any_of(TailBB.successors(), [](MachineBasicBlock *MBB) {679 return any_of(*MBB, [](MachineInstr &MI) { return MI.isPHI(); });680 }))681 return false;682 }683 684 // Check if any of the successors of TailBB has a PHI node in which the685 // value corresponding to TailBB uses a subregister.686 // If a phi node uses a register paired with a subregister, the actual687 // "value type" of the phi may differ from the type of the register without688 // any subregisters. Due to a bug, tail duplication may add a new operand689 // without a necessary subregister, producing an invalid code. This is690 // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll.691 // Disable tail duplication for this case for now, until the problem is692 // fixed.693 for (auto *SB : TailBB.successors()) {694 for (auto &I : *SB) {695 if (!I.isPHI())696 break;697 unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);698 assert(Idx != 0);699 MachineOperand &PU = I.getOperand(Idx);700 if (PU.getSubReg() != 0)701 return false;702 }703 }704 705 if (HasIndirectbr && PreRegAlloc)706 return true;707 708 if (IsSimple)709 return true;710 711 if (!PreRegAlloc)712 return true;713 714 return canCompletelyDuplicateBB(TailBB);715}716 717/// True if this BB has only one unconditional jump.718bool TailDuplicator::isSimpleBB(MachineBasicBlock *TailBB) {719 if (TailBB->succ_size() != 1)720 return false;721 if (TailBB->pred_empty())722 return false;723 MachineBasicBlock::iterator I = TailBB->getFirstNonDebugInstr(true);724 if (I == TailBB->end())725 return true;726 return I->isUnconditionalBranch();727}728 729static bool bothUsedInPHI(const MachineBasicBlock &A,730 const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) {731 for (MachineBasicBlock *BB : A.successors())732 if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI())733 return true;734 735 return false;736}737 738bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) {739 for (MachineBasicBlock *PredBB : BB.predecessors()) {740 if (PredBB->succ_size() > 1)741 return false;742 743 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;744 SmallVector<MachineOperand, 4> PredCond;745 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))746 return false;747 748 if (!PredCond.empty())749 return false;750 }751 return true;752}753 754bool TailDuplicator::duplicateSimpleBB(755 MachineBasicBlock *TailBB, SmallVectorImpl<MachineBasicBlock *> &TDBBs,756 const DenseSet<Register> &UsedByPhi) {757 SmallPtrSet<MachineBasicBlock *, 8> Succs(llvm::from_range,758 TailBB->successors());759 SmallVector<MachineBasicBlock *, 8> Preds(TailBB->predecessors());760 bool Changed = false;761 for (MachineBasicBlock *PredBB : Preds) {762 if (PredBB->hasEHPadSuccessor() || PredBB->mayHaveInlineAsmBr())763 continue;764 765 if (bothUsedInPHI(*PredBB, Succs))766 continue;767 768 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;769 SmallVector<MachineOperand, 4> PredCond;770 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))771 continue;772 773 Changed = true;774 LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB775 << "From simple Succ: " << *TailBB);776 777 MachineBasicBlock *NewTarget = *TailBB->succ_begin();778 MachineBasicBlock *NextBB = PredBB->getNextNode();779 780 // Make PredFBB explicit.781 if (PredCond.empty())782 PredFBB = PredTBB;783 784 // Make fall through explicit.785 if (!PredTBB)786 PredTBB = NextBB;787 if (!PredFBB)788 PredFBB = NextBB;789 790 // Redirect791 if (PredFBB == TailBB)792 PredFBB = NewTarget;793 if (PredTBB == TailBB)794 PredTBB = NewTarget;795 796 // Make the branch unconditional if possible797 if (PredTBB == PredFBB) {798 PredCond.clear();799 PredFBB = nullptr;800 }801 802 // Avoid adding fall through branches.803 if (PredFBB == NextBB)804 PredFBB = nullptr;805 if (PredTBB == NextBB && PredFBB == nullptr)806 PredTBB = nullptr;807 808 auto DL = PredBB->findBranchDebugLoc();809 TII->removeBranch(*PredBB);810 811 if (!PredBB->isSuccessor(NewTarget))812 PredBB->replaceSuccessor(TailBB, NewTarget);813 else {814 PredBB->removeSuccessor(TailBB, true);815 assert(PredBB->succ_size() <= 1);816 }817 818 if (PredTBB)819 TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL);820 821 TDBBs.push_back(PredBB);822 }823 return Changed;824}825 826bool TailDuplicator::canTailDuplicate(MachineBasicBlock *TailBB,827 MachineBasicBlock *PredBB) {828 // EH edges are ignored by analyzeBranch.829 if (PredBB->succ_size() > 1)830 return false;831 832 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;833 SmallVector<MachineOperand, 4> PredCond;834 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))835 return false;836 if (!PredCond.empty())837 return false;838 // FIXME: This is overly conservative; it may be ok to relax this in the839 // future under more specific conditions. If TailBB is an INLINEASM_BR840 // indirect target, we need to see if the edge from PredBB to TailBB is from841 // an INLINEASM_BR in PredBB, and then also if that edge was from the842 // indirect target list, fallthrough/default target, or potentially both. If843 // it's both, TailDuplicator::tailDuplicate will remove the edge, corrupting844 // the successor list in PredBB and predecessor list in TailBB.845 if (TailBB->isInlineAsmBrIndirectTarget())846 return false;847 return true;848}849 850/// If it is profitable, duplicate TailBB's contents in each851/// of its predecessors.852/// \p IsSimple result of isSimpleBB853/// \p TailBB Block to be duplicated.854/// \p ForcedLayoutPred When non-null, use this block as the layout predecessor855/// instead of the previous block in MF's order.856/// \p TDBBs A vector to keep track of all blocks tail-duplicated857/// into.858/// \p Copies A vector of copy instructions inserted. Used later to859/// walk all the inserted copies and remove redundant ones.860bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB,861 MachineBasicBlock *ForcedLayoutPred,862 SmallVectorImpl<MachineBasicBlock *> &TDBBs,863 SmallVectorImpl<MachineInstr *> &Copies,864 SmallVectorImpl<MachineBasicBlock *> *CandidatePtr) {865 LLVM_DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB)866 << '\n');867 868 bool ShouldUpdateTerminators = TailBB->canFallThrough();869 870 DenseSet<Register> UsedByPhi;871 getRegsUsedByPHIs(*TailBB, &UsedByPhi);872 873 if (IsSimple)874 return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi);875 876 // Iterate through all the unique predecessors and tail-duplicate this877 // block into them, if possible. Copying the list ahead of time also878 // avoids trouble with the predecessor list reallocating.879 bool Changed = false;880 SmallSetVector<MachineBasicBlock *, 8> Preds;881 if (CandidatePtr)882 Preds.insert_range(*CandidatePtr);883 else884 Preds.insert_range(TailBB->predecessors());885 886 for (MachineBasicBlock *PredBB : Preds) {887 assert(TailBB != PredBB &&888 "Single-block loop should have been rejected earlier!");889 890 if (!canTailDuplicate(TailBB, PredBB))891 continue;892 893 // Don't duplicate into a fall-through predecessor (at least for now).894 // If profile is available, findDuplicateCandidates can choose better895 // fall-through predecessor.896 if (!(MF->getFunction().hasProfileData() && LayoutMode)) {897 bool IsLayoutSuccessor = false;898 if (ForcedLayoutPred)899 IsLayoutSuccessor = (ForcedLayoutPred == PredBB);900 else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())901 IsLayoutSuccessor = true;902 if (IsLayoutSuccessor)903 continue;904 }905 906 LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB907 << "From Succ: " << *TailBB);908 909 TDBBs.push_back(PredBB);910 911 // Remove PredBB's unconditional branch.912 TII->removeBranch(*PredBB);913 914 // Clone the contents of TailBB into PredBB.915 DenseMap<Register, RegSubRegPair> LocalVRMap;916 SmallVector<std::pair<Register, RegSubRegPair>, 4> CopyInfos;917 for (MachineInstr &MI : llvm::make_early_inc_range(*TailBB)) {918 if (MI.isPHI()) {919 // Replace the uses of the def of the PHI with the register coming920 // from PredBB.921 processPHI(&MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true);922 } else {923 // Replace def of virtual registers with new registers, and update924 // uses with PHI source register or the new registers.925 duplicateInstruction(&MI, TailBB, PredBB, LocalVRMap, UsedByPhi);926 }927 }928 appendCopies(PredBB, CopyInfos, Copies);929 930 NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch931 932 // Update the CFG.933 PredBB->removeSuccessor(PredBB->succ_begin());934 assert(PredBB->succ_empty() &&935 "TailDuplicate called on block with multiple successors!");936 for (MachineBasicBlock *Succ : TailBB->successors())937 PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ));938 939 // Update branches in pred to jump to tail's layout successor if needed.940 if (ShouldUpdateTerminators)941 PredBB->updateTerminator(TailBB->getNextNode());942 943 Changed = true;944 ++NumTailDups;945 }946 947 // If TailBB was duplicated into all its predecessors except for the prior948 // block, which falls through unconditionally, move the contents of this949 // block into the prior block.950 MachineBasicBlock *PrevBB = ForcedLayoutPred;951 if (!PrevBB)952 PrevBB = &*std::prev(TailBB->getIterator());953 MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;954 SmallVector<MachineOperand, 4> PriorCond;955 // This has to check PrevBB->succ_size() because EH edges are ignored by956 // analyzeBranch.957 if (PrevBB->succ_size() == 1 &&958 // Layout preds are not always CFG preds. Check.959 *PrevBB->succ_begin() == TailBB &&960 !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond) &&961 PriorCond.empty() &&962 (!PriorTBB || PriorTBB == TailBB) &&963 TailBB->pred_size() == 1 &&964 !TailBB->hasAddressTaken()) {965 LLVM_DEBUG(dbgs() << "\nMerging into block: " << *PrevBB966 << "From MBB: " << *TailBB);967 // There may be a branch to the layout successor. This is unlikely but it968 // happens. The correct thing to do is to remove the branch before969 // duplicating the instructions in all cases.970 bool RemovedBranches = TII->removeBranch(*PrevBB) != 0;971 972 // If there are still tail instructions, abort the merge973 if (PrevBB->getFirstTerminator() == PrevBB->end()) {974 if (PreRegAlloc) {975 DenseMap<Register, RegSubRegPair> LocalVRMap;976 SmallVector<std::pair<Register, RegSubRegPair>, 4> CopyInfos;977 MachineBasicBlock::iterator I = TailBB->begin();978 // Process PHI instructions first.979 while (I != TailBB->end() && I->isPHI()) {980 // Replace the uses of the def of the PHI with the register coming981 // from PredBB.982 MachineInstr *MI = &*I++;983 processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi,984 true);985 }986 987 // Now copy the non-PHI instructions.988 while (I != TailBB->end()) {989 // Replace def of virtual registers with new registers, and update990 // uses with PHI source register or the new registers.991 MachineInstr *MI = &*I++;992 assert(!MI->isBundle() && "Not expecting bundles before regalloc!");993 duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);994 MI->eraseFromParent();995 }996 appendCopies(PrevBB, CopyInfos, Copies);997 } else {998 TII->removeBranch(*PrevBB);999 // No PHIs to worry about, just splice the instructions over.1000 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());1001 }1002 PrevBB->removeSuccessor(PrevBB->succ_begin());1003 assert(PrevBB->succ_empty());1004 PrevBB->transferSuccessors(TailBB);1005 1006 // Update branches in PrevBB based on Tail's layout successor.1007 if (ShouldUpdateTerminators)1008 PrevBB->updateTerminator(TailBB->getNextNode());1009 1010 TDBBs.push_back(PrevBB);1011 Changed = true;1012 } else {1013 LLVM_DEBUG(dbgs() << "Abort merging blocks, the predecessor still "1014 "contains terminator instructions");1015 // Return early if no changes were made1016 if (!Changed)1017 return RemovedBranches;1018 }1019 Changed |= RemovedBranches;1020 }1021 1022 // If this is after register allocation, there are no phis to fix.1023 if (!PreRegAlloc)1024 return Changed;1025 1026 // If we made no changes so far, we are safe.1027 if (!Changed)1028 return Changed;1029 1030 // Handle the nasty case in that we duplicated a block that is part of a loop1031 // into some but not all of its predecessors. For example:1032 // 1 -> 2 <-> 3 |1033 // \ |1034 // \---> rest |1035 // if we duplicate 2 into 1 but not into 3, we end up with1036 // 12 -> 3 <-> 2 -> rest |1037 // \ / |1038 // \----->-----/ |1039 // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced1040 // with a phi in 3 (which now dominates 2).1041 // What we do here is introduce a copy in 3 of the register defined by the1042 // phi, just like when we are duplicating 2 into 3, but we don't copy any1043 // real instructions or remove the 3 -> 2 edge from the phi in 2.1044 for (MachineBasicBlock *PredBB : Preds) {1045 if (is_contained(TDBBs, PredBB))1046 continue;1047 1048 // EH edges1049 if (PredBB->succ_size() != 1)1050 continue;1051 1052 DenseMap<Register, RegSubRegPair> LocalVRMap;1053 SmallVector<std::pair<Register, RegSubRegPair>, 4> CopyInfos;1054 // Process PHI instructions first.1055 for (MachineInstr &MI : make_early_inc_range(TailBB->phis())) {1056 // Replace the uses of the def of the PHI with the register coming1057 // from PredBB.1058 processPHI(&MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false);1059 }1060 appendCopies(PredBB, CopyInfos, Copies);1061 }1062 1063 return Changed;1064}1065 1066/// At the end of the block \p MBB generate COPY instructions between registers1067/// described by \p CopyInfos. Append resulting instructions to \p Copies.1068void TailDuplicator::appendCopies(MachineBasicBlock *MBB,1069 SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,1070 SmallVectorImpl<MachineInstr*> &Copies) {1071 MachineBasicBlock::iterator Loc = MBB->getFirstTerminator();1072 const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY);1073 for (auto &CI : CopyInfos) {1074 auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first)1075 .addReg(CI.second.Reg, 0, CI.second.SubReg);1076 Copies.push_back(C);1077 }1078}1079 1080/// Remove the specified dead machine basic block from the function, updating1081/// the CFG.1082void TailDuplicator::removeDeadBlock(1083 MachineBasicBlock *MBB,1084 function_ref<void(MachineBasicBlock *)> *RemovalCallback) {1085 assert(MBB->pred_empty() && "MBB must be dead!");1086 LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);1087 1088 MachineFunction *MF = MBB->getParent();1089 // Update the call info.1090 for (const MachineInstr &MI : *MBB)1091 if (MI.shouldUpdateAdditionalCallInfo())1092 MF->eraseAdditionalCallInfo(&MI);1093 1094 if (RemovalCallback)1095 (*RemovalCallback)(MBB);1096 1097 // Remove all successors.1098 while (!MBB->succ_empty())1099 MBB->removeSuccessor(MBB->succ_end() - 1);1100 1101 // Remove the block.1102 MBB->eraseFromParent();1103}1104