source: CLRX/CLRadeonExtender/trunk/amdasm/AsmRegAlloc.h @ 4120

Last change on this file since 4120 was 4120, checked in by matszpk, 6 months ago

CLRadeonExtender: AsmRegAlloc?: Remove obsolete class Liveness and fix clang warning.

File size: 11.2 KB
Line 
1/*
2 *  CLRadeonExtender - Unofficial OpenCL Radeon Extensions Library
3 *  Copyright (C) 2014-2018 Mateusz Szpakowski
4 *
5 *  This library is free software; you can redistribute it and/or
6 *  modify it under the terms of the GNU Lesser General Public
7 *  License as published by the Free Software Foundation; either
8 *  version 2.1 of the License, or (at your option) any later version.
9 *
10 *  This library is distributed in the hope that it will be useful,
11 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13 *  Lesser General Public License for more details.
14 *
15 *  You should have received a copy of the GNU Lesser General Public
16 *  License along with this library; if not, write to the Free Software
17 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18 */
19
20#ifndef __CLRX_ASMREGALLOC_H__
21#define __CLRX_ASMREGALLOC_H__
22
23#include <CLRX/Config.h>
24#include <iostream>
25#include <vector>
26#include <utility>
27#include <unordered_set>
28#include <unordered_map>
29#include <map>
30#include <algorithm>
31#include <CLRX/utils/Utilities.h>
32#include <CLRX/utils/Containers.h>
33#include <CLRX/amdasm/Assembler.h>
34#include "AsmInternals.h"
35
36using namespace CLRX;
37
38#define ASMREGALLOC_DEBUGDUMP 0
39
40namespace CLRX
41{
42
43typedef AsmRegAllocator::CodeBlock CodeBlock;
44typedef AsmRegAllocator::NextBlock NextBlock;
45typedef AsmRegAllocator::SSAInfo SSAInfo;
46typedef std::pair<const AsmSingleVReg, SSAInfo> SSAEntry;
47typedef AsmRegAllocator::VVarSetEntry VVarSetEntry;
48
49//  BlockIndex
50
51struct CLRX_INTERNAL BlockIndex
52{
53    size_t index;
54    size_t pass;
55   
56    BlockIndex(size_t _index = 0, size_t _pass = 0)
57            : index(_index), pass(_pass)
58    { }
59   
60    bool operator==(const BlockIndex& v) const
61    { return index==v.index && pass==v.pass; }
62    bool operator!=(const BlockIndex& v) const
63    { return index!=v.index || pass!=v.pass; }
64   
65    BlockIndex operator+(size_t p) const
66    { return BlockIndex(index+p, pass); }
67};
68
69};
70
71#if ASMREGALLOC_DEBUGDUMP
72extern CLRX_INTERNAL std::ostream& operator<<(std::ostream& os, const CLRX::BlockIndex& v);
73#endif
74
75namespace std
76{
77
78/// std::hash specialization for CLRX CString
79template<>
80struct hash<BlockIndex>
81{
82    typedef BlockIndex argument_type;    ///< argument type
83    typedef std::size_t result_type;    ///< result type
84   
85    /// a calling operator
86    size_t operator()(const BlockIndex& r1) const
87    {
88        std::hash<size_t> h1;
89        return h1(r1.index) ^ h1(r1.pass);
90    }
91};
92
93}
94
95namespace CLRX
96{
97
98class CLRX_INTERNAL CBlockBitPool: public std::vector<bool>
99{
100public:
101    CBlockBitPool(size_t n = 0, bool v = false) : std::vector<bool>(n<<1, v)
102    { }
103   
104    reference operator[](BlockIndex i)
105    { return std::vector<bool>::operator[](i.index + (i.pass ? (size()>>1) : 0)); }
106    const_reference operator[](BlockIndex i) const
107    { return std::vector<bool>::operator[](i.index + (i.pass ? (size()>>1) : 0)); }
108};
109
110/** Simple cache **/
111
112// map of last SSAId for routine, key - varid, value - last SSA ids
113class CLRX_INTERNAL LastSSAIdMap: public
114            std::unordered_map<AsmSingleVReg, VectorSet<size_t> >
115{
116public:
117    LastSSAIdMap()
118    { }
119   
120    iterator insertSSAId(const AsmSingleVReg& vreg, size_t ssaId)
121    {
122        auto res = insert({ vreg, { ssaId } });
123        if (!res.second)
124            res.first->second.insertValue(ssaId);
125        return res.first;
126    }
127   
128    void eraseSSAId(const AsmSingleVReg& vreg, size_t ssaId)
129    {
130        auto it = find(vreg);
131        if (it != end())
132             it->second.eraseValue(ssaId);
133    }
134   
135    size_t weight() const
136    { return size(); }
137};
138
139typedef std::unordered_map<AsmSingleVReg, BlockIndex> SVRegBlockMap;
140
141class CLRX_INTERNAL SVRegMap: public std::unordered_map<AsmSingleVReg, size_t>
142{
143public:
144    SVRegMap()
145    { }
146   
147    size_t weight() const
148    { return size(); }
149};
150
151typedef LastSSAIdMap RBWSSAIdMap;
152typedef std::unordered_map<BlockIndex, VectorSet<BlockIndex> > SubrLoopsMap;
153
154struct CLRX_INTERNAL RetSSAEntry
155{
156    std::vector<BlockIndex> routines;
157    VectorSet<size_t> ssaIds;
158    size_t prevSSAId; // for curSSAId
159};
160
161typedef std::unordered_map<AsmSingleVReg, RetSSAEntry> RetSSAIdMap;
162
163struct CLRX_INTERNAL LoopSSAIdMap
164{
165    LastSSAIdMap ssaIdMap;
166    bool passed;
167};
168
169struct CLRX_INTERNAL RoutineData
170{
171    // rbwSSAIdMap - read before write SSAId's map
172    SVRegMap rbwSSAIdMap;
173    SVRegMap origRbwSSAIdMap;
174    LastSSAIdMap curSSAIdMap;
175    LastSSAIdMap lastSSAIdMap;
176    // key - loop block, value - last ssaId map for loop end
177    std::unordered_map<BlockIndex, LoopSSAIdMap> loopEnds;
178    bool notFirstReturn;
179    bool generated;
180    size_t weight_;
181   
182    RoutineData() : notFirstReturn(false), generated(false), weight_(0)
183    { }
184   
185    void calculateWeight()
186    {
187        weight_ = rbwSSAIdMap.size() + lastSSAIdMap.weight();
188        for (const auto& entry: loopEnds)
189            weight_ += entry.second.ssaIdMap.weight();
190    }
191   
192    size_t weight() const
193    { return weight_; }
194};
195
196struct CLRX_INTERNAL LastAccessBlockPos
197{
198    size_t blockIndex;
199    bool inSubroutines; // true if last access in some called subroutine
200   
201    bool operator==(const LastAccessBlockPos& v) const
202    { return blockIndex==v.blockIndex; }
203    bool operator!=(const LastAccessBlockPos& v) const
204    { return blockIndex!=v.blockIndex; }
205};
206
207struct CLRX_INTERNAL LastVRegStackPos
208{
209    size_t stackPos;
210    bool inSubroutines; // true if last access in some called subroutine
211};
212
213typedef std::unordered_map<AsmSingleVReg, VectorSet<LastAccessBlockPos> > LastAccessMap;
214typedef std::unordered_map<AsmSingleVReg, LastAccessBlockPos> RoutineCurAccessMap;
215class CLRX_INTERNAL LastStackPosMap
216        : public std::unordered_map<AsmSingleVReg, LastVRegStackPos>
217{
218public:
219    LastStackPosMap()
220    { }
221   
222    size_t weight() const
223    { return size(); }
224};
225
226// Routine data for createLivenesses - holds svreg read before writes and
227// last access of the svregs
228struct CLRX_INTERNAL RoutineDataLv
229{
230    SVRegMap rbwSSAIdMap;
231    // holds all vreg SSA's used in routine (used while creating call point)
232    // includes subroutines called in this routines
233    std::unordered_set<size_t> allSSAs[MAX_REGTYPES_NUM];
234    // key - svreg, value - list of the last codeblocks where is svreg
235    LastAccessMap lastAccessMap;
236};
237
238// used by createSSAData
239struct CLRX_INTERNAL FlowStackEntry
240{
241    BlockIndex blockIndex;
242    size_t nextIndex;
243    bool isCall;
244    bool haveReturn;
245    RetSSAIdMap prevRetSSAIdSets;
246};
247
248// used by resolveSSAConflicts
249struct CLRX_INTERNAL FlowStackEntry2
250{
251    size_t blockIndex;
252    size_t nextIndex;
253};
254
255
256// used by createLivenesses
257struct CLRX_INTERNAL FlowStackEntry3
258{
259    size_t blockIndex;
260    size_t nextIndex;
261    bool isCall;
262};
263
264struct CLRX_INTERNAL FlowStackEntry4
265{
266    size_t blockIndex;
267    size_t nextIndex;
268    bool isCall;
269    RoutineCurAccessMap prevCurSVRegMap;
270};
271
272struct CLRX_INTERNAL CallStackEntry
273{
274    BlockIndex callBlock; // index
275    size_t callNextIndex; // index of call next
276    BlockIndex routineBlock;    // routine block
277};
278
279struct CLRX_INTERNAL CallStackEntry2
280{
281    size_t callBlock; // index
282    size_t callNextIndex; // index of call next
283    size_t routineBlock;    // routine block
284};
285
286typedef std::unordered_map<BlockIndex, RoutineData> RoutineMap;
287typedef std::unordered_map<BlockIndex, RoutineDataLv> RoutineLvMap;
288
289typedef std::unordered_map<size_t, std::pair<size_t, size_t> > PrevWaysIndexMap;
290
291class CLRX_INTERNAL ResSecondPointsToCache: public CBlockBitPool
292{
293public:
294    explicit ResSecondPointsToCache(size_t n) : CBlockBitPool(n<<1, false)
295    { }
296   
297    void increase(BlockIndex ip)
298    {
299        const size_t i = ip.index + (ip.pass ? (size()>>2) : 0);
300        if ((*this)[i<<1])
301            (*this)[(i<<1)+1] = true;
302        else
303            (*this)[i<<1] = true;
304    }
305   
306    cxuint count(BlockIndex ip) const
307    {
308        const size_t i = ip.index + (ip.pass ? (size()>>2) : 0);
309        return cxuint((*this)[i<<1]) + (*this)[(i<<1)+1];
310    }
311};
312
313typedef AsmRegAllocator::SSAReplace SSAReplace; // first - orig ssaid, second - dest ssaid
314typedef AsmRegAllocator::SSAReplacesMap SSAReplacesMap;
315
316#if ASMREGALLOC_DEBUGDUMP
317#define ARDOut std::cout
318#else
319struct NoOutput
320{
321    template<typename T>
322    NoOutput& operator<<(const T& v)
323    { return *this; }
324};
325
326#define ARDOut NoOutput()
327#endif
328
329struct Liveness
330{
331    std::map<size_t, size_t> l;
332   
333    Liveness() { }
334   
335    void clear()
336    { l.clear(); }
337   
338    void join(std::map<size_t, size_t>::iterator it)
339    {
340        if (it != l.begin())
341        {
342            auto prevIt = it;
343            --prevIt;
344            if (prevIt->second >= it->first)
345            {
346                // join with previous region
347                prevIt->second = std::max(it->second, prevIt->second);
348                l.erase(it);
349                it = prevIt;
350            }
351        }
352       
353        auto nextIt = it;
354        ++nextIt;
355        if (nextIt != l.end())
356        {
357            if (nextIt->first <= it->second)
358            {
359                // join with next region
360                it->second = std::max(it->second, nextIt->second);
361                l.erase(nextIt);
362            }
363        }
364    }
365   
366    void expand(size_t k)
367    {
368        auto it = l.upper_bound(k);
369        if (it != l.begin())
370            --it;
371        else // do nothing
372            return;
373        // try expand, lower new bound, then use older
374        it->second = std::max(it->second, k+1);
375        join(it);
376    }
377    void newRegion(size_t k)
378    { join(l.insert(std::make_pair(k, k)).first); }
379   
380    void insert(size_t k, size_t k2)
381    {
382        auto res = l.insert(std::make_pair(k, k2));
383        if (!res.second)
384            res.first->second = std::max(res.first->second, k2);
385        join(res.first);
386    }
387   
388    bool contain(size_t t) const
389    {
390        if (l.empty())
391            return false;
392        auto it = l.lower_bound(t);
393        if (it==l.begin() && it->first>t)
394            return false;
395        if (it==l.end() || it->first>t)
396            --it;
397        return it->first<=t && t<it->second;
398    }
399};
400
401typedef AsmRegAllocator::VarIndexMap VarIndexMap;
402
403typedef std::deque<FlowStackEntry3>::const_iterator FlowStackCIter;
404
405// key - singlevreg, value - code block chain
406typedef std::unordered_map<AsmSingleVReg, std::vector<LastVRegStackPos> > LastVRegMap;
407
408struct CLRX_INTERNAL LiveBlock
409{
410    size_t start;
411    size_t end;
412    size_t vidx;
413   
414    bool operator==(const LiveBlock& b) const
415    { return start==b.start && end==b.end && vidx==b.vidx; }
416   
417    bool operator<(const LiveBlock& b) const
418    { return start<b.start || (start==b.start &&
419            (end<b.end || (end==b.end && vidx<b.vidx))); }
420};
421
422typedef AsmRegAllocator::LinearDep LinearDep;
423typedef std::unordered_map<size_t, LinearDep> LinearDepMap;
424
425typedef AsmRegAllocator::InterGraph InterGraph;
426
427struct CLRX_INTERNAL SDOLDOCompare
428{
429    const InterGraph& interGraph;
430    const Array<size_t>& sdoCounts;
431   
432    SDOLDOCompare(const InterGraph& _interGraph, const Array<size_t>&_sdoCounts)
433        : interGraph(_interGraph), sdoCounts(_sdoCounts)
434    { }
435   
436    bool operator()(size_t a, size_t b) const
437    {
438        if (sdoCounts[a] > sdoCounts[b])
439            return true;
440        return interGraph[a].size() > interGraph[b].size();
441    }
442};
443
444};
445
446#endif
Note: See TracBrowser for help on using the repository browser.