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(llvm::is_contained(SuccPreds, VPB) && "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(llvm::is_contained(PredSuccs, VPB) && "Missing successor link."); 88 (void)PredSuccs; 89 } 90 } 91 } 92 93 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested 94 /// VPBlockBases. Do not recurse inside nested VPRegionBlocks. 95 static void verifyRegion(const VPRegionBlock *Region) { 96 const VPBlockBase *Entry = Region->getEntry(); 97 const VPBlockBase *Exit = Region->getExit(); 98 99 // Entry and Exit shouldn't have any predecessor/successor, respectively. 100 assert(!Entry->getNumPredecessors() && "Region entry has predecessors."); 101 assert(!Exit->getNumSuccessors() && "Region exit has successors."); 102 (void)Entry; 103 (void)Exit; 104 105 verifyBlocksInRegion(Region); 106 } 107 108 /// Verify the CFG invariants of VPRegionBlock \p Region and its nested 109 /// VPBlockBases. Recurse inside nested VPRegionBlocks. 110 static void verifyRegionRec(const VPRegionBlock *Region) { 111 verifyRegion(Region); 112 113 // Recurse inside nested regions. 114 for (const VPBlockBase *VPB : 115 make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()), 116 df_iterator<const VPBlockBase *>::end(Region->getExit()))) { 117 if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB)) 118 verifyRegionRec(SubRegion); 119 } 120 } 121 122 void VPlanVerifier::verifyHierarchicalCFG( 123 const VPRegionBlock *TopRegion) const { 124 if (!EnableHCFGVerifier) 125 return; 126 127 LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n"); 128 assert(!TopRegion->getParent() && "VPlan Top Region should have no parent."); 129 verifyRegionRec(TopRegion); 130 } 131