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