LLVM  9.0.0svn
SILowerI1Copies.cpp
Go to the documentation of this file.
1 //===-- SILowerI1Copies.cpp - Lower I1 Copies -----------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass lowers all occurrences of i1 values (with a vreg_1 register class)
10 // to lane masks (32 / 64-bit scalar registers). The pass assumes machine SSA
11 // form and a wave-level control flow graph.
12 //
13 // Before this pass, values that are semantically i1 and are defined and used
14 // within the same basic block are already represented as lane masks in scalar
15 // registers. However, values that cross basic blocks are always transferred
16 // between basic blocks in vreg_1 virtual registers and are lowered by this
17 // pass.
18 //
19 // The only instructions that use or define vreg_1 virtual registers are COPY,
20 // PHI, and IMPLICIT_DEF.
21 //
22 //===----------------------------------------------------------------------===//
23 
24 #include "AMDGPU.h"
25 #include "AMDGPUSubtarget.h"
27 #include "SIInstrInfo.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/IR/LLVMContext.h"
36 #include "llvm/Support/Debug.h"
38 
39 #define DEBUG_TYPE "si-i1-copies"
40 
41 using namespace llvm;
42 
43 static unsigned createLaneMaskReg(MachineFunction &MF);
44 static unsigned insertUndefLaneMask(MachineBasicBlock &MBB);
45 
46 namespace {
47 
48 class SILowerI1Copies : public MachineFunctionPass {
49 public:
50  static char ID;
51 
52 private:
53  bool IsWave32 = false;
54  MachineFunction *MF = nullptr;
55  MachineDominatorTree *DT = nullptr;
56  MachinePostDominatorTree *PDT = nullptr;
57  MachineRegisterInfo *MRI = nullptr;
58  const GCNSubtarget *ST = nullptr;
59  const SIInstrInfo *TII = nullptr;
60 
61  unsigned ExecReg;
62  unsigned MovOp;
63  unsigned AndOp;
64  unsigned OrOp;
65  unsigned XorOp;
66  unsigned AndN2Op;
67  unsigned OrN2Op;
68 
69  DenseSet<unsigned> ConstrainRegs;
70 
71 public:
72  SILowerI1Copies() : MachineFunctionPass(ID) {
74  }
75 
76  bool runOnMachineFunction(MachineFunction &MF) override;
77 
78  StringRef getPassName() const override { return "SI Lower i1 Copies"; }
79 
80  void getAnalysisUsage(AnalysisUsage &AU) const override {
81  AU.setPreservesCFG();
85  }
86 
87 private:
88  void lowerCopiesFromI1();
89  void lowerPhis();
90  void lowerCopiesToI1();
91  bool isConstantLaneMask(unsigned Reg, bool &Val) const;
92  void buildMergeLaneMasks(MachineBasicBlock &MBB,
94  unsigned DstReg, unsigned PrevReg, unsigned CurReg);
96  getSaluInsertionAtEnd(MachineBasicBlock &MBB) const;
97 
98  bool isLaneMaskReg(unsigned Reg) const {
99  return TII->getRegisterInfo().isSGPRReg(*MRI, Reg) &&
100  TII->getRegisterInfo().getRegSizeInBits(Reg, *MRI) ==
101  ST->getWavefrontSize();
102  }
103 };
104 
105 /// Helper class that determines the relationship between incoming values of a
106 /// phi in the control flow graph to determine where an incoming value can
107 /// simply be taken as a scalar lane mask as-is, and where it needs to be
108 /// merged with another, previously defined lane mask.
109 ///
110 /// The approach is as follows:
111 /// - Determine all basic blocks which, starting from the incoming blocks,
112 /// a wave may reach before entering the def block (the block containing the
113 /// phi).
114 /// - If an incoming block has no predecessors in this set, we can take the
115 /// incoming value as a scalar lane mask as-is.
116 /// -- A special case of this is when the def block has a self-loop.
117 /// - Otherwise, the incoming value needs to be merged with a previously
118 /// defined lane mask.
119 /// - If there is a path into the set of reachable blocks that does _not_ go
120 /// through an incoming block where we can take the scalar lane mask as-is,
121 /// we need to invent an available value for the SSAUpdater. Choices are
122 /// 0 and undef, with differing consequences for how to merge values etc.
123 ///
124 /// TODO: We could use region analysis to quickly skip over SESE regions during
125 /// the traversal.
126 ///
127 class PhiIncomingAnalysis {
129 
130  // For each reachable basic block, whether it is a source in the induced
131  // subgraph of the CFG.
133  SmallVector<MachineBasicBlock *, 4> ReachableOrdered;
136 
137 public:
138  PhiIncomingAnalysis(MachinePostDominatorTree &PDT) : PDT(PDT) {}
139 
140  /// Returns whether \p MBB is a source in the induced subgraph of reachable
141  /// blocks.
142  bool isSource(MachineBasicBlock &MBB) const {
143  return ReachableMap.find(&MBB)->second;
144  }
145 
146  ArrayRef<MachineBasicBlock *> predecessors() const { return Predecessors; }
147 
148  void analyze(MachineBasicBlock &DefBlock,
149  ArrayRef<MachineBasicBlock *> IncomingBlocks) {
150  assert(Stack.empty());
151  ReachableMap.clear();
152  ReachableOrdered.clear();
153  Predecessors.clear();
154 
155  // Insert the def block first, so that it acts as an end point for the
156  // traversal.
157  ReachableMap.try_emplace(&DefBlock, false);
158  ReachableOrdered.push_back(&DefBlock);
159 
160  for (MachineBasicBlock *MBB : IncomingBlocks) {
161  if (MBB == &DefBlock) {
162  ReachableMap[&DefBlock] = true; // self-loop on DefBlock
163  continue;
164  }
165 
166  ReachableMap.try_emplace(MBB, false);
167  ReachableOrdered.push_back(MBB);
168 
169  // If this block has a divergent terminator and the def block is its
170  // post-dominator, the wave may first visit the other successors.
171  bool Divergent = false;
172  for (MachineInstr &MI : MBB->terminators()) {
173  if (MI.getOpcode() == AMDGPU::SI_NON_UNIFORM_BRCOND_PSEUDO ||
174  MI.getOpcode() == AMDGPU::SI_IF ||
175  MI.getOpcode() == AMDGPU::SI_ELSE ||
176  MI.getOpcode() == AMDGPU::SI_LOOP) {
177  Divergent = true;
178  break;
179  }
180  }
181 
182  if (Divergent && PDT.dominates(&DefBlock, MBB)) {
183  for (MachineBasicBlock *Succ : MBB->successors())
184  Stack.push_back(Succ);
185  }
186  }
187 
188  while (!Stack.empty()) {
189  MachineBasicBlock *MBB = Stack.pop_back_val();
190  if (!ReachableMap.try_emplace(MBB, false).second)
191  continue;
192  ReachableOrdered.push_back(MBB);
193 
194  for (MachineBasicBlock *Succ : MBB->successors())
195  Stack.push_back(Succ);
196  }
197 
198  for (MachineBasicBlock *MBB : ReachableOrdered) {
199  bool HaveReachablePred = false;
200  for (MachineBasicBlock *Pred : MBB->predecessors()) {
201  if (ReachableMap.count(Pred)) {
202  HaveReachablePred = true;
203  } else {
204  Stack.push_back(Pred);
205  }
206  }
207  if (!HaveReachablePred)
208  ReachableMap[MBB] = true;
209  if (HaveReachablePred) {
210  for (MachineBasicBlock *UnreachablePred : Stack) {
211  if (llvm::find(Predecessors, UnreachablePred) == Predecessors.end())
212  Predecessors.push_back(UnreachablePred);
213  }
214  }
215  Stack.clear();
216  }
217  }
218 };
219 
220 /// Helper class that detects loops which require us to lower an i1 COPY into
221 /// bitwise manipulation.
222 ///
223 /// Unfortunately, we cannot use LoopInfo because LoopInfo does not distinguish
224 /// between loops with the same header. Consider this example:
225 ///
226 /// A-+-+
227 /// | | |
228 /// B-+ |
229 /// | |
230 /// C---+
231 ///
232 /// A is the header of a loop containing A, B, and C as far as LoopInfo is
233 /// concerned. However, an i1 COPY in B that is used in C must be lowered to
234 /// bitwise operations to combine results from different loop iterations when
235 /// B has a divergent branch (since by default we will compile this code such
236 /// that threads in a wave are merged at the entry of C).
237 ///
238 /// The following rule is implemented to determine whether bitwise operations
239 /// are required: use the bitwise lowering for a def in block B if a backward
240 /// edge to B is reachable without going through the nearest common
241 /// post-dominator of B and all uses of the def.
242 ///
243 /// TODO: This rule is conservative because it does not check whether the
244 /// relevant branches are actually divergent.
245 ///
246 /// The class is designed to cache the CFG traversal so that it can be re-used
247 /// for multiple defs within the same basic block.
248 ///
249 /// TODO: We could use region analysis to quickly skip over SESE regions during
250 /// the traversal.
251 ///
252 class LoopFinder {
255 
256  // All visited / reachable block, tagged by level (level 0 is the def block,
257  // level 1 are all blocks reachable including but not going through the def
258  // block's IPDOM, etc.).
260 
261  // Nearest common dominator of all visited blocks by level (level 0 is the
262  // def block). Used for seeding the SSAUpdater.
263  SmallVector<MachineBasicBlock *, 4> CommonDominators;
264 
265  // Post-dominator of all visited blocks.
266  MachineBasicBlock *VisitedPostDom = nullptr;
267 
268  // Level at which a loop was found: 0 is not possible; 1 = a backward edge is
269  // reachable without going through the IPDOM of the def block (if the IPDOM
270  // itself has an edge to the def block, the loop level is 2), etc.
271  unsigned FoundLoopLevel = ~0u;
272 
273  MachineBasicBlock *DefBlock = nullptr;
276 
277 public:
278  LoopFinder(MachineDominatorTree &DT, MachinePostDominatorTree &PDT)
279  : DT(DT), PDT(PDT) {}
280 
281  void initialize(MachineBasicBlock &MBB) {
282  Visited.clear();
283  CommonDominators.clear();
284  Stack.clear();
285  NextLevel.clear();
286  VisitedPostDom = nullptr;
287  FoundLoopLevel = ~0u;
288 
289  DefBlock = &MBB;
290  }
291 
292  /// Check whether a backward edge can be reached without going through the
293  /// given \p PostDom of the def block.
294  ///
295  /// Return the level of \p PostDom if a loop was found, or 0 otherwise.
296  unsigned findLoop(MachineBasicBlock *PostDom) {
297  MachineDomTreeNode *PDNode = PDT.getNode(DefBlock);
298 
299  if (!VisitedPostDom)
300  advanceLevel();
301 
302  unsigned Level = 0;
303  while (PDNode->getBlock() != PostDom) {
304  if (PDNode->getBlock() == VisitedPostDom)
305  advanceLevel();
306  PDNode = PDNode->getIDom();
307  Level++;
308  if (FoundLoopLevel == Level)
309  return Level;
310  }
311 
312  return 0;
313  }
314 
315  /// Add undef values dominating the loop and the optionally given additional
316  /// blocks, so that the SSA updater doesn't have to search all the way to the
317  /// function entry.
318  void addLoopEntries(unsigned LoopLevel, MachineSSAUpdater &SSAUpdater,
319  ArrayRef<MachineBasicBlock *> Blocks = {}) {
320  assert(LoopLevel < CommonDominators.size());
321 
322  MachineBasicBlock *Dom = CommonDominators[LoopLevel];
323  for (MachineBasicBlock *MBB : Blocks)
324  Dom = DT.findNearestCommonDominator(Dom, MBB);
325 
326  if (!inLoopLevel(*Dom, LoopLevel, Blocks)) {
327  SSAUpdater.AddAvailableValue(Dom, insertUndefLaneMask(*Dom));
328  } else {
329  // The dominator is part of the loop or the given blocks, so add the
330  // undef value to unreachable predecessors instead.
331  for (MachineBasicBlock *Pred : Dom->predecessors()) {
332  if (!inLoopLevel(*Pred, LoopLevel, Blocks))
333  SSAUpdater.AddAvailableValue(Pred, insertUndefLaneMask(*Pred));
334  }
335  }
336  }
337 
338 private:
339  bool inLoopLevel(MachineBasicBlock &MBB, unsigned LoopLevel,
340  ArrayRef<MachineBasicBlock *> Blocks) const {
341  auto DomIt = Visited.find(&MBB);
342  if (DomIt != Visited.end() && DomIt->second <= LoopLevel)
343  return true;
344 
345  if (llvm::find(Blocks, &MBB) != Blocks.end())
346  return true;
347 
348  return false;
349  }
350 
351  void advanceLevel() {
352  MachineBasicBlock *VisitedDom;
353 
354  if (!VisitedPostDom) {
355  VisitedPostDom = DefBlock;
356  VisitedDom = DefBlock;
357  Stack.push_back(DefBlock);
358  } else {
359  VisitedPostDom = PDT.getNode(VisitedPostDom)->getIDom()->getBlock();
360  VisitedDom = CommonDominators.back();
361 
362  for (unsigned i = 0; i < NextLevel.size();) {
363  if (PDT.dominates(VisitedPostDom, NextLevel[i])) {
364  Stack.push_back(NextLevel[i]);
365 
366  NextLevel[i] = NextLevel.back();
367  NextLevel.pop_back();
368  } else {
369  i++;
370  }
371  }
372  }
373 
374  unsigned Level = CommonDominators.size();
375  while (!Stack.empty()) {
376  MachineBasicBlock *MBB = Stack.pop_back_val();
377  if (!PDT.dominates(VisitedPostDom, MBB))
378  NextLevel.push_back(MBB);
379 
380  Visited[MBB] = Level;
381  VisitedDom = DT.findNearestCommonDominator(VisitedDom, MBB);
382 
383  for (MachineBasicBlock *Succ : MBB->successors()) {
384  if (Succ == DefBlock) {
385  if (MBB == VisitedPostDom)
386  FoundLoopLevel = std::min(FoundLoopLevel, Level + 1);
387  else
388  FoundLoopLevel = std::min(FoundLoopLevel, Level);
389  continue;
390  }
391 
392  if (Visited.try_emplace(Succ, ~0u).second) {
393  if (MBB == VisitedPostDom)
394  NextLevel.push_back(Succ);
395  else
396  Stack.push_back(Succ);
397  }
398  }
399  }
400 
401  CommonDominators.push_back(VisitedDom);
402  }
403 };
404 
405 } // End anonymous namespace.
406 
407 INITIALIZE_PASS_BEGIN(SILowerI1Copies, DEBUG_TYPE, "SI Lower i1 Copies", false,
408  false)
412  false)
413 
414 char SILowerI1Copies::ID = 0;
415 
416 char &llvm::SILowerI1CopiesID = SILowerI1Copies::ID;
417 
419  return new SILowerI1Copies();
420 }
421 
422 static unsigned createLaneMaskReg(MachineFunction &MF) {
423  const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
424  MachineRegisterInfo &MRI = MF.getRegInfo();
425  return MRI.createVirtualRegister(ST.isWave32() ? &AMDGPU::SReg_32RegClass
426  : &AMDGPU::SReg_64RegClass);
427 }
428 
429 static unsigned insertUndefLaneMask(MachineBasicBlock &MBB) {
430  MachineFunction &MF = *MBB.getParent();
431  const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
432  const SIInstrInfo *TII = ST.getInstrInfo();
433  unsigned UndefReg = createLaneMaskReg(MF);
434  BuildMI(MBB, MBB.getFirstTerminator(), {}, TII->get(AMDGPU::IMPLICIT_DEF),
435  UndefReg);
436  return UndefReg;
437 }
438 
439 /// Lower all instructions that def or use vreg_1 registers.
440 ///
441 /// In a first pass, we lower COPYs from vreg_1 to vector registers, as can
442 /// occur around inline assembly. We do this first, before vreg_1 registers
443 /// are changed to scalar mask registers.
444 ///
445 /// Then we lower all defs of vreg_1 registers. Phi nodes are lowered before
446 /// all others, because phi lowering looks through copies and can therefore
447 /// often make copy lowering unnecessary.
448 bool SILowerI1Copies::runOnMachineFunction(MachineFunction &TheMF) {
449  MF = &TheMF;
450  MRI = &MF->getRegInfo();
451  DT = &getAnalysis<MachineDominatorTree>();
452  PDT = &getAnalysis<MachinePostDominatorTree>();
453 
454  ST = &MF->getSubtarget<GCNSubtarget>();
455  TII = ST->getInstrInfo();
456  IsWave32 = ST->isWave32();
457 
458  if (IsWave32) {
459  ExecReg = AMDGPU::EXEC_LO;
460  MovOp = AMDGPU::S_MOV_B32;
461  AndOp = AMDGPU::S_AND_B32;
462  OrOp = AMDGPU::S_OR_B32;
463  XorOp = AMDGPU::S_XOR_B32;
464  AndN2Op = AMDGPU::S_ANDN2_B32;
465  OrN2Op = AMDGPU::S_ORN2_B32;
466  } else {
467  ExecReg = AMDGPU::EXEC;
468  MovOp = AMDGPU::S_MOV_B64;
469  AndOp = AMDGPU::S_AND_B64;
470  OrOp = AMDGPU::S_OR_B64;
471  XorOp = AMDGPU::S_XOR_B64;
472  AndN2Op = AMDGPU::S_ANDN2_B64;
473  OrN2Op = AMDGPU::S_ORN2_B64;
474  }
475 
476  lowerCopiesFromI1();
477  lowerPhis();
478  lowerCopiesToI1();
479 
480  for (unsigned Reg : ConstrainRegs)
481  MRI->constrainRegClass(Reg, &AMDGPU::SReg_1_XEXECRegClass);
482  ConstrainRegs.clear();
483 
484  return true;
485 }
486 
487 void SILowerI1Copies::lowerCopiesFromI1() {
489 
490  for (MachineBasicBlock &MBB : *MF) {
491  for (MachineInstr &MI : MBB) {
492  if (MI.getOpcode() != AMDGPU::COPY)
493  continue;
494 
495  unsigned DstReg = MI.getOperand(0).getReg();
496  unsigned SrcReg = MI.getOperand(1).getReg();
498  MRI->getRegClass(SrcReg) != &AMDGPU::VReg_1RegClass)
499  continue;
500 
501  if (isLaneMaskReg(DstReg) ||
503  MRI->getRegClass(DstReg) == &AMDGPU::VReg_1RegClass))
504  continue;
505 
506  // Copy into a 32-bit vector register.
507  LLVM_DEBUG(dbgs() << "Lower copy from i1: " << MI);
508  DebugLoc DL = MI.getDebugLoc();
509 
510  assert(TII->getRegisterInfo().getRegSizeInBits(DstReg, *MRI) == 32);
511  assert(!MI.getOperand(0).getSubReg());
512 
513  ConstrainRegs.insert(SrcReg);
514  BuildMI(MBB, MI, DL, TII->get(AMDGPU::V_CNDMASK_B32_e64), DstReg)
515  .addImm(0)
516  .addImm(0)
517  .addImm(0)
518  .addImm(-1)
519  .addReg(SrcReg);
520  DeadCopies.push_back(&MI);
521  }
522 
523  for (MachineInstr *MI : DeadCopies)
524  MI->eraseFromParent();
525  DeadCopies.clear();
526  }
527 }
528 
529 void SILowerI1Copies::lowerPhis() {
530  MachineSSAUpdater SSAUpdater(*MF);
531  LoopFinder LF(*DT, *PDT);
532  PhiIncomingAnalysis PIA(*PDT);
535  SmallVector<unsigned, 4> IncomingRegs;
536  SmallVector<unsigned, 4> IncomingUpdated;
537 #ifndef NDEBUG
538  DenseSet<unsigned> PhiRegisters;
539 #endif
540 
541  for (MachineBasicBlock &MBB : *MF) {
542  LF.initialize(MBB);
543 
544  for (MachineInstr &MI : MBB.phis()) {
545  unsigned DstReg = MI.getOperand(0).getReg();
546  if (MRI->getRegClass(DstReg) != &AMDGPU::VReg_1RegClass)
547  continue;
548 
549  LLVM_DEBUG(dbgs() << "Lower PHI: " << MI);
550 
551  MRI->setRegClass(DstReg, IsWave32 ? &AMDGPU::SReg_32RegClass
552  : &AMDGPU::SReg_64RegClass);
553 
554  // Collect incoming values.
555  for (unsigned i = 1; i < MI.getNumOperands(); i += 2) {
556  assert(i + 1 < MI.getNumOperands());
557  unsigned IncomingReg = MI.getOperand(i).getReg();
558  MachineBasicBlock *IncomingMBB = MI.getOperand(i + 1).getMBB();
559  MachineInstr *IncomingDef = MRI->getUniqueVRegDef(IncomingReg);
560 
561  if (IncomingDef->getOpcode() == AMDGPU::COPY) {
562  IncomingReg = IncomingDef->getOperand(1).getReg();
563  assert(isLaneMaskReg(IncomingReg));
564  assert(!IncomingDef->getOperand(1).getSubReg());
565  } else if (IncomingDef->getOpcode() == AMDGPU::IMPLICIT_DEF) {
566  continue;
567  } else {
568  assert(IncomingDef->isPHI() || PhiRegisters.count(IncomingReg));
569  }
570 
571  IncomingBlocks.push_back(IncomingMBB);
572  IncomingRegs.push_back(IncomingReg);
573  }
574 
575 #ifndef NDEBUG
576  PhiRegisters.insert(DstReg);
577 #endif
578 
579  // Phis in a loop that are observed outside the loop receive a simple but
580  // conservatively correct treatment.
581  MachineBasicBlock *PostDomBound = &MBB;
582  for (MachineInstr &Use : MRI->use_instructions(DstReg)) {
583  PostDomBound =
584  PDT->findNearestCommonDominator(PostDomBound, Use.getParent());
585  }
586 
587  unsigned FoundLoopLevel = LF.findLoop(PostDomBound);
588 
589  SSAUpdater.Initialize(DstReg);
590 
591  if (FoundLoopLevel) {
592  LF.addLoopEntries(FoundLoopLevel, SSAUpdater, IncomingBlocks);
593 
594  for (unsigned i = 0; i < IncomingRegs.size(); ++i) {
595  IncomingUpdated.push_back(createLaneMaskReg(*MF));
596  SSAUpdater.AddAvailableValue(IncomingBlocks[i],
597  IncomingUpdated.back());
598  }
599 
600  for (unsigned i = 0; i < IncomingRegs.size(); ++i) {
601  MachineBasicBlock &IMBB = *IncomingBlocks[i];
602  buildMergeLaneMasks(
603  IMBB, getSaluInsertionAtEnd(IMBB), {}, IncomingUpdated[i],
604  SSAUpdater.GetValueInMiddleOfBlock(&IMBB), IncomingRegs[i]);
605  }
606  } else {
607  // The phi is not observed from outside a loop. Use a more accurate
608  // lowering.
609  PIA.analyze(MBB, IncomingBlocks);
610 
611  for (MachineBasicBlock *MBB : PIA.predecessors())
612  SSAUpdater.AddAvailableValue(MBB, insertUndefLaneMask(*MBB));
613 
614  for (unsigned i = 0; i < IncomingRegs.size(); ++i) {
615  MachineBasicBlock &IMBB = *IncomingBlocks[i];
616  if (PIA.isSource(IMBB)) {
617  IncomingUpdated.push_back(0);
618  SSAUpdater.AddAvailableValue(&IMBB, IncomingRegs[i]);
619  } else {
620  IncomingUpdated.push_back(createLaneMaskReg(*MF));
621  SSAUpdater.AddAvailableValue(&IMBB, IncomingUpdated.back());
622  }
623  }
624 
625  for (unsigned i = 0; i < IncomingRegs.size(); ++i) {
626  if (!IncomingUpdated[i])
627  continue;
628 
629  MachineBasicBlock &IMBB = *IncomingBlocks[i];
630  buildMergeLaneMasks(
631  IMBB, getSaluInsertionAtEnd(IMBB), {}, IncomingUpdated[i],
632  SSAUpdater.GetValueInMiddleOfBlock(&IMBB), IncomingRegs[i]);
633  }
634  }
635 
636  unsigned NewReg = SSAUpdater.GetValueInMiddleOfBlock(&MBB);
637  if (NewReg != DstReg) {
638  MRI->replaceRegWith(NewReg, DstReg);
639 
640  // Ensure that DstReg has a single def and mark the old PHI node for
641  // deletion.
642  MI.getOperand(0).setReg(NewReg);
643  DeadPhis.push_back(&MI);
644  }
645 
646  IncomingBlocks.clear();
647  IncomingRegs.clear();
648  IncomingUpdated.clear();
649  }
650 
651  for (MachineInstr *MI : DeadPhis)
652  MI->eraseFromParent();
653  DeadPhis.clear();
654  }
655 }
656 
657 void SILowerI1Copies::lowerCopiesToI1() {
658  MachineSSAUpdater SSAUpdater(*MF);
659  LoopFinder LF(*DT, *PDT);
661 
662  for (MachineBasicBlock &MBB : *MF) {
663  LF.initialize(MBB);
664 
665  for (MachineInstr &MI : MBB) {
666  if (MI.getOpcode() != AMDGPU::IMPLICIT_DEF &&
667  MI.getOpcode() != AMDGPU::COPY)
668  continue;
669 
670  unsigned DstReg = MI.getOperand(0).getReg();
672  MRI->getRegClass(DstReg) != &AMDGPU::VReg_1RegClass)
673  continue;
674 
675  if (MRI->use_empty(DstReg)) {
676  DeadCopies.push_back(&MI);
677  continue;
678  }
679 
680  LLVM_DEBUG(dbgs() << "Lower Other: " << MI);
681 
682  MRI->setRegClass(DstReg, IsWave32 ? &AMDGPU::SReg_32RegClass
683  : &AMDGPU::SReg_64RegClass);
684  if (MI.getOpcode() == AMDGPU::IMPLICIT_DEF)
685  continue;
686 
687  DebugLoc DL = MI.getDebugLoc();
688  unsigned SrcReg = MI.getOperand(1).getReg();
689  assert(!MI.getOperand(1).getSubReg());
690 
692  !isLaneMaskReg(SrcReg)) {
693  assert(TII->getRegisterInfo().getRegSizeInBits(SrcReg, *MRI) == 32);
694  unsigned TmpReg = createLaneMaskReg(*MF);
695  BuildMI(MBB, MI, DL, TII->get(AMDGPU::V_CMP_NE_U32_e64), TmpReg)
696  .addReg(SrcReg)
697  .addImm(0);
698  MI.getOperand(1).setReg(TmpReg);
699  SrcReg = TmpReg;
700  }
701 
702  // Defs in a loop that are observed outside the loop must be transformed
703  // into appropriate bit manipulation.
704  MachineBasicBlock *PostDomBound = &MBB;
705  for (MachineInstr &Use : MRI->use_instructions(DstReg)) {
706  PostDomBound =
707  PDT->findNearestCommonDominator(PostDomBound, Use.getParent());
708  }
709 
710  unsigned FoundLoopLevel = LF.findLoop(PostDomBound);
711  if (FoundLoopLevel) {
712  SSAUpdater.Initialize(DstReg);
713  SSAUpdater.AddAvailableValue(&MBB, DstReg);
714  LF.addLoopEntries(FoundLoopLevel, SSAUpdater);
715 
716  buildMergeLaneMasks(MBB, MI, DL, DstReg,
717  SSAUpdater.GetValueInMiddleOfBlock(&MBB), SrcReg);
718  DeadCopies.push_back(&MI);
719  }
720  }
721 
722  for (MachineInstr *MI : DeadCopies)
723  MI->eraseFromParent();
724  DeadCopies.clear();
725  }
726 }
727 
728 bool SILowerI1Copies::isConstantLaneMask(unsigned Reg, bool &Val) const {
729  const MachineInstr *MI;
730  for (;;) {
731  MI = MRI->getUniqueVRegDef(Reg);
732  if (MI->getOpcode() != AMDGPU::COPY)
733  break;
734 
735  Reg = MI->getOperand(1).getReg();
737  return false;
738  if (!isLaneMaskReg(Reg))
739  return false;
740  }
741 
742  if (MI->getOpcode() != MovOp)
743  return false;
744 
745  if (!MI->getOperand(1).isImm())
746  return false;
747 
748  int64_t Imm = MI->getOperand(1).getImm();
749  if (Imm == 0) {
750  Val = false;
751  return true;
752  }
753  if (Imm == -1) {
754  Val = true;
755  return true;
756  }
757 
758  return false;
759 }
760 
761 static void instrDefsUsesSCC(const MachineInstr &MI, bool &Def, bool &Use) {
762  Def = false;
763  Use = false;
764 
765  for (const MachineOperand &MO : MI.operands()) {
766  if (MO.isReg() && MO.getReg() == AMDGPU::SCC) {
767  if (MO.isUse())
768  Use = true;
769  else
770  Def = true;
771  }
772  }
773 }
774 
775 /// Return a point at the end of the given \p MBB to insert SALU instructions
776 /// for lane mask calculation. Take terminators and SCC into account.
778 SILowerI1Copies::getSaluInsertionAtEnd(MachineBasicBlock &MBB) const {
779  auto InsertionPt = MBB.getFirstTerminator();
780  bool TerminatorsUseSCC = false;
781  for (auto I = InsertionPt, E = MBB.end(); I != E; ++I) {
782  bool DefsSCC;
783  instrDefsUsesSCC(*I, DefsSCC, TerminatorsUseSCC);
784  if (TerminatorsUseSCC || DefsSCC)
785  break;
786  }
787 
788  if (!TerminatorsUseSCC)
789  return InsertionPt;
790 
791  while (InsertionPt != MBB.begin()) {
792  InsertionPt--;
793 
794  bool DefSCC, UseSCC;
795  instrDefsUsesSCC(*InsertionPt, DefSCC, UseSCC);
796  if (DefSCC)
797  return InsertionPt;
798  }
799 
800  // We should have at least seen an IMPLICIT_DEF or COPY
801  llvm_unreachable("SCC used by terminator but no def in block");
802 }
803 
804 void SILowerI1Copies::buildMergeLaneMasks(MachineBasicBlock &MBB,
806  const DebugLoc &DL, unsigned DstReg,
807  unsigned PrevReg, unsigned CurReg) {
808  bool PrevVal;
809  bool PrevConstant = isConstantLaneMask(PrevReg, PrevVal);
810  bool CurVal;
811  bool CurConstant = isConstantLaneMask(CurReg, CurVal);
812 
813  if (PrevConstant && CurConstant) {
814  if (PrevVal == CurVal) {
815  BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), DstReg).addReg(CurReg);
816  } else if (CurVal) {
817  BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), DstReg).addReg(ExecReg);
818  } else {
819  BuildMI(MBB, I, DL, TII->get(XorOp), DstReg)
820  .addReg(ExecReg)
821  .addImm(-1);
822  }
823  return;
824  }
825 
826  unsigned PrevMaskedReg = 0;
827  unsigned CurMaskedReg = 0;
828  if (!PrevConstant) {
829  if (CurConstant && CurVal) {
830  PrevMaskedReg = PrevReg;
831  } else {
832  PrevMaskedReg = createLaneMaskReg(*MF);
833  BuildMI(MBB, I, DL, TII->get(AndN2Op), PrevMaskedReg)
834  .addReg(PrevReg)
835  .addReg(ExecReg);
836  }
837  }
838  if (!CurConstant) {
839  // TODO: check whether CurReg is already masked by EXEC
840  if (PrevConstant && PrevVal) {
841  CurMaskedReg = CurReg;
842  } else {
843  CurMaskedReg = createLaneMaskReg(*MF);
844  BuildMI(MBB, I, DL, TII->get(AndOp), CurMaskedReg)
845  .addReg(CurReg)
846  .addReg(ExecReg);
847  }
848  }
849 
850  if (PrevConstant && !PrevVal) {
851  BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), DstReg)
852  .addReg(CurMaskedReg);
853  } else if (CurConstant && !CurVal) {
854  BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), DstReg)
855  .addReg(PrevMaskedReg);
856  } else if (PrevConstant && PrevVal) {
857  BuildMI(MBB, I, DL, TII->get(OrN2Op), DstReg)
858  .addReg(CurMaskedReg)
859  .addReg(ExecReg);
860  } else {
861  BuildMI(MBB, I, DL, TII->get(OrOp), DstReg)
862  .addReg(PrevMaskedReg)
863  .addReg(CurMaskedReg ? CurMaskedReg : ExecReg);
864  }
865 }
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:38
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
AMDGPU specific subclass of TargetSubtarget.
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned getReg() const
getReg - Returns the register number.
#define DEBUG_TYPE
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
INITIALIZE_PASS_BEGIN(SILowerI1Copies, DEBUG_TYPE, "SI Lower i1 Copies", false, false) INITIALIZE_PASS_END(SILowerI1Copies
unsigned Reg
unsigned getSubReg() const
iterator_range< iterator > phis()
Returns a range that iterates over the phis in the basic block.
const SIInstrInfo * getInstrInfo() const override
A debug info location.
Definition: DebugLoc.h:33
static void instrDefsUsesSCC(const MachineInstr &MI, bool &Def, bool &Use)
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:460
bool isPHI() const
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
MachineSSAUpdater - This class updates SSA form for a set of virtual registers defined in multiple bl...
const SIRegisterInfo & getRegisterInfo() const
Definition: SIInstrInfo.h:171
iterator_range< succ_iterator > successors()
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
bool isSGPRReg(const MachineRegisterInfo &MRI, unsigned Reg) const
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
iterator_range< iterator > terminators()
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
static bool isSource(Value *V)
Return true if the given value is a source in the use-def chain, producing a narrow &#39;TypeSize&#39; value...
FunctionPass * createSILowerI1CopiesPass()
Base class for the actual dominator tree node.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
void Initialize(unsigned V)
Initialize - Reset this object to get ready for a new set of SSA updates.
const TargetRegisterClass * constrainRegClass(unsigned Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
NodeT * getBlock() const
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
DomTreeNodeBase * getIDom() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
iterator_range< pred_iterator > predecessors()
char & SILowerI1CopiesID
size_t size() const
Definition: SmallVector.h:52
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1213
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned getWavefrontSize() const
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
iterator end() const
Definition: ArrayRef.h:137
SI Lower i1 Copies
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
int64_t getImm() const
MachineInstr * getUniqueVRegDef(unsigned Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
Initialize the set of available library functions based on the specified target triple.
bool use_empty(unsigned RegNo) const
use_empty - Return true if there are no instructions using the specified register.
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Provides AMDGPU specific target descriptions.
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Interface definition for SIInstrInfo.
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
static unsigned createLaneMaskReg(MachineFunction &MF)
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
static unsigned insertUndefLaneMask(MachineBasicBlock &MBB)
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned GetValueInMiddleOfBlock(MachineBasicBlock *BB)
GetValueInMiddleOfBlock - Construct SSA form, materializing a value that is live in the middle of the...
void AddAvailableValue(MachineBasicBlock *BB, unsigned V)
AddAvailableValue - Indicate that a rewritten value is available at the end of the specified block wi...
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
iterator_range< use_instr_iterator > use_instructions(unsigned Reg) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
void setRegClass(unsigned Reg, const TargetRegisterClass *RC)
setRegClass - Set the register class of the specified virtual register.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
void initializeSILowerI1CopiesPass(PassRegistry &)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
unsigned createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...