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