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 /*========================== begin_copyright_notice ============================
10 
11 This file is distributed under the University of Illinois Open Source License.
12 See LICENSE.TXT for details.
13 
14 ============================= end_copyright_notice ===========================*/
15 
16 //===-------- DeSSA.hpp - divide phi variables into congruent class -------===//
17 //
18 //  Intel Extention to LLVM core
19 //===----------------------------------------------------------------------===//
20 //
21 // This pass is originated from the StrongPHIElimination on the machine-ir.
22 // We have adopted it to work on llvm-ir. Also note that we have changed it
23 // from a transformation to an analysis, meaning which only divides phi-vars
24 // into congruent classes, and does NOT insert the copies. A separate code-gen
25 // pass can use this analysis to emit non-ssa target code.
26 //
27 //===----------------------------------------------------------------------===//
28 
29 #pragma once
30 
31 #include "Compiler/CISACodeGen/LiveVars.hpp"
32 #include "Compiler/CISACodeGen/WIAnalysis.hpp"
33 #include "Compiler/CISACodeGen/PatternMatchPass.hpp"
34 #include "Compiler/MetaDataUtilsWrapper.h"
35 #include "common/LLVMWarningsPush.hpp"
36 #include <llvm/Pass.h>
37 #include <llvm/IR/Function.h>
38 #include <llvm/IR/Instruction.h>
39 #include <llvm/IR/Instructions.h>
40 #include <llvm/Support/Allocator.h>
41 #include <llvm/IR/CFG.h>
42 #include <llvm/Support/Debug.h>
43 #include <llvm/IR/Dominators.h>
44 #include <llvm/ADT/DenseMap.h>
45 #include <llvm/ADT/MapVector.h>
46 #include <llvm/ADT/SetVector.h>
47 #include <llvm/ADT/SmallSet.h>
48 #include <llvm/ADT/SmallVector.h>
49 #include <llvm/ADT/DenseSet.h>
50 #include "common/LLVMWarningsPop.hpp"
51 #include <map>
52 #include "Probe/Assertion.h"
53 
54 namespace IGC {
55 
56     class CShader;
57     class CVariable;
58     class CodeGenPatternMatch;
59     class CodeGenContextWrapper;
60 
61     class DeSSA : public llvm::FunctionPass {
62     public:
63         static char ID; // Pass identification, replacement for typeid
64 
65         DeSSA();
getAnalysisUsage(llvm::AnalysisUsage & AU) const66         virtual void getAnalysisUsage(llvm::AnalysisUsage& AU) const override {
67             AU.setPreservesAll();
68             AU.addRequired<llvm::DominatorTreeWrapperPass>();
69             AU.addRequired<WIAnalysis>();
70             AU.addRequired<LiveVarsAnalysis>();
71             AU.addRequired<CodeGenPatternMatch>();
72             AU.addRequired<llvm::LoopInfoWrapperPass>();
73             AU.addRequired<MetaDataUtilsWrapper>();
74             AU.addRequired<CodeGenContextWrapper>();
75         }
76         bool runOnFunction(llvm::Function&) override;
77 
releaseMemory()78         virtual void releaseMemory() override {
79             Allocator.Reset();
80             PHISrcDefs.clear();
81             PHISrcArgs.clear();
82             RegNodeMap.clear();
83             InsEltMap.clear();
84             AliasMap.clear();
85         }
86 
getPassName() const87         virtual llvm::StringRef getPassName() const  override {
88             return "DeSSA";
89         }
90 
91         /// Look at the phi-union and insert-element union, find the root value.
92         /// return 0 if reg is isolated, and not in any insert-element union
93         llvm::Value* getRootValue(llvm::Value*, e_alignment* pAlign = 0) const;
94 
95         bool isIsolated(llvm::Value*) const;
96 
isUniform(llvm::Value * v) const97         bool isUniform(llvm::Value* v) const {
98             return (WIA->isUniform(v));
99         }
100 
101         void getAllValuesInCongruentClass(
102             llvm::Value* V,
103             llvm::SmallVector<llvm::Value*, 8> & ValsInCC);
104 
105         /// print - print partitions in human readable form
106         virtual void print(llvm::raw_ostream& OS, const llvm::Module* = 0) const override;
107 
108         /// dump - Dump the partitions to dbgs().
109         void dump() const;
110 
111     private:
112         /// This struct represents a single node in the union-find data structure
113         /// representing the variable congruence classes. There is one difference
114         /// from a normal union-find data structure. We steal two bits from the parent
115         /// pointer . One of these bits is used to represent whether the register
116         /// itself has been isolated, and the other is used to represent whether the
117         /// PHI with that register as its destination has been isolated.
118         ///
119         /// Note that this leads to the strange situation where the leader of a
120         /// congruence class may no longer logically be a member, due to being
121         /// isolated.
122         struct Node {
NodeIGC::DeSSA::Node123             Node(llvm::Value* v, int c, e_alignment align)
124                 : parent(this), next(this), prev(this), value(v)
125                 , rank(0), alignment(align), color(c)
126             {
127             }
128 
129             /// Find leader (representative of a congruent class) by path halving
130             Node* getLeader();
131 
132             Node* parent;
133             // double-linked circular list. All values are in the same congruent class
134             // except those that have been isolated.
135             Node* next;
136             Node* prev;
137             llvm::Value* value;
138             unsigned rank;
139             e_alignment alignment;
140 
141             // Unique one for each node. Used to represent the color
142             // (in another word, id or label) of a congruent class.
143             // Start from 1
144             int color;
145         };
146 
147         /// Get the union-root of a register. The root is 0 if the register has been
148         /// isolated.
149         llvm::Value* getRegRoot(llvm::Value*, e_alignment* pAlign = 0) const;
150 
151         // Return color (>0) if V is in a congruent class; return 0 otherwise.
152         // (This is needed during traversal of algo. The color is used as the
153         // reprentative of a congruent class that remains unchanged during traversal.)
154         int getRootColor(llvm::Value* V);
155 
156         // Isolate a register.
157         void isolateReg(llvm::Value*);
158 
159         /// Is it isolated (single-valued congruent class)
isIsolated(Node * N) const160         bool isIsolated(Node* N) const { return (N == N->next); }
161 
162         // Split node from its existing congurent class, and
163         // node itself becomes a new single-value congruent class
164         void splitNode(Node* ND);
165 
166         /// Traverses a basic block, splitting any interferences found between
167         /// registers in the same congruence class. It takes two DenseMaps as
168         /// arguments that it also updates: CurrentDominatingParent, which maps
169         /// a color to the register in that congruence class whose definition was
170         /// most recently seen, and ImmediateDominatingParent, which maps a register
171         /// to the register in the same congruence class that most immediately
172         /// dominates it.
173         ///
174         /// This function assumes that it is being called in a depth-first traversal
175         /// of the dominator tree.
176         void SplitInterferencesForBasicBlock(
177             llvm::BasicBlock*,
178             llvm::DenseMap<int, llvm::Value*>& CurrentDominatingParent,
179             llvm::DenseMap<llvm::Value*, llvm::Value*>& ImmediateDominatingParent);
180 
181         void SplitInterferencesForArgument(
182             llvm::DenseMap<int, llvm::Value*>& CurrentDominatingParent,
183             llvm::DenseMap<llvm::Value*, llvm::Value*>& ImmediateDominatingParent);
184 
185         void SplitInterferencesForAlignment();
186 
187         llvm::DominatorTree* DT;
188         LiveVars* LV;
189         WIAnalysis* WIA;
190         llvm::LoopInfo* LI;
191         CodeGenPatternMatch* CG;
192         const llvm::DataLayout* DL;
193         CodeGenContext* CTX;
194         llvm::Function* m_F;  // Current Function
195 
196         llvm::BumpPtrAllocator Allocator;
197 
198         // Color (label) assigned to each congruent class
199         // start from 1. Make sure each Node has a different
200         // color number.
201         int CurrColor;
202 
203     public:
getLiveVars() const204         LiveVars* getLiveVars() const { return LV; }
205 
206         llvm::MapVector<llvm::Value*, Node*> RegNodeMap;
207 
208         // Maps a basic block to a list of its defs of registers that appear as PHI
209         // sources.
210         llvm::DenseMap<llvm::BasicBlock*, std::vector<llvm::Instruction*> > PHISrcDefs;
211         llvm::SetVector<llvm::Value*> PHISrcArgs;
212 
213         // Maps a color to a pair of a llvm::Instruction* and a virtual register, which
214         // is the operand of that PHI corresponding to the current basic block.
215         llvm::DenseMap<int, std::pair<llvm::Instruction*, llvm::Value*> > CurrentPHIForColor;
216 
217         // Implement reuse for InsertElement only
218         // Hierarchical coalescing:
219         // - step 1, union insert-elements into trees, update the liveness
220         // - step 2, build phi-union, the root of the InsElt-union-tree can be added to the phi-union.
221         // - step 3, detect interferences of every phi-union, a set of insert-elements are associated
222         //           with a single-node in phi-union. When being isolated, they are isolated together
223         llvm::MapVector<llvm::Value*, llvm::Value*> InsEltMap;
224 
225         // Value Alias map
226         //   This is used for maitaining aliases among values. It maps a value, called 'aliaser',
227         //   to its 'aliasee' (denoted as alias(aliaer, aliasee). This map has the following
228         //   properties:
229         //       1. No alias chain, that is, the map does not have both alias(v0, v1) and
230         //          alias(v1, v2) with v0 != V1 != v2.
231         //
232         //          Note that for each aliasee, say V,  alias(V, V) is in map for convenience to
233         //          indicate V is aliasee and to help setup aliasing entry of the map.
234         //       2. The aliasee's liveness info has been updated to be the union of all its aliasers.
235         //          In this way, only aliasee will be used in DeSSA node.
236         //
237         // The DeSSA/Coalescing procedure:
238         //   1. Follow Dominance tree to set up alias map. While setting up alias map,
239         //      update liveness for aliasee.
240         //   2. Make sure InsEltMap only use aliasee
241         //   3. Make sure DeSSA node only use aliasee.
242         llvm::DenseMap<llvm::Value*, llvm::Value*> AliasMap;
243 
244         // If an inst is an aliaser and no need to generate code
245         // due to aliasing, it will be added in this map.
246         llvm::DenseMap<llvm::Value*, int> NoopAliasMap;
247 
248         /// If there is no node for Val, create a new one.
249         void addReg(llvm::Value* Val, e_alignment Align);
250 
getGRFSize() const251         int getGRFSize() const { return CTX->platform.getGRFSize(); }
252 
253         /// union-by-rank:
254         ///   Join the congruence classes of two registers by attaching
255         ///   a shorter tree to a taller tree. If they have the same height,
256         ///   attaching Val2 to Val1. Note that unionRegs() expects that
257         ///   nodes for Val1 and Val2 have been created already.
unionRegs(llvm::Value * Val1,llvm::Value * Val2)258         void unionRegs(llvm::Value* Val1, llvm::Value* Val2) {
259             unionRegs(RegNodeMap[Val1], RegNodeMap[Val2]);
260         }
261 
262         // For a value, return its representative value that is used
263         // to create dessa node, which is its aliasee's InsElt root.
getNodeValue(llvm::Value * V) const264         llvm::Value* getNodeValue(llvm::Value* V) const {
265             llvm::Value* aliasee = getAliasee(V);
266             return getInsEltRoot(aliasee);
267         }
268 
269         llvm::Value* getInsEltRoot(llvm::Value* Val) const;
270         llvm::Value* getAliasee(llvm::Value* V) const;
271         bool isAliasee(llvm::Value* V) const;
272         bool isAliaser(llvm::Value* V) const;
273         bool isNoopAliaser(llvm::Value* V) const;
274         bool isSingleValued(llvm::Value* V) const;
275         bool interfere(llvm::Value* V0, llvm::Value* V1);
276         bool aliasInterfere(llvm::Value* V0, llvm::Value* V1);
277         bool alignInterfere(e_alignment a1, e_alignment a2);
278 
279     private:
280         void CoalesceInsertElementsForBasicBlock(llvm::BasicBlock* blk);
281 
InsEltMapAddValue(llvm::Value * Val)282         void InsEltMapAddValue(llvm::Value* Val) {
283             if (InsEltMap.find(Val) == InsEltMap.end()) {
284                 InsEltMap[Val] = Val;
285             }
286         }
InsEltMapUnionValue(llvm::Value * SrcVal,llvm::Value * DefVal)287         void InsEltMapUnionValue(llvm::Value* SrcVal, llvm::Value* DefVal) {
288             IGC_ASSERT(InsEltMap.find(SrcVal) != InsEltMap.end());
289             InsEltMap[DefVal] = InsEltMap[SrcVal];
290         }
291 
292         void unionRegs(Node* N1, Node* N2);
293         void CoalesceAliasInstForBasicBlock(llvm::BasicBlock* Blk);
294         int checkInsertElementAlias(
295             llvm::InsertElementInst* IEI,
296             llvm::SmallVector<llvm::Value*, 16> & AllIEIs);
297 
298         // Add Val->Val into aliasMap if it is not in the map yet.
299         // Return Val's aliasee.
AddAlias(llvm::Value * Val)300         void AddAlias(llvm::Value* Val) {
301             if (AliasMap.find(Val) == AliasMap.end())
302                 AliasMap[Val] = Val;
303         }
304 
305         // If V is an arg or a needed inst (by patternmatch),
306         // return true; otherwise, return false;
isArgOrNeededInst(llvm::Value * V)307         bool isArgOrNeededInst(llvm::Value* V) {
308             if (llvm::Instruction * I = llvm::dyn_cast<llvm::Instruction>(V))
309             {
310                 return CG->NeedInstruction(*I);
311             }
312             return llvm::isa<llvm::Argument>(V);
313         }
314     };
315 
316     struct MIIndexCompare {
MIIndexCompareIGC::MIIndexCompare317         MIIndexCompare(LiveVars* _lv) : LV(_lv) { }
318 
operator ()IGC::MIIndexCompare319         bool operator()(const llvm::Instruction* LHS, const llvm::Instruction* RHS) const {
320             return LV->getDistance(LHS) < LV->getDistance(RHS);
321         }
322 
323         LiveVars* LV;
324     };
325 
326 } // End CISA namespace
327