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 23 namespace 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. 35 class 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: begin()70 auto begin() const { return Actions.begin(); } end()71 auto end() const { return Actions.end(); } push_back(std::unique_ptr<Action> && ActPtr)72 void push_back(std::unique_ptr<Action> &&ActPtr) { 73 ActPtr->Idx = Actions.size(); 74 Actions.push_back(std::move(ActPtr)); 75 } clear()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 97 public: BottomUpVec()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