StructurizeCFG: Add an option for skipping regions with only uniform branches

[• tstellarAMD]

Summary

Tests for this will be added once the AMDGPU backend enables this
option.

[arsenm]

lib/Transforms/Scalar/StructurizeCFG.cpp

264 ↗

(On Diff #46050)

This should not be a required analysis. Even with the false option, it will force running the analysis. I think if the target pass config explicitly adds the analysis pass before StructurizeCFG it should work

[arsenm]

Do we need to worry about updating the DivergenceAnalysis as the control flow is changed in the non-uniform regions? Sometimes it introduces new xor instructions which won't be in DA's value map.

[• tstellarAMD]

Only require DivergenceAnalysis when skipping uniform regions is enabled.

[• tstellarAMD]

In D16602#340002, @arsenm wrote:

Do we need to worry about updating the DivergenceAnalysis as the control flow is changed in the non-uniform regions? Sometimes it introduces new xor instructions which won't be in DA's value map.

I don't think this would be a problem, because we don't use the DivergenceAnalysis any more, once we have started to structurize a region.

lib/Transforms/Scalar/StructurizeCFG.cpp

264 ↗

(On Diff #47285)

Explicitly adding DivergenceAnalysis in TargetPassConfig doesn't seem to work, so I've made DivergenceAnalysis required only when SkipUniformRegions is true.

[arsenm]

LGTM

llvm/trunk/include/llvm/Transforms/Scalar.h

 // parallel-and and parallel-or mode, etc...
 //
 FunctionPass *createFlattenCFGPass();
 
 //===----------------------------------------------------------------------===//
 //
 // CFG Structurization - Remove irreducible control flow
 //
-Pass *createStructurizeCFGPass();
+///
+/// When \p SkipUniformRegions is true the structizer will not structurize
+/// regions that only contain uniform branches.
+Pass *createStructurizeCFGPass(bool SkipUniformRegions = false);
 
 //===----------------------------------------------------------------------===//
 //
 // BreakCriticalEdges - Break all of the critical edges in the CFG by inserting
 // a dummy basic block. This pass may be "required" by passes that cannot deal
 // with critical edges. For this usage, a pass must call:
 //
 //   AU.addRequiredID(BreakCriticalEdgesID);

llvm/trunk/lib/Transforms/Scalar/StructurizeCFG.cpp

 //===-- StructurizeCFG.cpp ------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SCCIterator.h"
+#include "llvm/Analysis/DivergenceAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/RegionPass.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"

 /// |
 /// \endverbatim
 ///
 /// The back edge of the "Flow" block is always on the false side of the branch
 /// while the true side continues the general flow. So the loop condition
 /// consist of a network of PHI nodes where the true incoming values expresses
 /// breaks and the false values expresses continue states.
 class StructurizeCFG : public RegionPass {
+  bool SkipUniformRegions;
+  DivergenceAnalysis *DA;
+
   Type *Boolean;
   ConstantInt *BoolTrue;
   ConstantInt *BoolFalse;
   UndefValue *BoolUndef;
 
   Function *Func;
   Region *ParentRegion;
 
class StructurizeCFG : public RegionPass {
   void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd);
 
   void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd);
 
   void createFlow();
 
   void rebuildSSA();
 
+  bool hasOnlyUniformBranches(const Region *R);
+
 public:
   static char ID;
 
   StructurizeCFG() :
     RegionPass(ID) {
     initializeStructurizeCFGPass(*PassRegistry::getPassRegistry());
   }
 
+  StructurizeCFG(bool SkipUniformRegions) :
+    RegionPass(ID), SkipUniformRegions(SkipUniformRegions) {
+    initializeStructurizeCFGPass(*PassRegistry::getPassRegistry());
+  }
+
   using Pass::doInitialization;
   bool doInitialization(Region *R, RGPassManager &RGM) override;
 
   bool runOnRegion(Region *R, RGPassManager &RGM) override;
 
   const char *getPassName() const override {
     return "Structurize control flow";
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    if (SkipUniformRegions)
+      AU.addRequired<DivergenceAnalysis>();
     AU.addRequiredID(LowerSwitchID);
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     RegionPass::getAnalysisUsage(AU);
   }
 };
 
 } // end anonymous namespace
 
 char StructurizeCFG::ID = 0;
 
 INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG",
                       false, false)
+INITIALIZE_PASS_DEPENDENCY(DivergenceAnalysis)
 INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)
 INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG",
                     false, false)
 
 /// \brief Initialize the types and constants used in the pass
 bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
for (BasicBlock::iterator II = BB->begin(), IE = BB->end();
           Updater.AddAvailableValue(BB, &*II);
           Initialized = true;
         }
         Updater.RewriteUseAfterInsertions(U);
       }
     }
 }
 
+bool StructurizeCFG::hasOnlyUniformBranches(const Region *R) {
+  for (const BasicBlock *BB : R->blocks()) {
+    const BranchInst *Br = dyn_cast<BranchInst>(BB->getTerminator());
+    if (!Br || !Br->isConditional())
+      continue;
+
+    if (!DA->isUniform(Br->getCondition()))
+      return false;
+    DEBUG(dbgs() << "BB: " << BB->getName() << " has uniform terminator\n");
+  }
+  return true;
+}
+
 /// \brief Run the transformation for each region found
 bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
   if (R->isTopLevelRegion())
     return false;
 
+  if (SkipUniformRegions) {
+    DA = &getAnalysis<DivergenceAnalysis>();
+    // TODO: We could probably be smarter here with how we handle sub-regions.
+    if (hasOnlyUniformBranches(R)) {
+      DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R << '\n');
+      return false;
+    }
+  }
+
   Func = R->getEntry()->getParent();
   ParentRegion = R;
 
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 
   orderNodes();
   collectInfos();
bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
   Conditions.clear();
   Loops.clear();
   LoopPreds.clear();
   LoopConds.clear();
 
   return true;
 }
 
-/// \brief Create the pass
-Pass *llvm::createStructurizeCFGPass() {
-  return new StructurizeCFG();
+Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
+  return new StructurizeCFG(SkipUniformRegions);
 }