src/basesuif/useful/make_instr_ops.cc

   1 /* file "make_instr_ops.cc" */
   2
   3 /*  Copyright (c) 1995 Stanford University
   4
   5     All rights reserved.
   6
   7     This software is provided under the terms described in
   8     the "suif_copyright.h" include file. */
   9
  10 #include <suif_copyright.h>
  11
  12 /*
  13  *  This is the implementation of routines to build instruction
  14  *  operands out of single-use, single-def variables in the same basic
  15  *  block and scope.
  16  */
  17
  18 #define _MODULE_ "libsueful.a"
  19
  20 #define RCS_BASE_FILE make_instr_ops_cc
  21
  22 #include "useful_internal.h"
  23
  24 RCS_BASE(
  25     "$Id: make_instr_ops.cc,v 1.1.1.1 1998/06/16 15:15:33 brm Exp $")
  26
  27
  28 enum bound_kind {BK_LB, BK_UB, BK_STEP};
  29
  30 struct use_def_record
  31   {
  32     instruction *def;
  33     instruction *use;
  34     unsigned use_src_num;
  35     tree_for *for_use;
  36     bound_kind use_bound;
  37
  38     use_def_record(void)  { def = NULL; use = NULL; for_use = NULL; }
  39   };
  40
  41
  42 boolean make_instr_for_bounds = FALSE;
  43
  44
  45 static const char *k_useful_mio_use_def = NULL;
  46
  47 static var_sym_list *pending_vars = NULL;
  48
  49
  50 static void start_symtab(block_symtab *the_symtab);
  51 static void finish_symtab(block_symtab *the_symtab);
  52 static void handle_instr(instruction *the_instr);
  53 static void handle_for_bounds(tree_for *the_for);
  54 static void handle_a_bound(tree_for *the_for, operand bound_op,
  55                            bound_kind which_bound);
  56 static void handle_tree_node_list(tree_node_list *node_list);
  57 static void handle_tree_node(tree_node *the_node);
  58 static void kill_live(void);
  59
  60
  61 extern void init_make_instr_ops(void)
  62   {
  63     k_useful_mio_use_def = lexicon->enter("useful mio use def")->sp;
  64   }
  65
  66 extern void make_instr_ops(tree_node *the_node)
  67   {
  68     assert(pending_vars == NULL);
  69     pending_vars = new var_sym_list;
  70     handle_tree_node(the_node);
  71     assert(pending_vars->is_empty());
  72     delete pending_vars;
  73     pending_vars = NULL;
  74   }
  75
  76
  77 static void start_symtab(block_symtab *the_symtab)
  78   {
  79     sym_node_list_iter sym_iter(the_symtab->symbols());
  80     while (!sym_iter.is_empty())
  81       {
  82         sym_node *this_sym = sym_iter.step();
  83         if (!this_sym->is_var())
  84             continue;
  85         var_sym *this_var = (var_sym *)this_sym;
  86         if (this_var->is_addr_taken() || (!this_var->is_auto()) ||
  87             this_var->is_param() || (this_var->parent_var() != NULL) ||
  88             (this_var->num_children() != 0))
  89           {
  90             continue;
  91           }
  92         this_var->append_annote(k_useful_mio_use_def, new use_def_record);
  93       }
  94   }
  95
  96 static void finish_symtab(block_symtab *the_symtab)
  97   {
  98     sym_node_list_iter sym_iter(the_symtab->symbols());
  99     while (!sym_iter.is_empty())
 100       {
 101         sym_node *this_sym = sym_iter.step();
 102         use_def_record *the_usedef =
 103                 (use_def_record *)(this_sym->get_annote(k_useful_mio_use_def));
 104         if (the_usedef == NULL)
 105             continue;
 106         assert(this_sym->is_var());
 107         operand var_op = operand((var_sym *)this_sym);
 108         if (the_usedef->def != NULL)
 109           {
 110             assert(the_usedef->def->dst_op() == var_op);
 111             operand new_src = operand(the_usedef->def);
 112             if (the_usedef->use != NULL)
 113               {
 114                 assert(the_usedef->for_use == NULL);
 115                 assert(the_usedef->use->src_op(the_usedef->use_src_num) ==
 116                        var_op);
 117                 the_usedef->use->set_src_op(the_usedef->use_src_num, new_src);
 118               }
 119             else
 120               {
 121                 assert(the_usedef->for_use != NULL);
 122                 tree_instr *def_parent = the_usedef->def->parent();
 123                 assert(def_parent->instr() == the_usedef->def);
 124                 the_usedef->def->remove();
 125                 kill_node(def_parent);
 126                 switch (the_usedef->use_bound)
 127                   {
 128                     case BK_LB:
 129                         assert(the_usedef->for_use->lb_op() == var_op);
 130                         the_usedef->for_use->set_lb_op(new_src);
 131                         break;
 132                     case BK_UB:
 133                         assert(the_usedef->for_use->ub_op() == var_op);
 134                         the_usedef->for_use->set_ub_op(new_src);
 135                         break;
 136                     case BK_STEP:
 137                         assert(the_usedef->for_use->step_op() == var_op);
 138                         the_usedef->for_use->set_step_op(new_src);
 139                         break;
 140                     default:
 141                         assert(FALSE);
 142                   }
 143               }
 144           }
 145         delete the_usedef;
 146       }
 147   }
 148
 149 static void handle_instr(instruction *the_instr)
 150   {
 151     unsigned num_srcs = the_instr->num_srcs();
 152     for (unsigned src_num = 0; src_num < num_srcs; ++src_num)
 153       {
 154         operand this_src = the_instr->src_op(src_num);
 155         if (this_src.is_symbol())
 156           {
 157             var_sym *this_var = this_src.symbol();
 158             annote *usedef_annote =
 159                     this_var->annotes()->peek_annote(k_useful_mio_use_def);
 160             if (usedef_annote != NULL)
 161               {
 162                 use_def_record *the_usedef =
 163                         (use_def_record *)(usedef_annote->data());
 164                 assert(the_usedef != NULL);
 165                 if ((the_usedef->def == NULL) || (the_usedef->use != NULL) ||
 166                     (the_usedef->for_use != NULL))
 167                   {
 168                     annote *removed_annote =
 169                             this_var->annotes()->get_annote(
 170                                     k_useful_mio_use_def);
 171                     assert(removed_annote == usedef_annote);
 172                     delete usedef_annote;
 173                     delete the_usedef;
 174                   }
 175                 else
 176                   {
 177                     the_usedef->use = the_instr;
 178                     the_usedef->use_src_num = src_num;
 179                   }
 180               }
 181           }
 182         else if (this_src.is_expr())
 183           {
 184             handle_instr(this_src.instr());
 185           }
 186       }
 187
 188     operand dest_op = the_instr->dst_op();
 189     if (dest_op.is_symbol())
 190       {
 191         var_sym *dest_var = dest_op.symbol();
 192         annote *usedef_annote =
 193                 dest_var->annotes()->peek_annote(k_useful_mio_use_def);
 194         if (usedef_annote != NULL)
 195           {
 196             use_def_record *the_usedef =
 197                     (use_def_record *)(usedef_annote->data());
 198             assert(the_usedef != NULL);
 199             if (the_usedef->def != NULL)
 200               {
 201                 annote *removed_annote =
 202                         dest_var->annotes()->get_annote(k_useful_mio_use_def);
 203                 assert(removed_annote == usedef_annote);
 204                 delete usedef_annote;
 205                 delete the_usedef;
 206               }
 207             else
 208               {
 209                 the_usedef->def = the_instr;
 210                 assert(pending_vars != NULL);
 211                 pending_vars->append(dest_var);
 212               }
 213           }
 214       }
 215
 216     switch (the_instr->opcode())
 217       {
 218         case io_btrue:
 219         case io_bfalse:
 220         case io_jmp:
 221         case io_cal:
 222         case io_ret:
 223         case io_lab:
 224         case io_mbr:
 225         case io_gen:
 226             kill_live();
 227             break;
 228         default:
 229             break;
 230       }
 231   }
 232
 233 static void handle_for_bounds(tree_for *the_for)
 234   {
 235     handle_a_bound(the_for, the_for->lb_op(), BK_LB);
 236     handle_a_bound(the_for, the_for->ub_op(), BK_UB);
 237     handle_a_bound(the_for, the_for->step_op(), BK_STEP);
 238   }
 239
 240 static void handle_a_bound(tree_for *the_for, operand bound_op,
 241                            bound_kind which_bound)
 242   {
 243     if (bound_op.is_symbol())
 244       {
 245         var_sym *this_var = bound_op.symbol();
 246         annote *usedef_annote =
 247                 this_var->annotes()->peek_annote(k_useful_mio_use_def);
 248         if (usedef_annote != NULL)
 249           {
 250             use_def_record *the_usedef =
 251                     (use_def_record *)(usedef_annote->data());
 252             assert(the_usedef != NULL);
 253             if ((the_usedef->def == NULL) || (the_usedef->use != NULL) ||
 254                 (the_usedef->for_use != NULL))
 255               {
 256                 annote *removed_annote =
 257                         this_var->annotes()->get_annote(k_useful_mio_use_def);
 258                 assert(removed_annote == usedef_annote);
 259                 delete usedef_annote;
 260                 delete the_usedef;
 261               }
 262             else
 263               {
 264                 the_usedef->for_use = the_for;
 265                 the_usedef->use_bound = which_bound;
 266               }
 267           }
 268       }
 269     else if (bound_op.is_expr())
 270       {
 271         handle_instr(bound_op.instr());
 272       }
 273   }
 274
 275 static void handle_tree_node_list(tree_node_list *node_list)
 276   {
 277     kill_live();
 278
 279     tree_node_list_iter node_iter(node_list);
 280     while (!node_iter.is_empty())
 281       {
 282         tree_node *this_node = node_iter.step();
 283         handle_tree_node(this_node);
 284       }
 285
 286     kill_live();
 287   }
 288
 289 static void handle_tree_node(tree_node *the_node)
 290   {
 291     switch (the_node->kind())
 292       {
 293         case TREE_INSTR:
 294           {
 295             tree_instr *the_tree_instr = (tree_instr *)the_node;
 296             handle_instr(the_tree_instr->instr());
 297             break;
 298           }
 299         case TREE_FOR:
 300           {
 301             tree_for *the_for = (tree_for *)the_node;
 302             handle_for_bounds(the_for);
 303             handle_tree_node_list(the_for->body());
 304             handle_tree_node_list(the_for->landing_pad());
 305             break;
 306           }
 307         case TREE_BLOCK:
 308           {
 309             tree_block *the_block = (tree_block *)the_node;
 310             start_symtab(the_block->symtab());
 311             handle_tree_node_list(the_block->body());
 312             finish_symtab(the_block->symtab());
 313             break;
 314           }
 315         default:
 316           {
 317             unsigned num_children = the_node->num_child_lists();
 318             for (unsigned child_num = 0; child_num < num_children; ++child_num)
 319                 handle_tree_node_list(the_node->child_list_num(child_num));
 320             break;
 321           }
 322       }
 323   }
 324
 325 static void kill_live(void)
 326   {
 327     while (!pending_vars->is_empty())
 328       {
 329         var_sym *this_var = pending_vars->pop();
 330         annote *usedef_annote =
 331                 this_var->annotes()->peek_annote(k_useful_mio_use_def);
 332         if (usedef_annote != NULL)
 333           {
 334             use_def_record *the_usedef =
 335                     (use_def_record *)(usedef_annote->data());
 336             assert(the_usedef != NULL);
 337             assert(the_usedef->def != NULL);
 338             if ((the_usedef->use == NULL) && (the_usedef->for_use == NULL))
 339               {
 340                 annote *removed_annote =
 341                         this_var->annotes()->get_annote(k_useful_mio_use_def);
 342                 assert(removed_annote == usedef_annote);
 343                 delete usedef_annote;
 344                 delete the_usedef;
 345               }
 346           }
 347       }
 348   }