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