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 "simplify.h"
18#include "flow.h"
19
20static void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
21{
22	pseudo_t new = NULL;
23	pseudo_t phi;
24
25	/*
26	 * Check for somewhat common case of duplicate
27	 * phi nodes.
28	 */
29	FOR_EACH_PTR(dominators, phi) {
30		if (!new)
31			new = phi->def->phi_src;
32		else if (new != phi->def->phi_src)
33			goto complex_phi;
34	} END_FOR_EACH_PTR(phi);
35
36	/*
37	 * All the same pseudo - mark the phi-nodes unused
38	 * and convert the load into a LNOP and replace the
39	 * pseudo.
40	 */
41	replace_with_pseudo(insn, new);
42	FOR_EACH_PTR(dominators, phi) {
43		kill_instruction(phi->def);
44	} END_FOR_EACH_PTR(phi);
45	goto end;
46
47complex_phi:
48	kill_use(&insn->src);
49	insn->opcode = OP_PHI;
50	insn->phi_list = dominators;
51
52end:
53	repeat_phase |= REPEAT_CSE;
54}
55
56static int find_dominating_parents(struct instruction *insn,
57	struct basic_block *bb, struct pseudo_list **dominators,
58	int local)
59{
60	struct basic_block *parent;
61
62	FOR_EACH_PTR(bb->parents, parent) {
63		struct instruction *phisrc;
64		struct instruction *one;
65		pseudo_t phi;
66
67		FOR_EACH_PTR_REVERSE(parent->insns, one) {
68			int dominance;
69			if (!one->bb)
70				continue;
71			if (one == insn)
72				goto no_dominance;
73			dominance = dominates(insn, one, local);
74			if (dominance < 0) {
75				if (one->opcode == OP_LOAD)
76					continue;
77				return 0;
78			}
79			if (!dominance)
80				continue;
81			goto found_dominator;
82		} END_FOR_EACH_PTR_REVERSE(one);
83no_dominance:
84		if (parent->generation == bb->generation)
85			continue;
86		parent->generation = bb->generation;
87
88		if (!find_dominating_parents(insn, parent, dominators, local))
89			return 0;
90		continue;
91
92found_dominator:
93		phisrc = alloc_phisrc(one->target, one->type);
94		phisrc->phi_node = insn;
95		insert_last_instruction(parent, phisrc);
96		phi = phisrc->target;
97		phi->ident = phi->ident ? : one->target->ident;
98		use_pseudo(insn, phi, add_pseudo(dominators, phi));
99	} END_FOR_EACH_PTR(parent);
100	return 1;
101}
102
103static int address_taken(pseudo_t pseudo)
104{
105	struct pseudo_user *pu;
106	FOR_EACH_PTR(pseudo->users, pu) {
107		struct instruction *insn = pu->insn;
108		if (insn->bb && (insn->opcode != OP_LOAD && insn->opcode != OP_STORE))
109			return 1;
110		if (pu->userp != &insn->src)
111			return 1;
112	} END_FOR_EACH_PTR(pu);
113	return 0;
114}
115
116static int local_pseudo(pseudo_t pseudo)
117{
118	return pseudo->type == PSEUDO_SYM
119		&& !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
120		&& !address_taken(pseudo);
121}
122
123static bool compatible_loads(struct instruction *a, struct instruction *b)
124{
125	if (is_integral_type(a->type) && is_float_type(b->type))
126		return false;
127	if (is_float_type(a->type) && is_integral_type(b->type))
128		return false;
129	return true;
130}
131
132static void simplify_loads(struct basic_block *bb)
133{
134	struct instruction *insn;
135
136	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
137		if (!insn->bb)
138			continue;
139		if (insn->opcode == OP_LOAD) {
140			struct instruction *dom;
141			pseudo_t pseudo = insn->src;
142			int local = local_pseudo(pseudo);
143			struct pseudo_list *dominators;
144
145			if (insn->is_volatile)
146				continue;
147
148			if (!has_users(insn->target)) {
149				kill_instruction(insn);
150				continue;
151			}
152
153			RECURSE_PTR_REVERSE(insn, dom) {
154				int dominance;
155				if (!dom->bb)
156					continue;
157				dominance = dominates(insn, dom, local);
158				if (dominance) {
159					/* possible partial dominance? */
160					if (dominance < 0)  {
161						if (dom->opcode == OP_LOAD)
162							continue;
163						goto next_load;
164					}
165					if (!compatible_loads(insn, dom))
166						goto next_load;
167					/* Yeehaa! Found one! */
168					replace_with_pseudo(insn, dom->target);
169					goto next_load;
170				}
171			} END_FOR_EACH_PTR_REVERSE(dom);
172
173			/* OK, go find the parents */
174			bb->generation = ++bb_generation;
175			dominators = NULL;
176			if (find_dominating_parents(insn, bb, &dominators, local)) {
177				/* This happens with initial assignments to structures etc.. */
178				if (!dominators) {
179					if (local) {
180						assert(pseudo->type != PSEUDO_ARG);
181						replace_with_pseudo(insn, value_pseudo(0));
182					}
183					goto next_load;
184				}
185				rewrite_load_instruction(insn, dominators);
186			} else {	// cleanup pending phi-sources
187				int repeat = repeat_phase;
188				pseudo_t phi;
189				FOR_EACH_PTR(dominators, phi) {
190					kill_instruction(phi->def);
191				} END_FOR_EACH_PTR(phi);
192				repeat_phase = repeat;
193			}
194		}
195next_load:
196		/* Do the next one */;
197	} END_FOR_EACH_PTR_REVERSE(insn);
198}
199
200static bool try_to_kill_store(struct instruction *insn,
201			     struct instruction *dom, int local)
202{
203	int dominance = dominates(insn, dom, local);
204
205	if (dominance) {
206		/* possible partial dominance? */
207		if (dominance < 0)
208			return false;
209		if (insn->target == dom->target && insn->bb == dom->bb) {
210			// found a memop which makes the store redundant
211			kill_instruction_force(insn);
212			return false;
213		}
214		if (dom->opcode == OP_LOAD)
215			return false;
216		if (dom->is_volatile)
217			return false;
218		/* Yeehaa! Found one! */
219		kill_instruction_force(dom);
220	}
221	return true;
222}
223
224static void kill_dominated_stores(struct basic_block *bb)
225{
226	struct instruction *insn;
227
228	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
229		if (!insn->bb)
230			continue;
231		if (insn->opcode == OP_STORE) {
232			struct basic_block *par;
233			struct instruction *dom;
234			pseudo_t pseudo = insn->src;
235			int local;
236
237			if (!insn->type)
238				continue;
239			if (insn->is_volatile)
240				continue;
241
242			local = local_pseudo(pseudo);
243			RECURSE_PTR_REVERSE(insn, dom) {
244				if (!dom->bb)
245					continue;
246				if (!try_to_kill_store(insn, dom, local))
247					goto next_store;
248			} END_FOR_EACH_PTR_REVERSE(dom);
249
250			/* OK, we should check the parents now */
251			FOR_EACH_PTR(bb->parents, par) {
252
253				if (bb_list_size(par->children) != 1)
254					goto next_parent;
255				FOR_EACH_PTR(par->insns, dom) {
256					if (!dom->bb)
257						continue;
258					if (dom == insn)
259						goto next_parent;
260					if (!try_to_kill_store(insn, dom, local))
261						goto next_parent;
262				} END_FOR_EACH_PTR(dom);
263next_parent:
264				;
265			} END_FOR_EACH_PTR(par);
266		}
267next_store:
268		/* Do the next one */;
269	} END_FOR_EACH_PTR_REVERSE(insn);
270}
271
272void simplify_memops(struct entrypoint *ep)
273{
274	struct basic_block *bb;
275	pseudo_t pseudo;
276
277	FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
278		simplify_loads(bb);
279	} END_FOR_EACH_PTR_REVERSE(bb);
280
281	FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
282		kill_dominated_stores(bb);
283	} END_FOR_EACH_PTR_REVERSE(bb);
284
285	FOR_EACH_PTR(ep->accesses, pseudo) {
286		struct symbol *var = pseudo->sym;
287		unsigned long mod;
288		if (!var)
289			continue;
290		mod = var->ctype.modifiers;
291		if (mod & (MOD_VOLATILE | MOD_NONLOCAL | MOD_STATIC))
292			continue;
293		kill_dead_stores(ep, pseudo, local_pseudo(pseudo));
294	} END_FOR_EACH_PTR(pseudo);
295}
296