[PATCH] More address space checking
[smatch.git] / memops.c
blob8fd777d7cf7b0df5b967a24f6f58aa9daeab7e77
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 "flow.h"
19 static 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, int loads)
23 struct basic_block *parent;
25 if (bb_list_size(bb->parents) > 1)
26 loads = 0;
27 FOR_EACH_PTR(bb->parents, parent) {
28 struct instruction *one;
29 struct instruction *br;
30 pseudo_t phi;
32 FOR_EACH_PTR_REVERSE(parent->insns, one) {
33 int dominance;
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;
42 if (!dominance)
43 continue;
44 if (one->opcode == OP_LOAD && !loads)
45 continue;
46 goto found_dominator;
47 } END_FOR_EACH_PTR_REVERSE(one);
48 no_dominance:
49 if (parent->generation == generation)
50 continue;
51 parent->generation = generation;
53 if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local, loads))
54 return 0;
55 continue;
57 found_dominator:
58 br = delete_last_instruction(&parent->insns);
59 phi = alloc_phi(parent, one->target, one->size);
60 phi->ident = phi->ident ? : one->target->ident;
61 add_instruction(&parent->insns, br);
62 use_pseudo(phi, add_pseudo(dominators, phi));
63 } END_FOR_EACH_PTR(parent);
64 return 1;
68 * FIXME! This is wrong. Since we now distribute out the OP_SYMADDR,
69 * we can no longer really use "container()" to get from a user to
70 * the instruction that uses it.
72 * This happens to work, simply because the likelyhood of the
73 * (possibly non-instruction) containing the right bitpattern
74 * in the right place is pretty low. But this is still wrong.
76 * We should make symbol-pseudos count non-load/store usage,
77 * or something.
79 static int address_taken(pseudo_t pseudo)
81 pseudo_t *usep;
82 FOR_EACH_PTR(pseudo->users, usep) {
83 struct instruction *insn = container(usep, struct instruction, src);
84 if (insn->bb && (insn->opcode != OP_LOAD || insn->opcode != OP_STORE))
85 return 1;
86 } END_FOR_EACH_PTR(usep);
87 return 0;
90 static int local_pseudo(pseudo_t pseudo)
92 return pseudo->type == PSEUDO_SYM
93 && !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
94 && !address_taken(pseudo);
97 static void simplify_loads(struct basic_block *bb)
99 struct instruction *insn;
101 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
102 if (!insn->bb)
103 continue;
104 if (insn->opcode == OP_LOAD) {
105 struct instruction *dom;
106 pseudo_t pseudo = insn->src;
107 int local = local_pseudo(pseudo);
108 struct pseudo_list *dominators;
109 unsigned long generation;
111 /* Check for illegal offsets.. */
112 check_access(insn);
114 RECURSE_PTR_REVERSE(insn, dom) {
115 int dominance;
116 if (!dom->bb)
117 continue;
118 dominance = dominates(pseudo, insn, dom, local);
119 if (dominance) {
120 /* possible partial dominance? */
121 if (dominance < 0) {
122 if (dom->opcode == OP_LOAD)
123 continue;
124 goto next_load;
126 /* Yeehaa! Found one! */
127 convert_load_instruction(insn, dom->target);
128 goto next_load;
130 } END_FOR_EACH_PTR_REVERSE(dom);
132 /* Ok, go find the parents */
133 generation = ++bb_generation;
134 bb->generation = generation;
135 dominators = NULL;
136 if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local, 1)) {
137 /* This happens with initial assignments to structures etc.. */
138 if (!dominators) {
139 if (local) {
140 assert(pseudo->type != PSEUDO_ARG);
141 convert_load_instruction(insn, value_pseudo(0));
143 goto next_load;
145 rewrite_load_instruction(insn, dominators);
148 next_load:
149 /* Do the next one */;
150 } END_FOR_EACH_PTR_REVERSE(insn);
153 static void kill_store(struct instruction *insn)
155 if (insn) {
156 insn->bb = NULL;
157 insn->opcode = OP_SNOP;
158 kill_use(&insn->target);
162 static void kill_dominated_stores(struct basic_block *bb)
164 struct instruction *insn;
166 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
167 if (!insn->bb)
168 continue;
169 if (insn->opcode == OP_STORE) {
170 struct instruction *dom;
171 pseudo_t pseudo = insn->src;
172 int local = local_pseudo(pseudo);
174 RECURSE_PTR_REVERSE(insn, dom) {
175 int dominance;
176 if (!dom->bb)
177 continue;
178 dominance = dominates(pseudo, insn, dom, local);
179 if (dominance) {
180 /* possible partial dominance? */
181 if (dominance < 0)
182 goto next_store;
183 if (dom->opcode == OP_LOAD)
184 goto next_store;
185 /* Yeehaa! Found one! */
186 kill_store(dom);
188 } END_FOR_EACH_PTR_REVERSE(dom);
190 /* Ok, we should check the parents now */
192 next_store:
193 /* Do the next one */;
194 } END_FOR_EACH_PTR_REVERSE(insn);
197 void simplify_memops(struct entrypoint *ep)
199 struct basic_block *bb;
201 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
202 simplify_loads(bb);
203 } END_FOR_EACH_PTR_REVERSE(bb);
205 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
206 kill_dominated_stores(bb);
207 } END_FOR_EACH_PTR_REVERSE(bb);