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