1 //===-- SILowerControlFlow.cpp - Use predicates for control flow ----------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file
11 /// \brief This pass lowers the pseudo control flow instructions to real
12 /// machine instructions.
13 ///
14 /// All control flow is handled using predicated instructions and
15 /// a predicate stack.  Each Scalar ALU controls the operations of 64 Vector
16 /// ALUs.  The Scalar ALU can update the predicate for any of the Vector ALUs
17 /// by writting to the 64-bit EXEC register (each bit corresponds to a
18 /// single vector ALU).  Typically, for predicates, a vector ALU will write
19 /// to its bit of the VCC register (like EXEC VCC is 64-bits, one for each
20 /// Vector ALU) and then the ScalarALU will AND the VCC register with the
21 /// EXEC to update the predicates.
22 ///
23 /// For example:
24 /// %VCC = V_CMP_GT_F32 %VGPR1, %VGPR2
25 /// %SGPR0 = SI_IF %VCC
26 ///   %VGPR0 = V_ADD_F32 %VGPR0, %VGPR0
27 /// %SGPR0 = SI_ELSE %SGPR0
28 ///   %VGPR0 = V_SUB_F32 %VGPR0, %VGPR0
29 /// SI_END_CF %SGPR0
30 ///
31 /// becomes:
32 ///
33 /// %SGPR0 = S_AND_SAVEEXEC_B64 %VCC  // Save and update the exec mask
34 /// %SGPR0 = S_XOR_B64 %SGPR0, %EXEC  // Clear live bits from saved exec mask
35 /// S_CBRANCH_EXECZ label0            // This instruction is an optional
36 ///                                   // optimization which allows us to
37 ///                                   // branch if all the bits of
38 ///                                   // EXEC are zero.
39 /// %VGPR0 = V_ADD_F32 %VGPR0, %VGPR0 // Do the IF block of the branch
40 ///
41 /// label0:
42 /// %SGPR0 = S_OR_SAVEEXEC_B64 %EXEC   // Restore the exec mask for the Then block
43 /// %EXEC = S_XOR_B64 %SGPR0, %EXEC    // Clear live bits from saved exec mask
44 /// S_BRANCH_EXECZ label1              // Use our branch optimization
45 ///                                    // instruction again.
46 /// %VGPR0 = V_SUB_F32 %VGPR0, %VGPR   // Do the THEN block
47 /// label1:
48 /// %EXEC = S_OR_B64 %EXEC, %SGPR0     // Re-enable saved exec mask bits
49 //===----------------------------------------------------------------------===//
50 
51 #include "AMDGPU.h"
52 #include "AMDGPUSubtarget.h"
53 #include "SIInstrInfo.h"
54 #include "SIMachineFunctionInfo.h"
55 #include "llvm/CodeGen/LivePhysRegs.h"
56 #include "llvm/CodeGen/MachineFrameInfo.h"
57 #include "llvm/CodeGen/MachineFunction.h"
58 #include "llvm/CodeGen/MachineFunctionPass.h"
59 #include "llvm/CodeGen/MachineInstrBuilder.h"
60 #include "llvm/CodeGen/MachineRegisterInfo.h"
61 
62 using namespace llvm;
63 
64 #define DEBUG_TYPE "si-lower-control-flow"
65 
66 namespace {
67 
68 class SILowerControlFlow : public MachineFunctionPass {
69 private:
70   const SIRegisterInfo *TRI;
71   const SIInstrInfo *TII;
72   LiveIntervals *LIS;
73   MachineRegisterInfo *MRI;
74 
75   void emitIf(MachineInstr &MI);
76   void emitElse(MachineInstr &MI);
77   void emitBreak(MachineInstr &MI);
78   void emitIfBreak(MachineInstr &MI);
79   void emitElseBreak(MachineInstr &MI);
80   void emitLoop(MachineInstr &MI);
81   void emitEndCf(MachineInstr &MI);
82 
83 public:
84   static char ID;
85 
86   SILowerControlFlow() :
87     MachineFunctionPass(ID),
88     TRI(nullptr),
89     TII(nullptr),
90     LIS(nullptr),
91     MRI(nullptr) {}
92 
93   bool runOnMachineFunction(MachineFunction &MF) override;
94 
95   StringRef getPassName() const override {
96     return "SI Lower control flow pseudo instructions";
97   }
98 
99   void getAnalysisUsage(AnalysisUsage &AU) const override {
100     // Should preserve the same set that TwoAddressInstructions does.
101     AU.addPreserved<SlotIndexes>();
102     AU.addPreserved<LiveIntervals>();
103     AU.addPreservedID(LiveVariablesID);
104     AU.addPreservedID(MachineLoopInfoID);
105     AU.addPreservedID(MachineDominatorsID);
106     AU.setPreservesCFG();
107     MachineFunctionPass::getAnalysisUsage(AU);
108   }
109 };
110 
111 } // End anonymous namespace
112 
113 char SILowerControlFlow::ID = 0;
114 
115 INITIALIZE_PASS(SILowerControlFlow, DEBUG_TYPE,
116                "SI lower control flow", false, false)
117 
118 static void setImpSCCDefDead(MachineInstr &MI, bool IsDead) {
119   MachineOperand &ImpDefSCC = MI.getOperand(3);
120   assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
121 
122   ImpDefSCC.setIsDead(IsDead);
123 }
124 
125 char &llvm::SILowerControlFlowID = SILowerControlFlow::ID;
126 
127 void SILowerControlFlow::emitIf(MachineInstr &MI) {
128   MachineBasicBlock &MBB = *MI.getParent();
129   const DebugLoc &DL = MI.getDebugLoc();
130   MachineBasicBlock::iterator I(&MI);
131 
132   MachineOperand &SaveExec = MI.getOperand(0);
133   MachineOperand &Cond = MI.getOperand(1);
134   assert(SaveExec.getSubReg() == AMDGPU::NoSubRegister &&
135          Cond.getSubReg() == AMDGPU::NoSubRegister);
136 
137   unsigned SaveExecReg = SaveExec.getReg();
138 
139   MachineOperand &ImpDefSCC = MI.getOperand(4);
140   assert(ImpDefSCC.getReg() == AMDGPU::SCC && ImpDefSCC.isDef());
141 
142   // Add an implicit def of exec to discourage scheduling VALU after this which
143   // will interfere with trying to form s_and_saveexec_b64 later.
144   unsigned CopyReg = MRI->createVirtualRegister(&AMDGPU::SReg_64RegClass);
145   MachineInstr *CopyExec =
146     BuildMI(MBB, I, DL, TII->get(AMDGPU::COPY), CopyReg)
147     .addReg(AMDGPU::EXEC)
148     .addReg(AMDGPU::EXEC, RegState::ImplicitDefine);
149 
150   unsigned Tmp = MRI->createVirtualRegister(&AMDGPU::SReg_64RegClass);
151 
152   MachineInstr *And =
153     BuildMI(MBB, I, DL, TII->get(AMDGPU::S_AND_B64), Tmp)
154     .addReg(CopyReg)
155     //.addReg(AMDGPU::EXEC)
156     .addReg(Cond.getReg());
157   setImpSCCDefDead(*And, true);
158 
159   MachineInstr *Xor =
160     BuildMI(MBB, I, DL, TII->get(AMDGPU::S_XOR_B64), SaveExecReg)
161     .addReg(Tmp)
162     .addReg(CopyReg);
163   setImpSCCDefDead(*Xor, ImpDefSCC.isDead());
164 
165   // Use a copy that is a terminator to get correct spill code placement it with
166   // fast regalloc.
167   MachineInstr *SetExec =
168     BuildMI(MBB, I, DL, TII->get(AMDGPU::S_MOV_B64_term), AMDGPU::EXEC)
169     .addReg(Tmp, RegState::Kill);
170 
171   // Insert a pseudo terminator to help keep the verifier happy. This will also
172   // be used later when inserting skips.
173   MachineInstr *NewBr =
174     BuildMI(MBB, I, DL, TII->get(AMDGPU::SI_MASK_BRANCH))
175     .addOperand(MI.getOperand(2));
176 
177   if (!LIS) {
178     MI.eraseFromParent();
179     return;
180   }
181 
182   LIS->InsertMachineInstrInMaps(*CopyExec);
183 
184   // Replace with and so we don't need to fix the live interval for condition
185   // register.
186   LIS->ReplaceMachineInstrInMaps(MI, *And);
187 
188   LIS->InsertMachineInstrInMaps(*Xor);
189   LIS->InsertMachineInstrInMaps(*SetExec);
190   LIS->InsertMachineInstrInMaps(*NewBr);
191 
192   LIS->removeRegUnit(*MCRegUnitIterator(AMDGPU::EXEC, TRI));
193   MI.eraseFromParent();
194 
195   // FIXME: Is there a better way of adjusting the liveness? It shouldn't be
196   // hard to add another def here but I'm not sure how to correctly update the
197   // valno.
198   LIS->removeInterval(SaveExecReg);
199   LIS->createAndComputeVirtRegInterval(SaveExecReg);
200   LIS->createAndComputeVirtRegInterval(Tmp);
201   LIS->createAndComputeVirtRegInterval(CopyReg);
202 }
203 
204 void SILowerControlFlow::emitElse(MachineInstr &MI) {
205   MachineBasicBlock &MBB = *MI.getParent();
206   const DebugLoc &DL = MI.getDebugLoc();
207 
208   unsigned DstReg = MI.getOperand(0).getReg();
209   assert(MI.getOperand(0).getSubReg() == AMDGPU::NoSubRegister);
210 
211   bool ExecModified = MI.getOperand(3).getImm() != 0;
212   MachineBasicBlock::iterator Start = MBB.begin();
213 
214   // We are running before TwoAddressInstructions, and si_else's operands are
215   // tied. In order to correctly tie the registers, split this into a copy of
216   // the src like it does.
217   unsigned CopyReg = MRI->createVirtualRegister(&AMDGPU::SReg_64RegClass);
218   BuildMI(MBB, Start, DL, TII->get(AMDGPU::COPY), CopyReg)
219     .addOperand(MI.getOperand(1)); // Saved EXEC
220 
221   // This must be inserted before phis and any spill code inserted before the
222   // else.
223   unsigned SaveReg = ExecModified ?
224     MRI->createVirtualRegister(&AMDGPU::SReg_64RegClass) : DstReg;
225   MachineInstr *OrSaveExec =
226     BuildMI(MBB, Start, DL, TII->get(AMDGPU::S_OR_SAVEEXEC_B64), SaveReg)
227     .addReg(CopyReg);
228 
229   MachineBasicBlock *DestBB = MI.getOperand(2).getMBB();
230 
231   MachineBasicBlock::iterator ElsePt(MI);
232 
233   if (ExecModified) {
234     MachineInstr *And =
235       BuildMI(MBB, ElsePt, DL, TII->get(AMDGPU::S_AND_B64), DstReg)
236       .addReg(AMDGPU::EXEC)
237       .addReg(SaveReg);
238 
239     if (LIS)
240       LIS->InsertMachineInstrInMaps(*And);
241   }
242 
243   MachineInstr *Xor =
244     BuildMI(MBB, ElsePt, DL, TII->get(AMDGPU::S_XOR_B64_term), AMDGPU::EXEC)
245     .addReg(AMDGPU::EXEC)
246     .addReg(DstReg);
247 
248   MachineInstr *Branch =
249     BuildMI(MBB, ElsePt, DL, TII->get(AMDGPU::SI_MASK_BRANCH))
250     .addMBB(DestBB);
251 
252   if (!LIS) {
253     MI.eraseFromParent();
254     return;
255   }
256 
257   LIS->RemoveMachineInstrFromMaps(MI);
258   MI.eraseFromParent();
259 
260   LIS->InsertMachineInstrInMaps(*OrSaveExec);
261 
262   LIS->InsertMachineInstrInMaps(*Xor);
263   LIS->InsertMachineInstrInMaps(*Branch);
264 
265   // src reg is tied to dst reg.
266   LIS->removeInterval(DstReg);
267   LIS->createAndComputeVirtRegInterval(DstReg);
268   LIS->createAndComputeVirtRegInterval(CopyReg);
269   if (ExecModified)
270     LIS->createAndComputeVirtRegInterval(SaveReg);
271 
272   // Let this be recomputed.
273   LIS->removeRegUnit(*MCRegUnitIterator(AMDGPU::EXEC, TRI));
274 }
275 
276 void SILowerControlFlow::emitBreak(MachineInstr &MI) {
277   MachineBasicBlock &MBB = *MI.getParent();
278   const DebugLoc &DL = MI.getDebugLoc();
279   unsigned Dst = MI.getOperand(0).getReg();
280 
281   MachineInstr *Or =
282     BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_OR_B64), Dst)
283     .addReg(AMDGPU::EXEC)
284     .addOperand(MI.getOperand(1));
285 
286   if (LIS)
287     LIS->ReplaceMachineInstrInMaps(MI, *Or);
288   MI.eraseFromParent();
289 }
290 
291 void SILowerControlFlow::emitIfBreak(MachineInstr &MI) {
292   MI.setDesc(TII->get(AMDGPU::S_OR_B64));
293 }
294 
295 void SILowerControlFlow::emitElseBreak(MachineInstr &MI) {
296   MI.setDesc(TII->get(AMDGPU::S_OR_B64));
297 }
298 
299 void SILowerControlFlow::emitLoop(MachineInstr &MI) {
300   MachineBasicBlock &MBB = *MI.getParent();
301   const DebugLoc &DL = MI.getDebugLoc();
302 
303   MachineInstr *AndN2 =
304     BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_ANDN2_B64_term), AMDGPU::EXEC)
305     .addReg(AMDGPU::EXEC)
306     .addOperand(MI.getOperand(0));
307 
308   MachineInstr *Branch =
309     BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_CBRANCH_EXECNZ))
310     .addOperand(MI.getOperand(1));
311 
312   if (LIS) {
313     LIS->ReplaceMachineInstrInMaps(MI, *AndN2);
314     LIS->InsertMachineInstrInMaps(*Branch);
315   }
316 
317   MI.eraseFromParent();
318 }
319 
320 void SILowerControlFlow::emitEndCf(MachineInstr &MI) {
321   MachineBasicBlock &MBB = *MI.getParent();
322   const DebugLoc &DL = MI.getDebugLoc();
323 
324   MachineBasicBlock::iterator InsPt = MBB.begin();
325   MachineInstr *NewMI =
326     BuildMI(MBB, InsPt, DL, TII->get(AMDGPU::S_OR_B64), AMDGPU::EXEC)
327     .addReg(AMDGPU::EXEC)
328     .addOperand(MI.getOperand(0));
329 
330   if (LIS)
331     LIS->ReplaceMachineInstrInMaps(MI, *NewMI);
332 
333   MI.eraseFromParent();
334 
335   if (LIS)
336     LIS->handleMove(*NewMI);
337 }
338 
339 bool SILowerControlFlow::runOnMachineFunction(MachineFunction &MF) {
340   const SISubtarget &ST = MF.getSubtarget<SISubtarget>();
341   TII = ST.getInstrInfo();
342   TRI = &TII->getRegisterInfo();
343 
344   // This doesn't actually need LiveIntervals, but we can preserve them.
345   LIS = getAnalysisIfAvailable<LiveIntervals>();
346   MRI = &MF.getRegInfo();
347 
348   MachineFunction::iterator NextBB;
349   for (MachineFunction::iterator BI = MF.begin(), BE = MF.end();
350        BI != BE; BI = NextBB) {
351     NextBB = std::next(BI);
352     MachineBasicBlock &MBB = *BI;
353 
354     MachineBasicBlock::iterator I, Next;
355 
356     for (I = MBB.begin(); I != MBB.end(); I = Next) {
357       Next = std::next(I);
358       MachineInstr &MI = *I;
359 
360       switch (MI.getOpcode()) {
361       case AMDGPU::SI_IF:
362         emitIf(MI);
363         break;
364 
365       case AMDGPU::SI_ELSE:
366         emitElse(MI);
367         break;
368 
369       case AMDGPU::SI_BREAK:
370         emitBreak(MI);
371         break;
372 
373       case AMDGPU::SI_IF_BREAK:
374         emitIfBreak(MI);
375         break;
376 
377       case AMDGPU::SI_ELSE_BREAK:
378         emitElseBreak(MI);
379         break;
380 
381       case AMDGPU::SI_LOOP:
382         emitLoop(MI);
383         break;
384 
385       case AMDGPU::SI_END_CF:
386         emitEndCf(MI);
387         break;
388 
389       default:
390         break;
391       }
392     }
393   }
394 
395   return true;
396 }
397