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 if (NewReg != DstReg) {
577 replaceDstReg(NewReg, OldReg: DstReg, MBB: &MBB);
578 MI->eraseFromParent();
579 }
580
581 Incomings.clear();
582 }
583 return true;
584}
585
586bool Vreg1LoweringHelper::lowerCopiesToI1() {
587 bool Changed = false;
588 AMDGPU::LoopFinder LF(DT, PDT);
589 SmallVector<MachineInstr *, 4> DeadCopies;
590
591 for (MachineBasicBlock &MBB : MF) {
592 LF.initialize(MBB);
593
594 for (MachineInstr &MI : MBB) {
595 if (MI.getOpcode() != AMDGPU::IMPLICIT_DEF &&
596 MI.getOpcode() != AMDGPU::COPY)
597 continue;
598
599 Register DstReg = MI.getOperand(i: 0).getReg();
600 if (!isVreg1(Reg: DstReg))
601 continue;
602
603 Changed = true;
604
605 if (MRI->use_empty(RegNo: DstReg)) {
606 DeadCopies.push_back(Elt: &MI);
607 continue;
608 }
609
610 LLVM_DEBUG(dbgs() << "Lower Other: " << MI);
611
612 markAsLaneMask(DstReg);
613 initializeLaneMaskRegisterAttributes(LaneMask: DstReg);
614
615 if (MI.getOpcode() == AMDGPU::IMPLICIT_DEF)
616 continue;
617
618 const DebugLoc &DL = MI.getDebugLoc();
619 Register SrcReg = MI.getOperand(i: 1).getReg();
620 assert(!MI.getOperand(1).getSubReg());
621
622 if (!SrcReg.isVirtual() || (!isLaneMaskReg(Reg: SrcReg) && !isVreg1(Reg: SrcReg))) {
623 assert(TII->getRegisterInfo().getRegSizeInBits(SrcReg, *MRI) == 32);
624 Register TmpReg = AMDGPU::createLaneMaskReg(MRI, LaneMaskRegAttrs);
625 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::V_CMP_NE_U32_e64), DestReg: TmpReg)
626 .addReg(RegNo: SrcReg)
627 .addImm(Val: 0);
628 MI.getOperand(i: 1).setReg(TmpReg);
629 SrcReg = TmpReg;
630 } else {
631 // SrcReg needs to be live beyond copy.
632 MI.getOperand(i: 1).setIsKill(false);
633 }
634
635 // Defs in a loop that are observed outside the loop must be transformed
636 // into appropriate bit manipulation.
637 std::vector<MachineBasicBlock *> DomBlocks = {&MBB};
638 for (MachineInstr &Use : MRI->use_instructions(Reg: DstReg))
639 DomBlocks.push_back(x: Use.getParent());
640
641 MachineBasicBlock *PostDomBound =
642 PDT.findNearestCommonDominator(Blocks: DomBlocks);
643 unsigned FoundLoopLevel = LF.findLoop(PostDom: PostDomBound);
644 if (FoundLoopLevel) {
645 MachineIDFSSAUpdater SSAUpdater(DT, MF, DstReg);
646 SSAUpdater.addUseBlock(BB: &MBB);
647 SSAUpdater.addAvailableValue(BB: &MBB, V: DstReg);
648 LF.addLoopEntries(LoopLevel: FoundLoopLevel, SSAUpdater, MRI&: *MRI, LaneMaskRegAttrs);
649
650 SSAUpdater.calculate();
651 buildMergeLaneMasks(MBB, I: MI, DL, DstReg,
652 PrevReg: SSAUpdater.getValueInMiddleOfBlock(BB: &MBB), CurReg: SrcReg);
653 DeadCopies.push_back(Elt: &MI);
654 }
655 }
656
657 for (MachineInstr *MI : DeadCopies)
658 MI->eraseFromParent();
659 DeadCopies.clear();
660 }
661 return Changed;
662}
663
664bool AMDGPU::PhiLoweringHelper::isConstantLaneMask(Register Reg,
665 bool &Val) const {
666 const MachineInstr *MI;
667 for (;;) {
668 MI = MRI->getUniqueVRegDef(Reg);
669 if (MI->getOpcode() == AMDGPU::IMPLICIT_DEF)
670 return true;
671
672 if (MI->getOpcode() != AMDGPU::COPY)
673 break;
674
675 Reg = MI->getOperand(i: 1).getReg();
676 if (!Reg.isVirtual())
677 return false;
678 if (!isLaneMaskReg(Reg))
679 return false;
680 }
681
682 if (MI->getOpcode() != LMC->MovOpc)
683 return false;
684
685 if (!MI->getOperand(i: 1).isImm())
686 return false;
687
688 int64_t Imm = MI->getOperand(i: 1).getImm();
689 if (Imm == 0) {
690 Val = false;
691 return true;
692 }
693 if (Imm == -1) {
694 Val = true;
695 return true;
696 }
697
698 return false;
699}
700
701static void instrDefsUsesSCC(const MachineInstr &MI, bool &Def, bool &Use) {
702 Def = false;
703 Use = false;
704
705 for (const MachineOperand &MO : MI.operands()) {
706 if (MO.isReg() && MO.getReg() == AMDGPU::SCC) {
707 if (MO.isUse())
708 Use = true;
709 else
710 Def = true;
711 }
712 }
713}
714
715/// Return a point at the end of the given \p MBB to insert SALU instructions
716/// for lane mask calculation. Take terminators and SCC into account.
717MachineBasicBlock::iterator
718AMDGPU::PhiLoweringHelper::getSaluInsertionAtEnd(MachineBasicBlock &MBB) const {
719 auto InsertionPt = MBB.getFirstTerminator();
720 bool TerminatorsUseSCC = false;
721 for (auto I = InsertionPt, E = MBB.end(); I != E; ++I) {
722 bool DefsSCC;
723 instrDefsUsesSCC(MI: *I, Def&: DefsSCC, Use&: TerminatorsUseSCC);
724 if (TerminatorsUseSCC || DefsSCC)
725 break;
726 }
727
728 if (!TerminatorsUseSCC)
729 return InsertionPt;
730
731 while (InsertionPt != MBB.begin()) {
732 InsertionPt--;
733
734 bool DefSCC, UseSCC;
735 instrDefsUsesSCC(MI: *InsertionPt, Def&: DefSCC, Use&: UseSCC);
736 if (DefSCC)
737 return InsertionPt;
738 }
739
740 // We should have at least seen an IMPLICIT_DEF or COPY
741 llvm_unreachable("SCC used by terminator but no def in block");
742}
743
744// VReg_1 -> SReg_32 or SReg_64
745void Vreg1LoweringHelper::markAsLaneMask(Register DstReg) const {
746 MRI->setRegClass(Reg: DstReg, RC: ST->getBoolRC());
747}
748
749void Vreg1LoweringHelper::getCandidatesForLowering(
750 SmallVectorImpl<MachineInstr *> &Vreg1Phis) const {
751 for (MachineBasicBlock &MBB : MF) {
752 for (MachineInstr &MI : MBB.phis()) {
753 if (isVreg1(Reg: MI.getOperand(i: 0).getReg()))
754 Vreg1Phis.push_back(Elt: &MI);
755 }
756 }
757}
758
759void Vreg1LoweringHelper::collectIncomingValuesFromPhi(
760 const MachineInstr *MI,
761 SmallVectorImpl<AMDGPU::Incoming> &Incomings) const {
762 for (unsigned i = 1; i < MI->getNumOperands(); i += 2) {
763 assert(i + 1 < MI->getNumOperands());
764 Register IncomingReg = MI->getOperand(i).getReg();
765 MachineBasicBlock *IncomingMBB = MI->getOperand(i: i + 1).getMBB();
766 MachineInstr *IncomingDef = MRI->getUniqueVRegDef(Reg: IncomingReg);
767
768 if (IncomingDef->getOpcode() == AMDGPU::COPY) {
769 IncomingReg = IncomingDef->getOperand(i: 1).getReg();
770 assert(isLaneMaskReg(IncomingReg) || isVreg1(IncomingReg));
771 assert(!IncomingDef->getOperand(1).getSubReg());
772 } else if (IncomingDef->getOpcode() == AMDGPU::IMPLICIT_DEF) {
773 continue;
774 } else {
775 assert(IncomingDef->isPHI() || PhiRegisters.count(IncomingReg));
776 }
777
778 Incomings.emplace_back(Args&: IncomingReg, Args&: IncomingMBB, Args: Register());
779 }
780}
781
782void Vreg1LoweringHelper::replaceDstReg(Register NewReg, Register OldReg,
783 MachineBasicBlock *MBB) {
784 MRI->replaceRegWith(FromReg: NewReg, ToReg: OldReg);
785}
786
787void Vreg1LoweringHelper::buildMergeLaneMasks(MachineBasicBlock &MBB,
788 MachineBasicBlock::iterator I,
789 const DebugLoc &DL,
790 Register DstReg, Register PrevReg,
791 Register CurReg) {
792 bool PrevVal = false;
793 bool PrevConstant = isConstantLaneMask(Reg: PrevReg, Val&: PrevVal);
794 bool CurVal = false;
795 bool CurConstant = isConstantLaneMask(Reg: CurReg, Val&: CurVal);
796
797 if (PrevConstant && CurConstant) {
798 if (PrevVal == CurVal) {
799 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::COPY), DestReg: DstReg).addReg(RegNo: CurReg);
800 } else if (CurVal) {
801 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::COPY), DestReg: DstReg).addReg(RegNo: LMC->ExecReg);
802 } else {
803 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC->XorOpc), DestReg: DstReg)
804 .addReg(RegNo: LMC->ExecReg)
805 .addImm(Val: -1);
806 }
807 return;
808 }
809
810 Register PrevMaskedReg;
811 Register CurMaskedReg;
812 if (!PrevConstant) {
813 if (CurConstant && CurVal) {
814 PrevMaskedReg = PrevReg;
815 } else {
816 PrevMaskedReg = AMDGPU::createLaneMaskReg(MRI, LaneMaskRegAttrs);
817 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC->AndN2Opc), DestReg: PrevMaskedReg)
818 .addReg(RegNo: PrevReg)
819 .addReg(RegNo: LMC->ExecReg);
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 }
832 }
833
834 if (PrevConstant && !PrevVal) {
835 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::COPY), DestReg: DstReg)
836 .addReg(RegNo: CurMaskedReg);
837 } else if (CurConstant && !CurVal) {
838 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: AMDGPU::COPY), DestReg: DstReg)
839 .addReg(RegNo: PrevMaskedReg);
840 } else if (PrevConstant && PrevVal) {
841 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC->OrN2Opc), DestReg: DstReg)
842 .addReg(RegNo: CurMaskedReg)
843 .addReg(RegNo: LMC->ExecReg);
844 } else {
845 BuildMI(BB&: MBB, I, MIMD: DL, MCID: TII->get(Opcode: LMC->OrOpc), DestReg: DstReg)
846 .addReg(RegNo: PrevMaskedReg)
847 .addReg(RegNo: CurMaskedReg ? CurMaskedReg : LMC->ExecReg);
848 }
849}
850
851void Vreg1LoweringHelper::constrainAsLaneMask(AMDGPU::Incoming &In) {}
852
853/// Lower all instructions that def or use vreg_1 registers.
854///
855/// In a first pass, we lower COPYs from vreg_1 to vector registers, as can
856/// occur around inline assembly. We do this first, before vreg_1 registers
857/// are changed to scalar mask registers.
858///
859/// Then we lower all defs of vreg_1 registers. Phi nodes are lowered before
860/// all others, because phi lowering looks through copies and can therefore
861/// often make copy lowering unnecessary.
862static bool runFixI1Copies(MachineFunction &MF, MachineDominatorTree &MDT,
863 MachinePostDominatorTree &MPDT) {
864 // Only need to run this in SelectionDAG path.
865 if (MF.getProperties().hasSelected())
866 return false;
867
868 Vreg1LoweringHelper Helper(MF, MDT, MPDT);
869 bool Changed = false;
870 Changed |= Helper.lowerCopiesFromI1();
871 Changed |= Helper.lowerPhis();
872 Changed |= Helper.lowerCopiesToI1();
873 return Helper.cleanConstrainRegs(Changed);
874}
875
876PreservedAnalyses
877SILowerI1CopiesPass::run(MachineFunction &MF,
878 MachineFunctionAnalysisManager &MFAM) {
879 MachineDominatorTree &MDT = MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
880 MachinePostDominatorTree &MPDT =
881 MFAM.getResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
882 bool Changed = runFixI1Copies(MF, MDT, MPDT);
883 if (!Changed)
884 return PreservedAnalyses::all();
885
886 // TODO: Probably preserves most.
887 return getMachineFunctionPassPreservedAnalyses().preserveSet<CFGAnalyses>();
888}
889
890class SILowerI1CopiesLegacy : public MachineFunctionPass {
891public:
892 static char ID;
893
894 SILowerI1CopiesLegacy() : MachineFunctionPass(ID) {}
895
896 bool runOnMachineFunction(MachineFunction &MF) override;
897
898 StringRef getPassName() const override { return "SI Lower i1 Copies"; }
899
900 void getAnalysisUsage(AnalysisUsage &AU) const override {
901 AU.setPreservesCFG();
902 AU.addRequired<MachineDominatorTreeWrapperPass>();
903 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
904 MachineFunctionPass::getAnalysisUsage(AU);
905 }
906};
907
908bool SILowerI1CopiesLegacy::runOnMachineFunction(MachineFunction &MF) {
909 MachineDominatorTree &MDT =
910 getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
911 MachinePostDominatorTree &MPDT =
912 getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
913 return runFixI1Copies(MF, MDT, MPDT);
914}
915
916INITIALIZE_PASS_BEGIN(SILowerI1CopiesLegacy, DEBUG_TYPE, "SI Lower i1 Copies",
917 false, false)
918INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
919INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
920INITIALIZE_PASS_END(SILowerI1CopiesLegacy, DEBUG_TYPE, "SI Lower i1 Copies",
921 false, false)
922
923char SILowerI1CopiesLegacy::ID = 0;
924
925char &llvm::SILowerI1CopiesLegacyID = SILowerI1CopiesLegacy::ID;
926
927FunctionPass *llvm::createSILowerI1CopiesLegacyPass() {
928 return new SILowerI1CopiesLegacy();
929}
930