VPlanVerifier.cpp revision 355940
1219820Sjeff//===-- VPlanVerifier.cpp -------------------------------------------------===// 2219820Sjeff// 3219820Sjeff// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4219820Sjeff// See https://llvm.org/LICENSE.txt for license information. 5219820Sjeff// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6219820Sjeff// 7219820Sjeff//===----------------------------------------------------------------------===// 8219820Sjeff/// 9219820Sjeff/// \file 10219820Sjeff/// This file defines the class VPlanVerifier, which contains utility functions 11219820Sjeff/// to check the consistency and invariants of a VPlan. 12219820Sjeff/// 13219820Sjeff//===----------------------------------------------------------------------===// 14219820Sjeff 15219820Sjeff#include "VPlanVerifier.h" 16219820Sjeff#include "llvm/ADT/DepthFirstIterator.h" 17219820Sjeff 18219820Sjeff#define DEBUG_TYPE "loop-vectorize" 19219820Sjeff 20219820Sjeffusing namespace llvm; 21219820Sjeff 22219820Sjeffstatic cl::opt<bool> EnableHCFGVerifier("vplan-verify-hcfg", cl::init(false), 23219820Sjeff cl::Hidden, 24219820Sjeff cl::desc("Verify VPlan H-CFG.")); 25219820Sjeff 26219820Sjeff#ifndef NDEBUG 27219820Sjeff/// Utility function that checks whether \p VPBlockVec has duplicate 28219820Sjeff/// VPBlockBases. 29219820Sjeffstatic bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) { 30219820Sjeff SmallDenseSet<const VPBlockBase *, 8> VPBlockSet; 31219820Sjeff for (const auto *Block : VPBlockVec) { 32219820Sjeff if (VPBlockSet.count(Block)) 33219820Sjeff return true; 34219820Sjeff VPBlockSet.insert(Block); 35219820Sjeff } 36219820Sjeff return false; 37219820Sjeff} 38219820Sjeff#endif 39219820Sjeff 40219820Sjeff/// Helper function that verifies the CFG invariants of the VPBlockBases within 41219820Sjeff/// \p Region. Checks in this function are generic for VPBlockBases. They are 42219820Sjeff/// not specific for VPBasicBlocks or VPRegionBlocks. 43219820Sjeffstatic void verifyBlocksInRegion(const VPRegionBlock *Region) { 44219820Sjeff for (const VPBlockBase *VPB : 45219820Sjeff make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()), 46219820Sjeff df_iterator<const VPBlockBase *>::end(Region->getExit()))) { 47219820Sjeff // Check block's parent. 48219820Sjeff assert(VPB->getParent() == Region && "VPBlockBase has wrong parent"); 49219820Sjeff 50219820Sjeff // Check block's condition bit. 51219820Sjeff if (VPB->getNumSuccessors() > 1) 52219820Sjeff assert(VPB->getCondBit() && "Missing condition bit!"); 53219820Sjeff else 54219820Sjeff assert(!VPB->getCondBit() && "Unexpected condition bit!"); 55219820Sjeff 56219820Sjeff // Check block's successors. 57219820Sjeff const auto &Successors = VPB->getSuccessors(); 58219820Sjeff // There must be only one instance of a successor in block's successor list. 59219820Sjeff // TODO: This won't work for switch statements. 60219820Sjeff assert(!hasDuplicates(Successors) && 61219820Sjeff "Multiple instances of the same successor."); 62219820Sjeff 63219820Sjeff for (const VPBlockBase *Succ : Successors) { 64219820Sjeff // There must be a bi-directional link between block and successor. 65219820Sjeff const auto &SuccPreds = Succ->getPredecessors(); 66219820Sjeff assert(std::find(SuccPreds.begin(), SuccPreds.end(), VPB) != 67219820Sjeff SuccPreds.end() && 68219820Sjeff "Missing predecessor link."); 69219820Sjeff (void)SuccPreds; 70219820Sjeff } 71219820Sjeff 72219820Sjeff // Check block's predecessors. 73219820Sjeff const auto &Predecessors = VPB->getPredecessors(); 74219820Sjeff // There must be only one instance of a predecessor in block's predecessor 75219820Sjeff // list. 76219820Sjeff // TODO: This won't work for switch statements. 77219820Sjeff assert(!hasDuplicates(Predecessors) && 78219820Sjeff "Multiple instances of the same predecessor."); 79219820Sjeff 80219820Sjeff for (const VPBlockBase *Pred : Predecessors) { 81219820Sjeff // Block and predecessor must be inside the same region. 82219820Sjeff assert(Pred->getParent() == VPB->getParent() && 83219820Sjeff "Predecessor is not in the same region."); 84219820Sjeff 85219820Sjeff // There must be a bi-directional link between block and predecessor. 86219820Sjeff const auto &PredSuccs = Pred->getSuccessors(); 87219820Sjeff assert(std::find(PredSuccs.begin(), PredSuccs.end(), VPB) != 88219820Sjeff PredSuccs.end() && 89219820Sjeff "Missing successor link."); 90219820Sjeff (void)PredSuccs; 91219820Sjeff } 92219820Sjeff } 93219820Sjeff} 94219820Sjeff 95219820Sjeff/// Verify the CFG invariants of VPRegionBlock \p Region and its nested 96219820Sjeff/// VPBlockBases. Do not recurse inside nested VPRegionBlocks. 97219820Sjeffstatic void verifyRegion(const VPRegionBlock *Region) { 98219820Sjeff const VPBlockBase *Entry = Region->getEntry(); 99219820Sjeff const VPBlockBase *Exit = Region->getExit(); 100219820Sjeff 101219820Sjeff // Entry and Exit shouldn't have any predecessor/successor, respectively. 102219820Sjeff assert(!Entry->getNumPredecessors() && "Region entry has predecessors."); 103219820Sjeff assert(!Exit->getNumSuccessors() && "Region exit has successors."); 104219820Sjeff (void)Entry; 105219820Sjeff (void)Exit; 106219820Sjeff 107219820Sjeff verifyBlocksInRegion(Region); 108219820Sjeff} 109219820Sjeff 110219820Sjeff/// Verify the CFG invariants of VPRegionBlock \p Region and its nested 111219820Sjeff/// VPBlockBases. Recurse inside nested VPRegionBlocks. 112219820Sjeffstatic void verifyRegionRec(const VPRegionBlock *Region) { 113219820Sjeff verifyRegion(Region); 114219820Sjeff 115219820Sjeff // Recurse inside nested regions. 116219820Sjeff for (const VPBlockBase *VPB : 117219820Sjeff make_range(df_iterator<const VPBlockBase *>::begin(Region->getEntry()), 118219820Sjeff df_iterator<const VPBlockBase *>::end(Region->getExit()))) { 119219820Sjeff if (const auto *SubRegion = dyn_cast<VPRegionBlock>(VPB)) 120219820Sjeff verifyRegionRec(SubRegion); 121219820Sjeff } 122219820Sjeff} 123219820Sjeff 124219820Sjeffvoid VPlanVerifier::verifyHierarchicalCFG( 125219820Sjeff const VPRegionBlock *TopRegion) const { 126219820Sjeff if (!EnableHCFGVerifier) 127219820Sjeff return; 128219820Sjeff 129219820Sjeff LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n"); 130219820Sjeff assert(!TopRegion->getParent() && "VPlan Top Region should have no parent."); 131219820Sjeff verifyRegionRec(TopRegion); 132219820Sjeff} 133219820Sjeff