db: use the load_strings_from_file() helper function
[smatch.git] / memops.c
blob0a1106b0e4644c1378339f67f1d7fba7dbcc2bb1
1 /*
2 * memops - try to combine memory ops.
4 * Copyright (C) 2004 Linus Torvalds
5 */
7 #include <string.h>
8 #include <stdarg.h>
9 #include <stdlib.h>
10 #include <stdio.h>
11 #include <stddef.h>
12 #include <assert.h>
14 #include "parse.h"
15 #include "expression.h"
16 #include "linearize.h"
17 #include "simplify.h"
18 #include "flow.h"
21 * We should probably sort the phi list just to make it easier to compare
22 * later for equality.
24 static void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
26 pseudo_t new, phi;
29 * Check for somewhat common case of duplicate
30 * phi nodes.
32 new = first_pseudo(dominators)->def->phi_src;
33 FOR_EACH_PTR(dominators, phi) {
34 if (new != phi->def->phi_src)
35 goto complex_phi;
36 new->ident = new->ident ? : phi->ident;
37 } END_FOR_EACH_PTR(phi);
40 * All the same pseudo - mark the phi-nodes unused
41 * and convert the load into a LNOP and replace the
42 * pseudo.
44 replace_with_pseudo(insn, new);
45 FOR_EACH_PTR(dominators, phi) {
46 kill_instruction(phi->def);
47 } END_FOR_EACH_PTR(phi);
48 goto end;
50 complex_phi:
51 /* We leave symbol pseudos with a bogus usage list here */
52 if (insn->src->type != PSEUDO_SYM)
53 kill_use(&insn->src);
54 insn->opcode = OP_PHI;
55 insn->phi_list = dominators;
57 end:
58 repeat_phase |= REPEAT_CSE;
61 static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
62 struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
63 int local)
65 struct basic_block *parent;
67 FOR_EACH_PTR(bb->parents, parent) {
68 struct instruction *one;
69 struct instruction *br;
70 pseudo_t phi;
72 FOR_EACH_PTR_REVERSE(parent->insns, one) {
73 int dominance;
74 if (!one->bb)
75 continue;
76 if (one == insn)
77 goto no_dominance;
78 dominance = dominates(pseudo, insn, one, local);
79 if (dominance < 0) {
80 if (one->opcode == OP_LOAD)
81 continue;
82 return 0;
84 if (!dominance)
85 continue;
86 goto found_dominator;
87 } END_FOR_EACH_PTR_REVERSE(one);
88 no_dominance:
89 if (parent->generation == generation)
90 continue;
91 parent->generation = generation;
93 if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
94 return 0;
95 continue;
97 found_dominator:
98 br = delete_last_instruction(&parent->insns);
99 phi = alloc_phi(parent, one->target, one->type);
100 phi->ident = phi->ident ? : one->target->ident;
101 add_instruction(&parent->insns, br);
102 use_pseudo(insn, phi, add_pseudo(dominators, phi));
103 } END_FOR_EACH_PTR(parent);
104 return 1;
107 static int address_taken(pseudo_t pseudo)
109 struct pseudo_user *pu;
110 FOR_EACH_PTR(pseudo->users, pu) {
111 struct instruction *insn = pu->insn;
112 if (insn->bb && (insn->opcode != OP_LOAD && insn->opcode != OP_STORE))
113 return 1;
114 if (pu->userp != &insn->src)
115 return 1;
116 } END_FOR_EACH_PTR(pu);
117 return 0;
120 static int local_pseudo(pseudo_t pseudo)
122 return pseudo->type == PSEUDO_SYM
123 && !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
124 && !address_taken(pseudo);
127 static bool compatible_loads(struct instruction *a, struct instruction *b)
129 if (is_integral_type(a->type) && is_float_type(b->type))
130 return false;
131 if (is_float_type(a->type) && is_integral_type(b->type))
132 return false;
133 return true;
136 static void simplify_loads(struct basic_block *bb)
138 struct instruction *insn;
140 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
141 if (!insn->bb)
142 continue;
143 if (insn->opcode == OP_LOAD) {
144 struct instruction *dom;
145 pseudo_t pseudo = insn->src;
146 int local = local_pseudo(pseudo);
147 struct pseudo_list *dominators;
148 unsigned long generation;
150 if (insn->is_volatile)
151 continue;
153 if (!has_users(insn->target)) {
154 kill_instruction(insn);
155 continue;
158 RECURSE_PTR_REVERSE(insn, dom) {
159 int dominance;
160 if (!dom->bb)
161 continue;
162 dominance = dominates(pseudo, insn, dom, local);
163 if (dominance) {
164 /* possible partial dominance? */
165 if (dominance < 0) {
166 if (dom->opcode == OP_LOAD)
167 continue;
168 goto next_load;
170 if (!compatible_loads(insn, dom))
171 goto next_load;
172 /* Yeehaa! Found one! */
173 replace_with_pseudo(insn, dom->target);
174 goto next_load;
176 } END_FOR_EACH_PTR_REVERSE(dom);
178 /* OK, go find the parents */
179 generation = ++bb_generation;
180 bb->generation = generation;
181 dominators = NULL;
182 if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) {
183 /* This happens with initial assignments to structures etc.. */
184 if (!dominators) {
185 if (local) {
186 assert(pseudo->type != PSEUDO_ARG);
187 replace_with_pseudo(insn, value_pseudo(0));
189 goto next_load;
191 rewrite_load_instruction(insn, dominators);
192 } else { // cleanup pending phi-sources
193 int repeat = repeat_phase;
194 pseudo_t phi;
195 FOR_EACH_PTR(dominators, phi) {
196 kill_instruction(phi->def);
197 } END_FOR_EACH_PTR(phi);
198 repeat_phase = repeat;
201 next_load:
202 /* Do the next one */;
203 } END_FOR_EACH_PTR_REVERSE(insn);
206 static void kill_dominated_stores(struct basic_block *bb)
208 struct instruction *insn;
210 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
211 if (!insn->bb)
212 continue;
213 if (insn->opcode == OP_STORE) {
214 struct instruction *dom;
215 pseudo_t pseudo = insn->src;
216 int local;
218 if (!insn->type)
219 continue;
220 if (insn->is_volatile)
221 continue;
223 local = local_pseudo(pseudo);
224 RECURSE_PTR_REVERSE(insn, dom) {
225 int dominance;
226 if (!dom->bb)
227 continue;
228 dominance = dominates(pseudo, insn, dom, local);
229 if (dominance) {
230 /* possible partial dominance? */
231 if (dominance < 0)
232 goto next_store;
233 if (dom->opcode == OP_LOAD)
234 goto next_store;
235 /* Yeehaa! Found one! */
236 kill_instruction_force(dom);
238 } END_FOR_EACH_PTR_REVERSE(dom);
240 /* OK, we should check the parents now */
242 next_store:
243 /* Do the next one */;
244 } END_FOR_EACH_PTR_REVERSE(insn);
247 void simplify_memops(struct entrypoint *ep)
249 struct basic_block *bb;
250 pseudo_t pseudo;
252 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
253 simplify_loads(bb);
254 } END_FOR_EACH_PTR_REVERSE(bb);
256 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
257 kill_dominated_stores(bb);
258 } END_FOR_EACH_PTR_REVERSE(bb);
260 FOR_EACH_PTR(ep->accesses, pseudo) {
261 struct symbol *var = pseudo->sym;
262 unsigned long mod;
263 if (!var)
264 continue;
265 mod = var->ctype.modifiers;
266 if (mod & (MOD_VOLATILE | MOD_NONLOCAL | MOD_STATIC))
267 continue;
268 kill_dead_stores(ep, pseudo, local_pseudo(pseudo));
269 } END_FOR_EACH_PTR(pseudo);