summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/lib/Transforms/Vectorize/LoopVectorize.cpp4
-rw-r--r--llvm/lib/Transforms/Vectorize/VPlan.cpp5
-rw-r--r--llvm/lib/Transforms/Vectorize/VPlan.h105
-rw-r--r--llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h41
-rw-r--r--llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp15
-rw-r--r--llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h23
-rw-r--r--llvm/unittests/Transforms/Vectorize/CMakeLists.txt1
-rw-r--r--llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp196
-rw-r--r--llvm/unittests/Transforms/Vectorize/VPlanTestBase.h15
9 files changed, 382 insertions, 23 deletions
diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
index 348d1e4d75c..859d0c92ca5 100644
--- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
+++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -7060,8 +7060,8 @@ LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
auto Plan = llvm::make_unique<VPlan>();
// Build hierarchical CFG
- VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI);
- HCFGBuilder.buildHierarchicalCFG(*Plan.get());
+ VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI, *Plan);
+ HCFGBuilder.buildHierarchicalCFG();
return Plan;
}
diff --git a/llvm/lib/Transforms/Vectorize/VPlan.cpp b/llvm/lib/Transforms/Vectorize/VPlan.cpp
index f7b07b722bb..0780e70809d 100644
--- a/llvm/lib/Transforms/Vectorize/VPlan.cpp
+++ b/llvm/lib/Transforms/Vectorize/VPlan.cpp
@@ -18,6 +18,7 @@
//===----------------------------------------------------------------------===//
#include "VPlan.h"
+#include "VPlanDominatorTree.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SmallVector.h"
@@ -25,7 +26,6 @@
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
-#include "llvm/IR/Dominators.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
@@ -34,6 +34,7 @@
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/GenericDomTreeConstruction.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
@@ -576,3 +577,5 @@ void VPWidenMemoryInstructionRecipe::print(raw_ostream &O,
}
O << "\\l\"";
}
+
+template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
diff --git a/llvm/lib/Transforms/Vectorize/VPlan.h b/llvm/lib/Transforms/Vectorize/VPlan.h
index 866951cb79a..193d7a90621 100644
--- a/llvm/lib/Transforms/Vectorize/VPlan.h
+++ b/llvm/lib/Transforms/Vectorize/VPlan.h
@@ -28,6 +28,7 @@
#include "VPlanValue.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallPtrSet.h"
@@ -516,6 +517,16 @@ public:
/// Delete all blocks reachable from a given VPBlockBase, inclusive.
static void deleteCFG(VPBlockBase *Entry);
+
+ void printAsOperand(raw_ostream &OS, bool PrintType) const {
+ OS << getName();
+ }
+
+ void print(raw_ostream &OS) const {
+ // TODO: Only printing VPBB name for now since we only have dot printing
+ // support for VPInstructions/Recipes.
+ printAsOperand(OS, false);
+ }
};
/// VPRecipeBase is a base class modeling a sequence of one or more output IR
@@ -1037,6 +1048,12 @@ public:
EntryBlock->setParent(this);
}
+ // FIXME: DominatorTreeBase is doing 'A->getParent()->front()'. 'front' is a
+ // specific interface of llvm::Function, instead of using
+ // GraphTraints::getEntryNode. We should add a new template parameter to
+ // DominatorTreeBase representing the Graph type.
+ VPBlockBase &front() const { return *Entry; }
+
const VPBlockBase *getExit() const { return Exit; }
VPBlockBase *getExit() { return Exit; }
@@ -1210,12 +1227,15 @@ inline raw_ostream &operator<<(raw_ostream &OS, VPlan &Plan) {
return OS;
}
-//===--------------------------------------------------------------------===//
-// GraphTraits specializations for VPlan/VPRegionBlock Control-Flow Graphs //
-//===--------------------------------------------------------------------===//
+//===----------------------------------------------------------------------===//
+// GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs //
+//===----------------------------------------------------------------------===//
-// Provide specializations of GraphTraits to be able to treat a VPBlockBase as a
-// graph of VPBlockBase nodes...
+// The following set of template specializations implement GraphTraits to treat
+// any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
+// that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
+// VPBlockBase is a VPRegionBlock, this specialization provides access to its
+// successors/predecessors but not to the blocks inside the region.
template <> struct GraphTraits<VPBlockBase *> {
using NodeRef = VPBlockBase *;
@@ -1247,17 +1267,13 @@ template <> struct GraphTraits<const VPBlockBase *> {
}
};
-// Provide specializations of GraphTraits to be able to treat a VPBlockBase as a
-// graph of VPBlockBase nodes... and to walk it in inverse order. Inverse order
-// for a VPBlockBase is considered to be when traversing the predecessors of a
-// VPBlockBase instead of its successors.
+// Inverse order specialization for VPBasicBlocks. Predecessors are used instead
+// of successors for the inverse traversal.
template <> struct GraphTraits<Inverse<VPBlockBase *>> {
using NodeRef = VPBlockBase *;
using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
- static Inverse<VPBlockBase *> getEntryNode(Inverse<VPBlockBase *> B) {
- return B;
- }
+ static NodeRef getEntryNode(Inverse<NodeRef> B) { return B.Graph; }
static inline ChildIteratorType child_begin(NodeRef N) {
return N->getPredecessors().begin();
@@ -1268,6 +1284,71 @@ template <> struct GraphTraits<Inverse<VPBlockBase *>> {
}
};
+// The following set of template specializations implement GraphTraits to
+// treat VPRegionBlock as a graph and recurse inside its nodes. It's important
+// to note that the blocks inside the VPRegionBlock are treated as VPBlockBases
+// (i.e., no dyn_cast is performed, VPBlockBases specialization is used), so
+// there won't be automatic recursion into other VPBlockBases that turn to be
+// VPRegionBlocks.
+
+template <>
+struct GraphTraits<VPRegionBlock *> : public GraphTraits<VPBlockBase *> {
+ using GraphRef = VPRegionBlock *;
+ using nodes_iterator = df_iterator<NodeRef>;
+
+ static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
+
+ static nodes_iterator nodes_begin(GraphRef N) {
+ return nodes_iterator::begin(N->getEntry());
+ }
+
+ static nodes_iterator nodes_end(GraphRef N) {
+ // df_iterator::end() returns an empty iterator so the node used doesn't
+ // matter.
+ return nodes_iterator::end(N);
+ }
+};
+
+template <>
+struct GraphTraits<const VPRegionBlock *>
+ : public GraphTraits<const VPBlockBase *> {
+ using GraphRef = const VPRegionBlock *;
+ using nodes_iterator = df_iterator<NodeRef>;
+
+ static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
+
+ static nodes_iterator nodes_begin(GraphRef N) {
+ return nodes_iterator::begin(N->getEntry());
+ }
+
+ static nodes_iterator nodes_end(GraphRef N) {
+ // df_iterator::end() returns an empty iterator so the node used doesn't
+ // matter.
+ return nodes_iterator::end(N);
+ }
+};
+
+template <>
+struct GraphTraits<Inverse<VPRegionBlock *>>
+ : public GraphTraits<Inverse<VPBlockBase *>> {
+ using GraphRef = VPRegionBlock *;
+ using nodes_iterator = df_iterator<NodeRef>;
+
+ static NodeRef getEntryNode(Inverse<GraphRef> N) {
+ return N.Graph->getExit();
+ }
+
+ static nodes_iterator nodes_begin(GraphRef N) {
+ return nodes_iterator::begin(N->getExit());
+ }
+
+ static nodes_iterator nodes_end(GraphRef N) {
+ // df_iterator::end() returns an empty iterator so the node used doesn't
+ // matter.
+ return nodes_iterator::end(N);
+ }
+};
+
//===----------------------------------------------------------------------===//
// VPlan Utilities
//===----------------------------------------------------------------------===//
diff --git a/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h b/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
new file mode 100644
index 00000000000..1b81097b6d3
--- /dev/null
+++ b/llvm/lib/Transforms/Vectorize/VPlanDominatorTree.h
@@ -0,0 +1,41 @@
+//===-- VPlanDominatorTree.h ------------------------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file implements dominator tree analysis for a single level of a VPlan's
+/// H-CFG.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H
+#define LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H
+
+#include "VPlan.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/IR/Dominators.h"
+
+namespace llvm {
+
+/// Template specialization of the standard LLVM dominator tree utility for
+/// VPBlockBases.
+using VPDominatorTree = DomTreeBase<VPBlockBase>;
+
+using VPDomTreeNode = DomTreeNodeBase<VPBlockBase>;
+
+/// Template specializations of GraphTraits for VPDomTreeNode.
+template <>
+struct GraphTraits<VPDomTreeNode *>
+ : public DomTreeGraphTraitsBase<VPDomTreeNode, VPDomTreeNode::iterator> {};
+
+template <>
+struct GraphTraits<const VPDomTreeNode *>
+ : public DomTreeGraphTraitsBase<const VPDomTreeNode,
+ VPDomTreeNode::const_iterator> {};
+} // namespace llvm
+#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANDOMINATORTREE_H
diff --git a/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp b/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
index 08129b74cdd..26e112e02db 100644
--- a/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
+++ b/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
@@ -324,13 +324,22 @@ VPRegionBlock *PlainCFGBuilder::buildPlainCFG() {
return TopRegion;
}
+VPRegionBlock *VPlanHCFGBuilder::buildPlainCFG() {
+ PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
+ return PCFGBuilder.buildPlainCFG();
+}
+
// Public interface to build a H-CFG.
-void VPlanHCFGBuilder::buildHierarchicalCFG(VPlan &Plan) {
+void VPlanHCFGBuilder::buildHierarchicalCFG() {
// Build Top Region enclosing the plain CFG and set it as VPlan entry.
- PlainCFGBuilder PCFGBuilder(TheLoop, LI, Plan);
- VPRegionBlock *TopRegion = PCFGBuilder.buildPlainCFG();
+ VPRegionBlock *TopRegion = buildPlainCFG();
Plan.setEntry(TopRegion);
LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
Verifier.verifyHierarchicalCFG(TopRegion);
+
+ // Compute plain CFG dom tree for VPLInfo.
+ VPDomTree.recalculate(*TopRegion);
+ LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
+ VPDomTree.print(dbgs()));
}
diff --git a/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h b/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h
index c4e69843615..3f11dcb5164 100644
--- a/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h
+++ b/llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.h
@@ -26,14 +26,18 @@
#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VPLANHCFGBUILDER_H
#include "VPlan.h"
+#include "VPlanDominatorTree.h"
#include "VPlanVerifier.h"
namespace llvm {
class Loop;
+class VPlanTestBase;
/// Main class to build the VPlan H-CFG for an incoming IR.
class VPlanHCFGBuilder {
+ friend VPlanTestBase;
+
private:
// The outermost loop of the input loop nest considered for vectorization.
Loop *TheLoop;
@@ -41,14 +45,27 @@ private:
// Loop Info analysis.
LoopInfo *LI;
+ // The VPlan that will contain the H-CFG we are building.
+ VPlan &Plan;
+
// VPlan verifier utility.
VPlanVerifier Verifier;
+ // Dominator analysis for VPlan plain CFG to be used in the
+ // construction of the H-CFG. This analysis is no longer valid once regions
+ // are introduced.
+ VPDominatorTree VPDomTree;
+
+ /// Build plain CFG for TheLoop. Return a new VPRegionBlock (TopRegion)
+ /// enclosing the plain CFG.
+ VPRegionBlock *buildPlainCFG();
+
public:
- VPlanHCFGBuilder(Loop *Lp, LoopInfo *LI) : TheLoop(Lp), LI(LI) {}
+ VPlanHCFGBuilder(Loop *Lp, LoopInfo *LI, VPlan &P)
+ : TheLoop(Lp), LI(LI), Plan(P) {}
- /// Build H-CFG for TheLoop and update \p Plan accordingly.
- void buildHierarchicalCFG(VPlan &Plan);
+ /// Build H-CFG for TheLoop and update Plan accordingly.
+ void buildHierarchicalCFG();
};
} // namespace llvm
diff --git a/llvm/unittests/Transforms/Vectorize/CMakeLists.txt b/llvm/unittests/Transforms/Vectorize/CMakeLists.txt
index 4f2b8e9a139..e4e8fa677a7 100644
--- a/llvm/unittests/Transforms/Vectorize/CMakeLists.txt
+++ b/llvm/unittests/Transforms/Vectorize/CMakeLists.txt
@@ -6,6 +6,7 @@ set(LLVM_LINK_COMPONENTS
)
add_llvm_unittest(VectorizeTests
+ VPlanDominatorTreeTest.cpp
VPlanTest.cpp
VPlanHCFGTest.cpp
)
diff --git a/llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp b/llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp
new file mode 100644
index 00000000000..57f07392d8b
--- /dev/null
+++ b/llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp
@@ -0,0 +1,196 @@
+//===- llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp -----===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../lib/Transforms/Vectorize/VPlanHCFGBuilder.h"
+#include "VPlanTestBase.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace {
+
+class VPlanDominatorTreeTest : public VPlanTestBase {};
+
+TEST_F(VPlanDominatorTreeTest, BasicVPBBDomination) {
+ const char *ModuleString =
+ "define void @f(i32* %a, i32* %b, i32* %c, i32 %N, i32 %M, i32 %K) {\n"
+ "entry:\n"
+ " br label %for.body\n"
+ "for.body:\n"
+ " %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.inc ]\n"
+ " br i1 true, label %if.then, label %if.else\n"
+ "if.then:\n"
+ " br label %for.inc\n"
+ "if.else:\n"
+ " br label %for.inc\n"
+ "for.inc:\n"
+ " %iv.next = add nuw nsw i64 %iv, 1\n"
+ " %exitcond = icmp eq i64 %iv.next, 300\n"
+ " br i1 %exitcond, label %for.end, label %for.body\n"
+ "for.end:\n"
+ " ret void\n"
+ "}\n";
+
+ Module &M = parseModule(ModuleString);
+
+ Function *F = M.getFunction("f");
+ BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
+ auto Plan = buildPlainCFG(LoopHeader);
+
+ // Build VPlan domination tree analysis.
+ VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
+ VPDominatorTree VPDT;
+ VPDT.recalculate(*TopRegion);
+
+ VPBlockBase *PH = TopRegion->getEntry();
+ VPBlockBase *H = PH->getSingleSuccessor();
+ VPBlockBase *IfThen = H->getSuccessors()[0];
+ VPBlockBase *IfElse = H->getSuccessors()[1];
+ VPBlockBase *Latch = IfThen->getSingleSuccessor();
+ VPBlockBase *Exit = Latch->getSuccessors()[0] != H
+ ? Latch->getSuccessors()[0]
+ : Latch->getSuccessors()[1];
+ // Reachability.
+ EXPECT_TRUE(VPDT.isReachableFromEntry(PH));
+ EXPECT_TRUE(VPDT.isReachableFromEntry(H));
+ EXPECT_TRUE(VPDT.isReachableFromEntry(IfThen));
+ EXPECT_TRUE(VPDT.isReachableFromEntry(IfElse));
+ EXPECT_TRUE(VPDT.isReachableFromEntry(Latch));
+ EXPECT_TRUE(VPDT.isReachableFromEntry(Exit));
+
+ // VPBB dominance.
+ EXPECT_TRUE(VPDT.dominates(PH, PH));
+ EXPECT_TRUE(VPDT.dominates(PH, H));
+ EXPECT_TRUE(VPDT.dominates(PH, IfThen));
+ EXPECT_TRUE(VPDT.dominates(PH, IfElse));
+ EXPECT_TRUE(VPDT.dominates(PH, Latch));
+ EXPECT_TRUE(VPDT.dominates(PH, Exit));
+
+ EXPECT_FALSE(VPDT.dominates(H, PH));
+ EXPECT_TRUE(VPDT.dominates(H, H));
+ EXPECT_TRUE(VPDT.dominates(H, IfThen));
+ EXPECT_TRUE(VPDT.dominates(H, IfElse));
+ EXPECT_TRUE(VPDT.dominates(H, Latch));
+ EXPECT_TRUE(VPDT.dominates(H, Exit));
+
+ EXPECT_FALSE(VPDT.dominates(IfThen, PH));
+ EXPECT_FALSE(VPDT.dominates(IfThen, H));
+ EXPECT_TRUE(VPDT.dominates(IfThen, IfThen));
+ EXPECT_FALSE(VPDT.dominates(IfThen, IfElse));
+ EXPECT_FALSE(VPDT.dominates(IfThen, Latch));
+ EXPECT_FALSE(VPDT.dominates(IfThen, Exit));
+
+ EXPECT_FALSE(VPDT.dominates(IfElse, PH));
+ EXPECT_FALSE(VPDT.dominates(IfElse, H));
+ EXPECT_FALSE(VPDT.dominates(IfElse, IfThen));
+ EXPECT_TRUE(VPDT.dominates(IfElse, IfElse));
+ EXPECT_FALSE(VPDT.dominates(IfElse, Latch));
+ EXPECT_FALSE(VPDT.dominates(IfElse, Exit));
+
+ EXPECT_FALSE(VPDT.dominates(Latch, PH));
+ EXPECT_FALSE(VPDT.dominates(Latch, H));
+ EXPECT_FALSE(VPDT.dominates(Latch, IfThen));
+ EXPECT_FALSE(VPDT.dominates(Latch, IfElse));
+ EXPECT_TRUE(VPDT.dominates(Latch, Latch));
+ EXPECT_TRUE(VPDT.dominates(Latch, Exit));
+
+ EXPECT_FALSE(VPDT.dominates(Exit, PH));
+ EXPECT_FALSE(VPDT.dominates(Exit, H));
+ EXPECT_FALSE(VPDT.dominates(Exit, IfThen));
+ EXPECT_FALSE(VPDT.dominates(Exit, IfElse));
+ EXPECT_FALSE(VPDT.dominates(Exit, Latch));
+ EXPECT_TRUE(VPDT.dominates(Exit, Exit));
+
+ // VPBB proper dominance.
+ EXPECT_FALSE(VPDT.properlyDominates(PH, PH));
+ EXPECT_TRUE(VPDT.properlyDominates(PH, H));
+ EXPECT_TRUE(VPDT.properlyDominates(PH, IfThen));
+ EXPECT_TRUE(VPDT.properlyDominates(PH, IfElse));
+ EXPECT_TRUE(VPDT.properlyDominates(PH, Latch));
+ EXPECT_TRUE(VPDT.properlyDominates(PH, Exit));
+
+ EXPECT_FALSE(VPDT.properlyDominates(H, PH));
+ EXPECT_FALSE(VPDT.properlyDominates(H, H));
+ EXPECT_TRUE(VPDT.properlyDominates(H, IfThen));
+ EXPECT_TRUE(VPDT.properlyDominates(H, IfElse));
+ EXPECT_TRUE(VPDT.properlyDominates(H, Latch));
+ EXPECT_TRUE(VPDT.properlyDominates(H, Exit));
+
+ EXPECT_FALSE(VPDT.properlyDominates(IfThen, PH));
+ EXPECT_FALSE(VPDT.properlyDominates(IfThen, H));
+ EXPECT_FALSE(VPDT.properlyDominates(IfThen, IfThen));
+ EXPECT_FALSE(VPDT.properlyDominates(IfThen, IfElse));
+ EXPECT_FALSE(VPDT.properlyDominates(IfThen, Latch));
+ EXPECT_FALSE(VPDT.properlyDominates(IfThen, Exit));
+
+ EXPECT_FALSE(VPDT.properlyDominates(IfElse, PH));
+ EXPECT_FALSE(VPDT.properlyDominates(IfElse, H));
+ EXPECT_FALSE(VPDT.properlyDominates(IfElse, IfThen));
+ EXPECT_FALSE(VPDT.properlyDominates(IfElse, IfElse));
+ EXPECT_FALSE(VPDT.properlyDominates(IfElse, Latch));
+ EXPECT_FALSE(VPDT.properlyDominates(IfElse, Exit));
+
+ EXPECT_FALSE(VPDT.properlyDominates(Latch, PH));
+ EXPECT_FALSE(VPDT.properlyDominates(Latch, H));
+ EXPECT_FALSE(VPDT.properlyDominates(Latch, IfThen));
+ EXPECT_FALSE(VPDT.properlyDominates(Latch, IfElse));
+ EXPECT_FALSE(VPDT.properlyDominates(Latch, Latch));
+ EXPECT_TRUE(VPDT.properlyDominates(Latch, Exit));
+
+ EXPECT_FALSE(VPDT.properlyDominates(Exit, PH));
+ EXPECT_FALSE(VPDT.properlyDominates(Exit, H));
+ EXPECT_FALSE(VPDT.properlyDominates(Exit, IfThen));
+ EXPECT_FALSE(VPDT.properlyDominates(Exit, IfElse));
+ EXPECT_FALSE(VPDT.properlyDominates(Exit, Latch));
+ EXPECT_FALSE(VPDT.properlyDominates(Exit, Exit));
+
+ // VPBB nearest common dominator.
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, PH));
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, H));
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, IfThen));
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, IfElse));
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, Latch));
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, Exit));
+
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(H, PH));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, H));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, IfThen));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, IfElse));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, Latch));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, Exit));
+
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(IfThen, PH));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, H));
+ EXPECT_EQ(IfThen, VPDT.findNearestCommonDominator(IfThen, IfThen));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, IfElse));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, Latch));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, Exit));
+
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(IfElse, PH));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, H));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, IfThen));
+ EXPECT_EQ(IfElse, VPDT.findNearestCommonDominator(IfElse, IfElse));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, Latch));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, Exit));
+
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(Latch, PH));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, H));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, IfThen));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, IfElse));
+ EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Latch, Latch));
+ EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Latch, Exit));
+
+ EXPECT_EQ(PH, VPDT.findNearestCommonDominator(Exit, PH));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, H));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, IfThen));
+ EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, IfElse));
+ EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Exit, Latch));
+ EXPECT_EQ(Exit, VPDT.findNearestCommonDominator(Exit, Exit));
+}
+} // namespace
+} // namespace llvm
diff --git a/llvm/unittests/Transforms/Vectorize/VPlanTestBase.h b/llvm/unittests/Transforms/Vectorize/VPlanTestBase.h
index da3b39f4df0..0fc4a9a21c8 100644
--- a/llvm/unittests/Transforms/Vectorize/VPlanTestBase.h
+++ b/llvm/unittests/Transforms/Vectorize/VPlanTestBase.h
@@ -50,8 +50,19 @@ protected:
doAnalysis(*LoopHeader->getParent());
auto Plan = llvm::make_unique<VPlan>();
- VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get());
- HCFGBuilder.buildHierarchicalCFG(*Plan.get());
+ VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get(), *Plan);
+ HCFGBuilder.buildHierarchicalCFG();
+ return Plan;
+ }
+
+ /// Build the VPlan plain CFG for the loop starting from \p LoopHeader.
+ VPlanPtr buildPlainCFG(BasicBlock *LoopHeader) {
+ doAnalysis(*LoopHeader->getParent());
+
+ auto Plan = llvm::make_unique<VPlan>();
+ VPlanHCFGBuilder HCFGBuilder(LI->getLoopFor(LoopHeader), LI.get(), *Plan);
+ VPRegionBlock *TopRegion = HCFGBuilder.buildPlainCFG();
+ Plan->setEntry(TopRegion);
return Plan;
}
};
OpenPOWER on IntegriCloud