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
->ssa_args
.src0
== src
)
37 if (ins
->ssa_args
.src1
== src
)
43 /* Determine if a variable is live in the successors of a block */
45 is_live_after_successors(compiler_context
*ctx
, midgard_block
*bl
, int src
)
47 for (unsigned i
= 0; i
< bl
->nr_successors
; ++i
) {
48 midgard_block
*succ
= bl
->successors
[i
];
50 /* If we already visited, the value we're seeking
51 * isn't down this path (or we would have short
54 if (succ
->visited
) continue;
56 /* Otherwise (it's visited *now*), check the block */
60 /* Within this block, check if it's overwritten first */
61 bool block_done
= false;
63 mir_foreach_instr_in_block(succ
, ins
) {
64 if (midgard_is_live_in_instr(ins
, src
))
67 /* If written-before-use, we're gone */
69 if (ins
->ssa_args
.dest
== src
&& ins
->mask
== 0xF) {
78 /* ...and also, check *its* successors */
79 if (is_live_after_successors(ctx
, succ
, src
))
84 /* Welp. We're really not live. */
90 mir_is_live_after(compiler_context
*ctx
, midgard_block
*block
, midgard_instruction
*start
, int src
)
92 /* Check the rest of the block for liveness */
94 mir_foreach_instr_in_block_from(block
, ins
, mir_next_op(start
)) {
95 if (midgard_is_live_in_instr(ins
, src
))
99 /* Check the rest of the blocks for liveness recursively */
101 bool succ
= is_live_after_successors(ctx
, block
, src
);
103 mir_foreach_block(ctx
, block
) {
104 block
->visited
= false;
110 /* Just a quick check -- is it written more than once? (I.e. are we definitely
114 mir_has_multiple_writes(compiler_context
*ctx
, int dest
)
116 unsigned write_count
= 0;
118 mir_foreach_instr_global(ctx
, ins
) {
119 if (ins
->ssa_args
.dest
== dest
)
123 return write_count
> 1;