[StructurizeCFG] Use UniformityAnalysis instead of DivergenceAnalysis

[Pierre-vh]

Summary

Depends on D145572

[foad]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

802

Does UA need something like removeValue? I see it was added by @nhaehnle in D43743 "to avoid dangling pointers as a matter of defensive programming".

[Pierre-vh]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

802

I'm not too familiar with UA's implementation so I can't answer this, @sameerds does UA need anything like this?

[sameerds]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

802

Yeah, given the defensive nature of the comment, I thought we should put this in UA. But turns out that we don't really need to, because UA does not store pointers to terminator instructions. The side-effect of the structurizer is to delete and recreate terminators, but in the UA, a query on a terminator is actually done by looking up its parent basic block.

Also noteable is that only LegacyDA implemented this "remove" API. Although legacy DA acts as a wrapper to the newer DA, this particular function was never implemented in the latter.

In short, I think we don't need to implement this in UA.

[sameerds]

Quite possibly the scariest test of UA so far! I am definitely ducking behind a vibranium shield!

[foad]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

802

Sounds good, thanks for explaining!

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/InstructionSimplify.h"
-#include "llvm/Analysis/LegacyDivergenceAnalysis.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/RegionPass.h"
+#include "llvm/Analysis/UniformityAnalysis.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
class StructurizeCFG {
   Type *Boolean;
   ConstantInt *BoolTrue;
   ConstantInt *BoolFalse;
   UndefValue *BoolUndef;
 
   Function *Func;
   Region *ParentRegion;
 
-  LegacyDivergenceAnalysis *DA = nullptr;
+  UniformityInfo *UA = nullptr;
   DominatorTree *DT;
 
   SmallVector<RegionNode *, 8> Order;
   BBSet Visited;
   BBSet FlowSet;
 
   SmallVector<WeakVH, 8> AffectedPhis;
   BBPhiMap DeletedPhis;
class StructurizeCFG {
 
   void createFlow();
 
   void rebuildSSA();
 
 public:
   void init(Region *R);
   bool run(Region *R, DominatorTree *DT);
-  bool makeUniformRegion(Region *R, LegacyDivergenceAnalysis *DA);
+  bool makeUniformRegion(Region *R, UniformityInfo &UA);
 };
 
 class StructurizeCFGLegacyPass : public RegionPass {
   bool SkipUniformRegions;
 
 public:
   static char ID;
 
   explicit StructurizeCFGLegacyPass(bool SkipUniformRegions_ = false)
       : RegionPass(ID), SkipUniformRegions(SkipUniformRegions_) {
     if (ForceSkipUniformRegions.getNumOccurrences())
       SkipUniformRegions = ForceSkipUniformRegions.getValue();
     initializeStructurizeCFGLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnRegion(Region *R, RGPassManager &RGM) override {
     StructurizeCFG SCFG;
     SCFG.init(R);
     if (SkipUniformRegions) {
-      LegacyDivergenceAnalysis *DA = &getAnalysis<LegacyDivergenceAnalysis>();
-      if (SCFG.makeUniformRegion(R, DA))
+      UniformityInfo &UA =
+          getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo();
+      if (SCFG.makeUniformRegion(R, UA))
         return false;
     }
     DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     return SCFG.run(R, DT);
   }
 
   StringRef getPassName() const override { return "Structurize control flow"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     if (SkipUniformRegions)
-      AU.addRequired<LegacyDivergenceAnalysis>();
+      AU.addRequired<UniformityInfoWrapperPass>();
     AU.addRequiredID(LowerSwitchID);
     AU.addRequired<DominatorTreeWrapperPass>();
 
     AU.addPreserved<DominatorTreeWrapperPass>();
     RegionPass::getAnalysisUsage(AU);
   }
 };
 

 void StructurizeCFG::killTerminator(BasicBlock *BB) {
   Instruction *Term = BB->getTerminator();
   if (!Term)
     return;
 
   for (BasicBlock *Succ : successors(BB))
     delPhiValues(BB, Succ);
 
-  if (DA)
-    DA->removeValue(Term);
   Term->eraseFromParent();
 }
 
 /// Let node exit(s) point to NewExit
 void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
                                 bool IncludeDominator) {
   if (Node->isSubRegion()) {
     Region *SubRegion = Node->getNodeAs<Region>();
for (Instruction &I : *BB) {
           Initialized = true;
         }
         Updater.RewriteUseAfterInsertions(U);
       }
     }
 }
 
 static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID,
-                                   const LegacyDivergenceAnalysis &DA) {
+                                   const UniformityInfo &UA) {
   // Bool for if all sub-regions are uniform.
   bool SubRegionsAreUniform = true;
   // Count of how many direct children are conditional.
   unsigned ConditionalDirectChildren = 0;
 
   for (auto *E : R->elements()) {
     if (!E->isSubRegion()) {
       auto Br = dyn_cast<BranchInst>(E->getEntry()->getTerminator());
       if (!Br || !Br->isConditional())
         continue;
 
-      if (!DA.isUniform(Br))
+      if (!UA.isUniform(Br))
         return false;
 
       // One of our direct children is conditional.
       ConditionalDirectChildren++;
 
       LLVM_DEBUG(dbgs() << "BB: " << Br->getParent()->getName()
                         << " has uniform terminator\n");
     } else {

 void StructurizeCFG::init(Region *R) {
   LLVMContext &Context = R->getEntry()->getContext();
 
   Boolean = Type::getInt1Ty(Context);
   BoolTrue = ConstantInt::getTrue(Context);
   BoolFalse = ConstantInt::getFalse(Context);
   BoolUndef = UndefValue::get(Boolean);
 
-  this->DA = nullptr;
+  this->UA = nullptr;
 }
 
-bool StructurizeCFG::makeUniformRegion(Region *R,
-                                       LegacyDivergenceAnalysis *DA) {
+bool StructurizeCFG::makeUniformRegion(Region *R, UniformityInfo &UA) {
   if (R->isTopLevelRegion())
     return false;
 
-  this->DA = DA;
+  this->UA = &UA;
+
   // TODO: We could probably be smarter here with how we handle sub-regions.
   // We currently rely on the fact that metadata is set by earlier invocations
   // of the pass on sub-regions, and that this metadata doesn't get lost --
   // but we shouldn't rely on metadata for correctness!
   unsigned UniformMDKindID =
       R->getEntry()->getContext().getMDKindID("structurizecfg.uniform");
 
-  if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) {
+  if (hasOnlyUniformBranches(R, UniformMDKindID, UA)) {
     LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R
                       << '\n');
 
     // Mark all direct child block terminators as having been treated as
     // uniform. To account for a possible future in which non-uniform
     // sub-regions are treated more cleverly, indirect children are not
     // marked as uniform.
     MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {});