pan/midgard: Switch sources to an array for trinary sources
[mesa.git] / src / panfrost / midgard / midgard_liveness.c
1 /*
2 * Copyright (C) 2018-2019 Alyssa Rosenzweig <alyssa@rosenzweig.io>
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21 * SOFTWARE.
22 */
23
24 /* mir_is_live_after performs liveness analysis on the MIR, used primarily
25 * as part of register allocation. TODO: Algorithmic improvements for
26 * compiler performance (this is the worst algorithm possible -- see
27 * backlog with Connor on IRC) */
28
29 #include "compiler.h"
30
31 /* Determine if a variable is live in the successors of a block */
32 static bool
33 is_live_after_successors(compiler_context *ctx, midgard_block *bl, int src)
34 {
35 for (unsigned i = 0; i < bl->nr_successors; ++i) {
36 midgard_block *succ = bl->successors[i];
37
38 /* If we already visited, the value we're seeking
39 * isn't down this path (or we would have short
40 * circuited */
41
42 if (succ->visited) continue;
43
44 /* Otherwise (it's visited *now*), check the block */
45
46 succ->visited = true;
47
48 /* Within this block, check if it's overwritten first */
49 bool block_done = false;
50
51 mir_foreach_instr_in_block(succ, ins) {
52 if (mir_has_arg(ins, src))
53 return true;
54
55 /* If written-before-use, we're gone */
56
57 if (ins->ssa_args.dest == src && ins->mask == 0xF) {
58 block_done = true;
59 break;
60 }
61 }
62
63 if (block_done)
64 continue;
65
66 /* ...and also, check *its* successors */
67 if (is_live_after_successors(ctx, succ, src))
68 return true;
69
70 }
71
72 /* Welp. We're really not live. */
73
74 return false;
75 }
76
77 bool
78 mir_is_live_after(compiler_context *ctx, midgard_block *block, midgard_instruction *start, int src)
79 {
80 /* Check the rest of the block for liveness */
81
82 mir_foreach_instr_in_block_from(block, ins, mir_next_op(start)) {
83 if (mir_has_arg(ins, src))
84 return true;
85 }
86
87 /* Check the rest of the blocks for liveness recursively */
88
89 bool succ = is_live_after_successors(ctx, block, src);
90
91 mir_foreach_block(ctx, block) {
92 block->visited = false;
93 }
94
95 return succ;
96 }
97
98 /* Just a quick check -- is it written more than once? (I.e. are we definitely
99 * not SSA?) */
100
101 bool
102 mir_has_multiple_writes(compiler_context *ctx, int dest)
103 {
104 unsigned write_count = 0;
105
106 mir_foreach_instr_global(ctx, ins) {
107 if (ins->ssa_args.dest == dest)
108 write_count++;
109 }
110
111 return write_count > 1;
112 }