1/* Gimple range GORI functions. 2 Copyright (C) 2017-2022 Free Software Foundation, Inc. 3 Contributed by Andrew MacLeod <amacleod@redhat.com> 4 and Aldy Hernandez <aldyh@redhat.com>. 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify 9it under the terms of the GNU General Public License as published by 10the Free Software Foundation; either version 3, or (at your option) 11any later version. 12 13GCC is distributed in the hope that it will be useful, 14but WITHOUT ANY WARRANTY; without even the implied warranty of 15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16GNU General Public License for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING3. If not see 20<http://www.gnu.org/licenses/>. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "backend.h" 26#include "tree.h" 27#include "gimple.h" 28#include "ssa.h" 29#include "gimple-pretty-print.h" 30#include "gimple-range.h" 31 32// Calculate what we can determine of the range of this unary 33// statement's operand if the lhs of the expression has the range 34// LHS_RANGE. Return false if nothing can be determined. 35 36bool 37gimple_range_calc_op1 (irange &r, const gimple *stmt, const irange &lhs_range) 38{ 39 gcc_checking_assert (gimple_num_ops (stmt) < 3); 40 // Give up on empty ranges. 41 if (lhs_range.undefined_p ()) 42 return false; 43 44 // Unary operations require the type of the first operand in the 45 // second range position. 46 tree type = TREE_TYPE (gimple_range_operand1 (stmt)); 47 int_range<2> type_range (type); 48 return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, 49 type_range); 50} 51 52// Calculate what we can determine of the range of this statement's 53// first operand if the lhs of the expression has the range LHS_RANGE 54// and the second operand has the range OP2_RANGE. Return false if 55// nothing can be determined. 56 57bool 58gimple_range_calc_op1 (irange &r, const gimple *stmt, 59 const irange &lhs_range, const irange &op2_range) 60{ 61 // Give up on empty ranges. 62 if (lhs_range.undefined_p ()) 63 return false; 64 65 // Unary operation are allowed to pass a range in for second operand 66 // as there are often additional restrictions beyond the type which 67 // can be imposed. See operator_cast::op1_range(). 68 tree type = TREE_TYPE (gimple_range_operand1 (stmt)); 69 // If op2 is undefined, solve as if it is varying. 70 if (op2_range.undefined_p ()) 71 { 72 // This is sometimes invoked on single operand stmts. 73 if (gimple_num_ops (stmt) < 3) 74 return false; 75 int_range<2> trange (TREE_TYPE (gimple_range_operand2 (stmt))); 76 return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, 77 trange); 78 } 79 return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, 80 op2_range); 81} 82 83// Calculate what we can determine of the range of this statement's 84// second operand if the lhs of the expression has the range LHS_RANGE 85// and the first operand has the range OP1_RANGE. Return false if 86// nothing can be determined. 87 88bool 89gimple_range_calc_op2 (irange &r, const gimple *stmt, 90 const irange &lhs_range, const irange &op1_range) 91{ 92 // Give up on empty ranges. 93 if (lhs_range.undefined_p ()) 94 return false; 95 96 tree type = TREE_TYPE (gimple_range_operand2 (stmt)); 97 // If op1 is undefined, solve as if it is varying. 98 if (op1_range.undefined_p ()) 99 { 100 int_range<2> trange (TREE_TYPE (gimple_range_operand1 (stmt))); 101 return gimple_range_handler (stmt)->op2_range (r, type, lhs_range, 102 trange); 103 } 104 return gimple_range_handler (stmt)->op2_range (r, type, lhs_range, 105 op1_range); 106} 107 108// Return TRUE if GS is a logical && or || expression. 109 110static inline bool 111is_gimple_logical_p (const gimple *gs) 112{ 113 // Look for boolean and/or condition. 114 if (is_gimple_assign (gs)) 115 switch (gimple_expr_code (gs)) 116 { 117 case TRUTH_AND_EXPR: 118 case TRUTH_OR_EXPR: 119 return true; 120 121 case BIT_AND_EXPR: 122 case BIT_IOR_EXPR: 123 // Bitwise operations on single bits are logical too. 124 if (types_compatible_p (TREE_TYPE (gimple_assign_rhs1 (gs)), 125 boolean_type_node)) 126 return true; 127 break; 128 129 default: 130 break; 131 } 132 return false; 133} 134 135/* RANGE_DEF_CHAIN is used to determine which SSA names in a block can 136 have range information calculated for them, and what the 137 dependencies on each other are. 138 139 Information for a basic block is calculated once and stored. It is 140 only calculated the first time a query is made, so if no queries 141 are made, there is little overhead. 142 143 The def_chain bitmap is indexed by SSA_NAME_VERSION. Bits are set 144 within this bitmap to indicate SSA names that are defined in the 145 SAME block and used to calculate this SSA name. 146 147 148 <bb 2> : 149 _1 = x_4(D) + -2; 150 _2 = _1 * 4; 151 j_7 = foo (); 152 q_5 = _2 + 3; 153 if (q_5 <= 13) 154 155 _1 : x_4(D) 156 _2 : 1 x_4(D) 157 q_5 : _1 _2 x_4(D) 158 159 This dump indicates the bits set in the def_chain vector. 160 as well as demonstrates the def_chain bits for the related ssa_names. 161 162 Checking the chain for _2 indicates that _1 and x_4 are used in 163 its evaluation. 164 165 Def chains also only include statements which are valid gimple 166 so a def chain will only span statements for which the range 167 engine implements operations for. */ 168 169 170// Construct a range_def_chain. 171 172range_def_chain::range_def_chain () 173{ 174 bitmap_obstack_initialize (&m_bitmaps); 175 m_def_chain.create (0); 176 m_def_chain.safe_grow_cleared (num_ssa_names); 177 m_logical_depth = 0; 178} 179 180// Destruct a range_def_chain. 181 182range_def_chain::~range_def_chain () 183{ 184 m_def_chain.release (); 185 bitmap_obstack_release (&m_bitmaps); 186} 187 188// Return true if NAME is in the def chain of DEF. If BB is provided, 189// only return true if the defining statement of DEF is in BB. 190 191bool 192range_def_chain::in_chain_p (tree name, tree def) 193{ 194 gcc_checking_assert (gimple_range_ssa_p (def)); 195 gcc_checking_assert (gimple_range_ssa_p (name)); 196 197 // Get the defintion chain for DEF. 198 bitmap chain = get_def_chain (def); 199 200 if (chain == NULL) 201 return false; 202 return bitmap_bit_p (chain, SSA_NAME_VERSION (name)); 203} 204 205// Add either IMP or the import list B to the import set of DATA. 206 207void 208range_def_chain::set_import (struct rdc &data, tree imp, bitmap b) 209{ 210 // If there are no imports, just return 211 if (imp == NULL_TREE && !b) 212 return; 213 if (!data.m_import) 214 data.m_import = BITMAP_ALLOC (&m_bitmaps); 215 if (imp != NULL_TREE) 216 bitmap_set_bit (data.m_import, SSA_NAME_VERSION (imp)); 217 else 218 bitmap_ior_into (data.m_import, b); 219} 220 221// Return the import list for NAME. 222 223bitmap 224range_def_chain::get_imports (tree name) 225{ 226 if (!has_def_chain (name)) 227 get_def_chain (name); 228 bitmap i = m_def_chain[SSA_NAME_VERSION (name)].m_import; 229 return i; 230} 231 232// Return true if IMPORT is an import to NAMEs def chain. 233 234bool 235range_def_chain::chain_import_p (tree name, tree import) 236{ 237 bitmap b = get_imports (name); 238 if (b) 239 return bitmap_bit_p (b, SSA_NAME_VERSION (import)); 240 return false; 241} 242 243// Build def_chains for NAME if it is in BB. Copy the def chain into RESULT. 244 245void 246range_def_chain::register_dependency (tree name, tree dep, basic_block bb) 247{ 248 if (!gimple_range_ssa_p (dep)) 249 return; 250 251 unsigned v = SSA_NAME_VERSION (name); 252 if (v >= m_def_chain.length ()) 253 m_def_chain.safe_grow_cleared (num_ssa_names + 1); 254 struct rdc &src = m_def_chain[v]; 255 gimple *def_stmt = SSA_NAME_DEF_STMT (dep); 256 unsigned dep_v = SSA_NAME_VERSION (dep); 257 bitmap b; 258 259 // Set the direct dependency cache entries. 260 if (!src.ssa1) 261 src.ssa1 = dep; 262 else if (!src.ssa2 && src.ssa1 != dep) 263 src.ssa2 = dep; 264 265 // Don't calculate imports or export/dep chains if BB is not provided. 266 // This is usually the case for when the temporal cache wants the direct 267 // dependencies of a stmt. 268 if (!bb) 269 return; 270 271 if (!src.bm) 272 src.bm = BITMAP_ALLOC (&m_bitmaps); 273 274 // Add this operand into the result. 275 bitmap_set_bit (src.bm, dep_v); 276 277 if (gimple_bb (def_stmt) == bb && !is_a<gphi *>(def_stmt)) 278 { 279 // Get the def chain for the operand. 280 b = get_def_chain (dep); 281 // If there was one, copy it into result. Access def_chain directly 282 // as the get_def_chain request above could reallocate the vector. 283 if (b) 284 bitmap_ior_into (m_def_chain[v].bm, b); 285 // And copy the import list. 286 set_import (m_def_chain[v], NULL_TREE, get_imports (dep)); 287 } 288 else 289 // Originated outside the block, so it is an import. 290 set_import (src, dep, NULL); 291} 292 293bool 294range_def_chain::def_chain_in_bitmap_p (tree name, bitmap b) 295{ 296 bitmap a = get_def_chain (name); 297 if (a && b) 298 return bitmap_intersect_p (a, b); 299 return false; 300} 301 302void 303range_def_chain::add_def_chain_to_bitmap (bitmap b, tree name) 304{ 305 bitmap r = get_def_chain (name); 306 if (r) 307 bitmap_ior_into (b, r); 308} 309 310 311// Return TRUE if NAME has been processed for a def_chain. 312 313inline bool 314range_def_chain::has_def_chain (tree name) 315{ 316 // Ensure there is an entry in the internal vector. 317 unsigned v = SSA_NAME_VERSION (name); 318 if (v >= m_def_chain.length ()) 319 m_def_chain.safe_grow_cleared (num_ssa_names + 1); 320 return (m_def_chain[v].ssa1 != 0); 321} 322 323 324 325// Calculate the def chain for NAME and all of its dependent 326// operands. Only using names in the same BB. Return the bitmap of 327// all names in the m_def_chain. This only works for supported range 328// statements. 329 330bitmap 331range_def_chain::get_def_chain (tree name) 332{ 333 tree ssa1, ssa2, ssa3; 334 unsigned v = SSA_NAME_VERSION (name); 335 336 // If it has already been processed, just return the cached value. 337 if (has_def_chain (name) && m_def_chain[v].bm) 338 return m_def_chain[v].bm; 339 340 // No definition chain for default defs. 341 if (SSA_NAME_IS_DEFAULT_DEF (name)) 342 { 343 // A Default def is always an import. 344 set_import (m_def_chain[v], name, NULL); 345 return NULL; 346 } 347 348 gimple *stmt = SSA_NAME_DEF_STMT (name); 349 if (gimple_range_handler (stmt)) 350 { 351 ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); 352 ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); 353 ssa3 = NULL_TREE; 354 } 355 else if (is_a<gassign *> (stmt) 356 && gimple_assign_rhs_code (stmt) == COND_EXPR) 357 { 358 gassign *st = as_a<gassign *> (stmt); 359 ssa1 = gimple_range_ssa_p (gimple_assign_rhs1 (st)); 360 ssa2 = gimple_range_ssa_p (gimple_assign_rhs2 (st)); 361 ssa3 = gimple_range_ssa_p (gimple_assign_rhs3 (st)); 362 } 363 else 364 { 365 // Stmts not understood are always imports. 366 set_import (m_def_chain[v], name, NULL); 367 return NULL; 368 } 369 370 // Terminate the def chains if we see too many cascading stmts. 371 if (m_logical_depth == param_ranger_logical_depth) 372 return NULL; 373 374 // Increase the depth if we have a pair of ssa-names. 375 if (ssa1 && ssa2) 376 m_logical_depth++; 377 378 register_dependency (name, ssa1, gimple_bb (stmt)); 379 register_dependency (name, ssa2, gimple_bb (stmt)); 380 register_dependency (name, ssa3, gimple_bb (stmt)); 381 // Stmts with no understandable operands are also imports. 382 if (!ssa1 && !ssa2 & !ssa3) 383 set_import (m_def_chain[v], name, NULL); 384 385 if (ssa1 && ssa2) 386 m_logical_depth--; 387 388 return m_def_chain[v].bm; 389} 390 391// Dump what we know for basic block BB to file F. 392 393void 394range_def_chain::dump (FILE *f, basic_block bb, const char *prefix) 395{ 396 unsigned x, y; 397 bitmap_iterator bi; 398 399 // Dump the def chain for each SSA_NAME defined in BB. 400 for (x = 1; x < num_ssa_names; x++) 401 { 402 tree name = ssa_name (x); 403 if (!name) 404 continue; 405 gimple *stmt = SSA_NAME_DEF_STMT (name); 406 if (!stmt || (bb && gimple_bb (stmt) != bb)) 407 continue; 408 bitmap chain = (has_def_chain (name) ? get_def_chain (name) : NULL); 409 if (chain && !bitmap_empty_p (chain)) 410 { 411 fprintf (f, prefix); 412 print_generic_expr (f, name, TDF_SLIM); 413 fprintf (f, " : "); 414 415 bitmap imports = get_imports (name); 416 EXECUTE_IF_SET_IN_BITMAP (chain, 0, y, bi) 417 { 418 print_generic_expr (f, ssa_name (y), TDF_SLIM); 419 if (imports && bitmap_bit_p (imports, y)) 420 fprintf (f, "(I)"); 421 fprintf (f, " "); 422 } 423 fprintf (f, "\n"); 424 } 425 } 426} 427 428 429// ------------------------------------------------------------------- 430 431/* GORI_MAP is used to accumulate what SSA names in a block can 432 generate range information, and provides tools for the block ranger 433 to enable it to efficiently calculate these ranges. 434 435 GORI stands for "Generates Outgoing Range Information." 436 437 It utilizes the range_def_chain class to contruct def_chains. 438 Information for a basic block is calculated once and stored. It is 439 only calculated the first time a query is made. If no queries are 440 made, there is little overhead. 441 442 one bitmap is maintained for each basic block: 443 m_outgoing : a set bit indicates a range can be generated for a name. 444 445 Generally speaking, the m_outgoing vector is the union of the 446 entire def_chain of all SSA names used in the last statement of the 447 block which generate ranges. */ 448 449 450// Initialize a gori-map structure. 451 452gori_map::gori_map () 453{ 454 m_outgoing.create (0); 455 m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); 456 m_incoming.create (0); 457 m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun)); 458 m_maybe_variant = BITMAP_ALLOC (&m_bitmaps); 459} 460 461// Free any memory the GORI map allocated. 462 463gori_map::~gori_map () 464{ 465 m_incoming.release (); 466 m_outgoing.release (); 467} 468 469// Return the bitmap vector of all export from BB. Calculate if necessary. 470 471bitmap 472gori_map::exports (basic_block bb) 473{ 474 if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index]) 475 calculate_gori (bb); 476 return m_outgoing[bb->index]; 477} 478 479// Return the bitmap vector of all imports to BB. Calculate if necessary. 480 481bitmap 482gori_map::imports (basic_block bb) 483{ 484 if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index]) 485 calculate_gori (bb); 486 return m_incoming[bb->index]; 487} 488 489// Return true if NAME is can have ranges generated for it from basic 490// block BB. 491 492bool 493gori_map::is_export_p (tree name, basic_block bb) 494{ 495 // If no BB is specified, test if it is exported anywhere in the IL. 496 if (!bb) 497 return bitmap_bit_p (m_maybe_variant, SSA_NAME_VERSION (name)); 498 return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name)); 499} 500 501// Clear the m_maybe_variant bit so ranges will not be tracked for NAME. 502 503void 504gori_map::set_range_invariant (tree name) 505{ 506 bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name)); 507} 508 509// Return true if NAME is an import to block BB. 510 511bool 512gori_map::is_import_p (tree name, basic_block bb) 513{ 514 // If no BB is specified, test if it is exported anywhere in the IL. 515 return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name)); 516} 517 518// If NAME is non-NULL and defined in block BB, calculate the def 519// chain and add it to m_outgoing. 520 521void 522gori_map::maybe_add_gori (tree name, basic_block bb) 523{ 524 if (name) 525 { 526 // Check if there is a def chain, regardless of the block. 527 add_def_chain_to_bitmap (m_outgoing[bb->index], name); 528 // Check for any imports. 529 bitmap imp = get_imports (name); 530 // If there were imports, add them so we can recompute 531 if (imp) 532 bitmap_ior_into (m_incoming[bb->index], imp); 533 // This name is always an import. 534 if (gimple_bb (SSA_NAME_DEF_STMT (name)) != bb) 535 bitmap_set_bit (m_incoming[bb->index], SSA_NAME_VERSION (name)); 536 537 // Def chain doesn't include itself, and even if there isn't a 538 // def chain, this name should be added to exports. 539 bitmap_set_bit (m_outgoing[bb->index], SSA_NAME_VERSION (name)); 540 } 541} 542 543// Calculate all the required information for BB. 544 545void 546gori_map::calculate_gori (basic_block bb) 547{ 548 tree name; 549 if (bb->index >= (signed int)m_outgoing.length ()) 550 { 551 m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun)); 552 m_incoming.safe_grow_cleared (last_basic_block_for_fn (cfun)); 553 } 554 gcc_checking_assert (m_outgoing[bb->index] == NULL); 555 m_outgoing[bb->index] = BITMAP_ALLOC (&m_bitmaps); 556 m_incoming[bb->index] = BITMAP_ALLOC (&m_bitmaps); 557 558 if (single_succ_p (bb)) 559 return; 560 561 // If this block's last statement may generate range informaiton, go 562 // calculate it. 563 gimple *stmt = gimple_outgoing_range_stmt_p (bb); 564 if (!stmt) 565 return; 566 if (is_a<gcond *> (stmt)) 567 { 568 gcond *gc = as_a<gcond *>(stmt); 569 name = gimple_range_ssa_p (gimple_cond_lhs (gc)); 570 maybe_add_gori (name, gimple_bb (stmt)); 571 572 name = gimple_range_ssa_p (gimple_cond_rhs (gc)); 573 maybe_add_gori (name, gimple_bb (stmt)); 574 } 575 else 576 { 577 // Do not process switches if they are too large. 578 if (EDGE_COUNT (bb->succs) > (unsigned)param_evrp_switch_limit) 579 return; 580 gswitch *gs = as_a<gswitch *>(stmt); 581 name = gimple_range_ssa_p (gimple_switch_index (gs)); 582 maybe_add_gori (name, gimple_bb (stmt)); 583 } 584 // Add this bitmap to the aggregate list of all outgoing names. 585 bitmap_ior_into (m_maybe_variant, m_outgoing[bb->index]); 586} 587 588// Dump the table information for BB to file F. 589 590void 591gori_map::dump (FILE *f, basic_block bb, bool verbose) 592{ 593 // BB was not processed. 594 if (!m_outgoing[bb->index] || bitmap_empty_p (m_outgoing[bb->index])) 595 return; 596 597 tree name; 598 599 bitmap imp = imports (bb); 600 if (!bitmap_empty_p (imp)) 601 { 602 if (verbose) 603 fprintf (f, "bb<%u> Imports: ",bb->index); 604 else 605 fprintf (f, "Imports: "); 606 FOR_EACH_GORI_IMPORT_NAME (*this, bb, name) 607 { 608 print_generic_expr (f, name, TDF_SLIM); 609 fprintf (f, " "); 610 } 611 fputc ('\n', f); 612 } 613 614 if (verbose) 615 fprintf (f, "bb<%u> Exports: ",bb->index); 616 else 617 fprintf (f, "Exports: "); 618 // Dump the export vector. 619 FOR_EACH_GORI_EXPORT_NAME (*this, bb, name) 620 { 621 print_generic_expr (f, name, TDF_SLIM); 622 fprintf (f, " "); 623 } 624 fputc ('\n', f); 625 626 range_def_chain::dump (f, bb, " "); 627} 628 629// Dump the entire GORI map structure to file F. 630 631void 632gori_map::dump (FILE *f) 633{ 634 basic_block bb; 635 FOR_EACH_BB_FN (bb, cfun) 636 dump (f, bb); 637} 638 639DEBUG_FUNCTION void 640debug (gori_map &g) 641{ 642 g.dump (stderr); 643} 644 645// ------------------------------------------------------------------- 646 647// Construct a gori_compute object. 648 649gori_compute::gori_compute (int not_executable_flag) 650 : outgoing (param_evrp_switch_limit), tracer ("GORI ") 651{ 652 m_not_executable_flag = not_executable_flag; 653 // Create a boolean_type true and false range. 654 m_bool_zero = int_range<2> (boolean_false_node, boolean_false_node); 655 m_bool_one = int_range<2> (boolean_true_node, boolean_true_node); 656 if (dump_file && (param_ranger_debug & RANGER_DEBUG_GORI)) 657 tracer.enable_trace (); 658} 659 660// Given the switch S, return an evaluation in R for NAME when the lhs 661// evaluates to LHS. Returning false means the name being looked for 662// was not resolvable. 663 664bool 665gori_compute::compute_operand_range_switch (irange &r, gswitch *s, 666 const irange &lhs, 667 tree name, fur_source &src) 668{ 669 tree op1 = gimple_switch_index (s); 670 671 // If name matches, the range is simply the range from the edge. 672 // Empty ranges are viral as they are on a path which isn't 673 // executable. 674 if (op1 == name || lhs.undefined_p ()) 675 { 676 r = lhs; 677 return true; 678 } 679 680 // If op1 is in the defintion chain, pass lhs back. 681 if (gimple_range_ssa_p (op1) && in_chain_p (name, op1)) 682 return compute_operand_range (r, SSA_NAME_DEF_STMT (op1), lhs, name, src); 683 684 return false; 685} 686 687 688// Return an evaluation for NAME as it would appear in STMT when the 689// statement's lhs evaluates to LHS. If successful, return TRUE and 690// store the evaluation in R, otherwise return FALSE. 691 692bool 693gori_compute::compute_operand_range (irange &r, gimple *stmt, 694 const irange &lhs, tree name, 695 fur_source &src) 696{ 697 // If the lhs doesn't tell us anything, neither will unwinding further. 698 if (lhs.varying_p ()) 699 return false; 700 701 // Empty ranges are viral as they are on an unexecutable path. 702 if (lhs.undefined_p ()) 703 { 704 r.set_undefined (); 705 return true; 706 } 707 if (is_a<gswitch *> (stmt)) 708 return compute_operand_range_switch (r, as_a<gswitch *> (stmt), lhs, name, 709 src); 710 if (!gimple_range_handler (stmt)) 711 return false; 712 713 tree op1 = gimple_range_ssa_p (gimple_range_operand1 (stmt)); 714 tree op2 = gimple_range_ssa_p (gimple_range_operand2 (stmt)); 715 716 // Handle end of lookup first. 717 if (op1 == name) 718 return compute_operand1_range (r, stmt, lhs, name, src); 719 if (op2 == name) 720 return compute_operand2_range (r, stmt, lhs, name, src); 721 722 // NAME is not in this stmt, but one of the names in it ought to be 723 // derived from it. 724 bool op1_in_chain = op1 && in_chain_p (name, op1); 725 bool op2_in_chain = op2 && in_chain_p (name, op2); 726 727 // If neither operand is derived, then this stmt tells us nothing. 728 if (!op1_in_chain && !op2_in_chain) 729 return false; 730 731 bool res; 732 // Process logicals as they have special handling. 733 if (is_gimple_logical_p (stmt)) 734 { 735 unsigned idx; 736 if ((idx = tracer.header ("compute_operand "))) 737 { 738 print_generic_expr (dump_file, name, TDF_SLIM); 739 fprintf (dump_file, " with LHS = "); 740 lhs.dump (dump_file); 741 fprintf (dump_file, " at stmt "); 742 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 743 } 744 745 int_range_max op1_trange, op1_frange; 746 int_range_max op2_trange, op2_frange; 747 compute_logical_operands (op1_trange, op1_frange, stmt, lhs, 748 name, src, op1, op1_in_chain); 749 compute_logical_operands (op2_trange, op2_frange, stmt, lhs, 750 name, src, op2, op2_in_chain); 751 res = logical_combine (r, gimple_expr_code (stmt), lhs, 752 op1_trange, op1_frange, op2_trange, op2_frange); 753 if (idx) 754 tracer.trailer (idx, "compute_operand", res, name, r); 755 } 756 // Follow the appropriate operands now. 757 else if (op1_in_chain && op2_in_chain) 758 res = compute_operand1_and_operand2_range (r, stmt, lhs, name, src); 759 else if (op1_in_chain) 760 res = compute_operand1_range (r, stmt, lhs, name, src); 761 else if (op2_in_chain) 762 res = compute_operand2_range (r, stmt, lhs, name, src); 763 else 764 gcc_unreachable (); 765 766 // If neither operand is derived, this statement tells us nothing. 767 return res; 768} 769 770 771// Return TRUE if range R is either a true or false compatible range. 772 773static bool 774range_is_either_true_or_false (const irange &r) 775{ 776 if (r.undefined_p ()) 777 return false; 778 779 // This is complicated by the fact that Ada has multi-bit booleans, 780 // so true can be ~[0, 0] (i.e. [1,MAX]). 781 tree type = r.type (); 782 gcc_checking_assert (range_compatible_p (type, boolean_type_node)); 783 return (r.singleton_p () || !r.contains_p (build_zero_cst (type))); 784} 785 786// Evaluate a binary logical expression by combining the true and 787// false ranges for each of the operands based on the result value in 788// the LHS. 789 790bool 791gori_compute::logical_combine (irange &r, enum tree_code code, 792 const irange &lhs, 793 const irange &op1_true, const irange &op1_false, 794 const irange &op2_true, const irange &op2_false) 795{ 796 if (op1_true.varying_p () && op1_false.varying_p () 797 && op2_true.varying_p () && op2_false.varying_p ()) 798 return false; 799 800 unsigned idx; 801 if ((idx = tracer.header ("logical_combine"))) 802 { 803 switch (code) 804 { 805 case TRUTH_OR_EXPR: 806 case BIT_IOR_EXPR: 807 fprintf (dump_file, " || "); 808 break; 809 case TRUTH_AND_EXPR: 810 case BIT_AND_EXPR: 811 fprintf (dump_file, " && "); 812 break; 813 default: 814 break; 815 } 816 fprintf (dump_file, " with LHS = "); 817 lhs.dump (dump_file); 818 fputc ('\n', dump_file); 819 820 tracer.print (idx, "op1_true = "); 821 op1_true.dump (dump_file); 822 fprintf (dump_file, " op1_false = "); 823 op1_false.dump (dump_file); 824 fputc ('\n', dump_file); 825 tracer.print (idx, "op2_true = "); 826 op2_true.dump (dump_file); 827 fprintf (dump_file, " op2_false = "); 828 op2_false.dump (dump_file); 829 fputc ('\n', dump_file); 830 } 831 832 // This is not a simple fold of a logical expression, rather it 833 // determines ranges which flow through the logical expression. 834 // 835 // Assuming x_8 is an unsigned char, and relational statements: 836 // b_1 = x_8 < 20 837 // b_2 = x_8 > 5 838 // consider the logical expression and branch: 839 // c_2 = b_1 && b_2 840 // if (c_2) 841 // 842 // To determine the range of x_8 on either edge of the branch, one 843 // must first determine what the range of x_8 is when the boolean 844 // values of b_1 and b_2 are both true and false. 845 // b_1 TRUE x_8 = [0, 19] 846 // b_1 FALSE x_8 = [20, 255] 847 // b_2 TRUE x_8 = [6, 255] 848 // b_2 FALSE x_8 = [0,5]. 849 // 850 // These ranges are then combined based on the expected outcome of 851 // the branch. The range on the TRUE side of the branch must satisfy 852 // b_1 == true && b_2 == true 853 // 854 // In terms of x_8, that means both x_8 == [0, 19] and x_8 = [6, 255] 855 // must be true. The range of x_8 on the true side must be the 856 // intersection of both ranges since both must be true. Thus the 857 // range of x_8 on the true side is [6, 19]. 858 // 859 // To determine the ranges on the FALSE side, all 3 combinations of 860 // failing ranges must be considered, and combined as any of them 861 // can cause the false result. 862 // 863 // If the LHS can be TRUE or FALSE, then evaluate both a TRUE and 864 // FALSE results and combine them. If we fell back to VARYING any 865 // range restrictions that have been discovered up to this point 866 // would be lost. 867 if (!range_is_either_true_or_false (lhs)) 868 { 869 bool res; 870 int_range_max r1; 871 if (logical_combine (r1, code, m_bool_zero, op1_true, op1_false, 872 op2_true, op2_false) 873 && logical_combine (r, code, m_bool_one, op1_true, op1_false, 874 op2_true, op2_false)) 875 { 876 r.union_ (r1); 877 res = true; 878 } 879 else 880 res = false; 881 if (idx) 882 tracer.trailer (idx, "logical_combine", res, NULL_TREE, r); 883 } 884 885 switch (code) 886 { 887 // A logical AND combines ranges from 2 boolean conditions. 888 // c_2 = b_1 && b_2 889 case TRUTH_AND_EXPR: 890 case BIT_AND_EXPR: 891 if (!lhs.zero_p ()) 892 { 893 // The TRUE side is the intersection of the 2 true ranges. 894 r = op1_true; 895 r.intersect (op2_true); 896 } 897 else 898 { 899 // The FALSE side is the union of the other 3 cases. 900 int_range_max ff (op1_false); 901 ff.intersect (op2_false); 902 int_range_max tf (op1_true); 903 tf.intersect (op2_false); 904 int_range_max ft (op1_false); 905 ft.intersect (op2_true); 906 r = ff; 907 r.union_ (tf); 908 r.union_ (ft); 909 } 910 break; 911 // A logical OR combines ranges from 2 boolean conditons. 912 // c_2 = b_1 || b_2 913 case TRUTH_OR_EXPR: 914 case BIT_IOR_EXPR: 915 if (lhs.zero_p ()) 916 { 917 // An OR operation will only take the FALSE path if both 918 // operands are false simlulateously, which means they should 919 // be intersected. !(x || y) == !x && !y 920 r = op1_false; 921 r.intersect (op2_false); 922 } 923 else 924 { 925 // The TRUE side of an OR operation will be the union of 926 // the other three combinations. 927 int_range_max tt (op1_true); 928 tt.intersect (op2_true); 929 int_range_max tf (op1_true); 930 tf.intersect (op2_false); 931 int_range_max ft (op1_false); 932 ft.intersect (op2_true); 933 r = tt; 934 r.union_ (tf); 935 r.union_ (ft); 936 } 937 break; 938 default: 939 gcc_unreachable (); 940 } 941 942 if (idx) 943 tracer.trailer (idx, "logical_combine", true, NULL_TREE, r); 944 return true; 945} 946 947 948// Given a logical STMT, calculate true and false ranges for each 949// potential path of NAME, assuming NAME came through the OP chain if 950// OP_IN_CHAIN is true. 951 952void 953gori_compute::compute_logical_operands (irange &true_range, irange &false_range, 954 gimple *stmt, 955 const irange &lhs, 956 tree name, fur_source &src, 957 tree op, bool op_in_chain) 958{ 959 gimple *src_stmt = gimple_range_ssa_p (op) ? SSA_NAME_DEF_STMT (op) : NULL; 960 if (!op_in_chain || !src_stmt || chain_import_p (gimple_get_lhs (stmt), op)) 961 { 962 // If op is not in the def chain, or defined in this block, 963 // use its known value on entry to the block. 964 src.get_operand (true_range, name); 965 false_range = true_range; 966 unsigned idx; 967 if ((idx = tracer.header ("logical_operand"))) 968 { 969 print_generic_expr (dump_file, op, TDF_SLIM); 970 fprintf (dump_file, " not in computation chain. Queried.\n"); 971 tracer.trailer (idx, "logical_operand", true, NULL_TREE, true_range); 972 } 973 return; 974 } 975 976 enum tree_code code = gimple_expr_code (stmt); 977 // Optimize [0 = x | y], since neither operand can ever be non-zero. 978 if ((code == BIT_IOR_EXPR || code == TRUTH_OR_EXPR) && lhs.zero_p ()) 979 { 980 if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, 981 src)) 982 src.get_operand (false_range, name); 983 true_range = false_range; 984 return; 985 } 986 987 // Optimize [1 = x & y], since neither operand can ever be zero. 988 if ((code == BIT_AND_EXPR || code == TRUTH_AND_EXPR) && lhs == m_bool_one) 989 { 990 if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src)) 991 src.get_operand (true_range, name); 992 false_range = true_range; 993 return; 994 } 995 996 // Calculate ranges for true and false on both sides, since the false 997 // path is not always a simple inversion of the true side. 998 if (!compute_operand_range (true_range, src_stmt, m_bool_one, name, src)) 999 src.get_operand (true_range, name); 1000 if (!compute_operand_range (false_range, src_stmt, m_bool_zero, name, src)) 1001 src.get_operand (false_range, name); 1002} 1003 1004// Calculate a range for NAME from the operand 1 position of STMT 1005// assuming the result of the statement is LHS. Return the range in 1006// R, or false if no range could be calculated. 1007 1008bool 1009gori_compute::compute_operand1_range (irange &r, gimple *stmt, 1010 const irange &lhs, tree name, 1011 fur_source &src) 1012{ 1013 int_range_max op1_range, op2_range; 1014 tree op1 = gimple_range_operand1 (stmt); 1015 tree op2 = gimple_range_operand2 (stmt); 1016 1017 // Fetch the known range for op1 in this block. 1018 src.get_operand (op1_range, op1); 1019 1020 // Now range-op calcuate and put that result in r. 1021 if (op2) 1022 { 1023 src.get_operand (op2_range, op2); 1024 if (!gimple_range_calc_op1 (r, stmt, lhs, op2_range)) 1025 return false; 1026 } 1027 else 1028 { 1029 // We pass op1_range to the unary operation. Nomally it's a 1030 // hidden range_for_type parameter, but sometimes having the 1031 // actual range can result in better information. 1032 if (!gimple_range_calc_op1 (r, stmt, lhs, op1_range)) 1033 return false; 1034 } 1035 1036 unsigned idx; 1037 if ((idx = tracer.header ("compute op 1 ("))) 1038 { 1039 print_generic_expr (dump_file, op1, TDF_SLIM); 1040 fprintf (dump_file, ") at "); 1041 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1042 tracer.print (idx, "LHS ="); 1043 lhs.dump (dump_file); 1044 if (op2 && TREE_CODE (op2) == SSA_NAME) 1045 { 1046 fprintf (dump_file, ", "); 1047 print_generic_expr (dump_file, op2, TDF_SLIM); 1048 fprintf (dump_file, " = "); 1049 op2_range.dump (dump_file); 1050 } 1051 fprintf (dump_file, "\n"); 1052 tracer.print (idx, "Computes "); 1053 print_generic_expr (dump_file, op1, TDF_SLIM); 1054 fprintf (dump_file, " = "); 1055 r.dump (dump_file); 1056 fprintf (dump_file, " intersect Known range : "); 1057 op1_range.dump (dump_file); 1058 fputc ('\n', dump_file); 1059 } 1060 // Intersect the calculated result with the known result and return if done. 1061 if (op1 == name) 1062 { 1063 r.intersect (op1_range); 1064 if (idx) 1065 tracer.trailer (idx, "produces ", true, name, r); 1066 return true; 1067 } 1068 // If the calculation continues, we're using op1_range as the new LHS. 1069 op1_range.intersect (r); 1070 1071 if (idx) 1072 tracer.trailer (idx, "produces ", true, op1, op1_range); 1073 gimple *src_stmt = SSA_NAME_DEF_STMT (op1); 1074 gcc_checking_assert (src_stmt); 1075 1076 // Then feed this range back as the LHS of the defining statement. 1077 return compute_operand_range (r, src_stmt, op1_range, name, src); 1078} 1079 1080 1081// Calculate a range for NAME from the operand 2 position of S 1082// assuming the result of the statement is LHS. Return the range in 1083// R, or false if no range could be calculated. 1084 1085bool 1086gori_compute::compute_operand2_range (irange &r, gimple *stmt, 1087 const irange &lhs, tree name, 1088 fur_source &src) 1089{ 1090 int_range_max op1_range, op2_range; 1091 tree op1 = gimple_range_operand1 (stmt); 1092 tree op2 = gimple_range_operand2 (stmt); 1093 1094 src.get_operand (op1_range, op1); 1095 src.get_operand (op2_range, op2); 1096 1097 // Intersect with range for op2 based on lhs and op1. 1098 if (!gimple_range_calc_op2 (r, stmt, lhs, op1_range)) 1099 return false; 1100 1101 unsigned idx; 1102 if ((idx = tracer.header ("compute op 2 ("))) 1103 { 1104 print_generic_expr (dump_file, op2, TDF_SLIM); 1105 fprintf (dump_file, ") at "); 1106 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1107 tracer.print (idx, "LHS = "); 1108 lhs.dump (dump_file); 1109 if (TREE_CODE (op1) == SSA_NAME) 1110 { 1111 fprintf (dump_file, ", "); 1112 print_generic_expr (dump_file, op1, TDF_SLIM); 1113 fprintf (dump_file, " = "); 1114 op1_range.dump (dump_file); 1115 } 1116 fprintf (dump_file, "\n"); 1117 tracer.print (idx, "Computes "); 1118 print_generic_expr (dump_file, op2, TDF_SLIM); 1119 fprintf (dump_file, " = "); 1120 r.dump (dump_file); 1121 fprintf (dump_file, " intersect Known range : "); 1122 op2_range.dump (dump_file); 1123 fputc ('\n', dump_file); 1124 } 1125 // Intersect the calculated result with the known result and return if done. 1126 if (op2 == name) 1127 { 1128 r.intersect (op2_range); 1129 if (idx) 1130 tracer.trailer (idx, " produces ", true, NULL_TREE, r); 1131 return true; 1132 } 1133 // If the calculation continues, we're using op2_range as the new LHS. 1134 op2_range.intersect (r); 1135 1136 if (idx) 1137 tracer.trailer (idx, " produces ", true, op2, op2_range); 1138 gimple *src_stmt = SSA_NAME_DEF_STMT (op2); 1139 gcc_checking_assert (src_stmt); 1140// gcc_checking_assert (!is_import_p (op2, find.bb)); 1141 1142 // Then feed this range back as the LHS of the defining statement. 1143 return compute_operand_range (r, src_stmt, op2_range, name, src); 1144} 1145 1146// Calculate a range for NAME from both operand positions of S 1147// assuming the result of the statement is LHS. Return the range in 1148// R, or false if no range could be calculated. 1149 1150bool 1151gori_compute::compute_operand1_and_operand2_range (irange &r, 1152 gimple *stmt, 1153 const irange &lhs, 1154 tree name, 1155 fur_source &src) 1156{ 1157 int_range_max op_range; 1158 1159 // Calculate a good a range for op2. Since op1 == op2, this will 1160 // have already included whatever the actual range of name is. 1161 if (!compute_operand2_range (op_range, stmt, lhs, name, src)) 1162 return false; 1163 1164 // Now get the range thru op1. 1165 if (!compute_operand1_range (r, stmt, lhs, name, src)) 1166 return false; 1167 1168 // Both operands have to be simultaneously true, so perform an intersection. 1169 r.intersect (op_range); 1170 return true; 1171} 1172 1173// Return TRUE if NAME can be recomputed on any edge exiting BB. If any 1174// direct dependant is exported, it may also change the computed value of NAME. 1175 1176bool 1177gori_compute::may_recompute_p (tree name, basic_block bb) 1178{ 1179 tree dep1 = depend1 (name); 1180 tree dep2 = depend2 (name); 1181 1182 // If the first dependency is not set, there is no recompuation. 1183 if (!dep1) 1184 return false; 1185 1186 // Don't recalculate PHIs or statements with side_effects. 1187 gimple *s = SSA_NAME_DEF_STMT (name); 1188 if (is_a<gphi *> (s) || gimple_has_side_effects (s)) 1189 return false; 1190 1191 // If edge is specified, check if NAME can be recalculated on that edge. 1192 if (bb) 1193 return ((is_export_p (dep1, bb)) 1194 || (dep2 && is_export_p (dep2, bb))); 1195 1196 return (is_export_p (dep1)) || (dep2 && is_export_p (dep2)); 1197} 1198 1199// Return TRUE if NAME can be recomputed on edge E. If any direct dependant 1200// is exported on edge E, it may change the computed value of NAME. 1201 1202bool 1203gori_compute::may_recompute_p (tree name, edge e) 1204{ 1205 gcc_checking_assert (e); 1206 return may_recompute_p (name, e->src); 1207} 1208 1209 1210// Return TRUE if a range can be calculated or recomputed for NAME on any 1211// edge exiting BB. 1212 1213bool 1214gori_compute::has_edge_range_p (tree name, basic_block bb) 1215{ 1216 // Check if NAME is an export or can be recomputed. 1217 if (bb) 1218 return is_export_p (name, bb) || may_recompute_p (name, bb); 1219 1220 // If no block is specified, check for anywhere in the IL. 1221 return is_export_p (name) || may_recompute_p (name); 1222} 1223 1224// Return TRUE if a range can be calculated or recomputed for NAME on edge E. 1225 1226bool 1227gori_compute::has_edge_range_p (tree name, edge e) 1228{ 1229 gcc_checking_assert (e); 1230 return has_edge_range_p (name, e->src); 1231} 1232 1233// Calculate a range on edge E and return it in R. Try to evaluate a 1234// range for NAME on this edge. Return FALSE if this is either not a 1235// control edge or NAME is not defined by this edge. 1236 1237bool 1238gori_compute::outgoing_edge_range_p (irange &r, edge e, tree name, 1239 range_query &q) 1240{ 1241 int_range_max lhs; 1242 unsigned idx; 1243 1244 if ((e->flags & m_not_executable_flag)) 1245 { 1246 r.set_undefined (); 1247 if (dump_file && (dump_flags & TDF_DETAILS)) 1248 fprintf (dump_file, "Outgoing edge %d->%d unexecutable.\n", 1249 e->src->index, e->dest->index); 1250 return true; 1251 } 1252 1253 gcc_checking_assert (gimple_range_ssa_p (name)); 1254 // Determine if there is an outgoing edge. 1255 gimple *stmt = outgoing.edge_range_p (lhs, e); 1256 if (!stmt) 1257 return false; 1258 1259 fur_stmt src (stmt, &q); 1260 // If NAME can be calculated on the edge, use that. 1261 if (is_export_p (name, e->src)) 1262 { 1263 bool res; 1264 if ((idx = tracer.header ("outgoing_edge"))) 1265 { 1266 fprintf (dump_file, " for "); 1267 print_generic_expr (dump_file, name, TDF_SLIM); 1268 fprintf (dump_file, " on edge %d->%d\n", 1269 e->src->index, e->dest->index); 1270 } 1271 if ((res = compute_operand_range (r, stmt, lhs, name, src))) 1272 { 1273 // Sometimes compatible types get interchanged. See PR97360. 1274 // Make sure we are returning the type of the thing we asked for. 1275 if (!r.undefined_p () && r.type () != TREE_TYPE (name)) 1276 { 1277 gcc_checking_assert (range_compatible_p (r.type (), 1278 TREE_TYPE (name))); 1279 range_cast (r, TREE_TYPE (name)); 1280 } 1281 } 1282 if (idx) 1283 tracer.trailer (idx, "outgoing_edge", res, name, r); 1284 return res; 1285 } 1286 // If NAME isn't exported, check if it can be recomputed. 1287 else if (may_recompute_p (name, e)) 1288 { 1289 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 1290 1291 if ((idx = tracer.header ("recomputation"))) 1292 { 1293 fprintf (dump_file, " attempt on edge %d->%d for ", 1294 e->src->index, e->dest->index); 1295 print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM); 1296 } 1297 // Simply calculate DEF_STMT on edge E using the range query Q. 1298 fold_range (r, def_stmt, e, &q); 1299 if (idx) 1300 tracer.trailer (idx, "recomputation", true, name, r); 1301 return true; 1302 } 1303 return false; 1304} 1305 1306// Given COND ? OP1 : OP2 with ranges R1 for OP1 and R2 for OP2, Use gori 1307// to further resolve R1 and R2 if there are any dependencies between 1308// OP1 and COND or OP2 and COND. All values can are to be calculated using SRC 1309// as the origination source location for operands.. 1310// Effectively, use COND an the edge condition and solve for OP1 on the true 1311// edge and OP2 on the false edge. 1312 1313bool 1314gori_compute::condexpr_adjust (irange &r1, irange &r2, gimple *, tree cond, 1315 tree op1, tree op2, fur_source &src) 1316{ 1317 int_range_max tmp, cond_true, cond_false; 1318 tree ssa1 = gimple_range_ssa_p (op1); 1319 tree ssa2 = gimple_range_ssa_p (op2); 1320 if (!ssa1 && !ssa2) 1321 return false; 1322 if (!COMPARISON_CLASS_P (cond)) 1323 return false; 1324 tree type = TREE_TYPE (TREE_OPERAND (cond, 0)); 1325 if (!range_compatible_p (type, TREE_TYPE (TREE_OPERAND (cond, 1)))) 1326 return false; 1327 range_operator *hand = range_op_handler (TREE_CODE (cond), type); 1328 if (!hand) 1329 return false; 1330 1331 tree c1 = gimple_range_ssa_p (TREE_OPERAND (cond, 0)); 1332 tree c2 = gimple_range_ssa_p (TREE_OPERAND (cond, 1)); 1333 1334 // Only solve if there is one SSA name in the condition. 1335 if ((!c1 && !c2) || (c1 && c2)) 1336 return false; 1337 1338 // Pick up the current values of each part of the condition. 1339 int_range_max cl, cr; 1340 src.get_operand (cl, TREE_OPERAND (cond, 0)); 1341 src.get_operand (cr, TREE_OPERAND (cond, 1)); 1342 1343 tree cond_name = c1 ? c1 : c2; 1344 gimple *def_stmt = SSA_NAME_DEF_STMT (cond_name); 1345 1346 // Evaluate the value of COND_NAME on the true and false edges, using either 1347 // the op1 or op2 routines based on its location. 1348 if (c1) 1349 { 1350 if (!hand->op1_range (cond_false, type, m_bool_zero, cr)) 1351 return false; 1352 if (!hand->op1_range (cond_true, type, m_bool_one, cr)) 1353 return false; 1354 cond_false.intersect (cl); 1355 cond_true.intersect (cl); 1356 } 1357 else 1358 { 1359 if (!hand->op2_range (cond_false, type, m_bool_zero, cl)) 1360 return false; 1361 if (!hand->op2_range (cond_true, type, m_bool_one, cl)) 1362 return false; 1363 cond_false.intersect (cr); 1364 cond_true.intersect (cr); 1365 } 1366 1367 unsigned idx; 1368 if ((idx = tracer.header ("cond_expr evaluation : "))) 1369 { 1370 fprintf (dump_file, " range1 = "); 1371 r1.dump (dump_file); 1372 fprintf (dump_file, ", range2 = "); 1373 r1.dump (dump_file); 1374 fprintf (dump_file, "\n"); 1375 } 1376 1377 // Now solve for SSA1 or SSA2 if they are in the dependency chain. 1378 if (ssa1 && in_chain_p (ssa1, cond_name)) 1379 { 1380 if (compute_operand_range (tmp, def_stmt, cond_true, ssa1, src)) 1381 r1.intersect (tmp); 1382 } 1383 if (ssa2 && in_chain_p (ssa2, cond_name)) 1384 { 1385 if (compute_operand_range (tmp, def_stmt, cond_false, ssa2, src)) 1386 r2.intersect (tmp); 1387 } 1388 if (idx) 1389 { 1390 tracer.print (idx, "outgoing: range1 = "); 1391 r1.dump (dump_file); 1392 fprintf (dump_file, ", range2 = "); 1393 r1.dump (dump_file); 1394 fprintf (dump_file, "\n"); 1395 tracer.trailer (idx, "cond_expr", true, cond_name, cond_true); 1396 } 1397 return true; 1398} 1399 1400// Dump what is known to GORI computes to listing file F. 1401 1402void 1403gori_compute::dump (FILE *f) 1404{ 1405 gori_map::dump (f); 1406} 1407 1408// ------------------------------------------------------------------------ 1409// GORI iterator. Although we have bitmap iterators, don't expose that it 1410// is currently a bitmap. Use an export iterator to hide future changes. 1411 1412// Construct a basic iterator over an export bitmap. 1413 1414gori_export_iterator::gori_export_iterator (bitmap b) 1415{ 1416 bm = b; 1417 if (b) 1418 bmp_iter_set_init (&bi, b, 1, &y); 1419} 1420 1421 1422// Move to the next export bitmap spot. 1423 1424void 1425gori_export_iterator::next () 1426{ 1427 bmp_iter_next (&bi, &y); 1428} 1429 1430 1431// Fetch the name of the next export in the export list. Return NULL if 1432// iteration is done. 1433 1434tree 1435gori_export_iterator::get_name () 1436{ 1437 if (!bm) 1438 return NULL_TREE; 1439 1440 while (bmp_iter_set (&bi, &y)) 1441 { 1442 tree t = ssa_name (y); 1443 if (t) 1444 return t; 1445 next (); 1446 } 1447 return NULL_TREE; 1448} 1449