| //===-- 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 |