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) */
31 /* Determine if a variable is live in the successors of a block */
33 is_live_after_successors(compiler_context
*ctx
, midgard_block
*bl
, int src
)
35 for (unsigned i
= 0; i
< bl
->nr_successors
; ++i
) {
36 midgard_block
*succ
= bl
->successors
[i
];
38 /* If we already visited, the value we're seeking
39 * isn't down this path (or we would have short
42 if (succ
->visited
) continue;
44 /* Otherwise (it's visited *now*), check the block */
48 /* Within this block, check if it's overwritten first */
49 unsigned overwritten_mask
= 0;
51 mir_foreach_instr_in_block(succ
, ins
) {
52 /* Did we read any components that we haven't overwritten yet? */
53 if (mir_mask_of_read_components(ins
, src
) & ~overwritten_mask
)
56 /* If written-before-use, we're gone */
58 if (ins
->ssa_args
.dest
== src
)
59 overwritten_mask
|= ins
->mask
;
62 /* ...and also, check *its* successors */
63 if (is_live_after_successors(ctx
, succ
, src
))
68 /* Welp. We're really not live. */
74 mir_is_live_after(compiler_context
*ctx
, midgard_block
*block
, midgard_instruction
*start
, int src
)
76 /* Check the rest of the block for liveness */
78 mir_foreach_instr_in_block_from(block
, ins
, mir_next_op(start
)) {
79 if (mir_has_arg(ins
, src
))
83 /* Check the rest of the blocks for liveness recursively */
85 bool succ
= is_live_after_successors(ctx
, block
, src
);
87 mir_foreach_block(ctx
, block
) {
88 block
->visited
= false;
94 /* Just a quick check -- is it written more than once? (I.e. are we definitely
98 mir_has_multiple_writes(compiler_context
*ctx
, int dest
)
100 unsigned write_count
= 0;
102 mir_foreach_instr_global(ctx
, ins
) {
103 if (ins
->ssa_args
.dest
== dest
)
107 return write_count
> 1;