From eb7311ffb126282c9b131b2fa3d541eb0f0321ca Mon Sep 17 00:00:00 2001 From: Nicolai Haehnle Date: Wed, 4 Apr 2018 10:58:15 +0000 Subject: StructurizeCFG: Test for branch divergence correctly Fixes cases like the new test @nonuniform. In that test, %cc itself is a uniform value; however, when reading it after the end of the loop in basic block %if, its value is effectively non-uniform, so the branch is non-uniform. This problem was encountered in https://bugs.freedesktop.org/show_bug.cgi?id=103743; however, this change in itself is not sufficient to fix that bug, as there is another issue in the AMDGPU backend. As discovered after committing an earlier version of this change, this exposes a subtle interaction between this pass and DivergenceAnalysis: since we remove and re-create branch instructions, we can no longer rely on DivergenceAnalysis for branches in subregions that were already processed by the pass. Explicitly remove branch instructions from DivergenceAnalysis to avoid dangling pointers as a matter of defensive programming, and change how we detect non-uniform subregions. Change-Id: I32bbffece4a32f686fab54964dae1a5dd72949d4 Differential Revision: https://reviews.llvm.org/D43743 llvm-svn: 329165 --- llvm/lib/Transforms/Scalar/StructurizeCFG.cpp | 67 +++++++++++++++++++++------ 1 file changed, 54 insertions(+), 13 deletions(-) (limited to 'llvm/lib/Transforms') diff --git a/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp b/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp index 7e4177c3507..b54a92325c4 100644 --- a/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp +++ b/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp @@ -56,6 +56,12 @@ static const char *const FlowBlockName = "Flow"; namespace { +static cl::opt ForceSkipUniformRegions( + "structurizecfg-skip-uniform-regions", + cl::Hidden, + cl::desc("Force whether the StructurizeCFG pass skips uniform regions"), + cl::init(false)); + // Definition of the complex types used in this pass. using BBValuePair = std::pair; @@ -177,6 +183,7 @@ class StructurizeCFG : public RegionPass { Function *Func; Region *ParentRegion; + DivergenceAnalysis *DA; DominatorTree *DT; LoopInfo *LI; @@ -243,8 +250,11 @@ class StructurizeCFG : public RegionPass { public: static char ID; - explicit StructurizeCFG(bool SkipUniformRegions = false) - : RegionPass(ID), SkipUniformRegions(SkipUniformRegions) { + explicit StructurizeCFG(bool SkipUniformRegions_ = false) + : RegionPass(ID), + SkipUniformRegions(SkipUniformRegions_) { + if (ForceSkipUniformRegions.getNumOccurrences()) + SkipUniformRegions = ForceSkipUniformRegions.getValue(); initializeStructurizeCFGPass(*PassRegistry::getPassRegistry()); } @@ -612,6 +622,8 @@ void StructurizeCFG::killTerminator(BasicBlock *BB) { SI != SE; ++SI) delPhiValues(BB, *SI); + if (DA) + DA->removeValue(Term); Term->eraseFromParent(); } @@ -879,16 +891,37 @@ void StructurizeCFG::rebuildSSA() { } } -static bool hasOnlyUniformBranches(const Region *R, +static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID, const DivergenceAnalysis &DA) { - for (const BasicBlock *BB : R->blocks()) { - const BranchInst *Br = dyn_cast(BB->getTerminator()); - if (!Br || !Br->isConditional()) - continue; + for (auto E : R->elements()) { + if (!E->isSubRegion()) { + auto Br = dyn_cast(E->getEntry()->getTerminator()); + if (!Br || !Br->isConditional()) + continue; - if (!DA.isUniform(Br->getCondition())) - return false; - DEBUG(dbgs() << "BB: " << BB->getName() << " has uniform terminator\n"); + if (!DA.isUniform(Br)) + return false; + DEBUG(dbgs() << "BB: " << Br->getParent()->getName() + << " has uniform terminator\n"); + } else { + // Explicitly refuse to treat regions as uniform if they have non-uniform + // subregions. We cannot rely on DivergenceAnalysis for branches in + // subregions because those branches may have been removed and re-created, + // so we look for our metadata instead. + // + // Warning: It would be nice to treat regions as uniform based only on + // their direct child basic blocks' terminators, regardless of whether + // subregions are uniform or not. However, this requires a very careful + // look at SIAnnotateControlFlow to make sure nothing breaks there. + for (auto BB : E->getNodeAs()->blocks()) { + auto Br = dyn_cast(BB->getTerminator()); + if (!Br || !Br->isConditional()) + continue; + + if (!Br->getMetadata(UniformMDKindID)) + return false; + } + } } return true; } @@ -898,10 +931,18 @@ bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { if (R->isTopLevelRegion()) return false; + DA = nullptr; + if (SkipUniformRegions) { // TODO: We could probably be smarter here with how we handle sub-regions. - auto &DA = getAnalysis(); - if (hasOnlyUniformBranches(R, DA)) { + // 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"); + DA = &getAnalysis(); + + if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) { DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R << '\n'); // Mark all direct child block terminators as having been treated as @@ -914,7 +955,7 @@ bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { continue; if (Instruction *Term = E->getEntry()->getTerminator()) - Term->setMetadata("structurizecfg.uniform", MD); + Term->setMetadata(UniformMDKindID, MD); } return false; -- cgit v1.2.3