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

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

CLRadeonExtender: AsmRegAlloc?: Fixed putting vidxes to vidxRoutineMap (may beyond correct ssaIdIdx in loop).
add testcase with routine with loop.

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