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

Last change on this file since 4169 was 4169, checked in by matszpk, 14 months ago

CLRadeonExtender: AsmRegAlloc?: Fixed creating routine data (for livenesses) for two recursion passes.

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