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->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->type);
  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                 if (pu->userp != &insn->src)
  73                         return 1;
  74         } END_FOR_EACH_PTR(pu);
  75         return 0;
  76 }
  77
  78 static int local_pseudo(pseudo_t pseudo)
  79 {
  80         return pseudo->type == PSEUDO_SYM
  81                 && !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
  82                 && !address_taken(pseudo);
  83 }
  84
  85 static bool compatible_loads(struct instruction *a, struct instruction *b)
  86 {
  87         if (is_integral_type(a->type) && is_float_type(b->type))
  88                 return false;
  89         if (is_float_type(a->type) && is_integral_type(b->type))
  90                 return false;
  91         return true;
  92 }
  93
  94 static void simplify_loads(struct basic_block *bb)
  95 {
  96         struct instruction *insn;
  97
  98         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
  99                 if (!insn->bb)
 100                         continue;
 101                 if (insn->opcode == OP_LOAD) {
 102                         struct instruction *dom;
 103                         pseudo_t pseudo = insn->src;
 104                         int local = local_pseudo(pseudo);
 105                         struct pseudo_list *dominators;
 106                         unsigned long generation;
 107
 108                         /* Check for illegal offsets.. */
 109                         check_access(insn);
 110
 111                         if (insn->is_volatile)
 112                                 continue;
 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                                         if (!compatible_loads(insn, dom))
 127                                                 goto next_load;
 128                                         /* Yeehaa! Found one! */
 129                                         convert_load_instruction(insn, dom->target);
 130                                         goto next_load;
 131                                 }
 132                         } END_FOR_EACH_PTR_REVERSE(dom);
 133
 134                         /* OK, go find the parents */
 135                         generation = ++bb_generation;
 136                         bb->generation = generation;
 137                         dominators = NULL;
 138                         if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) {
 139                                 /* This happens with initial assignments to structures etc.. */
 140                                 if (!dominators) {
 141                                         if (local) {
 142                                                 assert(pseudo->type != PSEUDO_ARG);
 143                                                 convert_load_instruction(insn, value_pseudo(0));
 144                                         }
 145                                         goto next_load;
 146                                 }
 147                                 rewrite_load_instruction(insn, dominators);
 148                         } else {        // cleanup pending phi-sources
 149                                 pseudo_t phi;
 150                                 FOR_EACH_PTR(dominators, phi) {
 151                                         kill_instruction(phi->def);
 152                                 } END_FOR_EACH_PTR(phi);
 153                         }
 154                 }
 155 next_load:
 156                 /* Do the next one */;
 157         } END_FOR_EACH_PTR_REVERSE(insn);
 158 }
 159
 160 static void kill_dominated_stores(struct basic_block *bb)
 161 {
 162         struct instruction *insn;
 163
 164         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 165                 if (!insn->bb)
 166                         continue;
 167                 if (insn->opcode == OP_STORE) {
 168                         struct instruction *dom;
 169                         pseudo_t pseudo = insn->src;
 170                         int local;
 171
 172                         if (!insn->type)
 173                                 continue;
 174                         if (insn->is_volatile)
 175                                 continue;
 176
 177                         local = local_pseudo(pseudo);
 178                         RECURSE_PTR_REVERSE(insn, dom) {
 179                                 int dominance;
 180                                 if (!dom->bb)
 181                                         continue;
 182                                 dominance = dominates(pseudo, insn, dom, local);
 183                                 if (dominance) {
 184                                         /* possible partial dominance? */
 185                                         if (dominance < 0)
 186                                                 goto next_store;
 187                                         if (dom->opcode == OP_LOAD)
 188                                                 goto next_store;
 189                                         /* Yeehaa! Found one! */
 190                                         kill_instruction_force(dom);
 191                                 }
 192                         } END_FOR_EACH_PTR_REVERSE(dom);
 193
 194                         /* OK, we should check the parents now */
 195                 }
 196 next_store:
 197                 /* Do the next one */;
 198         } END_FOR_EACH_PTR_REVERSE(insn);
 199 }
 200
 201 void simplify_memops(struct entrypoint *ep)
 202 {
 203         struct basic_block *bb;
 204         pseudo_t pseudo;
 205
 206         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 207                 simplify_loads(bb);
 208         } END_FOR_EACH_PTR_REVERSE(bb);
 209
 210         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 211                 kill_dominated_stores(bb);
 212         } END_FOR_EACH_PTR_REVERSE(bb);
 213
 214         FOR_EACH_PTR(ep->accesses, pseudo) {
 215                 struct symbol *var = pseudo->sym;
 216                 unsigned long mod;
 217                 if (!var)
 218                         continue;
 219                 mod = var->ctype.modifiers;
 220                 if (mod & (MOD_VOLATILE | MOD_NONLOCAL | MOD_STATIC))
 221                         continue;
 222                 kill_dead_stores(ep, pseudo, local_pseudo(pseudo));
 223         } END_FOR_EACH_PTR(pseudo);
 224 }