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"
26#include "llvm/CodeGen/MachineSSAUpdater.h"
27#include "llvm/InitializePasses.h"
28#include "llvm/Target/CGPassBuilderOption.h"
29
30#define DEBUG_TYPE "si-i1-copies"
31
32using namespace llvm;
33
34static Register
35insertUndefLaneMask(MachineBasicBlock *MBB, MachineRegisterInfo *MRI,
36 MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs);
37
38namespace {
39
40class SILowerI1Copies : public MachineFunctionPass {
41public:
42 static char ID;
43
44 SILowerI1Copies() : MachineFunctionPass(ID) {
45 initializeSILowerI1CopiesPass(*PassRegistry::getPassRegistry());
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();
54 AU.addRequired<MachineDominatorTree>();
55 AU.addRequired<MachinePostDominatorTree>();
56 MachineFunctionPass::getAnalysisUsage(AU);
57 }
58};
59
60class Vreg1LoweringHelper : public PhiLoweringHelper {
61public:
62 Vreg1LoweringHelper(MachineFunction *MF, MachineDominatorTree *DT,
63 MachinePostDominatorTree *PDT);
64
65private:
66 DenseSet<Register> ConstrainRegs;
67
68public:
69 void markAsLaneMask(Register DstReg) const override;
70 void getCandidatesForLowering(
71 SmallVectorImpl<MachineInstr *> &Vreg1Phis) const override;
72 void collectIncomingValuesFromPhi(
73 const MachineInstr *MI,
74 SmallVectorImpl<Incoming> &Incomings) const override;
75 void replaceDstReg(Register NewReg, Register OldReg,
76 MachineBasicBlock *MBB) override;
77 void buildMergeLaneMasks(MachineBasicBlock &MBB,
78 MachineBasicBlock::iterator I, const DebugLoc &DL,
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,
92 MachineDominatorTree *DT,
93 MachinePostDominatorTree *PDT)
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, RC: &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 {
128 MachinePostDominatorTree &PDT;
129 const SIInstrInfo *TII;
130
131 // For each reachable basic block, whether it is a source in the induced
132 // subgraph of the CFG.
133 DenseMap<MachineBasicBlock *, bool> ReachableMap;
134 SmallVector<MachineBasicBlock *, 4> ReachableOrdered;
135 SmallVector<MachineBasicBlock *, 4> Stack;
136 SmallVector<MachineBasicBlock *, 4> Predecessors;
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(Val: &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(Key: &DefBlock, Args: false);
159 ReachableOrdered.push_back(Elt: &DefBlock);
160
161 for (auto Incoming : Incomings) {
162 MachineBasicBlock *MBB = Incoming.Block;
163 if (MBB == &DefBlock) {
164 ReachableMap[&DefBlock] = true; // self-loop on DefBlock
165 continue;
166 }
167
168 ReachableMap.try_emplace(Key: MBB, Args: false);
169 ReachableOrdered.push_back(Elt: 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(A: &DefBlock, B: MBB))
174 append_range(C&: Stack, R: MBB->successors());
175 }
176
177 while (!Stack.empty()) {
178 MachineBasicBlock *MBB = Stack.pop_back_val();
179 if (!ReachableMap.try_emplace(Key: MBB, Args: false).second)
180 continue;
181 ReachableOrdered.push_back(Elt: MBB);
182
183 append_range(C&: Stack, R: MBB->successors());
184 }
185
186 for (MachineBasicBlock *MBB : ReachableOrdered) {
187 bool HaveReachablePred = false;
188 for (MachineBasicBlock *Pred : MBB->predecessors()) {
189 if (ReachableMap.count(Val: Pred)) {
190 HaveReachablePred = true;
191 } else {
192 Stack.push_back(Elt: Pred);
193 }
194 }
195 if (!HaveReachablePred)
196 ReachableMap[MBB] = true;
197 if (HaveReachablePred) {
198 for (MachineBasicBlock *UnreachablePred : Stack) {
199 if (!llvm::is_contained(Range&: Predecessors, Element: UnreachablePred))
200 Predecessors.push_back(Elt: 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 {
241 MachineDominatorTree &DT;
242 MachinePostDominatorTree &PDT;
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.).
247 DenseMap<MachineBasicBlock *, unsigned> Visited;
248
249 // Nearest common dominator of all visited blocks by level (level 0 is the
250 // def block). Used for seeding the SSAUpdater.
251 SmallVector<MachineBasicBlock *, 4> CommonDominators;
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;
262 SmallVector<MachineBasicBlock *, 4> Stack;
263 SmallVector<MachineBasicBlock *, 4> NextLevel;
264
265public:
266 LoopFinder(MachineDominatorTree &DT, MachinePostDominatorTree &PDT)
267 : DT(DT), PDT(PDT) {}
268
269 void initialize(MachineBasicBlock &MBB) {
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(BB: 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,
307 MachineRegisterInfo &MRI,
308 MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs,
309 ArrayRef<Incoming> Incomings = {}) {
310 assert(LoopLevel < CommonDominators.size());
311
312 MachineBasicBlock *Dom = CommonDominators[LoopLevel];
313 for (auto &Incoming : Incomings)
314 Dom = DT.findNearestCommonDominator(A: Dom, B: Incoming.Block);
315
316 if (!inLoopLevel(MBB&: *Dom, LoopLevel, Incomings)) {
317 SSAUpdater.AddAvailableValue(
318 BB: Dom, V: insertUndefLaneMask(MBB: Dom, MRI: &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(MBB&: *Pred, LoopLevel, Incomings))
324 SSAUpdater.AddAvailableValue(
325 BB: Pred, V: insertUndefLaneMask(MBB: Pred, MRI: &MRI, LaneMaskRegAttrs));
326 }
327 }
328 }
329
330private:
331 bool inLoopLevel(MachineBasicBlock &MBB, unsigned LoopLevel,
332 ArrayRef<Incoming> Incomings) const {
333 auto DomIt = Visited.find(Val: &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(Elt: DefBlock);
351 } else {
352 VisitedPostDom = PDT.getNode(BB: VisitedPostDom)->getIDom()->getBlock();
353 VisitedDom = CommonDominators.back();
354
355 for (unsigned i = 0; i < NextLevel.size();) {
356 if (PDT.dominates(A: VisitedPostDom, B: NextLevel[i])) {
357 Stack.push_back(Elt: 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(A: VisitedPostDom, B: MBB))
371 NextLevel.push_back(Elt: MBB);
372
373 Visited[MBB] = Level;
374 VisitedDom = DT.findNearestCommonDominator(A: VisitedDom, B: MBB);
375
376 for (MachineBasicBlock *Succ : MBB->successors()) {
377 if (Succ == DefBlock) {
378 if (MBB == VisitedPostDom)
379 FoundLoopLevel = std::min(a: FoundLoopLevel, b: Level + 1);
380 else
381 FoundLoopLevel = std::min(a: FoundLoopLevel, b: Level);
382 continue;
383 }
384
385 if (Visited.try_emplace(Key: Succ, Args: ~0u).second) {
386 if (MBB == VisitedPostDom)
387 NextLevel.push_back(Elt: Succ);
388 else
389 Stack.push_back(Elt: Succ);
390 }
391 }
392 }
393
394 CommonDominators.push_back(Elt: VisitedDom);
395 }
396};
397
398} // End anonymous namespace.
399
400INITIALIZE_PASS_BEGIN(SILowerI1Copies, DEBUG_TYPE, "SI Lower i1 Copies", false,
401 false)
402INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
403INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
404INITIALIZE_PASS_END(SILowerI1Copies, DEBUG_TYPE, "SI Lower i1 Copies", false,
405 false)
406
407char SILowerI1Copies::ID = 0;
408
409char &llvm::SILowerI1CopiesID = SILowerI1Copies::ID;
410
411FunctionPass *llvm::createSILowerI1CopiesPass() {
412 return new SILowerI1Copies();
413}
414
415Register
416llvm::createLaneMaskReg(MachineRegisterInfo *MRI,
417 MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs) {
418 return MRI->createVirtualRegister(RegAttr: LaneMaskRegAttrs);
419}
420
421static Register
422insertUndefLaneMask(MachineBasicBlock *MBB, MachineRegisterInfo *MRI,
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 P: 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
459static bool isVRegCompatibleReg(const SIRegisterInfo &TRI,
460 const MachineRegisterInfo &MRI,
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;
469 SmallVector<MachineInstr *, 4> DeadCopies;
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(i: 0).getReg();
477 Register SrcReg = MI.getOperand(i: 1).getReg();
478 if (!isVreg1(Reg: SrcReg))
479 continue;
480
481 if (isLaneMaskReg(Reg: DstReg) || isVreg1(Reg: 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(V: 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(Elt: &MI);
501 }
502
503 for (MachineInstr *MI : DeadCopies)
504 MI->eraseFromParent();
505 DeadCopies.clear();
506 }
507 return Changed;
508}
509
510PhiLoweringHelper::PhiLoweringHelper(MachineFunction *MF,
511 MachineDominatorTree *DT,
512 MachinePostDominatorTree *PDT)
513 : MF(MF), DT(DT), PDT(PDT) {
514 MRI = &MF->getRegInfo();
515
516 ST = &MF->getSubtarget<GCNSubtarget>();
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
539bool PhiLoweringHelper::lowerPhis() {
540 MachineSSAUpdater SSAUpdater(*MF);
541 LoopFinder LF(*DT, *PDT);
542 PhiIncomingAnalysis PIA(*PDT, TII);
543 SmallVector<MachineInstr *, 4> Vreg1Phis;
544 SmallVector<Incoming, 4> Incomings;
545
546 getCandidatesForLowering(Vreg1Phis);
547 if (Vreg1Phis.empty())
548 return false;
549
550 DT->getBase().updateDFSNumbers();
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(i: 0).getReg();
562 markAsLaneMask(DstReg);
563 initializeLaneMaskRegisterAttributes(LaneMask: DstReg);
564
565 collectIncomingValuesFromPhi(MI, Incomings);
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(C&: Incomings, Comp: [this](Incoming LHS, Incoming RHS) {
572 return DT->getNode(BB: LHS.Block)->getDFSNumIn() <
573 DT->getNode(BB: RHS.Block)->getDFSNumIn();
574 });
575
576#ifndef NDEBUG
577 PhiRegisters.insert(V: 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(Reg: DstReg))
584 DomBlocks.push_back(x: Use.getParent());
585
586 MachineBasicBlock *PostDomBound =
587 PDT->findNearestCommonDominator(Blocks: DomBlocks);
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(PostDom: PostDomBound);
594
595 SSAUpdater.Initialize(V: DstReg);
596
597 if (FoundLoopLevel) {
598 LF.addLoopEntries(LoopLevel: FoundLoopLevel, SSAUpdater, MRI&: *MRI, LaneMaskRegAttrs,
599 Incomings);
600
601 for (auto &Incoming : Incomings) {
602 Incoming.UpdatedReg = createLaneMaskReg(MRI, LaneMaskRegAttrs);
603 SSAUpdater.AddAvailableValue(BB: Incoming.Block, V: Incoming.UpdatedReg);
604 }
605
606 for (auto &Incoming : Incomings) {
607 MachineBasicBlock &IMBB = *Incoming.Block;
608 buildMergeLaneMasks(
609 MBB&: IMBB, I: getSaluInsertionAtEnd(MBB&: IMBB), DL: {}, DstReg: Incoming.UpdatedReg,
610 PrevReg: SSAUpdater.GetValueInMiddleOfBlock(BB: &IMBB), CurReg: Incoming.Reg);
611 }
612 } else {
613 // The phi is not observed from outside a loop. Use a more accurate
614 // lowering.
615 PIA.analyze(DefBlock&: MBB, Incomings);
616
617 for (MachineBasicBlock *MBB : PIA.predecessors())
618 SSAUpdater.AddAvailableValue(
619 BB: MBB, V: insertUndefLaneMask(MBB, MRI, LaneMaskRegAttrs));
620
621 for (auto &Incoming : Incomings) {
622 MachineBasicBlock &IMBB = *Incoming.Block;
623 if (PIA.isSource(MBB&: IMBB)) {
624 constrainAsLaneMask(In&: Incoming);
625 SSAUpdater.AddAvailableValue(BB: &IMBB, V: Incoming.Reg);
626 } else {
627 Incoming.UpdatedReg = createLaneMaskReg(MRI, LaneMaskRegAttrs);
628 SSAUpdater.AddAvailableValue(BB: &IMBB, V: Incoming.UpdatedReg);
629 }
630 }
631
632 for (auto &Incoming : Incomings) {
633 if (!Incoming.UpdatedReg.isValid())
634 continue;
635
636 MachineBasicBlock &IMBB = *Incoming.Block;
637 buildMergeLaneMasks(
638 MBB&: IMBB, I: getSaluInsertionAtEnd(MBB&: IMBB), DL: {}, DstReg: Incoming.UpdatedReg,
639 PrevReg: SSAUpdater.GetValueInMiddleOfBlock(BB: &IMBB), CurReg: Incoming.Reg);
640 }
641 }
642
643 Register NewReg = SSAUpdater.GetValueInMiddleOfBlock(BB: &MBB);
644 if (NewReg != DstReg) {
645 replaceDstReg(NewReg, OldReg: DstReg, MBB: &MBB);
646 MI->eraseFromParent();
647 }
648
649 Incomings.clear();
650 }
651 return true;
652}
653
654bool Vreg1LoweringHelper::lowerCopiesToI1() {
655 bool Changed = false;
656 MachineSSAUpdater SSAUpdater(*MF);
657 LoopFinder LF(*DT, *PDT);
658 SmallVector<MachineInstr *, 4> DeadCopies;
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(i: 0).getReg();
669 if (!isVreg1(Reg: DstReg))
670 continue;
671
672 Changed = true;
673
674 if (MRI->use_empty(RegNo: DstReg)) {
675 DeadCopies.push_back(Elt: &MI);
676 continue;
677 }
678
679 LLVM_DEBUG(dbgs() << "Lower Other: " << MI);
680
681 markAsLaneMask(DstReg);
682 initializeLaneMaskRegisterAttributes(LaneMask: DstReg);
683
684 if (MI.getOpcode() == AMDGPU::IMPLICIT_DEF)
685 continue;
686
687 DebugLoc DL = MI.getDebugLoc();
688 Register SrcReg = MI.getOperand(i: 1).getReg();
689 assert(!MI.getOperand(1).getSubReg());
690
691 if (!SrcReg.isVirtual() || (!isLaneMaskReg(Reg: SrcReg) && !isVreg1(Reg: 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(i: 1).setReg(TmpReg);
698 SrcReg = TmpReg;
699 } else {
700 // SrcReg needs to be live beyond copy.
701 MI.getOperand(i: 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(Reg: DstReg))
708 DomBlocks.push_back(x: Use.getParent());
709
710 MachineBasicBlock *PostDomBound =
711 PDT->findNearestCommonDominator(Blocks: DomBlocks);
712 unsigned FoundLoopLevel = LF.findLoop(PostDom: PostDomBound);
713 if (FoundLoopLevel) {
714 SSAUpdater.Initialize(V: DstReg);
715 SSAUpdater.AddAvailableValue(BB: &MBB, V: DstReg);
716 LF.addLoopEntries(LoopLevel: FoundLoopLevel, SSAUpdater, MRI&: *MRI, LaneMaskRegAttrs);
717
718 buildMergeLaneMasks(MBB, I: MI, DL, DstReg,
719 PrevReg: SSAUpdater.GetValueInMiddleOfBlock(BB: &MBB), CurReg: SrcReg);
720 DeadCopies.push_back(Elt: &MI);
721 }
722 }
723
724 for (MachineInstr *MI : DeadCopies)
725 MI->eraseFromParent();
726 DeadCopies.clear();
727 }
728 return Changed;
729}
730
731bool PhiLoweringHelper::isConstantLaneMask(Register Reg, bool &Val) const {
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(i: 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(i: 1).isImm())
752 return false;
753
754 int64_t Imm = MI->getOperand(i: 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.
783MachineBasicBlock::iterator
784PhiLoweringHelper::getSaluInsertionAtEnd(MachineBasicBlock &MBB) const {
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(MI: *I, Def&: DefsSCC, Use&: 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(MI: *InsertionPt, Def&: DefSCC, Use&: 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(Reg: DstReg, RC: 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(Reg: MI.getOperand(i: 0).getReg()))
820 Vreg1Phis.push_back(Elt: &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: i + 1).getMBB();
831 MachineInstr *IncomingDef = MRI->getUniqueVRegDef(Reg: IncomingReg);
832
833 if (IncomingDef->getOpcode() == AMDGPU::COPY) {
834 IncomingReg = IncomingDef->getOperand(i: 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(Args&: IncomingReg, Args&: IncomingMBB, Args: Register());
844 }
845}
846
847void Vreg1LoweringHelper::replaceDstReg(Register NewReg, Register OldReg,
848 MachineBasicBlock *MBB) {
849 MRI->replaceRegWith(FromReg: NewReg, ToReg: OldReg);
850}
851
852void Vreg1LoweringHelper::buildMergeLaneMasks(MachineBasicBlock &MBB,
853 MachineBasicBlock::iterator I,
854 const DebugLoc &DL,
855 Register DstReg, Register PrevReg,
856 Register CurReg) {
857 bool PrevVal = false;
858 bool PrevConstant = isConstantLaneMask(Reg: PrevReg, Val&: PrevVal);
859 bool CurVal = false;
860 bool CurConstant = isConstantLaneMask(Reg: CurReg, Val&: 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) {}
917

source code of llvm/lib/Target/AMDGPU/SILowerI1Copies.cpp