1 /*========================== begin_copyright_notice ============================
2 
3 Copyright (C) 2017-2021 Intel Corporation
4 
5 SPDX-License-Identifier: MIT
6 
7 ============================= end_copyright_notice ===========================*/
8 
9 #pragma once
10 
11 #include "common/LLVMWarningsPush.hpp"
12 #include <llvm/Pass.h>
13 #include <llvm/IR/Type.h>
14 #include <llvm/IR/Instructions.h>
15 #include <llvm/ADT/DenseMap.h>
16 #include "llvm/ADT/MapVector.h"
17 #include <llvm/ADT/ilist.h>
18 #include <llvm/ADT/SetVector.h>
19 #include <llvm/ADT/SmallPtrSet.h>
20 #include <llvm/Support/Debug.h>
21 #include <llvm/IR/InstIterator.h>
22 #include <llvm/Support/raw_ostream.h>
23 #include <llvm/IR/Constants.h>
24 #include <llvm/IR/DataLayout.h>
25 #include "common/LLVMWarningsPop.hpp"
26 #include <llvm/ADT/DenseSet.h>
27 
28 #include <string>
29 #include <sstream>
30 #include <set>
31 #include <map>
32 
33 namespace IGC
34 {
35 
36     // Maximum width supported as input
37 #define MAX_INPUT_VECTOR_WIDTH 16
38 
39 // Define estimated amount of instructions in function
40 #define ESTIMATED_INST_NUM 128
41 
42 /// @brief Scalarization pass used for converting code in functions
43 ///  which operate on vector types, to work on scalar types (by breaking
44 ///  data elements to scalars, and breaking each vector operation
45 ///  to several scalar operations).
46 ///  Functions are also replaced (similar to instructions), according
47 ///  to data received from RuntimeServices.
48 
49     class ScalarizeFunction : public llvm::FunctionPass
50     {
51     public:
52         static char ID; // Pass identification, replacement for typeid
53 
54         ScalarizeFunction(bool selectiveScalarization = false);
55 
56         ~ScalarizeFunction();
57 
58         /// @brief Provides name of pass
getPassName()59         virtual llvm::StringRef getPassName() const override
60         {
61             return "ScalarizeFunction";
62         }
63 
getAnalysisUsage(llvm::AnalysisUsage & AU)64         virtual void getAnalysisUsage(llvm::AnalysisUsage& AU) const override
65         {
66             AU.setPreservesCFG();
67         }
68 
69         virtual bool runOnFunction(llvm::Function& F) override;
70 
71     private:
72 
73         /// @brief select an exclusive set that would not be scalarized
74         void buildExclusiveSet();
75         /// @brief main Method for dispatching instructions (according to inst type) for scalarization
76         /// @param I instruction to dispatch
77         void dispatchInstructionToScalarize(llvm::Instruction* I);
78 
79         /// @brief Instructions which cannot be Scalarized reach this function.
80         ///  They may have a vector value, so create empty SCM entries for them if needed,
81         ///  and also re-create any vector input which may have been scalarized
82         /// @param Inst instruction to work on
83         void recoverNonScalarizableInst(llvm::Instruction* Inst);
84 
85         /*! \name Scalarizarion Functions
86          *  \{ */
87          /// @brief Scalarize an instruction
88          /// @param I Instruction to scalarize
89         void scalarizeInstruction(llvm::BinaryOperator* BI);
90         void scalarizeInstruction(llvm::CmpInst* CI);
91         void scalarizeInstruction(llvm::CastInst* CI);
92         void scalarizeInstruction(llvm::PHINode* CI);
93         void scalarizeInstruction(llvm::SelectInst* SI);
94         void scalarizeInstruction(llvm::ExtractElementInst* SI);
95         void scalarizeInstruction(llvm::InsertElementInst* II);
96         void scalarizeInstruction(llvm::ShuffleVectorInst* SI);
97         void scalarizeInstruction(llvm::CallInst* CI);
98         void scalarizeInstruction(llvm::AllocaInst* CI);
99         void scalarizeInstruction(llvm::GetElementPtrInst* CI);
100 
101         /*! \name Scalarizarion Utility Functions
102          *  \{ */
103 
104          /// @brief Takes a vector value, and returns the scalarized "breakdown" of that value
105          /// @param retValues Array for returning scalar elements in
106          /// @param retIsConstant Return (by reference) if the given value is a constant
107          /// @param origValue Vector value to obtain elements from
108          /// @param origInst Instruction for which service is requested (may be used as insertion point)
109         void obtainScalarizedValues(llvm::SmallVectorImpl<llvm::Value*>& retValues, bool* retIsConstant,
110             llvm::Value* origValue, llvm::Instruction* origInst, int dstIdx = -1);
111 
112 
113         /// @brief a set contains vector from original kernel that need to be used after sclarization
114         llvm::SmallSetVector<llvm::Value*, ESTIMATED_INST_NUM> m_usedVectors;
115 
116         /// @brief update museVectors set with the vectori value to be obtained at when scalarization finish
117         /// @param vectorVal Vector being added to set
118         void obtainVectorValueWhichMightBeScalarized(llvm::Value* vectorVal);
119 
120         /// @brief Given a vector value, check if still exists, or rebuild from scalar elements
121         ///  this funciton assumes the SCM map is updated and thus should be run after sclarization is finished
122         /// @param vectorVal Vector being checked
123         void obtainVectorValueWhichMightBeScalarizedImpl(llvm::Value* vectorVal);
124 
125         /// @brief obtaining vector values that are needed after scalarizaion by invoking
126         ///  obtainVectorValueWhichMightBeScalarizedImpl over m_usedVectors
127         void resolveVectorValues();
128 
129         /// @brief Resolve deferred insts (Values which were scalarized with dummies)
130         void resolveDeferredInstructions();
131 
132         /*! \} */
133 
134         /// @brief Pointer to current function's context
135         llvm::LLVMContext* m_moduleContext;
136         /// @brief Accessor to current function's context
context()137         llvm::LLVMContext& context() { return *m_moduleContext; }
138         /// @brief Pointer to current function
139         llvm::Function* m_currFunc;
140 
141         /// @brief Set containing all the removed instructions in the function.
142         llvm::SmallDenseSet<llvm::Instruction*, ESTIMATED_INST_NUM> m_removedInsts;
143         /// @brief Counters for "transpose" statistics
144         int m_transposeCtr[llvm::Instruction::OtherOpsEnd];
145 
146         /// <summary>
147         /// @brief The instructions we do not want to scalarize
148         /// </summary>
149         std::set<llvm::Value*> m_Excludes;
150 
151         /// @brief The SCM (scalar conversions map). Per each value - map of its scalar elements
152         struct SCMEntry
153         {
154             llvm::SmallVector<llvm::Value*, MAX_INPUT_VECTOR_WIDTH>scalarValues;
155             bool isOriginalVectorRemoved;
156         };
157         llvm::DenseMap<llvm::Value*, SCMEntry*> m_SCM;
158 
159         /// @brief called to create a new SCM entry. If entry already exists - return it instead
160         /// @param origValue Value pointer to search in SCM
161         /// @return pointer to found or created SCM entry
162         SCMEntry* getSCMEntry(llvm::Value* origValue);
163 
164         /// @brief called to update values in SCM entry
165         /// @param entry SCM entry to update
166         /// @param scalarValues array of values to place in SCMEntry
167         /// @param origValue Value which is the key of the SCMEntry
168         /// @param isOrigValueRemoved True if original (vector) value was erased during scalarization
169         /// @param matchDbgLoc True if we want to match debug loc of the scalar value to orig Value.
170         void updateSCMEntryWithValues(SCMEntry* entry, llvm::Value* scalarValues[],
171             const llvm::Value* origValue, bool isOrigValueRemoved,
172             bool matchDbgLoc = true);
173 
174         /// @brief returns an SCM entry if it exists. otherwise return NULL.
175         /// @param origValue Value used as key in SCM
176         /// @return SCMEntry if found, NULL otherwise
177         SCMEntry* getScalarizedValues(llvm::Value* origValue);
178 
179         /// @brief release all allocations of SCM entries
180         void releaseAllSCMEntries();
181 
182         /// @brief create the dummy function which is called to signify a dummy value
getOrCreateDummyFunc(llvm::Type * dummyType,llvm::Module * module)183         inline llvm::Function* getOrCreateDummyFunc(llvm::Type* dummyType, llvm::Module* module) {
184             if (createdDummyFunctions.find(dummyType) == createdDummyFunctions.end()) {
185                 llvm::FunctionType* funcType = llvm::FunctionType::get(dummyType, false);
186                 llvm::Function* function = llvm::Function::Create(funcType, llvm::Function::InternalLinkage, "", module);
187                 createdDummyFunctions[dummyType] = function;
188                 return function;
189             }
190             else
191                 return createdDummyFunctions[dummyType];
192         }
193 
194         /// @brief deletes the memory associated with all the created dynamic Function objects in the map
destroyDummyFunc()195         inline void destroyDummyFunc() {
196             for (auto& function : createdDummyFunctions) {
197                 if (function.second) {
198                     function.second->eraseFromParent();
199                     function.second = nullptr;
200                 }
201             }
202         }
203 
204         /// @brief An array of available SCMEntry's
205         SCMEntry* m_SCMAllocationArray;
206 
207         /// @brief Index, in "SCMAllocationArray", of next free SCMEntry
208         unsigned m_SCMArrayLocation;
209 
210         /// @brief Vector containing all the "SCMAllocationArray" arrays which were allocated
211         llvm::SmallVector<SCMEntry*, 4> m_SCMArrays;
212 
213         /// @brief The DRL (Deferred resolution list).
214         typedef struct DRLEntry
215         {
216             llvm::Value* unresolvedInst;
217             llvm::SmallVector<llvm::Value*, MAX_INPUT_VECTOR_WIDTH>dummyVals;
218         } DRLEntry;
219         llvm::SmallVector<DRLEntry, 4> m_DRL;
220 
221         /*! \name Pre-Scalarization function arguments scan
222          *  \{ */
223 
224          /// @brief Data structure for holding "real" inputs/output of function call
225          //   first - arguments of function
226          //   second - retuns of function. There may be more than one return value, e.g. sincos
227         typedef std::pair< llvm::SmallVector<llvm::Value*, 4>, llvm::SmallVector<llvm::Value*, 4>    > funcRootsVect;
228         /// @brief Some getters which access funcRootsVect and make the code more readable
getReturns(funcRootsVect & FRV)229         static llvm::SmallVectorImpl<llvm::Value*>& getReturns(funcRootsVect& FRV) { return FRV.second; }
getReturns(const funcRootsVect & FRV)230         static const llvm::SmallVectorImpl<llvm::Value*>& getReturns(const funcRootsVect& FRV) { return FRV.second; }
getArgs(funcRootsVect & FRV)231         static llvm::SmallVectorImpl<llvm::Value*>& getArgs(funcRootsVect& FRV) { return FRV.first; }
getArgs(const funcRootsVect & FRV)232         static const llvm::SmallVectorImpl<llvm::Value*>& getArgs(const funcRootsVect& FRV) { return FRV.first; }
233 
234         /// @brief flag for selective scalarization
235         bool m_SelectiveScalarization;
236 
237         /// @brief This holds DataLayout of processed module
238         const llvm::DataLayout* m_pDL;
239 
240         /// @brief This holds all the created dummy functions throughout the lifetime of the pass, and manages their memory
241         llvm::MapVector<llvm::Type*, llvm::Function*> createdDummyFunctions;
242     };
243 
244 } // namespace IGC
245 
246 /// By default (no argument given to this function), vector load/store are kept as is.
247 extern "C" llvm::FunctionPass* createScalarizerPass(bool selectiveScalarization = false);
248