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