memops.c

   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 "simplify.h"
  18 #include "flow.h"
  19
  20 /*
  21  * We should probably sort the phi list just to make it easier to compare
  22  * later for equality.
  23  */
  24 static void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
  25 {
  26         pseudo_t new, phi;
  27
  28         /*
  29          * Check for somewhat common case of duplicate
  30          * phi nodes.
  31          */
  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);
  38
  39         /*
  40          * All the same pseudo - mark the phi-nodes unused
  41          * and convert the load into a LNOP and replace the
  42          * pseudo.
  43          */
  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;
  49
  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;
  56
  57 end:
  58         repeat_phase |= REPEAT_CSE;
  59 }
  60
  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)
  64 {
  65         struct basic_block *parent;
  66
  67         FOR_EACH_PTR(bb->parents, parent) {
  68                 struct instruction *one;
  69                 struct instruction *br;
  70                 pseudo_t phi;
  71
  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;
  83                         }
  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;
  92
  93                 if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
  94                         return 0;
  95                 continue;
  96
  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                 phi->def->phi_node = insn;
 104         } END_FOR_EACH_PTR(parent);
 105         return 1;
 106 }
 107
 108 static int address_taken(pseudo_t pseudo)
 109 {
 110         struct pseudo_user *pu;
 111         FOR_EACH_PTR(pseudo->users, pu) {
 112                 struct instruction *insn = pu->insn;
 113                 if (insn->bb && (insn->opcode != OP_LOAD && insn->opcode != OP_STORE))
 114                         return 1;
 115                 if (pu->userp != &insn->src)
 116                         return 1;
 117         } END_FOR_EACH_PTR(pu);
 118         return 0;
 119 }
 120
 121 static int local_pseudo(pseudo_t pseudo)
 122 {
 123         return pseudo->type == PSEUDO_SYM
 124                 && !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
 125                 && !address_taken(pseudo);
 126 }
 127
 128 static bool compatible_loads(struct instruction *a, struct instruction *b)
 129 {
 130         if (is_integral_type(a->type) && is_float_type(b->type))
 131                 return false;
 132         if (is_float_type(a->type) && is_integral_type(b->type))
 133                 return false;
 134         return true;
 135 }
 136
 137 static void simplify_loads(struct basic_block *bb)
 138 {
 139         struct instruction *insn;
 140
 141         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 142                 if (!insn->bb)
 143                         continue;
 144                 if (insn->opcode == OP_LOAD) {
 145                         struct instruction *dom;
 146                         pseudo_t pseudo = insn->src;
 147                         int local = local_pseudo(pseudo);
 148                         struct pseudo_list *dominators;
 149                         unsigned long generation;
 150
 151                         if (insn->is_volatile)
 152                                 continue;
 153
 154                         if (!has_users(insn->target)) {
 155                                 kill_instruction(insn);
 156                                 continue;
 157                         }
 158
 159                         RECURSE_PTR_REVERSE(insn, dom) {
 160                                 int dominance;
 161                                 if (!dom->bb)
 162                                         continue;
 163                                 dominance = dominates(pseudo, insn, dom, local);
 164                                 if (dominance) {
 165                                         /* possible partial dominance? */
 166                                         if (dominance < 0)  {
 167                                                 if (dom->opcode == OP_LOAD)
 168                                                         continue;
 169                                                 goto next_load;
 170                                         }
 171                                         if (!compatible_loads(insn, dom))
 172                                                 goto next_load;
 173                                         /* Yeehaa! Found one! */
 174                                         replace_with_pseudo(insn, dom->target);
 175                                         goto next_load;
 176                                 }
 177                         } END_FOR_EACH_PTR_REVERSE(dom);
 178
 179                         /* OK, go find the parents */
 180                         generation = ++bb_generation;
 181                         bb->generation = generation;
 182                         dominators = NULL;
 183                         if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) {
 184                                 /* This happens with initial assignments to structures etc.. */
 185                                 if (!dominators) {
 186                                         if (local) {
 187                                                 assert(pseudo->type != PSEUDO_ARG);
 188                                                 replace_with_pseudo(insn, value_pseudo(0));
 189                                         }
 190                                         goto next_load;
 191                                 }
 192                                 rewrite_load_instruction(insn, dominators);
 193                         } else {        // cleanup pending phi-sources
 194                                 int repeat = repeat_phase;
 195                                 pseudo_t phi;
 196                                 FOR_EACH_PTR(dominators, phi) {
 197                                         kill_instruction(phi->def);
 198                                 } END_FOR_EACH_PTR(phi);
 199                                 repeat_phase = repeat;
 200                         }
 201                 }
 202 next_load:
 203                 /* Do the next one */;
 204         } END_FOR_EACH_PTR_REVERSE(insn);
 205 }
 206
 207 static void kill_dominated_stores(struct basic_block *bb)
 208 {
 209         struct instruction *insn;
 210
 211         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 212                 if (!insn->bb)
 213                         continue;
 214                 if (insn->opcode == OP_STORE) {
 215                         struct instruction *dom;
 216                         pseudo_t pseudo = insn->src;
 217                         int local;
 218
 219                         if (!insn->type)
 220                                 continue;
 221                         if (insn->is_volatile)
 222                                 continue;
 223
 224                         local = local_pseudo(pseudo);
 225                         RECURSE_PTR_REVERSE(insn, dom) {
 226                                 int dominance;
 227                                 if (!dom->bb)
 228                                         continue;
 229                                 dominance = dominates(pseudo, insn, dom, local);
 230                                 if (dominance) {
 231                                         /* possible partial dominance? */
 232                                         if (dominance < 0)
 233                                                 goto next_store;
 234                                         if (dom->opcode == OP_LOAD)
 235                                                 goto next_store;
 236                                         /* Yeehaa! Found one! */
 237                                         kill_instruction_force(dom);
 238                                 }
 239                         } END_FOR_EACH_PTR_REVERSE(dom);
 240
 241                         /* OK, we should check the parents now */
 242                 }
 243 next_store:
 244                 /* Do the next one */;
 245         } END_FOR_EACH_PTR_REVERSE(insn);
 246 }
 247
 248 void simplify_memops(struct entrypoint *ep)
 249 {
 250         struct basic_block *bb;
 251         pseudo_t pseudo;
 252
 253         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 254                 simplify_loads(bb);
 255         } END_FOR_EACH_PTR_REVERSE(bb);
 256
 257         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 258                 kill_dominated_stores(bb);
 259         } END_FOR_EACH_PTR_REVERSE(bb);
 260
 261         FOR_EACH_PTR(ep->accesses, pseudo) {
 262                 struct symbol *var = pseudo->sym;
 263                 unsigned long mod;
 264                 if (!var)
 265                         continue;
 266                 mod = var->ctype.modifiers;
 267                 if (mod & (MOD_VOLATILE | MOD_NONLOCAL | MOD_STATIC))
 268                         continue;
 269                 kill_dead_stores(ep, pseudo, local_pseudo(pseudo));
 270         } END_FOR_EACH_PTR(pseudo);
 271 }