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 // Estimate the register pressure at a program point.
17 
18 #pragma once
19 
20 #include "common/LLVMWarningsPush.hpp"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/Value.h"
24 #include "llvm/Pass.h"
25 #include <llvm/IR/InstVisitor.h>
26 #include "llvm/Analysis/LoopInfo.h"
27 #include <llvmWrapper/IR/DerivedTypes.h>
28 #include "common/LLVMWarningsPop.hpp"
29 #include "Compiler/IGCPassSupport.h"
30 #include "Compiler/CISACodeGen/WIAnalysis.hpp"
31 #include "Probe/Assertion.h"
32 
33 namespace IGC
34 {
35     constexpr unsigned int SIMD_PRESSURE_MULTIPLIER = 8;
36     constexpr unsigned int OVERALL_PRESSURE_UPBOUND = 512;
37 
38     class RegisterPressureEstimate : public llvm::FunctionPass
39     {
40     public:
41         static char ID;
RegisterPressureEstimate()42         RegisterPressureEstimate()
43             : FunctionPass(ID), m_DL(nullptr), m_pFunc(nullptr), LI(nullptr),
44             WI(nullptr), m_available(false), MaxAssignedNumber(0)
45         {
46             initializeRegisterPressureEstimatePass(*llvm::PassRegistry::getPassRegistry());
47         }
48 
49         /// @brief  Provides name of pass
getPassName() const50         virtual llvm::StringRef getPassName() const override
51         {
52             return "RegisterPressureEstimate";
53         }
54 
55         void getAnalysisUsage(llvm::AnalysisUsage& AU) const override;
56         bool runOnFunction(llvm::Function& F) override;
57 
doFinalization(llvm::Module & F)58         bool doFinalization(llvm::Module& F) override
59         {
60             for (auto Item : m_pLiveRangePool)
61                 delete Item;
62             m_pLiveRangePool.clear();
63             return false;
64         }
65         /// \brief Describe a value is live at Begin and dead right after End.
66         struct Segment
67         {
68             unsigned Begin;
69             unsigned End;
SegmentIGC::RegisterPressureEstimate::Segment70             Segment() {}
SegmentIGC::RegisterPressureEstimate::Segment71             Segment(unsigned Begin, unsigned End) : Begin(Begin), End(End) {}
operator <IGC::RegisterPressureEstimate::Segment72             bool operator<(const Segment& Other) const
73             {
74                 if (Begin != Other.Begin)
75                 {
76                     return Begin < Other.Begin;
77                 }
78                 return End < Other.End;
79             }
80         };
81 
82         /// \brief A live range consists of a list of live segments.
83         struct LiveRange
84         {
85             /// Empty live range.
LiveRangeIGC::RegisterPressureEstimate::LiveRange86             LiveRange() {}
87 
88             LiveRange(const LiveRange&) = delete;
89 
90             /// \brief Shorten a segment.
91             void setBegin(unsigned B);
92 
93             /// \brief Append a new segment.
addSegmentIGC::RegisterPressureEstimate::LiveRange94             void addSegment(unsigned B, unsigned E)
95             {
96                 if (B < E)
97                 {
98                     Segments.push_back(Segment(B, E));
99                 }
100             }
101 
102             /// \brief Sort segments and merge them.
103             void sortAndMerge();
104 
105             /// \brief Check whether N is contained in this live range.
containsIGC::RegisterPressureEstimate::LiveRange106             bool contains(unsigned N) const
107             {
108                 // Segments are sorted.
109                 for (auto& Seg : Segments)
110                 {
111                     if (N < Seg.Begin)
112                     {
113                         return false;
114                     }
115                     if (N < Seg.End)
116                     {
117                         return true;
118                     }
119                 }
120                 // N is out of range.
121                 return false;
122             }
123 
124             void dump() const;
125             void print(llvm::raw_ostream& OS) const;
126             llvm::SmallVector<Segment, 8> Segments;
127         };
128 
getOrCreateLiveRange(llvm::Value * V)129         LiveRange* getOrCreateLiveRange(llvm::Value* V)
130         {
131             auto Iter = m_pLiveRanges.find(V);
132             if (Iter != m_pLiveRanges.end())
133             {
134                 return Iter->second;
135             }
136 
137             auto Result = m_pLiveRanges.insert(std::make_pair(V, createLiveRange()));
138             return Result.first->second;
139         }
140 
getLiveRangeOrNull(llvm::Value * V)141         LiveRange* getLiveRangeOrNull(llvm::Value* V)
142         {
143             auto Iter = m_pLiveRanges.find(V);
144             if (Iter != m_pLiveRanges.end())
145             {
146                 return Iter->second;
147             }
148             return nullptr;
149         }
150 
createLiveRange(llvm::Value * V)151         void createLiveRange(llvm::Value* V)
152         {
153             IGC_ASSERT(!m_pLiveRanges.count(V));
154             m_pLiveRanges[V] = createLiveRange();
155         }
156 
157         /// \brief Cleanup live ranges.
mergeLiveRanges()158         void mergeLiveRanges()
159         {
160             for (auto& Item : m_pLiveRanges)
161             {
162                 Item.second->sortAndMerge();
163             }
164         }
165 
166         /// \brief Assign a number to each instruction in a function.
167         void assignNumbers();
168 
169         /// \brief Print instruction list with numbering.
170         void printNumbering(llvm::raw_ostream& OS);
171         void dumpNumbering();
172 
173         /// \brief Used to fetch number on instructions and BB
174         unsigned getAssignedNumberForInst(llvm::Instruction*);
getMaxAssignedNumberForFunction()175         unsigned getMaxAssignedNumberForFunction() { return MaxAssignedNumber; }
176         unsigned getMaxAssignedNumberForBB(llvm::BasicBlock*);
177         unsigned getMinAssignedNumberForBB(llvm::BasicBlock* pBB);
178 
179         /// \brief Print live ranges.
180         void printLiveRanges(llvm::raw_ostream& OS);
181         void dumpLiveRanges();
182 
183         /// \brief Scan a function and build live ranges for all values of interest. A
184         /// live range consists of non-overlapping live intervals [i, j) where i is
185         /// the label this value starts to live and j is the label where it ends
186         /// living. This value may still be used at j but it does not interfere with
187         /// the value defined at j. Thus intervals are open on the right-hand side.
188         /// The return value of true indicates that live ranges are available for use.
189         bool buildLiveIntervals(bool RemoveLR = false);
190 
191         /// \brief Return the register pressure for the whole function.
192         unsigned getMaxRegisterPressure() const;
193 
194         /// \brief Return the register pressure for a basic block.
195         unsigned getMaxRegisterPressure(llvm::BasicBlock* BB) const;
196 
197         void printRegisterPressureInfo(bool Detailed = false,
198             const char* msg = "") const;
199 
isAvailable() const200         bool isAvailable() const { return m_available; }
201 
clear(bool RemoveLR)202         void clear(bool RemoveLR)
203         {
204             for (auto& Item : m_pLiveRanges)
205                 Item.second->Segments.clear();
206             if (RemoveLR)
207                 m_pLiveRanges.clear();
208             for (auto Item : m_pLiveRangePool)
209                 delete Item;
210             m_pLiveRangePool.clear();
211         }
212 
213         unsigned getRegisterPressureForInstructionFromRPMap(unsigned number) const;
214 
215         void buildRPMapPerInstruction();
216 
217     private:
218         /// \brief Return the register pressure at location specified by Inst.
219         unsigned getRegisterPressure(llvm::Instruction* Inst) const;
220 
getValueBytes(llvm::Value * V) const221         unsigned getValueBytes(llvm::Value* V) const
222         {
223             auto Ty = V->getType();
224             if (Ty->isVoidTy())
225                 return 0;
226             auto VTy = llvm::dyn_cast<IGCLLVM::FixedVectorType>(Ty);
227             auto eltTy = VTy ? VTy->getElementType() : Ty;
228             uint32_t nelts = VTy ? int_cast<uint32_t>(VTy->getNumElements()) : 1;
229             uint32_t eltBits = (uint32_t)m_DL->getTypeSizeInBits(eltTy);
230             uint32_t nBytes = nelts * ((eltBits + 7) / 8);
231             unsigned int simdness =
232                 (WI && WI->isUniform(V)) ? 1 : SIMD_PRESSURE_MULTIPLIER;
233             return simdness * nBytes;
234         }
235 
createLiveRange()236         LiveRange* createLiveRange()
237         {
238             LiveRange* LR = new LiveRange();
239             m_pLiveRangePool.push_back(LR);
240             return LR;
241         }
242 
243     private:
244         const llvm::DataLayout* m_DL;
245         /// The function being analyzed.
246         llvm::Function* m_pFunc;
247 
248         /// The loop info object.
249         llvm::LoopInfo* LI;
250 
251         /// uniform analysis object
252         WIAnalysis* WI;
253 
254         /// Each instruction gets an ID.
255         llvm::DenseMap<llvm::Value*, unsigned> m_pNumbers;
256 
257         /// The value to live range map.
258         std::map<llvm::Value*, LiveRange*> m_pLiveRanges;
259 
260         /// To check if live range info is available
261         bool m_available;
262 
263         std::vector<LiveRange*> m_pLiveRangePool;
264 
265         /// the max assigned number for live-range
266         unsigned int MaxAssignedNumber;
267 
268         llvm::DenseMap<unsigned, unsigned> m_pRegisterPressureByInstruction;
269     };
270 } // namespace IGC
271