1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
|
//===- VPlanCFG.h - GraphTraits for VP blocks -------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
/// Specializations of GraphTraits that allow VPBlockBase graphs to be
/// treated as proper graphs for generic algorithms;
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H
#define LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H
#include "VPlan.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallVector.h"
namespace llvm {
//===----------------------------------------------------------------------===//
// GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs //
//===----------------------------------------------------------------------===//
/// Iterator to traverse all successors of a VPBlockBase node. This includes the
/// entry node of VPRegionBlocks. Exit blocks of a region implicitly have their
/// parent region's successors. This ensures all blocks in a region are visited
/// before any blocks in a successor region when doing a reverse post-order
// traversal of the graph. Region blocks themselves traverse only their entries
// directly and not their successors. Those will be traversed when a region's
// exiting block is traversed
template <typename BlockPtrTy>
class VPAllSuccessorsIterator
: public iterator_facade_base<VPAllSuccessorsIterator<BlockPtrTy>,
std::bidirectional_iterator_tag,
VPBlockBase> {
BlockPtrTy Block;
/// Index of the current successor. For VPBasicBlock nodes, this simply is the
/// index for the successor array. For VPRegionBlock, SuccessorIdx == 0 is
/// used for the region's entry block, and SuccessorIdx - 1 are the indices
/// for the successor array.
size_t SuccessorIdx;
static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) {
while (Current && Current->getNumSuccessors() == 0)
Current = Current->getParent();
return Current;
}
/// Templated helper to dereference successor \p SuccIdx of \p Block. Used by
/// both the const and non-const operator* implementations.
template <typename T1> static T1 deref(T1 Block, unsigned SuccIdx) {
if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
assert(SuccIdx == 0);
return R->getEntry();
}
// For exit blocks, use the next parent region with successors.
return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx];
}
public:
/// Used by iterator_facade_base with bidirectional_iterator_tag.
using reference = BlockPtrTy;
VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0)
: Block(Block), SuccessorIdx(Idx) {}
VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other)
: Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {}
VPAllSuccessorsIterator &operator=(const VPAllSuccessorsIterator &R) {
Block = R.Block;
SuccessorIdx = R.SuccessorIdx;
return *this;
}
static VPAllSuccessorsIterator end(BlockPtrTy Block) {
if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
// Traverse through the region's entry node.
return {R, 1};
}
BlockPtrTy ParentWithSuccs = getBlockWithSuccs(Block);
unsigned NumSuccessors =
ParentWithSuccs ? ParentWithSuccs->getNumSuccessors() : 0;
return {Block, NumSuccessors};
}
bool operator==(const VPAllSuccessorsIterator &R) const {
return Block == R.Block && SuccessorIdx == R.SuccessorIdx;
}
const VPBlockBase *operator*() const { return deref(Block, SuccessorIdx); }
BlockPtrTy operator*() { return deref(Block, SuccessorIdx); }
VPAllSuccessorsIterator &operator++() {
SuccessorIdx++;
return *this;
}
VPAllSuccessorsIterator &operator--() {
SuccessorIdx--;
return *this;
}
VPAllSuccessorsIterator operator++(int X) {
VPAllSuccessorsIterator Orig = *this;
SuccessorIdx++;
return Orig;
}
};
/// Helper for GraphTraits specialization that traverses through VPRegionBlocks.
template <typename BlockTy> class VPBlockDeepTraversalWrapper {
BlockTy Entry;
public:
VPBlockDeepTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
BlockTy getEntry() { return Entry; }
};
/// GraphTraits specialization to recursively traverse VPBlockBase nodes,
/// including traversing through VPRegionBlocks. Exit blocks of a region
/// implicitly have their parent region's successors. This ensures all blocks in
/// a region are visited before any blocks in a successor region when doing a
/// reverse post-order traversal of the graph.
template <> struct GraphTraits<VPBlockDeepTraversalWrapper<VPBlockBase *>> {
using NodeRef = VPBlockBase *;
using ChildIteratorType = VPAllSuccessorsIterator<VPBlockBase *>;
static NodeRef getEntryNode(VPBlockDeepTraversalWrapper<VPBlockBase *> N) {
return N.getEntry();
}
static inline ChildIteratorType child_begin(NodeRef N) {
return ChildIteratorType(N);
}
static inline ChildIteratorType child_end(NodeRef N) {
return ChildIteratorType::end(N);
}
};
template <>
struct GraphTraits<VPBlockDeepTraversalWrapper<const VPBlockBase *>> {
using NodeRef = const VPBlockBase *;
using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>;
static NodeRef
getEntryNode(VPBlockDeepTraversalWrapper<const VPBlockBase *> N) {
return N.getEntry();
}
static inline ChildIteratorType child_begin(NodeRef N) {
return ChildIteratorType(N);
}
static inline ChildIteratorType child_end(NodeRef N) {
return ChildIteratorType::end(N);
}
};
/// Helper for GraphTraits specialization that does not traverses through
/// VPRegionBlocks.
template <typename BlockTy> class VPBlockShallowTraversalWrapper {
BlockTy Entry;
public:
VPBlockShallowTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
BlockTy getEntry() { return Entry; }
};
template <> struct GraphTraits<VPBlockShallowTraversalWrapper<VPBlockBase *>> {
using NodeRef = VPBlockBase *;
using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
static NodeRef getEntryNode(VPBlockShallowTraversalWrapper<VPBlockBase *> N) {
return N.getEntry();
}
static inline ChildIteratorType child_begin(NodeRef N) {
return N->getSuccessors().begin();
}
static inline ChildIteratorType child_end(NodeRef N) {
return N->getSuccessors().end();
}
};
template <>
struct GraphTraits<VPBlockShallowTraversalWrapper<const VPBlockBase *>> {
using NodeRef = const VPBlockBase *;
using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator;
static NodeRef
getEntryNode(VPBlockShallowTraversalWrapper<const VPBlockBase *> N) {
return N.getEntry();
}
static inline ChildIteratorType child_begin(NodeRef N) {
return N->getSuccessors().begin();
}
static inline ChildIteratorType child_end(NodeRef N) {
return N->getSuccessors().end();
}
};
/// Returns an iterator range to traverse the graph starting at \p G in
/// depth-first order. The iterator won't traverse through region blocks.
inline iterator_range<
df_iterator<VPBlockShallowTraversalWrapper<VPBlockBase *>>>
vp_depth_first_shallow(VPBlockBase *G) {
return depth_first(VPBlockShallowTraversalWrapper<VPBlockBase *>(G));
}
inline iterator_range<
df_iterator<VPBlockShallowTraversalWrapper<const VPBlockBase *>>>
vp_depth_first_shallow(const VPBlockBase *G) {
return depth_first(VPBlockShallowTraversalWrapper<const VPBlockBase *>(G));
}
/// Returns an iterator range to traverse the graph starting at \p G in
/// depth-first order while traversing through region blocks.
inline iterator_range<df_iterator<VPBlockDeepTraversalWrapper<VPBlockBase *>>>
vp_depth_first_deep(VPBlockBase *G) {
return depth_first(VPBlockDeepTraversalWrapper<VPBlockBase *>(G));
}
inline iterator_range<
df_iterator<VPBlockDeepTraversalWrapper<const VPBlockBase *>>>
vp_depth_first_deep(const VPBlockBase *G) {
return depth_first(VPBlockDeepTraversalWrapper<const VPBlockBase *>(G));
}
// The following set of template specializations implement GraphTraits to treat
// any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
// that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
// VPBlockBase is a VPRegionBlock, this specialization provides access to its
// successors/predecessors but not to the blocks inside the region.
template <> struct GraphTraits<VPBlockBase *> {
using NodeRef = VPBlockBase *;
using ChildIteratorType = VPAllSuccessorsIterator<VPBlockBase *>;
static NodeRef getEntryNode(NodeRef N) { return N; }
static inline ChildIteratorType child_begin(NodeRef N) {
return ChildIteratorType(N);
}
static inline ChildIteratorType child_end(NodeRef N) {
return ChildIteratorType::end(N);
}
};
template <> struct GraphTraits<const VPBlockBase *> {
using NodeRef = const VPBlockBase *;
using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>;
static NodeRef getEntryNode(NodeRef N) { return N; }
static inline ChildIteratorType child_begin(NodeRef N) {
return ChildIteratorType(N);
}
static inline ChildIteratorType child_end(NodeRef N) {
return ChildIteratorType::end(N);
}
};
/// Inverse graph traits are not implemented yet.
/// TODO: Implement a version of VPBlockNonRecursiveTraversalWrapper to traverse
/// predecessors recursively through regions.
template <> struct GraphTraits<Inverse<VPBlockBase *>> {
using NodeRef = VPBlockBase *;
using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
static NodeRef getEntryNode(Inverse<NodeRef> B) {
llvm_unreachable("not implemented");
}
static inline ChildIteratorType child_begin(NodeRef N) {
llvm_unreachable("not implemented");
}
static inline ChildIteratorType child_end(NodeRef N) {
llvm_unreachable("not implemented");
}
};
template <> struct GraphTraits<VPlan *> {
using GraphRef = VPlan *;
using NodeRef = VPBlockBase *;
using nodes_iterator = df_iterator<NodeRef>;
static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
static nodes_iterator nodes_begin(GraphRef N) {
return nodes_iterator::begin(N->getEntry());
}
static nodes_iterator nodes_end(GraphRef N) {
// df_iterator::end() returns an empty iterator so the node used doesn't
// matter.
return nodes_iterator::end(N->getEntry());
}
};
} // namespace llvm
#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H
|