contrib/llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

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