1/*
2 * memops - try to combine memory ops.
3 *
4 * Copyright (C) 2004 Linus Torvalds
5 */
6
7#include <string.h>
8#include <stdarg.h>
9#include <stdlib.h>
10#include <stdio.h>
11#include <stddef.h>
12#include <assert.h>
13
14#include "parse.h"
15#include "expression.h"
16#include "linearize.h"
17#include "flow.h"
18
19static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
20	struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
21	int local)
22{
23	struct basic_block *parent;
24
25	FOR_EACH_PTR(bb->parents, parent) {
26		struct instruction *one;
27		struct instruction *br;
28		pseudo_t phi;
29
30		FOR_EACH_PTR_REVERSE(parent->insns, one) {
31			int dominance;
32			if (!one->bb)
33				continue;
34			if (one == insn)
35				goto no_dominance;
36			dominance = dominates(pseudo, insn, one, local);
37			if (dominance < 0) {
38				if (one->opcode == OP_LOAD)
39					continue;
40				return 0;
41			}
42			if (!dominance)
43				continue;
44			goto found_dominator;
45		} END_FOR_EACH_PTR_REVERSE(one);
46no_dominance:
47		if (parent->generation == generation)
48			continue;
49		parent->generation = generation;
50
51		if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
52			return 0;
53		continue;
54
55found_dominator:
56		br = delete_last_instruction(&parent->insns);
57		phi = alloc_phi(parent, one->target, one->type);
58		phi->ident = phi->ident ? : one->target->ident;
59		add_instruction(&parent->insns, br);
60		use_pseudo(insn, phi, add_pseudo(dominators, phi));
61	} END_FOR_EACH_PTR(parent);
62	return 1;
63}
64
65static int address_taken(pseudo_t pseudo)
66{
67	struct pseudo_user *pu;
68	FOR_EACH_PTR(pseudo->users, pu) {
69		struct instruction *insn = pu->insn;
70		if (insn->bb && (insn->opcode != OP_LOAD && insn->opcode != OP_STORE))
71			return 1;
72		if (pu->userp != &insn->src)
73			return 1;
74	} END_FOR_EACH_PTR(pu);
75	return 0;
76}
77
78static int local_pseudo(pseudo_t pseudo)
79{
80	return pseudo->type == PSEUDO_SYM
81		&& !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
82		&& !address_taken(pseudo);
83}
84
85static void simplify_loads(struct basic_block *bb)
86{
87	struct instruction *insn;
88
89	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
90		if (!insn->bb)
91			continue;
92		if (insn->opcode == OP_LOAD) {
93			struct instruction *dom;
94			pseudo_t pseudo = insn->src;
95			int local = local_pseudo(pseudo);
96			struct pseudo_list *dominators;
97			unsigned long generation;
98
99			/* Check for illegal offsets.. */
100			check_access(insn);
101
102			if (insn->is_volatile)
103				continue;
104
105			RECURSE_PTR_REVERSE(insn, dom) {
106				int dominance;
107				if (!dom->bb)
108					continue;
109				dominance = dominates(pseudo, insn, dom, local);
110				if (dominance) {
111					/* possible partial dominance? */
112					if (dominance < 0)  {
113						if (dom->opcode == OP_LOAD)
114							continue;
115						goto next_load;
116					}
117					/* Yeehaa! Found one! */
118					convert_load_instruction(insn, dom->target);
119					goto next_load;
120				}
121			} END_FOR_EACH_PTR_REVERSE(dom);
122
123			/* OK, go find the parents */
124			generation = ++bb_generation;
125			bb->generation = generation;
126			dominators = NULL;
127			if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) {
128				/* This happens with initial assignments to structures etc.. */
129				if (!dominators) {
130					if (local) {
131						assert(pseudo->type != PSEUDO_ARG);
132						convert_load_instruction(insn, value_pseudo(0));
133					}
134					goto next_load;
135				}
136				rewrite_load_instruction(insn, dominators);
137			} else {	// cleanup pending phi-sources
138				pseudo_t phi;
139				FOR_EACH_PTR(dominators, phi) {
140					kill_instruction(phi->def);
141				} END_FOR_EACH_PTR(phi);
142			}
143		}
144next_load:
145		/* Do the next one */;
146	} END_FOR_EACH_PTR_REVERSE(insn);
147}
148
149static void kill_dominated_stores(struct basic_block *bb)
150{
151	struct instruction *insn;
152
153	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
154		if (!insn->bb)
155			continue;
156		if (insn->opcode == OP_STORE) {
157			struct instruction *dom;
158			pseudo_t pseudo = insn->src;
159			int local;
160
161			if (!insn->type)
162				continue;
163			if (insn->is_volatile)
164				continue;
165
166			local = local_pseudo(pseudo);
167			RECURSE_PTR_REVERSE(insn, dom) {
168				int dominance;
169				if (!dom->bb)
170					continue;
171				dominance = dominates(pseudo, insn, dom, local);
172				if (dominance) {
173					/* possible partial dominance? */
174					if (dominance < 0)
175						goto next_store;
176					if (dom->opcode == OP_LOAD)
177						goto next_store;
178					/* Yeehaa! Found one! */
179					kill_instruction_force(dom);
180				}
181			} END_FOR_EACH_PTR_REVERSE(dom);
182
183			/* OK, we should check the parents now */
184		}
185next_store:
186		/* Do the next one */;
187	} END_FOR_EACH_PTR_REVERSE(insn);
188}
189
190void simplify_memops(struct entrypoint *ep)
191{
192	struct basic_block *bb;
193	pseudo_t pseudo;
194
195	FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
196		simplify_loads(bb);
197	} END_FOR_EACH_PTR_REVERSE(bb);
198
199	FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
200		kill_dominated_stores(bb);
201	} END_FOR_EACH_PTR_REVERSE(bb);
202
203	FOR_EACH_PTR(ep->accesses, pseudo) {
204		struct symbol *var = pseudo->sym;
205		unsigned long mod;
206		if (!var)
207			continue;
208		mod = var->ctype.modifiers;
209		if (mod & (MOD_VOLATILE | MOD_NONLOCAL | MOD_STATIC))
210			continue;
211		kill_dead_stores(ep, pseudo, local_pseudo(pseudo));
212	} END_FOR_EACH_PTR(pseudo);
213}
214