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 #include "llvm/Support/CommandLine.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