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