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

Last change on this file since 3995 was 3995, checked in by matszpk, 7 months ago

CLRadeonExtender: AsmRegAlloc?: Move the rest of typedefs and classes from AsmRegAllocSSAData into AsmRegAlloc?.h.
Use size_t block indices in the part that resolving SSA conflicts.

File size: 6.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 <algorithm>
30#include <CLRX/utils/Utilities.h>
31#include <CLRX/utils/Containers.h>
32#include <CLRX/amdasm/Assembler.h>
33#include "AsmInternals.h"
34
35using namespace CLRX;
36
37#define ASMREGALLOC_DEBUGDUMP 0
38
39namespace CLRX
40{
41
42typedef AsmRegAllocator::CodeBlock CodeBlock;
43typedef AsmRegAllocator::NextBlock NextBlock;
44typedef AsmRegAllocator::SSAInfo SSAInfo;
45typedef std::pair<const AsmSingleVReg, SSAInfo> SSAEntry;
46
47//  BlockIndex
48
49struct CLRX_INTERNAL BlockIndex
50{
51    size_t index;
52    size_t pass;
53   
54    BlockIndex(size_t _index = 0, size_t _pass = 0)
55            : index(_index), pass(_pass)
56    { }
57   
58    bool operator==(const BlockIndex& v) const
59    { return index==v.index && pass==v.pass; }
60    bool operator!=(const BlockIndex& v) const
61    { return index!=v.index || pass!=v.pass; }
62   
63    BlockIndex operator+(size_t p) const
64    { return BlockIndex(index+p, pass); }
65};
66
67};
68
69#if ASMREGALLOC_DEBUGDUMP
70extern CLRX_INTERNAL std::ostream& operator<<(std::ostream& os, const CLRX::BlockIndex& v);
71#endif
72
73namespace std
74{
75
76/// std::hash specialization for CLRX CString
77template<>
78struct hash<BlockIndex>
79{
80    typedef BlockIndex argument_type;    ///< argument type
81    typedef std::size_t result_type;    ///< result type
82   
83    /// a calling operator
84    size_t operator()(const BlockIndex& r1) const
85    {
86        std::hash<size_t> h1;
87        return h1(r1.index) ^ h1(r1.pass);
88    }
89};
90
91}
92
93namespace CLRX
94{
95
96class CLRX_INTERNAL CBlockBitPool: public std::vector<bool>
97{
98public:
99    CBlockBitPool(size_t n = 0, bool v = false) : std::vector<bool>(n<<1, v)
100    { }
101   
102    reference operator[](BlockIndex i)
103    { return std::vector<bool>::operator[](i.index + (i.pass ? (size()>>1) : 0)); }
104    const_reference operator[](BlockIndex i) const
105    { return std::vector<bool>::operator[](i.index + (i.pass ? (size()>>1) : 0)); }
106};
107
108/** Simple cache **/
109
110// map of last SSAId for routine, key - varid, value - last SSA ids
111class CLRX_INTERNAL LastSSAIdMap: public
112            std::unordered_map<AsmSingleVReg, VectorSet<size_t> >
113{
114public:
115    LastSSAIdMap()
116    { }
117   
118    iterator insertSSAId(const AsmSingleVReg& vreg, size_t ssaId)
119    {
120        auto res = insert({ vreg, { ssaId } });
121        if (!res.second)
122            res.first->second.insertValue(ssaId);
123        return res.first;
124    }
125   
126    void eraseSSAId(const AsmSingleVReg& vreg, size_t ssaId)
127    {
128        auto it = find(vreg);
129        if (it != end())
130             it->second.eraseValue(ssaId);
131    }
132   
133    size_t weight() const
134    { return size(); }
135};
136
137typedef LastSSAIdMap RBWSSAIdMap;
138typedef std::unordered_map<BlockIndex, VectorSet<BlockIndex> > SubrLoopsMap;
139
140struct CLRX_INTERNAL RetSSAEntry
141{
142    std::vector<BlockIndex> routines;
143    VectorSet<size_t> ssaIds;
144    size_t prevSSAId; // for curSSAId
145};
146
147typedef std::unordered_map<AsmSingleVReg, RetSSAEntry> RetSSAIdMap;
148
149struct CLRX_INTERNAL LoopSSAIdMap
150{
151    LastSSAIdMap ssaIdMap;
152    bool passed;
153};
154
155struct CLRX_INTERNAL RoutineData
156{
157    // rbwSSAIdMap - read before write SSAId's map
158    std::unordered_map<AsmSingleVReg, size_t> rbwSSAIdMap;
159    std::unordered_map<AsmSingleVReg, size_t> origRbwSSAIdMap;
160    LastSSAIdMap curSSAIdMap;
161    LastSSAIdMap lastSSAIdMap;
162    // key - loop block, value - last ssaId map for loop end
163    std::unordered_map<BlockIndex, LoopSSAIdMap> loopEnds;
164    bool notFirstReturn;
165    size_t weight_;
166   
167    RoutineData() : notFirstReturn(false), weight_(0)
168    { }
169   
170    void calculateWeight()
171    {
172        weight_ = rbwSSAIdMap.size() + lastSSAIdMap.weight();
173        for (const auto& entry: loopEnds)
174            weight_ += entry.second.ssaIdMap.weight();
175    }
176   
177    size_t weight() const
178    { return weight_; }
179};
180
181struct CLRX_INTERNAL FlowStackEntry
182{
183    BlockIndex blockIndex;
184    size_t nextIndex;
185    bool isCall;
186    bool haveReturn;
187    RetSSAIdMap prevRetSSAIdSets;
188};
189
190struct CLRX_INTERNAL FlowStackEntry2
191{
192    size_t blockIndex;
193    size_t nextIndex;
194};
195
196struct CLRX_INTERNAL FlowStackEntry3
197{
198    size_t blockIndex;
199    size_t nextIndex;
200    bool isCall;
201    RetSSAIdMap prevRetSSAIdSets;
202};
203
204
205struct CLRX_INTERNAL CallStackEntry
206{
207    BlockIndex callBlock; // index
208    size_t callNextIndex; // index of call next
209    BlockIndex routineBlock;    // routine block
210};
211
212typedef std::unordered_map<BlockIndex, RoutineData> RoutineMap;
213
214typedef std::unordered_map<size_t, std::pair<size_t, size_t> > PrevWaysIndexMap;
215
216class CLRX_INTERNAL ResSecondPointsToCache: public CBlockBitPool
217{
218public:
219    explicit ResSecondPointsToCache(size_t n) : CBlockBitPool(n<<1, false)
220    { }
221   
222    void increase(BlockIndex ip)
223    {
224        const size_t i = ip.index + (ip.pass ? (size()>>2) : 0);
225        if ((*this)[i<<1])
226            (*this)[(i<<1)+1] = true;
227        else
228            (*this)[i<<1] = true;
229    }
230   
231    cxuint count(BlockIndex ip) const
232    {
233        const size_t i = ip.index + (ip.pass ? (size()>>2) : 0);
234        return cxuint((*this)[i<<1]) + (*this)[(i<<1)+1];
235    }
236};
237
238typedef AsmRegAllocator::SSAReplace SSAReplace; // first - orig ssaid, second - dest ssaid
239typedef AsmRegAllocator::SSAReplacesMap SSAReplacesMap;
240
241#if ASMREGALLOC_DEBUGDUMP
242#define ARDOut std::cout
243#else
244struct NoOutput
245{
246    template<typename T>
247    NoOutput& operator<<(const T& v)
248    { return *this; }
249};
250
251#define ARDOut NoOutput()
252#endif
253
254};
255
256#endif
Note: See TracBrowser for help on using the repository browser.