src/basesuif/useful/test_modification.cc

   1 /* file "test_modification.cc" */
   2
   3 /*  Copyright (c) 1994,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 test for potential
  14  *  modification of variables or expressions by SUIF code, for the
  15  *  SUIF library of miscellaneous useful routines.
  16  */
  17
  18 #define _MODULE_ "libsueful.a"
  19
  20 #define RCS_BASE_FILE test_modification_cc
  21
  22 #include "useful_internal.h"
  23
  24 RCS_BASE(
  25     "$Id: test_modification.cc,v 1.1.1.1 1998/06/16 15:15:37 brm Exp $")
  26
  27 /*----------------------------------------------------------------------*
  28     Begin Type Declarations
  29  *----------------------------------------------------------------------*/
  30
  31 /*----------------------------------------------------------------------*
  32     End Type Declarations
  33  *----------------------------------------------------------------------*/
  34 /*----------------------------------------------------------------------*
  35     Begin Private Function Declarations
  36  *----------------------------------------------------------------------*/
  37
  38 static boolean node_might_modify(var_sym *the_var, tree_node *the_node);
  39 static boolean expr_might_modify(var_sym *the_var, instruction *the_instr);
  40 static boolean op_might_modify(var_sym *the_var, operand the_op);
  41
  42 /*----------------------------------------------------------------------*
  43     End Private Function Declarations
  44  *----------------------------------------------------------------------*/
  45 /*----------------------------------------------------------------------*
  46     Begin Public Function Implementations
  47  *----------------------------------------------------------------------*/
  48
  49 extern boolean might_modify(var_sym *the_variable, tree_node_list *node_list)
  50   {
  51     if (the_variable->type()->is_volatile())
  52         return TRUE;
  53
  54     tree_node_list_iter the_iter(node_list);
  55     while (!the_iter.is_empty())
  56       {
  57         tree_node *this_node = the_iter.step();
  58         if (node_might_modify(the_variable, this_node))
  59             return TRUE;
  60       }
  61
  62     return FALSE;
  63   }
  64
  65 extern boolean might_modify(operand the_operand, tree_node_list *node_list)
  66   {
  67     switch (the_operand.kind())
  68       {
  69         case OPER_NULL:
  70             return FALSE;
  71         case OPER_SYM:
  72           {
  73             var_sym *the_var = the_operand.symbol();
  74             if ((node_list->parent() != NULL) &&
  75                 (node_list->parent()->scope() != NULL) &&
  76                 (!node_list->parent()->scope()->is_ancestor(
  77                           the_var->parent())))
  78               {
  79                 return TRUE;
  80               }
  81             return might_modify(the_var, node_list);
  82           }
  83         case OPER_INSTR:
  84           {
  85             instruction *instr = the_operand.instr();
  86             return might_modify(instr, node_list);
  87           }
  88         default:
  89             assert(FALSE);
  90             return TRUE;
  91       }
  92   }
  93
  94 extern boolean might_modify(instruction *the_instr, tree_node_list *node_list)
  95   {
  96     if (instr_is_impure_call(the_instr) || (the_instr->opcode() == io_gen))
  97         return TRUE;
  98
  99     if ((the_instr->opcode() == io_lod) || (the_instr->opcode() == io_cal))
 100       {
 101         unsigned num_srcs = the_instr->num_srcs();
 102         unsigned src_num = 0;
 103         if (the_instr->opcode() == io_cal)
 104             src_num = 1;
 105         for (; src_num < num_srcs; ++src_num)
 106           {
 107             operand this_op = the_instr->src_op(src_num);
 108             if (this_op.type()->unqual()->is_ptr())
 109               {
 110                 sym_node *addr_symbol = operand_address_root_symbol(this_op);
 111                 if (addr_symbol == NULL)
 112                     return TRUE;
 113                 if ((node_list->parent() != NULL) &&
 114                     (node_list->parent()->scope() != NULL) &&
 115                     (!node_list->parent()->scope()->is_ancestor(
 116                               addr_symbol->parent())))
 117                   {
 118                     return TRUE;
 119                   }
 120                 if (addr_symbol->is_var())
 121                   {
 122                     var_sym *addr_var = (var_sym *)addr_symbol;
 123                     if (might_modify(addr_var, node_list))
 124                         return TRUE;
 125                   }
 126               }
 127           }
 128       }
 129
 130     unsigned num_srcs = the_instr->num_srcs();
 131     for (unsigned src_num = 0; src_num < num_srcs; ++src_num)
 132       {
 133         if (might_modify(the_instr->src_op(src_num), node_list))
 134             return TRUE;
 135       }
 136
 137     return FALSE;
 138   }
 139
 140 /*----------------------------------------------------------------------*
 141     End Public Function Implementations
 142  *----------------------------------------------------------------------*/
 143 /*----------------------------------------------------------------------*
 144     Begin Private Function Implementations
 145  *----------------------------------------------------------------------*/
 146
 147 static boolean node_might_modify(var_sym *the_var, tree_node *the_node)
 148   {
 149     switch (the_node->kind())
 150       {
 151         case TREE_INSTR:
 152           {
 153             tree_instr *the_tree_instr = (tree_instr *)the_node;
 154             return expr_might_modify(the_var, the_tree_instr->instr());
 155           }
 156         case TREE_LOOP:
 157           {
 158             tree_loop *the_loop = (tree_loop *)the_node;
 159             if (might_modify(the_var, the_loop->body()))
 160                 return TRUE;
 161             return might_modify(the_var, the_loop->test());
 162           }
 163         case TREE_FOR:
 164           {
 165             tree_for *the_for = (tree_for *)the_node;
 166             if (the_var->overlaps(the_for->index()))
 167                 return TRUE;
 168             if (op_might_modify(the_var, the_for->lb_op()))
 169                 return TRUE;
 170             if (op_might_modify(the_var, the_for->ub_op()))
 171                 return TRUE;
 172             if (op_might_modify(the_var, the_for->step_op()))
 173                 return TRUE;
 174             if (might_modify(the_var, the_for->body()))
 175                 return TRUE;
 176             return might_modify(the_var, the_for->landing_pad());
 177           }
 178         case TREE_IF:
 179           {
 180             tree_if *the_if = (tree_if *)the_node;
 181             if (might_modify(the_var, the_if->header()))
 182                 return TRUE;
 183             if (might_modify(the_var, the_if->then_part()))
 184                 return TRUE;
 185             return might_modify(the_var, the_if->else_part());
 186           }
 187         case TREE_BLOCK:
 188           {
 189             tree_block *the_block = (tree_block *)the_node;
 190             return might_modify(the_var, the_block->body());
 191           }
 192         default:
 193             assert(FALSE);
 194             return TRUE;
 195       }
 196   }
 197
 198 static boolean expr_might_modify(var_sym *the_var, instruction *the_instr)
 199   {
 200     operand dest_op = the_instr->dst_op();
 201     if (dest_op.is_symbol() && (dest_op.symbol() == the_var))
 202         return TRUE;
 203
 204     switch (the_instr->opcode())
 205       {
 206         case io_cal:
 207             if (!instr_is_impure_call(the_instr))
 208                 break;
 209             /* fall through */
 210         case io_gen:
 211           {
 212             if (!the_var->is_auto())
 213                 return TRUE;
 214
 215             boolean is_fortran = FALSE;
 216             if ((the_instr->owner() != NULL) &&
 217                 (the_instr->owner()->proc()->src_lang() == src_fortran))
 218               {
 219                 is_fortran = TRUE;
 220               }
 221             if (!is_fortran)
 222               {
 223                 if (the_var->root_ancestor()->is_addr_taken())
 224                     return TRUE;
 225               }
 226
 227             unsigned num_srcs = the_instr->num_srcs();
 228             for (unsigned src_num = 0; src_num < num_srcs; ++src_num)
 229               {
 230                 operand this_op = the_instr->src_op(src_num);
 231                 if (this_op.type()->unqual()->is_ptr())
 232                   {
 233                     sym_node *modified_sym =
 234                             operand_address_root_symbol(this_op);
 235                     if ((modified_sym != NULL) && (modified_sym->is_var()))
 236                       {
 237                         var_sym *modified_var = (var_sym *)modified_sym;
 238                         if (modified_var->overlaps(the_var))
 239                             return TRUE;
 240                       }
 241                   }
 242               }
 243             break;
 244           }
 245         case io_str:
 246         case io_memcpy:
 247           {
 248             in_rrr *the_rrr = (in_rrr *)the_instr;
 249             operand dest_addr = the_rrr->dst_addr_op();
 250             sym_node *modified_sym = operand_address_root_symbol(dest_addr);
 251             if (modified_sym != NULL)
 252               {
 253                 if (modified_sym->is_var())
 254                   {
 255                     var_sym *modified_var = (var_sym *)modified_sym;
 256                     if (modified_var->overlaps(the_var))
 257                         return TRUE;
 258                   }
 259               }
 260             else
 261               {
 262                 if (the_var->root_ancestor()->is_addr_taken())
 263                     return TRUE;
 264               }
 265             break;
 266           }
 267         default:
 268             break;
 269       }
 270
 271     unsigned num_srcs = the_instr->num_srcs();
 272     for (unsigned src_num = 0; src_num < num_srcs; ++src_num)
 273       {
 274         if (op_might_modify(the_var, the_instr->src_op(src_num)))
 275             return TRUE;
 276       }
 277
 278     return FALSE;
 279   }
 280
 281 static boolean op_might_modify(var_sym *the_var, operand the_op)
 282   {
 283     if (the_op.is_expr())
 284         return expr_might_modify(the_var, the_op.instr());
 285     else
 286         return FALSE;
 287   }
 288
 289 /*----------------------------------------------------------------------*
 290     End Private Function Implementations
 291  *----------------------------------------------------------------------*/