Home | History | Annotate | Download | only in Vectorize 
      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 }
    134