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
|
//===- VPlan.h - VPlan-based SLP ------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
/// \file
/// This file contains the declarations for VPlan-based SLP.
///
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANSLP_H
#define LLVM_TRANSFORMS_VECTORIZE_VPLANSLP_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/VectorUtils.h"
namespace llvm {
class VPBasicBlock;
class VPBlockBase;
class VPRegionBlock;
class VPlan;
class VPValue;
class VPInstruction;
class VPInterleavedAccessInfo {
DenseMap<VPInstruction *, InterleaveGroup<VPInstruction> *>
InterleaveGroupMap;
/// Type for mapping of instruction based interleave groups to VPInstruction
/// interleave groups
using Old2NewTy = DenseMap<InterleaveGroup<Instruction> *,
InterleaveGroup<VPInstruction> *>;
/// Recursively \p Region and populate VPlan based interleave groups based on
/// \p IAI.
void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New,
InterleavedAccessInfo &IAI);
/// Recursively traverse \p Block and populate VPlan based interleave groups
/// based on \p IAI.
void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
InterleavedAccessInfo &IAI);
public:
LLVM_ABI_FOR_TEST VPInterleavedAccessInfo(VPlan &Plan,
InterleavedAccessInfo &IAI);
VPInterleavedAccessInfo(const VPInterleavedAccessInfo &) = delete;
VPInterleavedAccessInfo &operator=(const VPInterleavedAccessInfo &) = delete;
~VPInterleavedAccessInfo() {
// Avoid releasing a pointer twice.
SmallPtrSet<InterleaveGroup<VPInstruction> *, 4> DelSet(
llvm::from_range, llvm::make_second_range(InterleaveGroupMap));
for (auto *Ptr : DelSet)
delete Ptr;
}
/// Get the interleave group that \p Instr belongs to.
///
/// \returns nullptr if doesn't have such group.
InterleaveGroup<VPInstruction> *
getInterleaveGroup(VPInstruction *Instr) const {
return InterleaveGroupMap.lookup(Instr);
}
};
/// Class that maps (parts of) an existing VPlan to trees of combined
/// VPInstructions.
class VPlanSlp {
enum class OpMode { Failed, Load, Opcode };
/// Mapping of values in the original VPlan to a combined VPInstruction.
DenseMap<SmallVector<VPValue *, 4>, VPInstruction *> BundleToCombined;
VPInterleavedAccessInfo &IAI;
/// Basic block to operate on. For now, only instructions in a single BB are
/// considered.
const VPBasicBlock &BB;
/// Indicates whether we managed to combine all visited instructions or not.
bool CompletelySLP = true;
/// Width of the widest combined bundle in bits.
unsigned WidestBundleBits = 0;
using MultiNodeOpTy =
typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>;
// Input operand bundles for the current multi node. Each multi node operand
// bundle contains values not matching the multi node's opcode. They will
// be reordered in reorderMultiNodeOps, once we completed building a
// multi node.
SmallVector<MultiNodeOpTy, 4> MultiNodeOps;
/// Indicates whether we are building a multi node currently.
bool MultiNodeActive = false;
/// Check if we can vectorize Operands together.
bool areVectorizable(ArrayRef<VPValue *> Operands) const;
/// Add combined instruction \p New for the bundle \p Operands.
void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New);
/// Indicate we hit a bundle we failed to combine. Returns nullptr for now.
VPInstruction *markFailed();
/// Reorder operands in the multi node to maximize sequential memory access
/// and commutative operations.
SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps();
/// Choose the best candidate to use for the lane after \p Last. The set of
/// candidates to choose from are values with an opcode matching \p Last's
/// or loads consecutive to \p Last.
std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last,
SmallPtrSetImpl<VPValue *> &Candidates,
VPInterleavedAccessInfo &IAI);
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
/// Print bundle \p Values to dbgs().
void dumpBundle(ArrayRef<VPValue *> Values);
#endif
public:
VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {}
~VPlanSlp() = default;
/// Tries to build an SLP tree rooted at \p Operands and returns a
/// VPInstruction combining \p Operands, if they can be combined.
LLVM_ABI_FOR_TEST VPInstruction *buildGraph(ArrayRef<VPValue *> Operands);
/// Return the width of the widest combined bundle in bits.
unsigned getWidestBundleBits() const { return WidestBundleBits; }
/// Return true if all visited instruction can be combined.
bool isCompletelySLP() const { return CompletelySLP; }
};
} // end namespace llvm
#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
|
