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

Last change on this file since 4104 was 4104, checked in by matszpk, 12 months ago

CLRadeonExtender: AsmRegAlloc?: add joinRoutineDataLv (join routines while createRoutineDataLv), add last accesses of svregs to lastAccessMap,
add reverting that changes while returning from code block (createLivenesses).

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