lib/Transforms/Vectorize/VPlanVerifier.cpp

   1 //===-- VPlanVerifier.cpp -------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// \file
  10 /// This file defines the class VPlanVerifier, which contains utility functions
  11 /// to check the consistency and invariants of a VPlan.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "VPlanVerifier.h"
  16 #include "llvm/ADT/DepthFirstIterator.h"
  17
  18 #define DEBUG_TYPE "loop-vectorize"
  19
  20 using namespace llvm;
  21
  22 static cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false),
  23                                         cl::Hidden,
  24                                         cl::desc("Verify VPlan H-CFG."));
  25
  26 #ifndef NDEBUG
  27 /// Utility function that checks whether \p VPBlockVec has duplicate
  28 /// VPBlockBases.
  29 static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
  30   SmallDenseSet<const VPBlockBase *, 8> VPBlockSet;
  31   for (const auto *Block : VPBlockVec) {
  32     if (VPBlockSet.count(Block))
  33       return true;
  34     VPBlockSet.insert(Block);
  35   }
  36   return false;
  37 }
  38 #endif
  39
  40 /// Helper function that verifies the CFG invariants of the VPBlockBases within
  41 /// \p Region. Checks in this function are generic for VPBlockBases. They are
  42 /// not specific for VPBasicBlocks or VPRegionBlocks.
  43 static void verifyBlocksInRegion(const VPRegionBlock *Region) {
  44   for (const VPBlockBase *VPB :
  45        make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
  46                   df_iterator<const VPBlockBase *>::end(Region->getExit()))) {
  47     // Check block's parent.
  48     assert(VPB->getParent() == Region && "VPBlockBase has wrong parent");
  49
  50     // Check block's condition bit.
  51     if (VPB->getNumSuccessors() > 1)
  52       assert(VPB->getCondBit() && "Missing condition bit!");
  53     else
  54       assert(!VPB->getCondBit() && "Unexpected condition bit!");
  55
  56     // Check block's successors.
  57     const auto &Successors = VPB->getSuccessors();
  58     // There must be only one instance of a successor in block's successor list.
  59     // TODO: This won't work for switch statements.
  60     assert(!hasDuplicates(Successors) &&
  61            "Multiple instances of the same successor.");
  62
  63     for (const VPBlockBase *Succ : Successors) {
  64       // There must be a bi-directional link between block and successor.
  65       const auto &SuccPreds = Succ->getPredecessors();
  66       assert(std::find(SuccPreds.begin(), SuccPreds.end(), VPB) !=
  67                  SuccPreds.end() &&
  68              "Missing predecessor link.");
  69       (void)SuccPreds;
  70     }
  71
  72     // Check block's predecessors.
  73     const auto &Predecessors = VPB->getPredecessors();
  74     // There must be only one instance of a predecessor in block's predecessor
  75     // list.
  76     // TODO: This won't work for switch statements.
  77     assert(!hasDuplicates(Predecessors) &&
  78            "Multiple instances of the same predecessor.");
  79
  80     for (const VPBlockBase *Pred : Predecessors) {
  81       // Block and predecessor must be inside the same region.
  82       assert(Pred->getParent() == VPB->getParent() &&
  83              "Predecessor is not in the same region.");
  84
  85       // There must be a bi-directional link between block and predecessor.
  86       const auto &PredSuccs = Pred->getSuccessors();
  87       assert(std::find(PredSuccs.begin(), PredSuccs.end(), VPB) !=
  88                  PredSuccs.end() &&
  89              "Missing successor link.");
  90       (void)PredSuccs;
  91     }
  92   }
  93 }
  94
  95 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
  96 /// VPBlockBases. Do not recurse inside nested VPRegionBlocks.
  97 static void verifyRegion(const VPRegionBlock *Region) {
  98   const VPBlockBase *Entry = Region->getEntry();
  99   const VPBlockBase *Exit = Region->getExit();
 100
 101   // Entry and Exit shouldn't have any predecessor/successor, respectively.
 102   assert(!Entry->getNumPredecessors() && "Region entry has predecessors.");
 103   assert(!Exit->getNumSuccessors() && "Region exit has successors.");
 104   (void)Entry;
 105   (void)Exit;
 106
 107   verifyBlocksInRegion(Region);
 108 }
 109
 110 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested
 111 /// VPBlockBases. Recurse inside nested VPRegionBlocks.
 112 static void verifyRegionRec(const VPRegionBlock *Region) {
 113   verifyRegion(Region);
 114
 115   // Recurse inside nested regions.
 116   for (const VPBlockBase *VPB :
 117        make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
 118                   df_iterator<const VPBlockBase *>::end(Region->getExit()))) {
 119     if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB))
 120       verifyRegionRec(SubRegion);
 121   }
 122 }
 123
 124 void VPlanVerifier::verifyHierarchicalCFG(
 125     const VPRegionBlock *TopRegion) const {
 126   if (!EnableHCFGVerifier)
 127     return;
 128
 129   LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
 130   assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");
 131   verifyRegionRec(TopRegion);
 132 }