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