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         /*
  26          * The entrypoint is special - it dominates all non-local
  27          * pseudos, but no local ones.
  28          */
  29         if (bb == bb->ep->entry)
  30                 return !!local;
  31
  32         if (bb_list_size(bb->parents) > 1)
  33                 loads = 0;
  34         FOR_EACH_PTR(bb->parents, parent) {
  35                 struct instruction *one;
  36                 struct instruction *br;
  37                 pseudo_t phi;
  38
  39                 FOR_EACH_PTR_REVERSE(parent->insns, one) {
  40                         int dominance;
  41                         if (one == insn)
  42                                 goto no_dominance;
  43                         dominance = dominates(pseudo, insn, one, local);
  44                         if (dominance < 0) {
  45                                 if (one->opcode == OP_LOAD)
  46                                         continue;
  47                                 return 0;
  48                         }
  49                         if (!dominance)
  50                                 continue;
  51                         if (one->opcode == OP_LOAD && !loads)
  52                                 continue;
  53                         goto found_dominator;
  54                 } END_FOR_EACH_PTR_REVERSE(one);
  55 no_dominance:
  56                 if (parent->generation == generation)
  57                         continue;
  58                 parent->generation = generation;
  59
  60                 if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local, loads))
  61                         return 0;
  62                 continue;
  63
  64 found_dominator:
  65                 br = delete_last_instruction(&parent->insns);
  66                 phi = alloc_phi(parent, one->target, one->size);
  67                 phi->ident = phi->ident ? : one->target->ident;
  68                 add_instruction(&parent->insns, br);
  69                 use_pseudo(phi, add_pseudo(dominators, phi));
  70         } END_FOR_EACH_PTR(parent);
  71         return 1;
  72 }
  73
  74 static inline int address_taken(pseudo_t pseudo)
  75 {
  76         pseudo_t *usep;
  77         FOR_EACH_PTR(pseudo->users, usep) {
  78                 struct instruction *insn = container(usep, struct instruction, src);
  79                 if (insn->bb && insn->opcode == OP_SETVAL)
  80                         return 1;
  81         } END_FOR_EACH_PTR(usep);
  82         return 0;
  83 }
  84
  85 static int local_pseudo(pseudo_t pseudo)
  86 {
  87         return pseudo->type == PSEUDO_SYM
  88                 && !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
  89                 && !address_taken(pseudo);
  90 }
  91
  92 static void simplify_loads(struct basic_block *bb)
  93 {
  94         struct instruction *insn;
  95
  96         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
  97                 if (!insn->bb)
  98                         continue;
  99                 if (insn->opcode == OP_LOAD) {
 100                         struct instruction *dom;
 101                         pseudo_t pseudo = insn->src;
 102                         int local = local_pseudo(pseudo);
 103                         struct pseudo_list *dominators;
 104                         unsigned long generation;
 105
 106                         RECURSE_PTR_REVERSE(insn, dom) {
 107                                 int dominance;
 108                                 if (!dom->bb)
 109                                         continue;
 110                                 dominance = dominates(pseudo, insn, dom, local);
 111                                 if (dominance) {
 112                                         /* possible partial dominance? */
 113                                         if (dominance < 0)  {
 114                                                 if (dom->opcode == OP_LOAD)
 115                                                         continue;
 116                                                 goto next_load;
 117                                         }
 118                                         /* Yeehaa! Found one! */
 119                                         convert_load_instruction(insn, dom->target);
 120                                         goto next_load;
 121                                 }
 122                         } END_FOR_EACH_PTR_REVERSE(dom);
 123
 124                         /* Ok, go find the parents */
 125                         generation = ++bb_generation;
 126                         bb->generation = generation;
 127                         dominators = NULL;
 128                         if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local, 1)) {
 129                                 /* This happens with initial assignments to structures etc.. */
 130                                 if (!dominators) {
 131                                         if (local) {
 132                                                 assert(pseudo->type != PSEUDO_ARG);
 133                                                 convert_load_instruction(insn, value_pseudo(0));
 134                                         }
 135                                         goto next_load;
 136                                 }
 137                                 rewrite_load_instruction(insn, dominators);
 138                         }
 139                 }
 140 next_load:
 141                 /* Do the next one */;
 142         } END_FOR_EACH_PTR_REVERSE(insn);
 143 }
 144
 145 static void kill_store(struct instruction *insn)
 146 {
 147         if (insn) {
 148                 insn->bb = NULL;
 149                 insn->opcode = OP_SNOP;
 150                 kill_use(&insn->target);
 151         }
 152 }
 153
 154 static void kill_dominated_stores(struct basic_block *bb)
 155 {
 156         struct instruction *insn;
 157
 158         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 159                 if (!insn->bb)
 160                         continue;
 161                 if (insn->opcode == OP_STORE) {
 162                         struct instruction *dom;
 163                         pseudo_t pseudo = insn->src;
 164                         int local = local_pseudo(pseudo);
 165
 166                         RECURSE_PTR_REVERSE(insn, dom) {
 167                                 int dominance;
 168                                 if (!dom->bb)
 169                                         continue;
 170                                 dominance = dominates(pseudo, insn, dom, local);
 171                                 if (dominance) {
 172                                         /* possible partial dominance? */
 173                                         if (dominance < 0)
 174                                                 goto next_store;
 175                                         if (dom->opcode == OP_LOAD)
 176                                                 goto next_store;
 177                                         /* Yeehaa! Found one! */
 178                                         kill_store(dom);
 179                                 }
 180                         } END_FOR_EACH_PTR_REVERSE(dom);
 181
 182                         /* Ok, we should check the parents now */
 183                 }
 184 next_store:
 185                 /* Do the next one */;
 186         } END_FOR_EACH_PTR_REVERSE(insn);
 187 }
 188
 189 void simplify_memops(struct entrypoint *ep)
 190 {
 191         struct basic_block *bb;
 192
 193         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 194                 simplify_loads(bb);
 195         } END_FOR_EACH_PTR_REVERSE(bb);
 196
 197         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 198                 kill_dominated_stores(bb);
 199         } END_FOR_EACH_PTR_REVERSE(bb);
 200 }