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 static void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
  21 {
  22         pseudo_t new = NULL;
  23         pseudo_t phi;
  24
  25         /*
  26          * Check for somewhat common case of duplicate
  27          * phi nodes.
  28          */
  29         FOR_EACH_PTR(dominators, phi) {
  30                 if (!new)
  31                         new = phi->def->phi_src;
  32                 else if (new != phi->def->phi_src)
  33                         goto complex_phi;
  34         } END_FOR_EACH_PTR(phi);
  35
  36         /*
  37          * All the same pseudo - mark the phi-nodes unused
  38          * and convert the load into a LNOP and replace the
  39          * pseudo.
  40          */
  41         replace_with_pseudo(insn, new);
  42         FOR_EACH_PTR(dominators, phi) {
  43                 kill_instruction(phi->def);
  44         } END_FOR_EACH_PTR(phi);
  45         goto end;
  46
  47 complex_phi:
  48         kill_use(&insn->src);
  49         insn->opcode = OP_PHI;
  50         insn->phi_list = dominators;
  51
  52 end:
  53         repeat_phase |= REPEAT_CSE;
  54 }
  55
  56 static int find_dominating_parents(struct instruction *insn,
  57         struct basic_block *bb, struct pseudo_list **dominators,
  58         int local)
  59 {
  60         struct basic_block *parent;
  61
  62         FOR_EACH_PTR(bb->parents, parent) {
  63                 struct instruction *phisrc;
  64                 struct instruction *one;
  65                 pseudo_t phi;
  66
  67                 FOR_EACH_PTR_REVERSE(parent->insns, one) {
  68                         int dominance;
  69                         if (!one->bb)
  70                                 continue;
  71                         if (one == insn)
  72                                 goto no_dominance;
  73                         dominance = dominates(insn, one, local);
  74                         if (dominance < 0) {
  75                                 if (one->opcode == OP_LOAD)
  76                                         continue;
  77                                 return 0;
  78                         }
  79                         if (!dominance)
  80                                 continue;
  81                         goto found_dominator;
  82                 } END_FOR_EACH_PTR_REVERSE(one);
  83 no_dominance:
  84                 if (parent->generation == bb->generation)
  85                         continue;
  86                 parent->generation = bb->generation;
  87
  88                 if (!find_dominating_parents(insn, parent, dominators, local))
  89                         return 0;
  90                 continue;
  91
  92 found_dominator:
  93                 phisrc = alloc_phisrc(one->target, one->type);
  94                 phisrc->phi_node = insn;
  95                 insert_last_instruction(parent, phisrc);
  96                 phi = phisrc->target;
  97                 phi->ident = phi->ident ? : one->target->ident;
  98                 use_pseudo(insn, phi, add_pseudo(dominators, phi));
  99         } END_FOR_EACH_PTR(parent);
 100         return 1;
 101 }
 102
 103 static int address_taken(pseudo_t pseudo)
 104 {
 105         struct pseudo_user *pu;
 106         FOR_EACH_PTR(pseudo->users, pu) {
 107                 struct instruction *insn = pu->insn;
 108                 if (insn->bb && (insn->opcode != OP_LOAD && insn->opcode != OP_STORE))
 109                         return 1;
 110                 if (pu->userp != &insn->src)
 111                         return 1;
 112         } END_FOR_EACH_PTR(pu);
 113         return 0;
 114 }
 115
 116 static int local_pseudo(pseudo_t pseudo)
 117 {
 118         return pseudo->type == PSEUDO_SYM
 119                 && !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
 120                 && !address_taken(pseudo);
 121 }
 122
 123 static bool compatible_loads(struct instruction *a, struct instruction *b)
 124 {
 125         if (is_integral_type(a->type) && is_float_type(b->type))
 126                 return false;
 127         if (is_float_type(a->type) && is_integral_type(b->type))
 128                 return false;
 129         return true;
 130 }
 131
 132 static void simplify_loads(struct basic_block *bb)
 133 {
 134         struct instruction *insn;
 135
 136         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 137                 if (!insn->bb)
 138                         continue;
 139                 if (insn->opcode == OP_LOAD) {
 140                         struct instruction *dom;
 141                         pseudo_t pseudo = insn->src;
 142                         int local = local_pseudo(pseudo);
 143                         struct pseudo_list *dominators;
 144
 145                         if (insn->is_volatile)
 146                                 continue;
 147
 148                         if (!has_users(insn->target)) {
 149                                 kill_instruction(insn);
 150                                 continue;
 151                         }
 152
 153                         RECURSE_PTR_REVERSE(insn, dom) {
 154                                 int dominance;
 155                                 if (!dom->bb)
 156                                         continue;
 157                                 dominance = dominates(insn, dom, local);
 158                                 if (dominance) {
 159                                         /* possible partial dominance? */
 160                                         if (dominance < 0)  {
 161                                                 if (dom->opcode == OP_LOAD)
 162                                                         continue;
 163                                                 goto next_load;
 164                                         }
 165                                         if (!compatible_loads(insn, dom))
 166                                                 goto next_load;
 167                                         /* Yeehaa! Found one! */
 168                                         replace_with_pseudo(insn, dom->target);
 169                                         goto next_load;
 170                                 }
 171                         } END_FOR_EACH_PTR_REVERSE(dom);
 172
 173                         /* OK, go find the parents */
 174                         bb->generation = ++bb_generation;
 175                         dominators = NULL;
 176                         if (find_dominating_parents(insn, bb, &dominators, local)) {
 177                                 /* This happens with initial assignments to structures etc.. */
 178                                 if (!dominators) {
 179                                         if (local) {
 180                                                 assert(pseudo->type != PSEUDO_ARG);
 181                                                 replace_with_pseudo(insn, value_pseudo(0));
 182                                         }
 183                                         goto next_load;
 184                                 }
 185                                 rewrite_load_instruction(insn, dominators);
 186                         } else {        // cleanup pending phi-sources
 187                                 int repeat = repeat_phase;
 188                                 pseudo_t phi;
 189                                 FOR_EACH_PTR(dominators, phi) {
 190                                         kill_instruction(phi->def);
 191                                 } END_FOR_EACH_PTR(phi);
 192                                 repeat_phase = repeat;
 193                         }
 194                 }
 195 next_load:
 196                 /* Do the next one */;
 197         } END_FOR_EACH_PTR_REVERSE(insn);
 198 }
 199
 200 static bool try_to_kill_store(struct instruction *insn,
 201                              struct instruction *dom, int local)
 202 {
 203         int dominance = dominates(insn, dom, local);
 204
 205         if (dominance) {
 206                 /* possible partial dominance? */
 207                 if (dominance < 0)
 208                         return false;
 209                 if (insn->target == dom->target && insn->bb == dom->bb) {
 210                         // found a memop which makes the store redundant
 211                         kill_instruction_force(insn);
 212                         return false;
 213                 }
 214                 if (dom->opcode == OP_LOAD)
 215                         return false;
 216                 if (dom->is_volatile)
 217                         return false;
 218                 /* Yeehaa! Found one! */
 219                 kill_instruction_force(dom);
 220         }
 221         return true;
 222 }
 223
 224 static void kill_dominated_stores(struct basic_block *bb)
 225 {
 226         struct instruction *insn;
 227
 228         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 229                 if (!insn->bb)
 230                         continue;
 231                 if (insn->opcode == OP_STORE) {
 232                         struct basic_block *par;
 233                         struct instruction *dom;
 234                         pseudo_t pseudo = insn->src;
 235                         int local;
 236
 237                         if (!insn->type)
 238                                 continue;
 239                         if (insn->is_volatile)
 240                                 continue;
 241
 242                         local = local_pseudo(pseudo);
 243                         RECURSE_PTR_REVERSE(insn, dom) {
 244                                 if (!dom->bb)
 245                                         continue;
 246                                 if (!try_to_kill_store(insn, dom, local))
 247                                         goto next_store;
 248                         } END_FOR_EACH_PTR_REVERSE(dom);
 249
 250                         /* OK, we should check the parents now */
 251                         FOR_EACH_PTR(bb->parents, par) {
 252
 253                                 if (bb_list_size(par->children) != 1)
 254                                         goto next_parent;
 255                                 FOR_EACH_PTR(par->insns, dom) {
 256                                         if (!dom->bb)
 257                                                 continue;
 258                                         if (dom == insn)
 259                                                 goto next_parent;
 260                                         if (!try_to_kill_store(insn, dom, local))
 261                                                 goto next_parent;
 262                                 } END_FOR_EACH_PTR(dom);
 263 next_parent:
 264                                 ;
 265                         } END_FOR_EACH_PTR(par);
 266                 }
 267 next_store:
 268                 /* Do the next one */;
 269         } END_FOR_EACH_PTR_REVERSE(insn);
 270 }
 271
 272 void simplify_memops(struct entrypoint *ep)
 273 {
 274         struct basic_block *bb;
 275         pseudo_t pseudo;
 276
 277         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 278                 simplify_loads(bb);
 279         } END_FOR_EACH_PTR_REVERSE(bb);
 280
 281         FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 282                 kill_dominated_stores(bb);
 283         } END_FOR_EACH_PTR_REVERSE(bb);
 284
 285         FOR_EACH_PTR(ep->accesses, pseudo) {
 286                 struct symbol *var = pseudo->sym;
 287                 unsigned long mod;
 288                 if (!var)
 289                         continue;
 290                 mod = var->ctype.modifiers;
 291                 if (mod & (MOD_VOLATILE | MOD_NONLOCAL | MOD_STATIC))
 292                         continue;
 293                 kill_dead_stores(ep, pseudo, local_pseudo(pseudo));
 294         } END_FOR_EACH_PTR(pseudo);
 295 }