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 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 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 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 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 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 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