VPlanVerifier.cpp revision 336811
138494Sobrien//===-- VPlanVerifier.cpp -------------------------------------------------===// 238494Sobrien// 338494Sobrien// The LLVM Compiler Infrastructure 438494Sobrien// 5174294Sobrien// This file is distributed under the University of Illinois Open Source 638494Sobrien// License. See LICENSE.TXT for details. 738494Sobrien// 8174294Sobrien//===----------------------------------------------------------------------===// 9174294Sobrien/// 10174294Sobrien/// \file 1138494Sobrien/// This file defines the class VPlanVerifier, which contains utility functions 12174294Sobrien/// to check the consistency and invariants of a VPlan. 1338494Sobrien/// 1438494Sobrien//===----------------------------------------------------------------------===// 15174294Sobrien 1638494Sobrien#include "VPlanVerifier.h" 17174294Sobrien#include "llvm/ADT/DepthFirstIterator.h" 1838494Sobrien 1938494Sobrien#define DEBUG_TYPE "loop-vectorize" 2038494Sobrien 2138494Sobrienusing namespace llvm; 2238494Sobrien 2338494Sobrienstatic cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false), 2438494Sobrien cl::Hidden, 2538494Sobrien cl::desc("Verify VPlan H-CFG.")); 26174294Sobrien 2738494Sobrien#ifndef NDEBUG 2838494Sobrien/// Utility function that checks whether \p VPBlockVec has duplicate 2982794Sobrien/// VPBlockBases. 3038494Sobrienstatic bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) { 3138494Sobrien SmallDenseSet<const VPBlockBase *, 8> VPBlockSet; 3238494Sobrien for (const auto *Block : VPBlockVec) { 3352894Sobrien if (VPBlockSet.count(Block)) 3452894Sobrien return true; 3552894Sobrien VPBlockSet.insert(Block); 3652894Sobrien } 3738494Sobrien return false; 38174294Sobrien} 3938494Sobrien#endif 40174294Sobrien 41174294Sobrien/// Helper function that verifies the CFG invariants of the VPBlockBases within 42174294Sobrien/// \p Region. Checks in this function are generic for VPBlockBases. They are 43174294Sobrien/// not specific for VPBasicBlocks or VPRegionBlocks. 4438494Sobrienstatic void verifyBlocksInRegion(const VPRegionBlock *Region) { 4582794Sobrien for (const VPBlockBase *VPB : 46174294Sobrien make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()), 47174294Sobrien df_iterator<const VPBlockBase *>::end(Region->getExit()))) { 48174294Sobrien // Check block's parent. 49174294Sobrien assert(VPB->getParent() == Region && "VPBlockBase has wrong parent"); 50174294Sobrien 51174294Sobrien // Check block's condition bit. 52174294Sobrien if (VPB->getNumSuccessors() > 1) 53174294Sobrien assert(VPB->getCondBit() && "Missing condition bit!"); 54174294Sobrien else 55174294Sobrien assert(!VPB->getCondBit() && "Unexpected condition bit!"); 56174294Sobrien 57174294Sobrien // Check block's successors. 58174294Sobrien const auto &Successors = VPB->getSuccessors(); 59174294Sobrien // There must be only one instance of a successor in block's successor list. 6038494Sobrien // TODO: This won't work for switch statements. 6138494Sobrien assert(!hasDuplicates(Successors) && 6238494Sobrien "Multiple instances of the same successor."); 6338494Sobrien 6438494Sobrien for (const VPBlockBase *Succ : Successors) { 6538494Sobrien // There must be a bi-directional link between block and successor. 6638494Sobrien const auto &SuccPreds = Succ->getPredecessors(); 67310490Scy assert(std::find(SuccPreds.begin(), SuccPreds.end(), VPB) != 68310490Scy SuccPreds.end() && 69174294Sobrien "Missing predecessor link."); 70174294Sobrien (void)SuccPreds; 7138494Sobrien } 72174294Sobrien 7338494Sobrien // Check block's predecessors. 74174294Sobrien const auto &Predecessors = VPB->getPredecessors(); 7538494Sobrien // There must be only one instance of a predecessor in block's predecessor 7638494Sobrien // list. 7738494Sobrien // TODO: This won't work for switch statements. 7882794Sobrien assert(!hasDuplicates(Predecessors) && 7982794Sobrien "Multiple instances of the same predecessor."); 80174294Sobrien 81174294Sobrien for (const VPBlockBase *Pred : Predecessors) { 82174294Sobrien // Block and predecessor must be inside the same region. 8338494Sobrien assert(Pred->getParent() == VPB->getParent() && 8438494Sobrien "Predecessor is not in the same region."); 85174294Sobrien 86174294Sobrien // There must be a bi-directional link between block and predecessor. 8738494Sobrien const auto &PredSuccs = Pred->getSuccessors(); 8838494Sobrien assert(std::find(PredSuccs.begin(), PredSuccs.end(), VPB) != 89174294Sobrien PredSuccs.end() && 90174294Sobrien "Missing successor link."); 91174294Sobrien (void)PredSuccs; 9282794Sobrien } 93174294Sobrien } 9482794Sobrien} 9582794Sobrien 9682794Sobrien/// Verify the CFG invariants of VPRegionBlock \p Region and its nested 97174294Sobrien/// VPBlockBases. Do not recurse inside nested VPRegionBlocks. 98174294Sobrienstatic void verifyRegion(const VPRegionBlock *Region) { 99131702Smbr const VPBlockBase *Entry = Region->getEntry(); 100174294Sobrien const VPBlockBase *Exit = Region->getExit(); 101174294Sobrien 102174294Sobrien // Entry and Exit shouldn't have any predecessor/successor, respectively. 103174294Sobrien assert(!Entry->getNumPredecessors() && "Region entry has predecessors."); 104174294Sobrien assert(!Exit->getNumSuccessors() && "Region exit has successors."); 105174294Sobrien (void)Entry; 106174294Sobrien (void)Exit; 107174294Sobrien 108174294Sobrien verifyBlocksInRegion(Region); 10938494Sobrien} 11038494Sobrien 111310490Scy/// Verify the CFG invariants of VPRegionBlock \p Region and its nested 112174294Sobrien/// VPBlockBases. Recurse inside nested VPRegionBlocks. 113174294Sobrienstatic void verifyRegionRec(const VPRegionBlock *Region) { 114174294Sobrien verifyRegion(Region); 115174294Sobrien 116174294Sobrien // Recurse inside nested regions. 117174294Sobrien for (const VPBlockBase *VPB : 118174294Sobrien make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()), 119174294Sobrien df_iterator<const VPBlockBase *>::end(Region->getExit()))) { 120174294Sobrien if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB)) 121174294Sobrien verifyRegionRec(SubRegion); 122310490Scy } 123310490Scy} 124174294Sobrien 125174294Sobrienvoid VPlanVerifier::verifyHierarchicalCFG( 126174294Sobrien const VPRegionBlock *TopRegion) const { 12738494Sobrien if (!EnableHCFGVerifier) 12838494Sobrien return; 12938494Sobrien 13038494Sobrien LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n"); 13138494Sobrien assert(!TopRegion->getParent() && "VPlan Top Region should have no parent."); 13238494Sobrien verifyRegionRec(TopRegion); 13338494Sobrien} 13438494Sobrien