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