xref: /illumos-gate/usr/src/tools/smatch/src/memops.c (revision c85f09cc92abd00c84e58ec9f0f5d942906cb713)
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 
find_dominating_parents(pseudo_t pseudo,struct instruction * insn,struct basic_block * bb,unsigned long generation,struct pseudo_list ** dominators,int local)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)
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);
46 no_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 
55 found_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 
address_taken(pseudo_t pseudo)65 static 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 
local_pseudo(pseudo_t pseudo)78 static 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 
simplify_loads(struct basic_block * bb)85 static 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 		}
144 next_load:
145 		/* Do the next one */;
146 	} END_FOR_EACH_PTR_REVERSE(insn);
147 }
148 
kill_dominated_stores(struct basic_block * bb)149 static 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 		}
185 next_store:
186 		/* Do the next one */;
187 	} END_FOR_EACH_PTR_REVERSE(insn);
188 }
189 
simplify_memops(struct entrypoint * ep)190 void 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