Lines Matching +full:flow +full:- +full:level
1 //===--------------------- SIOptimizeVGPRLiveRange.cpp -------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 /// This pass tries to remove unnecessary VGPR live ranges in divergent if-else
13 /// When we do structurization, we usually transform an if-else into two
14 /// successive if-then (with a flow block to do predicate inversion). Consider a
16 /// if-else and used in both THEN (use in THEN is optional) and ELSE part:
23 /// bb.flow:
30 /// As register allocator has no idea of the thread-control-flow, it will just
33 /// to exec mask. For this if-else case, the lanes active in bb.then will be
34 /// inactive in bb.else, and vice-versa. So we are safe to say that %a was dead
39 /// This pass aims to tell register allocator that %a is in-fact dead,
40 /// through inserting a phi-node in bb.flow saying that %a is undef when coming
45 /// 1.) The def-point should be in the same loop-level as if-else-endif to make
47 /// 2.) There should be no further uses after the IF-ELSE region.
63 /// each active lane. Similar to the if-else case, the register allocator
66 /// to be live after its last use in the loop block. By inserting a phi-node at
72 //===----------------------------------------------------------------------===//
86 #define DEBUG_TYPE "si-opt-vgpr-liverange"
104 void collectElseRegionBlocks(MachineBasicBlock *Flow,
109 collectCandidateRegisters(MachineBasicBlock *If, MachineBasicBlock *Flow,
124 MachineBasicBlock *Flow) const;
127 Register Reg, Register NewReg, MachineBasicBlock *Flow,
133 MachineBasicBlock *Flow, MachineBasicBlock *Endif,
172 // Check whether the MBB is a else flow block and get the branching target which
176 for (auto &BR : MBB->terminators()) { in getElseTarget()
184 MachineBasicBlock *Flow, MachineBasicBlock *Endif, in collectElseRegionBlocks() argument
186 assert(Flow != Endif); in collectElseRegionBlocks()
191 for (auto *Pred : MBB->predecessors()) { in collectElseRegionBlocks()
192 if (Pred != Flow && !Blocks.contains(Pred)) in collectElseRegionBlocks()
214 for (auto &UseMI : MRI->use_nodbg_instructions(Reg)) { in findNonPHIUsesInBlock()
223 MachineBasicBlock *If, MachineBasicBlock *Flow, MachineBasicBlock *Endif, in collectCandidateRegisters() argument
230 for (auto &MI : Else->instrs()) { in collectCandidateRegisters()
240 if (MOReg.isPhysical() || !TRI->isVectorRegister(*MRI, MOReg)) in collectCandidateRegisters()
244 LiveVariables::VarInfo &VI = LV->getVarInfo(MOReg); in collectCandidateRegisters()
245 const MachineBasicBlock *DefMBB = MRI->getVRegDef(MOReg)->getParent(); in collectCandidateRegisters()
248 // b.) should be defined in the same loop-level. in collectCandidateRegisters()
249 if ((VI.AliveBlocks.test(If->getNumber()) || DefMBB == If) && in collectCandidateRegisters()
250 Loops->getLoopFor(DefMBB) == Loops->getLoopFor(If)) { in collectCandidateRegisters()
253 LiveVariables::VarInfo &VI = LV->getVarInfo(MOReg); in collectCandidateRegisters()
267 // region. Make sure the phi-use is the last use. in collectCandidateRegisters()
268 for (auto &MI : Endif->phis()) { in collectCandidateRegisters()
272 if (Pred == Flow) in collectCandidateRegisters()
280 if (Reg.isPhysical() || !TRI->isVectorRegister(*MRI, Reg)) in collectCandidateRegisters()
283 LiveVariables::VarInfo &VI = LV->getVarInfo(Reg); in collectCandidateRegisters()
292 // b.) should be defined in the same loop-level. in collectCandidateRegisters()
293 const MachineBasicBlock *DefMBB = MRI->getVRegDef(Reg)->getParent(); in collectCandidateRegisters()
294 if ((VI.AliveBlocks.test(If->getNumber()) || DefMBB == If) && in collectCandidateRegisters()
295 Loops->getLoopFor(DefMBB) == Loops->getLoopFor(If)) in collectCandidateRegisters()
301 for (auto I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); I != E; in collectCandidateRegisters()
303 if (!I->readsReg()) in collectCandidateRegisters()
305 auto *UseMI = I->getParent(); in collectCandidateRegisters()
306 auto *UseMBB = UseMI->getParent(); in collectCandidateRegisters()
307 if (UseMBB == Flow || UseMBB == Endif) { in collectCandidateRegisters()
308 if (!UseMI->isPHI()) in collectCandidateRegisters()
311 auto *IncomingMBB = UseMI->getOperand(I.getOperandNo() + 1).getMBB(); in collectCandidateRegisters()
312 // The register is live through the path If->Flow or Flow->Endif. in collectCandidateRegisters()
314 if ((UseMBB == Flow && IncomingMBB != If) || in collectCandidateRegisters()
315 (UseMBB == Endif && IncomingMBB == Flow)) in collectCandidateRegisters()
348 if ((MBB != LoopHeader && MBB->pred_size() != 1) || in collectWaterfallCandidateRegisters()
349 (MBB == LoopHeader && MBB->pred_size() != 2) || MBB->succ_size() != 1) { in collectWaterfallCandidateRegisters()
354 MBB = *MBB->succ_begin(); in collectWaterfallCandidateRegisters()
366 if (MOReg.isPhysical() || !TRI->isVectorRegister(*MRI, MOReg)) in collectWaterfallCandidateRegisters()
370 MachineBasicBlock *DefMBB = MRI->getVRegDef(MOReg)->getParent(); in collectWaterfallCandidateRegisters()
376 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(MOReg); in collectWaterfallCandidateRegisters()
378 for (auto *Succ : LoopEnd->successors()) { in collectWaterfallCandidateRegisters()
399 // Re-calculate the liveness of \p Reg in the THEN-region
401 Register Reg, MachineBasicBlock *If, MachineBasicBlock *Flow) const { in updateLiveRangeInThenRegion()
405 // Collect all successors until we see the flow block, where we should in updateLiveRangeInThenRegion()
409 for (auto *Succ : MBB->successors()) { in updateLiveRangeInThenRegion()
410 if (Succ != Flow && !Blocks.contains(Succ)) { in updateLiveRangeInThenRegion()
417 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg); in updateLiveRangeInThenRegion()
422 OldVarInfo.AliveBlocks.reset(MBB->getNumber()); in updateLiveRangeInThenRegion()
428 for (auto I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); I != E; in updateLiveRangeInThenRegion()
430 auto *UseMI = I->getParent(); in updateLiveRangeInThenRegion()
431 if (UseMI->isPHI() && I->readsReg()) { in updateLiveRangeInThenRegion()
432 if (Blocks.contains(UseMI->getParent())) in updateLiveRangeInThenRegion()
433 PHIIncoming.insert(UseMI->getOperand(I.getOperandNo() + 1).getMBB()); in updateLiveRangeInThenRegion()
443 LLVM_DEBUG(dbgs() << "Found one Non-PHI use in " in updateLiveRangeInThenRegion()
445 LV->HandleVirtRegUse(Reg, MBB, *(*Uses.begin())); in updateLiveRangeInThenRegion()
447 // Process the instructions in-order in updateLiveRangeInThenRegion()
448 LLVM_DEBUG(dbgs() << "Found " << Uses.size() << " Non-PHI uses in " in updateLiveRangeInThenRegion()
452 LV->HandleVirtRegUse(Reg, MBB, MI); in updateLiveRangeInThenRegion()
458 LV->MarkVirtRegAliveInBlock(OldVarInfo, MRI->getVRegDef(Reg)->getParent(), in updateLiveRangeInThenRegion()
464 if (Blocks.contains(MI->getParent())) in updateLiveRangeInThenRegion()
465 MI->addRegisterKilled(Reg, TRI); in updateLiveRangeInThenRegion()
470 Register Reg, Register NewReg, MachineBasicBlock *Flow, in updateLiveRangeInElseRegion() argument
473 LiveVariables::VarInfo &NewVarInfo = LV->getVarInfo(NewReg); in updateLiveRangeInElseRegion()
474 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg); in updateLiveRangeInElseRegion()
478 unsigned BBNum = MBB->getNumber(); in updateLiveRangeInElseRegion()
490 if (ElseBlocks.contains((*I)->getParent())) { in updateLiveRangeInElseRegion()
500 Register Reg, MachineBasicBlock *If, MachineBasicBlock *Flow, in optimizeLiveRange() argument
506 const auto *RC = MRI->getRegClass(Reg); in optimizeLiveRange()
507 Register NewReg = MRI->createVirtualRegister(RC); in optimizeLiveRange()
508 Register UndefReg = MRI->createVirtualRegister(RC); in optimizeLiveRange()
509 MachineInstrBuilder PHI = BuildMI(*Flow, Flow->getFirstNonPHI(), DebugLoc(), in optimizeLiveRange()
510 TII->get(TargetOpcode::PHI), NewReg); in optimizeLiveRange()
511 for (auto *Pred : Flow->predecessors()) { in optimizeLiveRange()
520 for (auto &O : make_early_inc_range(MRI->use_operands(Reg))) { in optimizeLiveRange()
522 auto *UseBlock = UseMI->getParent(); in optimizeLiveRange()
525 if (UseMI->isPHI()) in optimizeLiveRange()
527 else if (UseMI->isDebugInstr()) in optimizeLiveRange()
531 // them, in which case a non-phi instruction using the original register in optimizeLiveRange()
544 // The optimized Reg is not alive through Flow blocks anymore. in optimizeLiveRange()
545 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg); in optimizeLiveRange()
546 OldVarInfo.AliveBlocks.reset(Flow->getNumber()); in optimizeLiveRange()
548 updateLiveRangeInElseRegion(Reg, NewReg, Flow, Endif, ElseBlocks); in optimizeLiveRange()
549 updateLiveRangeInThenRegion(Reg, If, Flow); in optimizeLiveRange()
558 const auto *RC = MRI->getRegClass(Reg); in optimizeWaterfallLiveRange()
559 Register NewReg = MRI->createVirtualRegister(RC); in optimizeWaterfallLiveRange()
560 Register UndefReg = MRI->createVirtualRegister(RC); in optimizeWaterfallLiveRange()
564 for (auto &O : make_early_inc_range(MRI->use_operands(Reg))) { in optimizeWaterfallLiveRange()
566 auto *UseBlock = UseMI->getParent(); in optimizeWaterfallLiveRange()
573 BuildMI(*LoopHeader, LoopHeader->getFirstNonPHI(), DebugLoc(), in optimizeWaterfallLiveRange()
574 TII->get(TargetOpcode::PHI), NewReg); in optimizeWaterfallLiveRange()
575 for (auto *Pred : LoopHeader->predecessors()) { in optimizeWaterfallLiveRange()
582 LiveVariables::VarInfo &NewVarInfo = LV->getVarInfo(NewReg); in optimizeWaterfallLiveRange()
583 LiveVariables::VarInfo &OldVarInfo = LV->getVarInfo(Reg); in optimizeWaterfallLiveRange()
588 if (MI->readsRegister(NewReg, TRI)) { in optimizeWaterfallLiveRange()
589 MI->addRegisterKilled(NewReg, TRI); in optimizeWaterfallLiveRange()
597 MachineBasicBlock *KillBlock = Kill->getParent(); in optimizeWaterfallLiveRange()
600 auto BBNum = Block->getNumber(); in optimizeWaterfallLiveRange()
637 TRI = &TII->getRegisterInfo(); in runOnMachineFunction()
649 // optimal result for nesting if-else cases. in runOnMachineFunction()
652 // Detect the if-else blocks in runOnMachineFunction()
659 // Skip unexpected control flow. in runOnMachineFunction()
660 if (!MDT->dominates(&MBB, IfTarget) || !MDT->dominates(IfTarget, Endif)) in runOnMachineFunction()
666 LLVM_DEBUG(dbgs() << "Checking IF-ELSE-ENDIF: " in runOnMachineFunction()