src/basesuif/useful/estimate.cc

   1 /* file "estimate.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 is the implementation of the rough execution time estimating
  14  * routines for the SUIF ``useful'' library of miscellaneous useful
  15  * routines.
  16  */
  17
  18 #define _MODULE_ "libuseful.a"
  19
  20 #pragma implementation "basic.h"
  21
  22 #define RCS_BASE_FILE estimate_cc
  23
  24 #include "useful_internal.h"
  25
  26 RCS_BASE(
  27     "$Id: estimate.cc,v 1.1.1.1 1998/06/16 15:15:27 brm Exp $")
  28
  29 /*----------------------------------------------------------------------*
  30     Begin Documentation
  31  *----------------------------------------------------------------------*
  32
  33                 Summary
  34                 -------
  35
  36         This file is a place to put general estimation routines for
  37         SUIF.
  38
  39
  40  *----------------------------------------------------------------------*
  41     End Documentation
  42  *----------------------------------------------------------------------*/
  43
  44 #define LOAD_TIME_ESTIMATE           2.0
  45 #define STORE_TIME_ESTIMATE          2.0
  46 #define BRANCH_TIME_ESTIMATE         2.0
  47 #define INT_ALU_ESTIMATE             1.0
  48 #define FP_ADD_ESTIMATE              2.0
  49 #define FP_DIV_ESTIMATE              8.0
  50
  51 #define FUNC_CALL_ESTIMATE        1000.0
  52 #define INTRINSIC_CALL_ESTIMATE     50.0
  53 #define GENERIC_ESTIMATE           100.0
  54
  55 #define LOOP_ITERATIONS_ESTIMATE    100
  56
  57 extern double rough_time_estimate(tree_node_list *the_list)
  58   {
  59     double cost = 0.0;
  60     tree_node_list_iter the_iter(the_list);
  61     while (!the_iter.is_empty())
  62       {
  63         tree_node *this_node = the_iter.step();
  64         cost += rough_time_estimate(this_node);
  65       }
  66     return cost;
  67   }
  68
  69 extern double rough_time_estimate(tree_node *the_node)
  70   {
  71     switch (the_node->kind())
  72       {
  73         case TREE_INSTR:
  74           {
  75             tree_instr *the_tree_instr = (tree_instr *)the_node;
  76             return rough_time_estimate_instr_tree(the_tree_instr->instr());
  77           }
  78         case TREE_LOOP:
  79           {
  80             tree_loop *the_loop = (tree_loop *)the_node;
  81             double body_estimate = rough_time_estimate(the_loop->body());
  82             double test_estimate = rough_time_estimate(the_loop->test());
  83             return ((double) LOOP_ITERATIONS_ESTIMATE) *
  84                              (body_estimate + test_estimate);
  85           }
  86         case TREE_FOR:
  87           {
  88             tree_for *the_for = (tree_for *)the_node;
  89             double landing_pad_est =
  90                 rough_time_estimate(the_for->landing_pad());
  91             double body_estimate = rough_time_estimate(the_for->body());
  92             double init_estimate = rough_time_estimate(the_for->lb_op());
  93             init_estimate += rough_time_estimate(the_for->ub_op());
  94             init_estimate += rough_time_estimate(the_for->step_op());
  95
  96             int lb_int, ub_int, step_int;
  97             boolean lb_is_int, ub_is_int, step_is_int;
  98             lb_is_int = operand_is_int_const(the_for->lb_op(), &lb_int);
  99             ub_is_int = operand_is_int_const(the_for->ub_op(), &ub_int);
 100             step_is_int = operand_is_int_const(the_for->step_op(), &step_int);
 101             int factor = LOOP_ITERATIONS_ESTIMATE;
 102             if (lb_is_int && ub_is_int && step_is_int && (step_int != 0))
 103               {
 104                 factor = (ub_int - lb_int) / step_int;
 105                 if (factor < 0)
 106                     factor = 0;
 107               }
 108             double cost = landing_pad_est + init_estimate +
 109                           (body_estimate * (double) factor);
 110             return (cost);
 111           }
 112         case TREE_IF:
 113           {
 114             tree_if *the_if = (tree_if *)the_node;
 115             double header_estimate = rough_time_estimate(the_if->header());
 116             double then_estimate = rough_time_estimate(the_if->then_part());
 117             double else_estimate = rough_time_estimate(the_if->else_part());
 118             return header_estimate + ((then_estimate + else_estimate) / 2.0);
 119           }
 120         case TREE_BLOCK:
 121           {
 122             tree_block *the_block = (tree_block *)the_node;
 123             return rough_time_estimate(the_block->body());
 124           }
 125         default:
 126             assert(FALSE);
 127             return (0.0);
 128       }
 129   }
 130
 131 extern double rough_time_estimate(operand the_operand)
 132   {
 133     if (the_operand.is_expr())
 134         return rough_time_estimate_instr_tree(the_operand.instr());
 135     else
 136         return (0.0);
 137   }
 138
 139 extern double rough_time_estimate_instr_tree(instruction *the_instr)
 140   {
 141     double cost = 0.0;
 142
 143     unsigned num_srcs = the_instr->num_srcs();
 144     for (unsigned src_num = 0; src_num < num_srcs; ++src_num)
 145         cost += rough_time_estimate(the_instr->src_op(src_num));
 146     return cost + rough_time_estimate_one_instr(the_instr);
 147   }
 148
 149 extern double rough_time_estimate_one_instr(instruction *the_instr)
 150   {
 151     switch (the_instr->opcode())
 152       {
 153         case io_lod:
 154             return LOAD_TIME_ESTIMATE;
 155         case io_str:
 156             return STORE_TIME_ESTIMATE;
 157         case io_seq:
 158         case io_sne:
 159         case io_sl:
 160         case io_sle:
 161           {
 162             in_rrr *the_rrr = (in_rrr *)the_instr;
 163             if (the_rrr->src1_op().type()->unqual()->op() == TYPE_FLOAT)
 164                 return FP_ADD_ESTIMATE;
 165             else
 166                 return INT_ALU_ESTIMATE;
 167           }
 168         case io_btrue:
 169         case io_bfalse:
 170         case io_jmp:
 171         case io_ret:
 172             return BRANCH_TIME_ESTIMATE;
 173         case io_div:
 174         case io_divfloor:
 175         case io_divceil:
 176         case io_rem:
 177         case io_mod:
 178             if (the_instr->result_type()->unqual()->op() == TYPE_FLOAT)
 179                 return FP_DIV_ESTIMATE;
 180             else
 181                 return INT_ALU_ESTIMATE;
 182         case io_lab:
 183         case io_mrk:
 184         case io_nop:
 185             return (0.0);
 186         case io_mbr:
 187             return BRANCH_TIME_ESTIMATE + INT_ALU_ESTIMATE;
 188         case io_cal:
 189           {
 190             in_cal *the_call = (in_cal *)the_instr;
 191             proc_sym *the_proc = proc_for_call(the_call);
 192             if ((the_proc != NULL) &&
 193                 (the_proc->annotes()->peek_annote(k_fortran_intrinsic) !=
 194                  NULL))
 195               {
 196                 return INTRINSIC_CALL_ESTIMATE;
 197               }
 198             return FUNC_CALL_ESTIMATE;
 199           }
 200         case io_gen:
 201             return GENERIC_ESTIMATE;
 202         case io_array:
 203           {
 204             in_array *the_array = (in_array *)the_instr;
 205             if (the_instr->result_type()->unqual()->op() == TYPE_FLOAT)
 206                 return ((double) the_array->dims()) * FP_ADD_ESTIMATE * 2.0;
 207             else
 208                 return ((double) the_array->dims()) * INT_ALU_ESTIMATE * 2.0;
 209           }
 210         case io_memcpy:
 211             return LOAD_TIME_ESTIMATE + STORE_TIME_ESTIMATE;
 212         default:
 213             if (the_instr->result_type()->unqual()->op() == TYPE_FLOAT)
 214                 return FP_ADD_ESTIMATE;
 215             else
 216                 return INT_ALU_ESTIMATE;
 217       }
 218   }
 219
 220