1//===- VPlan.h - VPlan-based SLP ------------------------------------------===//
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 contains the declarations for VPlan-based SLP.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANSLP_H
15#define LLVM_TRANSFORMS_VECTORIZE_VPLANSLP_H
16
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/Analysis/VectorUtils.h"
21
22namespace llvm {
23
24class VPBasicBlock;
25class VPBlockBase;
26class VPRegionBlock;
27class VPlan;
28class VPValue;
29class VPInstruction;
30
31class VPInterleavedAccessInfo {
32 DenseMap<VPInstruction *, InterleaveGroup<VPInstruction> *>
33 InterleaveGroupMap;
34
35 /// Type for mapping of instruction based interleave groups to VPInstruction
36 /// interleave groups
37 using Old2NewTy = DenseMap<InterleaveGroup<Instruction> *,
38 InterleaveGroup<VPInstruction> *>;
39
40 /// Recursively \p Region and populate VPlan based interleave groups based on
41 /// \p IAI.
42 void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New,
43 InterleavedAccessInfo &IAI);
44 /// Recursively traverse \p Block and populate VPlan based interleave groups
45 /// based on \p IAI.
46 void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
47 InterleavedAccessInfo &IAI);
48
49public:
50 VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI);
51 VPInterleavedAccessInfo(const VPInterleavedAccessInfo &) = delete;
52 VPInterleavedAccessInfo &operator=(const VPInterleavedAccessInfo &) = delete;
53
54 ~VPInterleavedAccessInfo() {
55 // Avoid releasing a pointer twice.
56 SmallPtrSet<InterleaveGroup<VPInstruction> *, 4> DelSet(
57 llvm::from_range, llvm::make_second_range(c&: InterleaveGroupMap));
58 for (auto *Ptr : DelSet)
59 delete Ptr;
60 }
61
62 /// Get the interleave group that \p Instr belongs to.
63 ///
64 /// \returns nullptr if doesn't have such group.
65 InterleaveGroup<VPInstruction> *
66 getInterleaveGroup(VPInstruction *Instr) const {
67 return InterleaveGroupMap.lookup(Val: Instr);
68 }
69};
70
71/// Class that maps (parts of) an existing VPlan to trees of combined
72/// VPInstructions.
73class VPlanSlp {
74 enum class OpMode { Failed, Load, Opcode };
75
76 /// Mapping of values in the original VPlan to a combined VPInstruction.
77 DenseMap<SmallVector<VPValue *, 4>, VPInstruction *> BundleToCombined;
78
79 VPInterleavedAccessInfo &IAI;
80
81 /// Basic block to operate on. For now, only instructions in a single BB are
82 /// considered.
83 const VPBasicBlock &BB;
84
85 /// Indicates whether we managed to combine all visited instructions or not.
86 bool CompletelySLP = true;
87
88 /// Width of the widest combined bundle in bits.
89 unsigned WidestBundleBits = 0;
90
91 using MultiNodeOpTy =
92 typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>;
93
94 // Input operand bundles for the current multi node. Each multi node operand
95 // bundle contains values not matching the multi node's opcode. They will
96 // be reordered in reorderMultiNodeOps, once we completed building a
97 // multi node.
98 SmallVector<MultiNodeOpTy, 4> MultiNodeOps;
99
100 /// Indicates whether we are building a multi node currently.
101 bool MultiNodeActive = false;
102
103 /// Check if we can vectorize Operands together.
104 bool areVectorizable(ArrayRef<VPValue *> Operands) const;
105
106 /// Add combined instruction \p New for the bundle \p Operands.
107 void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New);
108
109 /// Indicate we hit a bundle we failed to combine. Returns nullptr for now.
110 VPInstruction *markFailed();
111
112 /// Reorder operands in the multi node to maximize sequential memory access
113 /// and commutative operations.
114 SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps();
115
116 /// Choose the best candidate to use for the lane after \p Last. The set of
117 /// candidates to choose from are values with an opcode matching \p Last's
118 /// or loads consecutive to \p Last.
119 std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last,
120 SmallPtrSetImpl<VPValue *> &Candidates,
121 VPInterleavedAccessInfo &IAI);
122
123#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
124 /// Print bundle \p Values to dbgs().
125 void dumpBundle(ArrayRef<VPValue *> Values);
126#endif
127
128public:
129 VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {}
130
131 ~VPlanSlp() = default;
132
133 /// Tries to build an SLP tree rooted at \p Operands and returns a
134 /// VPInstruction combining \p Operands, if they can be combined.
135 VPInstruction *buildGraph(ArrayRef<VPValue *> Operands);
136
137 /// Return the width of the widest combined bundle in bits.
138 unsigned getWidestBundleBits() const { return WidestBundleBits; }
139
140 /// Return true if all visited instruction can be combined.
141 bool isCompletelySLP() const { return CompletelySLP; }
142};
143} // end namespace llvm
144
145#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
146