source: CLRX/CLRadeonExtender/trunk/tests/amdasm/AsmRegAlloc3.cpp @ 4147

Last change on this file since 4147 was 4147, checked in by matszpk, 5 months ago

CLRadeonExtender: AsmRegAlloc?: Recover previous testcase.

File size: 81.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 <iterator>
24#include <sstream>
25#include <string>
26#include <vector>
27#include <cstring>
28#include <CLRX/utils/Utilities.h>
29#include <CLRX/amdasm/Assembler.h>
30#include <CLRX/utils/Containers.h>
31#include "../TestUtils.h"
32#include "AsmRegAlloc.h"
33
34using namespace CLRX;
35
36typedef AsmRegAllocator::OutLiveness OutLiveness;
37typedef AsmRegAllocator::LinearDep LinearDep;
38typedef AsmRegAllocator::VarIndexMap VarIndexMap;
39typedef AsmRegAllocator::VIdxSetEntry VIdxSetEntry;
40
41struct LinearDep2
42{
43    cxbyte align;
44    Array<size_t> prevVidxes;
45    Array<size_t> nextVidxes;
46};
47
48struct VIdxSetEntry2
49{
50    Array<size_t> vs[4];
51};
52
53struct AsmLivenessesCase
54{
55    const char* input;
56    Array<OutLiveness> livenesses[MAX_REGTYPES_NUM];
57    Array<std::pair<size_t, LinearDep2> > linearDepMaps[MAX_REGTYPES_NUM];
58    Array<std::pair<size_t, VIdxSetEntry2> > vidxRoutineMap;
59    Array<std::pair<size_t, VIdxSetEntry2> > vidxCallMap;
60    bool good;
61    const char* errorMessages;
62};
63
64static const AsmLivenessesCase createLivenessesCasesTbl[] =
65{
66    {   // 0 - simple case
67        R"ffDXD(.regvar sa:s:8, va:v:10
68        s_mov_b32 sa[4], sa[2]  # 0
69        s_add_u32 sa[4], sa[4], s3
70        v_xor_b32 va[4], va[2], v3
71)ffDXD",
72        {   // livenesses
73            {   // for SGPRs
74                { { 0, 5 } }, // S3
75                { { 0, 1 } }, // sa[2]'0
76                { { 1, 5 } }, // sa[4]'0
77                { { 5, 6 } }  // sa[4]'1
78            },
79            {   // for VGPRs
80                { { 0, 9 } }, // V3
81                { { 0, 9 } }, // va[2]'0
82                { { 9, 10 } } // va[4]'0 : out of range code block
83            },
84            { },
85            { }
86        },
87        { },  // linearDepMaps
88        { },  // vidxRoutineMap
89        { },  // vidxCallMap
90        true, ""
91    },
92    {   // 1 - simple case 2
93        R"ffDXD(.regvar sa:s:8, va:v:10
94        s_mov_b32 sa[4], sa[2]  # 0
95        s_add_u32 sa[4], sa[4], s3
96        v_xor_b32 va[4], va[2], v3
97        s_endpgm
98)ffDXD",
99        {   // livenesses
100            {   // for SGPRs
101                { { 0, 5 } }, // S3
102                { { 0, 1 } }, // sa[2]'0
103                { { 1, 5 } }, // sa[4]'0
104                { { 5, 6 } }  // sa[4]'1
105            },
106            {   // for VGPRs
107                { { 0, 9 } }, // V3
108                { { 0, 9 } }, // va[2]'0
109                { { 9, 10 } } // va[4]'0 : out of range code block
110            },
111            { },
112            { }
113        },
114        { },  // linearDepMaps
115        { },  // vidxRoutineMap
116        { },  // vidxCallMap
117        true, ""
118    },
119    {   // 2 - simple case (linear dep)
120        R"ffDXD(.regvar sa:s:8, va:v:10
121        .regvar sbuf:s:4, rbx4:v:6
122        s_mov_b64 sa[4:5], sa[2:3]  # 0
123        s_and_b64 sa[4:5], sa[4:5], s[4:5]
124        v_add_f64 va[4:5], va[2:3], v[3:4]
125        buffer_load_dwordx4 rbx4[1:5], va[6], sbuf[0:3], sa[7] idxen offset:603 tfe
126)ffDXD",
127        {   // livenesses
128            {   // for SGPRs
129                { { 0, 5 } }, // S4
130                { { 0, 5 } }, // S5
131                { { 0, 1 } }, // sa[2]'0
132                { { 0, 1 } }, // sa[3]'0
133                { { 1, 5 } }, // sa[4]'0
134                { { 5, 6 } }, // sa[4]'1
135                { { 1, 5 } }, // sa[5]'0
136                { { 5, 6 } }, // sa[5]'1
137                { { 0, 17 } }, // sa[7]'0
138                { { 0, 17 } }, // sbuf[0]'0
139                { { 0, 17 } }, // sbuf[1]'0
140                { { 0, 17 } }, // sbuf[2]'0
141                { { 0, 17 } }, // sbuf[3]'0
142            },
143            {   // for VGPRs
144                { { 0, 9 } }, // V3
145                { { 0, 9 } }, // V4
146                { { 17, 18 } }, // rbx4[1]'0
147                { { 17, 18 } }, // rbx4[2]'0
148                { { 17, 18 } }, // rbx4[3]'0
149                { { 17, 18 } }, // rbx4[4]'0
150                { { 0, 17 } }, // rbx4[5]'0: tfe - read before write
151                { { 0, 9 } }, // va[2]'0
152                { { 0, 9 } }, // va[3]'0
153                { { 9, 10 } }, // va[4]'0 : out of range code block
154                { { 9, 10 } }, // va[5]'0 : out of range code block
155                { { 0, 17 } } // va[6]'0
156            },
157            { },
158            { }
159        },
160        {   // linearDepMaps
161            {   // for SGPRs
162                { 2, { 2, { }, { 3 } } },  // sa[2]'0
163                { 3, { 0, { 2 }, { } } },  // sa[3]'0
164                { 4, { 2, { }, { 6 } } },  // sa[4]'0
165                { 5, { 2, { }, { 7 } } },  // sa[4]'1
166                { 6, { 0, { 4 }, { } } },  // sa[5]'0
167                { 7, { 0, { 5 }, { } } },   // sa[5]'1
168                { 9, { 4, { }, { 10 } } }, // sbuf[0]'0
169                { 10, { 0, { 9 }, { 11 } } }, // sbuf[1]'0
170                { 11, { 0, { 10 }, { 12 } } }, // sbuf[2]'0
171                { 12, { 0, { 11 }, { } } }  // sbuf[3]'0
172            },
173            {   // for VGPRs
174                { 2, { 1, { }, { 3 } } }, // rbx4[1]'0
175                { 3, { 0, { 2 }, { 4 } } }, // rbx4[2]'0
176                { 4, { 0, { 3 }, { 5 } } }, // rbx4[3]'0
177                { 5, { 0, { 4 }, { 6 } } }, // rbx4[4]'0
178                { 6, { 0, { 5 }, { } } }, // rbx4[5]'0
179                { 7, { 1, { }, { 8 } } },  // va[2]'0
180                { 8, { 0, { 7 }, { } } },  // va[3]'0
181                { 9, { 1, { }, { 10 } } },  // va[4]'0
182                { 10, { 0, { 9 }, { } } }  // va[5]'0
183            },
184            { },
185            { }
186        },
187        { },  // vidxRoutineMap
188        { },  // vidxCallMap
189        true, ""
190    },
191    {   // 3 - next simple case
192        R"ffDXD(.regvar sa:s:8, va:v:10
193        s_mov_b32 sa[4], sa[2]  # 0
194        s_add_u32 sa[4], sa[4], s3
195        v_xor_b32 va[4], va[2], v3
196        v_mov_b32 va[3], 1.45s
197        v_mov_b32 va[6], -7.45s
198        v_lshlrev_b32 va[5], sa[4], va[4]
199        v_mac_f32 va[3], va[6], v0
200        s_mul_i32 sa[7], sa[2], sa[3]
201        v_mac_f32 va[3], va[7], v0
202        s_endpgm
203)ffDXD",
204        {   // livenesses
205            {   // for SGPRs
206                { { 0, 5 } }, // 0: S3
207                { { 0, 37 } }, // 1: sa[2]'0
208                { { 0, 37 } }, // 2: sa[3]'0
209                { { 1, 5 } }, // 3: sa[4]'0
210                { { 5, 29 } }, // 4: sa[4]'1
211                { { 37, 38 } }  // 5: sa[7]'0
212            },
213            {   // for VGPRs
214                { { 0, 41 } }, // 0: v0
215                { { 0, 9 } }, // 1: v3
216                { { 0, 9 } }, // 2: va[2]'0
217                { { 13, 41 } }, // 3: va[3]'0
218                { { 9, 29 } }, // 4: va[4]'0
219                { { 29, 30 } }, // 5: va[5]'0
220                { { 21, 33 } }, // 6: va[6]'0
221                { { 0, 41 } }  // 7: va[7]'0
222            },
223            { },
224            { }
225        },
226        { }, // linearDepMaps
227        { },  // vidxRoutineMap
228        { },  // vidxCallMap
229        true, ""
230    },
231    {   // 4 - next test case
232        R"ffDXD(.regvar sa:s:8, va:v:10
233        s_mov_b32 sa[4], sa[2]  # 0
234        s_add_u32 sa[4], sa[4], s3  # 4
235       
236        v_xor_b32 v4, va[2], v3         # 8
237        v_xor_b32 va[5], v4, va[5]      # 12
238       
239        s_sub_u32 sa[4], sa[4], sa[3]   # 16
240       
241        v_xor_b32 v4, va[5], v3         # 20
242        v_xor_b32 va[6], v4, va[6]      # 24
243       
244        s_mul_i32 sa[4], sa[4], sa[1]   # 28
245        s_mul_i32 sa[4], sa[4], sa[0]   # 32
246       
247        v_xor_b32 v4, va[6], v3         # 36
248        v_xor_b32 va[7], v4, va[7]      # 40
249)ffDXD",
250        {   // livenesses
251            {   // for SGPRs
252                { { 0, 5 } },   // 0: S3
253                { { 0, 33 } },  // 1: sa[0]'0
254                { { 0, 29 } },  // 2: sa[1]'0
255                { { 0, 1 } },   // 3: sa[2]'0
256                { { 0, 17 } },  // 4: sa[3]'0
257                { { 1, 5 } },   // 5: sa[4]'0
258                { { 5, 17 } },  // 6: sa[4]'1
259                { { 17, 29 } }, // 7: sa[4]'2
260                { { 29, 33 } }, // 8: sa[4]'3
261                { { 33, 34 } }  // 9: sa[4]'4
262            },
263            {   // for VGPRs
264                { { 0, 37 } },   // 0: v3
265                { { 9, 13 }, { 21, 25 }, { 37, 41 } }, // 1: v4
266                { { 0, 9 } },    // 2: va[2]'0
267                { { 0, 13 } },   // 3: va[5]'0
268                { { 13, 21 } },  // 4: va[5]'1
269                { { 0, 25 } },   // 5: va[6]'0
270                { { 25, 37 } },  // 6: va[6]'1
271                { { 0, 41 } },   // 7: va[7]'0
272                { { 41, 42 } }   // 8: va[7]'1
273            },
274            { },
275            { }
276        },
277        { }, // linearDepMaps
278        { },  // vidxRoutineMap
279        { },  // vidxCallMap
280        true, ""
281    },
282    {   // 5 - blocks
283        R"ffDXD(.regvar sa:s:8, va:v:10
284        s_mov_b32 sa[4], sa[2]          # 0
285        s_add_u32 sa[4], sa[4], s3      # 4
286        v_mad_f32 va[0], va[1], va[2], v0  # 8
287        .cf_jump a0,a1,a2
288        s_setpc_b64 s[0:1]              # 16
289       
290a0:     s_mul_i32 sa[3], sa[4], s3      # 20
291        s_xor_b32 s4, sa[2], s4         # 24
292        s_endpgm                        # 28
293       
294a1:     v_add_f32 va[2], sa[5], va[0]   # 32
295        v_mul_f32 va[3], va[2], v0      # 36
296        s_endpgm                        # 40
297       
298a2:     s_cselect_b32 sa[2], sa[4], sa[3]   # 44
299        v_cndmask_b32 va[3], va[0], va[1], vcc     # 48
300        s_endpgm                        # 52
301)ffDXD",
302        {   // livenesses
303            {   // for SGPRs
304                { { 0, 17 } }, // 0: S0
305                { { 0, 17 } }, // 1: S1
306                { { 0, 21 } }, // 2: S3
307                { { 0, 26 } }, // 3: S4
308                { { 0, 25 } }, // 4: sa[2]'0
309                { { 45, 46 } }, // 5: sa[2]'1
310                { { 0, 20 }, { 44, 45 } }, // 6: sa[3]'0
311                { { 21, 22 } }, // 7: sa[3]'1
312                { { 1, 5 } }, // 8: sa[4]'0
313                { { 5, 21 }, { 44, 45 } }, // 9: sa[4]'1
314                { { 0, 20 }, { 32, 33 } }  // 10: sa[5]
315            },
316            {   // for VGPRs
317                { { 0, 20 }, { 32, 37 } }, // 0: V0
318                { { 9, 20 }, { 32, 33 }, { 44, 49 } }, // 1: va[0]'0
319                { { 0, 20 }, { 44, 49 } }, // 2: va[1]'0
320                { { 0, 9 } }, // 3: va[2]'0
321                { { 33, 37 } }, // 4: va[2]'1
322                { { 37, 38 } }, // 5: va[3]'0
323                { { 49, 50 } }  // 6: va[3]'1
324            },
325            { },
326            { }
327        },
328        {   // linearDepMaps
329            { },
330            { },
331            { },
332            { }
333        },
334        { },  // vidxRoutineMap
335        { },  // vidxCallMap
336        true, ""
337    },
338    {   // 6 - blocks
339        R"ffDXD(.regvar sa:s:8, va:v:10
340        s_mov_b32 sa[4], sa[2]              # 0
341        s_add_u32 sa[4], sa[4], s3          # 4
342        v_mad_f32 va[0], va[1], va[2], v0   # 8
343        s_xor_b32 sa[6], sa[2], sa[4]       # 16
344        .cf_jump a0,a1,a2
345        s_setpc_b64 s[0:1]                  # 20
346       
347a0:     s_mul_i32 sa[3], sa[4], s3          # 24
348        s_xor_b32 s4, sa[2], s4             # 28
349        s_cbranch_scc1 a01                  # 32
350a00:    s_add_u32 sa[4], sa[4], s4          # 36
351        s_endpgm                            # 40
352a01:    s_add_u32 sa[6], sa[6], s4          # 44
353        s_endpgm                            # 48
354       
355a1:     v_add_f32 va[2], sa[5], va[0]       # 52
356        v_mul_f32 va[3], va[2], v0          # 56
357        s_cbranch_scc1 a11                  # 60
358a10:    s_add_u32 sa[5], sa[7], s7          # 64
359        s_endpgm                            # 68
360a11:    v_add_f32 va[5], va[3], va[1]       # 72
361        s_endpgm                            # 76
362       
363a2:     s_cselect_b32 sa[2], sa[4], sa[3]   # 80
364        v_cndmask_b32 va[3], va[0], va[1], vcc  # 84
365        s_cbranch_scc1 a21                  # 88
366a20:    v_add_f32 va[1], va[3], va[4]       # 92
367        s_endpgm                            # 96
368a21:    v_add_f32 va[2], va[1], va[0]       # 100
369        s_endpgm                            # 104
370)ffDXD",
371        {   // livenesses
372            {   // for SGPRs
373                { { 0, 21 } }, // 0: S0
374                { { 0, 21 } }, // 1: S1
375                { { 0, 25 } }, // 2: S3
376                { { 0, 37 }, { 44, 45 } }, // 3: S4
377                { { 0, 24 }, { 52, 65 } }, // 4: S7
378                { { 0, 29 } }, // 5: sa[2]'0
379                { { 81, 82 } }, // 6: sa[2]'1
380                { { 0, 24 }, { 80, 81 } }, // 7: sa[3]'0
381                { { 25, 26 } }, // 8: sa[3]'1
382                { { 1, 5 } }, // 9: sa[4]'0
383                { { 5, 37, }, { 80, 81 } }, // 10 sa[4]'1
384                { { 37, 38 } }, // 11: sa[4]'2
385                { { 0, 24 }, { 52, 53 } }, // 12: sa[5]'0
386                { { 65, 66 } }, // 13: sa[5]'1
387                { { 17, 36 }, { 44, 45 } }, // 14: sa[6]'0
388                { { 45, 46 } }, // 15: sa[6]'1
389                { { 0, 24 }, { 52, 65 }  }  // 16: sa[7]'0
390            },
391            {   // for VGPRs
392                { { 0, 24 }, { 52, 57 } }, // 1: V0
393                { { 9, 24 }, { 52, 53 }, { 80, 92 }, { 100, 101 } }, // 1: va[0]'0
394                { { 0, 24 }, { 52, 64 }, { 72, 73 },
395                            { 80, 92 }, { 100, 101 } }, // 2: va[1]'0
396                { { 93, 94 } }, // 3: va[1]'1
397                { { 0, 9 } }, // 4: va[2]'0
398                { { 53, 57 } }, // 5: va[2]'1
399                { { 101, 102 } }, // 6: va[2]'2
400                { { 57, 64 }, { 72, 73 } }, // 7: va[3]'0
401                { { 85, 93 } }, // 8: va[3]'1
402                { { 0, 24 }, { 80, 93 } }, // 8: va[4]'0
403                { { 73, 74 } }  // 10: va[5]'0
404            },
405            { },
406            { }
407        },
408        {   // linearDepMaps
409            { },
410            { },
411            { },
412            { }
413        },
414        { },  // vidxRoutineMap
415        { },  // vidxCallMap
416        true, ""
417    },
418    {   // 7 - empty blocks
419        R"ffDXD(.regvar sa:s:8, va:v:10
420        s_mov_b32 sa[0], sa[2]              # 0
421        s_add_u32 sa[1], sa[3], s3          # 4
422        v_mad_f32 va[0], va[1], va[2], v0   # 8
423        s_xor_b32 sa[2], sa[4], sa[3]       # 16
424        .cf_jump a0,a1
425        s_setpc_b64 s[0:1]                  # 20
426       
427a0:     s_mul_i32 sa[1], sa[2], s3          # 24
428        s_nop 7                             # 28
429        s_cbranch_scc1 a01                  # 32
430        s_nop 7                             # 36
431        s_cbranch_execz a02                 # 40
432        s_nop 7                             # 44
433        s_cbranch_vccz a03                  # 48
434        s_nop 7                             # 52
435        s_cbranch_vccnz a04                 # 56
436        s_nop 7                             # 60
437        s_mul_i32 s2, sa[4], sa[2]          # 64
438        s_cbranch_scc0 a05                  # 68
439        s_endpgm                            # 72
440       
441a01:    s_mul_i32 sa[0], s2, s3             # 76
442        s_endpgm                            # 80
443       
444a02:    s_mul_i32 sa[1], s2, sa[4]          # 84
445        s_endpgm                            # 88
446       
447a03:    v_add_f32 va[3], va[1], va[0]       # 92
448        s_endpgm                            # 96
449       
450a04:    v_add_f32 va[3], va[3], va[4]       # 100
451        s_endpgm                            # 104
452       
453a05:    s_mul_i32 sa[5], s4, sa[6]          # 108
454        s_endpgm                            # 112
455
456a1:     v_mul_f32 va[1], sa[1], va[1]       # 116
457        v_nop                               # 120
458        s_cbranch_scc1 a11                  # 124
459        v_nop                               # 128
460        s_cbranch_execz a12                 # 132
461        v_nop                               # 136
462        s_cbranch_vccz a13                  # 140
463        v_nop                               # 144
464        s_cbranch_vccnz a14                 # 148
465        v_nop                               # 152
466        s_mul_i32 s2, sa[4], sa[2]          # 156
467        s_cbranch_scc0 a15                  # 160
468        s_endpgm                            # 164
469
470a11:    v_add_f32 v2, va[2], va[3]          # 168
471        s_endpgm                            # 172
472       
473a12:    v_add_f32 v2, va[0], va[3]          # 176
474        s_endpgm                            # 180
475       
476a13:    v_nop                               # 184
477        s_endpgm                            # 188
478       
479a14:    v_nop                               # 192
480        s_endpgm                            # 196
481       
482a15:    s_mul_i32 sa[5], s4, sa[1]          # 200
483        s_endpgm                            # 204
484)ffDXD",
485        {   // livenesses
486            {   // for SGPRs
487                { { 0, 21 } }, // 0: S0
488                { { 0, 21 } }, // 1: S1
489                { { 0, 44 }, { 65, 66 }, { 76, 77 },
490                        { 84, 85 }, { 157, 158 } }, // 2: S2
491                { { 0, 36 }, { 76, 77 } }, // 3: S3
492                { { 0, 72 }, { 108, 109 }, { 116, 164 }, { 200, 201 } }, // 4: S4
493                { { 1, 2 } }, // 5: sa[0]'0
494                { { 77, 78 } }, // 6: sa[0]'1
495                { { 5, 24 }, { 116, 164 }, { 200, 201 } }, // 7: sa[1]'0
496                { { 25, 26 } }, // 8: sa[1]'1
497                { { 85, 86 } }, // 9: sa[1]'2
498                { { 0, 1 } }, // 10: sa[2]'0
499                { { 17, 65 }, { 116, 157 } }, // 11: sa[2]'1
500                { { 0, 17 } }, // 12: sa[3]'0
501                { { 0, 65 }, { 84, 85 }, { 116, 157 } }, // 13: sa[4]'0
502                { { 109, 110 } }, // 14: sa[5]'0
503                { { 201, 202 } }, // 15: sa[5]'1
504                { { 0, 72 }, { 108, 109 } }  // 16: sa[6]'0
505            },
506            {   // for VGPRs
507                { { 0, 9 } }, // 0: V0
508                { { 169, 170 }, { 177, 178 } }, // 1: V2
509                { { 9, 52 }, { 92, 93 }, { 116, 136 }, { 176, 177 } }, // 2: va[0]'0
510                { { 0, 52 }, { 92, 93 }, { 116, 117 } }, // 3: va[1]'0
511                { { 117, 118 } }, // 4: va[1]'1
512                { { 0, 24 }, { 116, 128 }, { 168, 169 } }, // 5: va[2]'0
513                { { 0, 60 }, { 100, 101 }, { 116, 136 },
514                        { 168, 169 }, { 176, 177 } }, // 6: va[3]'0
515                { { 101, 102 } }, // 7: va[3]'1
516                { { 93, 94 } }, // 8: va[3]'2
517                { { 0, 60 }, { 100, 101 } }  // 9: va[4]'0
518            },
519            { },
520            { }
521        },
522        { },  // linearDepMaps
523        { },  // vidxRoutineMap
524        { },  // vidxCallMap
525        true, ""
526    },
527    {   // 8 - empty blocks
528        R"ffDXD(.regvar sa:s:8, va:v:10
529        s_mov_b32 sa[0], sa[2]              # 0
530        s_add_u32 sa[1], sa[3], s3          # 4
531        v_mad_f32 va[0], va[1], va[2], v0   # 8
532        s_xor_b32 sa[2], sa[4], sa[3]       # 16
533        .cf_jump a0
534        s_setpc_b64 s[0:1]                  # 20
535       
536a0:     s_mul_i32 sa[1], sa[2], s3          # 24
537        s_nop 7                             # 28
538        s_cbranch_scc1 a01                  # 32
539        s_nop 7                             # 36
540        s_cbranch_execz a02                 # 40
541        s_nop 7                             # 44
542        s_cbranch_vccz a03                  # 48
543        s_nop 7                             # 52
544        s_cbranch_vccnz a04                 # 56
545        s_nop 7                             # 60
546        s_nop 1                             # 64
547        s_cbranch_scc0 a05                  # 68
548        s_endpgm                            # 72
549       
550a01:    s_mul_i32 sa[0], s2, s3             # 76
551        s_endpgm                            # 80
552       
553a02:    s_mul_i32 sa[1], s2, sa[4]          # 84
554        s_endpgm                            # 88
555       
556a03:    v_add_f32 va[3], va[1], va[0]       # 92
557        s_endpgm                            # 96
558       
559a04:    v_add_f32 va[3], va[3], va[4]       # 100
560        s_endpgm                            # 104
561       
562a05:    s_mul_i32 sa[5], s4, sa[6]          # 108
563        s_endpgm                            # 112
564)ffDXD",
565        {   // livenesses
566            {   // for SGPRs
567                { { 0, 21 } }, // 0: S0
568                { { 0, 21 } }, // 1: S1
569                { { 0, 44 }, { 76, 77 }, { 84, 85 } }, // 2: S2
570                { { 0, 36 }, { 76, 77 } }, // 3: S3
571                { { 0, 72 }, { 108, 109 } }, // 4: S4
572                { { 1, 2 } }, // 5: sa[0]'0
573                { { 77, 78 } }, // 6: sa[0]'1
574                { { 5, 6 } }, // 7: sa[1]'0
575                { { 25, 26 } }, // 8: sa[1]'1
576                { { 85, 86 } }, // 9: sa[1]'2
577                { { 0, 1 } }, // 10: sa[2]'0
578                { { 17, 25 } }, // 11: sa[2]'1
579                { { 0, 17 } }, // 12: sa[3]'0
580                { { 0, 44 }, { 84, 85 } }, // 13: sa[4]'0
581                { { 109, 110 } }, // 14: sa[5]'0
582                { { 0, 72 }, { 108, 109 } }  // 16: sa[6]'0
583            },
584            {   // for VGPRs
585                { { 0, 9 } }, // 0: V0
586                { { 9, 52 }, { 92, 93 } }, // 2: va[0]'0
587                { { 0, 52 }, { 92, 93 } }, // 4: va[1]'1
588                { { 0, 9 } }, // 5: va[2]'0
589                { { 0, 60 }, { 100, 101 } }, // 6: va[3]'0
590                { { 101, 102 } }, // 7: va[3]'1
591                { { 93, 94 } }, // 8: va[3]'2
592                { { 0, 60 }, { 100, 101 } }  // 9: va[4]'0
593            },
594            { },
595            { }
596        },
597        { },  // linearDepMaps
598        { },  // vidxRoutineMap
599        { },  // vidxCallMap
600        true, ""
601    },
602    {   // 9 - simple joins
603        R"ffDXD(.regvar sa:s:12, va:v:8
604        s_mov_b32 sa[2], s2     # 0
605        .cf_jump a1,a2,a3
606        s_setpc_b64 s[0:1]      # 4
607       
608a1:     s_add_u32 sa[2], sa[2], sa[3]   # 8
609        s_add_u32 sa[2], sa[2], sa[3]   # 12
610        s_branch end                    # 16
611a2:     s_add_u32 sa[2], sa[2], sa[4]   # 20
612        s_add_u32 sa[2], sa[2], sa[4]   # 24
613        s_branch end                    # 28
614a3:     s_add_u32 sa[2], sa[2], sa[5]   # 32
615        s_add_u32 sa[2], sa[2], sa[5]   # 36
616        s_branch end                    # 40
617
618end:    s_xor_b32 sa[2], sa[2], s3      # 44
619        s_endpgm                        # 48
620)ffDXD",
621        {   // livenesses
622            {   // for SGPRs
623                { { 0, 5 } }, // 0: S0
624                { { 0, 5 } }, // 1: S1
625                { { 0, 1 } }, // 2: S2
626                { { 0, 45 } }, // 3: S3
627                { { 1, 9 }, { 20, 21 }, { 32, 33 } }, // 4: sa[2]'0
628                { { 9, 13 } }, // 5: sa[2]'1
629                { { 13, 20 }, { 25, 32 }, { 37, 45 } }, // 6: sa[2]'2
630                { { 45, 46 } }, // 7: sa[2]'3
631                { { 21, 25 } }, // 8: sa[2]'4
632                { { 33, 37 } }, // 9: sa[2]'5
633                { { 0, 13 } }, // 10: sa[3]'0
634                { { 0, 8 }, { 20, 25 } }, // 11: sa[4]'0
635                { { 0, 8 }, { 32, 37 } }  // 12: sa[5]'0
636            },
637            { },
638            { },
639            { }
640        },
641        { },  // linearDepMaps
642        { },  // vidxRoutineMap
643        { },  // vidxCallMap
644        true, ""
645    },
646    {   // 10 - more complex join
647        R"ffDXD(.regvar sa:s:12, va:v:8
648        s_mov_b32 sa[2], s2             # 0
649        s_xor_b32 sa[6], sa[2], s3      # 4
650        .cf_jump a1,a2,a3
651        s_setpc_b64 s[0:1]              # 8
652       
653a1:     s_add_u32 sa[2], sa[2], sa[3]   # 12
654        s_add_u32 sa[2], sa[2], sa[3]   # 16
655        .cf_jump b1,b2
656        s_setpc_b64 s[0:1]              # 20
657a2:     s_add_u32 sa[2], sa[2], sa[4]   # 24
658        s_add_u32 sa[2], sa[2], sa[4]   # 28
659        .cf_jump b1,b2
660        s_setpc_b64 s[0:1]              # 32
661a3:     s_add_u32 sa[2], sa[2], sa[5]   # 36
662        s_add_u32 sa[2], sa[2], sa[5]   # 40
663        .cf_jump b1,b2
664        s_setpc_b64 s[0:1]              # 44
665       
666b1:     s_add_u32 sa[5], sa[6], sa[4]   # 48
667        s_branch end                    # 52
668b2:     s_add_u32 sa[6], sa[5], sa[4]   # 56
669        s_branch end                    # 60
670       
671end:    s_xor_b32 sa[2], sa[2], s3      # 64
672        s_xor_b32 sa[3], sa[6], s4      # 68
673        s_endpgm                        # 72
674)ffDXD",
675        {   // livenesses
676            {   // for SGPRs
677                { { 0, 21 }, { 24, 33 }, { 36, 45 } }, // 0: S0
678                { { 0, 21 }, { 24, 33 }, { 36, 45 } }, // 1: S1
679                { { 0, 1 } }, // 2: S2
680                { { 0, 65 } }, // 3: S3
681                { { 0, 69 } }, // 4: S4
682                { { 1, 13 }, { 24, 25 }, { 36, 37 } }, // 5: sa[2]'0
683                { { 13, 17 } }, // 6: sa[2]'1
684                { { 17, 24 }, { 29, 36 }, { 41, 65 } }, // 7: sa[2]'2
685                { { 65, 66 } }, // 8: sa[2]'3
686                { { 25, 29 } }, // 9: sa[2]'4
687                { { 37, 41 } }, // 10: sa[2]'5
688                { { 0, 17 } }, // 11: sa[3]'0
689                { { 69, 70 } }, // 12: sa[3]'1
690                { { 0, 49 }, { 56, 57 } }, // 13: sa[4]'0
691                { { 0, 48 }, { 56, 57 } }, // 14: sa[5]'0
692                { { 49, 50 } }, // 15: sa[5]'0
693                { { 5, 56 }, { 57, 69 } }  // 16: sa[6]'0
694            },
695            { },
696            { },
697            { }
698        },
699        { },  // linearDepMaps
700        { },  // vidxRoutineMap
701        { },  // vidxCallMap
702        true, ""
703    },
704    {   // 11 - simple loop
705        R"ffDXD(.regvar sa:s:8, va:v:8
706        s_mov_b32 sa[0], 0              # 0
707        s_mov_b32 sa[1], s10            # 4
708        v_mov_b32 va[0], v0             # 8
709        v_mov_b32 va[1], v1             # 12
710        v_mov_b32 va[3], 0              # 16
711        v_mov_b32 va[4], 11             # 20
712loop:
713        ds_read_b32 va[2], va[3]        # 24
714        v_xor_b32 va[0], va[1], va[2]   # 32
715        v_not_b32 va[0], va[0]          # 36
716        v_xor_b32 va[0], 0xfff, va[0]   # 40
717        v_xor_b32 va[4], va[4], va[2]   # 48
718        v_not_b32 va[4], va[0]          # 52
719        v_xor_b32 va[4], 0xfff, va[0]   # 56
720        v_add_u32 va[1], vcc, 1001, va[1]   # 64
721       
722        s_add_u32 sa[0], sa[0], 1       # 72
723        s_cmp_lt_u32 sa[0], sa[1]       # 76
724        s_cbranch_scc1 loop             # 80
725       
726        v_xor_b32 va[0], 33, va[0]      # 84
727        s_add_u32 sa[0], 14, sa[0]      # 88
728        s_endpgm                        # 92
729)ffDXD",
730        {   // livenesses
731            {   // for SGPRs
732                { { 0, 5 } }, // 0: S10
733                { { 1, 89 } }, // 1: sa[0]'0
734                { { 89, 90 } }, // 2: sa[0]'1
735                { { 5, 84 } }  // 3: sa[1]'0
736            },
737            {   // for VGPRs
738                { { 0, 9 } }, // 0: V0
739                { { 0, 13 } }, // 1: V1
740                { { 9, 10 } }, // va[0]'0
741                { { 33, 37 } }, // va[0]'1
742                { { 37, 41 } }, // va[0]'2
743                { { 41, 85 } }, // va[0]'3
744                { { 85, 86 } }, // va[0]'4
745                { { 13, 84 } }, // va[1]'0
746                { { 25, 49 } }, // va[2]'0
747                { { 17, 84 } }, // va[3]'0
748                { { 21, 49 }, { 57, 84 } }, // va[4]'0
749                { { 49, 50 } }, // va[4]'1
750                { { 53, 54 } }  // va[4]'2
751            },
752            { },
753            { }
754        },
755        { },  // linearDepMaps
756        { },  // vidxRoutineMap
757        { },  // vidxCallMap
758        true, ""
759    },
760    {   // 12 - simple loop with fork (regvar used only in these forks)
761        R"ffDXD(.regvar sa:s:8, va:v:8
762        s_mov_b32 sa[2], s4             # 0
763loop:   s_cbranch_scc1 b1               # 4
764       
765b0:     s_add_u32 sa[2], sa[2], sa[0]   # 8
766        s_branch loopend                # 12
767b1:     s_add_u32 sa[2], sa[2], sa[1]   # 16
768loopend:
769        s_cbranch_scc0 loop             # 20
770        s_endpgm                        # 24
771)ffDXD",
772        {   // livenesses
773            {   // for SGPRs
774                { { 0, 1 } }, // 0: S4
775                { { 0, 24 } }, // 1: sa[0]'0
776                { { 0, 24 } }, // 2: sa[1]'0
777                { { 1, 24 } }  // 3: sa[2]'0
778            },
779            { },
780            { },
781            { }
782        },
783        { },  // linearDepMaps
784        { },  // vidxRoutineMap
785        { },  // vidxCallMap
786        true, ""
787    },
788    {   // 13 - simple with forks - holes in loop (second case)
789        R"ffDXD(.regvar sa:s:8, va:v:8
790loop:   s_cbranch_scc1 b1               # 0
791       
792b0:     s_add_u32 sa[2], sa[2], sa[0]   # 4
793        s_add_u32 sa[3], sa[0], sa[1]   # 8
794        s_branch loopend                # 12
795b1:     s_add_u32 sa[2], sa[0], sa[1]   # 16
796        s_add_u32 sa[3], sa[3], sa[1]   # 20
797loopend:
798        s_cbranch_scc0 loop             # 24
799        s_endpgm                        # 28
800)ffDXD",
801        {   // livenesses
802            {   // for SGPRs
803                { { 0, 28 } }, // 0: sa[0]'0
804                { { 0, 28 } }, // 1: sa[1]'0
805                { { 0, 16 }, { 17, 28 } }, // 2: sa[2]'0
806                { { 0, 4 }, { 9, 28 } }  // 3: sa[3]'0
807            },
808            { },
809            { },
810            { }
811        },
812        { },  // linearDepMaps
813        { },  // vidxRoutineMap
814        { },  // vidxCallMap
815        true, ""
816    },
817    {   // 14 - two loops, one nested
818        R"ffDXD(.regvar sa:s:8, va:v:8
819        s_mov_b64 sa[0:1], 0            # 0
820        v_mov_b32 va[0], v1             # 4
821        v_mov_b32 va[1], v2             # 8
822        v_mov_b32 va[2], v3             # 12
823       
824loop0:  v_lshrrev_b32 va[0], va[2], va[0]   # 16
825        v_xor_b32 va[0], va[1], va[0]       # 20
826       
827        s_xor_b32 sa[3], sa[0], 0x5     # 24
828        s_cmp_eq_u32 sa[3], 9           # 28
829        s_cbranch_scc1 bb0              # 32
830       
831        v_and_b32 va[0], -15, va[0]         # 36
832        v_sub_u32 va[0], vcc, -13, va[0]    # 40
833        s_branch loop1start                 # 44
834       
835bb0:    v_xor_b32 va[0], 15, va[0]          # 48
836        v_add_u32 va[0], vcc, 17, va[0]     # 52
837loop1start:
838        s_mov_b32 sa[1], sa[0]              # 56
839       
840loop1:  v_add_u32 va[2], vcc, va[2], va[1]  # 60
841        v_xor_b32 va[2], 0xffaaaa, va[0]    # 64
842       
843        s_xor_b32 sa[2], sa[1], 0x5     # 72
844        s_cmp_eq_u32 sa[2], 7           # 76
845        s_cbranch_scc1 bb1              # 80
846       
847        v_sub_u32 va[1], vcc, 5, va[1]      # 84
848        v_sub_u32 va[2], vcc, 7, va[2]      # 88
849        s_branch loop1end                   # 92
850       
851bb1:    v_xor_b32 va[1], 15, va[1]          # 96
852        v_xor_b32 va[2], 17, va[2]          # 100
853loop1end:
854       
855        s_add_u32 sa[1], sa[1], 1       # 104
856        s_cmp_lt_u32 sa[1], 52          # 108
857        s_cbranch_scc1 loop1            # 112
858       
859        v_xor_b32 va[0], va[1], va[0]   # 116
860        v_xor_b32 va[0], va[2], va[0]   # 120
861        v_xor_b32 va[0], sa[0], va[0]   # 124
862       
863        s_add_u32 sa[0], sa[0], 1       # 128
864        s_cmp_lt_u32 sa[0], 33          # 132
865        s_cbranch_scc1 loop0            # 136
866       
867        s_endpgm                        # 140
868)ffDXD",
869        {   // livenesses
870            {   // for SGPRs
871                { { 1, 140 } }, // 0: sa[0]'0
872                { { 1, 2 } }, // 1: sa[1]'0
873                { { 57, 116 } }, // 2: sa[1]'1
874                { { 73, 77 } }, // 3: sa[2]'0
875                { { 25, 29 } }  // 4: sa[3]'0
876            },
877            {   // for VGPRs
878                { { 0, 5 } }, // 0: V1
879                { { 0, 9 } }, // 1: V2
880                { { 0, 13 } }, // 2: V3
881                { { 5, 17 }, { 125, 140 } }, // 3: va[0]'0
882                { { 17, 21 } }, // 4: va[0]'1
883                { { 21, 37 }, { 48, 49 } }, // 5: va[0]'2
884                { { 37, 41 } }, // 6: va[0]'3
885                { { 41, 48 }, { 53, 117 } }, // 7: va[0]'4
886                { { 117, 121 } }, // 8: va[0]'5
887                { { 121, 125 } }, // 9: va[0]'6
888                { { 49, 53 } }, // 10: va[0]'7
889                { { 9, 140 } }, // 11: va[1]'0
890                { { 13, 61 }, { 89, 96 }, { 101, 140 } }, // 12: va[2]'0
891                { { 61, 62 } }, // 13: va[2]'1
892                { { 65, 89 }, { 96, 101 } }  // 14: va[2]'2
893            },
894            { },
895            { }
896        },
897        {   // linearDepMaps
898            { // for SGPRs
899                { 0, { 2, { }, { 1 } } },
900                { 1, { 0, { 0 }, { } } }
901            },
902            { },
903            { },
904            { }
905        },
906        { },  // vidxRoutineMap
907        { },  // vidxCallMap
908        true, ""
909    },
910    {   // 15 - trick - SSA replaces beyond visited point
911        R"ffDXD(.regvar sa:s:8, va:v:8
912        s_mov_b32 sa[2], s4             # 0
913        s_mov_b32 sa[3], s5             # 4
914       
915loop:   s_xor_b32 sa[2], sa[2], sa[4]   # 8
916        s_cbranch_scc0 end              # 12
917       
918        s_xor_b32 sa[3], sa[2], sa[4]   # 16
919        s_cbranch_scc0 loop             # 20
920       
921        s_endpgm                        # 24
922       
923end:    s_xor_b32 sa[3], sa[3], sa[4]   # 28
924        s_endpgm                        # 32
925)ffDXD",
926        {   // livenesses
927            {   // for SGPRs
928                { { 0, 1 } }, // 0: S4
929                { { 0, 5 } }, // 1: S5
930                { { 1, 24 } }, // 2: sa[2]'0
931                { { 5, 16 }, { 17, 24 }, { 28, 29 } }, // 3: sa[3]'0
932                { { 29, 30 } }, // 4: sa[3]'1
933                { { 0, 24 }, { 28, 29 } }  // 5: sa[4]'0
934            },
935            { },
936            { },
937            { }
938        },
939        { },  // linearDepMaps
940        { },  // vidxRoutineMap
941        { },  // vidxCallMap
942        true, ""
943    },
944    {   // 16 - trick - SSA replaces beyond visited point
945        R"ffDXD(.regvar sa:s:8, va:v:8
946        s_mov_b32 sa[2], s4             # 0
947        s_mov_b32 sa[3], s5             # 4
948       
949loop:   s_xor_b32 sa[2], sa[2], sa[4]   # 8
950        s_cbranch_scc0 end              # 12
951       
952        s_xor_b32 sa[3], sa[2], sa[4]   # 16
953        s_cbranch_scc0 loop             # 20
954       
955end:    s_xor_b32 sa[3], sa[3], sa[4]   # 24
956        s_endpgm                        # 28
957)ffDXD",
958        {   // livenesses
959            {   // for SGPRs
960                { { 0, 1 } }, // 0: S4
961                { { 0, 5 } }, // 1: S5
962                { { 1, 24 } }, // 2: sa[2]'0
963                { { 5, 16 }, { 17, 25 } }, // 3: sa[3]'0
964                { { 25, 26 } }, // 4: sa[3]'1
965                { { 0, 25 } }  // 5: sa[4]'0
966            },
967            { },
968            { },
969            { }
970        },
971        { },  // linearDepMaps
972        { },  // vidxRoutineMap
973        { },  // vidxCallMap
974        true, ""
975    },
976    {   // 17 - simple call
977        R"ffDXD(.regvar sa:s:8, va:v:8
978        s_mov_b32 sa[2], s4             # 0
979        s_mov_b32 sa[3], s5             # 4
980       
981        s_getpc_b64 s[2:3]              # 8
982        s_add_u32 s2, s2, routine-.     # 12
983        s_add_u32 s3, s3, routine-.+4   # 20
984        .cf_call routine
985        s_swappc_b64 s[0:1], s[2:3]     # 28
986       
987        s_lshl_b32 sa[2], sa[2], 3      # 32
988        s_lshl_b32 sa[3], sa[3], 4      # 36
989        s_endpgm                        # 40
990       
991routine:
992        s_xor_b32 sa[2], sa[2], sa[4]   # 44
993        s_xor_b32 sa[3], sa[3], sa[4]   # 48
994        .cf_ret
995        s_setpc_b64 s[0:1]              # 52
996)ffDXD",
997        {   // livenesses
998            {   // for SGPRs
999                { { 29, 32 }, { 44, 53 } }, // 0: S0
1000                { { 29, 32 }, { 44, 53 } }, // 1: S1
1001                { { 9, 29 } }, // 2: S2
1002                { { 9, 29 } }, // 3: S3
1003                { { 0, 1 } }, // 4: S4
1004                { { 0, 5 } }, // 5: S5
1005                { { 1, 32 }, { 44, 45 } }, // 6: sa[2]'0
1006                { { 32, 33 }, { 45, 56 } }, // 7: sa[2]'1
1007                { { 33, 34 } }, // 8: sa[2]'2
1008                { { 5, 32 }, { 44, 49 } }, // 9: sa[3]'0
1009                { { 32, 37 }, { 49, 56 } }, // 10: sa[3]'1
1010                { { 37, 38 } }, // 11: sa[3]'2
1011                { { 0, 32 }, { 44, 49 } }  // 12: sa[4]'0
1012            },
1013            { },
1014            { },
1015            { }
1016        },
1017        { }, // linearDepMaps
1018        {   // vidxRoutineMap
1019            { 2, { { { 0, 1, 6, 7, 9, 10, 12 }, { }, { }, { } } } }
1020        },
1021        { },  // vidxCallMap
1022        true, ""
1023    },
1024    {   // 18 - simple call, more complex routine
1025        R"ffDXD(.regvar sa:s:8, va:v:8
1026        s_mov_b32 sa[2], s4             # 0
1027        s_mov_b32 sa[3], s5             # 4
1028        s_mov_b32 sa[5], s5             # 8
1029       
1030        s_getpc_b64 s[2:3]              # 12
1031        s_add_u32 s2, s2, routine-.     # 16
1032        s_add_u32 s3, s3, routine-.+4   # 24
1033        .cf_call routine
1034        s_swappc_b64 s[0:1], s[2:3]     # 32
1035       
1036        s_lshl_b32 sa[2], sa[2], 3      # 36
1037        s_lshl_b32 sa[3], sa[3], 4      # 40
1038        s_lshl_b32 sa[5], sa[5], 5      # 44
1039        s_endpgm                        # 48
1040       
1041routine:
1042        s_xor_b32 sa[2], sa[2], sa[4]   # 52
1043        s_xor_b32 sa[3], sa[3], sa[4]   # 56
1044        s_cbranch_scc1 bb1              # 60
1045       
1046        s_min_u32 sa[2], sa[2], sa[4]   # 64
1047        s_min_u32 sa[3], sa[3], sa[4]   # 68
1048        .cf_ret
1049        s_setpc_b64 s[0:1]              # 72
1050       
1051bb1:    s_and_b32 sa[2], sa[2], sa[4]   # 76
1052        s_and_b32 sa[3], sa[3], sa[4]   # 80
1053        .cf_ret
1054        s_setpc_b64 s[0:1]              # 84
1055)ffDXD",
1056        {   // livenesses
1057            {   // for SGPRs
1058                { { 33, 36 }, { 52, 73 }, { 76, 85 } }, // 0: S0
1059                { { 33, 36 }, { 52, 73 }, { 76, 85 } }, // 1: S1
1060                { { 13, 33 } }, // 2: S2
1061                { { 13, 33 } }, // 3: S3
1062                { { 0, 1 } }, // 4: S4
1063                { { 0, 9 } }, // 5: S5
1064                { { 1, 36 }, { 52, 53 } }, // 6: sa[2]'0
1065                { { 53, 65 }, { 76, 77 } }, // 7: sa[2]'1
1066                { { 36, 37 }, { 65, 76 }, { 77, 88 } }, // 8: sa[2]'2
1067                { { 37, 38 } }, // 9: sa[2]'3
1068                { { 5, 36 }, { 52, 57 } }, // 10: sa[3]'0
1069                { { 57, 69 }, { 76, 81 } }, // 11: sa[3]'1
1070                { { 36, 41 }, { 69, 76 }, { 81, 88 } }, // 12: sa[3]'2
1071                { { 41, 42 } }, // 13: sa[3]'3
1072                { { 0, 36 }, { 52, 69 }, { 76, 81 } }, // 14: sa[4]'0
1073                { { 9, 45 } }, // 15: sa[5]'0
1074                { { 45, 46 } }  // 16: sa[5]'1
1075            },
1076            { },
1077            { },
1078            { }
1079        },
1080        { }, // linearDepMaps
1081        {   // vidxRoutineMap
1082            { 2, { { { 0, 1, 6, 7, 8, 10, 11, 12, 14 }, { }, { }, { } } } }
1083        },
1084        {   // vidxCallMap
1085            { 0, { { { 15 }, { }, { }, { } } } }
1086        },
1087        true, ""
1088    },
1089    {   // 19 - simple call, more complex routine
1090        R"ffDXD(.regvar sa:s:8, va:v:8
1091        s_mov_b32 sa[2], s4             # 0
1092        s_mov_b32 sa[3], s5             # 4
1093        s_mov_b32 sa[5], s5             # 8
1094       
1095        s_getpc_b64 s[2:3]              # 12
1096        s_add_u32 s2, s2, routine-.     # 16
1097        s_add_u32 s3, s3, routine-.+4   # 24
1098        .cf_call routine
1099        s_swappc_b64 s[0:1], s[2:3]     # 32
1100       
1101        s_lshl_b32 sa[2], sa[2], 3      # 36
1102        s_lshl_b32 sa[3], sa[3], sa[5]  # 40
1103        s_endpgm                        # 44
1104       
1105routine:
1106        s_xor_b32 sa[2], sa[2], sa[4]   # 48
1107        s_cbranch_scc1 bb1              # 52
1108       
1109        s_min_u32 sa[2], sa[2], sa[4]   # 56
1110        s_xor_b32 sa[3], sa[3], sa[4]   # 60
1111        .cf_ret
1112        s_setpc_b64 s[0:1]              # 64
1113       
1114bb1:    s_and_b32 sa[2], sa[2], sa[4]   # 68
1115        .cf_ret
1116        s_setpc_b64 s[0:1]              # 72
1117)ffDXD",
1118        {   // livenesses
1119            {   // for SGPRs
1120                { { 33, 36 }, { 48, 65 }, { 68, 73 } }, // 0: S0
1121                { { 33, 36 }, { 48, 65 }, { 68, 73 } }, // 1: S1
1122                { { 13, 33 } }, // 2: S2
1123                { { 13, 33 } }, // 3: S3
1124                { { 0, 1 } }, // 4: S4
1125                { { 0, 9 } }, // 5: S5
1126                { { 1, 36 }, { 48, 49 } }, // 6: sa[2]'0
1127                { { 49, 57 }, { 68, 69 } }, // 7: sa[2]'1
1128                { { 36, 37 }, { 57, 68 }, { 69, 76 } }, // 8: sa[2]'2
1129                { { 37, 38 } }, // 9: sa[2]'3
1130                { { 5, 41 }, { 48, 76 } }, // 10: sa[3]'0
1131                { { 41, 42 } }, // 11: sa[3]'1
1132                { { 0, 36 }, { 48, 61 }, { 68, 69 } }, // 12: sa[4]'0
1133                { { 9, 41 } }  // 13: sa[5]'0
1134            },
1135            { },
1136            { },
1137            { }
1138        },
1139        { }, // linearDepMaps
1140        {   // vidxRoutineMap
1141            { 2, { { { 0, 1, 6, 7, 8, 10, 12 }, { }, { }, { } } } }
1142        },
1143        {   // vidxCallMap
1144            { 0, { { { 13 }, { }, { }, { } } } }
1145        },
1146        true, ""
1147    },
1148    {   // 20 - multiple call of routine
1149        R"ffDXD(.regvar sa:s:8, va:v:8
1150        s_mov_b32 sa[2], s4             # 0
1151        s_mov_b32 sa[3], s5             # 4
1152       
1153        s_getpc_b64 s[2:3]              # 8
1154        s_add_u32 s2, s2, routine-.     # 12
1155        s_add_u32 s3, s3, routine-.+4   # 20
1156        .cf_call routine
1157        s_swappc_b64 s[0:1], s[2:3]     # 28
1158       
1159        s_lshl_b32 sa[2], sa[2], 3      # 32
1160        s_lshl_b32 sa[3], sa[3], 4      # 36
1161       
1162        s_getpc_b64 s[2:3]              # 40
1163        s_add_u32 s2, s2, routine-.     # 44
1164        s_add_u32 s3, s3, routine-.+4   # 52
1165        .cf_call routine
1166        s_swappc_b64 s[0:1], s[2:3]     # 60
1167       
1168        s_ashr_i32 sa[2], sa[2], 3      # 64
1169        s_ashr_i32 sa[2], sa[2], 3      # 68
1170        s_ashr_i32 sa[3], sa[3], 4      # 72
1171        s_ashr_i32 sa[3], sa[3], 4      # 76
1172       
1173        s_getpc_b64 s[2:3]              # 80
1174        s_add_u32 s2, s2, routine-.     # 84
1175        s_add_u32 s3, s3, routine-.+4   # 92
1176        .cf_call routine
1177        s_swappc_b64 s[0:1], s[2:3]     # 100
1178       
1179        s_ashr_i32 sa[2], sa[2], 3      # 104
1180        s_ashr_i32 sa[3], sa[3], 3      # 108
1181        s_endpgm                        # 112
1182       
1183routine:
1184        s_xor_b32 sa[2], sa[2], sa[4]   # 116
1185        s_xor_b32 sa[3], sa[3], sa[4]   # 120
1186        s_cbranch_scc1 bb1              # 124
1187       
1188        s_min_u32 sa[2], sa[2], sa[4]   # 128
1189        .cf_ret
1190        s_setpc_b64 s[0:1]              # 132
1191       
1192bb1:    s_and_b32 sa[2], sa[2], sa[4]   # 136
1193        .cf_ret
1194        s_setpc_b64 s[0:1]              # 140
1195)ffDXD",
1196        {   // livenesses
1197            {
1198                { { 29, 32 }, { 61, 64 }, { 101, 104 },
1199                        { 116, 133 }, { 136, 141 } }, // 0: S0
1200                { { 29, 32 }, { 61, 64 }, { 101, 104 },
1201                        { 116, 133 }, { 136, 141 } }, // 1: S1
1202                { { 9, 29 }, { 41, 61 }, { 81, 101 } }, // 2: S2
1203                { { 9, 29 }, { 41, 61 }, { 81, 101 } }, // 3: S3
1204                { { 0, 1 } }, // 4: S4
1205                { { 0, 5 } }, // 5: S5
1206                { { 1, 32 }, { 33, 64 }, { 69, 104 }, { 116, 117 } }, // 6: sa[2]'0
1207                { { 117, 129 }, { 136, 137 } }, // 7: sa[2]'1
1208                { { 32, 33 }, { 64, 65 }, { 104, 105 },
1209                        { 129, 136 }, { 137, 144 } }, // 8: sa[2]'2
1210                { { 65, 69 } }, // 9: sa[2]'3
1211                { { 105, 106 } }, // 10: sa[2]'4
1212                { { 5, 32 }, { 37, 64 }, { 77, 104 }, { 116, 121 } }, // 11: sa[3]'0
1213                { { 32, 37 }, { 64, 73 }, { 104, 109 }, { 121, 144 } }, // 12: sa[3]'1
1214                { { 73, 77 } }, // 13: sa[3]'2
1215                { { 109, 110 } }, // 14: sa[3]'3
1216                { { 0, 104 }, { 116, 144 } }  // 15: sa[4]'0
1217            },
1218            { },
1219            { },
1220            { }
1221        },
1222        { }, // linearDepMaps
1223        {   // vidxRoutineMap
1224            { 4, { { { 0, 1, 6, 7, 8, 11, 12, 15 }, { }, { }, { } } } }
1225        },
1226        { }, // vidxCallMap
1227        true, ""
1228    },
1229    {   // 21 - many nested routines - path penetration
1230        R"ffDXD(.regvar sa:s:8, va:v:8
1231        .cf_call routine
1232        s_swappc_b64 s[0:1], s[2:3]         # 0
1233       
1234        s_add_u32 sa[7], sa[7], sa[1]       # 4
1235        s_add_u32 sa[7], sa[7], sa[2]       # 8
1236        s_add_u32 sa[7], sa[7], sa[3]       # 12
1237        s_add_u32 sa[7], sa[7], sa[4]       # 16
1238        s_add_u32 sa[7], sa[7], sa[5]       # 20
1239        s_add_u32 sa[7], sa[7], sa[6]       # 24
1240        v_xor_b32 va[7], va[7], va[0]       # 28
1241        v_xor_b32 va[7], va[7], va[1]       # 32
1242        v_xor_b32 va[7], va[7], va[2]       # 36
1243        v_xor_b32 va[7], va[7], va[3]       # 40
1244        s_endpgm                            # 44
1245       
1246routine:
1247        v_add_u32 va[3], vcc, va[3], va[1]  # 48
1248        s_cbranch_scc0 r1_2                 # 52
1249       
1250r1_1:   s_add_u32 sa[2], sa[2], sa[0]       # 56
1251        .cf_call routine2
1252        s_swappc_b64 s[0:1], s[2:3]         # 60
1253        v_add_u32 va[3], vcc, va[3], va[1]  # 64
1254        .cf_ret
1255        s_setpc_b64 s[0:1]                  # 68
1256       
1257r1_2:   s_add_u32 sa[6], sa[6], sa[0]       # 72
1258        .cf_call routine3
1259        s_swappc_b64 s[0:1], s[2:3]         # 76
1260        v_add_u32 va[2], vcc, va[2], va[1]  # 80
1261        .cf_ret
1262        s_setpc_b64 s[0:1]                  # 84
1263
1264routine2:
1265        s_add_u32 sa[2], sa[2], sa[0]       # 88
1266        s_cbranch_scc0 r2_2                 # 92
1267       
1268r2_1:   s_add_u32 sa[2], sa[2], sa[0]       # 96
1269        .cf_ret
1270        s_setpc_b64 s[0:1]                  # 100
1271r2_2:   s_add_u32 sa[3], sa[3], sa[0]       # 104
1272        .cf_ret
1273        s_setpc_b64 s[0:1]                  # 108
1274
1275routine3:
1276        s_add_u32 sa[4], sa[4], sa[0]       # 112
1277        s_cbranch_scc0 r3_2                 # 116
1278       
1279r3_1:   s_add_u32 sa[4], sa[4], sa[0]       # 120
1280        .cf_ret
1281        s_setpc_b64 s[0:1]                  # 124
1282r3_2:   s_add_u32 sa[5], sa[5], sa[0]       # 128
1283        s_cbranch_scc0 r3_4                 # 132
1284r3_3:   v_add_u32 va[0], vcc, va[0], va[1]  # 136
1285        .cf_ret
1286        s_setpc_b64 s[0:1]                  # 140
1287r3_4:
1288        v_add_u32 va[0], vcc, va[0], va[1]  # 144
1289        .cf_ret
1290        s_setpc_b64 s[0:1]                  # 148
1291)ffDXD",
1292        {   // livenesses
1293            {   // for SGPRs
1294                { { 1, 2 }, { 61, 69 }, { 77, 85 }, { 88, 152 } }, // 0: S0
1295                { { 1, 2 }, { 61, 69 }, { 77, 85 }, { 88, 152 } }, // 1: S1
1296                { { 0, 4 }, { 48, 61 }, { 72, 77 } }, // 2: S2
1297                { { 0, 4 }, { 48, 61 }, { 72, 77 } }, // 3: S3
1298                { { 0, 4 }, { 48, 64 }, { 72, 80 }, { 88, 97 },
1299                    { 104, 105 }, { 112, 121 }, { 128, 129 } }, // 4: sa[0]'0
1300                { { 0, 5 } }, // 5: sa[1]'0
1301                { { 0, 9 }, { 48, 88 }, { 89, 112 } }, // 6: sa[2]'0
1302                { { 57, 64 }, { 88, 89 } }, // 7: sa[2]'1
1303                { { 0, 13 }, { 48, 112 } }, // 8: sa[3]'0
1304                { { 0, 17 }, { 48, 88 }, { 112, 152 } }, // 9: sa[4]'0  // ???
1305                { { 0, 21 }, { 48, 88 }, { 112, 152 } }, // 10: sa[5]'0
1306                { { 0, 25 }, { 48, 88 } }, // 11: sa[6]'0
1307                { { 0, 5 } }, // 12: sa[7]'0
1308                { { 5, 9 } }, // 13: sa[7]'1
1309                { { 9, 13 } }, // 14: sa[7]'2
1310                { { 13, 17 } }, // 15: sa[7]'3
1311                { { 17, 21 } }, // 16: sa[7]'4
1312                { { 21, 25 } }, // 17: sa[7]'5
1313                { { 25, 26 } }  // 18: sa[7]'6
1314            },
1315            {   // for VGPRs
1316                { { 0, 29 }, { 48, 88 }, { 112, 152 } }, // 0: va[0]'0
1317                { { 0, 33 }, { 48, 88 }, { 112, 152 } }, // 1: va[1]'0
1318                { { 0, 37 }, { 48, 88 } }, // 2: va[2]'0
1319                { { 0, 4 }, { 48, 49 } }, // 3: va[3]'0
1320                { { 4, 41 }, { 49, 88 } }, // 4: va[3]'1
1321                { { 0, 29 } }, // 5: va[7]'0
1322                { { 29, 33 } }, // 6: va[7]'1
1323                { { 33, 37 } }, // 7: va[7]'2
1324                { { 37, 41 } }, // 8: va[7]'3
1325                { { 41, 42 } }  // 9: va[7]'4
1326            },
1327            { },
1328            { }
1329        },
1330        { }, // linearDepMaps
1331        {
1332            { 2, { {
1333                // SGPRs
1334                { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11 },
1335                // VGPRs
1336                { 0, 1, 2, 3, 4 }, { }, { } } } },
1337            { 7, { { { 0, 1, 4, 6, 7, 8 }, { }, { }, { } } } },
1338            { 10, { {
1339                // SGPRs
1340                { 0, 1, 4, 9, 10 },
1341                // VGPRs
1342                { 0, 1 }, { }, { } } } }
1343        }, // vidxRoutineMap
1344        {
1345            { 0, { { { 5, 12 }, { 5 }, { }, { } } } },
1346            { 3, { { { 9, 10, 11 }, { 0, 1, 2, 4 }, { }, { } } } },
1347            { 5, { { { 6, 8, 11 }, { 2, 4 }, { }, { } } } }
1348        }, // vidxCallMap
1349        true, ""
1350    },
1351    {   // 22 - simple call, more complex routine (first unused return)
1352        R"ffDXD(.regvar sa:s:8, va:v:8
1353        s_mov_b32 sa[2], s4             # 0
1354        s_mov_b32 sa[3], s5             # 4
1355        s_mov_b32 sa[5], s5             # 8
1356       
1357        s_getpc_b64 s[2:3]              # 12
1358        s_add_u32 s2, s2, routine-.     # 16
1359        s_add_u32 s3, s3, routine-.+4   # 24
1360        .cf_call routine
1361        s_swappc_b64 s[0:1], s[2:3]     # 32
1362       
1363        s_lshl_b32 sa[2], sa[2], 3      # 36
1364        s_lshl_b32 sa[3], sa[3], sa[5]  # 40
1365        s_endpgm                        # 44
1366       
1367routine:
1368        s_xor_b32 sa[2], sa[2], sa[4]   # 48
1369        s_cbranch_scc1 bb1              # 52
1370       
1371        s_min_u32 sa[2], sa[2], sa[4]   # 56
1372        .cf_ret
1373        s_setpc_b64 s[0:1]              # 60
1374       
1375bb1:    s_and_b32 sa[2], sa[2], sa[4]   # 64
1376        s_xor_b32 sa[3], sa[3], sa[4]   # 68
1377        .cf_ret
1378        s_setpc_b64 s[0:1]              # 72
1379)ffDXD",
1380        {   // livenesses
1381            {   // for SGPRs
1382                { { 33, 36 }, { 48, 61 }, { 64, 73 } }, // 0: S0
1383                { { 33, 36 }, { 48, 61 }, { 64, 73 } }, // 1: S1
1384                { { 13, 33 } }, // 2: S2
1385                { { 13, 33 } }, // 3: S3
1386                { { 0, 1 } }, // 4: S4
1387                { { 0, 9 } }, // 5: S5
1388                { { 1, 36 }, { 48, 49 } }, // 6: sa[2]'0
1389                { { 49, 57 }, { 64, 65 } }, // 7: sa[2]'1
1390                { { 36, 37 }, { 57, 64 }, { 65, 76 } }, // 8: sa[2]'2
1391                { { 37, 38 } }, // 9: sa[2]'3
1392                { { 5, 41 }, { 48, 76 } }, // 10: sa[3]'0
1393                { { 41, 42 } }, // 11: sa[3]'1
1394                { { 0, 36 }, { 48, 57 }, { 64, 69 } }, // 12: sa[4]'0
1395                { { 9, 41 } }  // 13: sa[5]'0
1396            },
1397            { },
1398            { },
1399            { }
1400        },
1401        { }, // linearDepMaps
1402        {   // vidxRoutineMap
1403            { 2, { { { 0, 1, 6, 7, 8, 10, 12 }, { }, { }, { } } } }
1404        },
1405        {   // vidxCallMap
1406            { 0, { { { 13 }, { }, { }, { } } } }
1407        },
1408        true, ""
1409    },
1410    {   // 23 - simple nested call (checking filling unused path)
1411        R"ffDXD(.regvar sa:s:8, va:v:8
1412        s_mov_b32 sa[2], s4             # 0
1413        s_mov_b32 sa[3], s5             # 4
1414        s_mov_b32 sa[5], s5             # 8
1415       
1416        .cf_call routine
1417        s_swappc_b64 s[0:1], s[2:3]     # 12
1418       
1419        s_lshl_b32 sa[2], sa[2], 3      # 16
1420        s_lshl_b32 sa[3], sa[3], sa[5]  # 20
1421        s_endpgm                        # 24
1422       
1423routine:
1424        s_xor_b32 sa[2], sa[2], sa[4]   # 28
1425        s_cbranch_scc1 bb1              # 32
1426       
1427        s_min_u32 sa[2], sa[2], sa[4]   # 36
1428        .cf_ret
1429        s_setpc_b64 s[0:1]              # 40
1430       
1431bb1:    s_and_b32 sa[2], sa[2], sa[4]   # 44
1432       
1433        .cf_call routine2
1434        s_swappc_b64 s[4:5], s[6:7]     # 48
1435       
1436        .cf_ret
1437        s_setpc_b64 s[0:1]              # 52
1438       
1439routine2:
1440        s_xor_b32 sa[3], sa[3], sa[4]   # 56
1441        .cf_ret
1442        s_setpc_b64 s[4:5]              # 60
1443)ffDXD",
1444        {   // livenesses
1445            {   // for SGPRs
1446                { { 13, 16 }, { 28, 41 }, { 44, 53 } }, // 0: S0
1447                { { 13, 16 }, { 28, 41 }, { 44, 53 } }, // 1: S1
1448                { { 0, 13 } }, // 2: S2
1449                { { 0, 13 } }, // 3: S3
1450                { { 0, 1 }, { 49, 52 }, { 56, 61 } }, // 4: S4
1451                { { 0, 9 }, { 49, 52 }, { 56, 61 } }, // 5: S5
1452                { { 0, 16 }, { 28, 36 }, { 44, 49 } }, // 6: S6
1453                { { 0, 16 }, { 28, 36 }, { 44, 49 } }, // 7: S7
1454                { { 1, 16 }, { 28, 29 } }, // 8: sa[2]'0
1455                { { 29, 37 }, { 44, 45 } }, // 9: sa[2]'1
1456                { { 16, 17 }, { 37, 44 }, { 45, 56 } }, // 10: sa[2]'2
1457                { { 17, 18 } }, // 11: sa[2]'3
1458                { { 5, 21 }, { 28, 64 } }, // 12: sa[3]'0
1459                { { 21, 22 } }, // 13: sa[3]'1
1460                { { 0, 16 }, { 28, 37 }, { 44, 52 }, { 56, 57 } }, // 14: sa[4]'0
1461                { { 9, 21 } }  // 15: sa[5]'0
1462            },
1463            { },
1464            { },
1465            { }
1466        },
1467        { }, // linearDepMaps
1468        {   // vidxRoutineMap
1469            { 2, { { { 0, 1, 4, 5, 6, 7, 8, 9, 10, 12, 14 }, { }, { }, { } } } },
1470            { 6, { { { 4, 5, 12, 14 }, { }, { }, { } } } }
1471        },
1472        {   // vidxCallMap
1473            { 0, { { { 15 }, { }, { }, { } } } },
1474            { 4, { { { 0, 1, 10 }, { }, { }, { } } } }
1475        },
1476        true, ""
1477    },
1478    {   // 24 - simple call, more complex routine (sa[3] and sa[6] not used after call)
1479        R"ffDXD(.regvar sa:s:8, va:v:8
1480        s_mov_b32 sa[2], s4             # 0
1481        s_mov_b32 sa[3], s5             # 4
1482        s_mov_b32 sa[5], s5             # 8
1483       
1484        s_getpc_b64 s[2:3]              # 12
1485        s_add_u32 s2, s2, routine-.     # 16
1486        s_add_u32 s3, s3, routine-.+4   # 24
1487        .cf_call routine
1488        s_swappc_b64 s[0:1], s[2:3]     # 32
1489       
1490        s_lshl_b32 sa[2], sa[2], sa[5]  # 36
1491        s_nop 7                         # 40
1492        s_endpgm                        # 44
1493       
1494routine:
1495        s_xor_b32 sa[2], sa[2], sa[4]   # 48
1496        s_xor_b32 sa[6], sa[6], sa[4]   # 52
1497        s_cbranch_scc1 bb1              # 56
1498       
1499        s_min_u32 sa[2], sa[2], sa[4]   # 60
1500        s_xor_b32 sa[3], sa[3], sa[4]   # 64
1501        .cf_ret
1502        s_setpc_b64 s[0:1]              # 68
1503       
1504bb1:    s_and_b32 sa[2], sa[2], sa[4]   # 72
1505        .cf_ret
1506        s_setpc_b64 s[0:1]              # 76
1507)ffDXD",
1508        {   // livenesses
1509            {   // for SGPRs
1510                { { 33, 36 }, { 48, 69 }, { 72, 77 } }, // 0: S0
1511                { { 33, 36 }, { 48, 69 }, { 72, 77 } }, // 1: S1
1512                { { 13, 33 } }, // 2: S2
1513                { { 13, 33 } }, // 3: S3
1514                { { 0, 1 } }, // 4: S4
1515                { { 0, 9 } }, // 5: S5
1516                { { 1, 36 }, { 48, 49 } }, // 6: sa[2]'0
1517                { { 49, 61 }, { 72, 73 } }, // 7: sa[2]'1
1518                { { 36, 37 }, { 61, 72 }, { 73, 80 } }, // 8: sa[2]'2
1519                { { 37, 38 } }, // 9: sa[2]'3
1520                { { 5, 36 }, { 48, 65 } }, // 10: sa[3]'0
1521                { { 65, 66 } }, // 11: sa[3]'1
1522                { { 0, 36 }, { 48, 65 }, { 72, 73 } }, // 12: sa[4]'0
1523                { { 9, 37 } },  // 13: sa[5]'0
1524                { { 0, 36 }, { 48, 53 } }, // 14: sa[6]'0
1525                { { 53, 54 } }  // 15: sa[6]'1
1526            },
1527            { },
1528            { },
1529            { }
1530        },
1531        { }, // linearDepMaps
1532        {   // vidxRoutineMap
1533            { 2, { { { 0, 1, 6, 7, 8, 10, 11, 12, 14, 15 }, { }, { }, { } } } }
1534        },
1535        {   // vidxCallMap
1536            { 0, { { { 13 }, { }, { }, { } } } }
1537        },
1538        true, ""
1539    },
1540    {   // 25 - many routines and many calls. all vars in all return paths
1541        R"ffDXD(.regvar sa:s:8, va:v:8
1542        .cf_call routine
1543        s_swappc_b64 s[0:1], s[2:3]         # 0
1544       
1545        s_add_u32 sa[7], sa[7], sa[1]       # 4
1546        s_add_u32 sa[7], sa[7], sa[2]       # 8
1547        s_add_u32 sa[7], sa[7], sa[3]       # 12
1548        s_add_u32 sa[7], sa[7], sa[4]       # 16
1549        v_xor_b32 va[7], va[7], va[1]       # 20
1550        v_xor_b32 va[7], va[7], va[2]       # 24
1551        v_xor_b32 va[7], va[7], va[3]       # 28
1552        s_endpgm                            # 32
1553       
1554routine:
1555        s_add_u32 sa[2], sa[2], sa[0]       # 36
1556        s_cbranch_scc0 r1_2                 # 40
1557r1_1:
1558        v_add_u32 va[2], vcc, va[2], va[0]  # 44
1559        .cf_call routine2
1560        s_swappc_b64 s[0:1], s[2:3]         # 48
1561        v_add_u32 va[1], vcc, va[1], va[0]  # 52
1562        s_add_u32 sa[1], sa[1], sa[0]       # 56
1563        v_add_u32 va[3], vcc, va[3], va[0]  # 60
1564        .cf_ret
1565        s_setpc_b64 s[0:1]                  # 64
1566r1_2:
1567        s_add_u32 sa[3], sa[3], sa[0]       # 68
1568        s_add_u32 sa[1], sa[1], sa[0]       # 72
1569        .cf_call routine3
1570        s_swappc_b64 s[0:1], s[2:3]         # 76
1571        s_add_u32 sa[4], sa[4], sa[0]       # 80
1572        .cf_ret
1573        s_setpc_b64 s[0:1]                  # 84
1574       
1575routine2:
1576        s_add_u32 sa[3], sa[3], sa[0]       # 88
1577        s_cbranch_scc0 r2_2                 # 92
1578r2_1:
1579        s_add_u32 sa[4], sa[4], sa[0]       # 96
1580        .cf_ret
1581        s_setpc_b64 s[0:1]                  # 100
1582r2_2:
1583        s_add_u32 sa[4], sa[4], sa[0]       # 104
1584        .cf_ret
1585        s_setpc_b64 s[0:1]                  # 108
1586       
1587routine3:
1588        v_add_u32 va[1], vcc, va[1], va[0]  # 112
1589        v_add_u32 va[3], vcc, va[3], va[0]  # 116
1590        s_cbranch_scc0 r3_2                 # 120
1591r3_1:
1592        v_add_u32 va[2], vcc, va[2], va[0]  # 124
1593        .cf_ret
1594        s_setpc_b64 s[0:1]                  # 128
1595r3_2:
1596        v_add_u32 va[2], vcc, va[2], va[0]  # 132
1597        s_cbranch_scc1 r3_3                 # 136
1598        .cf_ret
1599        s_setpc_b64 s[0:1]                  # 140
1600r3_3:
1601        v_add_u32 va[3], vcc, va[3], va[0]  # 144
1602        .cf_ret
1603        s_setpc_b64 s[0:1]                  # 148
1604)ffDXD",
1605        {   // livenesses
1606            {   // SGPRs
1607                { { 1, 2 }, { 49, 65 }, { 77, 85 }, { 88, 152 } }, // 0: S0
1608                { { 1, 2 }, { 49, 65 }, { 77, 85 }, { 88, 152 } }, // 1: S1
1609                { { 0, 4 }, { 36, 49 }, { 68, 77 } }, // 2: S2
1610                { { 0, 4 }, { 36, 49 }, { 68, 77 } }, // 3: S3
1611                { { 0, 4 }, { 36, 57 }, { 68, 81 }, { 88, 112 } }, // 4: sa[0]'0
1612                { { 0, 4 }, { 36, 57 }, { 68, 73 } }, // 5: sa[1]'0
1613                { { 4, 5 }, { 57, 68 }, { 73, 88 } }, // 6: sa[1]'1
1614                { { 0, 4 }, { 36, 37 } }, // 7: sa[2]'0
1615                { { 4, 9 }, { 37, 88 } }, // 8: sa[2]'1
1616                { { 0, 4 }, { 36, 52 }, { 68, 69 }, { 88, 89 } }, // 9: sa[3]'0
1617                { { 4, 13 }, { 52, 68 }, { 69, 88 }, { 89, 112 } }, // 10: sa[3]'1
1618                { { 0, 4 }, { 36, 52 }, { 68, 81 },
1619                        { 88, 97 }, { 104, 105 } }, // 11: sa[4]'0
1620                { { 4, 17 }, { 52, 68 }, { 81, 88 },
1621                        { 97, 104 }, { 105, 112 } }, // 12: sa[4]'1
1622                { { 0, 5 } }, // 13: sa[7]'0
1623                { { 5, 9 } }, // 14: sa[7]'1
1624                { { 9, 13 } }, // 15: sa[7]'2
1625                { { 13, 17 } }, // 16: sa[7]'3
1626                { { 17, 18 } }  // 17: sa[7]'4
1627            },
1628            {   // for VPGRs
1629                { { 0, 4 }, { 36, 61 }, { 68, 80 },
1630                        { 112, 125 }, { 132, 140 }, { 144, 145 } }, // 0: va[0]'0
1631                { { 0, 4 }, { 36, 53 }, { 68, 80 }, { 112, 113 } }, // 1: va[1]'0
1632                { { 4, 21 }, { 53, 68 }, { 80, 88 }, { 113, 152 } }, // 2: va[1]'1
1633                { { 0, 4 }, { 36, 45 }, { 68, 80 },
1634                        { 112, 125 }, { 132, 133 } }, // 3: va[2]'0
1635                { { 4, 25 }, { 45, 68 }, { 80, 88 },
1636                        { 125, 132 }, { 133, 152 } }, // 4: va[2]'1
1637                { { 0, 4 }, { 36, 61 }, { 68, 80 }, { 112, 117 } }, // 5: va[3]'0
1638                { { 4, 29 }, { 61, 68 }, { 80, 88 }, { 117, 152 } }, // 6: va[3]'1
1639                { { 0, 21 } }, // 7: va[7]'0
1640                { { 21, 25 } }, // 8: va[7]'1
1641                { { 25, 29 } }, // 9: va[7]'2
1642                { { 29, 30 } }  // 10: va[7]'3
1643            },
1644            { },
1645            { }
1646        },
1647        { }, // linearDepMaps
1648        {   // vidxRoutineMap
1649            { 2, { {
1650                { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }, // for SGPRs
1651                { 0, 1, 2, 3, 4, 5, 6 }, // for VGPRs
1652                { }, { } } } },
1653            { 7, { {
1654                { 0, 1, 4, 9, 10, 11, 12 }, // for SGPRs
1655                { }, { }, { } } } },
1656            { 10, { { { 0, 1 },  // for SGPRs
1657                { 0, 1, 2, 3, 4, 5, 6 }, // for VGPRs
1658                { }, { } } } }
1659        },
1660        {   // vidxCallMap
1661            { 0, { { { 13 }, { 7 }, { }, { } } } },
1662            { 3, { { { 5, 8 }, { 0, 1, 4, 5 }, { }, { } } } },
1663            { 5, { { { 4, 6, 8, 10, 11 }, { }, { }, { } } } }
1664        },
1665        true, ""
1666    },
1667    {   // 26 - routine with loop
1668        R"ffDXD(.regvar sa:s:8, va:v:8, xa:s:8
1669        s_mov_b32 sa[2], s4             # 0
1670       
1671        .cf_call routine
1672        s_swappc_b64 s[0:1], s[2:3]     # 4
1673       
1674        s_xor_b32 sa[2], sa[2], sa[0]   # 8
1675        s_endpgm                        # 12
1676       
1677routine:
1678        s_and_b32 sa[2], sa[2], sa[1]   # 16
1679loop0:
1680        s_cbranch_vccz b1               # 20
1681b0:     s_cbranch_scc0 loop0            # 24
1682        s_branch ret2                   # 28
1683       
1684b1:     s_and_b32 sa[2], sa[0], sa[1]   # 32
1685        s_cbranch_scc0 loop0            # 36
1686        .cf_ret
1687        s_setpc_b64 s[0:1]              # 40
1688ret2:
1689        .cf_ret
1690        s_setpc_b64 s[0:1]              # 44
1691)ffDXD",
1692        {   // livenesses
1693            {   // for SGPRs
1694                { { 5, 8 }, { 16, 41 }, { 44, 45 } }, // 0: S0
1695                { { 5, 8 }, { 16, 41 }, { 44, 45 } }, // 1: S1
1696                { { 0, 5 } }, // 2: S2
1697                { { 0, 5 } }, // 3: S3
1698                { { 0, 1 } }, // 4: S4
1699                { { 0, 9 }, { 16, 48 } }, // 5: sa[0]'0
1700                { { 0, 8 }, { 16, 28 }, { 32, 40 } }, // 6: sa[1]'0
1701                { { 1, 8 }, { 16, 17 } }, // 7: sa[2]'0
1702                { { 8, 9 }, { 17, 48 } }, // 8: sa[2]'1
1703                { { 9, 10 } }  // 9: sa[2]'2
1704            },
1705            { },
1706            { },
1707            { }
1708        },
1709        { }, // linearDepMaps
1710        {   // vidxRoutineMap
1711            { 2, { { { 0, 1, 5, 6, 7, 8 }, { }, { }, { } } } }
1712        },
1713        { }, // vidxCallMap
1714        true, ""
1715    },
1716    {   // 27 - routine with loop (normal register instead regvar)
1717        R"ffDXD(.regvar sa:s:8, va:v:8, xa:s:8
1718        s_mov_b32 s6, s4                # 0
1719       
1720        .cf_call routine
1721        s_swappc_b64 s[0:1], s[2:3]     # 4
1722       
1723        s_xor_b32 s6, s6, sa[0]         # 8
1724        s_endpgm                        # 12
1725       
1726routine:
1727        s_and_b32 s6, s6, sa[1]         # 16
1728loop0:
1729        s_cbranch_vccz b1               # 20
1730b0:     s_cbranch_scc0 loop0            # 24
1731        s_branch ret2                   # 28
1732       
1733b1:     s_and_b32 s6, sa[0], sa[1]      # 32
1734        s_cbranch_scc0 loop0            # 36
1735        .cf_ret
1736        s_setpc_b64 s[0:1]              # 40
1737ret2:
1738        .cf_ret
1739        s_setpc_b64 s[0:1]              # 44
1740)ffDXD",
1741        {   // livenesses
1742            {   // for SGPRs
1743                { { 5, 8 }, { 16, 41 }, { 44, 45 } }, // 0: S0
1744                { { 5, 8 }, { 16, 41 }, { 44, 45 } }, // 1: S1
1745                { { 0, 5 } }, // 2: S2
1746                { { 0, 5 } }, // 3: S3
1747                { { 0, 1 } }, // 4: S4
1748                { { 1, 10 }, { 16, 48 } }, // 5: s6
1749                { { 0, 9 }, { 16, 48 } }, // 6: sa[0]'0
1750                { { 0, 8 }, { 16, 28 }, { 32, 40 } } // 7: sa[1]'0
1751            },
1752            { },
1753            { },
1754            { }
1755        },
1756        { }, // linearDepMaps
1757        {   // vidxRoutineMap
1758            { 2, { { { 0, 1, 5, 6, 7 }, { }, { }, { } } } }
1759        },
1760        { }, // vidxCallMap
1761        true, ""
1762    },
1763    {   // 28 - two routines with var sharing (output-input)
1764        R"ffDXD(.regvar sa:s:8, va:v:8, xa:s:8
1765        s_mov_b32 sa[2], s4             # 0
1766       
1767        .cf_call routine
1768        s_swappc_b64 s[0:1], s[2:3]     # 4
1769       
1770        s_sub_u32 sa[3], sa[2], sa[1]   # 8
1771        .cf_jump a0, a1, a2
1772        s_setpc_b64 s[2:3]              # 12
1773       
1774a0:     .cf_call routine2
1775        s_swappc_b64 s[0:1], s[2:3]     # 16
1776        s_xor_b32 sa[2], sa[2], sa[0]   # 20
1777        s_endpgm                        # 24
1778
1779a1:     .cf_call routine2
1780        s_swappc_b64 s[0:1], s[2:3]     # 28
1781        s_xor_b32 sa[2], sa[2], sa[0]   # 32
1782        s_endpgm                        # 36
1783       
1784a2:     .cf_call routine2
1785        s_swappc_b64 s[0:1], s[2:3]     # 40
1786        s_xor_b32 sa[2], sa[2], sa[0]   # 44
1787        s_endpgm                        # 48
1788       
1789routine:
1790        s_and_b32 sa[2], sa[2], sa[1]   # 52
1791        .cf_ret
1792        s_setpc_b64 s[0:1]              # 56
1793       
1794routine2:
1795        s_cbranch_vccz r2_1             # 60
1796r2_0:   s_and_b32 sa[2], sa[2], sa[1]   # 64
1797        .cf_ret
1798        s_setpc_b64 s[0:1]              # 68
1799r2_1:   s_and_b32 sa[2], sa[2], sa[1]   # 72
1800        s_xor_b32 sa[3], sa[3], sa[1]   # 76
1801        .cf_ret
1802        s_setpc_b64 s[0:1]              # 80
1803)ffDXD",
1804        {   // livenesses
1805            {   // for SGPRs
1806                { { 5, 8 }, { 17, 20 }, { 29, 32 }, { 41, 44 },
1807                    { 52, 57 }, { 60, 69 }, { 72, 81 } }, // 0: S0
1808                { { 5, 8 }, { 17, 20 }, { 29, 32 }, { 41, 44 },
1809                    { 52, 57 }, { 60, 69 }, { 72, 81 } }, // 1: S1
1810                { { 0, 17 }, { 28, 29 }, { 40, 41 } }, // 2: S2
1811                { { 0, 17 }, { 28, 29 }, { 40, 41 } }, // 3: S3
1812                { { 0, 1 } }, // 4: S4
1813                { { 0, 21 }, { 28, 33 }, { 40, 45 } }, // 5: sa[0]'0
1814                { { 0, 20 }, { 28, 32 }, { 40, 44 },
1815                    { 52, 65 }, { 72, 77 } }, // 6: sa[1]'0
1816                { { 1, 8 }, { 52, 53 } }, // 7: sa[2]'0
1817                { { 8, 20 }, { 28, 32 }, { 40, 44 },
1818                    { 53, 65 }, { 72, 73 } }, // 8: sa[2]'1
1819                { { 20, 21 }, { 32, 33 }, { 44, 45 },
1820                    { 65, 72 }, { 73, 84 } }, // 9: sa[2]'2
1821                { { 21, 22 } }, // 10: sa[2]'3
1822                { { 33, 34 } }, // 11: sa[2]'4
1823                { { 45, 46 } }, // 12: sa[2]'5
1824                { { 9, 20 }, { 28, 32 }, { 40, 44 },
1825                    { 60, 64 }, { 72, 77 } }, // 13: sa[3]'0
1826                { { 77, 78 } }  // 14: sa[3]'1
1827            },
1828            { },
1829            { },
1830            { }
1831        },
1832        { }, // linearDepMaps
1833        {   // vidxRoutineMap
1834            { 8, { { { 0, 1, 6, 7, 8 }, { }, { }, { } } } },
1835            { 9, { { { 0, 1, 6, 8, 9, 13, 14 }, { }, { }, { } } } }
1836        },
1837        {   // vidxCallMap
1838            { 0, { { { 2, 3, 5 }, { }, { }, { } } } },
1839            { 2, { { { 5 }, { }, { }, { } } } },
1840            { 4, { { { 5 }, { }, { }, { } } } },
1841            { 6, { { { 5 }, { }, { }, { } } } }
1842        },
1843        true, ""
1844    },
1845        {   // 29 - two routines with var sharing (output-input) 2
1846        R"ffDXD(.regvar sa:s:8, va:v:8, xa:s:8
1847        s_mov_b32 sa[2], s4             # 0
1848       
1849        .cf_call routine
1850        s_swappc_b64 s[0:1], s[2:3]     # 4
1851       
1852        s_sub_u32 sa[3], sa[2], sa[1]   # 8
1853        .cf_jump a0, a1, a2
1854        s_setpc_b64 s[2:3]              # 12
1855       
1856a0:     s_branch mp                     # 16
1857       
1858a1:     s_branch mp                     # 20
1859       
1860a2:     s_branch mp                     # 24
1861       
1862mp:     .cf_call routine2
1863        s_swappc_b64 s[0:1], s[2:3]     # 28
1864        s_xor_b32 sa[2], sa[2], sa[0]   # 32
1865        s_endpgm                        # 36
1866       
1867routine:
1868        s_and_b32 sa[2], sa[2], sa[1]   # 40
1869        .cf_ret
1870        s_setpc_b64 s[0:1]              # 44
1871       
1872routine2:
1873        s_cbranch_vccz r2_1             # 48
1874r2_0:   s_and_b32 sa[2], sa[2], sa[1]   # 52
1875        .cf_ret
1876        s_setpc_b64 s[0:1]              # 56
1877r2_1:   s_and_b32 sa[2], sa[2], sa[1]   # 60
1878        s_xor_b32 sa[3], sa[3], sa[1]   # 64
1879        .cf_ret
1880        s_setpc_b64 s[0:1]              # 68
1881)ffDXD",
1882        {   // livenesses
1883            {   // for SGPRs
1884                { { 5, 8 }, { 29, 32 }, { 40, 45 }, { 48, 57 }, { 60, 69 } }, // 0: S0
1885                { { 5, 8 }, { 29, 32 }, { 40, 45 }, { 48, 57 }, { 60, 69 } }, // 1: S1
1886                { { 0, 29 } }, // 2: S2
1887                { { 0, 29 } }, // 3: S3
1888                { { 0, 1 } }, // 4: S4
1889                { { 0, 33 } }, // 5: sa[0]'0
1890                { { 0, 32 }, { 40, 53 }, { 60, 65 } }, // 6: sa[1]'0
1891                { { 1, 8 }, { 40, 41 } }, // 7: sa[2]'0
1892                { { 8, 32 }, { 41, 53 }, { 60, 61 } }, // 8: sa[2]'1
1893                { { 32, 33 }, { 53, 60 }, { 61, 72 } }, // 9: sa[2]'2
1894                { { 33, 34 } }, // 10: sa[2]'3
1895                { { 9, 32 }, { 48, 52 }, { 60, 65 } }, // 11: sa[3]'0
1896                { { 65, 66 } }  // 12: sa[3]'1
1897            },
1898            { },
1899            { },
1900            { }
1901        },
1902        { }, // linearDepMaps
1903        {   // vidxRoutineMap
1904            { 7, { { { 0, 1, 6, 7, 8 }, { }, { }, { } } } },
1905            { 8, { { { 0, 1, 6, 8, 9, 11, 12 }, { }, { }, { } } } }
1906        },
1907        {   // vidxCallMap
1908            { 0, { { { 2, 3, 5 }, { }, { }, { } } } },
1909            { 5, { { { 5 }, { }, { }, { } } } }
1910        },
1911        true, ""
1912    },
1913    {   // 30 - two routines with var sharing (output-input) 3
1914        // (shared var in called routine3)
1915        R"ffDXD(.regvar sa:s:8, va:v:8, xa:s:8
1916        s_mov_b32 sa[2], s4             # 0
1917       
1918        .cf_call routine
1919        s_swappc_b64 s[0:1], s[2:3]     # 4
1920       
1921        s_sub_u32 sa[3], sa[2], sa[1]   # 8
1922        .cf_jump a0, a1, a2
1923        s_setpc_b64 s[2:3]              # 12
1924       
1925a0:     s_branch mp                     # 16
1926       
1927a1:     s_branch mp                     # 20
1928       
1929a2:     s_branch mp                     # 24
1930       
1931mp:     .cf_call routine2
1932        s_swappc_b64 s[0:1], s[2:3]     # 28
1933        s_xor_b32 sa[2], sa[2], sa[0]   # 32
1934        s_endpgm                        # 36
1935       
1936routine:
1937        s_and_b32 sa[2], sa[2], sa[1]   # 40
1938        .cf_ret
1939        s_setpc_b64 s[0:1]              # 44
1940       
1941routine2:
1942        s_cbranch_vccz r2_1             # 48
1943r2_0:   .cf_call routine3
1944        s_swappc_b64 s[6:7], s[0:1]     # 52
1945        .cf_ret
1946        s_setpc_b64 s[0:1]              # 56
1947r2_1:   .cf_call routine3
1948        s_swappc_b64 s[6:7], s[0:1]     # 60
1949        s_xor_b32 sa[3], sa[3], sa[1]   # 64
1950        .cf_ret
1951        s_setpc_b64 s[0:1]              # 68
1952routine3:
1953        s_and_b32 sa[2], sa[2], sa[1]   # 72
1954        .cf_ret
1955        s_setpc_b64 s[0:1]              # 76
1956)ffDXD",
1957        {   // livenesses
1958            {   // for SGPRs
1959                { { 5, 8 }, { 29, 32 }, { 40, 45 },
1960                    { 48, 57 }, { 60, 69 }, { 72, 80 } }, // 0: S0
1961                { { 5, 8 }, { 29, 32 }, { 40, 45 },
1962                    { 48, 57 }, { 60, 69 }, { 72, 80 } }, // 1: S1
1963                { { 0, 29 } }, // 2: S2
1964                { { 0, 29 } }, // 3: S3
1965                { { 0, 1 } }, // 4: S4
1966                { { 53, 54 }, { 61, 62 } }, // 5: S6
1967                { { 53, 54 }, { 61, 62 } }, // 6: S7
1968                { { 0, 33 } }, // 7: sa[0]'0
1969                { { 0, 32 }, { 40, 56 }, { 60, 65 }, { 72, 80 } }, // 8: sa[1]'0
1970                { { 1, 8 }, { 40, 41 } }, // 9: sa[2]'0
1971                { { 8, 32 }, { 41, 56 }, { 60, 64 }, { 72, 73 } }, // 10: sa[2]'1
1972                { { 32, 33 }, { 56, 60 }, { 64, 72 }, { 73, 80 } }, // 11: sa[2]'2
1973                { { 33, 34 } }, // 12: sa[2]'3
1974                { { 9, 32 }, { 48, 52 }, { 60, 65 } }, // 13: sa[3]'0
1975                { { 65, 66 } }  // 14: sa[3]'1
1976            },
1977            { },
1978            { },
1979            { }
1980        },
1981        { }, // linearDepMaps
1982        {   // vidxRoutineMap
1983            { 7, { { { 0, 1, 8, 9, 10 }, { }, { }, { } } } },
1984            { 8, { { { 0, 1, 8, 10, 11, 13, 14 }, { }, { }, { } } } },
1985            { 13, { { { 0, 1, 8, 10, 11 }, { }, { }, { } } } }
1986        },
1987        {   // vidxCallMap
1988            { 0, { { { 2, 3, 7 }, { }, { }, { } } } },
1989            { 5, { { { 7 }, { }, { }, { } } } },
1990            { 11, { { { 13 }, { }, { }, { } } } }
1991        },
1992        true, ""
1993    }
1994};
1995
1996static TestSingleVReg getTestSingleVReg(const AsmSingleVReg& vr,
1997        const std::unordered_map<const AsmRegVar*, CString>& rvMap)
1998{
1999    if (vr.regVar == nullptr)
2000        return { "", vr.index };
2001   
2002    auto it = rvMap.find(vr.regVar);
2003    if (it == rvMap.end())
2004        throw Exception("getTestSingleVReg: RegVar not found!!");
2005    return { it->second, vr.index };
2006}
2007
2008static void checkVIdxSetEntries(const std::string& testCaseName, const char* vvarSetName,
2009        const Array<std::pair<size_t, VIdxSetEntry2> >& expVIdxRoutineMap,
2010        const std::unordered_map<size_t,VIdxSetEntry>& vidxRoutineMap,
2011        const std::vector<size_t>* revLvIndexCvtTables)
2012{
2013    assertValue("testAsmLivenesses", testCaseName + vvarSetName + ".size",
2014            expVIdxRoutineMap.size(), vidxRoutineMap.size());
2015   
2016    for (size_t j = 0; j < vidxRoutineMap.size(); j++)
2017    {
2018        std::ostringstream vOss;
2019        vOss << vvarSetName << "#" << j;
2020        vOss.flush();
2021        std::string vcname(vOss.str());
2022       
2023        auto vcit = vidxRoutineMap.find(expVIdxRoutineMap[j].first);
2024        std::ostringstream kOss;
2025        kOss << expVIdxRoutineMap[j].first;
2026        kOss.flush();
2027        assertTrue("testAsmLivenesses", testCaseName + vcname +".key=" + kOss.str(),
2028                    vcit != vidxRoutineMap.end());
2029       
2030        const Array<size_t>* expEntry = expVIdxRoutineMap[j].second.vs;
2031        const VIdxSetEntry& resEntry = vcit->second;
2032        for (cxuint r = 0; r < MAX_REGTYPES_NUM; r++)
2033        {
2034            std::ostringstream vsOss;
2035            vsOss << ".vs#" << r;
2036            vsOss.flush();
2037            std::string vsname = vcname + vsOss.str();
2038           
2039            assertValue("testAsmLivenesses", testCaseName + vsname +".size",
2040                    expEntry[r].size(), resEntry.vs[r].size());
2041           
2042            std::vector<size_t> resVVars;
2043            std::transform(resEntry.vs[r].begin(), resEntry.vs[r].end(),
2044                    std::back_inserter(resVVars),
2045                    [&r,&revLvIndexCvtTables](size_t v)
2046                    { return revLvIndexCvtTables[r][v]; });
2047            std::sort(resVVars.begin(), resVVars.end());
2048            assertArray("testAsmLivenesses", testCaseName + vsname,
2049                        expEntry[r], resVVars);
2050        }
2051    }
2052}
2053
2054static void testCreateLivenessesCase(cxuint i, const AsmLivenessesCase& testCase)
2055{
2056    std::istringstream input(testCase.input);
2057    std::ostringstream errorStream;
2058   
2059    Assembler assembler("test.s", input,
2060                    (ASM_ALL&~ASM_ALTMACRO) | ASM_TESTRUN | ASM_TESTRESOLVE,
2061                    BinaryFormat::RAWCODE, GPUDeviceType::CAPE_VERDE, errorStream);
2062    bool good = assembler.assemble();
2063    if (assembler.getSections().size()<1)
2064    {
2065        std::ostringstream oss;
2066        oss << "FAILED for " << " testAsmLivenesses#" << i;
2067        throw Exception(oss.str());
2068    }
2069    const AsmSection& section = assembler.getSections()[0];
2070   
2071    AsmRegAllocator regAlloc(assembler);
2072   
2073    regAlloc.createCodeStructure(section.codeFlow, section.getSize(),
2074                            section.content.data());
2075    regAlloc.createSSAData(*section.usageHandler);
2076    regAlloc.applySSAReplaces();
2077    regAlloc.createLivenesses(*section.usageHandler);
2078   
2079    std::ostringstream oss;
2080    oss << " testAsmLivenesses case#" << i;
2081    const std::string testCaseName = oss.str();
2082   
2083    assertValue<bool>("testAsmLivenesses", testCaseName+".good",
2084                      testCase.good, good);
2085    assertString("testAsmLivenesses", testCaseName+".errorMessages",
2086              testCase.errorMessages, errorStream.str());
2087   
2088    std::unordered_map<const AsmRegVar*, CString> regVarNamesMap;
2089    for (const auto& rvEntry: assembler.getRegVarMap())
2090        regVarNamesMap.insert(std::make_pair(&rvEntry.second, rvEntry.first));
2091   
2092    // generate livenesses indices conversion table
2093    const VarIndexMap* vregIndexMaps = regAlloc.getVregIndexMaps();
2094   
2095    std::vector<size_t> lvIndexCvtTables[MAX_REGTYPES_NUM];
2096    std::vector<size_t> revLvIndexCvtTables[MAX_REGTYPES_NUM];
2097    for (size_t r = 0; r < MAX_REGTYPES_NUM; r++)
2098    {
2099        const VarIndexMap& vregIndexMap = vregIndexMaps[r];
2100        Array<std::pair<TestSingleVReg, const std::vector<size_t>*> > outVregIdxMap(
2101                    vregIndexMap.size());
2102       
2103        size_t j = 0;
2104        for (const auto& entry: vregIndexMap)
2105        {
2106            TestSingleVReg vreg = getTestSingleVReg(entry.first, regVarNamesMap);
2107            outVregIdxMap[j++] = std::make_pair(vreg, &entry.second);
2108        }
2109        mapSort(outVregIdxMap.begin(), outVregIdxMap.end());
2110       
2111        std::vector<size_t>& lvIndexCvtTable = lvIndexCvtTables[r];
2112        std::vector<size_t>& revLvIndexCvtTable = revLvIndexCvtTables[r];
2113        // generate livenessCvt table
2114        for (const auto& entry: outVregIdxMap)
2115            for (size_t v: *entry.second)
2116                if (v != SIZE_MAX)
2117                {
2118                    /*std::cout << "lvidx: " << v << ": " << entry.first.name << ":" <<
2119                            entry.first.index << std::endl;*/
2120                    size_t j = lvIndexCvtTable.size();
2121                    lvIndexCvtTable.push_back(v);
2122                    if (v+1 > revLvIndexCvtTable.size())
2123                        revLvIndexCvtTable.resize(v+1);
2124                    revLvIndexCvtTable[v] = j;
2125                }
2126    }
2127   
2128    const Array<OutLiveness>* resLivenesses = regAlloc.getOutLivenesses();
2129    for (size_t r = 0; r < MAX_REGTYPES_NUM; r++)
2130    {
2131        std::ostringstream rOss;
2132        rOss << "live.regtype#" << r;
2133        rOss.flush();
2134        std::string rtname(rOss.str());
2135       
2136        assertValue("testAsmLivenesses", testCaseName + rtname + ".size",
2137                    testCase.livenesses[r].size(), resLivenesses[r].size());
2138       
2139        for (size_t li = 0; li < resLivenesses[r].size(); li++)
2140        {
2141            std::ostringstream lOss;
2142            lOss << ".liveness#" << li;
2143            lOss.flush();
2144            std::string lvname(rtname + lOss.str());
2145            const OutLiveness& expLv = testCase.livenesses[r][li];
2146            const OutLiveness& resLv = resLivenesses[r][lvIndexCvtTables[r][li]];
2147           
2148            // checking liveness
2149            assertValue("testAsmLivenesses", testCaseName + lvname + ".size",
2150                    expLv.size(), resLv.size());
2151            for (size_t k = 0; k < resLv.size(); k++)
2152            {
2153                std::ostringstream regOss;
2154                regOss << ".reg#" << k;
2155                regOss.flush();
2156                std::string regname(lvname + regOss.str());
2157                assertValue("testAsmLivenesses", testCaseName + regname + ".first",
2158                    expLv[k].first, resLv[k].first);
2159                assertValue("testAsmLivenesses", testCaseName + regname + ".second",
2160                    expLv[k].second, resLv[k].second);
2161            }
2162        }
2163    }
2164   
2165    // checking linearDepMaps
2166    const std::unordered_map<size_t, LinearDep>* resLinearDepMaps =
2167                regAlloc.getLinearDepMaps();
2168    for (size_t r = 0; r < MAX_REGTYPES_NUM; r++)
2169    {
2170        std::ostringstream rOss;
2171        rOss << "lndep.regtype#" << r;
2172        rOss.flush();
2173        std::string rtname(rOss.str());
2174       
2175        assertValue("testAsmLivenesses", testCaseName + rtname + ".size",
2176                    testCase.linearDepMaps[r].size(), resLinearDepMaps[r].size());
2177       
2178        for (size_t di = 0; di < testCase.linearDepMaps[r].size(); di++)
2179        {
2180            std::ostringstream lOss;
2181            lOss << ".lndep#" << di;
2182            lOss.flush();
2183            std::string ldname(rtname + lOss.str());
2184            const auto& expLinearDepEntry = testCase.linearDepMaps[r][di];
2185            auto rlit = resLinearDepMaps[r].find(
2186                            lvIndexCvtTables[r][expLinearDepEntry.first]);
2187           
2188            std::ostringstream vOss;
2189            vOss << expLinearDepEntry.first;
2190            vOss.flush();
2191            assertTrue("testAsmLivenesses", testCaseName + ldname + ".key=" + vOss.str(),
2192                        rlit != resLinearDepMaps[r].end());
2193            const LinearDep2& expLinearDep = expLinearDepEntry.second;
2194            const LinearDep& resLinearDep = rlit->second;
2195           
2196            assertValue("testAsmLivenesses", testCaseName + ldname + ".align",
2197                        cxuint(expLinearDep.align), cxuint(resLinearDep.align));
2198           
2199            Array<size_t> resPrevVidxes(resLinearDep.prevVidxes.size());
2200            // convert to res ssaIdIndices
2201            for (size_t k = 0; k < resLinearDep.prevVidxes.size(); k++)
2202                resPrevVidxes[k] = revLvIndexCvtTables[r][resLinearDep.prevVidxes[k]];
2203           
2204            assertArray("testAsmLivenesses", testCaseName + ldname + ".prevVidxes",
2205                        expLinearDep.prevVidxes, resPrevVidxes);
2206           
2207            Array<size_t> resNextVidxes(resLinearDep.nextVidxes.size());
2208            // convert to res ssaIdIndices
2209            for (size_t k = 0; k < resLinearDep.nextVidxes.size(); k++)
2210                resNextVidxes[k] = revLvIndexCvtTables[r][resLinearDep.nextVidxes[k]];
2211           
2212            assertArray("testAsmLivenesses", testCaseName + ldname + ".nextVidxes",
2213                        expLinearDep.nextVidxes, resNextVidxes);
2214        }
2215    }
2216   
2217    // checking vidxRoutineMap
2218    checkVIdxSetEntries(testCaseName, "vidxRoutineMap", testCase.vidxRoutineMap,
2219                regAlloc.getVIdxRoutineMap(), revLvIndexCvtTables);
2220   
2221    // checking vidxCallMap
2222    checkVIdxSetEntries(testCaseName, "vidxCallMap", testCase.vidxCallMap,
2223                regAlloc.getVIdxCallMap(), revLvIndexCvtTables);
2224}
2225
2226int main(int argc, const char** argv)
2227{
2228    int retVal = 0;
2229    for (size_t i = 0; i < sizeof(createLivenessesCasesTbl)/sizeof(AsmLivenessesCase); i++)
2230        try
2231        { testCreateLivenessesCase(i, createLivenessesCasesTbl[i]); }
2232        catch(const std::exception& ex)
2233        {
2234            std::cerr << ex.what() << std::endl;
2235            retVal = 1;
2236        }
2237    return retVal;
2238}
Note: See TracBrowser for help on using the repository browser.