VPlanVerifier.cpp revision 336809
1130812Smarcel//===-- VPlanVerifier.cpp -------------------------------------------------===// 2130812Smarcel// 3130812Smarcel// The LLVM Compiler Infrastructure 4130812Smarcel// 5130812Smarcel// This file is distributed under the University of Illinois Open Source 6130812Smarcel// License. See LICENSE.TXT for details. 7130812Smarcel// 8130812Smarcel//===----------------------------------------------------------------------===// 9130812Smarcel/// 10130812Smarcel/// \file 11130812Smarcel/// This file defines the class VPlanVerifier, which contains utility functions 12130812Smarcel/// to check the consistency and invariants of a VPlan. 13130812Smarcel/// 14130812Smarcel//===----------------------------------------------------------------------===// 15130812Smarcel 16130812Smarcel#include "VPlanVerifier.h" 17130812Smarcel#include "llvm/ADT/DepthFirstIterator.h" 18130812Smarcel 19130812Smarcel#define DEBUG_TYPE "loop-vectorize" 20130812Smarcel 21130812Smarcelusing namespace llvm; 22130812Smarcel 23130812Smarcelstatic cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false), 24130812Smarcel cl::Hidden, 25130812Smarcel cl::desc("Verify VPlan H-CFG.")); 26130812Smarcel 27130812Smarcel#ifndef NDEBUG 28130812Smarcel/// Utility function that checks whether \p VPBlockVec has duplicate 29130812Smarcel/// VPBlockBases. 30130812Smarcelstatic bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) { 31130812Smarcel SmallDenseSet<const VPBlockBase *, 8> VPBlockSet; 32130812Smarcel for (const auto *Block : VPBlockVec) { 33130812Smarcel if (VPBlockSet.count(Block)) 34130812Smarcel return true; 35130812Smarcel VPBlockSet.insert(Block); 36130812Smarcel } 37130812Smarcel return false; 38130812Smarcel} 39130812Smarcel#endif 40130812Smarcel 41130812Smarcel/// Helper function that verifies the CFG invariants of the VPBlockBases within 42130812Smarcel/// \p Region. Checks in this function are generic for VPBlockBases. They are 43130812Smarcel/// not specific for VPBasicBlocks or VPRegionBlocks. 44130812Smarcelstatic void verifyBlocksInRegion(const VPRegionBlock *Region) { 45130812Smarcel for (const VPBlockBase *VPB : 46130812Smarcel make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()), 47130812Smarcel df_iterator<const VPBlockBase *>::end(Region->getExit()))) { 48130812Smarcel // Check block's parent. 49130812Smarcel assert(VPB->getParent() == Region && "VPBlockBase has wrong parent"); 50130812Smarcel 51130812Smarcel // Check block's condition bit. 52130812Smarcel if (VPB->getNumSuccessors() > 1) 53130812Smarcel assert(VPB->getCondBit() && "Missing condition bit!"); 54130812Smarcel else 55130812Smarcel assert(!VPB->getCondBit() && "Unexpected condition bit!"); 56130812Smarcel 57130812Smarcel // Check block's successors. 58130812Smarcel const auto &Successors = VPB->getSuccessors(); 59130812Smarcel // There must be only one instance of a successor in block's successor list. 60130812Smarcel // TODO: This won't work for switch statements. 61130812Smarcel assert(!hasDuplicates(Successors) && 62130812Smarcel "Multiple instances of the same successor."); 63130812Smarcel 64130812Smarcel for (const VPBlockBase *Succ : Successors) { 65130812Smarcel // There must be a bi-directional link between block and successor. 66130812Smarcel const auto &SuccPreds = Succ->getPredecessors(); 67130812Smarcel assert(std::find(SuccPreds.begin(), SuccPreds.end(), VPB) != 68130812Smarcel SuccPreds.end() && 69130812Smarcel "Missing predecessor link."); 70130812Smarcel (void)SuccPreds; 71130812Smarcel } 72130812Smarcel 73130812Smarcel // Check block's predecessors. 74130812Smarcel const auto &Predecessors = VPB->getPredecessors(); 75130812Smarcel // There must be only one instance of a predecessor in block's predecessor 76130812Smarcel // list. 77130812Smarcel // TODO: This won't work for switch statements. 78130812Smarcel assert(!hasDuplicates(Predecessors) && 79130812Smarcel "Multiple instances of the same predecessor."); 80130812Smarcel 81130812Smarcel for (const VPBlockBase *Pred : Predecessors) { 82130812Smarcel // Block and predecessor must be inside the same region. 83130812Smarcel assert(Pred->getParent() == VPB->getParent() && 84130812Smarcel "Predecessor is not in the same region."); 85130812Smarcel 86130812Smarcel // There must be a bi-directional link between block and predecessor. 87130812Smarcel const auto &PredSuccs = Pred->getSuccessors(); 88130812Smarcel assert(std::find(PredSuccs.begin(), PredSuccs.end(), VPB) != 89130812Smarcel PredSuccs.end() && 90130812Smarcel "Missing successor link."); 91130812Smarcel (void)PredSuccs; 92130812Smarcel } 93130812Smarcel } 94130812Smarcel} 95130812Smarcel 96130812Smarcel/// Verify the CFG invariants of VPRegionBlock \p Region and its nested 97130812Smarcel/// VPBlockBases. Do not recurse inside nested VPRegionBlocks. 98130812Smarcelstatic void verifyRegion(const VPRegionBlock *Region) { 99130812Smarcel const VPBlockBase *Entry = Region->getEntry(); 100130812Smarcel const VPBlockBase *Exit = Region->getExit(); 101130812Smarcel 102130812Smarcel // Entry and Exit shouldn't have any predecessor/successor, respectively. 103130812Smarcel assert(!Entry->getNumPredecessors() && "Region entry has predecessors."); 104130812Smarcel assert(!Exit->getNumSuccessors() && "Region exit has successors."); 105130812Smarcel (void)Entry; 106130812Smarcel (void)Exit; 107130812Smarcel 108130812Smarcel verifyBlocksInRegion(Region); 109130812Smarcel} 110130812Smarcel 111130812Smarcel/// Verify the CFG invariants of VPRegionBlock \p Region and its nested 112130812Smarcel/// VPBlockBases. Recurse inside nested VPRegionBlocks. 113130812Smarcelstatic void verifyRegionRec(const VPRegionBlock *Region) { 114130812Smarcel verifyRegion(Region); 115130812Smarcel 116130812Smarcel // Recurse inside nested regions. 117130812Smarcel for (const VPBlockBase *VPB : 118130812Smarcel make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()), 119130812Smarcel df_iterator<const VPBlockBase *>::end(Region->getExit()))) { 120130812Smarcel if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB)) 121130812Smarcel verifyRegionRec(SubRegion); 122130812Smarcel } 123130812Smarcel} 124130812Smarcel 125130812Smarcelvoid VPlanVerifier::verifyHierarchicalCFG( 126130812Smarcel const VPRegionBlock *TopRegion) const { 127130812Smarcel if (!EnableHCFGVerifier) 128130812Smarcel return; 129130812Smarcel 130130812Smarcel LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n"); 131130812Smarcel assert(!TopRegion->getParent() && "VPlan Top Region should have no parent."); 132130812Smarcel verifyRegionRec(TopRegion); 133130812Smarcel} 134130812Smarcel