LLVM 19.0.0git
SILowerI1Copies.cpp
Go to the documentation of this file.
1//===-- SILowerI1Copies.cpp - Lower I1 Copies -----------------------------===//
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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass lowers all occurrences of i1 values (with a vreg_1 register class)
10// to lane masks (32 / 64-bit scalar registers). The pass assumes machine SSA
11// form and a wave-level control flow graph.
12//
13// Before this pass, values that are semantically i1 and are defined and used
14// within the same basic block are already represented as lane masks in scalar
15// registers. However, values that cross basic blocks are always transferred
16// between basic blocks in vreg_1 virtual registers and are lowered by this
17// pass.
18//
19// The only instructions that use or define vreg_1 virtual registers are COPY,
20// PHI, and IMPLICIT_DEF.
21//
22//===----------------------------------------------------------------------===//
23
24#include "SILowerI1Copies.h"
25#include "AMDGPU.h"
29
30#define DEBUG_TYPE "si-i1-copies"
31
32using namespace llvm;
33
34static Register
36 MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs);
37
38namespace {
39
40class SILowerI1Copies : public MachineFunctionPass {
41public:
42 static char ID;
43
44 SILowerI1Copies() : MachineFunctionPass(ID) {
46 }
47
48 bool runOnMachineFunction(MachineFunction &MF) override;
49
50 StringRef getPassName() const override { return "SI Lower i1 Copies"; }
51
52 void getAnalysisUsage(AnalysisUsage &AU) const override {
53 AU.setPreservesCFG();
57 }
58};
59
60class Vreg1LoweringHelper : public PhiLoweringHelper {
61public:
62 Vreg1LoweringHelper(MachineFunction *MF, MachineDominatorTree *DT,
64
65private:
66 DenseSet<Register> ConstrainRegs;
67
68public:
69 void markAsLaneMask(Register DstReg) const override;
71 SmallVectorImpl<MachineInstr *> &Vreg1Phis) const override;
73 const MachineInstr *MI,
74 SmallVectorImpl<Incoming> &Incomings) const override;
75 void replaceDstReg(Register NewReg, Register OldReg,
76 MachineBasicBlock *MBB) override;
79 Register DstReg, Register PrevReg,
80 Register CurReg) override;
81 void constrainAsLaneMask(Incoming &In) override;
82
83 bool lowerCopiesFromI1();
84 bool lowerCopiesToI1();
85 bool cleanConstrainRegs(bool Changed);
86 bool isVreg1(Register Reg) const {
87 return Reg.isVirtual() && MRI->getRegClass(Reg) == &AMDGPU::VReg_1RegClass;
88 }
89};
90
91Vreg1LoweringHelper::Vreg1LoweringHelper(MachineFunction *MF,
94 : PhiLoweringHelper(MF, DT, PDT) {}
95
96bool Vreg1LoweringHelper::cleanConstrainRegs(bool Changed) {
97 assert(Changed || ConstrainRegs.empty());
98 for (Register Reg : ConstrainRegs)
99 MRI->constrainRegClass(Reg, &AMDGPU::SReg_1_XEXECRegClass);
100 ConstrainRegs.clear();
101
102 return Changed;
103}
104
105/// Helper class that determines the relationship between incoming values of a
106/// phi in the control flow graph to determine where an incoming value can
107/// simply be taken as a scalar lane mask as-is, and where it needs to be
108/// merged with another, previously defined lane mask.
109///
110/// The approach is as follows:
111/// - Determine all basic blocks which, starting from the incoming blocks,
112/// a wave may reach before entering the def block (the block containing the
113/// phi).
114/// - If an incoming block has no predecessors in this set, we can take the
115/// incoming value as a scalar lane mask as-is.
116/// -- A special case of this is when the def block has a self-loop.
117/// - Otherwise, the incoming value needs to be merged with a previously
118/// defined lane mask.
119/// - If there is a path into the set of reachable blocks that does _not_ go
120/// through an incoming block where we can take the scalar lane mask as-is,
121/// we need to invent an available value for the SSAUpdater. Choices are
122/// 0 and undef, with differing consequences for how to merge values etc.
123///
124/// TODO: We could use region analysis to quickly skip over SESE regions during
125/// the traversal.
126///
127class PhiIncomingAnalysis {
129 const SIInstrInfo *TII;
130
131 // For each reachable basic block, whether it is a source in the induced
132 // subgraph of the CFG.
137
138public:
139 PhiIncomingAnalysis(MachinePostDominatorTree &PDT, const SIInstrInfo *TII)
140 : PDT(PDT), TII(TII) {}
141
142 /// Returns whether \p MBB is a source in the induced subgraph of reachable
143 /// blocks.
144 bool isSource(MachineBasicBlock &MBB) const {
145 return ReachableMap.find(&MBB)->second;
146 }
147
148 ArrayRef<MachineBasicBlock *> predecessors() const { return Predecessors; }
149
150 void analyze(MachineBasicBlock &DefBlock, ArrayRef<Incoming> Incomings) {
151 assert(Stack.empty());
152 ReachableMap.clear();
153 ReachableOrdered.clear();
154 Predecessors.clear();
155
156 // Insert the def block first, so that it acts as an end point for the
157 // traversal.
158 ReachableMap.try_emplace(&DefBlock, false);
159 ReachableOrdered.push_back(&DefBlock);
160
161 for (auto Incoming : Incomings) {
163 if (MBB == &DefBlock) {
164 ReachableMap[&DefBlock] = true; // self-loop on DefBlock
165 continue;
166 }
167
168 ReachableMap.try_emplace(MBB, false);
169 ReachableOrdered.push_back(MBB);
170
171 // If this block has a divergent terminator and the def block is its
172 // post-dominator, the wave may first visit the other successors.
173 if (TII->hasDivergentBranch(MBB) && PDT.dominates(&DefBlock, MBB))
174 append_range(Stack, MBB->successors());
175 }
176
177 while (!Stack.empty()) {
178 MachineBasicBlock *MBB = Stack.pop_back_val();
179 if (!ReachableMap.try_emplace(MBB, false).second)
180 continue;
181 ReachableOrdered.push_back(MBB);
182
183 append_range(Stack, MBB->successors());
184 }
185
186 for (MachineBasicBlock *MBB : ReachableOrdered) {
187 bool HaveReachablePred = false;
188 for (MachineBasicBlock *Pred : MBB->predecessors()) {
189 if (ReachableMap.count(Pred)) {
190 HaveReachablePred = true;
191 } else {
192 Stack.push_back(Pred);
193 }
194 }
195 if (!HaveReachablePred)
196 ReachableMap[MBB] = true;
197 if (HaveReachablePred) {
198 for (MachineBasicBlock *UnreachablePred : Stack) {
199 if (!llvm::is_contained(Predecessors, UnreachablePred))
200 Predecessors.push_back(UnreachablePred);
201 }
202 }
203 Stack.clear();
204 }
205 }
206};
207
208/// Helper class that detects loops which require us to lower an i1 COPY into
209/// bitwise manipulation.
210///
211/// Unfortunately, we cannot use LoopInfo because LoopInfo does not distinguish
212/// between loops with the same header. Consider this example:
213///
214/// A-+-+
215/// | | |
216/// B-+ |
217/// | |
218/// C---+
219///
220/// A is the header of a loop containing A, B, and C as far as LoopInfo is
221/// concerned. However, an i1 COPY in B that is used in C must be lowered to
222/// bitwise operations to combine results from different loop iterations when
223/// B has a divergent branch (since by default we will compile this code such
224/// that threads in a wave are merged at the entry of C).
225///
226/// The following rule is implemented to determine whether bitwise operations
227/// are required: use the bitwise lowering for a def in block B if a backward
228/// edge to B is reachable without going through the nearest common
229/// post-dominator of B and all uses of the def.
230///
231/// TODO: This rule is conservative because it does not check whether the
232/// relevant branches are actually divergent.
233///
234/// The class is designed to cache the CFG traversal so that it can be re-used
235/// for multiple defs within the same basic block.
236///
237/// TODO: We could use region analysis to quickly skip over SESE regions during
238/// the traversal.
239///
240class LoopFinder {
243
244 // All visited / reachable block, tagged by level (level 0 is the def block,
245 // level 1 are all blocks reachable including but not going through the def
246 // block's IPDOM, etc.).
248
249 // Nearest common dominator of all visited blocks by level (level 0 is the
250 // def block). Used for seeding the SSAUpdater.
252
253 // Post-dominator of all visited blocks.
254 MachineBasicBlock *VisitedPostDom = nullptr;
255
256 // Level at which a loop was found: 0 is not possible; 1 = a backward edge is
257 // reachable without going through the IPDOM of the def block (if the IPDOM
258 // itself has an edge to the def block, the loop level is 2), etc.
259 unsigned FoundLoopLevel = ~0u;
260
261 MachineBasicBlock *DefBlock = nullptr;
264
265public:
267 : DT(DT), PDT(PDT) {}
268
270 Visited.clear();
271 CommonDominators.clear();
272 Stack.clear();
273 NextLevel.clear();
274 VisitedPostDom = nullptr;
275 FoundLoopLevel = ~0u;
276
277 DefBlock = &MBB;
278 }
279
280 /// Check whether a backward edge can be reached without going through the
281 /// given \p PostDom of the def block.
282 ///
283 /// Return the level of \p PostDom if a loop was found, or 0 otherwise.
284 unsigned findLoop(MachineBasicBlock *PostDom) {
285 MachineDomTreeNode *PDNode = PDT.getNode(DefBlock);
286
287 if (!VisitedPostDom)
288 advanceLevel();
289
290 unsigned Level = 0;
291 while (PDNode->getBlock() != PostDom) {
292 if (PDNode->getBlock() == VisitedPostDom)
293 advanceLevel();
294 PDNode = PDNode->getIDom();
295 Level++;
296 if (FoundLoopLevel == Level)
297 return Level;
298 }
299
300 return 0;
301 }
302
303 /// Add undef values dominating the loop and the optionally given additional
304 /// blocks, so that the SSA updater doesn't have to search all the way to the
305 /// function entry.
306 void addLoopEntries(unsigned LoopLevel, MachineSSAUpdater &SSAUpdater,
308 MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs,
309 ArrayRef<Incoming> Incomings = {}) {
310 assert(LoopLevel < CommonDominators.size());
311
312 MachineBasicBlock *Dom = CommonDominators[LoopLevel];
313 for (auto &Incoming : Incomings)
315
316 if (!inLoopLevel(*Dom, LoopLevel, Incomings)) {
318 Dom, insertUndefLaneMask(Dom, &MRI, LaneMaskRegAttrs));
319 } else {
320 // The dominator is part of the loop or the given blocks, so add the
321 // undef value to unreachable predecessors instead.
322 for (MachineBasicBlock *Pred : Dom->predecessors()) {
323 if (!inLoopLevel(*Pred, LoopLevel, Incomings))
325 Pred, insertUndefLaneMask(Pred, &MRI, LaneMaskRegAttrs));
326 }
327 }
328 }
329
330private:
331 bool inLoopLevel(MachineBasicBlock &MBB, unsigned LoopLevel,
332 ArrayRef<Incoming> Incomings) const {
333 auto DomIt = Visited.find(&MBB);
334 if (DomIt != Visited.end() && DomIt->second <= LoopLevel)
335 return true;
336
337 for (auto &Incoming : Incomings)
338 if (Incoming.Block == &MBB)
339 return true;
340
341 return false;
342 }
343
344 void advanceLevel() {
345 MachineBasicBlock *VisitedDom;
346
347 if (!VisitedPostDom) {
348 VisitedPostDom = DefBlock;
349 VisitedDom = DefBlock;
350 Stack.push_back(DefBlock);
351 } else {
352 VisitedPostDom = PDT.getNode(VisitedPostDom)->getIDom()->getBlock();
353 VisitedDom = CommonDominators.back();
354
355 for (unsigned i = 0; i < NextLevel.size();) {
356 if (PDT.dominates(VisitedPostDom, NextLevel[i])) {
357 Stack.push_back(NextLevel[i]);
358
359 NextLevel[i] = NextLevel.back();
360 NextLevel.pop_back();
361 } else {
362 i++;
363 }
364 }
365 }
366
367 unsigned Level = CommonDominators.size();
368 while (!Stack.empty()) {
369 MachineBasicBlock *MBB = Stack.pop_back_val();
370 if (!PDT.dominates(VisitedPostDom, MBB))
371 NextLevel.push_back(MBB);
372
373 Visited[MBB] = Level;
374 VisitedDom = DT.findNearestCommonDominator(VisitedDom, MBB);
375
376 for (MachineBasicBlock *Succ : MBB->successors()) {
377 if (Succ == DefBlock) {
378 if (MBB == VisitedPostDom)
379 FoundLoopLevel = std::min(FoundLoopLevel, Level + 1);
380 else
381 FoundLoopLevel = std::min(FoundLoopLevel, Level);
382 continue;
383 }
384
385 if (Visited.try_emplace(Succ, ~0u).second) {
386 if (MBB == VisitedPostDom)
387 NextLevel.push_back(Succ);
388 else
389 Stack.push_back(Succ);
390 }
391 }
392 }
393
394 CommonDominators.push_back(VisitedDom);
395 }
396};
397
398} // End anonymous namespace.
399
400INITIALIZE_PASS_BEGIN(SILowerI1Copies, DEBUG_TYPE, "SI Lower i1 Copies", false,
401 false)
405 false)
406
407char SILowerI1Copies::ID = 0;
408
409char &llvm::SILowerI1CopiesID = SILowerI1Copies::ID;
410
412 return new SILowerI1Copies();
413}
414
417 MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs) {
418 return MRI->createVirtualRegister(LaneMaskRegAttrs);
419}
420
421static Register
423 MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs) {
424 MachineFunction &MF = *MBB->getParent();
425 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
426 const SIInstrInfo *TII = ST.getInstrInfo();
427 Register UndefReg = createLaneMaskReg(MRI, LaneMaskRegAttrs);
428 BuildMI(*MBB, MBB->getFirstTerminator(), {}, TII->get(AMDGPU::IMPLICIT_DEF),
429 UndefReg);
430 return UndefReg;
431}
432
433/// Lower all instructions that def or use vreg_1 registers.
434///
435/// In a first pass, we lower COPYs from vreg_1 to vector registers, as can
436/// occur around inline assembly. We do this first, before vreg_1 registers
437/// are changed to scalar mask registers.
438///
439/// Then we lower all defs of vreg_1 registers. Phi nodes are lowered before
440/// all others, because phi lowering looks through copies and can therefore
441/// often make copy lowering unnecessary.
442bool SILowerI1Copies::runOnMachineFunction(MachineFunction &TheMF) {
443 // Only need to run this in SelectionDAG path.
444 if (TheMF.getProperties().hasProperty(
445 MachineFunctionProperties::Property::Selected))
446 return false;
447
448 Vreg1LoweringHelper Helper(&TheMF, &getAnalysis<MachineDominatorTree>(),
449 &getAnalysis<MachinePostDominatorTree>());
450
451 bool Changed = false;
452 Changed |= Helper.lowerCopiesFromI1();
453 Changed |= Helper.lowerPhis();
454 Changed |= Helper.lowerCopiesToI1();
455 return Helper.cleanConstrainRegs(Changed);
456}
457
458#ifndef NDEBUG
461 Register Reg) {
462 unsigned Size = TRI.getRegSizeInBits(Reg, MRI);
463 return Size == 1 || Size == 32;
464}
465#endif
466
467bool Vreg1LoweringHelper::lowerCopiesFromI1() {
468 bool Changed = false;
470
471 for (MachineBasicBlock &MBB : *MF) {
472 for (MachineInstr &MI : MBB) {
473 if (MI.getOpcode() != AMDGPU::COPY)
474 continue;
475
476 Register DstReg = MI.getOperand(0).getReg();
477 Register SrcReg = MI.getOperand(1).getReg();
478 if (!isVreg1(SrcReg))
479 continue;
480
481 if (isLaneMaskReg(DstReg) || isVreg1(DstReg))
482 continue;
483
484 Changed = true;
485
486 // Copy into a 32-bit vector register.
487 LLVM_DEBUG(dbgs() << "Lower copy from i1: " << MI);
488 DebugLoc DL = MI.getDebugLoc();
489
490 assert(isVRegCompatibleReg(TII->getRegisterInfo(), *MRI, DstReg));
491 assert(!MI.getOperand(0).getSubReg());
492
493 ConstrainRegs.insert(SrcReg);
494 BuildMI(MBB, MI, DL, TII->get(AMDGPU::V_CNDMASK_B32_e64), DstReg)
495 .addImm(0)
496 .addImm(0)
497 .addImm(0)
498 .addImm(-1)
499 .addReg(SrcReg);
500 DeadCopies.push_back(&MI);
501 }
502
503 for (MachineInstr *MI : DeadCopies)
504 MI->eraseFromParent();
505 DeadCopies.clear();
506 }
507 return Changed;
508}
509
513 : MF(MF), DT(DT), PDT(PDT) {
514 MRI = &MF->getRegInfo();
515
517 TII = ST->getInstrInfo();
518 IsWave32 = ST->isWave32();
519
520 if (IsWave32) {
521 ExecReg = AMDGPU::EXEC_LO;
522 MovOp = AMDGPU::S_MOV_B32;
523 AndOp = AMDGPU::S_AND_B32;
524 OrOp = AMDGPU::S_OR_B32;
525 XorOp = AMDGPU::S_XOR_B32;
526 AndN2Op = AMDGPU::S_ANDN2_B32;
527 OrN2Op = AMDGPU::S_ORN2_B32;
528 } else {
529 ExecReg = AMDGPU::EXEC;
530 MovOp = AMDGPU::S_MOV_B64;
531 AndOp = AMDGPU::S_AND_B64;
532 OrOp = AMDGPU::S_OR_B64;
533 XorOp = AMDGPU::S_XOR_B64;
534 AndN2Op = AMDGPU::S_ANDN2_B64;
535 OrN2Op = AMDGPU::S_ORN2_B64;
536 }
537}
538
541 LoopFinder LF(*DT, *PDT);
542 PhiIncomingAnalysis PIA(*PDT, TII);
544 SmallVector<Incoming, 4> Incomings;
545
546 getCandidatesForLowering(Vreg1Phis);
547 if (Vreg1Phis.empty())
548 return false;
549
551 MachineBasicBlock *PrevMBB = nullptr;
552 for (MachineInstr *MI : Vreg1Phis) {
553 MachineBasicBlock &MBB = *MI->getParent();
554 if (&MBB != PrevMBB) {
555 LF.initialize(MBB);
556 PrevMBB = &MBB;
557 }
558
559 LLVM_DEBUG(dbgs() << "Lower PHI: " << *MI);
560
561 Register DstReg = MI->getOperand(0).getReg();
562 markAsLaneMask(DstReg);
564
566
567 // Sort the incomings such that incoming values that dominate other incoming
568 // values are sorted earlier. This allows us to do some amount of on-the-fly
569 // constant folding.
570 // Incoming with smaller DFSNumIn goes first, DFSNumIn is 0 for entry block.
571 llvm::sort(Incomings, [this](Incoming LHS, Incoming RHS) {
572 return DT->getNode(LHS.Block)->getDFSNumIn() <
573 DT->getNode(RHS.Block)->getDFSNumIn();
574 });
575
576#ifndef NDEBUG
577 PhiRegisters.insert(DstReg);
578#endif
579
580 // Phis in a loop that are observed outside the loop receive a simple but
581 // conservatively correct treatment.
582 std::vector<MachineBasicBlock *> DomBlocks = {&MBB};
583 for (MachineInstr &Use : MRI->use_instructions(DstReg))
584 DomBlocks.push_back(Use.getParent());
585
586 MachineBasicBlock *PostDomBound =
588
589 // FIXME: This fails to find irreducible cycles. If we have a def (other
590 // than a constant) in a pair of blocks that end up looping back to each
591 // other, it will be mishandle. Due to structurization this shouldn't occur
592 // in practice.
593 unsigned FoundLoopLevel = LF.findLoop(PostDomBound);
594
595 SSAUpdater.Initialize(DstReg);
596
597 if (FoundLoopLevel) {
598 LF.addLoopEntries(FoundLoopLevel, SSAUpdater, *MRI, LaneMaskRegAttrs,
599 Incomings);
600
601 for (auto &Incoming : Incomings) {
604 }
605
606 for (auto &Incoming : Incomings) {
611 }
612 } else {
613 // The phi is not observed from outside a loop. Use a more accurate
614 // lowering.
615 PIA.analyze(MBB, Incomings);
616
617 for (MachineBasicBlock *MBB : PIA.predecessors())
620
621 for (auto &Incoming : Incomings) {
623 if (PIA.isSource(IMBB)) {
626 } else {
629 }
630 }
631
632 for (auto &Incoming : Incomings) {
634 continue;
635
640 }
641 }
642
644 if (NewReg != DstReg) {
645 replaceDstReg(NewReg, DstReg, &MBB);
646 MI->eraseFromParent();
647 }
648
649 Incomings.clear();
650 }
651 return true;
652}
653
654bool Vreg1LoweringHelper::lowerCopiesToI1() {
655 bool Changed = false;
657 LoopFinder LF(*DT, *PDT);
659
660 for (MachineBasicBlock &MBB : *MF) {
661 LF.initialize(MBB);
662
663 for (MachineInstr &MI : MBB) {
664 if (MI.getOpcode() != AMDGPU::IMPLICIT_DEF &&
665 MI.getOpcode() != AMDGPU::COPY)
666 continue;
667
668 Register DstReg = MI.getOperand(0).getReg();
669 if (!isVreg1(DstReg))
670 continue;
671
672 Changed = true;
673
674 if (MRI->use_empty(DstReg)) {
675 DeadCopies.push_back(&MI);
676 continue;
677 }
678
679 LLVM_DEBUG(dbgs() << "Lower Other: " << MI);
680
681 markAsLaneMask(DstReg);
682 initializeLaneMaskRegisterAttributes(DstReg);
683
684 if (MI.getOpcode() == AMDGPU::IMPLICIT_DEF)
685 continue;
686
687 DebugLoc DL = MI.getDebugLoc();
688 Register SrcReg = MI.getOperand(1).getReg();
689 assert(!MI.getOperand(1).getSubReg());
690
691 if (!SrcReg.isVirtual() || (!isLaneMaskReg(SrcReg) && !isVreg1(SrcReg))) {
692 assert(TII->getRegisterInfo().getRegSizeInBits(SrcReg, *MRI) == 32);
693 Register TmpReg = createLaneMaskReg(MRI, LaneMaskRegAttrs);
694 BuildMI(MBB, MI, DL, TII->get(AMDGPU::V_CMP_NE_U32_e64), TmpReg)
695 .addReg(SrcReg)
696 .addImm(0);
697 MI.getOperand(1).setReg(TmpReg);
698 SrcReg = TmpReg;
699 } else {
700 // SrcReg needs to be live beyond copy.
701 MI.getOperand(1).setIsKill(false);
702 }
703
704 // Defs in a loop that are observed outside the loop must be transformed
705 // into appropriate bit manipulation.
706 std::vector<MachineBasicBlock *> DomBlocks = {&MBB};
707 for (MachineInstr &Use : MRI->use_instructions(DstReg))
708 DomBlocks.push_back(Use.getParent());
709
710 MachineBasicBlock *PostDomBound =
711 PDT->findNearestCommonDominator(DomBlocks);
712 unsigned FoundLoopLevel = LF.findLoop(PostDomBound);
713 if (FoundLoopLevel) {
714 SSAUpdater.Initialize(DstReg);
716 LF.addLoopEntries(FoundLoopLevel, SSAUpdater, *MRI, LaneMaskRegAttrs);
717
718 buildMergeLaneMasks(MBB, MI, DL, DstReg,
720 DeadCopies.push_back(&MI);
721 }
722 }
723
724 for (MachineInstr *MI : DeadCopies)
725 MI->eraseFromParent();
726 DeadCopies.clear();
727 }
728 return Changed;
729}
730
732 const MachineInstr *MI;
733 for (;;) {
734 MI = MRI->getUniqueVRegDef(Reg);
735 if (MI->getOpcode() == AMDGPU::IMPLICIT_DEF)
736 return true;
737
738 if (MI->getOpcode() != AMDGPU::COPY)
739 break;
740
741 Reg = MI->getOperand(1).getReg();
742 if (!Reg.isVirtual())
743 return false;
744 if (!isLaneMaskReg(Reg))
745 return false;
746 }
747
748 if (MI->getOpcode() != MovOp)
749 return false;
750
751 if (!MI->getOperand(1).isImm())
752 return false;
753
754 int64_t Imm = MI->getOperand(1).getImm();
755 if (Imm == 0) {
756 Val = false;
757 return true;
758 }
759 if (Imm == -1) {
760 Val = true;
761 return true;
762 }
763
764 return false;
765}
766
767static void instrDefsUsesSCC(const MachineInstr &MI, bool &Def, bool &Use) {
768 Def = false;
769 Use = false;
770
771 for (const MachineOperand &MO : MI.operands()) {
772 if (MO.isReg() && MO.getReg() == AMDGPU::SCC) {
773 if (MO.isUse())
774 Use = true;
775 else
776 Def = true;
777 }
778 }
779}
780
781/// Return a point at the end of the given \p MBB to insert SALU instructions
782/// for lane mask calculation. Take terminators and SCC into account.
785 auto InsertionPt = MBB.getFirstTerminator();
786 bool TerminatorsUseSCC = false;
787 for (auto I = InsertionPt, E = MBB.end(); I != E; ++I) {
788 bool DefsSCC;
789 instrDefsUsesSCC(*I, DefsSCC, TerminatorsUseSCC);
790 if (TerminatorsUseSCC || DefsSCC)
791 break;
792 }
793
794 if (!TerminatorsUseSCC)
795 return InsertionPt;
796
797 while (InsertionPt != MBB.begin()) {
798 InsertionPt--;
799
800 bool DefSCC, UseSCC;
801 instrDefsUsesSCC(*InsertionPt, DefSCC, UseSCC);
802 if (DefSCC)
803 return InsertionPt;
804 }
805
806 // We should have at least seen an IMPLICIT_DEF or COPY
807 llvm_unreachable("SCC used by terminator but no def in block");
808}
809
810// VReg_1 -> SReg_32 or SReg_64
811void Vreg1LoweringHelper::markAsLaneMask(Register DstReg) const {
812 MRI->setRegClass(DstReg, ST->getBoolRC());
813}
814
815void Vreg1LoweringHelper::getCandidatesForLowering(
816 SmallVectorImpl<MachineInstr *> &Vreg1Phis) const {
817 for (MachineBasicBlock &MBB : *MF) {
818 for (MachineInstr &MI : MBB.phis()) {
819 if (isVreg1(MI.getOperand(0).getReg()))
820 Vreg1Phis.push_back(&MI);
821 }
822 }
823}
824
825void Vreg1LoweringHelper::collectIncomingValuesFromPhi(
826 const MachineInstr *MI, SmallVectorImpl<Incoming> &Incomings) const {
827 for (unsigned i = 1; i < MI->getNumOperands(); i += 2) {
828 assert(i + 1 < MI->getNumOperands());
829 Register IncomingReg = MI->getOperand(i).getReg();
830 MachineBasicBlock *IncomingMBB = MI->getOperand(i + 1).getMBB();
831 MachineInstr *IncomingDef = MRI->getUniqueVRegDef(IncomingReg);
832
833 if (IncomingDef->getOpcode() == AMDGPU::COPY) {
834 IncomingReg = IncomingDef->getOperand(1).getReg();
835 assert(isLaneMaskReg(IncomingReg) || isVreg1(IncomingReg));
836 assert(!IncomingDef->getOperand(1).getSubReg());
837 } else if (IncomingDef->getOpcode() == AMDGPU::IMPLICIT_DEF) {
838 continue;
839 } else {
840 assert(IncomingDef->isPHI() || PhiRegisters.count(IncomingReg));
841 }
842
843 Incomings.emplace_back(IncomingReg, IncomingMBB, Register());
844 }
845}
846
847void Vreg1LoweringHelper::replaceDstReg(Register NewReg, Register OldReg,
849 MRI->replaceRegWith(NewReg, OldReg);
850}
851
852void Vreg1LoweringHelper::buildMergeLaneMasks(MachineBasicBlock &MBB,
854 const DebugLoc &DL,
855 Register DstReg, Register PrevReg,
856 Register CurReg) {
857 bool PrevVal = false;
858 bool PrevConstant = isConstantLaneMask(PrevReg, PrevVal);
859 bool CurVal = false;
860 bool CurConstant = isConstantLaneMask(CurReg, CurVal);
861
862 if (PrevConstant && CurConstant) {
863 if (PrevVal == CurVal) {
864 BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), DstReg).addReg(CurReg);
865 } else if (CurVal) {
866 BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), DstReg).addReg(ExecReg);
867 } else {
868 BuildMI(MBB, I, DL, TII->get(XorOp), DstReg)
869 .addReg(ExecReg)
870 .addImm(-1);
871 }
872 return;
873 }
874
875 Register PrevMaskedReg;
876 Register CurMaskedReg;
877 if (!PrevConstant) {
878 if (CurConstant && CurVal) {
879 PrevMaskedReg = PrevReg;
880 } else {
881 PrevMaskedReg = createLaneMaskReg(MRI, LaneMaskRegAttrs);
882 BuildMI(MBB, I, DL, TII->get(AndN2Op), PrevMaskedReg)
883 .addReg(PrevReg)
884 .addReg(ExecReg);
885 }
886 }
887 if (!CurConstant) {
888 // TODO: check whether CurReg is already masked by EXEC
889 if (PrevConstant && PrevVal) {
890 CurMaskedReg = CurReg;
891 } else {
892 CurMaskedReg = createLaneMaskReg(MRI, LaneMaskRegAttrs);
893 BuildMI(MBB, I, DL, TII->get(AndOp), CurMaskedReg)
894 .addReg(CurReg)
895 .addReg(ExecReg);
896 }
897 }
898
899 if (PrevConstant && !PrevVal) {
900 BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), DstReg)
901 .addReg(CurMaskedReg);
902 } else if (CurConstant && !CurVal) {
903 BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), DstReg)
904 .addReg(PrevMaskedReg);
905 } else if (PrevConstant && PrevVal) {
906 BuildMI(MBB, I, DL, TII->get(OrN2Op), DstReg)
907 .addReg(CurMaskedReg)
908 .addReg(ExecReg);
909 } else {
910 BuildMI(MBB, I, DL, TII->get(OrOp), DstReg)
911 .addReg(PrevMaskedReg)
912 .addReg(CurMaskedReg ? CurMaskedReg : ExecReg);
913 }
914}
915
916void Vreg1LoweringHelper::constrainAsLaneMask(Incoming &In) {}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_DEBUG(X)
Definition: Debug.h:101
uint64_t Size
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static void instrDefsUsesSCC(const MachineInstr &MI, bool &Def, bool &Use)
static Register insertUndefLaneMask(MachineBasicBlock *MBB, MachineRegisterInfo *MRI, MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs)
SI Lower i1 Copies
static bool isVRegCompatibleReg(const SIRegisterInfo &TRI, const MachineRegisterInfo &MRI, Register Reg)
#define DEBUG_TYPE
Interface definition of the PhiLoweringHelper class that implements lane mask merging algorithm for d...
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
Value * RHS
Value * LHS
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:269
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A debug info location.
Definition: DebugLoc.h:33
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:235
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
iterator end()
Definition: DenseMap.h:84
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Base class for the actual dominator tree node.
DomTreeNodeBase * getIDom() const
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
NodeT * getBlock() const
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
const SIInstrInfo * getInstrInfo() const override
Definition: GCNSubtarget.h:251
bool isWave32() const
iterator_range< iterator > phis()
Returns a range that iterates over the phis in the basic block.
void push_back(MachineInstr *MI)
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
MachineDomTree & getBase()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
bool hasProperty(Property P) const
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const MachineFunctionProperties & getProperties() const
Get the function properties.
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
Definition: MachineInstr.h:69
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:546
bool isPHI() const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:556
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
Register getReg() const
getReg - Returns the register number.
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B) const
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
iterator_range< use_instr_iterator > use_instructions(Register Reg) const
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
MachineSSAUpdater - This class updates SSA form for a set of virtual registers defined in multiple bl...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
PhiLoweringHelper(MachineFunction *MF, MachineDominatorTree *DT, MachinePostDominatorTree *PDT)
bool isLaneMaskReg(Register Reg) const
MachineRegisterInfo * MRI
MachineDominatorTree * DT
DenseSet< Register > PhiRegisters
virtual void getCandidatesForLowering(SmallVectorImpl< MachineInstr * > &Vreg1Phis) const =0
MachineFunction * MF
virtual void constrainAsLaneMask(Incoming &In)=0
virtual void collectIncomingValuesFromPhi(const MachineInstr *MI, SmallVectorImpl< Incoming > &Incomings) const =0
virtual void markAsLaneMask(Register DstReg) const =0
MachinePostDominatorTree * PDT
const GCNSubtarget * ST
const SIInstrInfo * TII
MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs
MachineBasicBlock::iterator getSaluInsertionAtEnd(MachineBasicBlock &MBB) const
Return a point at the end of the given MBB to insert SALU instructions for lane mask calculation.
void initializeLaneMaskRegisterAttributes(Register LaneMask)
bool isConstantLaneMask(Register Reg, bool &Val) const
virtual void buildMergeLaneMasks(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, const DebugLoc &DL, Register DstReg, Register PrevReg, Register CurReg)=0
virtual void replaceDstReg(Register NewReg, Register OldReg, MachineBasicBlock *MBB)=0
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
constexpr bool isValid() const
Definition: Register.h:116
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:40
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
Definition: SSAUpdater.cpp:53
Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block.
Definition: SSAUpdater.cpp:98
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdater.cpp:70
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
char & SILowerI1CopiesID
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2082
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1656
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Register createLaneMaskReg(MachineRegisterInfo *MRI, MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs)
FunctionPass * createSILowerI1CopiesPass()
void initializeSILowerI1CopiesPass(PassRegistry &)
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
MachineBasicBlock * Block
Register UpdatedReg
All attributes(register class or bank and low-level type) a virtual register can have.