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 } 133