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
rewrite_load_instruction(struct instruction * insn,struct pseudo_list * dominators)20 static 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
47 complex_phi:
48 kill_use(&insn->src);
49 insn->opcode = OP_PHI;
50 insn->phi_list = dominators;
51
52 end:
53 repeat_phase |= REPEAT_CSE;
54 }
55
find_dominating_parents(struct instruction * insn,struct basic_block * bb,struct pseudo_list ** dominators,int local)56 static 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);
83 no_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
92 found_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
address_taken(pseudo_t pseudo)103 static 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
local_pseudo(pseudo_t pseudo)116 static 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
compatible_loads(struct instruction * a,struct instruction * b)123 static 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
simplify_loads(struct basic_block * bb)132 static 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 }
195 next_load:
196 /* Do the next one */;
197 } END_FOR_EACH_PTR_REVERSE(insn);
198 }
199
try_to_kill_store(struct instruction * insn,struct instruction * dom,int local)200 static 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
kill_dominated_stores(struct basic_block * bb)224 static 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);
263 next_parent:
264 ;
265 } END_FOR_EACH_PTR(par);
266 }
267 next_store:
268 /* Do the next one */;
269 } END_FOR_EACH_PTR_REVERSE(insn);
270 }
271
simplify_memops(struct entrypoint * ep)272 void 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