Line data    Source code

       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.
      52          41 : 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          41 :   Stack.push_back(A);
      58             :   do {
      59         105 :     MachineBasicBlock *MBB = Stack.back();
      60             :     Stack.pop_back();
      61             : 
      62         228 :     for (MachineBasicBlock *Succ : MBB->successors()) {
      63         123 :       if (Succ == A)
      64           0 :         return false;
      65         200 :       if (Succ != B && Reachable.insert(Succ).second)
      66          64 :         Stack.push_back(Succ);
      67             :     }
      68         105 :   } while (!Stack.empty());
      69             : 
      70             :   return true;
      71             : }
      72             : 
      73             : } // namespace AMDGPU
      74             : 
      75             : } // namespace llvm