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->size); 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 } END_FOR_EACH_PTR(pu); 73 return 0; 74 } 75 76 static int local_pseudo(pseudo_t pseudo) 77 { 78 return pseudo->type == PSEUDO_SYM 79 && !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL)) 80 && !address_taken(pseudo); 81 } 82 83 static void simplify_loads(struct basic_block *bb) 84 { 85 struct instruction *insn; 86 87 FOR_EACH_PTR_REVERSE(bb->insns, insn) { 88 if (!insn->bb) 89 continue; 90 if (insn->opcode == OP_LOAD) { 91 struct instruction *dom; 92 pseudo_t pseudo = insn->src; 93 int local = local_pseudo(pseudo); 94 struct pseudo_list *dominators; 95 unsigned long generation; 96 97 /* Check for illegal offsets.. */ 98 check_access(insn); 99 100 if (insn->type->ctype.modifiers & MOD_VOLATILE) 101 continue; 102 103 RECURSE_PTR_REVERSE(insn, dom) { 104 int dominance; 105 if (!dom->bb) 106 continue; 107 dominance = dominates(pseudo, insn, dom, local); 108 if (dominance) { 109 /* possible partial dominance? */ 110 if (dominance < 0) { 111 if (dom->opcode == OP_LOAD) 112 continue; 113 goto next_load; 114 } 115 /* Yeehaa! Found one! */ 116 convert_load_instruction(insn, dom->target); 117 goto next_load; 118 } 119 } END_FOR_EACH_PTR_REVERSE(dom); 120 121 /* OK, go find the parents */ 122 generation = ++bb_generation; 123 bb->generation = generation; 124 dominators = NULL; 125 if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) { 126 /* This happens with initial assignments to structures etc.. */ 127 if (!dominators) { 128 if (local) { 129 assert(pseudo->type != PSEUDO_ARG); 130 convert_load_instruction(insn, value_pseudo(insn->type, 0)); 131 } 132 goto next_load; 133 } 134 rewrite_load_instruction(insn, dominators); 135 } 136 } 137 next_load: 138 /* Do the next one */; 139 } END_FOR_EACH_PTR_REVERSE(insn); 140 } 141 142 static void kill_store(struct instruction *insn) 143 { 144 if (insn) { 145 insn->bb = NULL; 146 insn->opcode = OP_SNOP; 147 kill_use(&insn->target); 148 } 149 } 150 151 static void kill_dominated_stores(struct basic_block *bb) 152 { 153 struct instruction *insn; 154 155 FOR_EACH_PTR_REVERSE(bb->insns, insn) { 156 if (!insn->bb) 157 continue; 158 if (insn->opcode == OP_STORE) { 159 struct instruction *dom; 160 pseudo_t pseudo = insn->src; 161 int local = local_pseudo(pseudo); 162 163 RECURSE_PTR_REVERSE(insn, dom) { 164 int dominance; 165 if (!dom->bb) 166 continue; 167 dominance = dominates(pseudo, insn, dom, local); 168 if (dominance) { 169 /* possible partial dominance? */ 170 if (dominance < 0) 171 goto next_store; 172 if (dom->opcode == OP_LOAD) 173 goto next_store; 174 /* Yeehaa! Found one! */ 175 kill_store(dom); 176 } 177 } END_FOR_EACH_PTR_REVERSE(dom); 178 179 /* OK, we should check the parents now */ 180 } 181 next_store: 182 /* Do the next one */; 183 } END_FOR_EACH_PTR_REVERSE(insn); 184 } 185 186 void simplify_memops(struct entrypoint *ep) 187 { 188 struct basic_block *bb; 189 190 FOR_EACH_PTR_REVERSE(ep->bbs, bb) { 191 simplify_loads(bb); 192 } END_FOR_EACH_PTR_REVERSE(bb); 193 194 FOR_EACH_PTR_REVERSE(ep->bbs, bb) { 195 kill_dominated_stores(bb); 196 } END_FOR_EACH_PTR_REVERSE(bb); 197 } 198