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 "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, int loads)
  22 {
  23         struct basic_block *parent;
  24
  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;
  31
  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;
  41                         }
  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;
  52
  53                 if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local, loads))
  54                         return 0;
  55                 continue;
  56
  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;
  65 }
  66
  67 /*
  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.
  71  *
  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.
  75  *
  76  * We should make symbol-pseudos count non-load/store usage,
  77  * or something.
  78  */
  79 static int address_taken(pseudo_t pseudo)
  80 {
  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;
  88 }
  89
  90 static int local_pseudo(pseudo_t pseudo)
  91 {
  92         return pseudo->type == PSEUDO_SYM
  93                 && !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
  94                 && !address_taken(pseudo);
  95 }
  96
  97 static void simplify_loads(struct basic_block *bb)
  98 {
  99         struct instruction *insn;
 100
 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;
 110
 111                         /* Check for illegal offsets.. */
 112                         check_access(insn);
 113
 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;
 125                                         }
 126                                         /* Yeehaa! Found one! */
 127                                         convert_load_instruction(insn, dom->target);
 128                                         goto next_load;
 129                                 }
 130                         } END_FOR_EACH_PTR_REVERSE(dom);
 131
 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));
 142                                         }
 143                                         goto next_load;
 144                                 }
 145                                 rewrite_load_instruction(insn, dominators);
 146                         }
 147                 }
 148 next_load:
 149                 /* Do the next one */;
 150         } END_FOR_EACH_PTR_REVERSE(insn);
 151 }
 152
 153 static void kill_store(struct instruction *insn)
 154 {
 155         if (insn) {
 156                 insn->bb = NULL;
 157                 insn->opcode = OP_SNOP;
 158                 kill_use(&insn->target);
 159         }
 160 }
 161
 162 static void kill_dominated_stores(struct basic_block *bb)
 163 {
 164         struct instruction *insn;
 165
 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);
 173
 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);
 187                                 }
 188                         } END_FOR_EACH_PTR_REVERSE(dom);
 189
 190                         /* Ok, we should check the parents now */
 191                 }
 192 next_store:
 193                 /* Do the next one */;
 194         } END_FOR_EACH_PTR_REVERSE(insn);
 195 }
 196
 197 void simplify_memops(struct entrypoint *ep)
 198 {
 199         struct basic_block *bb;
 200
 201         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 202                 simplify_loads(bb);
 203         } END_FOR_EACH_PTR_REVERSE(bb);
 204
 205         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 206                 kill_dominated_stores(bb);
 207         } END_FOR_EACH_PTR_REVERSE(bb);
 208 }