2 * Copyright (C) 2018-2019 Alyssa Rosenzweig <alyssa@rosenzweig.io>
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:
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
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
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) */
32 midgard_is_live_in_instr(midgard_instruction
*ins
, int src
)
34 if (ins
->compact_branch
)
37 if (ins
->ssa_args
.src0
== src
)
40 if (!ins
->ssa_args
.inline_constant
&& ins
->ssa_args
.src1
== src
)
46 /* Determine if a variable is live in the successors of a block */
48 is_live_after_successors(compiler_context
*ctx
, midgard_block
*bl
, int src
)
50 for (unsigned i
= 0; i
< bl
->nr_successors
; ++i
) {
51 midgard_block
*succ
= bl
->successors
[i
];
53 /* If we already visited, the value we're seeking
54 * isn't down this path (or we would have short
57 if (succ
->visited
) continue;
59 /* Otherwise (it's visited *now*), check the block */
63 /* Within this block, check if it's overwritten first */
64 bool block_done
= false;
66 mir_foreach_instr_in_block(succ
, ins
) {
67 if (midgard_is_live_in_instr(ins
, src
))
70 /* If written-before-use, we're gone */
72 if (ins
->ssa_args
.dest
== src
&& ins
->type
== TAG_LOAD_STORE_4
&& ins
->load_store
.op
== midgard_op_ld_int4
&& ins
->load_store
.unknown
== 0x1EEA) {
81 /* ...and also, check *its* successors */
82 if (is_live_after_successors(ctx
, succ
, src
))
87 /* Welp. We're really not live. */
93 mir_is_live_after(compiler_context
*ctx
, midgard_block
*block
, midgard_instruction
*start
, int src
)
95 /* Check the rest of the block for liveness */
97 mir_foreach_instr_in_block_from(block
, ins
, mir_next_op(start
)) {
98 if (midgard_is_live_in_instr(ins
, src
))
102 /* Check the rest of the blocks for liveness recursively */
104 bool succ
= is_live_after_successors(ctx
, block
, src
);
106 mir_foreach_block(ctx
, block
) {
107 block
->visited
= false;
113 /* Just a quick check -- is it written more than once? (I.e. are we definitely
117 mir_has_multiple_writes(compiler_context
*ctx
, int dest
)
119 unsigned write_count
= 0;
121 mir_foreach_instr_global(ctx
, ins
) {
122 if (ins
->ssa_args
.dest
== dest
)
126 return write_count
> 1;