contrib/llvm/lib/Target/AMDGPU/Utils/AMDGPULaneDominator.cpp

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