src/basesuif/useful/labinfo.cc

   1 /* file "labinfo.cc" */
   2
   3 /*  Copyright (c) 1994 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 file implements routines to get information about how labels
  14  *  are used in the SUIF code for the SUIF library of miscellaneous
  15  *  useful routines.
  16  */
  17
  18 #define _MODULE_ "libuseful.a"
  19
  20 #define RCS_BASE_FILE useful_labinfo_cc
  21
  22 #include "useful_internal.h"
  23
  24 RCS_BASE(
  25     "$Id: labinfo.cc,v 1.1.1.1 1998/06/16 15:15:32 brm Exp $")
  26
  27 /*----------------------------------------------------------------------*
  28     Begin Constant Declarations
  29  *----------------------------------------------------------------------*/
  30
  31 /*----------------------------------------------------------------------*
  32     End Constant Declarations
  33  *----------------------------------------------------------------------*/
  34 /*----------------------------------------------------------------------*
  35     Begin Type Declarations
  36  *----------------------------------------------------------------------*/
  37
  38 /*----------------------------------------------------------------------*
  39     End Type Declarations
  40  *----------------------------------------------------------------------*/
  41 /*----------------------------------------------------------------------*
  42     Begin Private Global Variables
  43  *----------------------------------------------------------------------*/
  44
  45 static const char *k_useful_labinfo_info;
  46 static const char *k_useful_labinfo_backward;
  47 static const char *k_useful_labinfo_num_back;
  48
  49 /*----------------------------------------------------------------------*
  50     End Private Global Variables
  51  *----------------------------------------------------------------------*/
  52 /*----------------------------------------------------------------------*
  53     Begin Private Function Declarations
  54  *----------------------------------------------------------------------*/
  55
  56 static void add_data_for_node(tree_node *the_node);
  57 static void add_data_for_list(tree_node_list *the_list);
  58 static void add_data_for_label_instr(in_lab *the_label_instr);
  59 static void add_data_for_branch(in_bj *the_branch);
  60 static void add_data_for_mbr(in_mbr *the_mbr);
  61 static void remove_data_for_node(tree_node *the_node);
  62 static void remove_data_for_list(tree_node_list *the_list);
  63 static label_info *create_or_get_info(label_sym *the_label);
  64 static void delete_label_info(label_sym *the_label);
  65
  66 /*----------------------------------------------------------------------*
  67     End Private Function Declarations
  68  *----------------------------------------------------------------------*/
  69 /*----------------------------------------------------------------------*
  70     Begin Public Function Implementations
  71  *----------------------------------------------------------------------*/
  72
  73 extern void build_label_info(tree_node_list *node_list)
  74   {
  75     tree_node *parent_node = node_list->parent();
  76     switch (parent_node->kind())
  77       {
  78         case TREE_LOOP:
  79         case TREE_FOR:
  80         case TREE_IF:
  81             break;
  82         case TREE_BLOCK:
  83             if (parent_node->is_proc())
  84                 break;
  85             /* fall through */
  86         case TREE_INSTR:
  87         default:
  88             assert(FALSE);
  89       }
  90
  91     add_data_for_list(node_list);
  92   }
  93
  94 extern void remove_label_info(tree_node_list *node_list)
  95   {
  96     tree_node *parent_node = node_list->parent();
  97     switch (parent_node->kind())
  98       {
  99         case TREE_LOOP:
 100         case TREE_FOR:
 101         case TREE_IF:
 102             break;
 103         case TREE_BLOCK:
 104             if (parent_node->is_proc())
 105                 break;
 106             /* fall through */
 107         case TREE_INSTR:
 108         default:
 109             assert(FALSE);
 110       }
 111
 112     remove_data_for_list(node_list);
 113   }
 114
 115 extern label_info *get_lab_info(label_sym *the_label)
 116   {
 117     void *data = the_label->peek_annote(k_useful_labinfo_info);
 118     assert(data != NULL);
 119     return (label_info *)data;
 120   }
 121
 122 extern boolean is_backward_branch(in_bj *the_bj)
 123   {
 124     return (the_bj->annotes()->peek_annote(k_useful_labinfo_backward) != NULL);
 125   }
 126
 127 extern boolean mbr_lab_is_backward(in_mbr *the_mbr, label_sym *the_label)
 128   {
 129     void *backward_data = the_mbr->peek_annote(k_useful_labinfo_backward);
 130     assert(backward_data != NULL);
 131     boolean *backward_table = (boolean *)backward_data;
 132
 133     unsigned num_labs = the_mbr->num_labs();
 134
 135     if (the_label == the_mbr->default_lab())
 136         return backward_table[num_labs];
 137
 138     for (unsigned lab_num = 0; lab_num < num_labs; ++lab_num)
 139       {
 140         if (the_label == the_mbr->label(lab_num))
 141             return backward_table[lab_num];
 142       }
 143     assert(FALSE);
 144     return FALSE;
 145   }
 146
 147 extern int num_mbr_back_labs(in_mbr *the_mbr)
 148   {
 149     void *num_back_data = the_mbr->peek_annote(k_useful_labinfo_num_back);
 150     return (int)(long)num_back_data;
 151   }
 152
 153 extern void create_info_for_new_lab_instr(in_lab *new_lab_instr)
 154   {
 155     add_data_for_label_instr(new_lab_instr);
 156   }
 157
 158 /*----------------------------------------------------------------------*
 159     End Public Function Implementations
 160  *----------------------------------------------------------------------*/
 161 /*----------------------------------------------------------------------*
 162     Begin Internal Function Implementations
 163  *----------------------------------------------------------------------*/
 164
 165 extern void init_labinfo(void)
 166   {
 167     k_useful_labinfo_info = lexicon->enter("useful labinfo info")->sp;
 168     k_useful_labinfo_backward = lexicon->enter("useful labinfo backward")->sp;
 169     k_useful_labinfo_num_back = lexicon->enter("useful labinfo num back")->sp;
 170   }
 171
 172 /*----------------------------------------------------------------------*
 173     End Internal Function Implementations
 174  *----------------------------------------------------------------------*/
 175 /*----------------------------------------------------------------------*
 176     Begin Private Function Implementations
 177  *----------------------------------------------------------------------*/
 178
 179 static void add_data_for_node(tree_node *the_node)
 180   {
 181     switch (the_node->kind())
 182       {
 183         case TREE_INSTR:
 184           {
 185             tree_instr *the_tree_instr = (tree_instr *)the_node;
 186             instruction *the_instr = the_tree_instr->instr();
 187             switch (the_instr->opcode())
 188               {
 189                 case io_lab:
 190                   {
 191                     in_lab *the_label_instr = (in_lab *)the_instr;
 192                     add_data_for_label_instr(the_label_instr);
 193                     break;
 194                   }
 195                 case io_btrue:
 196                 case io_bfalse:
 197                 case io_jmp:
 198                   {
 199                     in_bj *the_branch = (in_bj *)the_instr;
 200                     add_data_for_branch(the_branch);
 201                     break;
 202                   }
 203                 case io_mbr:
 204                   {
 205                     in_mbr *the_mbr = (in_mbr *)the_instr;
 206                     add_data_for_mbr(the_mbr);
 207                     break;
 208                   }
 209                 default:
 210                     break;
 211               }
 212             break;
 213           }
 214         case TREE_BLOCK:
 215           {
 216             tree_block *the_block = (tree_block *)the_node;
 217             add_data_for_list(the_block->body());
 218             break;
 219           }
 220         default:
 221             break;
 222       }
 223   }
 224
 225 static void add_data_for_list(tree_node_list *the_list)
 226   {
 227     tree_node_list_iter node_iter(the_list);
 228     while (!node_iter.is_empty())
 229       {
 230         tree_node *this_node = node_iter.step();
 231         add_data_for_node(this_node);
 232       }
 233   }
 234
 235 static void add_data_for_label_instr(in_lab *the_label_instr)
 236   {
 237     label_sym *the_label_sym = the_label_instr->label();
 238     label_info *info_block = create_or_get_info(the_label_sym);
 239     if (info_block->definition != NULL)
 240       {
 241         error_line(1, the_label_instr, "label `%s' is multiply defined",
 242                    the_label_sym->name());
 243       }
 244     info_block->definition = the_label_instr;
 245   }
 246
 247 static void add_data_for_branch(in_bj *the_branch)
 248   {
 249     label_info *info_block = create_or_get_info(the_branch->target());
 250     if (info_block->definition == NULL)
 251       {
 252         info_block->forward_jumps.append(the_branch);
 253       }
 254     else
 255       {
 256         info_block->backward_jumps.append(the_branch);
 257         the_branch->append_annote(k_useful_labinfo_backward, NULL);
 258       }
 259   }
 260
 261 static void add_data_for_mbr(in_mbr *the_mbr)
 262   {
 263     unsigned num_labs = the_mbr->num_labs();
 264     boolean *backward_table = new boolean[num_labs + 1];
 265     int back_counter = 0;
 266     for (unsigned lab_num = 0; lab_num < num_labs; ++lab_num)
 267       {
 268         label_sym *this_label_sym = the_mbr->label(lab_num);
 269         label_info *info_block = create_or_get_info(this_label_sym);
 270         if (info_block->definition == NULL)
 271           {
 272             info_block->forward_jumps.append(the_mbr);
 273             backward_table[lab_num] = FALSE;
 274           }
 275         else
 276           {
 277             info_block->backward_jumps.append(the_mbr);
 278             backward_table[lab_num] = TRUE;
 279             ++back_counter;
 280           }
 281       }
 282
 283     label_info *info_block = create_or_get_info(the_mbr->default_lab());
 284     if (info_block->definition == NULL)
 285       {
 286         info_block->forward_jumps.append(the_mbr);
 287         backward_table[num_labs] = FALSE;
 288       }
 289     else
 290       {
 291         info_block->backward_jumps.append(the_mbr);
 292         backward_table[num_labs] = TRUE;
 293         ++back_counter;
 294       }
 295
 296     the_mbr->append_annote(k_useful_labinfo_backward, backward_table);
 297     the_mbr->append_annote(k_useful_labinfo_num_back, (void *)back_counter);
 298   }
 299
 300 static void remove_data_for_node(tree_node *the_node)
 301   {
 302     switch (the_node->kind())
 303       {
 304         case TREE_INSTR:
 305           {
 306             tree_instr *the_tree_instr = (tree_instr *)the_node;
 307             instruction *the_instr = the_tree_instr->instr();
 308             switch (the_instr->opcode())
 309               {
 310                 case io_lab:
 311                   {
 312                     in_lab *the_label_instr = (in_lab *)the_instr;
 313                     delete_label_info(the_label_instr->label());
 314                     break;
 315                   }
 316                 case io_btrue:
 317                 case io_bfalse:
 318                 case io_jmp:
 319                   {
 320                     in_bj *the_branch = (in_bj *)the_instr;
 321                     delete_label_info(the_branch->target());
 322                     if (the_branch->annotes()->peek_annote(
 323                                 k_useful_labinfo_backward) != NULL)
 324                       {
 325                         (void)(the_branch->get_annote(
 326                                 k_useful_labinfo_backward));
 327                       }
 328                     break;
 329                   }
 330                 case io_mbr:
 331                   {
 332                     in_mbr *the_mbr = (in_mbr *)the_instr;
 333                     unsigned num_labs = the_mbr->num_labs();
 334                     for (unsigned lab_num = 0; lab_num < num_labs; ++lab_num)
 335                         delete_label_info(the_mbr->label(lab_num));
 336                     delete_label_info(the_mbr->default_lab());
 337                     void *backward_data =
 338                             the_mbr->get_annote(k_useful_labinfo_backward);
 339                     assert(backward_data != NULL);
 340                     boolean *backward_table = (boolean *)backward_data;
 341                     delete[] backward_table;
 342                     (void)(the_mbr->get_annote(k_useful_labinfo_num_back));
 343                     break;
 344                   }
 345                 default:
 346                     break;
 347               }
 348             break;
 349           }
 350         case TREE_BLOCK:
 351           {
 352             tree_block *the_block = (tree_block *)the_node;
 353             remove_data_for_list(the_block->body());
 354             break;
 355           }
 356         default:
 357             break;
 358       }
 359   }
 360
 361 static void remove_data_for_list(tree_node_list *the_list)
 362   {
 363     tree_node_list_iter node_iter(the_list);
 364     while (!node_iter.is_empty())
 365       {
 366         tree_node *this_node = node_iter.step();
 367         remove_data_for_node(this_node);
 368       }
 369   }
 370
 371 static label_info *create_or_get_info(label_sym *the_label)
 372   {
 373     void *data = the_label->peek_annote(k_useful_labinfo_info);
 374     if (data != NULL)
 375         return (label_info *)data;
 376
 377     label_info *new_info_block = new label_info;
 378     new_info_block->definition = NULL;
 379     the_label->append_annote(k_useful_labinfo_info, new_info_block);
 380     return new_info_block;
 381   }
 382
 383 static void delete_label_info(label_sym *the_label)
 384   {
 385     if (the_label->peek_annote(k_useful_labinfo_info) != NULL)
 386       {
 387         void *old_data = the_label->get_annote(k_useful_labinfo_info);
 388         label_info *old_info_block = (label_info *)old_data;
 389         delete old_info_block;
 390       }
 391   }
 392
 393 /*----------------------------------------------------------------------*
 394     End Private Function Implementations
 395  *----------------------------------------------------------------------*/