Lines Matching +full:block +full:- +full:copy
1 //===- TailDuplicator.cpp - Duplicate blocks into predecessors' tails -----===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
61 "tail-dup-size",
66 "tail-dup-indirect-size",
72 TailDupPredSize("tail-dup-pred-size",
78 TailDupSuccSize("tail-dup-succ-size",
84 TailDupVerify("tail-dup-verify",
88 static cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U),
97 TII = MF->getSubtarget().getInstrInfo(); in initMF()
98 TRI = MF->getSubtarget().getRegisterInfo(); in initMF()
99 MRI = &MF->getRegInfo(); in initMF()
108 this->PreRegAlloc = PreRegAlloc; in initMF()
117 if (!MI->isPHI()) in VerifyPHIs()
121 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { in VerifyPHIs()
122 MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB(); in VerifyPHIs()
137 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { in VerifyPHIs()
138 MachineBasicBlock *PHIBB = MI->getOperand(i + 1).getMBB(); in VerifyPHIs()
146 if (PHIBB->getNumber() < 0) { in VerifyPHIs()
149 dbgs() << " non-existing " << printMBBReference(*PHIBB) << '\n'; in VerifyPHIs()
158 /// Tail duplicate the block and cleanup.
159 /// \p IsSimple - return value of isSimpleBB
160 /// \p MBB - block to be duplicated
161 /// \p ForcedLayoutPred - If non-null, treat this block as the layout
163 /// \p DuplicatedPreds - if non-null, \p DuplicatedPreds will contain a list of
164 /// all Preds that received a copy of \p MBB.
165 /// \p RemovalCallback - if non-null, called just before MBB is deleted.
173 SmallSetVector<MachineBasicBlock *, 8> Succs(MBB->succ_begin(), in tailDuplicateAndUpdate()
174 MBB->succ_end()); in tailDuplicateAndUpdate()
190 bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); in tailDuplicateAndUpdate()
196 NumTailDupRemoved += MBB->size(); in tailDuplicateAndUpdate()
208 MachineInstr *DefMI = MRI->getVRegDef(VReg); in tailDuplicateAndUpdate()
211 DefBB = DefMI->getParent(); in tailDuplicateAndUpdate()
218 for (std::pair<MachineBasicBlock *, Register> &J : LI->second) { in tailDuplicateAndUpdate()
225 // Rewrite uses that are outside of the original def's block. in tailDuplicateAndUpdate()
227 llvm::make_early_inc_range(MRI->use_operands(VReg))) { in tailDuplicateAndUpdate()
233 if (UseMI->isDebugValue()) { in tailDuplicateAndUpdate()
237 if (UseMI->getParent() == DefBB && !UseMI->isPHI()) in tailDuplicateAndUpdate()
242 MachineInstr *UseMI = UseMO->getParent(); in tailDuplicateAndUpdate()
243 UseMO->setReg( in tailDuplicateAndUpdate()
244 SSAUpdate.GetValueInMiddleOfBlock(UseMI->getParent(), true)); in tailDuplicateAndUpdate()
254 for (MachineInstr *Copy : Copies) { in tailDuplicateAndUpdate()
255 if (!Copy->isCopy()) in tailDuplicateAndUpdate()
257 Register Dst = Copy->getOperand(0).getReg(); in tailDuplicateAndUpdate()
258 Register Src = Copy->getOperand(1).getReg(); in tailDuplicateAndUpdate()
259 if (MRI->hasOneNonDBGUse(Src) && in tailDuplicateAndUpdate()
260 MRI->constrainRegClass(Src, MRI->getRegClass(Dst))) { in tailDuplicateAndUpdate()
261 // Copy is the only use. Do trivial copy propagation here. in tailDuplicateAndUpdate()
262 MRI->replaceRegWith(Dst, Src); in tailDuplicateAndUpdate()
263 Copy->eraseFromParent(); in tailDuplicateAndUpdate()
277 /// through. Tail-duplicate their instructions into their predecessors to
283 LLVM_DEBUG(dbgs() << "\n*** Before tail-duplicating\n"); in tailDuplicateBlocks()
308 for (MachineInstr &UseMI : MRI->use_instructions(Reg)) { in isDefLiveOut()
318 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) in getPHISrcRegOpIdx()
319 if (MI->getOperand(i + 1).getMBB() == SrcBB) in getPHISrcRegOpIdx()
324 // Remember which registers are used by phis in this block. This is
326 // block (which is why we need to copy the information).
334 UsedByPhi->insert(SrcReg); in getRegsUsedByPHIs()
345 LI->second.push_back(std::make_pair(BB, NewReg)); in addSSAUpdateEntry()
354 /// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the
361 Register DefReg = MI->getOperand(0).getReg(); in processPHI()
364 Register SrcReg = MI->getOperand(SrcOpIdx).getReg(); in processPHI()
365 unsigned SrcSubReg = MI->getOperand(SrcOpIdx).getSubReg(); in processPHI()
366 const TargetRegisterClass *RC = MRI->getRegClass(DefReg); in processPHI()
369 // Insert a copy from source to the end of the block. The def register is the in processPHI()
370 // available value liveout of the block. in processPHI()
371 Register NewDef = MRI->createVirtualRegister(RC); in processPHI()
380 MI->removeOperand(SrcOpIdx + 1); in processPHI()
381 MI->removeOperand(SrcOpIdx); in processPHI()
382 if (MI->getNumOperands() == 1 && !TailBB->hasAddressTaken()) in processPHI()
383 MI->eraseFromParent(); in processPHI()
384 else if (MI->getNumOperands() == 1) in processPHI()
385 MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); in processPHI()
395 if (MI->isCFIInstruction()) { in duplicateInstruction()
396 BuildMI(*PredBB, PredBB->end(), PredBB->findDebugLoc(PredBB->begin()), in duplicateInstruction()
397 TII->get(TargetOpcode::CFI_INSTRUCTION)) in duplicateInstruction()
398 .addCFIIndex(MI->getOperand(0).getCFIIndex()) in duplicateInstruction()
399 .setMIFlags(MI->getFlags()); in duplicateInstruction()
402 MachineInstr &NewMI = TII->duplicate(*PredBB, PredBB->end(), *MI); in duplicateInstruction()
412 const TargetRegisterClass *RC = MRI->getRegClass(Reg); in duplicateInstruction()
413 Register NewReg = MRI->createVirtualRegister(RC); in duplicateInstruction()
424 auto *OrigRC = MRI->getRegClass(Reg); in duplicateInstruction()
425 auto *MappedRC = MRI->getRegClass(VI->second.Reg); in duplicateInstruction()
427 if (VI->second.SubReg != 0) { in duplicateInstruction()
428 ConstrRC = TRI->getMatchingSuperRegClass(MappedRC, OrigRC, in duplicateInstruction()
429 VI->second.SubReg); in duplicateInstruction()
434 MRI->setRegClass(VI->second.Reg, ConstrRC); in duplicateInstruction()
437 // For mapped registers that do not have sub-registers, simply in duplicateInstruction()
445 : MRI->constrainRegClass(VI->second.Reg, OrigRC); in duplicateInstruction()
451 MO.setReg(VI->second.Reg); in duplicateInstruction()
452 // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a in duplicateInstruction()
453 // sub-register, we need to compose the sub-register indices. in duplicateInstruction()
455 TRI->composeSubRegIndices(VI->second.SubReg, MO.getSubReg())); in duplicateInstruction()
458 // class constraints. An explicit COPY is necessary. Create one in duplicateInstruction()
460 Register NewReg = MRI->createVirtualRegister(OrigRC); in duplicateInstruction()
462 TII->get(TargetOpcode::COPY), NewReg) in duplicateInstruction()
463 .addReg(VI->second.Reg, 0, VI->second.SubReg); in duplicateInstruction()
469 // is same as NewReg:subreg, so keep the sub-register index in duplicateInstruction()
492 MachineInstrBuilder MIB(*FromBB->getParent(), MI); in updateSuccessorsPHIs()
509 for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) { in updateSuccessorsPHIs()
525 // This register is defined in the tail block. in updateSuccessorsPHIs()
526 for (const std::pair<MachineBasicBlock *, Register> &J : LI->second) { in updateSuccessorsPHIs()
532 if (!SrcBB->isSuccessor(SuccBB)) in updateSuccessorsPHIs()
545 // Live in tail block, must also be live in predecessors. in updateSuccessorsPHIs()
564 /// Determine if it is profitable to duplicate this block.
567 // When doing tail-duplication during layout, the block ordering is in flux, in shouldTailDuplicate()
573 // Don't try to tail-duplicate single-block loops. in shouldTailDuplicate()
580 // https://github.com/llvm/llvm-project/issues/78578. in shouldTailDuplicate()
589 bool OptForSize = MF->getFunction().hasOptSize() || in shouldTailDuplicate()
598 // If the block to be duplicated ends in an unanalyzable fallthrough, don't in shouldTailDuplicate()
604 if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) && in shouldTailDuplicate()
621 // Check the instructions in the block to determine whether tail-duplication in shouldTailDuplicate()
625 // Non-duplicable things shouldn't be tail-duplicated. in shouldTailDuplicate()
626 // CFI instructions are marked as non-duplicable, because Darwin compact in shouldTailDuplicate()
631 (TailBB.getParent()->getTarget().getTargetTriple().isOSDarwin() || in shouldTailDuplicate()
640 // Do not duplicate 'return' instructions if this is a pre-regalloc run. in shouldTailDuplicate()
656 // for the COPY when replacing PHIs. in shouldTailDuplicate()
675 // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll. in shouldTailDuplicate()
704 if (TailBB->succ_size() != 1) in isSimpleBB()
706 if (TailBB->pred_empty()) in isSimpleBB()
708 MachineBasicBlock::iterator I = TailBB->getFirstNonDebugInstr(true); in isSimpleBB()
709 if (I == TailBB->end()) in isSimpleBB()
711 return I->isUnconditionalBranch(); in isSimpleBB()
717 if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI()) in bothUsedInPHI()
725 if (PredBB->succ_size() > 1) in canCompletelyDuplicateBB()
730 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond)) in canCompletelyDuplicateBB()
742 SmallPtrSet<MachineBasicBlock *, 8> Succs(TailBB->succ_begin(), in duplicateSimpleBB()
743 TailBB->succ_end()); in duplicateSimpleBB()
744 SmallVector<MachineBasicBlock *, 8> Preds(TailBB->predecessors()); in duplicateSimpleBB()
747 if (PredBB->hasEHPadSuccessor() || PredBB->mayHaveInlineAsmBr()) in duplicateSimpleBB()
755 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond)) in duplicateSimpleBB()
759 LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB in duplicateSimpleBB()
762 MachineBasicBlock *NewTarget = *TailBB->succ_begin(); in duplicateSimpleBB()
763 MachineBasicBlock *NextBB = PredBB->getNextNode(); in duplicateSimpleBB()
793 auto DL = PredBB->findBranchDebugLoc(); in duplicateSimpleBB()
794 TII->removeBranch(*PredBB); in duplicateSimpleBB()
796 if (!PredBB->isSuccessor(NewTarget)) in duplicateSimpleBB()
797 PredBB->replaceSuccessor(TailBB, NewTarget); in duplicateSimpleBB()
799 PredBB->removeSuccessor(TailBB, true); in duplicateSimpleBB()
800 assert(PredBB->succ_size() <= 1); in duplicateSimpleBB()
804 TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL); in duplicateSimpleBB()
814 if (PredBB->succ_size() > 1) in canTailDuplicate()
819 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond)) in canTailDuplicate()
830 if (TailBB->isInlineAsmBrIndirectTarget()) in canTailDuplicate()
838 /// \p TailBB Block to be duplicated.
839 /// \p ForcedLayoutPred When non-null, use this block as the layout predecessor
840 /// instead of the previous block in MF's order.
841 /// \p TDBBs A vector to keep track of all blocks tail-duplicated
843 /// \p Copies A vector of copy instructions inserted. Used later to
850 LLVM_DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB) in tailDuplicate()
853 bool ShouldUpdateTerminators = TailBB->canFallThrough(); in tailDuplicate()
861 // Iterate through all the unique predecessors and tail-duplicate this in tailDuplicate()
862 // block into them, if possible. Copying the list ahead of time also in tailDuplicate()
867 Preds.insert(CandidatePtr->begin(), CandidatePtr->end()); in tailDuplicate()
869 Preds.insert(TailBB->pred_begin(), TailBB->pred_end()); in tailDuplicate()
873 "Single-block loop should have been rejected earlier!"); in tailDuplicate()
878 // Don't duplicate into a fall-through predecessor (at least for now). in tailDuplicate()
880 // fall-through predecessor. in tailDuplicate()
881 if (!(MF->getFunction().hasProfileData() && LayoutMode)) { in tailDuplicate()
885 else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough()) in tailDuplicate()
891 LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB in tailDuplicate()
897 TII->removeBranch(*PredBB); in tailDuplicate()
915 NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch in tailDuplicate()
918 PredBB->removeSuccessor(PredBB->succ_begin()); in tailDuplicate()
919 assert(PredBB->succ_empty() && in tailDuplicate()
920 "TailDuplicate called on block with multiple successors!"); in tailDuplicate()
921 for (MachineBasicBlock *Succ : TailBB->successors()) in tailDuplicate()
922 PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ)); in tailDuplicate()
926 PredBB->updateTerminator(TailBB->getNextNode()); in tailDuplicate()
933 // block, which falls through unconditionally, move the contents of this in tailDuplicate()
934 // block into the prior block. in tailDuplicate()
937 PrevBB = &*std::prev(TailBB->getIterator()); in tailDuplicate()
940 // This has to check PrevBB->succ_size() because EH edges are ignored by in tailDuplicate()
942 if (PrevBB->succ_size() == 1 && in tailDuplicate()
944 *PrevBB->succ_begin() == TailBB && in tailDuplicate()
945 !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond) && in tailDuplicate()
948 TailBB->pred_size() == 1 && in tailDuplicate()
949 !TailBB->hasAddressTaken()) { in tailDuplicate()
950 LLVM_DEBUG(dbgs() << "\nMerging into block: " << *PrevBB in tailDuplicate()
955 bool RemovedBranches = TII->removeBranch(*PrevBB) != 0; in tailDuplicate()
958 if (PrevBB->getFirstTerminator() == PrevBB->end()) { in tailDuplicate()
962 MachineBasicBlock::iterator I = TailBB->begin(); in tailDuplicate()
964 while (I != TailBB->end() && I->isPHI()) { in tailDuplicate()
972 // Now copy the non-PHI instructions. in tailDuplicate()
973 while (I != TailBB->end()) { in tailDuplicate()
977 assert(!MI->isBundle() && "Not expecting bundles before regalloc!"); in tailDuplicate()
979 MI->eraseFromParent(); in tailDuplicate()
983 TII->removeBranch(*PrevBB); in tailDuplicate()
985 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end()); in tailDuplicate()
987 PrevBB->removeSuccessor(PrevBB->succ_begin()); in tailDuplicate()
988 assert(PrevBB->succ_empty()); in tailDuplicate()
989 PrevBB->transferSuccessors(TailBB); in tailDuplicate()
993 PrevBB->updateTerminator(TailBB->getNextNode()); in tailDuplicate()
1015 // Handle the nasty case in that we duplicated a block that is part of a loop in tailDuplicate()
1017 // 1 -> 2 <-> 3 | in tailDuplicate()
1019 // \---> rest | in tailDuplicate()
1021 // 12 -> 3 <-> 2 -> rest | in tailDuplicate()
1023 // \----->-----/ | in tailDuplicate()
1026 // What we do here is introduce a copy in 3 of the register defined by the in tailDuplicate()
1027 // phi, just like when we are duplicating 2 into 3, but we don't copy any in tailDuplicate()
1028 // real instructions or remove the 3 -> 2 edge from the phi in 2. in tailDuplicate()
1034 if (PredBB->succ_size() != 1) in tailDuplicate()
1040 for (MachineInstr &MI : make_early_inc_range(TailBB->phis())) { in tailDuplicate()
1051 /// At the end of the block \p MBB generate COPY instructions between registers
1056 MachineBasicBlock::iterator Loc = MBB->getFirstTerminator(); in appendCopies()
1057 const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY); in appendCopies()
1065 /// Remove the specified dead machine basic block from the function, updating
1070 assert(MBB->pred_empty() && "MBB must be dead!"); in removeDeadBlock()
1073 MachineFunction *MF = MBB->getParent(); in removeDeadBlock()
1077 MF->eraseCallSiteInfo(&MI); in removeDeadBlock()
1083 while (!MBB->succ_empty()) in removeDeadBlock()
1084 MBB->removeSuccessor(MBB->succ_end() - 1); in removeDeadBlock()
1086 // Remove the block. in removeDeadBlock()
1087 MBB->eraseFromParent(); in removeDeadBlock()