source: CLRX/CLRadeonExtender/trunk/tests/amdasm/AsmRegAlloc2.cpp @ 3998

Last change on this file since 3998 was 3998, checked in by matszpk, 15 months ago

CLRadeonExtender: AsmRegAlloc?: Add second testcase (SSAReplaces).

File size: 17.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#include <CLRX/Config.h>
21#include <algorithm>
22#include <iostream>
23#include <sstream>
24#include <string>
25#include <vector>
26#include <cstring>
27#include <CLRX/utils/Utilities.h>
28#include <CLRX/amdasm/Assembler.h>
29#include <CLRX/utils/Containers.h>
30#include "../TestUtils.h"
31#include "AsmRegAlloc.h"
32
33using namespace CLRX;
34
35struct AsmApplySSAReplacesCase
36{
37    Array<CCodeBlock2> inCodeBlocks;
38    Array<std::pair<TestSingleVReg2, Array<SSAReplace> > > inSSAReplaces;
39    Array<CCodeBlock2> codeBlocks; // expected code blocks
40};
41
42static const AsmApplySSAReplacesCase ssaApplyReplacesCasesTbl[] =
43{
44    {   // 0 - first testcase
45        // 16 - trick - SSA replaces beyond visited point
46        {
47            // block 0 - start
48            { 0, 8,
49                { },
50                {
51                    { { "", 4 }, SSAInfo(0, 0, 0, 0, 0, true) },
52                    { { "", 5 }, SSAInfo(0, 0, 0, 0, 0, true) },
53                    { { "sa", 2 }, SSAInfo(0, 1, 1, 1, 1, false) },
54                    { { "sa", 3 }, SSAInfo(0, 1, 1, 1, 1, false) }
55                }, false, false, false },
56            // block 1 - loop
57            { 8, 16,
58                { { 2, false }, { 4, false } },
59                {
60                    { { "sa", 2 }, SSAInfo(1, 2, 2, 2, 1, true) },
61                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
62                }, false, false, false },
63            // block 2 - loop part 2
64            { 16, 24,
65                { { 1, false }, { 3, false } },
66                {
67                    { { "sa", 2 }, SSAInfo(2, SIZE_MAX, 3, SIZE_MAX, 0, true) },
68                    { { "sa", 3 }, SSAInfo(1, 2, 2, 2, 1, false) },
69                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
70                }, false, false, false },
71            // block 3 - end 2
72            { 24, 28,
73                { },
74                { }, false, false, true },
75            // block 4 - end
76            { 28, 36,
77                { },
78                {
79                    { { "sa", 3 }, SSAInfo(1, 3, 3, 3, 1, true) },
80                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
81                }, false, false, true }
82        },
83        {
84            { { "sa", 2 }, { { 2, 1 } } },
85            // must be
86            { { "sa", 3 }, { { 2, 1 } } }
87        },
88        // expected code blocks
89        {
90            // block 0 - start
91            { 0, 8,
92                { },
93                {
94                    { { "", 4 }, SSAInfo(0, 0, 0, 0, 0, true) },
95                    { { "", 5 }, SSAInfo(0, 0, 0, 0, 0, true) },
96                    { { "sa", 2 }, SSAInfo(0, 1, 1, 1, 1, false) },
97                    { { "sa", 3 }, SSAInfo(0, 1, 1, 1, 1, false) }
98                }, false, false, false },
99            // block 1 - loop
100            { 8, 16,
101                { { 2, false }, { 4, false } },
102                {
103                    { { "sa", 2 }, SSAInfo(1, 1, 2, 1, 1, true) },
104                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
105                }, false, false, false },
106            // block 2 - loop part 2
107            { 16, 24,
108                { { 1, false }, { 3, false } },
109                {
110                    { { "sa", 2 }, SSAInfo(1, SIZE_MAX, 3, SIZE_MAX, 0, true) },
111                    { { "sa", 3 }, SSAInfo(1, 1, 2, 1, 1, false) },
112                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
113                }, false, false, false },
114            // block 3 - end 2
115            { 24, 28,
116                { },
117                { }, false, false, true },
118            // block 4 - end
119            { 28, 36,
120                { },
121                {
122                    { { "sa", 3 }, SSAInfo(1, 3, 3, 3, 1, true) },
123                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
124                }, false, false, true }
125        }
126    },
127    {   // 1 - second testcase
128        // 13 - yet another branch example
129        {
130            // block 0
131            { 0, 12,
132                { { 1, false }, { 2, false }, { 4, false }, { 6, false } },
133                {
134                    { { "", 0 }, SSAInfo(0, 0, 0, 0, 0, true) },
135                    { { "", 1 }, SSAInfo(0, 0, 0, 0, 0, true) },
136                    { { "", 4 }, SSAInfo(0, 0, 0, 0, 0, true) },
137                    { { "", 5 }, SSAInfo(0, 0, 0, 0, 0, true) },
138                    { { "sa", 2 }, SSAInfo(0, 1, 1, 1, 1, false) },
139                    { { "sa", 3 }, SSAInfo(0, 1, 1, 1, 1, false) }
140                }, false, false, false },
141            // block 1 - b0
142            { 12, 24,
143                { },
144                {
145                    { { "sa", 2 }, SSAInfo(1, 2, 2, 2, 1, true) },
146                    { { "sa", 3 }, SSAInfo(1, 2, 2, 2, 1, true) },
147                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
148                }, false, false, true },
149            // block 2 - b1
150            { 24, 32,
151                { },
152                {
153                    { { "sa", 2 }, SSAInfo(1, 3, 3, 3, 1, true) },
154                    { { "sa", 3 }, SSAInfo(1, 3, 3, 3, 1, true) },
155                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
156                }, false, false, false },
157            // block 3 - b1x
158            { 32, 40,
159                { { 1, false } },
160                {
161                    { { "sa", 2 }, SSAInfo(3, 4, 4, 4, 1, true) },
162                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
163                }, false, false, true },
164            // block 4 - b2
165            { 40, 48,
166                { },
167                {
168                    { { "sa", 2 }, SSAInfo(1, 5, 5, 5, 1, true) },
169                    { { "sa", 3 }, SSAInfo(1, 4, 4, 4, 1, true) },
170                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
171                }, false, false, false },
172            // block 5 - b2x
173            { 48, 56,
174                { { 3, false } },
175                {
176                    { { "sa", 2 }, SSAInfo(5, 6, 6, 6, 1, true) },
177                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
178                }, false, false, true },
179            // block 6 - b3
180            { 56, 68,
181                { { 5, false } },
182                {
183                    { { "sa", 2 }, SSAInfo(1, 7, 7, 7, 1, true) },
184                    { { "sa", 3 }, SSAInfo(1, 5, 5, 5, 1, true) },
185                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
186                }, false, false, true }
187        },
188        {   // SSA replaces
189            { { "sa", 2 }, { { 4, 1 }, { 6, 3 }, { 7, 5 } } },
190            { { "sa", 3 }, { { 3, 1 }, { 4, 1 }, { 5, 1 } } }
191        },
192        // expected blocks
193        {
194            // block 0
195            { 0, 12,
196                { { 1, false }, { 2, false }, { 4, false }, { 6, false } },
197                {
198                    { { "", 0 }, SSAInfo(0, 0, 0, 0, 0, true) },
199                    { { "", 1 }, SSAInfo(0, 0, 0, 0, 0, true) },
200                    { { "", 4 }, SSAInfo(0, 0, 0, 0, 0, true) },
201                    { { "", 5 }, SSAInfo(0, 0, 0, 0, 0, true) },
202                    { { "sa", 2 }, SSAInfo(0, 1, 1, 1, 1, false) },
203                    { { "sa", 3 }, SSAInfo(0, 1, 1, 1, 1, false) }
204                }, false, false, false },
205            // block 1 - b0
206            { 12, 24,
207                { },
208                {
209                    { { "sa", 2 }, SSAInfo(1, 2, 2, 2, 1, true) },
210                    { { "sa", 3 }, SSAInfo(1, 2, 2, 2, 1, true) },
211                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
212                }, false, false, true },
213            // block 2 - b1
214            { 24, 32,
215                { },
216                {
217                    { { "sa", 2 }, SSAInfo(1, 3, 3, 3, 1, true) },
218                    { { "sa", 3 }, SSAInfo(1, 1, 3, 1, 1, true) },
219                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
220                }, false, false, false },
221            // block 3 - b1x
222            { 32, 40,
223                { { 1, false } },
224                {
225                    { { "sa", 2 }, SSAInfo(3, 1, 4, 1, 1, true) },
226                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
227                }, false, false, true },
228            // block 4 - b2
229            { 40, 48,
230                { },
231                {
232                    { { "sa", 2 }, SSAInfo(1, 5, 5, 5, 1, true) },
233                    { { "sa", 3 }, SSAInfo(1, 1, 4, 1, 1, true) },
234                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
235                }, false, false, false },
236            // block 5 - b2x
237            { 48, 56,
238                { { 3, false } },
239                {
240                    { { "sa", 2 }, SSAInfo(5, 3, 6, 3, 1, true) },
241                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
242                }, false, false, true },
243            // block 6 - b3
244            { 56, 68,
245                { { 5, false } },
246                {
247                    { { "sa", 2 }, SSAInfo(1, 5, 7, 5, 1, true) },
248                    { { "sa", 3 }, SSAInfo(1, 1, 5, 1, 1, true) },
249                    { { "sa", 4 }, SSAInfo(0, SIZE_MAX, 1, SIZE_MAX, 0, true) }
250                }, false, false, true }
251        }
252    }
253};
254
255std::ostream& operator<<(std::ostream& os, const TestSingleVReg& vreg)
256{
257    if (!vreg.name.empty())
258        os << vreg.name << "[" << vreg.index << "]";
259    else
260        os << "@REG[" << vreg.index << "]";
261    return os;
262}
263
264static TestSingleVReg getTestSingleVReg(const AsmSingleVReg& vr,
265        const std::unordered_map<const AsmRegVar*, CString>& rvMap)
266{
267    if (vr.regVar == nullptr)
268        return { "", vr.index };
269   
270    auto it = rvMap.find(vr.regVar);
271    if (it == rvMap.end())
272        throw Exception("getTestSingleVReg: RegVar not found!!");
273    return { it->second, vr.index };
274}
275
276static void testApplySSAReplaces(cxuint i, const AsmApplySSAReplacesCase& testCase)
277{
278    std::istringstream input("");
279    Assembler assembler("test.s", input, ASM_ALL&~ASM_ALTMACRO,
280                    BinaryFormat::RAWCODE, GPUDeviceType::CAPE_VERDE);
281   
282    std::unordered_map<CString, AsmRegVar> regVars;
283    std::vector<CodeBlock> inCodeBlocks;
284    // generate input code blocks
285    for (size_t i = 0; i < testCase.inCodeBlocks.size(); i++)
286    {
287        const CCodeBlock2& cc = testCase.inCodeBlocks[i];
288        CodeBlock inCodeBlock{ cc.start, cc.end,
289            std::vector<AsmRegAllocator::NextBlock>(cc.nexts.begin(), cc.nexts.end()),
290            cc.haveCalls, cc.haveReturn, cc.haveEnd };
291        for (const auto& v: cc.ssaInfos)
292        {
293            AsmSingleVReg vreg{ nullptr, v.first.index };
294            if (v.first.name != nullptr)
295            {
296                auto res = regVars.insert({ v.first.name , AsmRegVar{ 0, 100 } });
297                vreg.regVar = &res.first->second;
298            }
299            inCodeBlock.ssaInfoMap.insert({ vreg, v.second });
300        }
301        inCodeBlocks.push_back(inCodeBlock);
302    }
303    SSAReplacesMap inSSAReplaces;
304    // generate SSA replaces
305    for (const auto& replace: testCase.inSSAReplaces)
306    {
307        AsmSingleVReg vreg{ nullptr, replace.first.index };
308        if (replace.first.name != nullptr)
309        {
310            auto res = regVars.insert({ replace.first.name , AsmRegVar{ 0, 100 } });
311            vreg.regVar = &res.first->second;
312        }
313        inSSAReplaces.insert({ vreg, VectorSet<SSAReplace>(
314                    replace.second.begin(), replace.second.end()) });
315    }
316   
317    AsmRegAllocator regAlloc(assembler, inCodeBlocks, inSSAReplaces);
318    regAlloc.applySSAReplaces();
319   
320    const std::vector<CodeBlock>& resCodeBlocks = regAlloc.getCodeBlocks();
321    std::ostringstream oss;
322    oss << " testAsmSSAReplace case#" << i;
323    const std::string testCaseName = oss.str();
324   
325    assertValue("testAsmSSAReplace", testCaseName+".codeBlocks.size",
326                testCase.codeBlocks.size(), resCodeBlocks.size());
327   
328    std::unordered_map<const AsmRegVar*, CString> regVarNamesMap;
329    for (const auto& rvEntry: regVars)
330        regVarNamesMap.insert(std::make_pair(&rvEntry.second, rvEntry.first));
331   
332    for (size_t j = 0; j < resCodeBlocks.size(); j++)
333    {
334        const CCodeBlock2& expCBlock = testCase.codeBlocks[j];
335        const CodeBlock& resCBlock = resCodeBlocks[j];
336        std::ostringstream codeBlockOss;
337        codeBlockOss << ".codeBlock#" << j << ".";
338        codeBlockOss.flush();
339        std::string cbname(codeBlockOss.str());
340        assertValue("testAsmSSAReplace", testCaseName + cbname + "start",
341                    expCBlock.start, resCBlock.start);
342        assertValue("testAsmSSAReplace", testCaseName + cbname + "end",
343                    expCBlock.end, resCBlock.end);
344        assertValue("testAsmSSAReplace", testCaseName + cbname + "nextsSize",
345                    expCBlock.nexts.size(), resCBlock.nexts.size());
346       
347        for (size_t k = 0; k < expCBlock.nexts.size(); k++)
348        {
349            std::ostringstream nextOss;
350            nextOss << "next#" << k << ".";
351            nextOss.flush();
352            std::string nname(nextOss.str());
353           
354            assertValue("testAsmSSAReplace", testCaseName + cbname + nname + "block",
355                    expCBlock.nexts[k].block, resCBlock.nexts[k].block);
356            assertValue("testAsmSSAReplace", testCaseName + cbname + nname + "isCall",
357                    int(expCBlock.nexts[k].isCall), int(resCBlock.nexts[k].isCall));
358        }
359       
360        assertValue("testAsmSSAReplace", testCaseName + cbname + "ssaInfoSize",
361                    expCBlock.ssaInfos.size(), resCBlock.ssaInfoMap.size());
362       
363        Array<std::pair<TestSingleVReg, SSAInfo> > resSSAInfos(
364                        resCBlock.ssaInfoMap.size());
365        std::transform(resCBlock.ssaInfoMap.begin(), resCBlock.ssaInfoMap.end(),
366            resSSAInfos.begin(),
367            [&regVarNamesMap](const std::pair<AsmSingleVReg, SSAInfo>& a)
368            -> std::pair<TestSingleVReg, SSAInfo>
369            { return { getTestSingleVReg(a.first, regVarNamesMap), a.second }; });
370        mapSort(resSSAInfos.begin(), resSSAInfos.end());
371       
372        for (size_t k = 0; k < expCBlock.ssaInfos.size(); k++)
373        {
374            std::ostringstream ssaOss;
375            ssaOss << "ssaInfo#" << k << ".";
376            ssaOss.flush();
377            std::string ssaName(ssaOss.str());
378           
379            const TestSingleVReg expVReg = { expCBlock.ssaInfos[k].first.name,
380                    expCBlock.ssaInfos[k].first.index };
381           
382            assertValue("testAsmSSAReplace", testCaseName + cbname + ssaName + "svreg",
383                        expVReg, resSSAInfos[k].first);
384            const SSAInfo& expSInfo = expCBlock.ssaInfos[k].second;
385            const SSAInfo& resSInfo = resSSAInfos[k].second;
386            assertValue("testAsmSSAReplace",
387                        testCaseName + cbname + ssaName + "ssaIdBefore",
388                        expSInfo.ssaIdBefore, resSInfo.ssaIdBefore);
389            assertValue("testAsmSSAReplace", testCaseName + cbname + ssaName + "ssaId",
390                        expSInfo.ssaId, resSInfo.ssaId);
391            assertValue("testAsmSSAReplace",
392                        testCaseName + cbname + ssaName + "ssaIdChange",
393                        expSInfo.ssaIdChange, resSInfo.ssaIdChange);
394            assertValue("testAsmSSAReplace",
395                        testCaseName + cbname + ssaName + "ssaIdFirst",
396                        expSInfo.ssaIdFirst, resSInfo.ssaIdFirst);
397            assertValue("testAsmSSAReplace",
398                        testCaseName + cbname + ssaName + "ssaIdLast",
399                        expSInfo.ssaIdLast, resSInfo.ssaIdLast);
400            assertValue("testAsmSSAReplace", testCaseName + cbname + ssaName +
401                        "readBeforeWrite", int(expSInfo.readBeforeWrite),
402                        int(resSInfo.readBeforeWrite));
403        }
404       
405        assertValue("testAsmSSAReplace", testCaseName + cbname + "haveCalls",
406                    int(expCBlock.haveCalls), int(resCBlock.haveCalls));
407        assertValue("testAsmSSAReplace", testCaseName + cbname + "haveReturn",
408                    int(expCBlock.haveReturn), int(resCBlock.haveReturn));
409        assertValue("testAsmSSAReplace", testCaseName + cbname + "haveEnd",
410                    int(expCBlock.haveEnd), int(resCBlock.haveEnd));
411    }
412}
413
414int main(int argc, const char** argv)
415{
416    int retVal = 0;
417    for (size_t i = 0; i < sizeof(ssaApplyReplacesCasesTbl)/
418                        sizeof(AsmApplySSAReplacesCase); i++)
419        try
420        { testApplySSAReplaces(i, ssaApplyReplacesCasesTbl[i]); }
421        catch(const std::exception& ex)
422        {
423            std::cerr << ex.what() << std::endl;
424            retVal = 1;
425        }
426    return retVal;
427}
Note: See TracBrowser for help on using the repository browser.