1 //===-- AMDGPULaneDominator.cpp - Determine Lane Dominators ---------------===//
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 // MBB A lane-dominates MBB B if
11 // 1. A dominates B in the usual sense, i.e. every path from the entry to B
12 //    goes through A, and
13 // 2. whenever B executes, every active lane during that execution of B was
14 //    also active during the most recent execution of A.
15 //
16 // The simplest example where A dominates B but does not lane-dominate it is
17 // where A is a loop:
18 //
19 //     |
20 //     +--+
21 //     A  |
22 //     +--+
23 //     |
24 //     B
25 //
26 // Unfortunately, the second condition is not fully captured by the control
27 // flow graph when it is unstructured (as may happen when branch conditions are
28 // uniform).
29 //
30 // The following replacement of the second condition is a conservative
31 // approximation. It is an equivalent condition when the CFG is fully
32 // structured:
33 //
34 // 2'. every cycle in the CFG that contains A also contains B.
35 //
36 //===----------------------------------------------------------------------===//
37 
38 #include "AMDGPULaneDominator.h"
39 
40 #include "llvm/ADT/DenseSet.h"
41 #include "llvm/ADT/SmallVector.h"
42 #include "llvm/CodeGen/MachineBasicBlock.h"
43 
44 namespace llvm {
45 
46 namespace AMDGPU {
47 
48 // Given machine basic blocks A and B where A dominates B, check whether
49 // A lane-dominates B.
50 //
51 // The check is conservative, i.e. there can be false-negatives.
laneDominates(MachineBasicBlock * A,MachineBasicBlock * B)52 bool laneDominates(MachineBasicBlock *A, MachineBasicBlock *B) {
53   // Check whether A is reachable from itself without going through B.
54   DenseSet<MachineBasicBlock *> Reachable;
55   SmallVector<MachineBasicBlock *, 8> Stack;
56 
57   Stack.push_back(A);
58   do {
59     MachineBasicBlock *MBB = Stack.back();
60     Stack.pop_back();
61 
62     for (MachineBasicBlock *Succ : MBB->successors()) {
63       if (Succ == A)
64         return false;
65       if (Succ != B && Reachable.insert(Succ).second)
66         Stack.push_back(Succ);
67     }
68   } while (!Stack.empty());
69 
70   return true;
71 }
72 
73 } // namespace AMDGPU
74 
75 } // namespace llvm
76