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/MachineIDFSSAUpdater.h"
27#include "llvm/InitializePasses.h"
28
29#define DEBUG_TYPE "si-i1-copies"
30
31using namespace llvm;
32
33static Register
34insertUndefLaneMask(MachineBasicBlock *MBB, MachineRegisterInfo *MRI,
35 MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs);
36
37namespace {
38
39class Vreg1LoweringHelper : public AMDGPU::PhiLoweringHelper {
40public:
41 Vreg1LoweringHelper(MachineFunction *MF, MachineDominatorTree *DT,
42 MachinePostDominatorTree *PDT);
43
44private:
45 DenseSet<Register> ConstrainRegs;
46
47public:
48 void markAsLaneMask(Register DstReg) const override;
49 void getCandidatesForLowering(
50 SmallVectorImpl<MachineInstr *> &Vreg1Phis) const override;
51 void collectIncomingValuesFromPhi(
52 const MachineInstr *MI,
53 SmallVectorImpl<AMDGPU::Incoming> &Incomings) const override;
54 void replaceDstReg(Register NewReg, Register OldReg,
55 MachineBasicBlock *MBB) override;
56 void buildMergeLaneMasks(MachineBasicBlock &MBB,
57 MachineBasicBlock::iterator I, const DebugLoc &DL,
58 Register DstReg, Register PrevReg,
59 Register CurReg) override;
60 void constrainAsLaneMask(AMDGPU::Incoming &In) override;
61
62 bool lowerCopiesFromI1();
63 bool lowerCopiesToI1();
64 bool cleanConstrainRegs(bool Changed);
65 bool isVreg1(Register Reg) const {
66 return Reg.isVirtual() && MRI->getRegClass(Reg) == &AMDGPU::VReg_1RegClass;
67 }
68};
69
70Vreg1LoweringHelper::Vreg1LoweringHelper(MachineFunction *MF,
71 MachineDominatorTree *DT,
72 MachinePostDominatorTree *PDT)
73 : PhiLoweringHelper(MF, DT, PDT) {}
74
75bool Vreg1LoweringHelper::cleanConstrainRegs(bool Changed) {
76 assert(Changed || ConstrainRegs.empty());
77 for (Register Reg : ConstrainRegs)
78 MRI->constrainRegClass(Reg, RC: TII->getRegisterInfo().getWaveMaskRegClass());
79 ConstrainRegs.clear();
80
81 return Changed;
82}
83
84/// Helper class that determines the relationship between incoming values of a
85/// phi in the control flow graph to determine where an incoming value can
86/// simply be taken as a scalar lane mask as-is, and where it needs to be
87/// merged with another, previously defined lane mask.
88///
89/// The approach is as follows:
90/// - Determine all basic blocks which, starting from the incoming blocks,
91/// a wave may reach before entering the def block (the block containing the
92/// phi).
93/// - If an incoming block has no predecessors in this set, we can take the
94/// incoming value as a scalar lane mask as-is.
95/// -- A special case of this is when the def block has a self-loop.
96/// - Otherwise, the incoming value needs to be merged with a previously
97/// defined lane mask.
98/// - If there is a path into the set of reachable blocks that does _not_ go
99/// through an incoming block where we can take the scalar lane mask as-is,
100/// we need to invent an available value for the SSAUpdater. Choices are
101/// 0 and undef, with differing consequences for how to merge values etc.
102///
103/// TODO: We could use region analysis to quickly skip over SESE regions during
104/// the traversal.
105///
106class PhiIncomingAnalysis {
107 MachinePostDominatorTree &PDT;
108 const SIInstrInfo *TII;
109
110 // For each reachable basic block, whether it is a source in the induced
111 // subgraph of the CFG.
112 MapVector<MachineBasicBlock *, bool> ReachableMap;
113 SmallVector<MachineBasicBlock *, 4> Stack;
114 SmallVector<MachineBasicBlock *, 4> Predecessors;
115
116public:
117 PhiIncomingAnalysis(MachinePostDominatorTree &PDT, const SIInstrInfo *TII)
118 : PDT(PDT), TII(TII) {}
119
120 /// Returns whether \p MBB is a source in the induced subgraph of reachable
121 /// blocks.
122 bool isSource(MachineBasicBlock &MBB) const {
123 return ReachableMap.find(Key: &MBB)->second;
124 }
125
126 ArrayRef<MachineBasicBlock *> predecessors() const { return Predecessors; }
127
128 void analyze(MachineBasicBlock &DefBlock,
129 ArrayRef<AMDGPU::Incoming> Incomings) {
130 assert(Stack.empty());
131 ReachableMap.clear();
132 Predecessors.clear();
133
134 // Insert the def block first, so that it acts as an end point for the
135 // traversal.
136 ReachableMap.try_emplace(Key: &DefBlock, Args: false);
137
138 for (auto Incoming : Incomings) {
139 MachineBasicBlock *MBB = Incoming.Block;
140 if (MBB == &DefBlock) {
141 ReachableMap[&DefBlock] = true; // self-loop on DefBlock
142 continue;
143 }
144
145 ReachableMap.try_emplace(Key: MBB, Args: false);
146
147 // If this block has a divergent terminator and the def block is its
148 // post-dominator, the wave may first visit the other successors.
149 if (TII->hasDivergentBranch(MBB) && PDT.dominates(A: &DefBlock, B: MBB))
150 append_range(C&: Stack, R: MBB->successors());
151 }
152
153 while (!Stack.empty()) {
154 MachineBasicBlock *MBB = Stack.pop_back_val();
155 if (ReachableMap.try_emplace(Key: MBB, Args: false).second)
156 append_range(C&: Stack, R: MBB->successors());
157 }
158
159 for (auto &[MBB, Reachable] : ReachableMap) {
160 bool HaveReachablePred = false;
161 for (MachineBasicBlock *Pred : MBB->predecessors()) {
162 if (ReachableMap.count(Key: Pred)) {
163 HaveReachablePred = true;
164 } else {
165 Stack.push_back(Elt: Pred);
166 }
167 }
168 if (!HaveReachablePred)
169 Reachable = true;
170 if (HaveReachablePred) {
171 for (MachineBasicBlock *UnreachablePred : Stack) {
172 if (!llvm::is_contained(Range&: Predecessors, Element: UnreachablePred))
173 Predecessors.push_back(Elt: UnreachablePred);
174 }
175 }
176 Stack.clear();
177 }
178 }
179};
180
181/// Helper class that detects loops which require us to lower an i1 COPY into
182/// bitwise manipulation.
183///
184/// Unfortunately, we cannot use LoopInfo because LoopInfo does not distinguish
185/// between loops with the same header. Consider this example:
186///
187/// A-+-+
188/// | | |
189/// B-+ |
190/// | |
191/// C---+
192///
193/// A is the header of a loop containing A, B, and C as far as LoopInfo is
194/// concerned. However, an i1 COPY in B that is used in C must be lowered to
195/// bitwise operations to combine results from different loop iterations when
196/// B has a divergent branch (since by default we will compile this code such
197/// that threads in a wave are merged at the entry of C).
198///
199/// The following rule is implemented to determine whether bitwise operations
200/// are required: use the bitwise lowering for a def in block B if a backward
201/// edge to B is reachable without going through the nearest common
202/// post-dominator of B and all uses of the def.
203///
204/// TODO: This rule is conservative because it does not check whether the
205/// relevant branches are actually divergent.
206///
207/// The class is designed to cache the CFG traversal so that it can be re-used
208/// for multiple defs within the same basic block.
209///
210/// TODO: We could use region analysis to quickly skip over SESE regions during
211/// the traversal.
212///
213class LoopFinder {
214 MachineDominatorTree &DT;
215 MachinePostDominatorTree &PDT;
216
217 // All visited / reachable block, tagged by level (level 0 is the def block,
218 // level 1 are all blocks reachable including but not going through the def
219 // block's IPDOM, etc.).
220 DenseMap<MachineBasicBlock *, unsigned> Visited;
221
222 // Nearest common dominator of all visited blocks by level (level 0 is the
223 // def block). Used for seeding the SSAUpdater.
224 SmallVector<MachineBasicBlock *, 4> CommonDominators;
225
226 // Post-dominator of all visited blocks.
227 MachineBasicBlock *VisitedPostDom = nullptr;
228
229 // Level at which a loop was found: 0 is not possible; 1 = a backward edge is
230 // reachable without going through the IPDOM of the def block (if the IPDOM
231 // itself has an edge to the def block, the loop level is 2), etc.
232 unsigned FoundLoopLevel = ~0u;
233
234 MachineBasicBlock *DefBlock = nullptr;
235 SmallVector<MachineBasicBlock *, 4> Stack;
236 SmallVector<MachineBasicBlock *, 4> NextLevel;
237
238public:
239 LoopFinder(MachineDominatorTree &DT, MachinePostDominatorTree &PDT)
240 : DT(DT), PDT(PDT) {}
241
242 void initialize(MachineBasicBlock &MBB) {
243 Visited.clear();
244 CommonDominators.clear();
245 Stack.clear();
246 NextLevel.clear();
247 VisitedPostDom = nullptr;
248 FoundLoopLevel = ~0u;
249
250 DefBlock = &MBB;
251 }
252
253 /// Check whether a backward edge can be reached without going through the
254 /// given \p PostDom of the def block.
255 ///
256 /// Return the level of \p PostDom if a loop was found, or 0 otherwise.
257 unsigned findLoop(MachineBasicBlock *PostDom) {
258 MachineDomTreeNode *PDNode = PDT.getNode(BB: DefBlock);
259
260 if (!VisitedPostDom)
261 advanceLevel();
262
263 unsigned Level = 0;
264 while (PDNode->getBlock() != PostDom) {
265 if (PDNode->getBlock() == VisitedPostDom)
266 advanceLevel();
267 PDNode = PDNode->getIDom();
268 Level++;
269 if (FoundLoopLevel == Level)
270 return Level;
271 }
272
273 return 0;
274 }
275
276 /// Add undef values dominating the loop and the optionally given additional
277 /// blocks, so that the SSA updater doesn't have to search all the way to the
278 /// function entry.
279 void addLoopEntries(unsigned LoopLevel, MachineIDFSSAUpdater &SSAUpdater,
280 MachineRegisterInfo &MRI,
281 MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs,
282 ArrayRef<AMDGPU::Incoming> Incomings = {}) {
283 assert(LoopLevel < CommonDominators.size());
284
285 MachineBasicBlock *Dom = CommonDominators[LoopLevel];
286 for (auto &Incoming : Incomings)
287 Dom = DT.findNearestCommonDominator(A: Dom, B: Incoming.Block);
288
289 if (!inLoopLevel(MBB&: *Dom, LoopLevel, Incomings)) {
290 SSAUpdater.addAvailableValue(
291 BB: Dom, V: insertUndefLaneMask(MBB: Dom, MRI: &MRI, LaneMaskRegAttrs));
292 } else {
293 // The dominator is part of the loop or the given blocks, so add the
294 // undef value to unreachable predecessors instead.
295 for (MachineBasicBlock *Pred : Dom->predecessors()) {
296 if (!inLoopLevel(MBB&: *Pred, LoopLevel, Incomings))
297 SSAUpdater.addAvailableValue(
298 BB: Pred, V: insertUndefLaneMask(MBB: Pred, MRI: &MRI, LaneMaskRegAttrs));
299 }
300 }
301 }
302
303private:
304 bool inLoopLevel(MachineBasicBlock &MBB, unsigned LoopLevel,
305 ArrayRef<AMDGPU::Incoming> Incomings) const {
306 auto DomIt = Visited.find(Val: &MBB);
307 if (DomIt != Visited.end() && DomIt->second <= LoopLevel)
308 return true;
309
310 for (auto &Incoming : Incomings)
311 if (Incoming.Block == &MBB)
312 return true;
313
314 return false;
315 }
316
317 void advanceLevel() {
318 MachineBasicBlock *VisitedDom;
319
320 if (!VisitedPostDom) {
321 VisitedPostDom = DefBlock;
322 VisitedDom = DefBlock;
323 Stack.push_back(Elt: DefBlock);
324 } else {
325 VisitedPostDom = PDT.getNode(BB: VisitedPostDom)->getIDom()->getBlock();
326 VisitedDom = CommonDominators.back();
327
328 for (unsigned i = 0; i < NextLevel.size();) {
329 if (PDT.dominates(A: VisitedPostDom, B: NextLevel[i])) {
330 Stack.push_back(Elt: NextLevel[i]);
331
332 NextLevel[i] = NextLevel.back();
333 NextLevel.pop_back();
334 } else {
335 i++;
336 }
337 }
338 }
339
340 unsigned Level = CommonDominators.size();
341 while (!Stack.empty()) {
342 MachineBasicBlock *MBB = Stack.pop_back_val();
343 if (!PDT.dominates(A: VisitedPostDom, B: MBB))
344 NextLevel.push_back(Elt: MBB);
345
346 Visited[MBB] = Level;
347 VisitedDom = DT.findNearestCommonDominator(A: VisitedDom, B: MBB);
348
349 for (MachineBasicBlock *Succ : MBB->successors()) {
350 if (Succ == DefBlock) {
351 if (MBB == VisitedPostDom)
352 FoundLoopLevel = std::min(a: FoundLoopLevel, b: Level + 1);
353 else
354 FoundLoopLevel = std::min(a: FoundLoopLevel, b: Level);
355 continue;
356 }
357
358 if (Visited.try_emplace(Key: Succ, Args: ~0u).second) {
359 if (MBB == VisitedPostDom)
360 NextLevel.push_back(Elt: Succ);
361 else
362 Stack.push_back(Elt: Succ);
363 }
364 }
365 }
366
367 CommonDominators.push_back(Elt: VisitedDom);
368 }
369};
370
371} // End anonymous namespace.
372
373Register llvm::AMDGPU::createLaneMaskReg(
374 MachineRegisterInfo *MRI, MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs) {
375 return MRI->createVirtualRegister(RegAttr: LaneMaskRegAttrs);
376}
377
378static Register
379insertUndefLaneMask(MachineBasicBlock *MBB, MachineRegisterInfo *MRI,
380 MachineRegisterInfo::VRegAttrs LaneMaskRegAttrs) {
381 MachineFunction &MF = *MBB->getParent();
382 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
383 const SIInstrInfo *TII = ST.getInstrInfo();
384 Register UndefReg = AMDGPU::createLaneMaskReg(MRI, LaneMaskRegAttrs);
385 BuildMI(BB&: *MBB, I: MBB->getFirstTerminator(), MIMD: {}, MCID: TII->get(Opcode: AMDGPU::IMPLICIT_DEF),
386 DestReg: UndefReg);
387 return UndefReg;
388}
389
390#ifndef NDEBUG
391static bool isVRegCompatibleReg(const SIRegisterInfo &TRI,
392 const MachineRegisterInfo &MRI,
393 Register Reg) {
394 unsigned Size = TRI.getRegSizeInBits(Reg, MRI);
395 return Size == 1 || Size == 32;
396}
397#endif
398
399bool Vreg1LoweringHelper::lowerCopiesFromI1() {
400 bool Changed = false;
401 SmallVector<MachineInstr *, 4> DeadCopies;
402
403 for (MachineBasicBlock &MBB : *MF) {
404 for (MachineInstr &MI : MBB) {
405 if (MI.getOpcode() != AMDGPU::COPY)
406 continue;
407
408 Register DstReg = MI.getOperand(i: 0).getReg();
409 Register SrcReg = MI.getOperand(i: 1).getReg();
410 if (!isVreg1(Reg: SrcReg))
411 continue;
412
413 if (isLaneMaskReg(Reg: DstReg) || isVreg1(Reg: DstReg))
414 continue;
415
416 Changed = true;
417
418 // Copy into a 32-bit vector register.
419 LLVM_DEBUG(dbgs() << "Lower copy from i1: " << MI);
420 const DebugLoc &DL = MI.getDebugLoc();
421
422 assert(isVRegCompatibleReg(TII->getRegisterInfo(), *MRI, DstReg));
423 assert(!MI.getOperand(0).getSubReg());
424
425 ConstrainRegs.insert(V: SrcReg);
426 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::V_CNDMASK_B32_e64), DestReg: DstReg)
427 .addImm(Val: 0)
428 .addImm(Val: 0)
429 .addImm(Val: 0)
430 .addImm(Val: -1)
431 .addReg(RegNo: SrcReg);
432 DeadCopies.push_back(Elt: &MI);
433 }
434
435 for (MachineInstr *MI : DeadCopies)
436 MI->eraseFromParent();
437 DeadCopies.clear();
438 }
439 return Changed;
440}
441
442AMDGPU::PhiLoweringHelper::PhiLoweringHelper(MachineFunction *MF,
443 MachineDominatorTree *DT,
444 MachinePostDominatorTree *PDT)
445 : MF(MF), DT(DT), PDT(PDT), ST(&MF->getSubtarget<GCNSubtarget>()),
446 LMC(&AMDGPU::LaneMaskConstants::get(ST: *ST)) {
447 MRI = &MF->getRegInfo();
448
449 TII = ST->getInstrInfo();
450}
451
452bool AMDGPU::PhiLoweringHelper::lowerPhis() {
453 LoopFinder LF(*DT, *PDT);
454 PhiIncomingAnalysis PIA(*PDT, TII);
455 SmallVector<MachineInstr *, 4> Vreg1Phis;
456 SmallVector<Incoming, 4> Incomings;
457
458 getCandidatesForLowering(Vreg1Phis);
459 if (Vreg1Phis.empty())
460 return false;
461
462 DT->updateDFSNumbers();
463 MachineBasicBlock *PrevMBB = nullptr;
464 for (MachineInstr *MI : Vreg1Phis) {
465 MachineBasicBlock &MBB = *MI->getParent();
466 if (&MBB != PrevMBB) {
467 LF.initialize(MBB);
468 PrevMBB = &MBB;
469 }
470
471 LLVM_DEBUG(dbgs() << "Lower PHI: " << *MI);
472
473 Register DstReg = MI->getOperand(i: 0).getReg();
474 markAsLaneMask(DstReg);
475 initializeLaneMaskRegisterAttributes(LaneMask: DstReg);
476
477 collectIncomingValuesFromPhi(MI, Incomings);
478
479 // Sort the incomings such that incoming values that dominate other incoming
480 // values are sorted earlier. This allows us to do some amount of on-the-fly
481 // constant folding.
482 // Incoming with smaller DFSNumIn goes first, DFSNumIn is 0 for entry block.
483 llvm::sort(C&: Incomings, Comp: [this](Incoming LHS, Incoming RHS) {
484 return DT->getNode(BB: LHS.Block)->getDFSNumIn() <
485 DT->getNode(BB: RHS.Block)->getDFSNumIn();
486 });
487
488#ifndef NDEBUG
489 PhiRegisters.insert(DstReg);
490#endif
491
492 // Phis in a loop that are observed outside the loop receive a simple but
493 // conservatively correct treatment.
494 std::vector<MachineBasicBlock *> DomBlocks = {&MBB};
495 for (MachineInstr &Use : MRI->use_instructions(Reg: DstReg))
496 DomBlocks.push_back(x: Use.getParent());
497
498 MachineBasicBlock *PostDomBound =
499 PDT->findNearestCommonDominator(Blocks: DomBlocks);
500
501 // FIXME: This fails to find irreducible cycles. If we have a def (other
502 // than a constant) in a pair of blocks that end up looping back to each
503 // other, it will be mishandle. Due to structurization this shouldn't occur
504 // in practice.
505 unsigned FoundLoopLevel = LF.findLoop(PostDom: PostDomBound);
506
507 MachineIDFSSAUpdater SSAUpdater(*DT, *MF, DstReg);
508 SSAUpdater.addUseBlock(BB: &MBB);
509
510 if (FoundLoopLevel) {
511 LF.addLoopEntries(LoopLevel: FoundLoopLevel, SSAUpdater, MRI&: *MRI, LaneMaskRegAttrs,
512 Incomings);
513
514 for (auto &Incoming : Incomings) {
515 SSAUpdater.addUseBlock(BB: Incoming.Block);
516 Incoming.UpdatedReg = createLaneMaskReg(MRI, LaneMaskRegAttrs);
517 SSAUpdater.addAvailableValue(BB: Incoming.Block, V: Incoming.UpdatedReg);
518 }
519
520 SSAUpdater.calculate();
521
522 for (auto &Incoming : Incomings) {
523 MachineBasicBlock &IMBB = *Incoming.Block;
524 buildMergeLaneMasks(
525 MBB&: IMBB, I: getSaluInsertionAtEnd(MBB&: IMBB), DL: {}, DstReg: Incoming.UpdatedReg,
526 PrevReg: SSAUpdater.getValueInMiddleOfBlock(BB: &IMBB), CurReg: Incoming.Reg);
527 }
528 } else {
529 // The phi is not observed from outside a loop. Use a more accurate
530 // lowering.
531 PIA.analyze(DefBlock&: MBB, Incomings);
532
533 for (MachineBasicBlock *MBB : PIA.predecessors())
534 SSAUpdater.addAvailableValue(
535 BB: MBB, V: insertUndefLaneMask(MBB, MRI, LaneMaskRegAttrs));
536
537 for (auto &Incoming : Incomings) {
538 MachineBasicBlock &IMBB = *Incoming.Block;
539 if (PIA.isSource(MBB&: IMBB)) {
540 constrainAsLaneMask(In&: Incoming);
541 SSAUpdater.addAvailableValue(BB: &IMBB, V: Incoming.Reg);
542 } else {
543 SSAUpdater.addUseBlock(BB: &IMBB);
544 Incoming.UpdatedReg = createLaneMaskReg(MRI, LaneMaskRegAttrs);
545 SSAUpdater.addAvailableValue(BB: &IMBB, V: Incoming.UpdatedReg);
546 }
547 }
548
549 SSAUpdater.calculate();
550
551 for (auto &Incoming : Incomings) {
552 if (!Incoming.UpdatedReg.isValid())
553 continue;
554
555 MachineBasicBlock &IMBB = *Incoming.Block;
556 buildMergeLaneMasks(
557 MBB&: IMBB, I: getSaluInsertionAtEnd(MBB&: IMBB), DL: {}, DstReg: Incoming.UpdatedReg,
558 PrevReg: SSAUpdater.getValueInMiddleOfBlock(BB: &IMBB), CurReg: Incoming.Reg);
559 }
560 }
561
562 Register NewReg = SSAUpdater.getValueInMiddleOfBlock(BB: &MBB);
563 if (NewReg != DstReg) {
564 replaceDstReg(NewReg, OldReg: DstReg, MBB: &MBB);
565 MI->eraseFromParent();
566 }
567
568 Incomings.clear();
569 }
570 return true;
571}
572
573bool Vreg1LoweringHelper::lowerCopiesToI1() {
574 bool Changed = false;
575 LoopFinder LF(*DT, *PDT);
576 SmallVector<MachineInstr *, 4> DeadCopies;
577
578 for (MachineBasicBlock &MBB : *MF) {
579 LF.initialize(MBB);
580
581 for (MachineInstr &MI : MBB) {
582 if (MI.getOpcode() != AMDGPU::IMPLICIT_DEF &&
583 MI.getOpcode() != AMDGPU::COPY)
584 continue;
585
586 Register DstReg = MI.getOperand(i: 0).getReg();
587 if (!isVreg1(Reg: DstReg))
588 continue;
589
590 Changed = true;
591
592 if (MRI->use_empty(RegNo: DstReg)) {
593 DeadCopies.push_back(Elt: &MI);
594 continue;
595 }
596
597 LLVM_DEBUG(dbgs() << "Lower Other: " << MI);
598
599 markAsLaneMask(DstReg);
600 initializeLaneMaskRegisterAttributes(LaneMask: DstReg);
601
602 if (MI.getOpcode() == AMDGPU::IMPLICIT_DEF)
603 continue;
604
605 const DebugLoc &DL = MI.getDebugLoc();
606 Register SrcReg = MI.getOperand(i: 1).getReg();
607 assert(!MI.getOperand(1).getSubReg());
608
609 if (!SrcReg.isVirtual() || (!isLaneMaskReg(Reg: SrcReg) && !isVreg1(Reg: SrcReg))) {
610 assert(TII->getRegisterInfo().getRegSizeInBits(SrcReg, *MRI) == 32);
611 Register TmpReg = AMDGPU::createLaneMaskReg(MRI, LaneMaskRegAttrs);
612 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::V_CMP_NE_U32_e64), DestReg: TmpReg)
613 .addReg(RegNo: SrcReg)
614 .addImm(Val: 0);
615 MI.getOperand(i: 1).setReg(TmpReg);
616 SrcReg = TmpReg;
617 } else {
618 // SrcReg needs to be live beyond copy.
619 MI.getOperand(i: 1).setIsKill(false);
620 }
621
622 // Defs in a loop that are observed outside the loop must be transformed
623 // into appropriate bit manipulation.
624 std::vector<MachineBasicBlock *> DomBlocks = {&MBB};
625 for (MachineInstr &Use : MRI->use_instructions(Reg: DstReg))
626 DomBlocks.push_back(x: Use.getParent());
627
628 MachineBasicBlock *PostDomBound =
629 PDT->findNearestCommonDominator(Blocks: DomBlocks);
630 unsigned FoundLoopLevel = LF.findLoop(PostDom: PostDomBound);
631 if (FoundLoopLevel) {
632 MachineIDFSSAUpdater SSAUpdater(*DT, *MF, DstReg);
633 SSAUpdater.addUseBlock(BB: &MBB);
634 SSAUpdater.addAvailableValue(BB: &MBB, V: DstReg);
635 LF.addLoopEntries(LoopLevel: FoundLoopLevel, SSAUpdater, MRI&: *MRI, LaneMaskRegAttrs);
636
637 SSAUpdater.calculate();
638 buildMergeLaneMasks(MBB, I: MI, DL, DstReg,
639 PrevReg: SSAUpdater.getValueInMiddleOfBlock(BB: &MBB), CurReg: SrcReg);
640 DeadCopies.push_back(Elt: &MI);
641 }
642 }
643
644 for (MachineInstr *MI : DeadCopies)
645 MI->eraseFromParent();
646 DeadCopies.clear();
647 }
648 return Changed;
649}
650
651bool AMDGPU::PhiLoweringHelper::isConstantLaneMask(Register Reg,
652 bool &Val) const {
653 const MachineInstr *MI;
654 for (;;) {
655 MI = MRI->getUniqueVRegDef(Reg);
656 if (MI->getOpcode() == AMDGPU::IMPLICIT_DEF)
657 return true;
658
659 if (MI->getOpcode() != AMDGPU::COPY)
660 break;
661
662 Reg = MI->getOperand(i: 1).getReg();
663 if (!Reg.isVirtual())
664 return false;
665 if (!isLaneMaskReg(Reg))
666 return false;
667 }
668
669 if (MI->getOpcode() != LMC->MovOpc)
670 return false;
671
672 if (!MI->getOperand(i: 1).isImm())
673 return false;
674
675 int64_t Imm = MI->getOperand(i: 1).getImm();
676 if (Imm == 0) {
677 Val = false;
678 return true;
679 }
680 if (Imm == -1) {
681 Val = true;
682 return true;
683 }
684
685 return false;
686}
687
688static void instrDefsUsesSCC(const MachineInstr &MI, bool &Def, bool &Use) {
689 Def = false;
690 Use = false;
691
692 for (const MachineOperand &MO : MI.operands()) {
693 if (MO.isReg() && MO.getReg() == AMDGPU::SCC) {
694 if (MO.isUse())
695 Use = true;
696 else
697 Def = true;
698 }
699 }
700}
701
702/// Return a point at the end of the given \p MBB to insert SALU instructions
703/// for lane mask calculation. Take terminators and SCC into account.
704MachineBasicBlock::iterator
705AMDGPU::PhiLoweringHelper::getSaluInsertionAtEnd(MachineBasicBlock &MBB) const {
706 auto InsertionPt = MBB.getFirstTerminator();
707 bool TerminatorsUseSCC = false;
708 for (auto I = InsertionPt, E = MBB.end(); I != E; ++I) {
709 bool DefsSCC;
710 instrDefsUsesSCC(MI: *I, Def&: DefsSCC, Use&: TerminatorsUseSCC);
711 if (TerminatorsUseSCC || DefsSCC)
712 break;
713 }
714
715 if (!TerminatorsUseSCC)
716 return InsertionPt;
717
718 while (InsertionPt != MBB.begin()) {
719 InsertionPt--;
720
721 bool DefSCC, UseSCC;
722 instrDefsUsesSCC(MI: *InsertionPt, Def&: DefSCC, Use&: UseSCC);
723 if (DefSCC)
724 return InsertionPt;
725 }
726
727 // We should have at least seen an IMPLICIT_DEF or COPY
728 llvm_unreachable("SCC used by terminator but no def in block");
729}
730
731// VReg_1 -> SReg_32 or SReg_64
732void Vreg1LoweringHelper::markAsLaneMask(Register DstReg) const {
733 MRI->setRegClass(Reg: DstReg, RC: ST->getBoolRC());
734}
735
736void Vreg1LoweringHelper::getCandidatesForLowering(
737 SmallVectorImpl<MachineInstr *> &Vreg1Phis) const {
738 for (MachineBasicBlock &MBB : *MF) {
739 for (MachineInstr &MI : MBB.phis()) {
740 if (isVreg1(Reg: MI.getOperand(i: 0).getReg()))
741 Vreg1Phis.push_back(Elt: &MI);
742 }
743 }
744}
745
746void Vreg1LoweringHelper::collectIncomingValuesFromPhi(
747 const MachineInstr *MI,
748 SmallVectorImpl<AMDGPU::Incoming> &Incomings) const {
749 for (unsigned i = 1; i < MI->getNumOperands(); i += 2) {
750 assert(i + 1 < MI->getNumOperands());
751 Register IncomingReg = MI->getOperand(i).getReg();
752 MachineBasicBlock *IncomingMBB = MI->getOperand(i: i + 1).getMBB();
753 MachineInstr *IncomingDef = MRI->getUniqueVRegDef(Reg: IncomingReg);
754
755 if (IncomingDef->getOpcode() == AMDGPU::COPY) {
756 IncomingReg = IncomingDef->getOperand(i: 1).getReg();
757 assert(isLaneMaskReg(IncomingReg) || isVreg1(IncomingReg));
758 assert(!IncomingDef->getOperand(1).getSubReg());
759 } else if (IncomingDef->getOpcode() == AMDGPU::IMPLICIT_DEF) {
760 continue;
761 } else {
762 assert(IncomingDef->isPHI() || PhiRegisters.count(IncomingReg));
763 }
764
765 Incomings.emplace_back(Args&: IncomingReg, Args&: IncomingMBB, Args: Register());
766 }
767}
768
769void Vreg1LoweringHelper::replaceDstReg(Register NewReg, Register OldReg,
770 MachineBasicBlock *MBB) {
771 MRI->replaceRegWith(FromReg: NewReg, ToReg: OldReg);
772}
773
774void Vreg1LoweringHelper::buildMergeLaneMasks(MachineBasicBlock &MBB,
775 MachineBasicBlock::iterator I,
776 const DebugLoc &DL,
777 Register DstReg, Register PrevReg,
778 Register CurReg) {
779 bool PrevVal = false;
780 bool PrevConstant = isConstantLaneMask(Reg: PrevReg, Val&: PrevVal);
781 bool CurVal = false;
782 bool CurConstant = isConstantLaneMask(Reg: CurReg, Val&: CurVal);
783
784 if (PrevConstant && CurConstant) {
785 if (PrevVal == CurVal) {
786 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::COPY), DestReg: DstReg).addReg(RegNo: CurReg);
787 } else if (CurVal) {
788 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::COPY), DestReg: DstReg).addReg(RegNo: LMC->ExecReg);
789 } else {
790 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC->XorOpc), DestReg: DstReg)
791 .addReg(RegNo: LMC->ExecReg)
792 .addImm(Val: -1);
793 }
794 return;
795 }
796
797 Register PrevMaskedReg;
798 Register CurMaskedReg;
799 if (!PrevConstant) {
800 if (CurConstant && CurVal) {
801 PrevMaskedReg = PrevReg;
802 } else {
803 PrevMaskedReg = AMDGPU::createLaneMaskReg(MRI, LaneMaskRegAttrs);
804 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC->AndN2Opc), DestReg: PrevMaskedReg)
805 .addReg(RegNo: PrevReg)
806 .addReg(RegNo: LMC->ExecReg);
807 }
808 }
809 if (!CurConstant) {
810 // TODO: check whether CurReg is already masked by EXEC
811 if (PrevConstant && PrevVal) {
812 CurMaskedReg = CurReg;
813 } else {
814 CurMaskedReg = AMDGPU::createLaneMaskReg(MRI, LaneMaskRegAttrs);
815 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC->AndOpc), DestReg: CurMaskedReg)
816 .addReg(RegNo: CurReg)
817 .addReg(RegNo: LMC->ExecReg);
818 }
819 }
820
821 if (PrevConstant && !PrevVal) {
822 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::COPY), DestReg: DstReg)
823 .addReg(RegNo: CurMaskedReg);
824 } else if (CurConstant && !CurVal) {
825 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::COPY), DestReg: DstReg)
826 .addReg(RegNo: PrevMaskedReg);
827 } else if (PrevConstant && PrevVal) {
828 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC->OrN2Opc), DestReg: DstReg)
829 .addReg(RegNo: CurMaskedReg)
830 .addReg(RegNo: LMC->ExecReg);
831 } else {
832 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC->OrOpc), DestReg: DstReg)
833 .addReg(RegNo: PrevMaskedReg)
834 .addReg(RegNo: CurMaskedReg ? CurMaskedReg : LMC->ExecReg);
835 }
836}
837
838void Vreg1LoweringHelper::constrainAsLaneMask(AMDGPU::Incoming &In) {}
839
840/// Lower all instructions that def or use vreg_1 registers.
841///
842/// In a first pass, we lower COPYs from vreg_1 to vector registers, as can
843/// occur around inline assembly. We do this first, before vreg_1 registers
844/// are changed to scalar mask registers.
845///
846/// Then we lower all defs of vreg_1 registers. Phi nodes are lowered before
847/// all others, because phi lowering looks through copies and can therefore
848/// often make copy lowering unnecessary.
849static bool runFixI1Copies(MachineFunction &MF, MachineDominatorTree &MDT,
850 MachinePostDominatorTree &MPDT) {
851 // Only need to run this in SelectionDAG path.
852 if (MF.getProperties().hasSelected())
853 return false;
854
855 Vreg1LoweringHelper Helper(&MF, &MDT, &MPDT);
856 bool Changed = false;
857 Changed |= Helper.lowerCopiesFromI1();
858 Changed |= Helper.lowerPhis();
859 Changed |= Helper.lowerCopiesToI1();
860 return Helper.cleanConstrainRegs(Changed);
861}
862
863PreservedAnalyses
864SILowerI1CopiesPass::run(MachineFunction &MF,
865 MachineFunctionAnalysisManager &MFAM) {
866 MachineDominatorTree &MDT = MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
867 MachinePostDominatorTree &MPDT =
868 MFAM.getResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
869 bool Changed = runFixI1Copies(MF, MDT, MPDT);
870 if (!Changed)
871 return PreservedAnalyses::all();
872
873 // TODO: Probably preserves most.
874 return getMachineFunctionPassPreservedAnalyses().preserveSet<CFGAnalyses>();
875}
876
877class SILowerI1CopiesLegacy : public MachineFunctionPass {
878public:
879 static char ID;
880
881 SILowerI1CopiesLegacy() : MachineFunctionPass(ID) {}
882
883 bool runOnMachineFunction(MachineFunction &MF) override;
884
885 StringRef getPassName() const override { return "SI Lower i1 Copies"; }
886
887 void getAnalysisUsage(AnalysisUsage &AU) const override {
888 AU.setPreservesCFG();
889 AU.addRequired<MachineDominatorTreeWrapperPass>();
890 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
891 MachineFunctionPass::getAnalysisUsage(AU);
892 }
893};
894
895bool SILowerI1CopiesLegacy::runOnMachineFunction(MachineFunction &MF) {
896 MachineDominatorTree &MDT =
897 getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
898 MachinePostDominatorTree &MPDT =
899 getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
900 return runFixI1Copies(MF, MDT, MPDT);
901}
902
903INITIALIZE_PASS_BEGIN(SILowerI1CopiesLegacy, DEBUG_TYPE, "SI Lower i1 Copies",
904 false, false)
905INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
906INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
907INITIALIZE_PASS_END(SILowerI1CopiesLegacy, DEBUG_TYPE, "SI Lower i1 Copies",
908 false, false)
909
910char SILowerI1CopiesLegacy::ID = 0;
911
912char &llvm::SILowerI1CopiesLegacyID = SILowerI1CopiesLegacy::ID;
913
914FunctionPass *llvm::createSILowerI1CopiesLegacyPass() {
915 return new SILowerI1CopiesLegacy();
916}
917