1 /* Read and annotate call graph profile from the auto profile data file. 2 Copyright (C) 2014-2018 Free Software Foundation, Inc. 3 Contributed by Dehao Chen (dehao@google.com) 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #define INCLUDE_MAP 23 #define INCLUDE_SET 24 #include "system.h" 25 #include "coretypes.h" 26 #include "backend.h" 27 #include "tree.h" 28 #include "gimple.h" 29 #include "predict.h" 30 #include "alloc-pool.h" 31 #include "tree-pass.h" 32 #include "ssa.h" 33 #include "cgraph.h" 34 #include "gcov-io.h" 35 #include "diagnostic-core.h" 36 #include "profile.h" 37 #include "langhooks.h" 38 #include "cfgloop.h" 39 #include "tree-cfg.h" 40 #include "tree-cfgcleanup.h" 41 #include "tree-into-ssa.h" 42 #include "gimple-iterator.h" 43 #include "value-prof.h" 44 #include "params.h" 45 #include "symbol-summary.h" 46 #include "ipa-prop.h" 47 #include "ipa-fnsummary.h" 48 #include "ipa-inline.h" 49 #include "tree-inline.h" 50 #include "auto-profile.h" 51 #include "tree-pretty-print.h" 52 #include "gimple-pretty-print.h" 53 54 /* The following routines implements AutoFDO optimization. 55 56 This optimization uses sampling profiles to annotate basic block counts 57 and uses heuristics to estimate branch probabilities. 58 59 There are three phases in AutoFDO: 60 61 Phase 1: Read profile from the profile data file. 62 The following info is read from the profile datafile: 63 * string_table: a map between function name and its index. 64 * autofdo_source_profile: a map from function_instance name to 65 function_instance. This is represented as a forest of 66 function_instances. 67 * WorkingSet: a histogram of how many instructions are covered for a 68 given percentage of total cycles. This is describing the binary 69 level information (not source level). This info is used to help 70 decide if we want aggressive optimizations that could increase 71 code footprint (e.g. loop unroll etc.) 72 A function instance is an instance of function that could either be a 73 standalone symbol, or a clone of a function that is inlined into another 74 function. 75 76 Phase 2: Early inline + value profile transformation. 77 Early inline uses autofdo_source_profile to find if a callsite is: 78 * inlined in the profiled binary. 79 * callee body is hot in the profiling run. 80 If both condition satisfies, early inline will inline the callsite 81 regardless of the code growth. 82 Phase 2 is an iterative process. During each iteration, we also check 83 if an indirect callsite is promoted and inlined in the profiling run. 84 If yes, vpt will happen to force promote it and in the next iteration, 85 einline will inline the promoted callsite in the next iteration. 86 87 Phase 3: Annotate control flow graph. 88 AutoFDO uses a separate pass to: 89 * Annotate basic block count 90 * Estimate branch probability 91 92 After the above 3 phases, all profile is readily annotated on the GCC IR. 93 AutoFDO tries to reuse all FDO infrastructure as much as possible to make 94 use of the profile. E.g. it uses existing mechanism to calculate the basic 95 block/edge frequency, as well as the cgraph node/edge count. 96 */ 97 98 #define DEFAULT_AUTO_PROFILE_FILE "fbdata.afdo" 99 #define AUTO_PROFILE_VERSION 1 100 101 namespace autofdo 102 { 103 104 /* Represent a source location: (function_decl, lineno). */ 105 typedef std::pair<tree, unsigned> decl_lineno; 106 107 /* Represent an inline stack. vector[0] is the leaf node. */ 108 typedef auto_vec<decl_lineno> inline_stack; 109 110 /* String array that stores function names. */ 111 typedef auto_vec<char *> string_vector; 112 113 /* Map from function name's index in string_table to target's 114 execution count. */ 115 typedef std::map<unsigned, gcov_type> icall_target_map; 116 117 /* Set of gimple stmts. Used to track if the stmt has already been promoted 118 to direct call. */ 119 typedef std::set<gimple *> stmt_set; 120 121 /* Represent count info of an inline stack. */ 122 struct count_info 123 { 124 /* Sampled count of the inline stack. */ 125 gcov_type count; 126 127 /* Map from indirect call target to its sample count. */ 128 icall_target_map targets; 129 130 /* Whether this inline stack is already used in annotation. 131 132 Each inline stack should only be used to annotate IR once. 133 This will be enforced when instruction-level discriminator 134 is supported. */ 135 bool annotated; 136 }; 137 138 /* operator< for "const char *". */ 139 struct string_compare 140 { 141 bool operator()(const char *a, const char *b) const 142 { 143 return strcmp (a, b) < 0; 144 } 145 }; 146 147 /* Store a string array, indexed by string position in the array. */ 148 class string_table 149 { 150 public: 151 string_table () 152 {} 153 154 ~string_table (); 155 156 /* For a given string, returns its index. */ 157 int get_index (const char *name) const; 158 159 /* For a given decl, returns the index of the decl name. */ 160 int get_index_by_decl (tree decl) const; 161 162 /* For a given index, returns the string. */ 163 const char *get_name (int index) const; 164 165 /* Read profile, return TRUE on success. */ 166 bool read (); 167 168 private: 169 typedef std::map<const char *, unsigned, string_compare> string_index_map; 170 string_vector vector_; 171 string_index_map map_; 172 }; 173 174 /* Profile of a function instance: 175 1. total_count of the function. 176 2. head_count (entry basic block count) of the function (only valid when 177 function is a top-level function_instance, i.e. it is the original copy 178 instead of the inlined copy). 179 3. map from source location (decl_lineno) to profile (count_info). 180 4. map from callsite to callee function_instance. */ 181 class function_instance 182 { 183 public: 184 typedef auto_vec<function_instance *> function_instance_stack; 185 186 /* Read the profile and return a function_instance with head count as 187 HEAD_COUNT. Recursively read callsites to create nested function_instances 188 too. STACK is used to track the recursive creation process. */ 189 static function_instance * 190 read_function_instance (function_instance_stack *stack, 191 gcov_type head_count); 192 193 /* Recursively deallocate all callsites (nested function_instances). */ 194 ~function_instance (); 195 196 /* Accessors. */ 197 int 198 name () const 199 { 200 return name_; 201 } 202 gcov_type 203 total_count () const 204 { 205 return total_count_; 206 } 207 gcov_type 208 head_count () const 209 { 210 return head_count_; 211 } 212 213 /* Traverse callsites of the current function_instance to find one at the 214 location of LINENO and callee name represented in DECL. */ 215 function_instance *get_function_instance_by_decl (unsigned lineno, 216 tree decl) const; 217 218 /* Store the profile info for LOC in INFO. Return TRUE if profile info 219 is found. */ 220 bool get_count_info (location_t loc, count_info *info) const; 221 222 /* Read the inlined indirect call target profile for STMT and store it in 223 MAP, return the total count for all inlined indirect calls. */ 224 gcov_type find_icall_target_map (gcall *stmt, icall_target_map *map) const; 225 226 /* Sum of counts that is used during annotation. */ 227 gcov_type total_annotated_count () const; 228 229 /* Mark LOC as annotated. */ 230 void mark_annotated (location_t loc); 231 232 private: 233 /* Callsite, represented as (decl_lineno, callee_function_name_index). */ 234 typedef std::pair<unsigned, unsigned> callsite; 235 236 /* Map from callsite to callee function_instance. */ 237 typedef std::map<callsite, function_instance *> callsite_map; 238 239 function_instance (unsigned name, gcov_type head_count) 240 : name_ (name), total_count_ (0), head_count_ (head_count) 241 { 242 } 243 244 /* Map from source location (decl_lineno) to profile (count_info). */ 245 typedef std::map<unsigned, count_info> position_count_map; 246 247 /* function_instance name index in the string_table. */ 248 unsigned name_; 249 250 /* Total sample count. */ 251 gcov_type total_count_; 252 253 /* Entry BB's sample count. */ 254 gcov_type head_count_; 255 256 /* Map from callsite location to callee function_instance. */ 257 callsite_map callsites; 258 259 /* Map from source location to count_info. */ 260 position_count_map pos_counts; 261 }; 262 263 /* Profile for all functions. */ 264 class autofdo_source_profile 265 { 266 public: 267 static autofdo_source_profile * 268 create () 269 { 270 autofdo_source_profile *map = new autofdo_source_profile (); 271 272 if (map->read ()) 273 return map; 274 delete map; 275 return NULL; 276 } 277 278 ~autofdo_source_profile (); 279 280 /* For a given DECL, returns the top-level function_instance. */ 281 function_instance *get_function_instance_by_decl (tree decl) const; 282 283 /* Find count_info for a given gimple STMT. If found, store the count_info 284 in INFO and return true; otherwise return false. */ 285 bool get_count_info (gimple *stmt, count_info *info) const; 286 287 /* Find total count of the callee of EDGE. */ 288 gcov_type get_callsite_total_count (struct cgraph_edge *edge) const; 289 290 /* Update value profile INFO for STMT from the inlined indirect callsite. 291 Return true if INFO is updated. */ 292 bool update_inlined_ind_target (gcall *stmt, count_info *info); 293 294 /* Mark LOC as annotated. */ 295 void mark_annotated (location_t loc); 296 297 private: 298 /* Map from function_instance name index (in string_table) to 299 function_instance. */ 300 typedef std::map<unsigned, function_instance *> name_function_instance_map; 301 302 autofdo_source_profile () {} 303 304 /* Read AutoFDO profile and returns TRUE on success. */ 305 bool read (); 306 307 /* Return the function_instance in the profile that correspond to the 308 inline STACK. */ 309 function_instance * 310 get_function_instance_by_inline_stack (const inline_stack &stack) const; 311 312 name_function_instance_map map_; 313 }; 314 315 /* Store the strings read from the profile data file. */ 316 static string_table *afdo_string_table; 317 318 /* Store the AutoFDO source profile. */ 319 static autofdo_source_profile *afdo_source_profile; 320 321 /* gcov_ctr_summary structure to store the profile_info. */ 322 static struct gcov_ctr_summary *afdo_profile_info; 323 324 /* Helper functions. */ 325 326 /* Return the original name of NAME: strip the suffix that starts 327 with '.' Caller is responsible for freeing RET. */ 328 329 static char * 330 get_original_name (const char *name) 331 { 332 char *ret = xstrdup (name); 333 char *find = strchr (ret, '.'); 334 if (find != NULL) 335 *find = 0; 336 return ret; 337 } 338 339 /* Return the combined location, which is a 32bit integer in which 340 higher 16 bits stores the line offset of LOC to the start lineno 341 of DECL, The lower 16 bits stores the discriminator. */ 342 343 static unsigned 344 get_combined_location (location_t loc, tree decl) 345 { 346 /* TODO: allow more bits for line and less bits for discriminator. */ 347 if (LOCATION_LINE (loc) - DECL_SOURCE_LINE (decl) >= (1<<16)) 348 warning_at (loc, OPT_Woverflow, "offset exceeds 16 bytes"); 349 return ((LOCATION_LINE (loc) - DECL_SOURCE_LINE (decl)) << 16); 350 } 351 352 /* Return the function decl of a given lexical BLOCK. */ 353 354 static tree 355 get_function_decl_from_block (tree block) 356 { 357 tree decl; 358 359 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (block)) == UNKNOWN_LOCATION) 360 return NULL_TREE; 361 362 for (decl = BLOCK_ABSTRACT_ORIGIN (block); 363 decl && (TREE_CODE (decl) == BLOCK); 364 decl = BLOCK_ABSTRACT_ORIGIN (decl)) 365 if (TREE_CODE (decl) == FUNCTION_DECL) 366 break; 367 return decl; 368 } 369 370 /* Store inline stack for STMT in STACK. */ 371 372 static void 373 get_inline_stack (location_t locus, inline_stack *stack) 374 { 375 if (LOCATION_LOCUS (locus) == UNKNOWN_LOCATION) 376 return; 377 378 tree block = LOCATION_BLOCK (locus); 379 if (block && TREE_CODE (block) == BLOCK) 380 { 381 int level = 0; 382 for (block = BLOCK_SUPERCONTEXT (block); 383 block && (TREE_CODE (block) == BLOCK); 384 block = BLOCK_SUPERCONTEXT (block)) 385 { 386 location_t tmp_locus = BLOCK_SOURCE_LOCATION (block); 387 if (LOCATION_LOCUS (tmp_locus) == UNKNOWN_LOCATION) 388 continue; 389 390 tree decl = get_function_decl_from_block (block); 391 stack->safe_push ( 392 std::make_pair (decl, get_combined_location (locus, decl))); 393 locus = tmp_locus; 394 level++; 395 } 396 } 397 stack->safe_push ( 398 std::make_pair (current_function_decl, 399 get_combined_location (locus, current_function_decl))); 400 } 401 402 /* Return STMT's combined location, which is a 32bit integer in which 403 higher 16 bits stores the line offset of LOC to the start lineno 404 of DECL, The lower 16 bits stores the discriminator. */ 405 406 static unsigned 407 get_relative_location_for_stmt (gimple *stmt) 408 { 409 location_t locus = gimple_location (stmt); 410 if (LOCATION_LOCUS (locus) == UNKNOWN_LOCATION) 411 return UNKNOWN_LOCATION; 412 413 for (tree block = gimple_block (stmt); block && (TREE_CODE (block) == BLOCK); 414 block = BLOCK_SUPERCONTEXT (block)) 415 if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (block)) != UNKNOWN_LOCATION) 416 return get_combined_location (locus, 417 get_function_decl_from_block (block)); 418 return get_combined_location (locus, current_function_decl); 419 } 420 421 /* Return true if BB contains indirect call. */ 422 423 static bool 424 has_indirect_call (basic_block bb) 425 { 426 gimple_stmt_iterator gsi; 427 428 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 429 { 430 gimple *stmt = gsi_stmt (gsi); 431 if (gimple_code (stmt) == GIMPLE_CALL && !gimple_call_internal_p (stmt) 432 && (gimple_call_fn (stmt) == NULL 433 || TREE_CODE (gimple_call_fn (stmt)) != FUNCTION_DECL)) 434 return true; 435 } 436 return false; 437 } 438 439 /* Member functions for string_table. */ 440 441 /* Deconstructor. */ 442 443 string_table::~string_table () 444 { 445 for (unsigned i = 0; i < vector_.length (); i++) 446 free (vector_[i]); 447 } 448 449 450 /* Return the index of a given function NAME. Return -1 if NAME is not 451 found in string table. */ 452 453 int 454 string_table::get_index (const char *name) const 455 { 456 if (name == NULL) 457 return -1; 458 string_index_map::const_iterator iter = map_.find (name); 459 if (iter == map_.end ()) 460 return -1; 461 462 return iter->second; 463 } 464 465 /* Return the index of a given function DECL. Return -1 if DECL is not 466 found in string table. */ 467 468 int 469 string_table::get_index_by_decl (tree decl) const 470 { 471 char *name 472 = get_original_name (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl))); 473 int ret = get_index (name); 474 free (name); 475 if (ret != -1) 476 return ret; 477 ret = get_index (lang_hooks.dwarf_name (decl, 0)); 478 if (ret != -1) 479 return ret; 480 if (DECL_ABSTRACT_ORIGIN (decl) && DECL_ABSTRACT_ORIGIN (decl) != decl) 481 return get_index_by_decl (DECL_ABSTRACT_ORIGIN (decl)); 482 483 return -1; 484 } 485 486 /* Return the function name of a given INDEX. */ 487 488 const char * 489 string_table::get_name (int index) const 490 { 491 gcc_assert (index > 0 && index < (int)vector_.length ()); 492 return vector_[index]; 493 } 494 495 /* Read the string table. Return TRUE if reading is successful. */ 496 497 bool 498 string_table::read () 499 { 500 if (gcov_read_unsigned () != GCOV_TAG_AFDO_FILE_NAMES) 501 return false; 502 /* Skip the length of the section. */ 503 gcov_read_unsigned (); 504 /* Read in the file name table. */ 505 unsigned string_num = gcov_read_unsigned (); 506 for (unsigned i = 0; i < string_num; i++) 507 { 508 vector_.safe_push (get_original_name (gcov_read_string ())); 509 map_[vector_.last ()] = i; 510 } 511 return true; 512 } 513 514 /* Member functions for function_instance. */ 515 516 function_instance::~function_instance () 517 { 518 for (callsite_map::iterator iter = callsites.begin (); 519 iter != callsites.end (); ++iter) 520 delete iter->second; 521 } 522 523 /* Traverse callsites of the current function_instance to find one at the 524 location of LINENO and callee name represented in DECL. */ 525 526 function_instance * 527 function_instance::get_function_instance_by_decl (unsigned lineno, 528 tree decl) const 529 { 530 int func_name_idx = afdo_string_table->get_index_by_decl (decl); 531 if (func_name_idx != -1) 532 { 533 callsite_map::const_iterator ret 534 = callsites.find (std::make_pair (lineno, func_name_idx)); 535 if (ret != callsites.end ()) 536 return ret->second; 537 } 538 func_name_idx 539 = afdo_string_table->get_index (lang_hooks.dwarf_name (decl, 0)); 540 if (func_name_idx != -1) 541 { 542 callsite_map::const_iterator ret 543 = callsites.find (std::make_pair (lineno, func_name_idx)); 544 if (ret != callsites.end ()) 545 return ret->second; 546 } 547 if (DECL_ABSTRACT_ORIGIN (decl)) 548 return get_function_instance_by_decl (lineno, DECL_ABSTRACT_ORIGIN (decl)); 549 550 return NULL; 551 } 552 553 /* Store the profile info for LOC in INFO. Return TRUE if profile info 554 is found. */ 555 556 bool 557 function_instance::get_count_info (location_t loc, count_info *info) const 558 { 559 position_count_map::const_iterator iter = pos_counts.find (loc); 560 if (iter == pos_counts.end ()) 561 return false; 562 *info = iter->second; 563 return true; 564 } 565 566 /* Mark LOC as annotated. */ 567 568 void 569 function_instance::mark_annotated (location_t loc) 570 { 571 position_count_map::iterator iter = pos_counts.find (loc); 572 if (iter == pos_counts.end ()) 573 return; 574 iter->second.annotated = true; 575 } 576 577 /* Read the inlined indirect call target profile for STMT and store it in 578 MAP, return the total count for all inlined indirect calls. */ 579 580 gcov_type 581 function_instance::find_icall_target_map (gcall *stmt, 582 icall_target_map *map) const 583 { 584 gcov_type ret = 0; 585 unsigned stmt_offset = get_relative_location_for_stmt (stmt); 586 587 for (callsite_map::const_iterator iter = callsites.begin (); 588 iter != callsites.end (); ++iter) 589 { 590 unsigned callee = iter->second->name (); 591 /* Check if callsite location match the stmt. */ 592 if (iter->first.first != stmt_offset) 593 continue; 594 struct cgraph_node *node = cgraph_node::get_for_asmname ( 595 get_identifier (afdo_string_table->get_name (callee))); 596 if (node == NULL) 597 continue; 598 if (!check_ic_target (stmt, node)) 599 continue; 600 (*map)[callee] = iter->second->total_count (); 601 ret += iter->second->total_count (); 602 } 603 return ret; 604 } 605 606 /* Read the profile and create a function_instance with head count as 607 HEAD_COUNT. Recursively read callsites to create nested function_instances 608 too. STACK is used to track the recursive creation process. */ 609 610 /* function instance profile format: 611 612 ENTRY_COUNT: 8 bytes 613 NAME_INDEX: 4 bytes 614 NUM_POS_COUNTS: 4 bytes 615 NUM_CALLSITES: 4 byte 616 POS_COUNT_1: 617 POS_1_OFFSET: 4 bytes 618 NUM_TARGETS: 4 bytes 619 COUNT: 8 bytes 620 TARGET_1: 621 VALUE_PROFILE_TYPE: 4 bytes 622 TARGET_IDX: 8 bytes 623 COUNT: 8 bytes 624 TARGET_2 625 ... 626 TARGET_n 627 POS_COUNT_2 628 ... 629 POS_COUNT_N 630 CALLSITE_1: 631 CALLSITE_1_OFFSET: 4 bytes 632 FUNCTION_INSTANCE_PROFILE (nested) 633 CALLSITE_2 634 ... 635 CALLSITE_n. */ 636 637 function_instance * 638 function_instance::read_function_instance (function_instance_stack *stack, 639 gcov_type head_count) 640 { 641 unsigned name = gcov_read_unsigned (); 642 unsigned num_pos_counts = gcov_read_unsigned (); 643 unsigned num_callsites = gcov_read_unsigned (); 644 function_instance *s = new function_instance (name, head_count); 645 stack->safe_push (s); 646 647 for (unsigned i = 0; i < num_pos_counts; i++) 648 { 649 unsigned offset = gcov_read_unsigned () & 0xffff0000; 650 unsigned num_targets = gcov_read_unsigned (); 651 gcov_type count = gcov_read_counter (); 652 s->pos_counts[offset].count = count; 653 for (unsigned j = 0; j < stack->length (); j++) 654 (*stack)[j]->total_count_ += count; 655 for (unsigned j = 0; j < num_targets; j++) 656 { 657 /* Only indirect call target histogram is supported now. */ 658 gcov_read_unsigned (); 659 gcov_type target_idx = gcov_read_counter (); 660 s->pos_counts[offset].targets[target_idx] = gcov_read_counter (); 661 } 662 } 663 for (unsigned i = 0; i < num_callsites; i++) 664 { 665 unsigned offset = gcov_read_unsigned (); 666 function_instance *callee_function_instance 667 = read_function_instance (stack, 0); 668 s->callsites[std::make_pair (offset, callee_function_instance->name ())] 669 = callee_function_instance; 670 } 671 stack->pop (); 672 return s; 673 } 674 675 /* Sum of counts that is used during annotation. */ 676 677 gcov_type 678 function_instance::total_annotated_count () const 679 { 680 gcov_type ret = 0; 681 for (callsite_map::const_iterator iter = callsites.begin (); 682 iter != callsites.end (); ++iter) 683 ret += iter->second->total_annotated_count (); 684 for (position_count_map::const_iterator iter = pos_counts.begin (); 685 iter != pos_counts.end (); ++iter) 686 if (iter->second.annotated) 687 ret += iter->second.count; 688 return ret; 689 } 690 691 /* Member functions for autofdo_source_profile. */ 692 693 autofdo_source_profile::~autofdo_source_profile () 694 { 695 for (name_function_instance_map::const_iterator iter = map_.begin (); 696 iter != map_.end (); ++iter) 697 delete iter->second; 698 } 699 700 /* For a given DECL, returns the top-level function_instance. */ 701 702 function_instance * 703 autofdo_source_profile::get_function_instance_by_decl (tree decl) const 704 { 705 int index = afdo_string_table->get_index_by_decl (decl); 706 if (index == -1) 707 return NULL; 708 name_function_instance_map::const_iterator ret = map_.find (index); 709 return ret == map_.end () ? NULL : ret->second; 710 } 711 712 /* Find count_info for a given gimple STMT. If found, store the count_info 713 in INFO and return true; otherwise return false. */ 714 715 bool 716 autofdo_source_profile::get_count_info (gimple *stmt, count_info *info) const 717 { 718 if (LOCATION_LOCUS (gimple_location (stmt)) == cfun->function_end_locus) 719 return false; 720 721 inline_stack stack; 722 get_inline_stack (gimple_location (stmt), &stack); 723 if (stack.length () == 0) 724 return false; 725 function_instance *s = get_function_instance_by_inline_stack (stack); 726 if (s == NULL) 727 return false; 728 return s->get_count_info (stack[0].second, info); 729 } 730 731 /* Mark LOC as annotated. */ 732 733 void 734 autofdo_source_profile::mark_annotated (location_t loc) 735 { 736 inline_stack stack; 737 get_inline_stack (loc, &stack); 738 if (stack.length () == 0) 739 return; 740 function_instance *s = get_function_instance_by_inline_stack (stack); 741 if (s == NULL) 742 return; 743 s->mark_annotated (stack[0].second); 744 } 745 746 /* Update value profile INFO for STMT from the inlined indirect callsite. 747 Return true if INFO is updated. */ 748 749 bool 750 autofdo_source_profile::update_inlined_ind_target (gcall *stmt, 751 count_info *info) 752 { 753 if (dump_file) 754 { 755 fprintf (dump_file, "Checking indirect call -> direct call "); 756 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 757 } 758 759 if (LOCATION_LOCUS (gimple_location (stmt)) == cfun->function_end_locus) 760 { 761 if (dump_file) 762 fprintf (dump_file, " good locus\n"); 763 return false; 764 } 765 766 count_info old_info; 767 get_count_info (stmt, &old_info); 768 gcov_type total = 0; 769 for (icall_target_map::const_iterator iter = old_info.targets.begin (); 770 iter != old_info.targets.end (); ++iter) 771 total += iter->second; 772 773 /* Program behavior changed, original promoted (and inlined) target is not 774 hot any more. Will avoid promote the original target. 775 776 To check if original promoted target is still hot, we check the total 777 count of the unpromoted targets (stored in TOTAL). If a callsite count 778 (stored in INFO) is smaller than half of the total count, the original 779 promoted target is considered not hot any more. */ 780 if (info->count < total / 2) 781 { 782 if (dump_file) 783 fprintf (dump_file, " not hot anymore %ld < %ld", 784 (long)info->count, 785 (long)total /2); 786 return false; 787 } 788 789 inline_stack stack; 790 get_inline_stack (gimple_location (stmt), &stack); 791 if (stack.length () == 0) 792 { 793 if (dump_file) 794 fprintf (dump_file, " no inline stack\n"); 795 return false; 796 } 797 function_instance *s = get_function_instance_by_inline_stack (stack); 798 if (s == NULL) 799 { 800 if (dump_file) 801 fprintf (dump_file, " function not found in inline stack\n"); 802 return false; 803 } 804 icall_target_map map; 805 if (s->find_icall_target_map (stmt, &map) == 0) 806 { 807 if (dump_file) 808 fprintf (dump_file, " no target map\n"); 809 return false; 810 } 811 for (icall_target_map::const_iterator iter = map.begin (); 812 iter != map.end (); ++iter) 813 info->targets[iter->first] = iter->second; 814 if (dump_file) 815 fprintf (dump_file, " looks good\n"); 816 return true; 817 } 818 819 /* Find total count of the callee of EDGE. */ 820 821 gcov_type 822 autofdo_source_profile::get_callsite_total_count ( 823 struct cgraph_edge *edge) const 824 { 825 inline_stack stack; 826 stack.safe_push (std::make_pair (edge->callee->decl, 0)); 827 get_inline_stack (gimple_location (edge->call_stmt), &stack); 828 829 function_instance *s = get_function_instance_by_inline_stack (stack); 830 if (s == NULL 831 || afdo_string_table->get_index (IDENTIFIER_POINTER ( 832 DECL_ASSEMBLER_NAME (edge->callee->decl))) != s->name ()) 833 return 0; 834 835 return s->total_count (); 836 } 837 838 /* Read AutoFDO profile and returns TRUE on success. */ 839 840 /* source profile format: 841 842 GCOV_TAG_AFDO_FUNCTION: 4 bytes 843 LENGTH: 4 bytes 844 NUM_FUNCTIONS: 4 bytes 845 FUNCTION_INSTANCE_1 846 FUNCTION_INSTANCE_2 847 ... 848 FUNCTION_INSTANCE_N. */ 849 850 bool 851 autofdo_source_profile::read () 852 { 853 if (gcov_read_unsigned () != GCOV_TAG_AFDO_FUNCTION) 854 { 855 inform (UNKNOWN_LOCATION, "Not expected TAG."); 856 return false; 857 } 858 859 /* Skip the length of the section. */ 860 gcov_read_unsigned (); 861 862 /* Read in the function/callsite profile, and store it in local 863 data structure. */ 864 unsigned function_num = gcov_read_unsigned (); 865 for (unsigned i = 0; i < function_num; i++) 866 { 867 function_instance::function_instance_stack stack; 868 function_instance *s = function_instance::read_function_instance ( 869 &stack, gcov_read_counter ()); 870 afdo_profile_info->sum_all += s->total_count (); 871 map_[s->name ()] = s; 872 } 873 return true; 874 } 875 876 /* Return the function_instance in the profile that correspond to the 877 inline STACK. */ 878 879 function_instance * 880 autofdo_source_profile::get_function_instance_by_inline_stack ( 881 const inline_stack &stack) const 882 { 883 name_function_instance_map::const_iterator iter = map_.find ( 884 afdo_string_table->get_index_by_decl (stack[stack.length () - 1].first)); 885 if (iter == map_.end()) 886 return NULL; 887 function_instance *s = iter->second; 888 for (unsigned i = stack.length() - 1; i > 0; i--) 889 { 890 s = s->get_function_instance_by_decl ( 891 stack[i].second, stack[i - 1].first); 892 if (s == NULL) 893 return NULL; 894 } 895 return s; 896 } 897 898 /* Module profile is only used by LIPO. Here we simply ignore it. */ 899 900 static void 901 fake_read_autofdo_module_profile () 902 { 903 /* Read in the module info. */ 904 gcov_read_unsigned (); 905 906 /* Skip the length of the section. */ 907 gcov_read_unsigned (); 908 909 /* Read in the file name table. */ 910 unsigned total_module_num = gcov_read_unsigned (); 911 gcc_assert (total_module_num == 0); 912 } 913 914 /* Read data from profile data file. */ 915 916 static void 917 read_profile (void) 918 { 919 if (gcov_open (auto_profile_file, 1) == 0) 920 { 921 error ("cannot open profile file %s", auto_profile_file); 922 return; 923 } 924 925 if (gcov_read_unsigned () != GCOV_DATA_MAGIC) 926 { 927 error ("AutoFDO profile magic number does not match"); 928 return; 929 } 930 931 /* Skip the version number. */ 932 unsigned version = gcov_read_unsigned (); 933 if (version != AUTO_PROFILE_VERSION) 934 { 935 error ("AutoFDO profile version %u does match %u", 936 version, AUTO_PROFILE_VERSION); 937 return; 938 } 939 940 /* Skip the empty integer. */ 941 gcov_read_unsigned (); 942 943 /* string_table. */ 944 afdo_string_table = new string_table (); 945 if (!afdo_string_table->read()) 946 { 947 error ("cannot read string table from %s", auto_profile_file); 948 return; 949 } 950 951 /* autofdo_source_profile. */ 952 afdo_source_profile = autofdo_source_profile::create (); 953 if (afdo_source_profile == NULL) 954 { 955 error ("cannot read function profile from %s", auto_profile_file); 956 return; 957 } 958 959 /* autofdo_module_profile. */ 960 fake_read_autofdo_module_profile (); 961 962 /* Read in the working set. */ 963 if (gcov_read_unsigned () != GCOV_TAG_AFDO_WORKING_SET) 964 { 965 error ("cannot read working set from %s", auto_profile_file); 966 return; 967 } 968 969 /* Skip the length of the section. */ 970 gcov_read_unsigned (); 971 gcov_working_set_t set[128]; 972 for (unsigned i = 0; i < 128; i++) 973 { 974 set[i].num_counters = gcov_read_unsigned (); 975 set[i].min_counter = gcov_read_counter (); 976 } 977 add_working_set (set); 978 } 979 980 /* From AutoFDO profiles, find values inside STMT for that we want to measure 981 histograms for indirect-call optimization. 982 983 This function is actually served for 2 purposes: 984 * before annotation, we need to mark histogram, promote and inline 985 * after annotation, we just need to mark, and let follow-up logic to 986 decide if it needs to promote and inline. */ 987 988 static void 989 afdo_indirect_call (gimple_stmt_iterator *gsi, const icall_target_map &map, 990 bool transform) 991 { 992 gimple *gs = gsi_stmt (*gsi); 993 tree callee; 994 995 if (map.size () == 0) 996 return; 997 gcall *stmt = dyn_cast <gcall *> (gs); 998 if ((!stmt) || gimple_call_fndecl (stmt) != NULL_TREE) 999 return; 1000 1001 callee = gimple_call_fn (stmt); 1002 1003 histogram_value hist = gimple_alloc_histogram_value ( 1004 cfun, HIST_TYPE_INDIR_CALL, stmt, callee); 1005 hist->n_counters = 3; 1006 hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters); 1007 gimple_add_histogram_value (cfun, stmt, hist); 1008 1009 gcov_type total = 0; 1010 icall_target_map::const_iterator max_iter = map.end (); 1011 1012 for (icall_target_map::const_iterator iter = map.begin (); 1013 iter != map.end (); ++iter) 1014 { 1015 total += iter->second; 1016 if (max_iter == map.end () || max_iter->second < iter->second) 1017 max_iter = iter; 1018 } 1019 1020 hist->hvalue.counters[0] 1021 = (unsigned long long)afdo_string_table->get_name (max_iter->first); 1022 hist->hvalue.counters[1] = max_iter->second; 1023 hist->hvalue.counters[2] = total; 1024 1025 if (!transform) 1026 return; 1027 1028 struct cgraph_edge *indirect_edge 1029 = cgraph_node::get (current_function_decl)->get_edge (stmt); 1030 struct cgraph_node *direct_call = cgraph_node::get_for_asmname ( 1031 get_identifier ((const char *) hist->hvalue.counters[0])); 1032 1033 if (dump_file) 1034 { 1035 fprintf (dump_file, "Indirect call -> direct call "); 1036 print_generic_expr (dump_file, callee, TDF_SLIM); 1037 fprintf (dump_file, " => "); 1038 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM); 1039 } 1040 1041 if (direct_call == NULL || !check_ic_target (stmt, direct_call)) 1042 { 1043 if (dump_file) 1044 fprintf (dump_file, " not transforming\n"); 1045 return; 1046 } 1047 if (DECL_STRUCT_FUNCTION (direct_call->decl) == NULL) 1048 { 1049 if (dump_file) 1050 fprintf (dump_file, " no declaration\n"); 1051 return; 1052 } 1053 1054 if (dump_file) 1055 { 1056 fprintf (dump_file, " transformation on insn "); 1057 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1058 fprintf (dump_file, "\n"); 1059 } 1060 1061 /* FIXME: Count should be initialized. */ 1062 struct cgraph_edge *new_edge 1063 = indirect_edge->make_speculative (direct_call, 1064 profile_count::uninitialized ()); 1065 new_edge->redirect_call_stmt_to_callee (); 1066 gimple_remove_histogram_value (cfun, stmt, hist); 1067 inline_call (new_edge, true, NULL, NULL, false); 1068 } 1069 1070 /* From AutoFDO profiles, find values inside STMT for that we want to measure 1071 histograms and adds them to list VALUES. */ 1072 1073 static void 1074 afdo_vpt (gimple_stmt_iterator *gsi, const icall_target_map &map, 1075 bool transform) 1076 { 1077 afdo_indirect_call (gsi, map, transform); 1078 } 1079 1080 typedef std::set<basic_block> bb_set; 1081 typedef std::set<edge> edge_set; 1082 1083 static bool 1084 is_bb_annotated (const basic_block bb, const bb_set &annotated) 1085 { 1086 return annotated.find (bb) != annotated.end (); 1087 } 1088 1089 static void 1090 set_bb_annotated (basic_block bb, bb_set *annotated) 1091 { 1092 annotated->insert (bb); 1093 } 1094 1095 static bool 1096 is_edge_annotated (const edge e, const edge_set &annotated) 1097 { 1098 return annotated.find (e) != annotated.end (); 1099 } 1100 1101 static void 1102 set_edge_annotated (edge e, edge_set *annotated) 1103 { 1104 annotated->insert (e); 1105 } 1106 1107 /* For a given BB, set its execution count. Attach value profile if a stmt 1108 is not in PROMOTED, because we only want to promote an indirect call once. 1109 Return TRUE if BB is annotated. */ 1110 1111 static bool 1112 afdo_set_bb_count (basic_block bb, const stmt_set &promoted) 1113 { 1114 gimple_stmt_iterator gsi; 1115 edge e; 1116 edge_iterator ei; 1117 gcov_type max_count = 0; 1118 bool has_annotated = false; 1119 1120 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1121 { 1122 count_info info; 1123 gimple *stmt = gsi_stmt (gsi); 1124 if (gimple_clobber_p (stmt) || is_gimple_debug (stmt)) 1125 continue; 1126 if (afdo_source_profile->get_count_info (stmt, &info)) 1127 { 1128 if (info.count > max_count) 1129 max_count = info.count; 1130 has_annotated = true; 1131 if (info.targets.size () > 0 1132 && promoted.find (stmt) == promoted.end ()) 1133 afdo_vpt (&gsi, info.targets, false); 1134 } 1135 } 1136 1137 if (!has_annotated) 1138 return false; 1139 1140 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1141 afdo_source_profile->mark_annotated (gimple_location (gsi_stmt (gsi))); 1142 for (gphi_iterator gpi = gsi_start_phis (bb); 1143 !gsi_end_p (gpi); 1144 gsi_next (&gpi)) 1145 { 1146 gphi *phi = gpi.phi (); 1147 size_t i; 1148 for (i = 0; i < gimple_phi_num_args (phi); i++) 1149 afdo_source_profile->mark_annotated (gimple_phi_arg_location (phi, i)); 1150 } 1151 FOR_EACH_EDGE (e, ei, bb->succs) 1152 afdo_source_profile->mark_annotated (e->goto_locus); 1153 1154 bb->count = profile_count::from_gcov_type (max_count).afdo (); 1155 return true; 1156 } 1157 1158 /* BB1 and BB2 are in an equivalent class iff: 1159 1. BB1 dominates BB2. 1160 2. BB2 post-dominates BB1. 1161 3. BB1 and BB2 are in the same loop nest. 1162 This function finds the equivalent class for each basic block, and 1163 stores a pointer to the first BB in its equivalent class. Meanwhile, 1164 set bb counts for the same equivalent class to be idenical. Update 1165 ANNOTATED_BB for the first BB in its equivalent class. */ 1166 1167 static void 1168 afdo_find_equiv_class (bb_set *annotated_bb) 1169 { 1170 basic_block bb; 1171 1172 FOR_ALL_BB_FN (bb, cfun) 1173 bb->aux = NULL; 1174 1175 FOR_ALL_BB_FN (bb, cfun) 1176 { 1177 vec<basic_block> dom_bbs; 1178 basic_block bb1; 1179 int i; 1180 1181 if (bb->aux != NULL) 1182 continue; 1183 bb->aux = bb; 1184 dom_bbs = get_dominated_by (CDI_DOMINATORS, bb); 1185 FOR_EACH_VEC_ELT (dom_bbs, i, bb1) 1186 if (bb1->aux == NULL && dominated_by_p (CDI_POST_DOMINATORS, bb, bb1) 1187 && bb1->loop_father == bb->loop_father) 1188 { 1189 bb1->aux = bb; 1190 if (bb1->count > bb->count && is_bb_annotated (bb1, *annotated_bb)) 1191 { 1192 bb->count = bb1->count; 1193 set_bb_annotated (bb, annotated_bb); 1194 } 1195 } 1196 dom_bbs = get_dominated_by (CDI_POST_DOMINATORS, bb); 1197 FOR_EACH_VEC_ELT (dom_bbs, i, bb1) 1198 if (bb1->aux == NULL && dominated_by_p (CDI_DOMINATORS, bb, bb1) 1199 && bb1->loop_father == bb->loop_father) 1200 { 1201 bb1->aux = bb; 1202 if (bb1->count > bb->count && is_bb_annotated (bb1, *annotated_bb)) 1203 { 1204 bb->count = bb1->count; 1205 set_bb_annotated (bb, annotated_bb); 1206 } 1207 } 1208 } 1209 } 1210 1211 /* If a basic block's count is known, and only one of its in/out edges' count 1212 is unknown, its count can be calculated. Meanwhile, if all of the in/out 1213 edges' counts are known, then the basic block's unknown count can also be 1214 calculated. 1215 IS_SUCC is true if out edges of a basic blocks are examined. 1216 Update ANNOTATED_BB and ANNOTATED_EDGE accordingly. 1217 Return TRUE if any basic block/edge count is changed. */ 1218 1219 static bool 1220 afdo_propagate_edge (bool is_succ, bb_set *annotated_bb, 1221 edge_set *annotated_edge) 1222 { 1223 basic_block bb; 1224 bool changed = false; 1225 1226 FOR_EACH_BB_FN (bb, cfun) 1227 { 1228 edge e, unknown_edge = NULL; 1229 edge_iterator ei; 1230 int num_unknown_edge = 0; 1231 profile_count total_known_count = profile_count::zero ().afdo (); 1232 1233 FOR_EACH_EDGE (e, ei, is_succ ? bb->succs : bb->preds) 1234 if (!is_edge_annotated (e, *annotated_edge)) 1235 num_unknown_edge++, unknown_edge = e; 1236 else 1237 total_known_count += e->count (); 1238 1239 if (num_unknown_edge == 0) 1240 { 1241 if (total_known_count > bb->count) 1242 { 1243 bb->count = total_known_count; 1244 changed = true; 1245 } 1246 if (!is_bb_annotated (bb, *annotated_bb)) 1247 { 1248 set_bb_annotated (bb, annotated_bb); 1249 changed = true; 1250 } 1251 } 1252 else if (num_unknown_edge == 1 && is_bb_annotated (bb, *annotated_bb)) 1253 { 1254 unknown_edge->probability 1255 = total_known_count.probability_in (bb->count); 1256 set_edge_annotated (unknown_edge, annotated_edge); 1257 changed = true; 1258 } 1259 } 1260 return changed; 1261 } 1262 1263 /* Special propagation for circuit expressions. Because GCC translates 1264 control flow into data flow for circuit expressions. E.g. 1265 BB1: 1266 if (a && b) 1267 BB2 1268 else 1269 BB3 1270 1271 will be translated into: 1272 1273 BB1: 1274 if (a) 1275 goto BB.t1 1276 else 1277 goto BB.t3 1278 BB.t1: 1279 if (b) 1280 goto BB.t2 1281 else 1282 goto BB.t3 1283 BB.t2: 1284 goto BB.t3 1285 BB.t3: 1286 tmp = PHI (0 (BB1), 0 (BB.t1), 1 (BB.t2) 1287 if (tmp) 1288 goto BB2 1289 else 1290 goto BB3 1291 1292 In this case, we need to propagate through PHI to determine the edge 1293 count of BB1->BB.t1, BB.t1->BB.t2. 1294 Update ANNOTATED_EDGE accordingly. */ 1295 1296 static void 1297 afdo_propagate_circuit (const bb_set &annotated_bb, edge_set *annotated_edge) 1298 { 1299 basic_block bb; 1300 FOR_ALL_BB_FN (bb, cfun) 1301 { 1302 gimple *def_stmt; 1303 tree cmp_rhs, cmp_lhs; 1304 gimple *cmp_stmt = last_stmt (bb); 1305 edge e; 1306 edge_iterator ei; 1307 1308 if (!cmp_stmt || gimple_code (cmp_stmt) != GIMPLE_COND) 1309 continue; 1310 cmp_rhs = gimple_cond_rhs (cmp_stmt); 1311 cmp_lhs = gimple_cond_lhs (cmp_stmt); 1312 if (!TREE_CONSTANT (cmp_rhs) 1313 || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs))) 1314 continue; 1315 if (TREE_CODE (cmp_lhs) != SSA_NAME) 1316 continue; 1317 if (!is_bb_annotated (bb, annotated_bb)) 1318 continue; 1319 def_stmt = SSA_NAME_DEF_STMT (cmp_lhs); 1320 while (def_stmt && gimple_code (def_stmt) == GIMPLE_ASSIGN 1321 && gimple_assign_single_p (def_stmt) 1322 && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME) 1323 def_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt)); 1324 if (!def_stmt) 1325 continue; 1326 gphi *phi_stmt = dyn_cast <gphi *> (def_stmt); 1327 if (!phi_stmt) 1328 continue; 1329 FOR_EACH_EDGE (e, ei, bb->succs) 1330 { 1331 unsigned i, total = 0; 1332 edge only_one; 1333 bool check_value_one = (((integer_onep (cmp_rhs)) 1334 ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR)) 1335 ^ ((e->flags & EDGE_TRUE_VALUE) != 0)); 1336 if (!is_edge_annotated (e, *annotated_edge)) 1337 continue; 1338 for (i = 0; i < gimple_phi_num_args (phi_stmt); i++) 1339 { 1340 tree val = gimple_phi_arg_def (phi_stmt, i); 1341 edge ep = gimple_phi_arg_edge (phi_stmt, i); 1342 1343 if (!TREE_CONSTANT (val) 1344 || !(integer_zerop (val) || integer_onep (val))) 1345 continue; 1346 if (check_value_one ^ integer_onep (val)) 1347 continue; 1348 total++; 1349 only_one = ep; 1350 if (!e->probability.initialized_p () 1351 && !is_edge_annotated (ep, *annotated_edge)) 1352 { 1353 ep->probability = profile_probability::never ().afdo (); 1354 set_edge_annotated (ep, annotated_edge); 1355 } 1356 } 1357 if (total == 1 && !is_edge_annotated (only_one, *annotated_edge)) 1358 { 1359 only_one->probability = e->probability; 1360 set_edge_annotated (only_one, annotated_edge); 1361 } 1362 } 1363 } 1364 } 1365 1366 /* Propagate the basic block count and edge count on the control flow 1367 graph. We do the propagation iteratively until stablize. */ 1368 1369 static void 1370 afdo_propagate (bb_set *annotated_bb, edge_set *annotated_edge) 1371 { 1372 basic_block bb; 1373 bool changed = true; 1374 int i = 0; 1375 1376 FOR_ALL_BB_FN (bb, cfun) 1377 { 1378 bb->count = ((basic_block)bb->aux)->count; 1379 if (is_bb_annotated ((basic_block)bb->aux, *annotated_bb)) 1380 set_bb_annotated (bb, annotated_bb); 1381 } 1382 1383 while (changed && i++ < 10) 1384 { 1385 changed = false; 1386 1387 if (afdo_propagate_edge (true, annotated_bb, annotated_edge)) 1388 changed = true; 1389 if (afdo_propagate_edge (false, annotated_bb, annotated_edge)) 1390 changed = true; 1391 afdo_propagate_circuit (*annotated_bb, annotated_edge); 1392 } 1393 } 1394 1395 /* Propagate counts on control flow graph and calculate branch 1396 probabilities. */ 1397 1398 static void 1399 afdo_calculate_branch_prob (bb_set *annotated_bb, edge_set *annotated_edge) 1400 { 1401 basic_block bb; 1402 bool has_sample = false; 1403 1404 FOR_EACH_BB_FN (bb, cfun) 1405 { 1406 if (bb->count > profile_count::zero ()) 1407 { 1408 has_sample = true; 1409 break; 1410 } 1411 } 1412 1413 if (!has_sample) 1414 return; 1415 1416 calculate_dominance_info (CDI_POST_DOMINATORS); 1417 calculate_dominance_info (CDI_DOMINATORS); 1418 loop_optimizer_init (0); 1419 1420 afdo_find_equiv_class (annotated_bb); 1421 afdo_propagate (annotated_bb, annotated_edge); 1422 1423 FOR_EACH_BB_FN (bb, cfun) 1424 { 1425 edge e; 1426 edge_iterator ei; 1427 int num_unknown_succ = 0; 1428 profile_count total_count = profile_count::zero (); 1429 1430 FOR_EACH_EDGE (e, ei, bb->succs) 1431 { 1432 if (!is_edge_annotated (e, *annotated_edge)) 1433 num_unknown_succ++; 1434 else 1435 total_count += e->count (); 1436 } 1437 if (num_unknown_succ == 0 && total_count > profile_count::zero ()) 1438 { 1439 FOR_EACH_EDGE (e, ei, bb->succs) 1440 e->probability = e->count ().probability_in (total_count); 1441 } 1442 } 1443 FOR_ALL_BB_FN (bb, cfun) 1444 bb->aux = NULL; 1445 1446 loop_optimizer_finalize (); 1447 free_dominance_info (CDI_DOMINATORS); 1448 free_dominance_info (CDI_POST_DOMINATORS); 1449 } 1450 1451 /* Perform value profile transformation using AutoFDO profile. Add the 1452 promoted stmts to PROMOTED_STMTS. Return TRUE if there is any 1453 indirect call promoted. */ 1454 1455 static bool 1456 afdo_vpt_for_early_inline (stmt_set *promoted_stmts) 1457 { 1458 basic_block bb; 1459 if (afdo_source_profile->get_function_instance_by_decl ( 1460 current_function_decl) == NULL) 1461 return false; 1462 1463 compute_fn_summary (cgraph_node::get (current_function_decl), true); 1464 1465 bool has_vpt = false; 1466 FOR_EACH_BB_FN (bb, cfun) 1467 { 1468 if (!has_indirect_call (bb)) 1469 continue; 1470 gimple_stmt_iterator gsi; 1471 1472 gcov_type bb_count = 0; 1473 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1474 { 1475 count_info info; 1476 gimple *stmt = gsi_stmt (gsi); 1477 if (afdo_source_profile->get_count_info (stmt, &info)) 1478 bb_count = MAX (bb_count, info.count); 1479 } 1480 1481 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1482 { 1483 gcall *stmt = dyn_cast <gcall *> (gsi_stmt (gsi)); 1484 /* IC_promotion and early_inline_2 is done in multiple iterations. 1485 No need to promoted the stmt if its in promoted_stmts (means 1486 it is already been promoted in the previous iterations). */ 1487 if ((!stmt) || gimple_call_fn (stmt) == NULL 1488 || TREE_CODE (gimple_call_fn (stmt)) == FUNCTION_DECL 1489 || promoted_stmts->find (stmt) != promoted_stmts->end ()) 1490 continue; 1491 1492 count_info info; 1493 afdo_source_profile->get_count_info (stmt, &info); 1494 info.count = bb_count; 1495 if (afdo_source_profile->update_inlined_ind_target (stmt, &info)) 1496 { 1497 /* Promote the indirect call and update the promoted_stmts. */ 1498 promoted_stmts->insert (stmt); 1499 afdo_vpt (&gsi, info.targets, true); 1500 has_vpt = true; 1501 } 1502 } 1503 } 1504 1505 if (has_vpt) 1506 { 1507 unsigned todo = optimize_inline_calls (current_function_decl); 1508 if (todo & TODO_update_ssa_any) 1509 update_ssa (TODO_update_ssa); 1510 return true; 1511 } 1512 1513 return false; 1514 } 1515 1516 /* Annotate auto profile to the control flow graph. Do not annotate value 1517 profile for stmts in PROMOTED_STMTS. */ 1518 1519 static void 1520 afdo_annotate_cfg (const stmt_set &promoted_stmts) 1521 { 1522 basic_block bb; 1523 bb_set annotated_bb; 1524 edge_set annotated_edge; 1525 const function_instance *s 1526 = afdo_source_profile->get_function_instance_by_decl ( 1527 current_function_decl); 1528 1529 if (s == NULL) 1530 return; 1531 cgraph_node::get (current_function_decl)->count 1532 = profile_count::from_gcov_type (s->head_count ()).afdo (); 1533 ENTRY_BLOCK_PTR_FOR_FN (cfun)->count 1534 = profile_count::from_gcov_type (s->head_count ()).afdo (); 1535 profile_count max_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count; 1536 1537 FOR_EACH_BB_FN (bb, cfun) 1538 { 1539 edge e; 1540 edge_iterator ei; 1541 1542 /* As autoFDO uses sampling approach, we have to assume that all 1543 counters are zero when not seen by autoFDO. */ 1544 bb->count = profile_count::zero ().afdo (); 1545 FOR_EACH_EDGE (e, ei, bb->succs) 1546 e->probability = profile_probability::uninitialized (); 1547 1548 if (afdo_set_bb_count (bb, promoted_stmts)) 1549 set_bb_annotated (bb, &annotated_bb); 1550 if (bb->count > max_count) 1551 max_count = bb->count; 1552 } 1553 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count 1554 > ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->count) 1555 { 1556 ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->count 1557 = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count; 1558 set_bb_annotated (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, &annotated_bb); 1559 } 1560 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count 1561 > EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->count) 1562 { 1563 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->count 1564 = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count; 1565 set_bb_annotated (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb, &annotated_bb); 1566 } 1567 afdo_source_profile->mark_annotated ( 1568 DECL_SOURCE_LOCATION (current_function_decl)); 1569 afdo_source_profile->mark_annotated (cfun->function_start_locus); 1570 afdo_source_profile->mark_annotated (cfun->function_end_locus); 1571 if (max_count > profile_count::zero ()) 1572 { 1573 afdo_calculate_branch_prob (&annotated_bb, &annotated_edge); 1574 update_max_bb_count (); 1575 profile_status_for_fn (cfun) = PROFILE_READ; 1576 } 1577 if (flag_value_profile_transformations) 1578 { 1579 gimple_value_profile_transformations (); 1580 free_dominance_info (CDI_DOMINATORS); 1581 free_dominance_info (CDI_POST_DOMINATORS); 1582 update_ssa (TODO_update_ssa); 1583 } 1584 } 1585 1586 /* Wrapper function to invoke early inliner. */ 1587 1588 static void 1589 early_inline () 1590 { 1591 compute_fn_summary (cgraph_node::get (current_function_decl), true); 1592 unsigned todo = early_inliner (cfun); 1593 if (todo & TODO_update_ssa_any) 1594 update_ssa (TODO_update_ssa); 1595 } 1596 1597 /* Use AutoFDO profile to annoate the control flow graph. 1598 Return the todo flag. */ 1599 1600 static unsigned int 1601 auto_profile (void) 1602 { 1603 struct cgraph_node *node; 1604 1605 if (symtab->state == FINISHED) 1606 return 0; 1607 1608 init_node_map (true); 1609 profile_info = autofdo::afdo_profile_info; 1610 1611 FOR_EACH_FUNCTION (node) 1612 { 1613 if (!gimple_has_body_p (node->decl)) 1614 continue; 1615 1616 /* Don't profile functions produced for builtin stuff. */ 1617 if (DECL_SOURCE_LOCATION (node->decl) == BUILTINS_LOCATION) 1618 continue; 1619 1620 push_cfun (DECL_STRUCT_FUNCTION (node->decl)); 1621 1622 /* First do indirect call promotion and early inline to make the 1623 IR match the profiled binary before actual annotation. 1624 1625 This is needed because an indirect call might have been promoted 1626 and inlined in the profiled binary. If we do not promote and 1627 inline these indirect calls before annotation, the profile for 1628 these promoted functions will be lost. 1629 1630 e.g. foo() --indirect_call--> bar() 1631 In profiled binary, the callsite is promoted and inlined, making 1632 the profile look like: 1633 1634 foo: { 1635 loc_foo_1: count_1 1636 bar@loc_foo_2: { 1637 loc_bar_1: count_2 1638 loc_bar_2: count_3 1639 } 1640 } 1641 1642 Before AutoFDO pass, loc_foo_2 is not promoted thus not inlined. 1643 If we perform annotation on it, the profile inside bar@loc_foo2 1644 will be wasted. 1645 1646 To avoid this, we promote loc_foo_2 and inline the promoted bar 1647 function before annotation, so the profile inside bar@loc_foo2 1648 will be useful. */ 1649 autofdo::stmt_set promoted_stmts; 1650 for (int i = 0; i < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS); i++) 1651 { 1652 if (!flag_value_profile_transformations 1653 || !autofdo::afdo_vpt_for_early_inline (&promoted_stmts)) 1654 break; 1655 early_inline (); 1656 } 1657 1658 early_inline (); 1659 autofdo::afdo_annotate_cfg (promoted_stmts); 1660 compute_function_frequency (); 1661 1662 /* Local pure-const may imply need to fixup the cfg. */ 1663 if (execute_fixup_cfg () & TODO_cleanup_cfg) 1664 cleanup_tree_cfg (); 1665 1666 free_dominance_info (CDI_DOMINATORS); 1667 free_dominance_info (CDI_POST_DOMINATORS); 1668 cgraph_edge::rebuild_edges (); 1669 compute_fn_summary (cgraph_node::get (current_function_decl), true); 1670 pop_cfun (); 1671 } 1672 1673 return TODO_rebuild_cgraph_edges; 1674 } 1675 } /* namespace autofdo. */ 1676 1677 /* Read the profile from the profile data file. */ 1678 1679 void 1680 read_autofdo_file (void) 1681 { 1682 if (auto_profile_file == NULL) 1683 auto_profile_file = DEFAULT_AUTO_PROFILE_FILE; 1684 1685 autofdo::afdo_profile_info = (struct gcov_ctr_summary *)xcalloc ( 1686 1, sizeof (struct gcov_ctr_summary)); 1687 autofdo::afdo_profile_info->runs = 1; 1688 autofdo::afdo_profile_info->sum_max = 0; 1689 autofdo::afdo_profile_info->sum_all = 0; 1690 1691 /* Read the profile from the profile file. */ 1692 autofdo::read_profile (); 1693 } 1694 1695 /* Free the resources. */ 1696 1697 void 1698 end_auto_profile (void) 1699 { 1700 delete autofdo::afdo_source_profile; 1701 delete autofdo::afdo_string_table; 1702 profile_info = NULL; 1703 } 1704 1705 /* Returns TRUE if EDGE is hot enough to be inlined early. */ 1706 1707 bool 1708 afdo_callsite_hot_enough_for_early_inline (struct cgraph_edge *edge) 1709 { 1710 gcov_type count 1711 = autofdo::afdo_source_profile->get_callsite_total_count (edge); 1712 1713 if (count > 0) 1714 { 1715 bool is_hot; 1716 const struct gcov_ctr_summary *saved_profile_info = profile_info; 1717 /* At early inline stage, profile_info is not set yet. We need to 1718 temporarily set it to afdo_profile_info to calculate hotness. */ 1719 profile_info = autofdo::afdo_profile_info; 1720 is_hot = maybe_hot_count_p (NULL, profile_count::from_gcov_type (count)); 1721 profile_info = saved_profile_info; 1722 return is_hot; 1723 } 1724 1725 return false; 1726 } 1727 1728 namespace 1729 { 1730 1731 const pass_data pass_data_ipa_auto_profile = { 1732 SIMPLE_IPA_PASS, "afdo", /* name */ 1733 OPTGROUP_NONE, /* optinfo_flags */ 1734 TV_IPA_AUTOFDO, /* tv_id */ 1735 0, /* properties_required */ 1736 0, /* properties_provided */ 1737 0, /* properties_destroyed */ 1738 0, /* todo_flags_start */ 1739 0, /* todo_flags_finish */ 1740 }; 1741 1742 class pass_ipa_auto_profile : public simple_ipa_opt_pass 1743 { 1744 public: 1745 pass_ipa_auto_profile (gcc::context *ctxt) 1746 : simple_ipa_opt_pass (pass_data_ipa_auto_profile, ctxt) 1747 { 1748 } 1749 1750 /* opt_pass methods: */ 1751 virtual bool 1752 gate (function *) 1753 { 1754 return flag_auto_profile; 1755 } 1756 virtual unsigned int 1757 execute (function *) 1758 { 1759 return autofdo::auto_profile (); 1760 } 1761 }; // class pass_ipa_auto_profile 1762 1763 } // anon namespace 1764 1765 simple_ipa_opt_pass * 1766 make_pass_ipa_auto_profile (gcc::context *ctxt) 1767 { 1768 return new pass_ipa_auto_profile (ctxt); 1769 } 1770