1//===- BottomUpVec.h --------------------------------------------*- C++ -*-===//
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// A Bottom-Up Vectorizer pass.
10//
11
12#ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_PASSES_BOTTOMUPVEC_H
13#define LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_PASSES_BOTTOMUPVEC_H
14
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/StringRef.h"
17#include "llvm/SandboxIR/Constant.h"
18#include "llvm/SandboxIR/Pass.h"
19#include "llvm/Support/raw_ostream.h"
20#include "llvm/Transforms/Vectorize/SandboxVectorizer/InstrMaps.h"
21#include "llvm/Transforms/Vectorize/SandboxVectorizer/Legality.h"
22
23namespace llvm::sandboxir {
24
25/// This is a simple bottom-up vectorizer Region pass.
26/// It expects a "seed slice" as an input in the Region's Aux vector.
27/// The "seed slice" is a vector of instructions that can be used as a starting
28/// point for vectorization, like stores to consecutive memory addresses.
29/// Starting from the seed instructions, it walks up the def-use chain looking
30/// for more instructions that can be vectorized. This pass will generate vector
31/// code if it can legally vectorize the code, regardless of whether it is
32/// profitable or not. For now profitability is checked at the end of the region
33/// pass pipeline by a dedicated pass that accepts or rejects the IR
34/// transaction, depending on the cost.
35class BottomUpVec final : public RegionPass {
36 bool Change = false;
37 /// The original instructions that are potentially dead after vectorization.
38 DenseSet<Instruction *> DeadInstrCandidates;
39 /// Maps scalars to vectors.
40 std::unique_ptr<InstrMaps> IMaps;
41 /// Counter used for force-stopping the vectorizer after this many
42 /// invocations. Used for debugging miscompiles.
43 unsigned long BottomUpInvocationCnt = 0;
44
45 /// Creates and returns a vector instruction that replaces the instructions in
46 /// \p Bndl. \p Operands are the already vectorized operands.
47 Value *createVectorInstr(ArrayRef<Value *> Bndl, ArrayRef<Value *> Operands);
48 /// Erases all dead instructions from the dead instruction candidates
49 /// collected during vectorization.
50 void tryEraseDeadInstrs();
51 /// Creates a shuffle instruction that shuffles \p VecOp according to \p Mask.
52 /// \p UserBB is the block of the user bundle.
53 Value *createShuffle(Value *VecOp, const ShuffleMask &Mask,
54 BasicBlock *UserBB);
55 /// Packs all elements of \p ToPack into a vector and returns that vector. \p
56 /// UserBB is the block of the user bundle.
57 Value *createPack(ArrayRef<Value *> ToPack, BasicBlock *UserBB);
58 /// After we create vectors for groups of instructions, the original
59 /// instructions are potentially dead and may need to be removed. This
60 /// function helps collect these instructions (along with the pointer operands
61 /// for loads/stores) so that they can be cleaned up later.
62 void collectPotentiallyDeadInstrs(ArrayRef<Value *> Bndl);
63
64 /// Helper class describing how(if) to vectorize the code.
65 class ActionsVector {
66 private:
67 SmallVector<std::unique_ptr<Action>, 16> Actions;
68
69 public:
70 auto begin() const { return Actions.begin(); }
71 auto end() const { return Actions.end(); }
72 void push_back(std::unique_ptr<Action> &&ActPtr) {
73 ActPtr->Idx = Actions.size();
74 Actions.push_back(Elt: std::move(ActPtr));
75 }
76 void clear() { Actions.clear(); }
77#ifndef NDEBUG
78 void print(raw_ostream &OS) const;
79 void dump() const;
80#endif // NDEBUG
81 };
82 ActionsVector Actions;
83 /// Helper counter for debugging. It counts the bundles that we attempt to
84 /// vectorize in vectorizeRec().
85 unsigned DebugBndlCnt = 0;
86
87 /// Recursively try to vectorize \p Bndl and its operands. This populates the
88 /// `Actions` vector.
89 Action *vectorizeRec(ArrayRef<Value *> Bndl, ArrayRef<Value *> UserBndl,
90 unsigned Depth, LegalityAnalysis &Legality);
91 /// Generate vector instructions based on `Actions` and return the last vector
92 /// created.
93 Value *emitVectors();
94 /// Entry point for vectorization starting from \p Seeds.
95 bool tryVectorize(ArrayRef<Value *> Seeds, LegalityAnalysis &Legality);
96
97public:
98 BottomUpVec() : RegionPass("bottom-up-vec") {}
99 bool runOnRegion(Region &Rgn, const Analyses &A) final;
100};
101
102} // namespace llvm::sandboxir
103
104#endif // LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_PASSES_BOTTOMUPVEC_H
105