[VPlan] Remove unused native utilities incompatible with nested regions.

[fhahn]

Summary

The implementations of VPlanDominatorTree, VPlanLoopInfo and VPlanPredicator
are all incompatible with modeling loops in VPlans as region without
explicit back-edges.

Those pieces are not actively used and only exercised by a few gtest
unit tests. They are at the moment blocking progress towards unifying
the native and inner-loop vectorizer paths in D121624 and D123005.

I think we should not block forward progress on unused pieces of code,
so this patch removes the utilities for now. The plan is to re-introduce
them as needed in a way that is compatible with the unified VPlan scheme
used in both the inner loop vectorizer and the native path.

[sguggill]

LGTM. Thanks Florian!

[fhahn]

Rebased, I am planning to commit this soon.

llvm/lib/Transforms/Vectorize/CMakeLists.txt

 add_llvm_component_library(LLVMVectorize
   LoadStoreVectorizer.cpp
   LoopVectorizationLegality.cpp
   LoopVectorize.cpp
   SLPVectorizer.cpp
   Vectorize.cpp
   VectorCombine.cpp
   VPlan.cpp
   VPlanHCFGBuilder.cpp
-  VPlanPredicator.cpp
   VPlanSLP.cpp
   VPlanTransforms.cpp
   VPlanVerifier.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/Vectorize
 

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

 #include "llvm/Transforms/Vectorize/LoopVectorize.h"
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define LV_NAME "loop-vectorize"
 #define DEBUG_TYPE LV_NAME
 
-extern cl::opt<bool> EnableVPlanPredication;
-
 static cl::opt<bool>
     EnableIfConversion("enable-if-conversion", cl::init(true), cl::Hidden,
                        cl::desc("Enable if-conversion during vectorization."));
 
 namespace llvm {
 cl::opt<bool>
     HintsAllowReordering("hints-allow-reordering", cl::init(true), cl::Hidden,
                          cl::desc("Allow enabling loop hints to reorder "
for (BasicBlock *BB : TheLoop->blocks()) {
     }
 
     // Check whether the BranchInst is a supported one. Only unconditional
     // branches, conditional branches with an outer loop invariant condition or
     // backedges are supported.
     // FIXME: We skip these checks when VPlan predication is enabled as we
     // want to allow divergent branches. This whole check will be removed
     // once VPlan predication is on by default.
-    if (!EnableVPlanPredication && Br && Br->isConditional() &&
+    if (Br && Br->isConditional() &&
         !TheLoop->isLoopInvariant(Br->getCondition()) &&
         !LI->isLoopHeader(Br->getSuccessor(0)) &&
         !LI->isLoopHeader(Br->getSuccessor(1))) {
       reportVectorizationFailure("Unsupported conditional branch",
           "loop control flow is not understood by vectorizer",
           "CFGNotUnderstood", ORE, TheLoop);
       if (DoExtraAnalysis)
         Result = false;

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Vectorize/LoopVectorize.h"
 #include "LoopVectorizationPlanner.h"
 #include "VPRecipeBuilder.h"
 #include "VPlan.h"
 #include "VPlanHCFGBuilder.h"
-#include "VPlanPredicator.h"
 #include "VPlanTransforms.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/None.h"
static cl::opt<bool> PreferPredicatedReductionSelect(
     cl::desc(
         "Prefer predicating a reduction operation over an after loop select."));
 
 cl::opt<bool> EnableVPlanNativePath(
     "enable-vplan-native-path", cl::init(false), cl::Hidden,
     cl::desc("Enable VPlan-native vectorization path with "
              "support for outer loop vectorization."));
 
-// FIXME: Remove this switch once we have divergence analysis. Currently we
-// assume divergent non-backedge branches when this switch is true.
-cl::opt<bool> EnableVPlanPredication(
-    "enable-vplan-predication", cl::init(false), cl::Hidden,
-    cl::desc("Enable VPlan-native vectorization path predicator with "
-             "support for outer loop vectorization."));
-
 // This flag enables the stress testing of the VPlan H-CFG construction in the
 // VPlan-native vectorization path. It must be used in conjuction with
 // -enable-vplan-native-path. -vplan-verify-hcfg can also be used to enable the
 // verification of the H-CFGs built.
 static cl::opt<bool> VPlanBuildStressTest(
     "vplan-build-stress-test", cl::init(false), cl::Hidden,
     cl::desc(
         "Build VPlan for every supported loop nest in the function and bail "
VPlanPtr LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
   // Build hierarchical CFG
   VPlanHCFGBuilder HCFGBuilder(OrigLoop, LI, *Plan);
   HCFGBuilder.buildHierarchicalCFG();
 
   for (ElementCount VF = Range.Start; ElementCount::isKnownLT(VF, Range.End);
        VF *= 2)
     Plan->addVF(VF);
 
-  if (EnableVPlanPredication) {
-    VPlanPredicator VPP(*Plan);
-    VPP.predicate();
-
-    // Avoid running transformation to recipes until masked code generation in
-    // VPlan-native path is in place.
-    return Plan;
-  }
-
   SmallPtrSet<Instruction *, 1> DeadInstructions;
   VPlanTransforms::VPInstructionsToVPRecipes(
       OrigLoop, Plan,
       [this](PHINode *P) { return Legal->getIntOrFpInductionDescriptor(P); },
       DeadInstructions, *PSE.getSE());
 
   // Update plan to be compatible with the inner loop vectorizer for
   // code-generation.
static bool processLoopInVPlanNativePath(
   CM.collectElementTypesForWidening();
 
   // Plan how to best vectorize, return the best VF and its cost.
   const VectorizationFactor VF = LVP.planInVPlanNativePath(UserVF);
 
   // If we are stress testing VPlan builds, do not attempt to generate vector
   // code. Masked vector code generation support will follow soon.
   // Also, do not attempt to vectorize if no vector code will be produced.
-  if (VPlanBuildStressTest || EnableVPlanPredication ||
-      VectorizationFactor::Disabled() == VF)
+  if (VPlanBuildStressTest || VectorizationFactor::Disabled() == VF)
     return false;
 
   VPlan &BestPlan = LVP.getBestPlanFor(VF.Width);
 
   {
     GeneratedRTChecks Checks(*PSE.getSE(), DT, LI,
                              F->getParent()->getDataLayout());
     InnerLoopVectorizer LB(L, PSE, LI, DT, TLI, TTI, AC, ORE, VF.Width, 1, LVL,

llvm/lib/Transforms/Vectorize/VPlan.h

 /// 6. The VPlanPrinter class providing a way to print a plan in dot format;
 /// These are documented in docs/VectorizationPlan.rst.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
 
-#include "VPlanLoopInfo.h"
 #include "VPlanValue.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/FMF.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <string>
 
class VPlan {
   /// Holds a mapping between Values and their corresponding VPValue inside
   /// VPlan.
   Value2VPValueTy Value2VPValue;
 
   /// Contains all VPValues that been allocated by addVPValue directly and need
   /// to be free when the plan's destructor is called.
   SmallVector<VPValue *, 16> VPValuesToFree;
 
-  /// Holds the VPLoopInfo analysis for this VPlan.
-  VPLoopInfo VPLInfo;
-
   /// Indicates whether it is safe use the Value2VPValue mapping or if the
   /// mapping cannot be used any longer, because it is stale.
   bool Value2VPValueEnabled = true;
 
   /// Values used outside the plan.
   MapVector<PHINode *, VPLiveOut *> LiveOuts;
 
 public:
public:
   }
 
   void removeVPValueFor(Value *V) {
     assert(Value2VPValueEnabled &&
            "IR value to VPValue mapping may be out of date!");
     Value2VPValue.erase(V);
   }
 
-  /// Return the VPLoopInfo analysis for this VPlan.
-  VPLoopInfo &getVPLoopInfo() { return VPLInfo; }
-  const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; }
-
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print this VPlan to \p O.
   void print(raw_ostream &O) const;
 
   /// Print this VPlan in DOT format to \p O.
   void printDOT(raw_ostream &O) const;
 
   /// Dump the plan to stderr (for debugging).
static VPBasicBlock *tryToMergeBlockIntoPredecessor(VPBlockBase *Block) {
     for (auto *Succ : Successors) {
       VPBlockUtils::disconnectBlocks(Block, Succ);
       VPBlockUtils::connectBlocks(PredVPBB, Succ);
     }
     delete Block;
     return PredVPBB;
   }
 
-  /// Returns true if the edge \p FromBlock -> \p ToBlock is a back-edge.
-  static bool isBackEdge(const VPBlockBase *FromBlock,
-                         const VPBlockBase *ToBlock, const VPLoopInfo *VPLI) {
-    assert(FromBlock->getParent() == ToBlock->getParent() &&
-           FromBlock->getParent() && "Must be in same region");
-    const VPLoop *FromLoop = VPLI->getLoopFor(FromBlock);
-    const VPLoop *ToLoop = VPLI->getLoopFor(ToBlock);
-    if (!FromLoop || !ToLoop || FromLoop != ToLoop)
-      return false;
-
-    // A back-edge is a branch from the loop latch to its header.
-    return ToLoop->isLoopLatch(FromBlock) && ToBlock == ToLoop->getHeader();
-  }
-
-  /// Returns true if \p Block is a loop latch
-  static bool blockIsLoopLatch(const VPBlockBase *Block,
-                               const VPLoopInfo *VPLInfo) {
-    if (const VPLoop *ParentVPL = VPLInfo->getLoopFor(Block))
-      return ParentVPL->isLoopLatch(Block);
-
-    return false;
-  }
-
-  /// Count and return the number of succesors of \p PredBlock excluding any
-  /// backedges.
-  static unsigned countSuccessorsNoBE(VPBlockBase *PredBlock,
-                                      VPLoopInfo *VPLI) {
-    unsigned Count = 0;
-    for (VPBlockBase *SuccBlock : PredBlock->getSuccessors()) {
-      if (!VPBlockUtils::isBackEdge(PredBlock, SuccBlock, VPLI))
-        Count++;
-    }
-    return Count;
-  }
-
   /// Return an iterator range over \p Range which only includes \p BlockTy
   /// blocks. The accesses are casted to \p BlockTy.
   template <typename BlockTy, typename T>
   static auto blocksOnly(const T &Range) {
     // Create BaseTy with correct const-ness based on BlockTy.
     using BaseTy =
         typename std::conditional<std::is_const<BlockTy>::value,
                                   const VPBlockBase, VPBlockBase>::type;

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

void VPlanHCFGBuilder::buildHierarchicalCFG() {
   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()));
-
-  // Compute VPLInfo and keep it in Plan.
-  VPLoopInfo &VPLInfo = Plan.getVPLoopInfo();
-  VPLInfo.analyze(VPDomTree);
-  LLVM_DEBUG(dbgs() << "VPLoop Info After buildPlainCFG:\n";
-             VPLInfo.print(dbgs()));
 }

llvm/lib/Transforms/Vectorize/VPlanLoopInfo.h

-//===-- VPLoopInfo.h --------------------------------------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-///
-/// \file
-/// This file defines VPLoopInfo analysis and VPLoop class. VPLoopInfo is a
-/// specialization of LoopInfoBase for VPBlockBase. VPLoops is a specialization
-/// of LoopBase that is used to hold loop metadata from VPLoopInfo. Further
-/// information can be found in VectorizationPlanner.rst.
-///
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLOOPINFO_H
-#define LLVM_TRANSFORMS_VECTORIZE_VPLOOPINFO_H
-
-#include "llvm/Analysis/LoopInfoImpl.h"
-
-namespace llvm {
-class VPBlockBase;
-
-/// Hold analysis information for every loop detected by VPLoopInfo. It is an
-/// instantiation of LoopBase.
-class VPLoop : public LoopBase<VPBlockBase, VPLoop> {
-private:
-  friend class LoopInfoBase<VPBlockBase, VPLoop>;
-  explicit VPLoop(VPBlockBase *VPB) : LoopBase<VPBlockBase, VPLoop>(VPB) {}
-};
-
-/// VPLoopInfo provides analysis of natural loop for VPBlockBase-based
-/// Hierarchical CFG. It is a specialization of LoopInfoBase class.
-// TODO: VPLoopInfo is initially computed on top of the VPlan plain CFG, which
-// is the same as the incoming IR CFG. If it's more efficient than running the
-// whole loop detection algorithm, we may want to create a mechanism to
-// translate LoopInfo into VPLoopInfo. However, that would require significant
-// changes in LoopInfoBase class.
-typedef LoopInfoBase<VPBlockBase, VPLoop> VPLoopInfo;
-
-} // namespace llvm
-
-#endif // LLVM_TRANSFORMS_VECTORIZE_VPLOOPINFO_H

llvm/lib/Transforms/Vectorize/VPlanPredicator.h

-//===-- VPlanPredicator.h ---------------------------------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-///
-/// \file
-/// This file defines the VPlanPredicator class which contains the public
-/// interfaces to predicate and linearize the VPlan region.
-///
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_PREDICATOR_H
-#define LLVM_TRANSFORMS_VECTORIZE_VPLAN_PREDICATOR_H
-
-#include "LoopVectorizationPlanner.h"
-#include "VPlanDominatorTree.h"
-#include "VPlanLoopInfo.h"
-#include <list>
-
-namespace llvm {
-class VPBasicBlock;
-class VPBlockBase;
-class VPRegionBlock;
-class VPValue;
-class VPlan;
-
-class VPlanPredicator {
-private:
-  enum class EdgeType {
-    TRUE_EDGE,
-    FALSE_EDGE,
-  };
-
-  // VPlan being predicated.
-  VPlan &Plan;
-
-  // VPLoopInfo for Plan's HCFG.
-  VPLoopInfo *VPLI;
-
-  // Dominator tree for Plan's HCFG.
-  VPDominatorTree VPDomTree;
-
-  // VPlan builder used to generate VPInstructions for block predicates.
-  VPBuilder Builder;
-
-  /// Get the type of edge from \p FromBlock to \p ToBlock. Returns TRUE_EDGE if
-  /// \p ToBlock is either the unconditional successor or the conditional true
-  /// successor of \p FromBlock and FALSE_EDGE otherwise.
-  EdgeType getEdgeTypeBetween(VPBlockBase *FromBlock, VPBlockBase *ToBlock);
-
-  /// Create and return VPValue corresponding to the predicate for the edge from
-  /// \p PredBB to \p CurrentBlock.
-  VPValue *getOrCreateNotPredicate(VPBasicBlock *PredBB, VPBasicBlock *CurrBB);
-
-  /// Generate and return the result of ORing all the predicate VPValues in \p
-  /// Worklist.
-  VPValue *genPredicateTree(std::list<VPValue *> &Worklist);
-
-  /// Create or propagate predicate for \p CurrBlock in region \p Region using
-  /// predicate(s) of its predecessor(s)
-  void createOrPropagatePredicates(VPBlockBase *CurrBlock,
-                                   VPRegionBlock *Region);
-
-  /// Predicate the CFG within \p Region.
-  void predicateRegionRec(VPRegionBlock *Region);
-
-  /// Linearize the CFG within \p Region.
-  void linearizeRegionRec(VPRegionBlock *Region);
-
-public:
-  VPlanPredicator(VPlan &Plan);
-
-  /// Predicate Plan's HCFG.
-  void predicate();
-};
-} // end namespace llvm
-#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_PREDICATOR_H

llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp

-//===-- VPlanPredicator.cpp -------------------------------------*- C++ -*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-///
-/// \file
-/// This file implements the VPlanPredicator class which contains the public
-/// interfaces to predicate and linearize the VPlan region.
-///
-//===----------------------------------------------------------------------===//
-
-#include "VPlanPredicator.h"
-#include "VPlan.h"
-#include "llvm/ADT/PostOrderIterator.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/raw_ostream.h"
-
-#define DEBUG_TYPE "VPlanPredicator"
-
-using namespace llvm;
-
-// Generate VPInstructions at the beginning of CurrBB that calculate the
-// predicate being propagated from PredBB to CurrBB depending on the edge type
-// between them. For example if:
-//  i.  PredBB is controlled by predicate %BP, and
-//  ii. The edge PredBB->CurrBB is the false edge, controlled by the condition
-//  bit value %CBV then this function will generate the following two
-//  VPInstructions at the start of CurrBB:
-//   %IntermediateVal = not %CBV
-//   %FinalVal        = and %BP %IntermediateVal
-// It returns %FinalVal.
-VPValue *VPlanPredicator::getOrCreateNotPredicate(VPBasicBlock *PredBB,
-                                                  VPBasicBlock *CurrBB) {
-  VPValue *CBV = PredBB->getCondBit();
-
-  // Set the intermediate value - this is either 'CBV', or 'not CBV'
-  // depending on the edge type.
-  EdgeType ET = getEdgeTypeBetween(PredBB, CurrBB);
-  VPValue *IntermediateVal = nullptr;
-  switch (ET) {
-  case EdgeType::TRUE_EDGE:
-    // CurrBB is the true successor of PredBB - nothing to do here.
-    IntermediateVal = CBV;
-    break;
-
-  case EdgeType::FALSE_EDGE:
-    // CurrBB is the False successor of PredBB - compute not of CBV.
-    IntermediateVal = Builder.createNot(CBV, {});
-    break;
-  }
-
-  // Now AND intermediate value with PredBB's block predicate if it has one.
-  VPValue *BP = PredBB->getPredicate();
-  if (BP)
-    return Builder.createAnd(BP, IntermediateVal, {});
-  else
-    return IntermediateVal;
-}
-
-// Generate a tree of ORs for all IncomingPredicates in  WorkList.
-// Note: This function destroys the original Worklist.
-//
-// P1 P2 P3 P4 P5
-//  \ /   \ /  /
-//  OR1   OR2 /
-//    \    | /
-//     \   +/-+
-//      \  /  |
-//       OR3  |
-//         \  |
-//          OR4 <- Returns this
-//           |
-//
-// The algorithm uses a worklist of predicates as its main data structure.
-// We pop a pair of values from the front (e.g. P1 and P2), generate an OR
-// (in this example OR1), and push it back. In this example the worklist
-// contains {P3, P4, P5, OR1}.
-// The process iterates until we have only one element in the Worklist (OR4).
-// The last element is the root predicate which is returned.
-VPValue *VPlanPredicator::genPredicateTree(std::list<VPValue *> &Worklist) {
-  if (Worklist.empty())
-    return nullptr;
-
-  // The worklist initially contains all the leaf nodes. Initialize the tree
-  // using them.
-  while (Worklist.size() >= 2) {
-    // Pop a pair of values from the front.
-    VPValue *LHS = Worklist.front();
-    Worklist.pop_front();
-    VPValue *RHS = Worklist.front();
-    Worklist.pop_front();
-
-    // Create an OR of these values.
-    VPValue *Or = Builder.createOr(LHS, RHS, {});
-
-    // Push OR to the back of the worklist.
-    Worklist.push_back(Or);
-  }
-
-  assert(Worklist.size() == 1 && "Expected 1 item in worklist");
-
-  // The root is the last node in the worklist.
-  VPValue *Root = Worklist.front();
-
-  // This root needs to replace the existing block predicate. This is done in
-  // the caller function.
-  return Root;
-}
-
-// Return whether the edge FromBlock -> ToBlock is a TRUE_EDGE or FALSE_EDGE
-VPlanPredicator::EdgeType
-VPlanPredicator::getEdgeTypeBetween(VPBlockBase *FromBlock,
-                                    VPBlockBase *ToBlock) {
-  unsigned Count = 0;
-  for (VPBlockBase *SuccBlock : FromBlock->getSuccessors()) {
-    if (SuccBlock == ToBlock) {
-      assert(Count < 2 && "Switch not supported currently");
-      return (Count == 0) ? EdgeType::TRUE_EDGE : EdgeType::FALSE_EDGE;
-    }
-    Count++;
-  }
-
-  llvm_unreachable("Broken getEdgeTypeBetween");
-}
-
-// Generate all predicates needed for CurrBlock by going through its immediate
-// predecessor blocks.
-void VPlanPredicator::createOrPropagatePredicates(VPBlockBase *CurrBlock,
-                                                  VPRegionBlock *Region) {
-  // Blocks that dominate region exiting inherit the predicate from the region.
-  // Return after setting the predicate.
-  if (VPDomTree.dominates(CurrBlock, Region->getExiting())) {
-    VPValue *RegionBP = Region->getPredicate();
-    CurrBlock->setPredicate(RegionBP);
-    return;
-  }
-
-  // Collect all incoming predicates in a worklist.
-  std::list<VPValue *> IncomingPredicates;
-
-  // Set the builder's insertion point to the top of the current BB
-  VPBasicBlock *CurrBB = cast<VPBasicBlock>(CurrBlock->getEntryBasicBlock());
-  Builder.setInsertPoint(CurrBB, CurrBB->begin());
-
-  // For each predecessor, generate the VPInstructions required for
-  // computing 'BP AND (not) CBV" at the top of CurrBB.
-  // Collect the outcome of this calculation for all predecessors
-  // into IncomingPredicates.
-  for (VPBlockBase *PredBlock : CurrBlock->getPredecessors()) {
-    // Skip back-edges
-    if (VPBlockUtils::isBackEdge(PredBlock, CurrBlock, VPLI))
-      continue;
-
-    VPValue *IncomingPredicate = nullptr;
-    unsigned NumPredSuccsNoBE =
-        VPBlockUtils::countSuccessorsNoBE(PredBlock, VPLI);
-
-    // If there is an unconditional branch to the currBB, then we don't create
-    // edge predicates. We use the predecessor's block predicate instead.
-    if (NumPredSuccsNoBE == 1)
-      IncomingPredicate = PredBlock->getPredicate();
-    else if (NumPredSuccsNoBE == 2) {
-      // Emit recipes into CurrBlock if required
-      assert(isa<VPBasicBlock>(PredBlock) && "Only BBs have multiple exits");
-      IncomingPredicate =
-          getOrCreateNotPredicate(cast<VPBasicBlock>(PredBlock), CurrBB);
-    } else
-      llvm_unreachable("FIXME: switch statement ?");
-
-    if (IncomingPredicate)
-      IncomingPredicates.push_back(IncomingPredicate);
-  }
-
-  // Logically OR all incoming predicates by building the Predicate Tree.
-  VPValue *Predicate = genPredicateTree(IncomingPredicates);
-
-  // Now update the block's predicate with the new one.
-  CurrBlock->setPredicate(Predicate);
-}
-
-// Generate all predicates needed for Region.
-void VPlanPredicator::predicateRegionRec(VPRegionBlock *Region) {
-  VPBasicBlock *EntryBlock = cast<VPBasicBlock>(Region->getEntry());
-  ReversePostOrderTraversal<VPBlockBase *> RPOT(EntryBlock);
-
-  // Generate edge predicates and append them to the block predicate. RPO is
-  // necessary since the predecessor blocks' block predicate needs to be set
-  // before the current block's block predicate can be computed.
-  for (VPBlockBase *Block : RPOT) {
-    // TODO: Handle nested regions once we start generating the same.
-    assert(!isa<VPRegionBlock>(Block) && "Nested region not expected");
-    createOrPropagatePredicates(Block, Region);
-  }
-}
-
-// Linearize the CFG within Region.
-// TODO: Predication and linearization need RPOT for every region.
-// This traversal is expensive. Since predication is not adding new
-// blocks, we should be able to compute RPOT once in predication and
-// reuse it here. This becomes even more important once we have nested
-// regions.
-void VPlanPredicator::linearizeRegionRec(VPRegionBlock *Region) {
-  ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
-  VPBlockBase *PrevBlock = nullptr;
-
-  for (VPBlockBase *CurrBlock : RPOT) {
-    // TODO: Handle nested regions once we start generating the same.
-    assert(!isa<VPRegionBlock>(CurrBlock) && "Nested region not expected");
-
-    // Linearize control flow by adding an unconditional edge between PrevBlock
-    // and CurrBlock skipping loop headers and latches to keep intact loop
-    // header predecessors and loop latch successors.
-    if (PrevBlock && !VPLI->isLoopHeader(CurrBlock) &&
-        !VPBlockUtils::blockIsLoopLatch(PrevBlock, VPLI)) {
-
-      LLVM_DEBUG(dbgs() << "Linearizing: " << PrevBlock->getName() << "->"
-                        << CurrBlock->getName() << "\n");
-
-      PrevBlock->clearSuccessors();
-      CurrBlock->clearPredecessors();
-      VPBlockUtils::connectBlocks(PrevBlock, CurrBlock);
-    }
-
-    PrevBlock = CurrBlock;
-  }
-}
-
-// Entry point. The driver function for the predicator.
-void VPlanPredicator::predicate() {
-  // Predicate the blocks within Region.
-  predicateRegionRec(cast<VPRegionBlock>(Plan.getEntry()));
-
-  // Linearlize the blocks with Region.
-  linearizeRegionRec(cast<VPRegionBlock>(Plan.getEntry()));
-}
-
-VPlanPredicator::VPlanPredicator(VPlan &Plan)
-    : Plan(Plan), VPLI(&(Plan.getVPLoopInfo())) {
-  // FIXME: Predicator is currently computing the dominator information for the
-  // top region. Once we start storing dominator information in a VPRegionBlock,
-  // we can avoid this recalculation.
-  VPDomTree.recalculate(*(cast<VPRegionBlock>(Plan.getEntry())));
-}

llvm/unittests/Transforms/Vectorize/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   Core
   Vectorize
   AsmParser
   )
 
 add_llvm_unittest(VectorizeTests
-  VPlanDominatorTreeTest.cpp
-  VPlanLoopInfoTest.cpp
-  VPlanPredicatorTest.cpp
   VPlanTest.cpp
   VPlanHCFGTest.cpp
   VPlanSlpTest.cpp
   )
 
 set_property(TARGET VectorizeTests PROPERTY FOLDER "Tests/UnitTests/TransformsTests")

llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp

-//===- llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp -----===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#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

llvm/unittests/Transforms/Vectorize/VPlanLoopInfoTest.cpp

-//===- llvm/unittests/Transforms/Vectorize/VPlanLoopInfoTest.cpp -----===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "../lib/Transforms/Vectorize/VPlanLoopInfo.h"
-#include "VPlanTestBase.h"
-#include "gtest/gtest.h"
-
-namespace llvm {
-namespace {
-
-class VPlanLoopInfo : public VPlanTestBase {};
-
-TEST_F(VPlanLoopInfo, BasicLoopInfoTest) {
-  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 = buildHCFG(LoopHeader);
-
-  // Build VPlan domination tree and loop info analyses.
-  VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
-  VPDominatorTree VPDT;
-  VPDT.recalculate(*TopRegion);
-  VPLoopInfo VPLI;
-  VPLI.analyze(VPDT);
-
-  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];
-
-  // Number of loops.
-  EXPECT_EQ(1, std::distance(VPLI.begin(), VPLI.end()));
-  VPLoop *VPLp = *VPLI.begin();
-
-  // VPBBs contained in VPLoop.
-  EXPECT_FALSE(VPLp->contains(PH));
-  EXPECT_EQ(nullptr, VPLI.getLoopFor(PH));
-  EXPECT_TRUE(VPLp->contains(H));
-  EXPECT_EQ(VPLp, VPLI.getLoopFor(H));
-  EXPECT_TRUE(VPLp->contains(IfThen));
-  EXPECT_EQ(VPLp, VPLI.getLoopFor(IfThen));
-  EXPECT_TRUE(VPLp->contains(IfElse));
-  EXPECT_EQ(VPLp, VPLI.getLoopFor(IfElse));
-  EXPECT_TRUE(VPLp->contains(Latch));
-  EXPECT_EQ(VPLp, VPLI.getLoopFor(Latch));
-  EXPECT_FALSE(VPLp->contains(Exit));
-  EXPECT_EQ(nullptr, VPLI.getLoopFor(Exit));
-
-  // VPLoop's parts.
-  EXPECT_EQ(PH, VPLp->getLoopPreheader());
-  EXPECT_EQ(H, VPLp->getHeader());
-  EXPECT_EQ(Latch, VPLp->getLoopLatch());
-  EXPECT_EQ(Latch, VPLp->getExitingBlock());
-  EXPECT_EQ(Exit, VPLp->getExitBlock());
-}
-} // namespace
-} // namespace llvm

llvm/unittests/Transforms/Vectorize/VPlanPredicatorTest.cpp

-//===- llvm/unittests/Transforms/Vectorize/VPlanPredicatorTest.cpp -----===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#include "../lib/Transforms/Vectorize/VPlanPredicator.h"
-#include "VPlanTestBase.h"
-#include "gtest/gtest.h"
-
-namespace llvm {
-namespace {
-
-class VPlanPredicatorTest : public VPlanTestBase {};
-
-TEST_F(VPlanPredicatorTest, BasicPredicatorTest) {
-  const char *ModuleString =
-      "@arr = common global [8 x [8 x i64]] "
-      "zeroinitializer, align 16\n"
-      "@arr2 = common global [8 x [8 x i64]] "
-      "zeroinitializer, align 16\n"
-      "@arr3 = common global [8 x [8 x i64]] "
-      "zeroinitializer, align 16\n"
-      "define void @f(i64 %n1) {\n"
-      "entry:\n"
-      "  br label %for.cond1.preheader\n"
-      "for.cond1.preheader:                              \n"
-      "  %i1.029 = phi i64 [ 0, %entry ], [ %inc14, %for.inc13 ]\n"
-      "  br label %for.body3\n"
-      "for.body3:                                        \n"
-      "  %i2.028 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.inc ]\n"
-      "  %arrayidx4 = getelementptr inbounds [8 x [8 x i64]], [8 x [8 x i64]]* "
-      "@arr, i64 0, i64 %i2.028, i64 %i1.029\n"
-      "  %0 = load i64, i64* %arrayidx4, align 8\n"
-      "  %cmp5 = icmp ugt i64 %0, 10\n"
-      "  br i1 %cmp5, label %if.then, label %for.inc\n"
-      "if.then:                                          \n"
-      "  %arrayidx7 = getelementptr inbounds [8 x [8 x i64]], [8 x [8 x i64]]* "
-      "@arr2, i64 0, i64 %i2.028, i64 %i1.029\n"
-      "  %1 = load i64, i64* %arrayidx7, align 8\n"
-      "  %cmp8 = icmp ugt i64 %1, 100\n"
-      "  br i1 %cmp8, label %if.then9, label %for.inc\n"
-      "if.then9:                                         \n"
-      "  %add = add nuw nsw i64 %i2.028, %i1.029\n"
-      "  %arrayidx11 = getelementptr inbounds [8 x [8 x i64]], [8 x [8 x "
-      "i64]]* @arr3, i64 0, i64 %i2.028, i64 %i1.029\n"
-      "  store i64 %add, i64* %arrayidx11, align 8\n"
-      "  br label %for.inc\n"
-      "for.inc:                                          \n"
-      "  %inc = add nuw nsw i64 %i2.028, 1\n"
-      "  %exitcond = icmp eq i64 %inc, 8\n"
-      "  br i1 %exitcond, label %for.inc13, label %for.body3\n"
-      "for.inc13:                                        \n"
-      "  %inc14 = add nuw nsw i64 %i1.029, 1\n"
-      "  %exitcond30 = icmp eq i64 %inc14, 8\n"
-      "  br i1 %exitcond30, label %for.end15, label %for.cond1.preheader\n"
-      "for.end15:                                        \n"
-      "  ret void\n"
-      "}\n";
-
-  Module &M = parseModule(ModuleString);
-
-  Function *F = M.getFunction("f");
-  BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
-  auto Plan = buildHCFG(LoopHeader);
-
-  VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
-  VPBlockBase *PH = TopRegion->getEntry();
-  VPBlockBase *H = PH->getSingleSuccessor();
-  VPBlockBase *InnerLoopH = H->getSingleSuccessor();
-  VPBlockBase *OuterIf = InnerLoopH->getSuccessors()[0];
-  VPBlockBase *InnerLoopLatch = InnerLoopH->getSuccessors()[1];
-  VPBlockBase *InnerIf = OuterIf->getSuccessors()[0];
-  VPValue *CBV1 = InnerLoopH->getCondBit();
-  VPValue *CBV2 = OuterIf->getCondBit();
-
-  // Apply predication.
-  VPlanPredicator VPP(*Plan);
-  VPP.predicate();
-
-  VPBlockBase *InnerLoopLinSucc = InnerLoopH->getSingleSuccessor();
-  VPBlockBase *OuterIfLinSucc = OuterIf->getSingleSuccessor();
-  VPBlockBase *InnerIfLinSucc = InnerIf->getSingleSuccessor();
-  VPValue *OuterIfPred = OuterIf->getPredicate();
-  VPInstruction *InnerAnd =
-      cast<VPInstruction>(InnerIf->getEntryBasicBlock()->begin());
-  VPValue *InnerIfPred = InnerIf->getPredicate();
-
-  // Test block predicates
-  EXPECT_NE(nullptr, CBV1);
-  EXPECT_NE(nullptr, CBV2);
-  EXPECT_NE(nullptr, InnerAnd);
-  EXPECT_EQ(CBV1, OuterIfPred);
-  EXPECT_EQ(InnerAnd->getOpcode(), Instruction::And);
-  EXPECT_EQ(InnerAnd->getOperand(0), CBV1);
-  EXPECT_EQ(InnerAnd->getOperand(1), CBV2);
-  EXPECT_EQ(InnerIfPred, InnerAnd);
-
-  // Test Linearization
-  EXPECT_EQ(InnerLoopLinSucc, OuterIf);
-  EXPECT_EQ(OuterIfLinSucc, InnerIf);
-  EXPECT_EQ(InnerIfLinSucc, InnerLoopLatch);
-
-  // Check that the containing VPlan is set correctly.
-  EXPECT_EQ(&*Plan, InnerLoopLinSucc->getPlan());
-  EXPECT_EQ(&*Plan, OuterIfLinSucc->getPlan());
-  EXPECT_EQ(&*Plan, InnerIfLinSucc->getPlan());
-  EXPECT_EQ(&*Plan, InnerIf->getPlan());
-  EXPECT_EQ(&*Plan, InnerLoopLatch->getPlan());
-}
-
-// Test generation of Not and Or during predication.
-TEST_F(VPlanPredicatorTest, PredicatorNegOrTest) {
-  const char *ModuleString =
-      "@arr = common global [100 x [100 x i32]] zeroinitializer, align 16\n"
-      "@arr2 = common global [100 x [100 x i32]] zeroinitializer, align 16\n"
-      "@arr3 = common global [100 x [100 x i32]] zeroinitializer, align 16\n"
-      "define void @foo() {\n"
-      "entry:\n"
-      "  br label %for.cond1.preheader\n"
-      "for.cond1.preheader:                              \n"
-      "  %indvars.iv42 = phi i64 [ 0, %entry ], [ %indvars.iv.next43, "
-      "%for.inc22 ]\n"
-      "  br label %for.body3\n"
-      "for.body3:                                        \n"
-      "  %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ "
-      "%indvars.iv.next, %if.end21 ]\n"
-      "  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 "
-      "x i32]]* @arr, i64 0, i64 %indvars.iv, i64 %indvars.iv42\n"
-      "  %0 = load i32, i32* %arrayidx5, align 4\n"
-      "  %cmp6 = icmp slt i32 %0, 100\n"
-      "  br i1 %cmp6, label %if.then, label %if.end21\n"
-      "if.then:                                          \n"
-      "  %cmp7 = icmp sgt i32 %0, 10\n"
-      "  br i1 %cmp7, label %if.then8, label %if.else\n"
-      "if.then8:                                         \n"
-      "  %add = add nsw i32 %0, 10\n"
-      "  %arrayidx12 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 "
-      "x i32]]* @arr2, i64 0, i64 %indvars.iv, i64 %indvars.iv42\n"
-      "  store i32 %add, i32* %arrayidx12, align 4\n"
-      "  br label %if.end\n"
-      "if.else:                                          \n"
-      "  %sub = add nsw i32 %0, -10\n"
-      "  %arrayidx16 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 "
-      "x i32]]* @arr3, i64 0, i64 %indvars.iv, i64 %indvars.iv42\n"
-      "  store i32 %sub, i32* %arrayidx16, align 4\n"
-      "  br label %if.end\n"
-      "if.end:                                           \n"
-      "  store i32 222, i32* %arrayidx5, align 4\n"
-      "  br label %if.end21\n"
-      "if.end21:                                         \n"
-      "  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n"
-      "  %exitcond = icmp eq i64 %indvars.iv.next, 100\n"
-      "  br i1 %exitcond, label %for.inc22, label %for.body3\n"
-      "for.inc22:                                        \n"
-      "  %indvars.iv.next43 = add nuw nsw i64 %indvars.iv42, 1\n"
-      "  %exitcond44 = icmp eq i64 %indvars.iv.next43, 100\n"
-      "  br i1 %exitcond44, label %for.end24, label %for.cond1.preheader\n"
-      "for.end24:                                        \n"
-      "  ret void\n"
-      "}\n";
-
-  Module &M = parseModule(ModuleString);
-  Function *F = M.getFunction("foo");
-  BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
-  auto Plan = buildHCFG(LoopHeader);
-
-  VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
-  VPBlockBase *PH = TopRegion->getEntry();
-  VPBlockBase *H = PH->getSingleSuccessor();
-  VPBlockBase *OuterIfCmpBlk = H->getSingleSuccessor();
-  VPBlockBase *InnerIfCmpBlk = OuterIfCmpBlk->getSuccessors()[0];
-  VPBlockBase *InnerIfTSucc = InnerIfCmpBlk->getSuccessors()[0];
-  VPBlockBase *InnerIfFSucc = InnerIfCmpBlk->getSuccessors()[1];
-  VPBlockBase *TSuccSucc = InnerIfTSucc->getSingleSuccessor();
-  VPBlockBase *FSuccSucc = InnerIfFSucc->getSingleSuccessor();
-
-  VPValue *OuterCBV = OuterIfCmpBlk->getCondBit();
-  VPValue *InnerCBV = InnerIfCmpBlk->getCondBit();
-
-  // Apply predication.
-  VPlanPredicator VPP(*Plan);
-  VPP.predicate();
-
-  VPInstruction *And =
-      cast<VPInstruction>(InnerIfTSucc->getEntryBasicBlock()->begin());
-  VPInstruction *Not =
-      cast<VPInstruction>(InnerIfFSucc->getEntryBasicBlock()->begin());
-  VPInstruction *NotAnd = cast<VPInstruction>(
-      &*std::next(InnerIfFSucc->getEntryBasicBlock()->begin(), 1));
-  VPInstruction *Or =
-      cast<VPInstruction>(TSuccSucc->getEntryBasicBlock()->begin());
-
-  // Test block predicates
-  EXPECT_NE(nullptr, OuterCBV);
-  EXPECT_NE(nullptr, InnerCBV);
-  EXPECT_NE(nullptr, And);
-  EXPECT_NE(nullptr, Not);
-  EXPECT_NE(nullptr, NotAnd);
-
-  EXPECT_EQ(And->getOpcode(), Instruction::And);
-  EXPECT_EQ(NotAnd->getOpcode(), Instruction::And);
-  EXPECT_EQ(Not->getOpcode(), VPInstruction::Not);
-
-  EXPECT_EQ(And->getOperand(0), OuterCBV);
-  EXPECT_EQ(And->getOperand(1), InnerCBV);
-
-  EXPECT_EQ(Not->getOperand(0), InnerCBV);
-
-  EXPECT_EQ(NotAnd->getOperand(0), OuterCBV);
-  EXPECT_EQ(NotAnd->getOperand(1), Not);
-
-  EXPECT_EQ(InnerIfTSucc->getPredicate(), And);
-  EXPECT_EQ(InnerIfFSucc->getPredicate(), NotAnd);
-
-  EXPECT_EQ(TSuccSucc, FSuccSucc);
-  EXPECT_EQ(Or->getOpcode(), Instruction::Or);
-  EXPECT_EQ(TSuccSucc->getPredicate(), Or);
-
-  // Test operands of the Or - account for differences in predecessor block
-  // ordering.
-  VPInstruction *OrOp0Inst = cast<VPInstruction>(Or->getOperand(0));
-  VPInstruction *OrOp1Inst = cast<VPInstruction>(Or->getOperand(1));
-
-  bool ValidOrOperands = false;
-  if (((OrOp0Inst == And) && (OrOp1Inst == NotAnd)) ||
-      ((OrOp0Inst == NotAnd) && (OrOp1Inst == And)))
-    ValidOrOperands = true;
-
-  EXPECT_TRUE(ValidOrOperands);
-}
-
-} // namespace
-} // namespace llvm

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

 //===- llvm/unittests/Transforms/Vectorize/VPlanTest.cpp - VPlan tests ----===//
 //
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "../lib/Transforms/Vectorize/VPlan.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "gtest/gtest.h"
 #include <string>
 
 namespace llvm {
 namespace {