1// SPDX-License-Identifier: MIT
2//
3// Copyright (C) 2004 Linus Torvalds
4// Copyright (C) 2004 Christopher Li
5
6///
7// Optimization main loop
8// ----------------------
9
10#include <assert.h>
11#include "optimize.h"
12#include "flowgraph.h"
13#include "linearize.h"
14#include "liveness.h"
15#include "simplify.h"
16#include "flow.h"
17#include "cse.h"
18#include "ir.h"
19#include "ssa.h"
20
21int repeat_phase;
22
23static void clear_symbol_pseudos(struct entrypoint *ep)
24{
25	pseudo_t pseudo;
26
27	FOR_EACH_PTR(ep->accesses, pseudo) {
28		pseudo->sym->pseudo = NULL;
29	} END_FOR_EACH_PTR(pseudo);
30}
31
32
33static void clean_up_insns(struct entrypoint *ep)
34{
35	struct basic_block *bb;
36
37	FOR_EACH_PTR(ep->bbs, bb) {
38		struct instruction *insn;
39		FOR_EACH_PTR(bb->insns, insn) {
40			if (!insn->bb)
41				continue;
42			repeat_phase |= simplify_instruction(insn);
43			if (!insn->bb)
44				continue;
45			assert(insn->bb == bb);
46			cse_collect(insn);
47		} END_FOR_EACH_PTR(insn);
48	} END_FOR_EACH_PTR(bb);
49}
50
51static void cleanup_cfg(struct entrypoint *ep)
52{
53	kill_unreachable_bbs(ep);
54	domtree_build(ep);
55}
56
57///
58// optimization main loop
59void optimize(struct entrypoint *ep)
60{
61	if (fdump_ir & PASS_LINEARIZE)
62		show_entry(ep);
63
64	/*
65	 * Do trivial flow simplification - branches to
66	 * branches, kill dead basicblocks etc
67	 */
68	kill_unreachable_bbs(ep);
69	ir_validate(ep);
70
71	cfg_postorder(ep);
72	if (simplify_cfg_early(ep))
73		kill_unreachable_bbs(ep);
74	ir_validate(ep);
75
76	domtree_build(ep);
77
78	/*
79	 * Turn symbols into pseudos
80	 */
81	if (fpasses & PASS_MEM2REG)
82		ssa_convert(ep);
83	ir_validate(ep);
84	if (fdump_ir & PASS_MEM2REG)
85		show_entry(ep);
86
87	if (!(fpasses & PASS_OPTIM))
88		return;
89repeat:
90	/*
91	 * Remove trivial instructions, and try to CSE
92	 * the rest.
93	 */
94	do {
95		simplify_memops(ep);
96		do {
97			repeat_phase = 0;
98			clean_up_insns(ep);
99			if (repeat_phase & REPEAT_CFG_CLEANUP)
100				kill_unreachable_bbs(ep);
101
102			cse_eliminate(ep);
103			simplify_memops(ep);
104		} while (repeat_phase);
105		pack_basic_blocks(ep);
106		if (repeat_phase & REPEAT_CFG_CLEANUP)
107			cleanup_cfg(ep);
108	} while (repeat_phase);
109
110	vrfy_flow(ep);
111
112	/* Cleanup */
113	clear_symbol_pseudos(ep);
114
115	/* And track pseudo register usage */
116	track_pseudo_liveness(ep);
117
118	/*
119	 * Some flow optimizations can only effectively
120	 * be done when we've done liveness analysis. But
121	 * if they trigger, we need to start all over
122	 * again
123	 */
124	if (simplify_flow(ep)) {
125		clear_liveness(ep);
126		if (repeat_phase & REPEAT_CFG_CLEANUP)
127			cleanup_cfg(ep);
128		goto repeat;
129	}
130
131	/* Finally, add deathnotes to pseudos now that we have them */
132	if (dbg_dead)
133		track_pseudo_death(ep);
134}
135