old-autovect-branch/gcc/cv.c

   1 /* Call site versioning
   2    Copyright (C) 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tree.h"
  25 #include "langhooks.h"
  26 #include "ggc.h"
  27 #include "target.h"
  28 #include "cgraph.h"
  29 #include "function.h"
  30 #include "ipa-prop.h"
  31 #include "cfghooks.h"
  32 #include "tree-flow.h"
  33 #include "tree-inline.h"
  34 #include "splay-tree.h"
  35 #include "tree-inline-aux.h"
  36 #include "tree-pass.h"
  37 #include "flags.h"
  38 #include "timevar.h"
  39
  40 typedef struct loop_info
  41 {
  42   basic_block preheader;
  43   basic_block postheader;
  44   basic_block loop_begin;
  45   basic_block loop_end;
  46 } loop_info;
  47
  48 #define SWITCH_BLOCKS_NUM 6
  49 #define DUPLICATE_BLOCKS_NUM 6
  50 typedef struct duplicate_info
  51 {
  52   int n_switch_bb;
  53   basic_block switch_blocks[SWITCH_BLOCKS_NUM];
  54   int n_duplicate_bb;
  55   basic_block duplicate_blocks[DUPLICATE_BLOCKS_NUM];
  56   basic_block merge_block;
  57 } duplicate_info;
  58
  59 bool
  60 type_to_consider (tree type);
  61 bool arg_defined_in_statement_p (tree stmt, tree argument);
  62 bool
  63 has_defs (tree call, basic_block * switch_blocks, int switch_blocks_num);
  64 tree
  65 loop_find_call (struct loop_info *loopinfo);
  66
  67
  68
  69 bool
  70 has_defs (tree call, basic_block * switch_blocks, int switch_blocks_num)
  71 {
  72   int i = 0, j = 0;
  73   tree arg,stmt;
  74   basic_block current;
  75   block_stmt_iterator bsi;
  76   gcc_assert (TREE_CODE (call) == CALL_EXPR);
  77   arg = TREE_OPERAND (call, 1);
  78
  79 /*  fprintf (dump_file, "In has_defs\n");                                                                                           */
  80
  81   for (i = 0; arg != NULL_TREE && i < switch_blocks_num; arg = TREE_CHAIN (arg), i++)
  82     {
  83 /*fprintf (dump_file, "In for. i = %d\n",i);*/
  84
  85
  86       if (type_to_consider (arg))
  87         {
  88           /* fprintf (dump_file, "Exited type to consider!\n");*/
  89           j = 0;
  90           while (j < switch_blocks_num && switch_blocks[j] != NULL)
  91             {
  92
  93               /* fprintf (dump_file, "Reading basic block %d",j); */
  94                current = switch_blocks[j];
  95    /* fprintf (dump_file, "Read %d",j); */
  96               for (bsi = bsi_start (/*switch_blocks[j])*/current); !bsi_end_p (bsi);
  97                    bsi_next (&bsi))
  98                 {
  99 /*                   fprintf (dump_file, "In while's for !\n");                                                                                            */
 100                   stmt = bsi_stmt (bsi);
 101                   if (arg_defined_in_statement_p (stmt, arg))
 102                   {
 103 /*                    fprintf (dump_file, "Found !!!\n"); */
 104                     return true;
 105                   }
 106                 }
 107              j++;
 108             }
 109         }
 110     }
 111     /*fprintf (dump_file, "Exiting !!!\n");                                                                                            */
 112   return false;
 113 }
 114
 115
 116 bool
 117 type_to_consider (tree type)
 118 {
 119 /*   fprintf (dump_file, "In type to consider!\n"); */
 120
 121   /* Strip the *'s off.  */
 122   type = TREE_TYPE(TREE_VALUE(type));
 123  /* while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
 124     type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
 125   */
 126   switch (TREE_CODE (type))
 127     {
 128     case BOOLEAN_TYPE:
 129     case CHAR_TYPE:
 130     case COMPLEX_TYPE:
 131     case ENUMERAL_TYPE:
 132     case INTEGER_TYPE:
 133     case QUAL_UNION_TYPE:
 134     case REAL_TYPE:
 135     case RECORD_TYPE:
 136     case UNION_TYPE:
 137     case VECTOR_TYPE:
 138     case VOID_TYPE:
 139       return true;
 140
 141
 142     default:
 143       return false;
 144     }
 145 }
 146
 147 bool arg_defined_in_statement_p (tree stmt, tree argument)
 148 {
 149         if (TREE_CODE(stmt) == MODIFY_EXPR)
 150                 if (TREE_OPERAND (stmt, 0) == TREE_VALUE(argument))
 151                         return true;
 152         return false;
 153 }
 154
 155 tree
 156 loop_find_call (struct loop_info *loopinfo)
 157 {
 158   basic_block currloop[2], bb = NULL;
 159   int loopnumbb = 2;
 160   int count;
 161   block_stmt_iterator bsi;
 162   tree call, stmt, decl;
 163   currloop[0] = loopinfo->loop_begin;
 164   currloop[1] = loopinfo->loop_end;
 165   /* fprintf (dump_file, "check loop bb %d \n", 4444); */
 166   /*basic_block bb; */
 167   for (count = 0; count < loopnumbb; count++)
 168     {
 169       if ((bb = currloop[count]) != NULL)
 170         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 171           {
 172            /* fprintf (dump_file, "hi check loop bb %d \n", bb->index); */
 173             stmt = bsi_stmt (bsi);
 174             call = get_call_expr_in (stmt);
 175             if (call && (decl = get_callee_fndecl (call)))
 176               {
 177 /*                fprintf (dump_file,"call bb %d \n", bb->index); */
 178                 return call;
 179               }
 180           }
 181     }
 182
 183   return NULL_TREE;
 184 }
 185
 186
 187
 188 static int
 189 check_single_loop (basic_block bb, loop_info *li)
 190 {
 191   edge e;
 192   edge_iterator ei;
 193   basic_block bb1;
 194   int found;
 195
 196   if (dump_file)
 197     fprintf (dump_file, "check loop bb %d \n", bb->index);
 198
 199   if (EDGE_COUNT (bb->succs) != 2)
 200     return 0;
 201   found = 0;
 202   FOR_EACH_EDGE (e, ei, bb->succs)
 203     {
 204       bb1 = e->dest;
 205       if (!bb1)
 206         continue;
 207       if (dump_file)
 208         fprintf (dump_file, "check succs bb1 %d \n", bb1->index);
 209
 210       if ((EDGE_COUNT (bb1->preds) != 1) ||
 211           (EDGE_COUNT (bb1->succs) != 1) ||
 212           (EDGE_SUCC (bb1, 0)->dest) != bb )
 213         {
 214           li->postheader = bb1;
 215           continue;
 216         }
 217
 218
 219       if (found)
 220         return 0;
 221
 222       li->loop_begin = bb;
 223       li->loop_end = bb1;
 224       found = 1;
 225     }
 226
 227   if (!found)
 228     return 0;
 229
 230   if (!li->postheader)
 231     return 0;
 232
 233   if (dump_file)
 234     {
 235       fprintf (dump_file, "postheader %d\n", li->postheader->index);
 236       fprintf (dump_file, "header %d\n", li->loop_begin->index);
 237       fprintf (dump_file, "latch %d\n", li->loop_end->index);
 238     }
 239
 240   if (EDGE_COUNT (bb->preds) != 2)
 241       return 0;
 242   FOR_EACH_EDGE (e, ei, bb->preds)
 243     {
 244       bb1 = e->src;
 245       if (!bb1 ||
 246           (bb1 == li->loop_end))
 247         continue;
 248
 249       if (li->preheader)
 250         return 0;
 251       li->preheader = bb1;
 252     }
 253
 254   if (!li->preheader ||
 255       EDGE_COUNT (li->preheader->preds) < 2 ||
 256       EDGE_COUNT (li->preheader->succs) != 1)
 257     return 0;
 258
 259   if (dump_file)
 260     fprintf (dump_file, "prehader %d\n", li->preheader->index);
 261
 262   if (li->preheader->next_bb != li->loop_end ||
 263       li->loop_end->next_bb != li->loop_begin ||
 264       li->loop_begin->next_bb != li->postheader)
 265     return 0;
 266
 267   return found;
 268 }
 269
 270 static int
 271 find_switch_blocks (loop_info *li, duplicate_info *di)
 272 {
 273   edge e;
 274   edge_iterator ei;
 275   basic_block bb1;
 276   int i;
 277
 278   bb1 = li->preheader;
 279   i = 0;
 280   FOR_EACH_EDGE (e, ei, bb1->preds)
 281     {
 282       if (i >= SWITCH_BLOCKS_NUM)
 283         return 0;
 284       if (EDGE_COUNT (e->src->succs) != 1)
 285         continue;
 286       di->switch_blocks[i++] = e->src;
 287     }
 288   if (!i)
 289     return 0;
 290   di->n_switch_bb = i;
 291
 292
 293   i = 0;
 294   di->duplicate_blocks[i++] = bb1;
 295   di->duplicate_blocks[i++] = li->loop_end;
 296   di->duplicate_blocks[i++] = li->loop_begin;
 297   di->n_duplicate_bb = i;
 298
 299   if (dump_file)
 300     {
 301       for (i = 0; i < di->n_switch_bb; i++)
 302         fprintf (dump_file, "switch %d\n",di->switch_blocks[i]->index);
 303       for (i = 0; i < di->n_duplicate_bb; i++)
 304         fprintf (dump_file, "duplicate %d\n",di->duplicate_blocks[i]->index);
 305     }
 306
 307   /*  di->merge_block = di->duplicate_blocks [di->n_duplicate_bb - 1]->next_bb; remove after CHECK */
 308   di->merge_block = li->postheader;
 309
 310 #if 0
 311   for (i = 0; i < di->n_switch_bb; i++)
 312     {
 313       edge e;
 314       block_stmt_iterator bsi;
 315
 316       bsi = bsi_last (di->switch_blocks[i]);
 317
 318       /* enable after CHECK.
 319       tree goto_stmt;
 320       goto_stmt = bsi_stmt (bsi);
 321       if (TREE_CODE (goto_stmt) == GOTO_EXPR)
 322          return 0;;
 323          bsi_prev (&bsi); */
 324       e = split_block (di->switch_blocks[i], bsi_stmt (bsi));
 325     }
 326 #endif
 327
 328   return 1;
 329 }
 330
 331 static void
 332 duplicate_code_path (duplicate_info *di, int index, inline_data *id)
 333 {
 334   gcov_type count_scale;
 335   int frequency_scale;
 336   int j;
 337   splay_tree st;
 338   basic_block after_switch;
 339
 340   if (dump_file)
 341     fprintf (dump_file, "path %d\n", di->switch_blocks[index]->index);
 342   count_scale = 1;
 343   if (di->switch_blocks[index]->count)
 344     count_scale = (REG_BR_PROB_BASE * count_scale
 345                    / di->switch_blocks[index]->count);
 346
 347   frequency_scale = 1;
 348   if (di->switch_blocks[index]->frequency)
 349     frequency_scale = (REG_BR_PROB_BASE * frequency_scale
 350                    / di->switch_blocks[index]->frequency);
 351
 352   di->duplicate_blocks [0]->prev_bb->aux = di->switch_blocks [index];
 353   di->duplicate_blocks [di->n_duplicate_bb - 1]->next_bb->aux =
 354     EDGE_SUCC (di->switch_blocks [index], 0)->dest;
 355
 356   st = id->decl_map;
 357   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
 358                                  NULL, NULL);
 359
 360   /* CHECK lang_hooks.tree_inlining.auto_var_in_fn_p */
 361   for (j = 0; j < di->n_duplicate_bb; j++)
 362     {
 363       if (dump_file)
 364         fprintf (dump_file, "copy bb %d\n", di->duplicate_blocks[j]->index);
 365       di->duplicate_blocks [j]->aux =
 366         copy_bb (id, di->duplicate_blocks [j], frequency_scale, count_scale);
 367       if (dump_file)
 368         fprintf (dump_file, "duplicate bb %d\n", ((basic_block) (di->duplicate_blocks[j]->aux))->index);
 369     }
 370
 371   for (j = 0; j < di->n_duplicate_bb; j++)
 372     {
 373       if (dump_file)
 374         fprintf (dump_file, "edges bb %d\n", di->duplicate_blocks[j]->index);
 375
 376       copy_edges_for_bb (di->duplicate_blocks [j], count_scale);
 377     }
 378
 379   after_switch = EDGE_SUCC (di->switch_blocks [index], 0)->dest;
 380   redirect_edge_succ (EDGE_SUCC (di->switch_blocks [index], 0),
 381                       di->duplicate_blocks [0]->aux);
 382   /* EDGE_SUCC (after_switch, 0)->flags &= ~EDGE_FALLTHRU; CHECK */
 383   redirect_edge_succ (EDGE_SUCC (after_switch, 0),
 384                       di->duplicate_blocks [di->n_duplicate_bb - 1]->next_bb);
 385   for (j = 0; j < di->n_duplicate_bb; j++)
 386     di->duplicate_blocks [j]->aux = NULL;
 387   di->duplicate_blocks [0]->prev_bb->aux = NULL;
 388   di->duplicate_blocks [di->n_duplicate_bb - 1]->next_bb->aux = NULL;
 389
 390   splay_tree_delete (id->decl_map);
 391   id->decl_map = st;
 392 }
 393
 394 static void
 395 duplicate_code (duplicate_info *di, inline_data *id, struct function *cfun)
 396 {
 397   int i;
 398
 399 #if 1
 400   for (i = 0; i < di->n_switch_bb; i++)
 401     {
 402       edge e;
 403       block_stmt_iterator bsi;
 404
 405       bsi = bsi_last (di->switch_blocks[i]);
 406
 407       /* enable after CHECK.
 408       tree goto_stmt;
 409       goto_stmt = bsi_stmt (bsi);
 410       if (TREE_CODE (goto_stmt) == GOTO_EXPR)
 411          return 0;;
 412          bsi_prev (&bsi); */
 413       e = split_block (di->switch_blocks[i], bsi_stmt (bsi));
 414     }
 415 #endif
 416
 417   id->current_node = id->node = cgraph_node (current_function_decl);
 418   id->caller = id->callee = current_function_decl;
 419   id->callee_cfun = cfun;
 420   id->eh_region_offset = 0;
 421   id->eh_region = 0;
 422   id->versioning_p = 1;
 423   id->saving_p = 0;
 424   id->cloning_p = 0;
 425   id->ipa_info = 0;
 426   id->block = NULL;
 427   id->copybb_only_p = 1;
 428   for (i = 0; i < di->n_switch_bb; i++)
 429     duplicate_code_path (di, i, id);
 430 }
 431
 432 static void
 433 callsite_versioning (struct function *cfun)
 434 {
 435   basic_block bb;
 436   loop_info li;
 437   duplicate_info di;
 438   int found, check;
 439   inline_data id;
 440   tree call_insn;
 441
 442
 443   /*  printf ("enter callsite versioning \n"); */
 444   FOR_EACH_BB (bb)
 445     {
 446       li.preheader = NULL;
 447       li.loop_begin = NULL;
 448       li.loop_end = NULL;
 449       li.postheader = NULL;
 450       found = check_single_loop (bb, &li) ;
 451       if (!found)
 452         continue;
 453       if (dump_file)
 454         fprintf (dump_file, "***loop info*** \n");
 455
 456       di.n_switch_bb = 0;
 457       di.n_duplicate_bb = 0;
 458       di.merge_block = NULL;
 459       check = find_switch_blocks (&li, &di);
 460       if (!check)
 461         continue;
 462       if (dump_file)
 463         fprintf (dump_file, "***duplicate info*** \n");
 464
 465       call_insn =  loop_find_call (&li) ;
 466       if (call_insn == NULL_TREE ) continue;
 467       else
 468           if(has_defs (call_insn, di.switch_blocks,  di.n_switch_bb))
 469           {
 470             /* fprintf (dump_file, "Ura! Check passed \n");  */
 471             memset (&id, 0, sizeof (id));
 472             duplicate_code (&di, &id, cfun);
 473             if (dump_file)
 474               fprintf (dump_file, "***success*** \n");
 475           }
 476           /*else fprintf (dump_file, "Noooo! \n"); */
 477
 478 /*      int_args = call_find_args (call_insn); */
 479       /* if (has_defs (di.switch_blocks, int_args)) */
 480     }
 481 /*  printf ("exit callsite versioning \n"); */
 482 }
 483
 484 void
 485 cv_driver (void)
 486 {
 487   struct cgraph_node *node;
 488
 489   /*  printf("enter cv \n"); */
 490   for (node = cgraph_nodes; node; node = node->next)
 491     {
 492       tree temp_fn;
 493
 494       if (DECL_SAVED_TREE (node->decl) == NULL)
 495         continue;
 496
 497       if (!node->lowered)
 498         continue;
 499
 500       temp_fn = current_function_decl;
 501       current_function_decl = node->decl;
 502       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
 503       /*      bitmap_obstack_initialize (NULL); */
 504       tree_register_cfg_hooks ();
 505       callsite_versioning (DECL_STRUCT_FUNCTION (node->decl));
 506       free_dominance_info (CDI_DOMINATORS);
 507       free_dominance_info (CDI_POST_DOMINATORS);
 508       pop_cfun ();
 509       current_function_decl = temp_fn;
 510     }
 511   /*  printf("exit cv \n"); */
 512 }
 513
 514 /* Gate for the call versionin ogptimization.  */
 515 static bool
 516 cgraph_gate_cv (void)
 517 {
 518   return flag_cv;
 519 }
 520
 521 struct tree_opt_pass pass_cv = {
 522   "cv",                         /* name */
 523   cgraph_gate_cv,               /* gate */
 524   cv_driver,                    /* execute */
 525   NULL,                         /* sub */
 526   NULL,                         /* next */
 527   0,                            /* static_pass_number */
 528   TV_CV,                        /* tv_id */
 529   0,                            /* properties_required */
 530   PROP_trees,                   /* properties_provided */
 531   0,                            /* properties_destroyed */
 532   0,                            /* todo_flags_start */
 533   TODO_dump_func,               /* todo_flags_finish */
 534   0                             /* letter */
 535 };