1169689Skan/* Induction variable optimizations. 2169689Skan Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify it 7169689Skanunder the terms of the GNU General Public License as published by the 8169689SkanFree Software Foundation; either version 2, or (at your option) any 9169689Skanlater version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT 12169689SkanANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14169689Skanfor more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20169689Skan 21169689Skan/* This pass tries to find the optimal set of induction variables for the loop. 22169689Skan It optimizes just the basic linear induction variables (although adding 23169689Skan support for other types should not be too hard). It includes the 24169689Skan optimizations commonly known as strength reduction, induction variable 25169689Skan coalescing and induction variable elimination. It does it in the 26169689Skan following steps: 27169689Skan 28169689Skan 1) The interesting uses of induction variables are found. This includes 29169689Skan 30169689Skan -- uses of induction variables in non-linear expressions 31169689Skan -- addresses of arrays 32169689Skan -- comparisons of induction variables 33169689Skan 34169689Skan 2) Candidates for the induction variables are found. This includes 35169689Skan 36169689Skan -- old induction variables 37169689Skan -- the variables defined by expressions derived from the "interesting 38169689Skan uses" above 39169689Skan 40169689Skan 3) The optimal (w.r. to a cost function) set of variables is chosen. The 41169689Skan cost function assigns a cost to sets of induction variables and consists 42169689Skan of three parts: 43169689Skan 44169689Skan -- The use costs. Each of the interesting uses chooses the best induction 45169689Skan variable in the set and adds its cost to the sum. The cost reflects 46169689Skan the time spent on modifying the induction variables value to be usable 47169689Skan for the given purpose (adding base and offset for arrays, etc.). 48169689Skan -- The variable costs. Each of the variables has a cost assigned that 49169689Skan reflects the costs associated with incrementing the value of the 50169689Skan variable. The original variables are somewhat preferred. 51169689Skan -- The set cost. Depending on the size of the set, extra cost may be 52169689Skan added to reflect register pressure. 53169689Skan 54169689Skan All the costs are defined in a machine-specific way, using the target 55169689Skan hooks and machine descriptions to determine them. 56169689Skan 57169689Skan 4) The trees are transformed to use the new variables, the dead code is 58169689Skan removed. 59169689Skan 60169689Skan All of this is done loop by loop. Doing it globally is theoretically 61169689Skan possible, it might give a better performance and it might enable us 62169689Skan to decide costs more precisely, but getting all the interactions right 63169689Skan would be complicated. */ 64169689Skan 65169689Skan#include "config.h" 66169689Skan#include "system.h" 67169689Skan#include "coretypes.h" 68169689Skan#include "tm.h" 69169689Skan#include "tree.h" 70169689Skan#include "rtl.h" 71169689Skan#include "tm_p.h" 72169689Skan#include "hard-reg-set.h" 73169689Skan#include "basic-block.h" 74169689Skan#include "output.h" 75169689Skan#include "diagnostic.h" 76169689Skan#include "tree-flow.h" 77169689Skan#include "tree-dump.h" 78169689Skan#include "timevar.h" 79169689Skan#include "cfgloop.h" 80169689Skan#include "varray.h" 81169689Skan#include "expr.h" 82169689Skan#include "tree-pass.h" 83169689Skan#include "ggc.h" 84169689Skan#include "insn-config.h" 85169689Skan#include "recog.h" 86169689Skan#include "hashtab.h" 87169689Skan#include "tree-chrec.h" 88169689Skan#include "tree-scalar-evolution.h" 89169689Skan#include "cfgloop.h" 90169689Skan#include "params.h" 91169689Skan#include "langhooks.h" 92169689Skan 93169689Skan/* The infinite cost. */ 94169689Skan#define INFTY 10000000 95169689Skan 96169689Skan/* The expected number of loop iterations. TODO -- use profiling instead of 97169689Skan this. */ 98169689Skan#define AVG_LOOP_NITER(LOOP) 5 99169689Skan 100169689Skan 101169689Skan/* Representation of the induction variable. */ 102169689Skanstruct iv 103169689Skan{ 104169689Skan tree base; /* Initial value of the iv. */ 105169689Skan tree base_object; /* A memory object to that the induction variable points. */ 106169689Skan tree step; /* Step of the iv (constant only). */ 107169689Skan tree ssa_name; /* The ssa name with the value. */ 108169689Skan bool biv_p; /* Is it a biv? */ 109169689Skan bool have_use_for; /* Do we already have a use for it? */ 110169689Skan unsigned use_id; /* The identifier in the use if it is the case. */ 111169689Skan}; 112169689Skan 113169689Skan/* Per-ssa version information (induction variable descriptions, etc.). */ 114169689Skanstruct version_info 115169689Skan{ 116169689Skan tree name; /* The ssa name. */ 117169689Skan struct iv *iv; /* Induction variable description. */ 118169689Skan bool has_nonlin_use; /* For a loop-level invariant, whether it is used in 119169689Skan an expression that is not an induction variable. */ 120169689Skan unsigned inv_id; /* Id of an invariant. */ 121169689Skan bool preserve_biv; /* For the original biv, whether to preserve it. */ 122169689Skan}; 123169689Skan 124169689Skan/* Types of uses. */ 125169689Skanenum use_type 126169689Skan{ 127169689Skan USE_NONLINEAR_EXPR, /* Use in a nonlinear expression. */ 128169689Skan USE_ADDRESS, /* Use in an address. */ 129169689Skan USE_COMPARE /* Use is a compare. */ 130169689Skan}; 131169689Skan 132169689Skan/* The candidate - cost pair. */ 133169689Skanstruct cost_pair 134169689Skan{ 135169689Skan struct iv_cand *cand; /* The candidate. */ 136169689Skan unsigned cost; /* The cost. */ 137169689Skan bitmap depends_on; /* The list of invariants that have to be 138169689Skan preserved. */ 139169689Skan tree value; /* For final value elimination, the expression for 140169689Skan the final value of the iv. For iv elimination, 141169689Skan the new bound to compare with. */ 142169689Skan}; 143169689Skan 144169689Skan/* Use. */ 145169689Skanstruct iv_use 146169689Skan{ 147169689Skan unsigned id; /* The id of the use. */ 148169689Skan enum use_type type; /* Type of the use. */ 149169689Skan struct iv *iv; /* The induction variable it is based on. */ 150169689Skan tree stmt; /* Statement in that it occurs. */ 151169689Skan tree *op_p; /* The place where it occurs. */ 152169689Skan bitmap related_cands; /* The set of "related" iv candidates, plus the common 153169689Skan important ones. */ 154169689Skan 155169689Skan unsigned n_map_members; /* Number of candidates in the cost_map list. */ 156169689Skan struct cost_pair *cost_map; 157169689Skan /* The costs wrto the iv candidates. */ 158169689Skan 159169689Skan struct iv_cand *selected; 160169689Skan /* The selected candidate. */ 161169689Skan}; 162169689Skan 163169689Skan/* The position where the iv is computed. */ 164169689Skanenum iv_position 165169689Skan{ 166169689Skan IP_NORMAL, /* At the end, just before the exit condition. */ 167169689Skan IP_END, /* At the end of the latch block. */ 168169689Skan IP_ORIGINAL /* The original biv. */ 169169689Skan}; 170169689Skan 171169689Skan/* The induction variable candidate. */ 172169689Skanstruct iv_cand 173169689Skan{ 174169689Skan unsigned id; /* The number of the candidate. */ 175169689Skan bool important; /* Whether this is an "important" candidate, i.e. such 176169689Skan that it should be considered by all uses. */ 177169689Skan enum iv_position pos; /* Where it is computed. */ 178169689Skan tree incremented_at; /* For original biv, the statement where it is 179169689Skan incremented. */ 180169689Skan tree var_before; /* The variable used for it before increment. */ 181169689Skan tree var_after; /* The variable used for it after increment. */ 182169689Skan struct iv *iv; /* The value of the candidate. NULL for 183169689Skan "pseudocandidate" used to indicate the possibility 184169689Skan to replace the final value of an iv by direct 185169689Skan computation of the value. */ 186169689Skan unsigned cost; /* Cost of the candidate. */ 187169689Skan bitmap depends_on; /* The list of invariants that are used in step of the 188169689Skan biv. */ 189169689Skan}; 190169689Skan 191169689Skan/* The data used by the induction variable optimizations. */ 192169689Skan 193169689Skantypedef struct iv_use *iv_use_p; 194169689SkanDEF_VEC_P(iv_use_p); 195169689SkanDEF_VEC_ALLOC_P(iv_use_p,heap); 196169689Skan 197169689Skantypedef struct iv_cand *iv_cand_p; 198169689SkanDEF_VEC_P(iv_cand_p); 199169689SkanDEF_VEC_ALLOC_P(iv_cand_p,heap); 200169689Skan 201169689Skanstruct ivopts_data 202169689Skan{ 203169689Skan /* The currently optimized loop. */ 204169689Skan struct loop *current_loop; 205169689Skan 206169689Skan /* Number of registers used in it. */ 207169689Skan unsigned regs_used; 208169689Skan 209169689Skan /* Numbers of iterations for all exits of the current loop. */ 210169689Skan htab_t niters; 211169689Skan 212169689Skan /* The size of version_info array allocated. */ 213169689Skan unsigned version_info_size; 214169689Skan 215169689Skan /* The array of information for the ssa names. */ 216169689Skan struct version_info *version_info; 217169689Skan 218169689Skan /* The bitmap of indices in version_info whose value was changed. */ 219169689Skan bitmap relevant; 220169689Skan 221169689Skan /* The maximum invariant id. */ 222169689Skan unsigned max_inv_id; 223169689Skan 224169689Skan /* The uses of induction variables. */ 225169689Skan VEC(iv_use_p,heap) *iv_uses; 226169689Skan 227169689Skan /* The candidates. */ 228169689Skan VEC(iv_cand_p,heap) *iv_candidates; 229169689Skan 230169689Skan /* A bitmap of important candidates. */ 231169689Skan bitmap important_candidates; 232169689Skan 233169689Skan /* Whether to consider just related and important candidates when replacing a 234169689Skan use. */ 235169689Skan bool consider_all_candidates; 236169689Skan}; 237169689Skan 238169689Skan/* An assignment of iv candidates to uses. */ 239169689Skan 240169689Skanstruct iv_ca 241169689Skan{ 242169689Skan /* The number of uses covered by the assignment. */ 243169689Skan unsigned upto; 244169689Skan 245169689Skan /* Number of uses that cannot be expressed by the candidates in the set. */ 246169689Skan unsigned bad_uses; 247169689Skan 248169689Skan /* Candidate assigned to a use, together with the related costs. */ 249169689Skan struct cost_pair **cand_for_use; 250169689Skan 251169689Skan /* Number of times each candidate is used. */ 252169689Skan unsigned *n_cand_uses; 253169689Skan 254169689Skan /* The candidates used. */ 255169689Skan bitmap cands; 256169689Skan 257169689Skan /* The number of candidates in the set. */ 258169689Skan unsigned n_cands; 259169689Skan 260169689Skan /* Total number of registers needed. */ 261169689Skan unsigned n_regs; 262169689Skan 263169689Skan /* Total cost of expressing uses. */ 264169689Skan unsigned cand_use_cost; 265169689Skan 266169689Skan /* Total cost of candidates. */ 267169689Skan unsigned cand_cost; 268169689Skan 269169689Skan /* Number of times each invariant is used. */ 270169689Skan unsigned *n_invariant_uses; 271169689Skan 272169689Skan /* Total cost of the assignment. */ 273169689Skan unsigned cost; 274169689Skan}; 275169689Skan 276169689Skan/* Difference of two iv candidate assignments. */ 277169689Skan 278169689Skanstruct iv_ca_delta 279169689Skan{ 280169689Skan /* Changed use. */ 281169689Skan struct iv_use *use; 282169689Skan 283169689Skan /* An old assignment (for rollback purposes). */ 284169689Skan struct cost_pair *old_cp; 285169689Skan 286169689Skan /* A new assignment. */ 287169689Skan struct cost_pair *new_cp; 288169689Skan 289169689Skan /* Next change in the list. */ 290169689Skan struct iv_ca_delta *next_change; 291169689Skan}; 292169689Skan 293169689Skan/* Bound on number of candidates below that all candidates are considered. */ 294169689Skan 295169689Skan#define CONSIDER_ALL_CANDIDATES_BOUND \ 296169689Skan ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND)) 297169689Skan 298169689Skan/* If there are more iv occurrences, we just give up (it is quite unlikely that 299169689Skan optimizing such a loop would help, and it would take ages). */ 300169689Skan 301169689Skan#define MAX_CONSIDERED_USES \ 302169689Skan ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES)) 303169689Skan 304169689Skan/* If there are at most this number of ivs in the set, try removing unnecessary 305169689Skan ivs from the set always. */ 306169689Skan 307169689Skan#define ALWAYS_PRUNE_CAND_SET_BOUND \ 308169689Skan ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND)) 309169689Skan 310169689Skan/* The list of trees for that the decl_rtl field must be reset is stored 311169689Skan here. */ 312169689Skan 313169689Skanstatic VEC(tree,heap) *decl_rtl_to_reset; 314169689Skan 315169689Skan/* Number of uses recorded in DATA. */ 316169689Skan 317169689Skanstatic inline unsigned 318169689Skann_iv_uses (struct ivopts_data *data) 319169689Skan{ 320169689Skan return VEC_length (iv_use_p, data->iv_uses); 321169689Skan} 322169689Skan 323169689Skan/* Ith use recorded in DATA. */ 324169689Skan 325169689Skanstatic inline struct iv_use * 326169689Skaniv_use (struct ivopts_data *data, unsigned i) 327169689Skan{ 328169689Skan return VEC_index (iv_use_p, data->iv_uses, i); 329169689Skan} 330169689Skan 331169689Skan/* Number of candidates recorded in DATA. */ 332169689Skan 333169689Skanstatic inline unsigned 334169689Skann_iv_cands (struct ivopts_data *data) 335169689Skan{ 336169689Skan return VEC_length (iv_cand_p, data->iv_candidates); 337169689Skan} 338169689Skan 339169689Skan/* Ith candidate recorded in DATA. */ 340169689Skan 341169689Skanstatic inline struct iv_cand * 342169689Skaniv_cand (struct ivopts_data *data, unsigned i) 343169689Skan{ 344169689Skan return VEC_index (iv_cand_p, data->iv_candidates, i); 345169689Skan} 346169689Skan 347169689Skan/* The single loop exit if it dominates the latch, NULL otherwise. */ 348169689Skan 349169689Skanedge 350169689Skansingle_dom_exit (struct loop *loop) 351169689Skan{ 352169689Skan edge exit = loop->single_exit; 353169689Skan 354169689Skan if (!exit) 355169689Skan return NULL; 356169689Skan 357169689Skan if (!just_once_each_iteration_p (loop, exit->src)) 358169689Skan return NULL; 359169689Skan 360169689Skan return exit; 361169689Skan} 362169689Skan 363169689Skan/* Dumps information about the induction variable IV to FILE. */ 364169689Skan 365169689Skanextern void dump_iv (FILE *, struct iv *); 366169689Skanvoid 367169689Skandump_iv (FILE *file, struct iv *iv) 368169689Skan{ 369169689Skan if (iv->ssa_name) 370169689Skan { 371169689Skan fprintf (file, "ssa name "); 372169689Skan print_generic_expr (file, iv->ssa_name, TDF_SLIM); 373169689Skan fprintf (file, "\n"); 374169689Skan } 375169689Skan 376169689Skan fprintf (file, " type "); 377169689Skan print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM); 378169689Skan fprintf (file, "\n"); 379169689Skan 380169689Skan if (iv->step) 381169689Skan { 382169689Skan fprintf (file, " base "); 383169689Skan print_generic_expr (file, iv->base, TDF_SLIM); 384169689Skan fprintf (file, "\n"); 385169689Skan 386169689Skan fprintf (file, " step "); 387169689Skan print_generic_expr (file, iv->step, TDF_SLIM); 388169689Skan fprintf (file, "\n"); 389169689Skan } 390169689Skan else 391169689Skan { 392169689Skan fprintf (file, " invariant "); 393169689Skan print_generic_expr (file, iv->base, TDF_SLIM); 394169689Skan fprintf (file, "\n"); 395169689Skan } 396169689Skan 397169689Skan if (iv->base_object) 398169689Skan { 399169689Skan fprintf (file, " base object "); 400169689Skan print_generic_expr (file, iv->base_object, TDF_SLIM); 401169689Skan fprintf (file, "\n"); 402169689Skan } 403169689Skan 404169689Skan if (iv->biv_p) 405169689Skan fprintf (file, " is a biv\n"); 406169689Skan} 407169689Skan 408169689Skan/* Dumps information about the USE to FILE. */ 409169689Skan 410169689Skanextern void dump_use (FILE *, struct iv_use *); 411169689Skanvoid 412169689Skandump_use (FILE *file, struct iv_use *use) 413169689Skan{ 414169689Skan fprintf (file, "use %d\n", use->id); 415169689Skan 416169689Skan switch (use->type) 417169689Skan { 418169689Skan case USE_NONLINEAR_EXPR: 419169689Skan fprintf (file, " generic\n"); 420169689Skan break; 421169689Skan 422169689Skan case USE_ADDRESS: 423169689Skan fprintf (file, " address\n"); 424169689Skan break; 425169689Skan 426169689Skan case USE_COMPARE: 427169689Skan fprintf (file, " compare\n"); 428169689Skan break; 429169689Skan 430169689Skan default: 431169689Skan gcc_unreachable (); 432169689Skan } 433169689Skan 434169689Skan fprintf (file, " in statement "); 435169689Skan print_generic_expr (file, use->stmt, TDF_SLIM); 436169689Skan fprintf (file, "\n"); 437169689Skan 438169689Skan fprintf (file, " at position "); 439169689Skan if (use->op_p) 440169689Skan print_generic_expr (file, *use->op_p, TDF_SLIM); 441169689Skan fprintf (file, "\n"); 442169689Skan 443169689Skan dump_iv (file, use->iv); 444169689Skan 445169689Skan if (use->related_cands) 446169689Skan { 447169689Skan fprintf (file, " related candidates "); 448169689Skan dump_bitmap (file, use->related_cands); 449169689Skan } 450169689Skan} 451169689Skan 452169689Skan/* Dumps information about the uses to FILE. */ 453169689Skan 454169689Skanextern void dump_uses (FILE *, struct ivopts_data *); 455169689Skanvoid 456169689Skandump_uses (FILE *file, struct ivopts_data *data) 457169689Skan{ 458169689Skan unsigned i; 459169689Skan struct iv_use *use; 460169689Skan 461169689Skan for (i = 0; i < n_iv_uses (data); i++) 462169689Skan { 463169689Skan use = iv_use (data, i); 464169689Skan 465169689Skan dump_use (file, use); 466169689Skan fprintf (file, "\n"); 467169689Skan } 468169689Skan} 469169689Skan 470169689Skan/* Dumps information about induction variable candidate CAND to FILE. */ 471169689Skan 472169689Skanextern void dump_cand (FILE *, struct iv_cand *); 473169689Skanvoid 474169689Skandump_cand (FILE *file, struct iv_cand *cand) 475169689Skan{ 476169689Skan struct iv *iv = cand->iv; 477169689Skan 478169689Skan fprintf (file, "candidate %d%s\n", 479169689Skan cand->id, cand->important ? " (important)" : ""); 480169689Skan 481169689Skan if (cand->depends_on) 482169689Skan { 483169689Skan fprintf (file, " depends on "); 484169689Skan dump_bitmap (file, cand->depends_on); 485169689Skan } 486169689Skan 487169689Skan if (!iv) 488169689Skan { 489169689Skan fprintf (file, " final value replacement\n"); 490169689Skan return; 491169689Skan } 492169689Skan 493169689Skan switch (cand->pos) 494169689Skan { 495169689Skan case IP_NORMAL: 496169689Skan fprintf (file, " incremented before exit test\n"); 497169689Skan break; 498169689Skan 499169689Skan case IP_END: 500169689Skan fprintf (file, " incremented at end\n"); 501169689Skan break; 502169689Skan 503169689Skan case IP_ORIGINAL: 504169689Skan fprintf (file, " original biv\n"); 505169689Skan break; 506169689Skan } 507169689Skan 508169689Skan dump_iv (file, iv); 509169689Skan} 510169689Skan 511169689Skan/* Returns the info for ssa version VER. */ 512169689Skan 513169689Skanstatic inline struct version_info * 514169689Skanver_info (struct ivopts_data *data, unsigned ver) 515169689Skan{ 516169689Skan return data->version_info + ver; 517169689Skan} 518169689Skan 519169689Skan/* Returns the info for ssa name NAME. */ 520169689Skan 521169689Skanstatic inline struct version_info * 522169689Skanname_info (struct ivopts_data *data, tree name) 523169689Skan{ 524169689Skan return ver_info (data, SSA_NAME_VERSION (name)); 525169689Skan} 526169689Skan 527169689Skan/* Checks whether there exists number X such that X * B = A, counting modulo 528169689Skan 2^BITS. */ 529169689Skan 530169689Skanstatic bool 531169689Skandivide (unsigned bits, unsigned HOST_WIDE_INT a, unsigned HOST_WIDE_INT b, 532169689Skan HOST_WIDE_INT *x) 533169689Skan{ 534169689Skan unsigned HOST_WIDE_INT mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1); 535169689Skan unsigned HOST_WIDE_INT inv, ex, val; 536169689Skan unsigned i; 537169689Skan 538169689Skan a &= mask; 539169689Skan b &= mask; 540169689Skan 541169689Skan /* First divide the whole equation by 2 as long as possible. */ 542169689Skan while (!(a & 1) && !(b & 1)) 543169689Skan { 544169689Skan a >>= 1; 545169689Skan b >>= 1; 546169689Skan bits--; 547169689Skan mask >>= 1; 548169689Skan } 549169689Skan 550169689Skan if (!(b & 1)) 551169689Skan { 552169689Skan /* If b is still even, a is odd and there is no such x. */ 553169689Skan return false; 554169689Skan } 555169689Skan 556169689Skan /* Find the inverse of b. We compute it as 557169689Skan b^(2^(bits - 1) - 1) (mod 2^bits). */ 558169689Skan inv = 1; 559169689Skan ex = b; 560169689Skan for (i = 0; i < bits - 1; i++) 561169689Skan { 562169689Skan inv = (inv * ex) & mask; 563169689Skan ex = (ex * ex) & mask; 564169689Skan } 565169689Skan 566169689Skan val = (a * inv) & mask; 567169689Skan 568169689Skan gcc_assert (((val * b) & mask) == a); 569169689Skan 570169689Skan if ((val >> (bits - 1)) & 1) 571169689Skan val |= ~mask; 572169689Skan 573169689Skan *x = val; 574169689Skan 575169689Skan return true; 576169689Skan} 577169689Skan 578169689Skan/* Returns true if STMT is after the place where the IP_NORMAL ivs will be 579169689Skan emitted in LOOP. */ 580169689Skan 581169689Skanstatic bool 582169689Skanstmt_after_ip_normal_pos (struct loop *loop, tree stmt) 583169689Skan{ 584169689Skan basic_block bb = ip_normal_pos (loop), sbb = bb_for_stmt (stmt); 585169689Skan 586169689Skan gcc_assert (bb); 587169689Skan 588169689Skan if (sbb == loop->latch) 589169689Skan return true; 590169689Skan 591169689Skan if (sbb != bb) 592169689Skan return false; 593169689Skan 594169689Skan return stmt == last_stmt (bb); 595169689Skan} 596169689Skan 597169689Skan/* Returns true if STMT if after the place where the original induction 598169689Skan variable CAND is incremented. */ 599169689Skan 600169689Skanstatic bool 601169689Skanstmt_after_ip_original_pos (struct iv_cand *cand, tree stmt) 602169689Skan{ 603169689Skan basic_block cand_bb = bb_for_stmt (cand->incremented_at); 604169689Skan basic_block stmt_bb = bb_for_stmt (stmt); 605169689Skan block_stmt_iterator bsi; 606169689Skan 607169689Skan if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb)) 608169689Skan return false; 609169689Skan 610169689Skan if (stmt_bb != cand_bb) 611169689Skan return true; 612169689Skan 613169689Skan /* Scan the block from the end, since the original ivs are usually 614169689Skan incremented at the end of the loop body. */ 615169689Skan for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi)) 616169689Skan { 617169689Skan if (bsi_stmt (bsi) == cand->incremented_at) 618169689Skan return false; 619169689Skan if (bsi_stmt (bsi) == stmt) 620169689Skan return true; 621169689Skan } 622169689Skan} 623169689Skan 624169689Skan/* Returns true if STMT if after the place where the induction variable 625169689Skan CAND is incremented in LOOP. */ 626169689Skan 627169689Skanstatic bool 628169689Skanstmt_after_increment (struct loop *loop, struct iv_cand *cand, tree stmt) 629169689Skan{ 630169689Skan switch (cand->pos) 631169689Skan { 632169689Skan case IP_END: 633169689Skan return false; 634169689Skan 635169689Skan case IP_NORMAL: 636169689Skan return stmt_after_ip_normal_pos (loop, stmt); 637169689Skan 638169689Skan case IP_ORIGINAL: 639169689Skan return stmt_after_ip_original_pos (cand, stmt); 640169689Skan 641169689Skan default: 642169689Skan gcc_unreachable (); 643169689Skan } 644169689Skan} 645169689Skan 646169689Skan/* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */ 647169689Skan 648169689Skanstatic bool 649169689Skanabnormal_ssa_name_p (tree exp) 650169689Skan{ 651169689Skan if (!exp) 652169689Skan return false; 653169689Skan 654169689Skan if (TREE_CODE (exp) != SSA_NAME) 655169689Skan return false; 656169689Skan 657169689Skan return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) != 0; 658169689Skan} 659169689Skan 660169689Skan/* Returns false if BASE or INDEX contains a ssa name that occurs in an 661169689Skan abnormal phi node. Callback for for_each_index. */ 662169689Skan 663169689Skanstatic bool 664169689Skanidx_contains_abnormal_ssa_name_p (tree base, tree *index, 665169689Skan void *data ATTRIBUTE_UNUSED) 666169689Skan{ 667169689Skan if (TREE_CODE (base) == ARRAY_REF) 668169689Skan { 669169689Skan if (abnormal_ssa_name_p (TREE_OPERAND (base, 2))) 670169689Skan return false; 671169689Skan if (abnormal_ssa_name_p (TREE_OPERAND (base, 3))) 672169689Skan return false; 673169689Skan } 674169689Skan 675169689Skan return !abnormal_ssa_name_p (*index); 676169689Skan} 677169689Skan 678169689Skan/* Returns true if EXPR contains a ssa name that occurs in an 679169689Skan abnormal phi node. */ 680169689Skan 681169689Skanbool 682169689Skancontains_abnormal_ssa_name_p (tree expr) 683169689Skan{ 684169689Skan enum tree_code code; 685169689Skan enum tree_code_class class; 686169689Skan 687169689Skan if (!expr) 688169689Skan return false; 689169689Skan 690169689Skan code = TREE_CODE (expr); 691169689Skan class = TREE_CODE_CLASS (code); 692169689Skan 693169689Skan if (code == SSA_NAME) 694169689Skan return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0; 695169689Skan 696169689Skan if (code == INTEGER_CST 697169689Skan || is_gimple_min_invariant (expr)) 698169689Skan return false; 699169689Skan 700169689Skan if (code == ADDR_EXPR) 701169689Skan return !for_each_index (&TREE_OPERAND (expr, 0), 702169689Skan idx_contains_abnormal_ssa_name_p, 703169689Skan NULL); 704169689Skan 705169689Skan switch (class) 706169689Skan { 707169689Skan case tcc_binary: 708169689Skan case tcc_comparison: 709169689Skan if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 1))) 710169689Skan return true; 711169689Skan 712169689Skan /* Fallthru. */ 713169689Skan case tcc_unary: 714169689Skan if (contains_abnormal_ssa_name_p (TREE_OPERAND (expr, 0))) 715169689Skan return true; 716169689Skan 717169689Skan break; 718169689Skan 719169689Skan default: 720169689Skan gcc_unreachable (); 721169689Skan } 722169689Skan 723169689Skan return false; 724169689Skan} 725169689Skan 726169689Skan/* Element of the table in that we cache the numbers of iterations obtained 727169689Skan from exits of the loop. */ 728169689Skan 729169689Skanstruct nfe_cache_elt 730169689Skan{ 731169689Skan /* The edge for that the number of iterations is cached. */ 732169689Skan edge exit; 733169689Skan 734169689Skan /* Number of iterations corresponding to this exit, or NULL if it cannot be 735169689Skan determined. */ 736169689Skan tree niter; 737169689Skan}; 738169689Skan 739169689Skan/* Hash function for nfe_cache_elt E. */ 740169689Skan 741169689Skanstatic hashval_t 742169689Skannfe_hash (const void *e) 743169689Skan{ 744169689Skan const struct nfe_cache_elt *elt = e; 745169689Skan 746169689Skan return htab_hash_pointer (elt->exit); 747169689Skan} 748169689Skan 749169689Skan/* Equality function for nfe_cache_elt E1 and edge E2. */ 750169689Skan 751169689Skanstatic int 752169689Skannfe_eq (const void *e1, const void *e2) 753169689Skan{ 754169689Skan const struct nfe_cache_elt *elt1 = e1; 755169689Skan 756169689Skan return elt1->exit == e2; 757169689Skan} 758169689Skan 759169689Skan/* Returns tree describing number of iterations determined from 760169689Skan EXIT of DATA->current_loop, or NULL if something goes wrong. */ 761169689Skan 762169689Skanstatic tree 763169689Skanniter_for_exit (struct ivopts_data *data, edge exit) 764169689Skan{ 765169689Skan struct nfe_cache_elt *nfe_desc; 766169689Skan struct tree_niter_desc desc; 767169689Skan PTR *slot; 768169689Skan 769169689Skan slot = htab_find_slot_with_hash (data->niters, exit, 770169689Skan htab_hash_pointer (exit), 771169689Skan INSERT); 772169689Skan 773169689Skan if (!*slot) 774169689Skan { 775169689Skan nfe_desc = xmalloc (sizeof (struct nfe_cache_elt)); 776169689Skan nfe_desc->exit = exit; 777169689Skan 778169689Skan /* Try to determine number of iterations. We must know it 779169689Skan unconditionally (i.e., without possibility of # of iterations 780169689Skan being zero). Also, we cannot safely work with ssa names that 781169689Skan appear in phi nodes on abnormal edges, so that we do not create 782169689Skan overlapping life ranges for them (PR 27283). */ 783169689Skan if (number_of_iterations_exit (data->current_loop, 784169689Skan exit, &desc, true) 785169689Skan && zero_p (desc.may_be_zero) 786169689Skan && !contains_abnormal_ssa_name_p (desc.niter)) 787169689Skan nfe_desc->niter = desc.niter; 788169689Skan else 789169689Skan nfe_desc->niter = NULL_TREE; 790169689Skan } 791169689Skan else 792169689Skan nfe_desc = *slot; 793169689Skan 794169689Skan return nfe_desc->niter; 795169689Skan} 796169689Skan 797169689Skan/* Returns tree describing number of iterations determined from 798169689Skan single dominating exit of DATA->current_loop, or NULL if something 799169689Skan goes wrong. */ 800169689Skan 801169689Skanstatic tree 802169689Skanniter_for_single_dom_exit (struct ivopts_data *data) 803169689Skan{ 804169689Skan edge exit = single_dom_exit (data->current_loop); 805169689Skan 806169689Skan if (!exit) 807169689Skan return NULL; 808169689Skan 809169689Skan return niter_for_exit (data, exit); 810169689Skan} 811169689Skan 812169689Skan/* Initializes data structures used by the iv optimization pass, stored 813169689Skan in DATA. */ 814169689Skan 815169689Skanstatic void 816169689Skantree_ssa_iv_optimize_init (struct ivopts_data *data) 817169689Skan{ 818169689Skan data->version_info_size = 2 * num_ssa_names; 819169689Skan data->version_info = XCNEWVEC (struct version_info, data->version_info_size); 820169689Skan data->relevant = BITMAP_ALLOC (NULL); 821169689Skan data->important_candidates = BITMAP_ALLOC (NULL); 822169689Skan data->max_inv_id = 0; 823169689Skan data->niters = htab_create (10, nfe_hash, nfe_eq, free); 824169689Skan data->iv_uses = VEC_alloc (iv_use_p, heap, 20); 825169689Skan data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20); 826169689Skan decl_rtl_to_reset = VEC_alloc (tree, heap, 20); 827169689Skan} 828169689Skan 829169689Skan/* Returns a memory object to that EXPR points. In case we are able to 830169689Skan determine that it does not point to any such object, NULL is returned. */ 831169689Skan 832169689Skanstatic tree 833169689Skandetermine_base_object (tree expr) 834169689Skan{ 835169689Skan enum tree_code code = TREE_CODE (expr); 836169689Skan tree base, obj, op0, op1; 837169689Skan 838169689Skan /* If this is a pointer casted to any type, we need to determine 839169689Skan the base object for the pointer; so handle conversions before 840169689Skan throwing away non-pointer expressions. */ 841169689Skan if (TREE_CODE (expr) == NOP_EXPR 842169689Skan || TREE_CODE (expr) == CONVERT_EXPR) 843169689Skan return determine_base_object (TREE_OPERAND (expr, 0)); 844169689Skan 845169689Skan if (!POINTER_TYPE_P (TREE_TYPE (expr))) 846169689Skan return NULL_TREE; 847169689Skan 848169689Skan switch (code) 849169689Skan { 850169689Skan case INTEGER_CST: 851169689Skan return NULL_TREE; 852169689Skan 853169689Skan case ADDR_EXPR: 854169689Skan obj = TREE_OPERAND (expr, 0); 855169689Skan base = get_base_address (obj); 856169689Skan 857169689Skan if (!base) 858169689Skan return expr; 859169689Skan 860169689Skan if (TREE_CODE (base) == INDIRECT_REF) 861169689Skan return determine_base_object (TREE_OPERAND (base, 0)); 862169689Skan 863169689Skan return fold_convert (ptr_type_node, 864169689Skan build_fold_addr_expr (base)); 865169689Skan 866169689Skan case PLUS_EXPR: 867169689Skan case MINUS_EXPR: 868169689Skan op0 = determine_base_object (TREE_OPERAND (expr, 0)); 869169689Skan op1 = determine_base_object (TREE_OPERAND (expr, 1)); 870169689Skan 871169689Skan if (!op1) 872169689Skan return op0; 873169689Skan 874169689Skan if (!op0) 875169689Skan return (code == PLUS_EXPR 876169689Skan ? op1 877169689Skan : fold_build1 (NEGATE_EXPR, ptr_type_node, op1)); 878169689Skan 879169689Skan return fold_build2 (code, ptr_type_node, op0, op1); 880169689Skan 881169689Skan default: 882169689Skan return fold_convert (ptr_type_node, expr); 883169689Skan } 884169689Skan} 885169689Skan 886169689Skan/* Allocates an induction variable with given initial value BASE and step STEP 887169689Skan for loop LOOP. */ 888169689Skan 889169689Skanstatic struct iv * 890169689Skanalloc_iv (tree base, tree step) 891169689Skan{ 892169689Skan struct iv *iv = XCNEW (struct iv); 893169689Skan 894169689Skan if (step && integer_zerop (step)) 895169689Skan step = NULL_TREE; 896169689Skan 897169689Skan iv->base = base; 898169689Skan iv->base_object = determine_base_object (base); 899169689Skan iv->step = step; 900169689Skan iv->biv_p = false; 901169689Skan iv->have_use_for = false; 902169689Skan iv->use_id = 0; 903169689Skan iv->ssa_name = NULL_TREE; 904169689Skan 905169689Skan return iv; 906169689Skan} 907169689Skan 908169689Skan/* Sets STEP and BASE for induction variable IV. */ 909169689Skan 910169689Skanstatic void 911169689Skanset_iv (struct ivopts_data *data, tree iv, tree base, tree step) 912169689Skan{ 913169689Skan struct version_info *info = name_info (data, iv); 914169689Skan 915169689Skan gcc_assert (!info->iv); 916169689Skan 917169689Skan bitmap_set_bit (data->relevant, SSA_NAME_VERSION (iv)); 918169689Skan info->iv = alloc_iv (base, step); 919169689Skan info->iv->ssa_name = iv; 920169689Skan} 921169689Skan 922169689Skan/* Finds induction variable declaration for VAR. */ 923169689Skan 924169689Skanstatic struct iv * 925169689Skanget_iv (struct ivopts_data *data, tree var) 926169689Skan{ 927169689Skan basic_block bb; 928169689Skan 929169689Skan if (!name_info (data, var)->iv) 930169689Skan { 931169689Skan bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); 932169689Skan 933169689Skan if (!bb 934169689Skan || !flow_bb_inside_loop_p (data->current_loop, bb)) 935169689Skan set_iv (data, var, var, NULL_TREE); 936169689Skan } 937169689Skan 938169689Skan return name_info (data, var)->iv; 939169689Skan} 940169689Skan 941169689Skan/* Determines the step of a biv defined in PHI. Returns NULL if PHI does 942169689Skan not define a simple affine biv with nonzero step. */ 943169689Skan 944169689Skanstatic tree 945169689Skandetermine_biv_step (tree phi) 946169689Skan{ 947169689Skan struct loop *loop = bb_for_stmt (phi)->loop_father; 948169689Skan tree name = PHI_RESULT (phi); 949169689Skan affine_iv iv; 950169689Skan 951169689Skan if (!is_gimple_reg (name)) 952169689Skan return NULL_TREE; 953169689Skan 954169689Skan if (!simple_iv (loop, phi, name, &iv, true)) 955169689Skan return NULL_TREE; 956169689Skan 957169689Skan return (zero_p (iv.step) ? NULL_TREE : iv.step); 958169689Skan} 959169689Skan 960169689Skan/* Finds basic ivs. */ 961169689Skan 962169689Skanstatic bool 963169689Skanfind_bivs (struct ivopts_data *data) 964169689Skan{ 965169689Skan tree phi, step, type, base; 966169689Skan bool found = false; 967169689Skan struct loop *loop = data->current_loop; 968169689Skan 969169689Skan for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi)) 970169689Skan { 971169689Skan if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi))) 972169689Skan continue; 973169689Skan 974169689Skan step = determine_biv_step (phi); 975169689Skan if (!step) 976169689Skan continue; 977169689Skan 978169689Skan base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); 979169689Skan base = expand_simple_operations (base); 980169689Skan if (contains_abnormal_ssa_name_p (base) 981169689Skan || contains_abnormal_ssa_name_p (step)) 982169689Skan continue; 983169689Skan 984169689Skan type = TREE_TYPE (PHI_RESULT (phi)); 985169689Skan base = fold_convert (type, base); 986169689Skan if (step) 987169689Skan step = fold_convert (type, step); 988169689Skan 989169689Skan set_iv (data, PHI_RESULT (phi), base, step); 990169689Skan found = true; 991169689Skan } 992169689Skan 993169689Skan return found; 994169689Skan} 995169689Skan 996169689Skan/* Marks basic ivs. */ 997169689Skan 998169689Skanstatic void 999169689Skanmark_bivs (struct ivopts_data *data) 1000169689Skan{ 1001169689Skan tree phi, var; 1002169689Skan struct iv *iv, *incr_iv; 1003169689Skan struct loop *loop = data->current_loop; 1004169689Skan basic_block incr_bb; 1005169689Skan 1006169689Skan for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi)) 1007169689Skan { 1008169689Skan iv = get_iv (data, PHI_RESULT (phi)); 1009169689Skan if (!iv) 1010169689Skan continue; 1011169689Skan 1012169689Skan var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); 1013169689Skan incr_iv = get_iv (data, var); 1014169689Skan if (!incr_iv) 1015169689Skan continue; 1016169689Skan 1017169689Skan /* If the increment is in the subloop, ignore it. */ 1018169689Skan incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); 1019169689Skan if (incr_bb->loop_father != data->current_loop 1020169689Skan || (incr_bb->flags & BB_IRREDUCIBLE_LOOP)) 1021169689Skan continue; 1022169689Skan 1023169689Skan iv->biv_p = true; 1024169689Skan incr_iv->biv_p = true; 1025169689Skan } 1026169689Skan} 1027169689Skan 1028169689Skan/* Checks whether STMT defines a linear induction variable and stores its 1029169689Skan parameters to IV. */ 1030169689Skan 1031169689Skanstatic bool 1032169689Skanfind_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv) 1033169689Skan{ 1034169689Skan tree lhs; 1035169689Skan struct loop *loop = data->current_loop; 1036169689Skan 1037169689Skan iv->base = NULL_TREE; 1038169689Skan iv->step = NULL_TREE; 1039169689Skan 1040169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 1041169689Skan return false; 1042169689Skan 1043169689Skan lhs = TREE_OPERAND (stmt, 0); 1044169689Skan if (TREE_CODE (lhs) != SSA_NAME) 1045169689Skan return false; 1046169689Skan 1047169689Skan if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), iv, true)) 1048169689Skan return false; 1049169689Skan iv->base = expand_simple_operations (iv->base); 1050169689Skan 1051169689Skan if (contains_abnormal_ssa_name_p (iv->base) 1052169689Skan || contains_abnormal_ssa_name_p (iv->step)) 1053169689Skan return false; 1054169689Skan 1055169689Skan return true; 1056169689Skan} 1057169689Skan 1058169689Skan/* Finds general ivs in statement STMT. */ 1059169689Skan 1060169689Skanstatic void 1061169689Skanfind_givs_in_stmt (struct ivopts_data *data, tree stmt) 1062169689Skan{ 1063169689Skan affine_iv iv; 1064169689Skan 1065169689Skan if (!find_givs_in_stmt_scev (data, stmt, &iv)) 1066169689Skan return; 1067169689Skan 1068169689Skan set_iv (data, TREE_OPERAND (stmt, 0), iv.base, iv.step); 1069169689Skan} 1070169689Skan 1071169689Skan/* Finds general ivs in basic block BB. */ 1072169689Skan 1073169689Skanstatic void 1074169689Skanfind_givs_in_bb (struct ivopts_data *data, basic_block bb) 1075169689Skan{ 1076169689Skan block_stmt_iterator bsi; 1077169689Skan 1078169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1079169689Skan find_givs_in_stmt (data, bsi_stmt (bsi)); 1080169689Skan} 1081169689Skan 1082169689Skan/* Finds general ivs. */ 1083169689Skan 1084169689Skanstatic void 1085169689Skanfind_givs (struct ivopts_data *data) 1086169689Skan{ 1087169689Skan struct loop *loop = data->current_loop; 1088169689Skan basic_block *body = get_loop_body_in_dom_order (loop); 1089169689Skan unsigned i; 1090169689Skan 1091169689Skan for (i = 0; i < loop->num_nodes; i++) 1092169689Skan find_givs_in_bb (data, body[i]); 1093169689Skan free (body); 1094169689Skan} 1095169689Skan 1096169689Skan/* For each ssa name defined in LOOP determines whether it is an induction 1097169689Skan variable and if so, its initial value and step. */ 1098169689Skan 1099169689Skanstatic bool 1100169689Skanfind_induction_variables (struct ivopts_data *data) 1101169689Skan{ 1102169689Skan unsigned i; 1103169689Skan bitmap_iterator bi; 1104169689Skan 1105169689Skan if (!find_bivs (data)) 1106169689Skan return false; 1107169689Skan 1108169689Skan find_givs (data); 1109169689Skan mark_bivs (data); 1110169689Skan 1111169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1112169689Skan { 1113169689Skan tree niter = niter_for_single_dom_exit (data); 1114169689Skan 1115169689Skan if (niter) 1116169689Skan { 1117169689Skan fprintf (dump_file, " number of iterations "); 1118169689Skan print_generic_expr (dump_file, niter, TDF_SLIM); 1119169689Skan fprintf (dump_file, "\n\n"); 1120169689Skan }; 1121169689Skan 1122169689Skan fprintf (dump_file, "Induction variables:\n\n"); 1123169689Skan 1124169689Skan EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi) 1125169689Skan { 1126169689Skan if (ver_info (data, i)->iv) 1127169689Skan dump_iv (dump_file, ver_info (data, i)->iv); 1128169689Skan } 1129169689Skan } 1130169689Skan 1131169689Skan return true; 1132169689Skan} 1133169689Skan 1134169689Skan/* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */ 1135169689Skan 1136169689Skanstatic struct iv_use * 1137169689Skanrecord_use (struct ivopts_data *data, tree *use_p, struct iv *iv, 1138169689Skan tree stmt, enum use_type use_type) 1139169689Skan{ 1140169689Skan struct iv_use *use = XCNEW (struct iv_use); 1141169689Skan 1142169689Skan use->id = n_iv_uses (data); 1143169689Skan use->type = use_type; 1144169689Skan use->iv = iv; 1145169689Skan use->stmt = stmt; 1146169689Skan use->op_p = use_p; 1147169689Skan use->related_cands = BITMAP_ALLOC (NULL); 1148169689Skan 1149169689Skan /* To avoid showing ssa name in the dumps, if it was not reset by the 1150169689Skan caller. */ 1151169689Skan iv->ssa_name = NULL_TREE; 1152169689Skan 1153169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1154169689Skan dump_use (dump_file, use); 1155169689Skan 1156169689Skan VEC_safe_push (iv_use_p, heap, data->iv_uses, use); 1157169689Skan 1158169689Skan return use; 1159169689Skan} 1160169689Skan 1161169689Skan/* Checks whether OP is a loop-level invariant and if so, records it. 1162169689Skan NONLINEAR_USE is true if the invariant is used in a way we do not 1163169689Skan handle specially. */ 1164169689Skan 1165169689Skanstatic void 1166169689Skanrecord_invariant (struct ivopts_data *data, tree op, bool nonlinear_use) 1167169689Skan{ 1168169689Skan basic_block bb; 1169169689Skan struct version_info *info; 1170169689Skan 1171169689Skan if (TREE_CODE (op) != SSA_NAME 1172169689Skan || !is_gimple_reg (op)) 1173169689Skan return; 1174169689Skan 1175169689Skan bb = bb_for_stmt (SSA_NAME_DEF_STMT (op)); 1176169689Skan if (bb 1177169689Skan && flow_bb_inside_loop_p (data->current_loop, bb)) 1178169689Skan return; 1179169689Skan 1180169689Skan info = name_info (data, op); 1181169689Skan info->name = op; 1182169689Skan info->has_nonlin_use |= nonlinear_use; 1183169689Skan if (!info->inv_id) 1184169689Skan info->inv_id = ++data->max_inv_id; 1185169689Skan bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op)); 1186169689Skan} 1187169689Skan 1188169689Skan/* Checks whether the use OP is interesting and if so, records it. */ 1189169689Skan 1190169689Skanstatic struct iv_use * 1191169689Skanfind_interesting_uses_op (struct ivopts_data *data, tree op) 1192169689Skan{ 1193169689Skan struct iv *iv; 1194169689Skan struct iv *civ; 1195169689Skan tree stmt; 1196169689Skan struct iv_use *use; 1197169689Skan 1198169689Skan if (TREE_CODE (op) != SSA_NAME) 1199169689Skan return NULL; 1200169689Skan 1201169689Skan iv = get_iv (data, op); 1202169689Skan if (!iv) 1203169689Skan return NULL; 1204169689Skan 1205169689Skan if (iv->have_use_for) 1206169689Skan { 1207169689Skan use = iv_use (data, iv->use_id); 1208169689Skan 1209169689Skan gcc_assert (use->type == USE_NONLINEAR_EXPR); 1210169689Skan return use; 1211169689Skan } 1212169689Skan 1213169689Skan if (zero_p (iv->step)) 1214169689Skan { 1215169689Skan record_invariant (data, op, true); 1216169689Skan return NULL; 1217169689Skan } 1218169689Skan iv->have_use_for = true; 1219169689Skan 1220169689Skan civ = XNEW (struct iv); 1221169689Skan *civ = *iv; 1222169689Skan 1223169689Skan stmt = SSA_NAME_DEF_STMT (op); 1224169689Skan gcc_assert (TREE_CODE (stmt) == PHI_NODE 1225169689Skan || TREE_CODE (stmt) == MODIFY_EXPR); 1226169689Skan 1227169689Skan use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR); 1228169689Skan iv->use_id = use->id; 1229169689Skan 1230169689Skan return use; 1231169689Skan} 1232169689Skan 1233169689Skan/* Checks whether the condition *COND_P in STMT is interesting 1234169689Skan and if so, records it. */ 1235169689Skan 1236169689Skanstatic void 1237169689Skanfind_interesting_uses_cond (struct ivopts_data *data, tree stmt, tree *cond_p) 1238169689Skan{ 1239169689Skan tree *op0_p; 1240169689Skan tree *op1_p; 1241169689Skan struct iv *iv0 = NULL, *iv1 = NULL, *civ; 1242169689Skan struct iv const_iv; 1243169689Skan tree zero = integer_zero_node; 1244169689Skan 1245169689Skan const_iv.step = NULL_TREE; 1246169689Skan 1247169689Skan if (TREE_CODE (*cond_p) != SSA_NAME 1248169689Skan && !COMPARISON_CLASS_P (*cond_p)) 1249169689Skan return; 1250169689Skan 1251169689Skan if (TREE_CODE (*cond_p) == SSA_NAME) 1252169689Skan { 1253169689Skan op0_p = cond_p; 1254169689Skan op1_p = &zero; 1255169689Skan } 1256169689Skan else 1257169689Skan { 1258169689Skan op0_p = &TREE_OPERAND (*cond_p, 0); 1259169689Skan op1_p = &TREE_OPERAND (*cond_p, 1); 1260169689Skan } 1261169689Skan 1262169689Skan if (TREE_CODE (*op0_p) == SSA_NAME) 1263169689Skan iv0 = get_iv (data, *op0_p); 1264169689Skan else 1265169689Skan iv0 = &const_iv; 1266169689Skan 1267169689Skan if (TREE_CODE (*op1_p) == SSA_NAME) 1268169689Skan iv1 = get_iv (data, *op1_p); 1269169689Skan else 1270169689Skan iv1 = &const_iv; 1271169689Skan 1272169689Skan if (/* When comparing with non-invariant value, we may not do any senseful 1273169689Skan induction variable elimination. */ 1274169689Skan (!iv0 || !iv1) 1275169689Skan /* Eliminating condition based on two ivs would be nontrivial. 1276169689Skan ??? TODO -- it is not really important to handle this case. */ 1277169689Skan || (!zero_p (iv0->step) && !zero_p (iv1->step))) 1278169689Skan { 1279169689Skan find_interesting_uses_op (data, *op0_p); 1280169689Skan find_interesting_uses_op (data, *op1_p); 1281169689Skan return; 1282169689Skan } 1283169689Skan 1284169689Skan if (zero_p (iv0->step) && zero_p (iv1->step)) 1285169689Skan { 1286169689Skan /* If both are invariants, this is a work for unswitching. */ 1287169689Skan return; 1288169689Skan } 1289169689Skan 1290169689Skan civ = XNEW (struct iv); 1291169689Skan *civ = zero_p (iv0->step) ? *iv1: *iv0; 1292169689Skan record_use (data, cond_p, civ, stmt, USE_COMPARE); 1293169689Skan} 1294169689Skan 1295169689Skan/* Returns true if expression EXPR is obviously invariant in LOOP, 1296169689Skan i.e. if all its operands are defined outside of the LOOP. */ 1297169689Skan 1298169689Skanbool 1299169689Skanexpr_invariant_in_loop_p (struct loop *loop, tree expr) 1300169689Skan{ 1301169689Skan basic_block def_bb; 1302169689Skan unsigned i, len; 1303169689Skan 1304169689Skan if (is_gimple_min_invariant (expr)) 1305169689Skan return true; 1306169689Skan 1307169689Skan if (TREE_CODE (expr) == SSA_NAME) 1308169689Skan { 1309169689Skan def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (expr)); 1310169689Skan if (def_bb 1311169689Skan && flow_bb_inside_loop_p (loop, def_bb)) 1312169689Skan return false; 1313169689Skan 1314169689Skan return true; 1315169689Skan } 1316169689Skan 1317169689Skan if (!EXPR_P (expr)) 1318169689Skan return false; 1319169689Skan 1320169689Skan len = TREE_CODE_LENGTH (TREE_CODE (expr)); 1321169689Skan for (i = 0; i < len; i++) 1322169689Skan if (!expr_invariant_in_loop_p (loop, TREE_OPERAND (expr, i))) 1323169689Skan return false; 1324169689Skan 1325169689Skan return true; 1326169689Skan} 1327169689Skan 1328169689Skan/* Cumulates the steps of indices into DATA and replaces their values with the 1329169689Skan initial ones. Returns false when the value of the index cannot be determined. 1330169689Skan Callback for for_each_index. */ 1331169689Skan 1332169689Skanstruct ifs_ivopts_data 1333169689Skan{ 1334169689Skan struct ivopts_data *ivopts_data; 1335169689Skan tree stmt; 1336169689Skan tree *step_p; 1337169689Skan}; 1338169689Skan 1339169689Skanstatic bool 1340169689Skanidx_find_step (tree base, tree *idx, void *data) 1341169689Skan{ 1342169689Skan struct ifs_ivopts_data *dta = data; 1343169689Skan struct iv *iv; 1344169689Skan tree step, iv_base, iv_step, lbound, off; 1345169689Skan struct loop *loop = dta->ivopts_data->current_loop; 1346169689Skan 1347169689Skan if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF 1348169689Skan || TREE_CODE (base) == ALIGN_INDIRECT_REF) 1349169689Skan return false; 1350169689Skan 1351169689Skan /* If base is a component ref, require that the offset of the reference 1352169689Skan be invariant. */ 1353169689Skan if (TREE_CODE (base) == COMPONENT_REF) 1354169689Skan { 1355169689Skan off = component_ref_field_offset (base); 1356169689Skan return expr_invariant_in_loop_p (loop, off); 1357169689Skan } 1358169689Skan 1359169689Skan /* If base is array, first check whether we will be able to move the 1360169689Skan reference out of the loop (in order to take its address in strength 1361169689Skan reduction). In order for this to work we need both lower bound 1362169689Skan and step to be loop invariants. */ 1363169689Skan if (TREE_CODE (base) == ARRAY_REF) 1364169689Skan { 1365169689Skan step = array_ref_element_size (base); 1366169689Skan lbound = array_ref_low_bound (base); 1367169689Skan 1368169689Skan if (!expr_invariant_in_loop_p (loop, step) 1369169689Skan || !expr_invariant_in_loop_p (loop, lbound)) 1370169689Skan return false; 1371169689Skan } 1372169689Skan 1373169689Skan if (TREE_CODE (*idx) != SSA_NAME) 1374169689Skan return true; 1375169689Skan 1376169689Skan iv = get_iv (dta->ivopts_data, *idx); 1377169689Skan if (!iv) 1378169689Skan return false; 1379169689Skan 1380169689Skan /* XXX We produce for a base of *D42 with iv->base being &x[0] 1381169689Skan *&x[0], which is not folded and does not trigger the 1382169689Skan ARRAY_REF path below. */ 1383169689Skan *idx = iv->base; 1384169689Skan 1385169689Skan if (!iv->step) 1386169689Skan return true; 1387169689Skan 1388169689Skan if (TREE_CODE (base) == ARRAY_REF) 1389169689Skan { 1390169689Skan step = array_ref_element_size (base); 1391169689Skan 1392169689Skan /* We only handle addresses whose step is an integer constant. */ 1393169689Skan if (TREE_CODE (step) != INTEGER_CST) 1394169689Skan return false; 1395169689Skan } 1396169689Skan else 1397169689Skan /* The step for pointer arithmetics already is 1 byte. */ 1398169689Skan step = build_int_cst (sizetype, 1); 1399169689Skan 1400169689Skan iv_base = iv->base; 1401169689Skan iv_step = iv->step; 1402169689Skan if (!convert_affine_scev (dta->ivopts_data->current_loop, 1403169689Skan sizetype, &iv_base, &iv_step, dta->stmt, 1404169689Skan false)) 1405169689Skan { 1406169689Skan /* The index might wrap. */ 1407169689Skan return false; 1408169689Skan } 1409169689Skan 1410169689Skan step = fold_build2 (MULT_EXPR, sizetype, step, iv_step); 1411169689Skan 1412169689Skan if (!*dta->step_p) 1413169689Skan *dta->step_p = step; 1414169689Skan else 1415169689Skan *dta->step_p = fold_build2 (PLUS_EXPR, sizetype, *dta->step_p, step); 1416169689Skan 1417169689Skan return true; 1418169689Skan} 1419169689Skan 1420169689Skan/* Records use in index IDX. Callback for for_each_index. Ivopts data 1421169689Skan object is passed to it in DATA. */ 1422169689Skan 1423169689Skanstatic bool 1424169689Skanidx_record_use (tree base, tree *idx, 1425169689Skan void *data) 1426169689Skan{ 1427169689Skan find_interesting_uses_op (data, *idx); 1428169689Skan if (TREE_CODE (base) == ARRAY_REF) 1429169689Skan { 1430169689Skan find_interesting_uses_op (data, array_ref_element_size (base)); 1431169689Skan find_interesting_uses_op (data, array_ref_low_bound (base)); 1432169689Skan } 1433169689Skan return true; 1434169689Skan} 1435169689Skan 1436169689Skan/* Returns true if memory reference REF may be unaligned. */ 1437169689Skan 1438169689Skanstatic bool 1439169689Skanmay_be_unaligned_p (tree ref) 1440169689Skan{ 1441169689Skan tree base; 1442169689Skan tree base_type; 1443169689Skan HOST_WIDE_INT bitsize; 1444169689Skan HOST_WIDE_INT bitpos; 1445169689Skan tree toffset; 1446169689Skan enum machine_mode mode; 1447169689Skan int unsignedp, volatilep; 1448169689Skan unsigned base_align; 1449169689Skan 1450169689Skan /* TARGET_MEM_REFs are translated directly to valid MEMs on the target, 1451169689Skan thus they are not misaligned. */ 1452169689Skan if (TREE_CODE (ref) == TARGET_MEM_REF) 1453169689Skan return false; 1454169689Skan 1455169689Skan /* The test below is basically copy of what expr.c:normal_inner_ref 1456169689Skan does to check whether the object must be loaded by parts when 1457169689Skan STRICT_ALIGNMENT is true. */ 1458169689Skan base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode, 1459169689Skan &unsignedp, &volatilep, true); 1460169689Skan base_type = TREE_TYPE (base); 1461169689Skan base_align = TYPE_ALIGN (base_type); 1462169689Skan 1463169689Skan if (mode != BLKmode 1464169689Skan && (base_align < GET_MODE_ALIGNMENT (mode) 1465169689Skan || bitpos % GET_MODE_ALIGNMENT (mode) != 0 1466169689Skan || bitpos % BITS_PER_UNIT != 0)) 1467169689Skan return true; 1468169689Skan 1469169689Skan return false; 1470169689Skan} 1471169689Skan 1472169689Skan/* Return true if EXPR may be non-addressable. */ 1473169689Skan 1474169689Skanstatic bool 1475169689Skanmay_be_nonaddressable_p (tree expr) 1476169689Skan{ 1477169689Skan switch (TREE_CODE (expr)) 1478169689Skan { 1479169689Skan case COMPONENT_REF: 1480169689Skan return DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1)) 1481169689Skan || may_be_nonaddressable_p (TREE_OPERAND (expr, 0)); 1482169689Skan 1483169689Skan case ARRAY_REF: 1484169689Skan case ARRAY_RANGE_REF: 1485169689Skan return may_be_nonaddressable_p (TREE_OPERAND (expr, 0)); 1486169689Skan 1487169689Skan case VIEW_CONVERT_EXPR: 1488169689Skan /* This kind of view-conversions may wrap non-addressable objects 1489169689Skan and make them look addressable. After some processing the 1490169689Skan non-addressability may be uncovered again, causing ADDR_EXPRs 1491169689Skan of inappropriate objects to be built. */ 1492169689Skan return AGGREGATE_TYPE_P (TREE_TYPE (expr)) 1493169689Skan && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))); 1494169689Skan 1495169689Skan default: 1496169689Skan break; 1497169689Skan } 1498169689Skan 1499169689Skan return false; 1500169689Skan} 1501169689Skan 1502169689Skan/* Finds addresses in *OP_P inside STMT. */ 1503169689Skan 1504169689Skanstatic void 1505169689Skanfind_interesting_uses_address (struct ivopts_data *data, tree stmt, tree *op_p) 1506169689Skan{ 1507169689Skan tree base = *op_p, step = NULL; 1508169689Skan struct iv *civ; 1509169689Skan struct ifs_ivopts_data ifs_ivopts_data; 1510169689Skan 1511169689Skan /* Do not play with volatile memory references. A bit too conservative, 1512169689Skan perhaps, but safe. */ 1513169689Skan if (stmt_ann (stmt)->has_volatile_ops) 1514169689Skan goto fail; 1515169689Skan 1516169689Skan /* Ignore bitfields for now. Not really something terribly complicated 1517169689Skan to handle. TODO. */ 1518169689Skan if (TREE_CODE (base) == BIT_FIELD_REF) 1519169689Skan goto fail; 1520169689Skan 1521169689Skan if (may_be_nonaddressable_p (base)) 1522169689Skan goto fail; 1523169689Skan 1524169689Skan if (STRICT_ALIGNMENT 1525169689Skan && may_be_unaligned_p (base)) 1526169689Skan goto fail; 1527169689Skan 1528169689Skan base = unshare_expr (base); 1529169689Skan 1530169689Skan if (TREE_CODE (base) == TARGET_MEM_REF) 1531169689Skan { 1532169689Skan tree type = build_pointer_type (TREE_TYPE (base)); 1533169689Skan tree astep; 1534169689Skan 1535169689Skan if (TMR_BASE (base) 1536169689Skan && TREE_CODE (TMR_BASE (base)) == SSA_NAME) 1537169689Skan { 1538169689Skan civ = get_iv (data, TMR_BASE (base)); 1539169689Skan if (!civ) 1540169689Skan goto fail; 1541169689Skan 1542169689Skan TMR_BASE (base) = civ->base; 1543169689Skan step = civ->step; 1544169689Skan } 1545169689Skan if (TMR_INDEX (base) 1546169689Skan && TREE_CODE (TMR_INDEX (base)) == SSA_NAME) 1547169689Skan { 1548169689Skan civ = get_iv (data, TMR_INDEX (base)); 1549169689Skan if (!civ) 1550169689Skan goto fail; 1551169689Skan 1552169689Skan TMR_INDEX (base) = civ->base; 1553169689Skan astep = civ->step; 1554169689Skan 1555169689Skan if (astep) 1556169689Skan { 1557169689Skan if (TMR_STEP (base)) 1558169689Skan astep = fold_build2 (MULT_EXPR, type, TMR_STEP (base), astep); 1559169689Skan 1560169689Skan if (step) 1561169689Skan step = fold_build2 (PLUS_EXPR, type, step, astep); 1562169689Skan else 1563169689Skan step = astep; 1564169689Skan } 1565169689Skan } 1566169689Skan 1567169689Skan if (zero_p (step)) 1568169689Skan goto fail; 1569169689Skan base = tree_mem_ref_addr (type, base); 1570169689Skan } 1571169689Skan else 1572169689Skan { 1573169689Skan ifs_ivopts_data.ivopts_data = data; 1574169689Skan ifs_ivopts_data.stmt = stmt; 1575169689Skan ifs_ivopts_data.step_p = &step; 1576169689Skan if (!for_each_index (&base, idx_find_step, &ifs_ivopts_data) 1577169689Skan || zero_p (step)) 1578169689Skan goto fail; 1579169689Skan 1580169689Skan gcc_assert (TREE_CODE (base) != ALIGN_INDIRECT_REF); 1581169689Skan gcc_assert (TREE_CODE (base) != MISALIGNED_INDIRECT_REF); 1582169689Skan 1583169689Skan base = build_fold_addr_expr (base); 1584169689Skan 1585169689Skan /* Substituting bases of IVs into the base expression might 1586169689Skan have caused folding opportunities. */ 1587169689Skan if (TREE_CODE (base) == ADDR_EXPR) 1588169689Skan { 1589169689Skan tree *ref = &TREE_OPERAND (base, 0); 1590169689Skan while (handled_component_p (*ref)) 1591169689Skan ref = &TREE_OPERAND (*ref, 0); 1592169689Skan if (TREE_CODE (*ref) == INDIRECT_REF) 1593169689Skan *ref = fold_indirect_ref (*ref); 1594169689Skan } 1595169689Skan } 1596169689Skan 1597169689Skan civ = alloc_iv (base, step); 1598169689Skan record_use (data, op_p, civ, stmt, USE_ADDRESS); 1599169689Skan return; 1600169689Skan 1601169689Skanfail: 1602169689Skan for_each_index (op_p, idx_record_use, data); 1603169689Skan} 1604169689Skan 1605169689Skan/* Finds and records invariants used in STMT. */ 1606169689Skan 1607169689Skanstatic void 1608169689Skanfind_invariants_stmt (struct ivopts_data *data, tree stmt) 1609169689Skan{ 1610169689Skan ssa_op_iter iter; 1611169689Skan use_operand_p use_p; 1612169689Skan tree op; 1613169689Skan 1614169689Skan FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) 1615169689Skan { 1616169689Skan op = USE_FROM_PTR (use_p); 1617169689Skan record_invariant (data, op, false); 1618169689Skan } 1619169689Skan} 1620169689Skan 1621169689Skan/* Finds interesting uses of induction variables in the statement STMT. */ 1622169689Skan 1623169689Skanstatic void 1624169689Skanfind_interesting_uses_stmt (struct ivopts_data *data, tree stmt) 1625169689Skan{ 1626169689Skan struct iv *iv; 1627169689Skan tree op, lhs, rhs; 1628169689Skan ssa_op_iter iter; 1629169689Skan use_operand_p use_p; 1630169689Skan 1631169689Skan find_invariants_stmt (data, stmt); 1632169689Skan 1633169689Skan if (TREE_CODE (stmt) == COND_EXPR) 1634169689Skan { 1635169689Skan find_interesting_uses_cond (data, stmt, &COND_EXPR_COND (stmt)); 1636169689Skan return; 1637169689Skan } 1638169689Skan 1639169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 1640169689Skan { 1641169689Skan lhs = TREE_OPERAND (stmt, 0); 1642169689Skan rhs = TREE_OPERAND (stmt, 1); 1643169689Skan 1644169689Skan if (TREE_CODE (lhs) == SSA_NAME) 1645169689Skan { 1646169689Skan /* If the statement defines an induction variable, the uses are not 1647169689Skan interesting by themselves. */ 1648169689Skan 1649169689Skan iv = get_iv (data, lhs); 1650169689Skan 1651169689Skan if (iv && !zero_p (iv->step)) 1652169689Skan return; 1653169689Skan } 1654169689Skan 1655169689Skan switch (TREE_CODE_CLASS (TREE_CODE (rhs))) 1656169689Skan { 1657169689Skan case tcc_comparison: 1658169689Skan find_interesting_uses_cond (data, stmt, &TREE_OPERAND (stmt, 1)); 1659169689Skan return; 1660169689Skan 1661169689Skan case tcc_reference: 1662169689Skan find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 1)); 1663169689Skan if (REFERENCE_CLASS_P (lhs)) 1664169689Skan find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0)); 1665169689Skan return; 1666169689Skan 1667169689Skan default: ; 1668169689Skan } 1669169689Skan 1670169689Skan if (REFERENCE_CLASS_P (lhs) 1671169689Skan && is_gimple_val (rhs)) 1672169689Skan { 1673169689Skan find_interesting_uses_address (data, stmt, &TREE_OPERAND (stmt, 0)); 1674169689Skan find_interesting_uses_op (data, rhs); 1675169689Skan return; 1676169689Skan } 1677169689Skan 1678169689Skan /* TODO -- we should also handle address uses of type 1679169689Skan 1680169689Skan memory = call (whatever); 1681169689Skan 1682169689Skan and 1683169689Skan 1684169689Skan call (memory). */ 1685169689Skan } 1686169689Skan 1687169689Skan if (TREE_CODE (stmt) == PHI_NODE 1688169689Skan && bb_for_stmt (stmt) == data->current_loop->header) 1689169689Skan { 1690169689Skan lhs = PHI_RESULT (stmt); 1691169689Skan iv = get_iv (data, lhs); 1692169689Skan 1693169689Skan if (iv && !zero_p (iv->step)) 1694169689Skan return; 1695169689Skan } 1696169689Skan 1697169689Skan FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) 1698169689Skan { 1699169689Skan op = USE_FROM_PTR (use_p); 1700169689Skan 1701169689Skan if (TREE_CODE (op) != SSA_NAME) 1702169689Skan continue; 1703169689Skan 1704169689Skan iv = get_iv (data, op); 1705169689Skan if (!iv) 1706169689Skan continue; 1707169689Skan 1708169689Skan find_interesting_uses_op (data, op); 1709169689Skan } 1710169689Skan} 1711169689Skan 1712169689Skan/* Finds interesting uses of induction variables outside of loops 1713169689Skan on loop exit edge EXIT. */ 1714169689Skan 1715169689Skanstatic void 1716169689Skanfind_interesting_uses_outside (struct ivopts_data *data, edge exit) 1717169689Skan{ 1718169689Skan tree phi, def; 1719169689Skan 1720169689Skan for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) 1721169689Skan { 1722169689Skan def = PHI_ARG_DEF_FROM_EDGE (phi, exit); 1723169689Skan find_interesting_uses_op (data, def); 1724169689Skan } 1725169689Skan} 1726169689Skan 1727169689Skan/* Finds uses of the induction variables that are interesting. */ 1728169689Skan 1729169689Skanstatic void 1730169689Skanfind_interesting_uses (struct ivopts_data *data) 1731169689Skan{ 1732169689Skan basic_block bb; 1733169689Skan block_stmt_iterator bsi; 1734169689Skan tree phi; 1735169689Skan basic_block *body = get_loop_body (data->current_loop); 1736169689Skan unsigned i; 1737169689Skan struct version_info *info; 1738169689Skan edge e; 1739169689Skan 1740169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1741169689Skan fprintf (dump_file, "Uses:\n\n"); 1742169689Skan 1743169689Skan for (i = 0; i < data->current_loop->num_nodes; i++) 1744169689Skan { 1745169689Skan edge_iterator ei; 1746169689Skan bb = body[i]; 1747169689Skan 1748169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1749169689Skan if (e->dest != EXIT_BLOCK_PTR 1750169689Skan && !flow_bb_inside_loop_p (data->current_loop, e->dest)) 1751169689Skan find_interesting_uses_outside (data, e); 1752169689Skan 1753169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1754169689Skan find_interesting_uses_stmt (data, phi); 1755169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1756169689Skan find_interesting_uses_stmt (data, bsi_stmt (bsi)); 1757169689Skan } 1758169689Skan 1759169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1760169689Skan { 1761169689Skan bitmap_iterator bi; 1762169689Skan 1763169689Skan fprintf (dump_file, "\n"); 1764169689Skan 1765169689Skan EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi) 1766169689Skan { 1767169689Skan info = ver_info (data, i); 1768169689Skan if (info->inv_id) 1769169689Skan { 1770169689Skan fprintf (dump_file, " "); 1771169689Skan print_generic_expr (dump_file, info->name, TDF_SLIM); 1772169689Skan fprintf (dump_file, " is invariant (%d)%s\n", 1773169689Skan info->inv_id, info->has_nonlin_use ? "" : ", eliminable"); 1774169689Skan } 1775169689Skan } 1776169689Skan 1777169689Skan fprintf (dump_file, "\n"); 1778169689Skan } 1779169689Skan 1780169689Skan free (body); 1781169689Skan} 1782169689Skan 1783169689Skan/* Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR 1784169689Skan is true, assume we are inside an address. If TOP_COMPREF is true, assume 1785169689Skan we are at the top-level of the processed address. */ 1786169689Skan 1787169689Skanstatic tree 1788169689Skanstrip_offset_1 (tree expr, bool inside_addr, bool top_compref, 1789169689Skan unsigned HOST_WIDE_INT *offset) 1790169689Skan{ 1791169689Skan tree op0 = NULL_TREE, op1 = NULL_TREE, tmp, step; 1792169689Skan enum tree_code code; 1793169689Skan tree type, orig_type = TREE_TYPE (expr); 1794169689Skan unsigned HOST_WIDE_INT off0, off1, st; 1795169689Skan tree orig_expr = expr; 1796169689Skan 1797169689Skan STRIP_NOPS (expr); 1798169689Skan 1799169689Skan type = TREE_TYPE (expr); 1800169689Skan code = TREE_CODE (expr); 1801169689Skan *offset = 0; 1802169689Skan 1803169689Skan switch (code) 1804169689Skan { 1805169689Skan case INTEGER_CST: 1806169689Skan if (!cst_and_fits_in_hwi (expr) 1807169689Skan || zero_p (expr)) 1808169689Skan return orig_expr; 1809169689Skan 1810169689Skan *offset = int_cst_value (expr); 1811169689Skan return build_int_cst (orig_type, 0); 1812169689Skan 1813169689Skan case PLUS_EXPR: 1814169689Skan case MINUS_EXPR: 1815169689Skan op0 = TREE_OPERAND (expr, 0); 1816169689Skan op1 = TREE_OPERAND (expr, 1); 1817169689Skan 1818169689Skan op0 = strip_offset_1 (op0, false, false, &off0); 1819169689Skan op1 = strip_offset_1 (op1, false, false, &off1); 1820169689Skan 1821169689Skan *offset = (code == PLUS_EXPR ? off0 + off1 : off0 - off1); 1822169689Skan if (op0 == TREE_OPERAND (expr, 0) 1823169689Skan && op1 == TREE_OPERAND (expr, 1)) 1824169689Skan return orig_expr; 1825169689Skan 1826169689Skan if (zero_p (op1)) 1827169689Skan expr = op0; 1828169689Skan else if (zero_p (op0)) 1829169689Skan { 1830169689Skan if (code == PLUS_EXPR) 1831169689Skan expr = op1; 1832169689Skan else 1833169689Skan expr = fold_build1 (NEGATE_EXPR, type, op1); 1834169689Skan } 1835169689Skan else 1836169689Skan expr = fold_build2 (code, type, op0, op1); 1837169689Skan 1838169689Skan return fold_convert (orig_type, expr); 1839169689Skan 1840169689Skan case ARRAY_REF: 1841169689Skan if (!inside_addr) 1842169689Skan return orig_expr; 1843169689Skan 1844169689Skan step = array_ref_element_size (expr); 1845169689Skan if (!cst_and_fits_in_hwi (step)) 1846169689Skan break; 1847169689Skan 1848169689Skan st = int_cst_value (step); 1849169689Skan op1 = TREE_OPERAND (expr, 1); 1850169689Skan op1 = strip_offset_1 (op1, false, false, &off1); 1851169689Skan *offset = off1 * st; 1852169689Skan 1853169689Skan if (top_compref 1854169689Skan && zero_p (op1)) 1855169689Skan { 1856169689Skan /* Strip the component reference completely. */ 1857169689Skan op0 = TREE_OPERAND (expr, 0); 1858169689Skan op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0); 1859169689Skan *offset += off0; 1860169689Skan return op0; 1861169689Skan } 1862169689Skan break; 1863169689Skan 1864169689Skan case COMPONENT_REF: 1865169689Skan if (!inside_addr) 1866169689Skan return orig_expr; 1867169689Skan 1868169689Skan tmp = component_ref_field_offset (expr); 1869169689Skan if (top_compref 1870169689Skan && cst_and_fits_in_hwi (tmp)) 1871169689Skan { 1872169689Skan /* Strip the component reference completely. */ 1873169689Skan op0 = TREE_OPERAND (expr, 0); 1874169689Skan op0 = strip_offset_1 (op0, inside_addr, top_compref, &off0); 1875169689Skan *offset = off0 + int_cst_value (tmp); 1876169689Skan return op0; 1877169689Skan } 1878169689Skan break; 1879169689Skan 1880169689Skan case ADDR_EXPR: 1881169689Skan op0 = TREE_OPERAND (expr, 0); 1882169689Skan op0 = strip_offset_1 (op0, true, true, &off0); 1883169689Skan *offset += off0; 1884169689Skan 1885169689Skan if (op0 == TREE_OPERAND (expr, 0)) 1886169689Skan return orig_expr; 1887169689Skan 1888169689Skan expr = build_fold_addr_expr (op0); 1889169689Skan return fold_convert (orig_type, expr); 1890169689Skan 1891169689Skan case INDIRECT_REF: 1892169689Skan inside_addr = false; 1893169689Skan break; 1894169689Skan 1895169689Skan default: 1896169689Skan return orig_expr; 1897169689Skan } 1898169689Skan 1899169689Skan /* Default handling of expressions for that we want to recurse into 1900169689Skan the first operand. */ 1901169689Skan op0 = TREE_OPERAND (expr, 0); 1902169689Skan op0 = strip_offset_1 (op0, inside_addr, false, &off0); 1903169689Skan *offset += off0; 1904169689Skan 1905169689Skan if (op0 == TREE_OPERAND (expr, 0) 1906169689Skan && (!op1 || op1 == TREE_OPERAND (expr, 1))) 1907169689Skan return orig_expr; 1908169689Skan 1909169689Skan expr = copy_node (expr); 1910169689Skan TREE_OPERAND (expr, 0) = op0; 1911169689Skan if (op1) 1912169689Skan TREE_OPERAND (expr, 1) = op1; 1913169689Skan 1914169689Skan /* Inside address, we might strip the top level component references, 1915169689Skan thus changing type of the expression. Handling of ADDR_EXPR 1916169689Skan will fix that. */ 1917169689Skan expr = fold_convert (orig_type, expr); 1918169689Skan 1919169689Skan return expr; 1920169689Skan} 1921169689Skan 1922169689Skan/* Strips constant offsets from EXPR and stores them to OFFSET. */ 1923169689Skan 1924169689Skanstatic tree 1925169689Skanstrip_offset (tree expr, unsigned HOST_WIDE_INT *offset) 1926169689Skan{ 1927169689Skan return strip_offset_1 (expr, false, false, offset); 1928169689Skan} 1929169689Skan 1930169689Skan/* Returns variant of TYPE that can be used as base for different uses. 1931169689Skan We return unsigned type with the same precision, which avoids problems 1932169689Skan with overflows. */ 1933169689Skan 1934169689Skanstatic tree 1935169689Skangeneric_type_for (tree type) 1936169689Skan{ 1937169689Skan if (POINTER_TYPE_P (type)) 1938169689Skan return unsigned_type_for (type); 1939169689Skan 1940169689Skan if (TYPE_UNSIGNED (type)) 1941169689Skan return type; 1942169689Skan 1943169689Skan return unsigned_type_for (type); 1944169689Skan} 1945169689Skan 1946169689Skan/* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains 1947169689Skan the bitmap to that we should store it. */ 1948169689Skan 1949169689Skanstatic struct ivopts_data *fd_ivopts_data; 1950169689Skanstatic tree 1951169689Skanfind_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data) 1952169689Skan{ 1953169689Skan bitmap *depends_on = data; 1954169689Skan struct version_info *info; 1955169689Skan 1956169689Skan if (TREE_CODE (*expr_p) != SSA_NAME) 1957169689Skan return NULL_TREE; 1958169689Skan info = name_info (fd_ivopts_data, *expr_p); 1959169689Skan 1960169689Skan if (!info->inv_id || info->has_nonlin_use) 1961169689Skan return NULL_TREE; 1962169689Skan 1963169689Skan if (!*depends_on) 1964169689Skan *depends_on = BITMAP_ALLOC (NULL); 1965169689Skan bitmap_set_bit (*depends_on, info->inv_id); 1966169689Skan 1967169689Skan return NULL_TREE; 1968169689Skan} 1969169689Skan 1970169689Skan/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and 1971169689Skan position to POS. If USE is not NULL, the candidate is set as related to 1972169689Skan it. If both BASE and STEP are NULL, we add a pseudocandidate for the 1973169689Skan replacement of the final value of the iv by a direct computation. */ 1974169689Skan 1975169689Skanstatic struct iv_cand * 1976169689Skanadd_candidate_1 (struct ivopts_data *data, 1977169689Skan tree base, tree step, bool important, enum iv_position pos, 1978169689Skan struct iv_use *use, tree incremented_at) 1979169689Skan{ 1980169689Skan unsigned i; 1981169689Skan struct iv_cand *cand = NULL; 1982169689Skan tree type, orig_type; 1983169689Skan 1984169689Skan if (base) 1985169689Skan { 1986169689Skan orig_type = TREE_TYPE (base); 1987169689Skan type = generic_type_for (orig_type); 1988169689Skan if (type != orig_type) 1989169689Skan { 1990169689Skan base = fold_convert (type, base); 1991169689Skan if (step) 1992169689Skan step = fold_convert (type, step); 1993169689Skan } 1994169689Skan } 1995169689Skan 1996169689Skan for (i = 0; i < n_iv_cands (data); i++) 1997169689Skan { 1998169689Skan cand = iv_cand (data, i); 1999169689Skan 2000169689Skan if (cand->pos != pos) 2001169689Skan continue; 2002169689Skan 2003169689Skan if (cand->incremented_at != incremented_at) 2004169689Skan continue; 2005169689Skan 2006169689Skan if (!cand->iv) 2007169689Skan { 2008169689Skan if (!base && !step) 2009169689Skan break; 2010169689Skan 2011169689Skan continue; 2012169689Skan } 2013169689Skan 2014169689Skan if (!base && !step) 2015169689Skan continue; 2016169689Skan 2017169689Skan if (!operand_equal_p (base, cand->iv->base, 0)) 2018169689Skan continue; 2019169689Skan 2020169689Skan if (zero_p (cand->iv->step)) 2021169689Skan { 2022169689Skan if (zero_p (step)) 2023169689Skan break; 2024169689Skan } 2025169689Skan else 2026169689Skan { 2027169689Skan if (step && operand_equal_p (step, cand->iv->step, 0)) 2028169689Skan break; 2029169689Skan } 2030169689Skan } 2031169689Skan 2032169689Skan if (i == n_iv_cands (data)) 2033169689Skan { 2034169689Skan cand = XCNEW (struct iv_cand); 2035169689Skan cand->id = i; 2036169689Skan 2037169689Skan if (!base && !step) 2038169689Skan cand->iv = NULL; 2039169689Skan else 2040169689Skan cand->iv = alloc_iv (base, step); 2041169689Skan 2042169689Skan cand->pos = pos; 2043169689Skan if (pos != IP_ORIGINAL && cand->iv) 2044169689Skan { 2045169689Skan cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp"); 2046169689Skan cand->var_after = cand->var_before; 2047169689Skan } 2048169689Skan cand->important = important; 2049169689Skan cand->incremented_at = incremented_at; 2050169689Skan VEC_safe_push (iv_cand_p, heap, data->iv_candidates, cand); 2051169689Skan 2052169689Skan if (step 2053169689Skan && TREE_CODE (step) != INTEGER_CST) 2054169689Skan { 2055169689Skan fd_ivopts_data = data; 2056169689Skan walk_tree (&step, find_depends, &cand->depends_on, NULL); 2057169689Skan } 2058169689Skan 2059169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2060169689Skan dump_cand (dump_file, cand); 2061169689Skan } 2062169689Skan 2063169689Skan if (important && !cand->important) 2064169689Skan { 2065169689Skan cand->important = true; 2066169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2067169689Skan fprintf (dump_file, "Candidate %d is important\n", cand->id); 2068169689Skan } 2069169689Skan 2070169689Skan if (use) 2071169689Skan { 2072169689Skan bitmap_set_bit (use->related_cands, i); 2073169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2074169689Skan fprintf (dump_file, "Candidate %d is related to use %d\n", 2075169689Skan cand->id, use->id); 2076169689Skan } 2077169689Skan 2078169689Skan return cand; 2079169689Skan} 2080169689Skan 2081169689Skan/* Returns true if incrementing the induction variable at the end of the LOOP 2082169689Skan is allowed. 2083169689Skan 2084169689Skan The purpose is to avoid splitting latch edge with a biv increment, thus 2085169689Skan creating a jump, possibly confusing other optimization passes and leaving 2086169689Skan less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS 2087169689Skan is not available (so we do not have a better alternative), or if the latch 2088169689Skan edge is already nonempty. */ 2089169689Skan 2090169689Skanstatic bool 2091169689Skanallow_ip_end_pos_p (struct loop *loop) 2092169689Skan{ 2093169689Skan if (!ip_normal_pos (loop)) 2094169689Skan return true; 2095169689Skan 2096169689Skan if (!empty_block_p (ip_end_pos (loop))) 2097169689Skan return true; 2098169689Skan 2099169689Skan return false; 2100169689Skan} 2101169689Skan 2102169689Skan/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and 2103169689Skan position to POS. If USE is not NULL, the candidate is set as related to 2104169689Skan it. The candidate computation is scheduled on all available positions. */ 2105169689Skan 2106169689Skanstatic void 2107169689Skanadd_candidate (struct ivopts_data *data, 2108169689Skan tree base, tree step, bool important, struct iv_use *use) 2109169689Skan{ 2110169689Skan if (ip_normal_pos (data->current_loop)) 2111169689Skan add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL_TREE); 2112169689Skan if (ip_end_pos (data->current_loop) 2113169689Skan && allow_ip_end_pos_p (data->current_loop)) 2114169689Skan add_candidate_1 (data, base, step, important, IP_END, use, NULL_TREE); 2115169689Skan} 2116169689Skan 2117169689Skan/* Add a standard "0 + 1 * iteration" iv candidate for a 2118169689Skan type with SIZE bits. */ 2119169689Skan 2120169689Skanstatic void 2121169689Skanadd_standard_iv_candidates_for_size (struct ivopts_data *data, 2122169689Skan unsigned int size) 2123169689Skan{ 2124169689Skan tree type = lang_hooks.types.type_for_size (size, true); 2125169689Skan add_candidate (data, build_int_cst (type, 0), build_int_cst (type, 1), 2126169689Skan true, NULL); 2127169689Skan} 2128169689Skan 2129169689Skan/* Adds standard iv candidates. */ 2130169689Skan 2131169689Skanstatic void 2132169689Skanadd_standard_iv_candidates (struct ivopts_data *data) 2133169689Skan{ 2134169689Skan add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE); 2135169689Skan 2136169689Skan /* The same for a double-integer type if it is still fast enough. */ 2137169689Skan if (BITS_PER_WORD >= INT_TYPE_SIZE * 2) 2138169689Skan add_standard_iv_candidates_for_size (data, INT_TYPE_SIZE * 2); 2139169689Skan} 2140169689Skan 2141169689Skan 2142169689Skan/* Adds candidates bases on the old induction variable IV. */ 2143169689Skan 2144169689Skanstatic void 2145169689Skanadd_old_iv_candidates (struct ivopts_data *data, struct iv *iv) 2146169689Skan{ 2147169689Skan tree phi, def; 2148169689Skan struct iv_cand *cand; 2149169689Skan 2150169689Skan add_candidate (data, iv->base, iv->step, true, NULL); 2151169689Skan 2152169689Skan /* The same, but with initial value zero. */ 2153169689Skan add_candidate (data, 2154169689Skan build_int_cst (TREE_TYPE (iv->base), 0), 2155169689Skan iv->step, true, NULL); 2156169689Skan 2157169689Skan phi = SSA_NAME_DEF_STMT (iv->ssa_name); 2158169689Skan if (TREE_CODE (phi) == PHI_NODE) 2159169689Skan { 2160169689Skan /* Additionally record the possibility of leaving the original iv 2161169689Skan untouched. */ 2162169689Skan def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop)); 2163169689Skan cand = add_candidate_1 (data, 2164169689Skan iv->base, iv->step, true, IP_ORIGINAL, NULL, 2165169689Skan SSA_NAME_DEF_STMT (def)); 2166169689Skan cand->var_before = iv->ssa_name; 2167169689Skan cand->var_after = def; 2168169689Skan } 2169169689Skan} 2170169689Skan 2171169689Skan/* Adds candidates based on the old induction variables. */ 2172169689Skan 2173169689Skanstatic void 2174169689Skanadd_old_ivs_candidates (struct ivopts_data *data) 2175169689Skan{ 2176169689Skan unsigned i; 2177169689Skan struct iv *iv; 2178169689Skan bitmap_iterator bi; 2179169689Skan 2180169689Skan EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi) 2181169689Skan { 2182169689Skan iv = ver_info (data, i)->iv; 2183169689Skan if (iv && iv->biv_p && !zero_p (iv->step)) 2184169689Skan add_old_iv_candidates (data, iv); 2185169689Skan } 2186169689Skan} 2187169689Skan 2188169689Skan/* Adds candidates based on the value of the induction variable IV and USE. */ 2189169689Skan 2190169689Skanstatic void 2191169689Skanadd_iv_value_candidates (struct ivopts_data *data, 2192169689Skan struct iv *iv, struct iv_use *use) 2193169689Skan{ 2194169689Skan unsigned HOST_WIDE_INT offset; 2195169689Skan tree base; 2196169689Skan 2197169689Skan add_candidate (data, iv->base, iv->step, false, use); 2198169689Skan 2199169689Skan /* The same, but with initial value zero. Make such variable important, 2200169689Skan since it is generic enough so that possibly many uses may be based 2201169689Skan on it. */ 2202169689Skan add_candidate (data, build_int_cst (TREE_TYPE (iv->base), 0), 2203169689Skan iv->step, true, use); 2204169689Skan 2205169689Skan /* Third, try removing the constant offset. */ 2206169689Skan base = strip_offset (iv->base, &offset); 2207169689Skan if (offset) 2208169689Skan add_candidate (data, base, iv->step, false, use); 2209169689Skan} 2210169689Skan 2211169689Skan/* Adds candidates based on the uses. */ 2212169689Skan 2213169689Skanstatic void 2214169689Skanadd_derived_ivs_candidates (struct ivopts_data *data) 2215169689Skan{ 2216169689Skan unsigned i; 2217169689Skan 2218169689Skan for (i = 0; i < n_iv_uses (data); i++) 2219169689Skan { 2220169689Skan struct iv_use *use = iv_use (data, i); 2221169689Skan 2222169689Skan if (!use) 2223169689Skan continue; 2224169689Skan 2225169689Skan switch (use->type) 2226169689Skan { 2227169689Skan case USE_NONLINEAR_EXPR: 2228169689Skan case USE_COMPARE: 2229169689Skan case USE_ADDRESS: 2230169689Skan /* Just add the ivs based on the value of the iv used here. */ 2231169689Skan add_iv_value_candidates (data, use->iv, use); 2232169689Skan break; 2233169689Skan 2234169689Skan default: 2235169689Skan gcc_unreachable (); 2236169689Skan } 2237169689Skan } 2238169689Skan} 2239169689Skan 2240169689Skan/* Record important candidates and add them to related_cands bitmaps 2241169689Skan if needed. */ 2242169689Skan 2243169689Skanstatic void 2244169689Skanrecord_important_candidates (struct ivopts_data *data) 2245169689Skan{ 2246169689Skan unsigned i; 2247169689Skan struct iv_use *use; 2248169689Skan 2249169689Skan for (i = 0; i < n_iv_cands (data); i++) 2250169689Skan { 2251169689Skan struct iv_cand *cand = iv_cand (data, i); 2252169689Skan 2253169689Skan if (cand->important) 2254169689Skan bitmap_set_bit (data->important_candidates, i); 2255169689Skan } 2256169689Skan 2257169689Skan data->consider_all_candidates = (n_iv_cands (data) 2258169689Skan <= CONSIDER_ALL_CANDIDATES_BOUND); 2259169689Skan 2260169689Skan if (data->consider_all_candidates) 2261169689Skan { 2262169689Skan /* We will not need "related_cands" bitmaps in this case, 2263169689Skan so release them to decrease peak memory consumption. */ 2264169689Skan for (i = 0; i < n_iv_uses (data); i++) 2265169689Skan { 2266169689Skan use = iv_use (data, i); 2267169689Skan BITMAP_FREE (use->related_cands); 2268169689Skan } 2269169689Skan } 2270169689Skan else 2271169689Skan { 2272169689Skan /* Add important candidates to the related_cands bitmaps. */ 2273169689Skan for (i = 0; i < n_iv_uses (data); i++) 2274169689Skan bitmap_ior_into (iv_use (data, i)->related_cands, 2275169689Skan data->important_candidates); 2276169689Skan } 2277169689Skan} 2278169689Skan 2279169689Skan/* Finds the candidates for the induction variables. */ 2280169689Skan 2281169689Skanstatic void 2282169689Skanfind_iv_candidates (struct ivopts_data *data) 2283169689Skan{ 2284169689Skan /* Add commonly used ivs. */ 2285169689Skan add_standard_iv_candidates (data); 2286169689Skan 2287169689Skan /* Add old induction variables. */ 2288169689Skan add_old_ivs_candidates (data); 2289169689Skan 2290169689Skan /* Add induction variables derived from uses. */ 2291169689Skan add_derived_ivs_candidates (data); 2292169689Skan 2293169689Skan /* Record the important candidates. */ 2294169689Skan record_important_candidates (data); 2295169689Skan} 2296169689Skan 2297169689Skan/* Allocates the data structure mapping the (use, candidate) pairs to costs. 2298169689Skan If consider_all_candidates is true, we use a two-dimensional array, otherwise 2299169689Skan we allocate a simple list to every use. */ 2300169689Skan 2301169689Skanstatic void 2302169689Skanalloc_use_cost_map (struct ivopts_data *data) 2303169689Skan{ 2304169689Skan unsigned i, size, s, j; 2305169689Skan 2306169689Skan for (i = 0; i < n_iv_uses (data); i++) 2307169689Skan { 2308169689Skan struct iv_use *use = iv_use (data, i); 2309169689Skan bitmap_iterator bi; 2310169689Skan 2311169689Skan if (data->consider_all_candidates) 2312169689Skan size = n_iv_cands (data); 2313169689Skan else 2314169689Skan { 2315169689Skan s = 0; 2316169689Skan EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi) 2317169689Skan { 2318169689Skan s++; 2319169689Skan } 2320169689Skan 2321169689Skan /* Round up to the power of two, so that moduling by it is fast. */ 2322169689Skan for (size = 1; size < s; size <<= 1) 2323169689Skan continue; 2324169689Skan } 2325169689Skan 2326169689Skan use->n_map_members = size; 2327169689Skan use->cost_map = XCNEWVEC (struct cost_pair, size); 2328169689Skan } 2329169689Skan} 2330169689Skan 2331169689Skan/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends 2332169689Skan on invariants DEPENDS_ON and that the value used in expressing it 2333169689Skan is VALUE.*/ 2334169689Skan 2335169689Skanstatic void 2336169689Skanset_use_iv_cost (struct ivopts_data *data, 2337169689Skan struct iv_use *use, struct iv_cand *cand, unsigned cost, 2338169689Skan bitmap depends_on, tree value) 2339169689Skan{ 2340169689Skan unsigned i, s; 2341169689Skan 2342169689Skan if (cost == INFTY) 2343169689Skan { 2344169689Skan BITMAP_FREE (depends_on); 2345169689Skan return; 2346169689Skan } 2347169689Skan 2348169689Skan if (data->consider_all_candidates) 2349169689Skan { 2350169689Skan use->cost_map[cand->id].cand = cand; 2351169689Skan use->cost_map[cand->id].cost = cost; 2352169689Skan use->cost_map[cand->id].depends_on = depends_on; 2353169689Skan use->cost_map[cand->id].value = value; 2354169689Skan return; 2355169689Skan } 2356169689Skan 2357169689Skan /* n_map_members is a power of two, so this computes modulo. */ 2358169689Skan s = cand->id & (use->n_map_members - 1); 2359169689Skan for (i = s; i < use->n_map_members; i++) 2360169689Skan if (!use->cost_map[i].cand) 2361169689Skan goto found; 2362169689Skan for (i = 0; i < s; i++) 2363169689Skan if (!use->cost_map[i].cand) 2364169689Skan goto found; 2365169689Skan 2366169689Skan gcc_unreachable (); 2367169689Skan 2368169689Skanfound: 2369169689Skan use->cost_map[i].cand = cand; 2370169689Skan use->cost_map[i].cost = cost; 2371169689Skan use->cost_map[i].depends_on = depends_on; 2372169689Skan use->cost_map[i].value = value; 2373169689Skan} 2374169689Skan 2375169689Skan/* Gets cost of (USE, CANDIDATE) pair. */ 2376169689Skan 2377169689Skanstatic struct cost_pair * 2378169689Skanget_use_iv_cost (struct ivopts_data *data, struct iv_use *use, 2379169689Skan struct iv_cand *cand) 2380169689Skan{ 2381169689Skan unsigned i, s; 2382169689Skan struct cost_pair *ret; 2383169689Skan 2384169689Skan if (!cand) 2385169689Skan return NULL; 2386169689Skan 2387169689Skan if (data->consider_all_candidates) 2388169689Skan { 2389169689Skan ret = use->cost_map + cand->id; 2390169689Skan if (!ret->cand) 2391169689Skan return NULL; 2392169689Skan 2393169689Skan return ret; 2394169689Skan } 2395169689Skan 2396169689Skan /* n_map_members is a power of two, so this computes modulo. */ 2397169689Skan s = cand->id & (use->n_map_members - 1); 2398169689Skan for (i = s; i < use->n_map_members; i++) 2399169689Skan if (use->cost_map[i].cand == cand) 2400169689Skan return use->cost_map + i; 2401169689Skan 2402169689Skan for (i = 0; i < s; i++) 2403169689Skan if (use->cost_map[i].cand == cand) 2404169689Skan return use->cost_map + i; 2405169689Skan 2406169689Skan return NULL; 2407169689Skan} 2408169689Skan 2409169689Skan/* Returns estimate on cost of computing SEQ. */ 2410169689Skan 2411169689Skanstatic unsigned 2412169689Skanseq_cost (rtx seq) 2413169689Skan{ 2414169689Skan unsigned cost = 0; 2415169689Skan rtx set; 2416169689Skan 2417169689Skan for (; seq; seq = NEXT_INSN (seq)) 2418169689Skan { 2419169689Skan set = single_set (seq); 2420169689Skan if (set) 2421169689Skan cost += rtx_cost (set, SET); 2422169689Skan else 2423169689Skan cost++; 2424169689Skan } 2425169689Skan 2426169689Skan return cost; 2427169689Skan} 2428169689Skan 2429169689Skan/* Produce DECL_RTL for object obj so it looks like it is stored in memory. */ 2430169689Skanstatic rtx 2431169689Skanproduce_memory_decl_rtl (tree obj, int *regno) 2432169689Skan{ 2433169689Skan rtx x; 2434169689Skan 2435169689Skan gcc_assert (obj); 2436169689Skan if (TREE_STATIC (obj) || DECL_EXTERNAL (obj)) 2437169689Skan { 2438169689Skan const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj)); 2439169689Skan x = gen_rtx_SYMBOL_REF (Pmode, name); 2440169689Skan } 2441169689Skan else 2442169689Skan x = gen_raw_REG (Pmode, (*regno)++); 2443169689Skan 2444169689Skan return gen_rtx_MEM (DECL_MODE (obj), x); 2445169689Skan} 2446169689Skan 2447169689Skan/* Prepares decl_rtl for variables referred in *EXPR_P. Callback for 2448169689Skan walk_tree. DATA contains the actual fake register number. */ 2449169689Skan 2450169689Skanstatic tree 2451169689Skanprepare_decl_rtl (tree *expr_p, int *ws, void *data) 2452169689Skan{ 2453169689Skan tree obj = NULL_TREE; 2454169689Skan rtx x = NULL_RTX; 2455169689Skan int *regno = data; 2456169689Skan 2457169689Skan switch (TREE_CODE (*expr_p)) 2458169689Skan { 2459169689Skan case ADDR_EXPR: 2460169689Skan for (expr_p = &TREE_OPERAND (*expr_p, 0); 2461169689Skan handled_component_p (*expr_p); 2462169689Skan expr_p = &TREE_OPERAND (*expr_p, 0)) 2463169689Skan continue; 2464169689Skan obj = *expr_p; 2465169689Skan if (DECL_P (obj) && !DECL_RTL_SET_P (obj)) 2466169689Skan x = produce_memory_decl_rtl (obj, regno); 2467169689Skan break; 2468169689Skan 2469169689Skan case SSA_NAME: 2470169689Skan *ws = 0; 2471169689Skan obj = SSA_NAME_VAR (*expr_p); 2472169689Skan if (!DECL_RTL_SET_P (obj)) 2473169689Skan x = gen_raw_REG (DECL_MODE (obj), (*regno)++); 2474169689Skan break; 2475169689Skan 2476169689Skan case VAR_DECL: 2477169689Skan case PARM_DECL: 2478169689Skan case RESULT_DECL: 2479169689Skan *ws = 0; 2480169689Skan obj = *expr_p; 2481169689Skan 2482169689Skan if (DECL_RTL_SET_P (obj)) 2483169689Skan break; 2484169689Skan 2485169689Skan if (DECL_MODE (obj) == BLKmode) 2486169689Skan x = produce_memory_decl_rtl (obj, regno); 2487169689Skan else 2488169689Skan x = gen_raw_REG (DECL_MODE (obj), (*regno)++); 2489169689Skan 2490169689Skan break; 2491169689Skan 2492169689Skan default: 2493169689Skan break; 2494169689Skan } 2495169689Skan 2496169689Skan if (x) 2497169689Skan { 2498169689Skan VEC_safe_push (tree, heap, decl_rtl_to_reset, obj); 2499169689Skan SET_DECL_RTL (obj, x); 2500169689Skan } 2501169689Skan 2502169689Skan return NULL_TREE; 2503169689Skan} 2504169689Skan 2505169689Skan/* Determines cost of the computation of EXPR. */ 2506169689Skan 2507169689Skanstatic unsigned 2508169689Skancomputation_cost (tree expr) 2509169689Skan{ 2510169689Skan rtx seq, rslt; 2511169689Skan tree type = TREE_TYPE (expr); 2512169689Skan unsigned cost; 2513169689Skan /* Avoid using hard regs in ways which may be unsupported. */ 2514169689Skan int regno = LAST_VIRTUAL_REGISTER + 1; 2515169689Skan 2516169689Skan walk_tree (&expr, prepare_decl_rtl, ®no, NULL); 2517169689Skan start_sequence (); 2518169689Skan rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL); 2519169689Skan seq = get_insns (); 2520169689Skan end_sequence (); 2521169689Skan 2522169689Skan cost = seq_cost (seq); 2523169689Skan if (MEM_P (rslt)) 2524169689Skan cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type)); 2525169689Skan 2526169689Skan return cost; 2527169689Skan} 2528169689Skan 2529169689Skan/* Returns variable containing the value of candidate CAND at statement AT. */ 2530169689Skan 2531169689Skanstatic tree 2532169689Skanvar_at_stmt (struct loop *loop, struct iv_cand *cand, tree stmt) 2533169689Skan{ 2534169689Skan if (stmt_after_increment (loop, cand, stmt)) 2535169689Skan return cand->var_after; 2536169689Skan else 2537169689Skan return cand->var_before; 2538169689Skan} 2539169689Skan 2540169689Skan/* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb, 2541169689Skan but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */ 2542169689Skan 2543169689Skanint 2544169689Skantree_int_cst_sign_bit (tree t) 2545169689Skan{ 2546169689Skan unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1; 2547169689Skan unsigned HOST_WIDE_INT w; 2548169689Skan 2549169689Skan if (bitno < HOST_BITS_PER_WIDE_INT) 2550169689Skan w = TREE_INT_CST_LOW (t); 2551169689Skan else 2552169689Skan { 2553169689Skan w = TREE_INT_CST_HIGH (t); 2554169689Skan bitno -= HOST_BITS_PER_WIDE_INT; 2555169689Skan } 2556169689Skan 2557169689Skan return (w >> bitno) & 1; 2558169689Skan} 2559169689Skan 2560169689Skan/* If we can prove that TOP = cst * BOT for some constant cst, 2561169689Skan store cst to MUL and return true. Otherwise return false. 2562169689Skan The returned value is always sign-extended, regardless of the 2563169689Skan signedness of TOP and BOT. */ 2564169689Skan 2565169689Skanstatic bool 2566169689Skanconstant_multiple_of (tree top, tree bot, double_int *mul) 2567169689Skan{ 2568169689Skan tree mby; 2569169689Skan enum tree_code code; 2570169689Skan double_int res, p0, p1; 2571169689Skan unsigned precision = TYPE_PRECISION (TREE_TYPE (top)); 2572169689Skan 2573169689Skan STRIP_NOPS (top); 2574169689Skan STRIP_NOPS (bot); 2575169689Skan 2576169689Skan if (operand_equal_p (top, bot, 0)) 2577169689Skan { 2578169689Skan *mul = double_int_one; 2579169689Skan return true; 2580169689Skan } 2581169689Skan 2582169689Skan code = TREE_CODE (top); 2583169689Skan switch (code) 2584169689Skan { 2585169689Skan case MULT_EXPR: 2586169689Skan mby = TREE_OPERAND (top, 1); 2587169689Skan if (TREE_CODE (mby) != INTEGER_CST) 2588169689Skan return false; 2589169689Skan 2590169689Skan if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res)) 2591169689Skan return false; 2592169689Skan 2593169689Skan *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)), 2594169689Skan precision); 2595169689Skan return true; 2596169689Skan 2597169689Skan case PLUS_EXPR: 2598169689Skan case MINUS_EXPR: 2599169689Skan if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0) 2600169689Skan || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1)) 2601169689Skan return false; 2602169689Skan 2603169689Skan if (code == MINUS_EXPR) 2604169689Skan p1 = double_int_neg (p1); 2605169689Skan *mul = double_int_sext (double_int_add (p0, p1), precision); 2606169689Skan return true; 2607169689Skan 2608169689Skan case INTEGER_CST: 2609169689Skan if (TREE_CODE (bot) != INTEGER_CST) 2610169689Skan return false; 2611169689Skan 2612169689Skan p0 = double_int_sext (tree_to_double_int (bot), precision); 2613169689Skan p1 = double_int_sext (tree_to_double_int (top), precision); 2614169689Skan if (double_int_zero_p (p1)) 2615169689Skan return false; 2616169689Skan *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res), 2617169689Skan precision); 2618169689Skan return double_int_zero_p (res); 2619169689Skan 2620169689Skan default: 2621169689Skan return false; 2622169689Skan } 2623169689Skan} 2624169689Skan 2625169689Skan/* Sets COMB to CST. */ 2626169689Skan 2627169689Skanstatic void 2628169689Skanaff_combination_const (struct affine_tree_combination *comb, tree type, 2629169689Skan unsigned HOST_WIDE_INT cst) 2630169689Skan{ 2631169689Skan unsigned prec = TYPE_PRECISION (type); 2632169689Skan 2633169689Skan comb->type = type; 2634169689Skan comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1); 2635169689Skan 2636169689Skan comb->n = 0; 2637169689Skan comb->rest = NULL_TREE; 2638169689Skan comb->offset = cst & comb->mask; 2639169689Skan} 2640169689Skan 2641169689Skan/* Sets COMB to single element ELT. */ 2642169689Skan 2643169689Skanstatic void 2644169689Skanaff_combination_elt (struct affine_tree_combination *comb, tree type, tree elt) 2645169689Skan{ 2646169689Skan unsigned prec = TYPE_PRECISION (type); 2647169689Skan 2648169689Skan comb->type = type; 2649169689Skan comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1); 2650169689Skan 2651169689Skan comb->n = 1; 2652169689Skan comb->elts[0] = elt; 2653169689Skan comb->coefs[0] = 1; 2654169689Skan comb->rest = NULL_TREE; 2655169689Skan comb->offset = 0; 2656169689Skan} 2657169689Skan 2658169689Skan/* Scales COMB by SCALE. */ 2659169689Skan 2660169689Skanstatic void 2661169689Skanaff_combination_scale (struct affine_tree_combination *comb, 2662169689Skan unsigned HOST_WIDE_INT scale) 2663169689Skan{ 2664169689Skan unsigned i, j; 2665169689Skan 2666169689Skan if (scale == 1) 2667169689Skan return; 2668169689Skan 2669169689Skan if (scale == 0) 2670169689Skan { 2671169689Skan aff_combination_const (comb, comb->type, 0); 2672169689Skan return; 2673169689Skan } 2674169689Skan 2675169689Skan comb->offset = (scale * comb->offset) & comb->mask; 2676169689Skan for (i = 0, j = 0; i < comb->n; i++) 2677169689Skan { 2678169689Skan comb->coefs[j] = (scale * comb->coefs[i]) & comb->mask; 2679169689Skan comb->elts[j] = comb->elts[i]; 2680169689Skan if (comb->coefs[j] != 0) 2681169689Skan j++; 2682169689Skan } 2683169689Skan comb->n = j; 2684169689Skan 2685169689Skan if (comb->rest) 2686169689Skan { 2687169689Skan if (comb->n < MAX_AFF_ELTS) 2688169689Skan { 2689169689Skan comb->coefs[comb->n] = scale; 2690169689Skan comb->elts[comb->n] = comb->rest; 2691169689Skan comb->rest = NULL_TREE; 2692169689Skan comb->n++; 2693169689Skan } 2694169689Skan else 2695169689Skan comb->rest = fold_build2 (MULT_EXPR, comb->type, comb->rest, 2696169689Skan build_int_cst_type (comb->type, scale)); 2697169689Skan } 2698169689Skan} 2699169689Skan 2700169689Skan/* Adds ELT * SCALE to COMB. */ 2701169689Skan 2702169689Skanstatic void 2703169689Skanaff_combination_add_elt (struct affine_tree_combination *comb, tree elt, 2704169689Skan unsigned HOST_WIDE_INT scale) 2705169689Skan{ 2706169689Skan unsigned i; 2707169689Skan 2708169689Skan if (scale == 0) 2709169689Skan return; 2710169689Skan 2711169689Skan for (i = 0; i < comb->n; i++) 2712169689Skan if (operand_equal_p (comb->elts[i], elt, 0)) 2713169689Skan { 2714169689Skan comb->coefs[i] = (comb->coefs[i] + scale) & comb->mask; 2715169689Skan if (comb->coefs[i]) 2716169689Skan return; 2717169689Skan 2718169689Skan comb->n--; 2719169689Skan comb->coefs[i] = comb->coefs[comb->n]; 2720169689Skan comb->elts[i] = comb->elts[comb->n]; 2721169689Skan 2722169689Skan if (comb->rest) 2723169689Skan { 2724169689Skan gcc_assert (comb->n == MAX_AFF_ELTS - 1); 2725169689Skan comb->coefs[comb->n] = 1; 2726169689Skan comb->elts[comb->n] = comb->rest; 2727169689Skan comb->rest = NULL_TREE; 2728169689Skan comb->n++; 2729169689Skan } 2730169689Skan return; 2731169689Skan } 2732169689Skan if (comb->n < MAX_AFF_ELTS) 2733169689Skan { 2734169689Skan comb->coefs[comb->n] = scale; 2735169689Skan comb->elts[comb->n] = elt; 2736169689Skan comb->n++; 2737169689Skan return; 2738169689Skan } 2739169689Skan 2740169689Skan if (scale == 1) 2741169689Skan elt = fold_convert (comb->type, elt); 2742169689Skan else 2743169689Skan elt = fold_build2 (MULT_EXPR, comb->type, 2744169689Skan fold_convert (comb->type, elt), 2745169689Skan build_int_cst_type (comb->type, scale)); 2746169689Skan 2747169689Skan if (comb->rest) 2748169689Skan comb->rest = fold_build2 (PLUS_EXPR, comb->type, comb->rest, elt); 2749169689Skan else 2750169689Skan comb->rest = elt; 2751169689Skan} 2752169689Skan 2753169689Skan/* Adds COMB2 to COMB1. */ 2754169689Skan 2755169689Skanstatic void 2756169689Skanaff_combination_add (struct affine_tree_combination *comb1, 2757169689Skan struct affine_tree_combination *comb2) 2758169689Skan{ 2759169689Skan unsigned i; 2760169689Skan 2761169689Skan comb1->offset = (comb1->offset + comb2->offset) & comb1->mask; 2762169689Skan for (i = 0; i < comb2->n; i++) 2763169689Skan aff_combination_add_elt (comb1, comb2->elts[i], comb2->coefs[i]); 2764169689Skan if (comb2->rest) 2765169689Skan aff_combination_add_elt (comb1, comb2->rest, 1); 2766169689Skan} 2767169689Skan 2768169689Skan/* Convert COMB to TYPE. */ 2769169689Skan 2770169689Skanstatic void 2771169689Skanaff_combination_convert (tree type, struct affine_tree_combination *comb) 2772169689Skan{ 2773169689Skan unsigned prec = TYPE_PRECISION (type); 2774169689Skan unsigned i; 2775169689Skan 2776169689Skan /* If the precision of both types is the same, it suffices to change the type 2777169689Skan of the whole combination -- the elements are allowed to have another type 2778169689Skan equivalent wrto STRIP_NOPS. */ 2779169689Skan if (prec == TYPE_PRECISION (comb->type)) 2780169689Skan { 2781169689Skan comb->type = type; 2782169689Skan return; 2783169689Skan } 2784169689Skan 2785169689Skan comb->mask = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1); 2786169689Skan comb->offset = comb->offset & comb->mask; 2787169689Skan 2788169689Skan /* The type of the elements can be different from comb->type only as 2789169689Skan much as what STRIP_NOPS would remove. We can just directly cast 2790169689Skan to TYPE. */ 2791169689Skan for (i = 0; i < comb->n; i++) 2792169689Skan comb->elts[i] = fold_convert (type, comb->elts[i]); 2793169689Skan if (comb->rest) 2794169689Skan comb->rest = fold_convert (type, comb->rest); 2795169689Skan 2796169689Skan comb->type = type; 2797169689Skan} 2798169689Skan 2799169689Skan/* Splits EXPR into an affine combination of parts. */ 2800169689Skan 2801169689Skanstatic void 2802169689Skantree_to_aff_combination (tree expr, tree type, 2803169689Skan struct affine_tree_combination *comb) 2804169689Skan{ 2805169689Skan struct affine_tree_combination tmp; 2806169689Skan enum tree_code code; 2807169689Skan tree cst, core, toffset; 2808169689Skan HOST_WIDE_INT bitpos, bitsize; 2809169689Skan enum machine_mode mode; 2810169689Skan int unsignedp, volatilep; 2811169689Skan 2812169689Skan STRIP_NOPS (expr); 2813169689Skan 2814169689Skan code = TREE_CODE (expr); 2815169689Skan switch (code) 2816169689Skan { 2817169689Skan case INTEGER_CST: 2818169689Skan aff_combination_const (comb, type, int_cst_value (expr)); 2819169689Skan return; 2820169689Skan 2821169689Skan case PLUS_EXPR: 2822169689Skan case MINUS_EXPR: 2823169689Skan tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); 2824169689Skan tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp); 2825169689Skan if (code == MINUS_EXPR) 2826169689Skan aff_combination_scale (&tmp, -1); 2827169689Skan aff_combination_add (comb, &tmp); 2828169689Skan return; 2829169689Skan 2830169689Skan case MULT_EXPR: 2831169689Skan cst = TREE_OPERAND (expr, 1); 2832169689Skan if (TREE_CODE (cst) != INTEGER_CST) 2833169689Skan break; 2834169689Skan tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); 2835169689Skan aff_combination_scale (comb, int_cst_value (cst)); 2836169689Skan return; 2837169689Skan 2838169689Skan case NEGATE_EXPR: 2839169689Skan tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); 2840169689Skan aff_combination_scale (comb, -1); 2841169689Skan return; 2842169689Skan 2843169689Skan case ADDR_EXPR: 2844169689Skan core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos, 2845169689Skan &toffset, &mode, &unsignedp, &volatilep, 2846169689Skan false); 2847169689Skan if (bitpos % BITS_PER_UNIT != 0) 2848169689Skan break; 2849169689Skan aff_combination_const (comb, type, bitpos / BITS_PER_UNIT); 2850169689Skan core = build_fold_addr_expr (core); 2851169689Skan if (TREE_CODE (core) == ADDR_EXPR) 2852169689Skan aff_combination_add_elt (comb, core, 1); 2853169689Skan else 2854169689Skan { 2855169689Skan tree_to_aff_combination (core, type, &tmp); 2856169689Skan aff_combination_add (comb, &tmp); 2857169689Skan } 2858169689Skan if (toffset) 2859169689Skan { 2860169689Skan tree_to_aff_combination (toffset, type, &tmp); 2861169689Skan aff_combination_add (comb, &tmp); 2862169689Skan } 2863169689Skan return; 2864169689Skan 2865169689Skan default: 2866169689Skan break; 2867169689Skan } 2868169689Skan 2869169689Skan aff_combination_elt (comb, type, expr); 2870169689Skan} 2871169689Skan 2872169689Skan/* Creates EXPR + ELT * SCALE in TYPE. MASK is the mask for width of TYPE. */ 2873169689Skan 2874169689Skanstatic tree 2875169689Skanadd_elt_to_tree (tree expr, tree type, tree elt, unsigned HOST_WIDE_INT scale, 2876169689Skan unsigned HOST_WIDE_INT mask) 2877169689Skan{ 2878169689Skan enum tree_code code; 2879169689Skan 2880169689Skan scale &= mask; 2881169689Skan elt = fold_convert (type, elt); 2882169689Skan 2883169689Skan if (scale == 1) 2884169689Skan { 2885169689Skan if (!expr) 2886169689Skan return elt; 2887169689Skan 2888169689Skan return fold_build2 (PLUS_EXPR, type, expr, elt); 2889169689Skan } 2890169689Skan 2891169689Skan if (scale == mask) 2892169689Skan { 2893169689Skan if (!expr) 2894169689Skan return fold_build1 (NEGATE_EXPR, type, elt); 2895169689Skan 2896169689Skan return fold_build2 (MINUS_EXPR, type, expr, elt); 2897169689Skan } 2898169689Skan 2899169689Skan if (!expr) 2900169689Skan return fold_build2 (MULT_EXPR, type, elt, 2901169689Skan build_int_cst_type (type, scale)); 2902169689Skan 2903169689Skan if ((scale | (mask >> 1)) == mask) 2904169689Skan { 2905169689Skan /* Scale is negative. */ 2906169689Skan code = MINUS_EXPR; 2907169689Skan scale = (-scale) & mask; 2908169689Skan } 2909169689Skan else 2910169689Skan code = PLUS_EXPR; 2911169689Skan 2912169689Skan elt = fold_build2 (MULT_EXPR, type, elt, 2913169689Skan build_int_cst_type (type, scale)); 2914169689Skan return fold_build2 (code, type, expr, elt); 2915169689Skan} 2916169689Skan 2917169689Skan/* Copies the tree elements of COMB to ensure that they are not shared. */ 2918169689Skan 2919169689Skanstatic void 2920169689Skanunshare_aff_combination (struct affine_tree_combination *comb) 2921169689Skan{ 2922169689Skan unsigned i; 2923169689Skan 2924169689Skan for (i = 0; i < comb->n; i++) 2925169689Skan comb->elts[i] = unshare_expr (comb->elts[i]); 2926169689Skan if (comb->rest) 2927169689Skan comb->rest = unshare_expr (comb->rest); 2928169689Skan} 2929169689Skan 2930169689Skan/* Makes tree from the affine combination COMB. */ 2931169689Skan 2932169689Skanstatic tree 2933169689Skanaff_combination_to_tree (struct affine_tree_combination *comb) 2934169689Skan{ 2935169689Skan tree type = comb->type; 2936169689Skan tree expr = comb->rest; 2937169689Skan unsigned i; 2938169689Skan unsigned HOST_WIDE_INT off, sgn; 2939169689Skan 2940169689Skan if (comb->n == 0 && comb->offset == 0) 2941169689Skan { 2942169689Skan if (expr) 2943169689Skan { 2944169689Skan /* Handle the special case produced by get_computation_aff when 2945169689Skan the type does not fit in HOST_WIDE_INT. */ 2946169689Skan return fold_convert (type, expr); 2947169689Skan } 2948169689Skan else 2949169689Skan return build_int_cst (type, 0); 2950169689Skan } 2951169689Skan 2952169689Skan gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE); 2953169689Skan 2954169689Skan for (i = 0; i < comb->n; i++) 2955169689Skan expr = add_elt_to_tree (expr, type, comb->elts[i], comb->coefs[i], 2956169689Skan comb->mask); 2957169689Skan 2958169689Skan if ((comb->offset | (comb->mask >> 1)) == comb->mask) 2959169689Skan { 2960169689Skan /* Offset is negative. */ 2961169689Skan off = (-comb->offset) & comb->mask; 2962169689Skan sgn = comb->mask; 2963169689Skan } 2964169689Skan else 2965169689Skan { 2966169689Skan off = comb->offset; 2967169689Skan sgn = 1; 2968169689Skan } 2969169689Skan return add_elt_to_tree (expr, type, build_int_cst_type (type, off), sgn, 2970169689Skan comb->mask); 2971169689Skan} 2972169689Skan 2973169689Skan/* Folds EXPR using the affine expressions framework. */ 2974169689Skan 2975169689Skanstatic tree 2976169689Skanfold_affine_expr (tree expr) 2977169689Skan{ 2978169689Skan tree type = TREE_TYPE (expr); 2979169689Skan struct affine_tree_combination comb; 2980169689Skan 2981169689Skan if (TYPE_PRECISION (type) > HOST_BITS_PER_WIDE_INT) 2982169689Skan return expr; 2983169689Skan 2984169689Skan tree_to_aff_combination (expr, type, &comb); 2985169689Skan return aff_combination_to_tree (&comb); 2986169689Skan} 2987169689Skan 2988169689Skan/* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the 2989169689Skan same precision that is at least as wide as the precision of TYPE, stores 2990169689Skan BA to A and BB to B, and returns the type of BA. Otherwise, returns the 2991169689Skan type of A and B. */ 2992169689Skan 2993169689Skanstatic tree 2994169689Skandetermine_common_wider_type (tree *a, tree *b) 2995169689Skan{ 2996169689Skan tree wider_type = NULL; 2997169689Skan tree suba, subb; 2998169689Skan tree atype = TREE_TYPE (*a); 2999169689Skan 3000169689Skan if ((TREE_CODE (*a) == NOP_EXPR 3001169689Skan || TREE_CODE (*a) == CONVERT_EXPR)) 3002169689Skan { 3003169689Skan suba = TREE_OPERAND (*a, 0); 3004169689Skan wider_type = TREE_TYPE (suba); 3005169689Skan if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (atype)) 3006169689Skan return atype; 3007169689Skan } 3008169689Skan else 3009169689Skan return atype; 3010169689Skan 3011169689Skan if ((TREE_CODE (*b) == NOP_EXPR 3012169689Skan || TREE_CODE (*b) == CONVERT_EXPR)) 3013169689Skan { 3014169689Skan subb = TREE_OPERAND (*b, 0); 3015169689Skan if (TYPE_PRECISION (wider_type) != TYPE_PRECISION (TREE_TYPE (subb))) 3016169689Skan return atype; 3017169689Skan } 3018169689Skan else 3019169689Skan return atype; 3020169689Skan 3021169689Skan *a = suba; 3022169689Skan *b = subb; 3023169689Skan return wider_type; 3024169689Skan} 3025169689Skan 3026169689Skan/* Determines the expression by that USE is expressed from induction variable 3027169689Skan CAND at statement AT in LOOP. The expression is stored in a decomposed 3028169689Skan form into AFF. Returns false if USE cannot be expressed using CAND. */ 3029169689Skan 3030169689Skanstatic bool 3031169689Skanget_computation_aff (struct loop *loop, 3032169689Skan struct iv_use *use, struct iv_cand *cand, tree at, 3033169689Skan struct affine_tree_combination *aff) 3034169689Skan{ 3035169689Skan tree ubase = use->iv->base; 3036169689Skan tree ustep = use->iv->step; 3037169689Skan tree cbase = cand->iv->base; 3038169689Skan tree cstep = cand->iv->step; 3039169689Skan tree utype = TREE_TYPE (ubase), ctype = TREE_TYPE (cbase); 3040169689Skan tree common_type; 3041169689Skan tree uutype; 3042169689Skan tree expr, delta; 3043169689Skan tree ratio; 3044169689Skan unsigned HOST_WIDE_INT ustepi, cstepi; 3045169689Skan HOST_WIDE_INT ratioi; 3046169689Skan struct affine_tree_combination cbase_aff, expr_aff; 3047169689Skan tree cstep_orig = cstep, ustep_orig = ustep; 3048169689Skan double_int rat; 3049169689Skan 3050169689Skan if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype)) 3051169689Skan { 3052169689Skan /* We do not have a precision to express the values of use. */ 3053169689Skan return false; 3054169689Skan } 3055169689Skan 3056169689Skan expr = var_at_stmt (loop, cand, at); 3057169689Skan 3058169689Skan if (TREE_TYPE (expr) != ctype) 3059169689Skan { 3060169689Skan /* This may happen with the original ivs. */ 3061169689Skan expr = fold_convert (ctype, expr); 3062169689Skan } 3063169689Skan 3064169689Skan if (TYPE_UNSIGNED (utype)) 3065169689Skan uutype = utype; 3066169689Skan else 3067169689Skan { 3068169689Skan uutype = unsigned_type_for (utype); 3069169689Skan ubase = fold_convert (uutype, ubase); 3070169689Skan ustep = fold_convert (uutype, ustep); 3071169689Skan } 3072169689Skan 3073169689Skan if (uutype != ctype) 3074169689Skan { 3075169689Skan expr = fold_convert (uutype, expr); 3076169689Skan cbase = fold_convert (uutype, cbase); 3077169689Skan cstep = fold_convert (uutype, cstep); 3078169689Skan 3079169689Skan /* If the conversion is not noop, we must take it into account when 3080169689Skan considering the value of the step. */ 3081169689Skan if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype)) 3082169689Skan cstep_orig = cstep; 3083169689Skan } 3084169689Skan 3085169689Skan if (cst_and_fits_in_hwi (cstep_orig) 3086169689Skan && cst_and_fits_in_hwi (ustep_orig)) 3087169689Skan { 3088169689Skan ustepi = int_cst_value (ustep_orig); 3089169689Skan cstepi = int_cst_value (cstep_orig); 3090169689Skan 3091169689Skan if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi)) 3092169689Skan { 3093169689Skan /* TODO maybe consider case when ustep divides cstep and the ratio is 3094169689Skan a power of 2 (so that the division is fast to execute)? We would 3095169689Skan need to be much more careful with overflows etc. then. */ 3096169689Skan return false; 3097169689Skan } 3098169689Skan 3099169689Skan ratio = build_int_cst_type (uutype, ratioi); 3100169689Skan } 3101169689Skan else 3102169689Skan { 3103169689Skan if (!constant_multiple_of (ustep_orig, cstep_orig, &rat)) 3104169689Skan return false; 3105169689Skan ratio = double_int_to_tree (uutype, rat); 3106169689Skan 3107169689Skan /* Ratioi is only used to detect special cases when the multiplicative 3108169689Skan factor is 1 or -1, so if rat does not fit to HOST_WIDE_INT, we may 3109169689Skan set it to 0. */ 3110169689Skan if (double_int_fits_in_shwi_p (rat)) 3111169689Skan ratioi = double_int_to_shwi (rat); 3112169689Skan else 3113169689Skan ratioi = 0; 3114169689Skan } 3115169689Skan 3116169689Skan /* In case both UBASE and CBASE are shortened to UUTYPE from some common 3117169689Skan type, we achieve better folding by computing their difference in this 3118169689Skan wider type, and cast the result to UUTYPE. We do not need to worry about 3119169689Skan overflows, as all the arithmetics will in the end be performed in UUTYPE 3120169689Skan anyway. */ 3121169689Skan common_type = determine_common_wider_type (&ubase, &cbase); 3122169689Skan 3123169689Skan /* We may need to shift the value if we are after the increment. */ 3124169689Skan if (stmt_after_increment (loop, cand, at)) 3125169689Skan { 3126169689Skan if (uutype != common_type) 3127169689Skan cstep = fold_convert (common_type, cstep); 3128169689Skan cbase = fold_build2 (PLUS_EXPR, common_type, cbase, cstep); 3129169689Skan } 3130169689Skan 3131169689Skan /* use = ubase - ratio * cbase + ratio * var. 3132169689Skan 3133169689Skan In general case ubase + ratio * (var - cbase) could be better (one less 3134169689Skan multiplication), but often it is possible to eliminate redundant parts 3135169689Skan of computations from (ubase - ratio * cbase) term, and if it does not 3136169689Skan happen, fold is able to apply the distributive law to obtain this form 3137169689Skan anyway. */ 3138169689Skan 3139169689Skan if (TYPE_PRECISION (common_type) > HOST_BITS_PER_WIDE_INT) 3140169689Skan { 3141169689Skan /* Let's compute in trees and just return the result in AFF. This case 3142169689Skan should not be very common, and fold itself is not that bad either, 3143169689Skan so making the aff. functions more complicated to handle this case 3144169689Skan is not that urgent. */ 3145169689Skan if (ratioi == 1) 3146169689Skan { 3147169689Skan delta = fold_build2 (MINUS_EXPR, common_type, ubase, cbase); 3148169689Skan if (uutype != common_type) 3149169689Skan delta = fold_convert (uutype, delta); 3150169689Skan expr = fold_build2 (PLUS_EXPR, uutype, expr, delta); 3151169689Skan } 3152169689Skan else if (ratioi == -1) 3153169689Skan { 3154169689Skan delta = fold_build2 (PLUS_EXPR, common_type, ubase, cbase); 3155169689Skan if (uutype != common_type) 3156169689Skan delta = fold_convert (uutype, delta); 3157169689Skan expr = fold_build2 (MINUS_EXPR, uutype, delta, expr); 3158169689Skan } 3159169689Skan else 3160169689Skan { 3161169689Skan delta = fold_build2 (MULT_EXPR, common_type, cbase, ratio); 3162169689Skan delta = fold_build2 (MINUS_EXPR, common_type, ubase, delta); 3163169689Skan if (uutype != common_type) 3164169689Skan delta = fold_convert (uutype, delta); 3165169689Skan expr = fold_build2 (MULT_EXPR, uutype, ratio, expr); 3166169689Skan expr = fold_build2 (PLUS_EXPR, uutype, delta, expr); 3167169689Skan } 3168169689Skan 3169169689Skan aff->type = uutype; 3170169689Skan aff->n = 0; 3171169689Skan aff->offset = 0; 3172169689Skan aff->mask = 0; 3173169689Skan aff->rest = expr; 3174169689Skan return true; 3175169689Skan } 3176169689Skan 3177169689Skan /* If we got here, the types fits in HOST_WIDE_INT, thus it must be 3178169689Skan possible to compute ratioi. */ 3179169689Skan gcc_assert (ratioi); 3180169689Skan 3181169689Skan tree_to_aff_combination (ubase, common_type, aff); 3182169689Skan tree_to_aff_combination (cbase, common_type, &cbase_aff); 3183169689Skan tree_to_aff_combination (expr, uutype, &expr_aff); 3184169689Skan aff_combination_scale (&cbase_aff, -ratioi); 3185169689Skan aff_combination_scale (&expr_aff, ratioi); 3186169689Skan aff_combination_add (aff, &cbase_aff); 3187169689Skan if (common_type != uutype) 3188169689Skan aff_combination_convert (uutype, aff); 3189169689Skan aff_combination_add (aff, &expr_aff); 3190169689Skan 3191169689Skan return true; 3192169689Skan} 3193169689Skan 3194169689Skan/* Determines the expression by that USE is expressed from induction variable 3195169689Skan CAND at statement AT in LOOP. The computation is unshared. */ 3196169689Skan 3197169689Skanstatic tree 3198169689Skanget_computation_at (struct loop *loop, 3199169689Skan struct iv_use *use, struct iv_cand *cand, tree at) 3200169689Skan{ 3201169689Skan struct affine_tree_combination aff; 3202169689Skan tree type = TREE_TYPE (use->iv->base); 3203169689Skan 3204169689Skan if (!get_computation_aff (loop, use, cand, at, &aff)) 3205169689Skan return NULL_TREE; 3206169689Skan unshare_aff_combination (&aff); 3207169689Skan return fold_convert (type, aff_combination_to_tree (&aff)); 3208169689Skan} 3209169689Skan 3210169689Skan/* Determines the expression by that USE is expressed from induction variable 3211169689Skan CAND in LOOP. The computation is unshared. */ 3212169689Skan 3213169689Skanstatic tree 3214169689Skanget_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand) 3215169689Skan{ 3216169689Skan return get_computation_at (loop, use, cand, use->stmt); 3217169689Skan} 3218169689Skan 3219169689Skan/* Returns cost of addition in MODE. */ 3220169689Skan 3221169689Skanstatic unsigned 3222169689Skanadd_cost (enum machine_mode mode) 3223169689Skan{ 3224169689Skan static unsigned costs[NUM_MACHINE_MODES]; 3225169689Skan rtx seq; 3226169689Skan unsigned cost; 3227169689Skan 3228169689Skan if (costs[mode]) 3229169689Skan return costs[mode]; 3230169689Skan 3231169689Skan start_sequence (); 3232169689Skan force_operand (gen_rtx_fmt_ee (PLUS, mode, 3233169689Skan gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1), 3234169689Skan gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)), 3235169689Skan NULL_RTX); 3236169689Skan seq = get_insns (); 3237169689Skan end_sequence (); 3238169689Skan 3239169689Skan cost = seq_cost (seq); 3240169689Skan if (!cost) 3241169689Skan cost = 1; 3242169689Skan 3243169689Skan costs[mode] = cost; 3244169689Skan 3245169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3246169689Skan fprintf (dump_file, "Addition in %s costs %d\n", 3247169689Skan GET_MODE_NAME (mode), cost); 3248169689Skan return cost; 3249169689Skan} 3250169689Skan 3251169689Skan/* Entry in a hashtable of already known costs for multiplication. */ 3252169689Skanstruct mbc_entry 3253169689Skan{ 3254169689Skan HOST_WIDE_INT cst; /* The constant to multiply by. */ 3255169689Skan enum machine_mode mode; /* In mode. */ 3256169689Skan unsigned cost; /* The cost. */ 3257169689Skan}; 3258169689Skan 3259169689Skan/* Counts hash value for the ENTRY. */ 3260169689Skan 3261169689Skanstatic hashval_t 3262169689Skanmbc_entry_hash (const void *entry) 3263169689Skan{ 3264169689Skan const struct mbc_entry *e = entry; 3265169689Skan 3266169689Skan return 57 * (hashval_t) e->mode + (hashval_t) (e->cst % 877); 3267169689Skan} 3268169689Skan 3269169689Skan/* Compares the hash table entries ENTRY1 and ENTRY2. */ 3270169689Skan 3271169689Skanstatic int 3272169689Skanmbc_entry_eq (const void *entry1, const void *entry2) 3273169689Skan{ 3274169689Skan const struct mbc_entry *e1 = entry1; 3275169689Skan const struct mbc_entry *e2 = entry2; 3276169689Skan 3277169689Skan return (e1->mode == e2->mode 3278169689Skan && e1->cst == e2->cst); 3279169689Skan} 3280169689Skan 3281169689Skan/* Returns cost of multiplication by constant CST in MODE. */ 3282169689Skan 3283169689Skanunsigned 3284169689Skanmultiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode) 3285169689Skan{ 3286169689Skan static htab_t costs; 3287169689Skan struct mbc_entry **cached, act; 3288169689Skan rtx seq; 3289169689Skan unsigned cost; 3290169689Skan 3291169689Skan if (!costs) 3292169689Skan costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free); 3293169689Skan 3294169689Skan act.mode = mode; 3295169689Skan act.cst = cst; 3296169689Skan cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT); 3297169689Skan if (*cached) 3298169689Skan return (*cached)->cost; 3299169689Skan 3300169689Skan *cached = XNEW (struct mbc_entry); 3301169689Skan (*cached)->mode = mode; 3302169689Skan (*cached)->cst = cst; 3303169689Skan 3304169689Skan start_sequence (); 3305169689Skan expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1), 3306169689Skan gen_int_mode (cst, mode), NULL_RTX, 0); 3307169689Skan seq = get_insns (); 3308169689Skan end_sequence (); 3309169689Skan 3310169689Skan cost = seq_cost (seq); 3311169689Skan 3312169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3313169689Skan fprintf (dump_file, "Multiplication by %d in %s costs %d\n", 3314169689Skan (int) cst, GET_MODE_NAME (mode), cost); 3315169689Skan 3316169689Skan (*cached)->cost = cost; 3317169689Skan 3318169689Skan return cost; 3319169689Skan} 3320169689Skan 3321169689Skan/* Returns true if multiplying by RATIO is allowed in address. */ 3322169689Skan 3323169689Skanbool 3324169689Skanmultiplier_allowed_in_address_p (HOST_WIDE_INT ratio) 3325169689Skan{ 3326169689Skan#define MAX_RATIO 128 3327169689Skan static sbitmap valid_mult; 3328169689Skan 3329169689Skan if (!valid_mult) 3330169689Skan { 3331169689Skan rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1); 3332169689Skan rtx addr; 3333169689Skan HOST_WIDE_INT i; 3334169689Skan 3335169689Skan valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1); 3336169689Skan sbitmap_zero (valid_mult); 3337169689Skan addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX); 3338169689Skan for (i = -MAX_RATIO; i <= MAX_RATIO; i++) 3339169689Skan { 3340169689Skan XEXP (addr, 1) = gen_int_mode (i, Pmode); 3341169689Skan if (memory_address_p (Pmode, addr)) 3342169689Skan SET_BIT (valid_mult, i + MAX_RATIO); 3343169689Skan } 3344169689Skan 3345169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3346169689Skan { 3347169689Skan fprintf (dump_file, " allowed multipliers:"); 3348169689Skan for (i = -MAX_RATIO; i <= MAX_RATIO; i++) 3349169689Skan if (TEST_BIT (valid_mult, i + MAX_RATIO)) 3350169689Skan fprintf (dump_file, " %d", (int) i); 3351169689Skan fprintf (dump_file, "\n"); 3352169689Skan fprintf (dump_file, "\n"); 3353169689Skan } 3354169689Skan } 3355169689Skan 3356169689Skan if (ratio > MAX_RATIO || ratio < -MAX_RATIO) 3357169689Skan return false; 3358169689Skan 3359169689Skan return TEST_BIT (valid_mult, ratio + MAX_RATIO); 3360169689Skan} 3361169689Skan 3362169689Skan/* Returns cost of address in shape symbol + var + OFFSET + RATIO * index. 3363169689Skan If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false, 3364169689Skan variable is omitted. The created memory accesses MODE. 3365169689Skan 3366169689Skan TODO -- there must be some better way. This all is quite crude. */ 3367169689Skan 3368169689Skanstatic unsigned 3369169689Skanget_address_cost (bool symbol_present, bool var_present, 3370169689Skan unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio) 3371169689Skan{ 3372169689Skan static bool initialized = false; 3373169689Skan static HOST_WIDE_INT rat, off; 3374169689Skan static HOST_WIDE_INT min_offset, max_offset; 3375169689Skan static unsigned costs[2][2][2][2]; 3376169689Skan unsigned cost, acost; 3377169689Skan bool offset_p, ratio_p; 3378169689Skan HOST_WIDE_INT s_offset; 3379169689Skan unsigned HOST_WIDE_INT mask; 3380169689Skan unsigned bits; 3381169689Skan 3382169689Skan if (!initialized) 3383169689Skan { 3384169689Skan HOST_WIDE_INT i; 3385169689Skan int old_cse_not_expected; 3386169689Skan unsigned sym_p, var_p, off_p, rat_p, add_c; 3387169689Skan rtx seq, addr, base; 3388169689Skan rtx reg0, reg1; 3389169689Skan 3390169689Skan initialized = true; 3391169689Skan 3392169689Skan reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1); 3393169689Skan 3394169689Skan addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX); 3395169689Skan for (i = 1; i <= 1 << 20; i <<= 1) 3396169689Skan { 3397169689Skan XEXP (addr, 1) = gen_int_mode (i, Pmode); 3398169689Skan if (!memory_address_p (Pmode, addr)) 3399169689Skan break; 3400169689Skan } 3401169689Skan max_offset = i >> 1; 3402169689Skan off = max_offset; 3403169689Skan 3404169689Skan for (i = 1; i <= 1 << 20; i <<= 1) 3405169689Skan { 3406169689Skan XEXP (addr, 1) = gen_int_mode (-i, Pmode); 3407169689Skan if (!memory_address_p (Pmode, addr)) 3408169689Skan break; 3409169689Skan } 3410169689Skan min_offset = -(i >> 1); 3411169689Skan 3412169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3413169689Skan { 3414169689Skan fprintf (dump_file, "get_address_cost:\n"); 3415169689Skan fprintf (dump_file, " min offset %d\n", (int) min_offset); 3416169689Skan fprintf (dump_file, " max offset %d\n", (int) max_offset); 3417169689Skan } 3418169689Skan 3419169689Skan rat = 1; 3420169689Skan for (i = 2; i <= MAX_RATIO; i++) 3421169689Skan if (multiplier_allowed_in_address_p (i)) 3422169689Skan { 3423169689Skan rat = i; 3424169689Skan break; 3425169689Skan } 3426169689Skan 3427169689Skan /* Compute the cost of various addressing modes. */ 3428169689Skan acost = 0; 3429169689Skan reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1); 3430169689Skan reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2); 3431169689Skan 3432169689Skan for (i = 0; i < 16; i++) 3433169689Skan { 3434169689Skan sym_p = i & 1; 3435169689Skan var_p = (i >> 1) & 1; 3436169689Skan off_p = (i >> 2) & 1; 3437169689Skan rat_p = (i >> 3) & 1; 3438169689Skan 3439169689Skan addr = reg0; 3440169689Skan if (rat_p) 3441169689Skan addr = gen_rtx_fmt_ee (MULT, Pmode, addr, gen_int_mode (rat, Pmode)); 3442169689Skan 3443169689Skan if (var_p) 3444169689Skan addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1); 3445169689Skan 3446169689Skan if (sym_p) 3447169689Skan { 3448169689Skan base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup ("")); 3449169689Skan if (off_p) 3450169689Skan base = gen_rtx_fmt_e (CONST, Pmode, 3451169689Skan gen_rtx_fmt_ee (PLUS, Pmode, 3452169689Skan base, 3453169689Skan gen_int_mode (off, Pmode))); 3454169689Skan } 3455169689Skan else if (off_p) 3456169689Skan base = gen_int_mode (off, Pmode); 3457169689Skan else 3458169689Skan base = NULL_RTX; 3459169689Skan 3460169689Skan if (base) 3461169689Skan addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base); 3462169689Skan 3463169689Skan start_sequence (); 3464169689Skan /* To avoid splitting addressing modes, pretend that no cse will 3465169689Skan follow. */ 3466169689Skan old_cse_not_expected = cse_not_expected; 3467169689Skan cse_not_expected = true; 3468169689Skan addr = memory_address (Pmode, addr); 3469169689Skan cse_not_expected = old_cse_not_expected; 3470169689Skan seq = get_insns (); 3471169689Skan end_sequence (); 3472169689Skan 3473169689Skan acost = seq_cost (seq); 3474169689Skan acost += address_cost (addr, Pmode); 3475169689Skan 3476169689Skan if (!acost) 3477169689Skan acost = 1; 3478169689Skan costs[sym_p][var_p][off_p][rat_p] = acost; 3479169689Skan } 3480169689Skan 3481169689Skan /* On some targets, it is quite expensive to load symbol to a register, 3482169689Skan which makes addresses that contain symbols look much more expensive. 3483169689Skan However, the symbol will have to be loaded in any case before the 3484169689Skan loop (and quite likely we have it in register already), so it does not 3485169689Skan make much sense to penalize them too heavily. So make some final 3486169689Skan tweaks for the SYMBOL_PRESENT modes: 3487169689Skan 3488169689Skan If VAR_PRESENT is false, and the mode obtained by changing symbol to 3489169689Skan var is cheaper, use this mode with small penalty. 3490169689Skan If VAR_PRESENT is true, try whether the mode with 3491169689Skan SYMBOL_PRESENT = false is cheaper even with cost of addition, and 3492169689Skan if this is the case, use it. */ 3493169689Skan add_c = add_cost (Pmode); 3494169689Skan for (i = 0; i < 8; i++) 3495169689Skan { 3496169689Skan var_p = i & 1; 3497169689Skan off_p = (i >> 1) & 1; 3498169689Skan rat_p = (i >> 2) & 1; 3499169689Skan 3500169689Skan acost = costs[0][1][off_p][rat_p] + 1; 3501169689Skan if (var_p) 3502169689Skan acost += add_c; 3503169689Skan 3504169689Skan if (acost < costs[1][var_p][off_p][rat_p]) 3505169689Skan costs[1][var_p][off_p][rat_p] = acost; 3506169689Skan } 3507169689Skan 3508169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3509169689Skan { 3510169689Skan fprintf (dump_file, "Address costs:\n"); 3511169689Skan 3512169689Skan for (i = 0; i < 16; i++) 3513169689Skan { 3514169689Skan sym_p = i & 1; 3515169689Skan var_p = (i >> 1) & 1; 3516169689Skan off_p = (i >> 2) & 1; 3517169689Skan rat_p = (i >> 3) & 1; 3518169689Skan 3519169689Skan fprintf (dump_file, " "); 3520169689Skan if (sym_p) 3521169689Skan fprintf (dump_file, "sym + "); 3522169689Skan if (var_p) 3523169689Skan fprintf (dump_file, "var + "); 3524169689Skan if (off_p) 3525169689Skan fprintf (dump_file, "cst + "); 3526169689Skan if (rat_p) 3527169689Skan fprintf (dump_file, "rat * "); 3528169689Skan 3529169689Skan acost = costs[sym_p][var_p][off_p][rat_p]; 3530169689Skan fprintf (dump_file, "index costs %d\n", acost); 3531169689Skan } 3532169689Skan fprintf (dump_file, "\n"); 3533169689Skan } 3534169689Skan } 3535169689Skan 3536169689Skan bits = GET_MODE_BITSIZE (Pmode); 3537169689Skan mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1); 3538169689Skan offset &= mask; 3539169689Skan if ((offset >> (bits - 1) & 1)) 3540169689Skan offset |= ~mask; 3541169689Skan s_offset = offset; 3542169689Skan 3543169689Skan cost = 0; 3544169689Skan offset_p = (s_offset != 0 3545169689Skan && min_offset <= s_offset && s_offset <= max_offset); 3546169689Skan ratio_p = (ratio != 1 3547169689Skan && multiplier_allowed_in_address_p (ratio)); 3548169689Skan 3549169689Skan if (ratio != 1 && !ratio_p) 3550169689Skan cost += multiply_by_cost (ratio, Pmode); 3551169689Skan 3552169689Skan if (s_offset && !offset_p && !symbol_present) 3553169689Skan { 3554169689Skan cost += add_cost (Pmode); 3555169689Skan var_present = true; 3556169689Skan } 3557169689Skan 3558169689Skan acost = costs[symbol_present][var_present][offset_p][ratio_p]; 3559169689Skan return cost + acost; 3560169689Skan} 3561169689Skan 3562169689Skan/* Estimates cost of forcing expression EXPR into a variable. */ 3563169689Skan 3564169689Skanunsigned 3565169689Skanforce_expr_to_var_cost (tree expr) 3566169689Skan{ 3567169689Skan static bool costs_initialized = false; 3568169689Skan static unsigned integer_cost; 3569169689Skan static unsigned symbol_cost; 3570169689Skan static unsigned address_cost; 3571169689Skan tree op0, op1; 3572169689Skan unsigned cost0, cost1, cost; 3573169689Skan enum machine_mode mode; 3574169689Skan 3575169689Skan if (!costs_initialized) 3576169689Skan { 3577169689Skan tree var = create_tmp_var_raw (integer_type_node, "test_var"); 3578169689Skan rtx x = gen_rtx_MEM (DECL_MODE (var), 3579169689Skan gen_rtx_SYMBOL_REF (Pmode, "test_var")); 3580169689Skan tree addr; 3581169689Skan tree type = build_pointer_type (integer_type_node); 3582169689Skan 3583169689Skan integer_cost = computation_cost (build_int_cst (integer_type_node, 3584169689Skan 2000)); 3585169689Skan 3586169689Skan SET_DECL_RTL (var, x); 3587169689Skan TREE_STATIC (var) = 1; 3588169689Skan addr = build1 (ADDR_EXPR, type, var); 3589169689Skan symbol_cost = computation_cost (addr) + 1; 3590169689Skan 3591169689Skan address_cost 3592169689Skan = computation_cost (build2 (PLUS_EXPR, type, 3593169689Skan addr, 3594169689Skan build_int_cst (type, 2000))) + 1; 3595169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3596169689Skan { 3597169689Skan fprintf (dump_file, "force_expr_to_var_cost:\n"); 3598169689Skan fprintf (dump_file, " integer %d\n", (int) integer_cost); 3599169689Skan fprintf (dump_file, " symbol %d\n", (int) symbol_cost); 3600169689Skan fprintf (dump_file, " address %d\n", (int) address_cost); 3601169689Skan fprintf (dump_file, " other %d\n", (int) target_spill_cost); 3602169689Skan fprintf (dump_file, "\n"); 3603169689Skan } 3604169689Skan 3605169689Skan costs_initialized = true; 3606169689Skan } 3607169689Skan 3608169689Skan STRIP_NOPS (expr); 3609169689Skan 3610169689Skan if (SSA_VAR_P (expr)) 3611169689Skan return 0; 3612169689Skan 3613169689Skan if (TREE_INVARIANT (expr)) 3614169689Skan { 3615169689Skan if (TREE_CODE (expr) == INTEGER_CST) 3616169689Skan return integer_cost; 3617169689Skan 3618169689Skan if (TREE_CODE (expr) == ADDR_EXPR) 3619169689Skan { 3620169689Skan tree obj = TREE_OPERAND (expr, 0); 3621169689Skan 3622169689Skan if (TREE_CODE (obj) == VAR_DECL 3623169689Skan || TREE_CODE (obj) == PARM_DECL 3624169689Skan || TREE_CODE (obj) == RESULT_DECL) 3625169689Skan return symbol_cost; 3626169689Skan } 3627169689Skan 3628169689Skan return address_cost; 3629169689Skan } 3630169689Skan 3631169689Skan switch (TREE_CODE (expr)) 3632169689Skan { 3633169689Skan case PLUS_EXPR: 3634169689Skan case MINUS_EXPR: 3635169689Skan case MULT_EXPR: 3636169689Skan op0 = TREE_OPERAND (expr, 0); 3637169689Skan op1 = TREE_OPERAND (expr, 1); 3638169689Skan STRIP_NOPS (op0); 3639169689Skan STRIP_NOPS (op1); 3640169689Skan 3641169689Skan if (is_gimple_val (op0)) 3642169689Skan cost0 = 0; 3643169689Skan else 3644169689Skan cost0 = force_expr_to_var_cost (op0); 3645169689Skan 3646169689Skan if (is_gimple_val (op1)) 3647169689Skan cost1 = 0; 3648169689Skan else 3649169689Skan cost1 = force_expr_to_var_cost (op1); 3650169689Skan 3651169689Skan break; 3652169689Skan 3653169689Skan default: 3654169689Skan /* Just an arbitrary value, FIXME. */ 3655169689Skan return target_spill_cost; 3656169689Skan } 3657169689Skan 3658169689Skan mode = TYPE_MODE (TREE_TYPE (expr)); 3659169689Skan switch (TREE_CODE (expr)) 3660169689Skan { 3661169689Skan case PLUS_EXPR: 3662169689Skan case MINUS_EXPR: 3663169689Skan cost = add_cost (mode); 3664169689Skan break; 3665169689Skan 3666169689Skan case MULT_EXPR: 3667169689Skan if (cst_and_fits_in_hwi (op0)) 3668169689Skan cost = multiply_by_cost (int_cst_value (op0), mode); 3669169689Skan else if (cst_and_fits_in_hwi (op1)) 3670169689Skan cost = multiply_by_cost (int_cst_value (op1), mode); 3671169689Skan else 3672169689Skan return target_spill_cost; 3673169689Skan break; 3674169689Skan 3675169689Skan default: 3676169689Skan gcc_unreachable (); 3677169689Skan } 3678169689Skan 3679169689Skan cost += cost0; 3680169689Skan cost += cost1; 3681169689Skan 3682169689Skan /* Bound the cost by target_spill_cost. The parts of complicated 3683169689Skan computations often are either loop invariant or at least can 3684169689Skan be shared between several iv uses, so letting this grow without 3685169689Skan limits would not give reasonable results. */ 3686169689Skan return cost < target_spill_cost ? cost : target_spill_cost; 3687169689Skan} 3688169689Skan 3689169689Skan/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the 3690169689Skan invariants the computation depends on. */ 3691169689Skan 3692169689Skanstatic unsigned 3693169689Skanforce_var_cost (struct ivopts_data *data, 3694169689Skan tree expr, bitmap *depends_on) 3695169689Skan{ 3696169689Skan if (depends_on) 3697169689Skan { 3698169689Skan fd_ivopts_data = data; 3699169689Skan walk_tree (&expr, find_depends, depends_on, NULL); 3700169689Skan } 3701169689Skan 3702169689Skan return force_expr_to_var_cost (expr); 3703169689Skan} 3704169689Skan 3705169689Skan/* Estimates cost of expressing address ADDR as var + symbol + offset. The 3706169689Skan value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set 3707169689Skan to false if the corresponding part is missing. DEPENDS_ON is a set of the 3708169689Skan invariants the computation depends on. */ 3709169689Skan 3710169689Skanstatic unsigned 3711169689Skansplit_address_cost (struct ivopts_data *data, 3712169689Skan tree addr, bool *symbol_present, bool *var_present, 3713169689Skan unsigned HOST_WIDE_INT *offset, bitmap *depends_on) 3714169689Skan{ 3715169689Skan tree core; 3716169689Skan HOST_WIDE_INT bitsize; 3717169689Skan HOST_WIDE_INT bitpos; 3718169689Skan tree toffset; 3719169689Skan enum machine_mode mode; 3720169689Skan int unsignedp, volatilep; 3721169689Skan 3722169689Skan core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode, 3723169689Skan &unsignedp, &volatilep, false); 3724169689Skan 3725169689Skan if (toffset != 0 3726169689Skan || bitpos % BITS_PER_UNIT != 0 3727169689Skan || TREE_CODE (core) != VAR_DECL) 3728169689Skan { 3729169689Skan *symbol_present = false; 3730169689Skan *var_present = true; 3731169689Skan fd_ivopts_data = data; 3732169689Skan walk_tree (&addr, find_depends, depends_on, NULL); 3733169689Skan return target_spill_cost; 3734169689Skan } 3735169689Skan 3736169689Skan *offset += bitpos / BITS_PER_UNIT; 3737169689Skan if (TREE_STATIC (core) 3738169689Skan || DECL_EXTERNAL (core)) 3739169689Skan { 3740169689Skan *symbol_present = true; 3741169689Skan *var_present = false; 3742169689Skan return 0; 3743169689Skan } 3744169689Skan 3745169689Skan *symbol_present = false; 3746169689Skan *var_present = true; 3747169689Skan return 0; 3748169689Skan} 3749169689Skan 3750169689Skan/* Estimates cost of expressing difference of addresses E1 - E2 as 3751169689Skan var + symbol + offset. The value of offset is added to OFFSET, 3752169689Skan SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding 3753169689Skan part is missing. DEPENDS_ON is a set of the invariants the computation 3754169689Skan depends on. */ 3755169689Skan 3756169689Skanstatic unsigned 3757169689Skanptr_difference_cost (struct ivopts_data *data, 3758169689Skan tree e1, tree e2, bool *symbol_present, bool *var_present, 3759169689Skan unsigned HOST_WIDE_INT *offset, bitmap *depends_on) 3760169689Skan{ 3761169689Skan HOST_WIDE_INT diff = 0; 3762169689Skan unsigned cost; 3763169689Skan 3764169689Skan gcc_assert (TREE_CODE (e1) == ADDR_EXPR); 3765169689Skan 3766169689Skan if (ptr_difference_const (e1, e2, &diff)) 3767169689Skan { 3768169689Skan *offset += diff; 3769169689Skan *symbol_present = false; 3770169689Skan *var_present = false; 3771169689Skan return 0; 3772169689Skan } 3773169689Skan 3774169689Skan if (e2 == integer_zero_node) 3775169689Skan return split_address_cost (data, TREE_OPERAND (e1, 0), 3776169689Skan symbol_present, var_present, offset, depends_on); 3777169689Skan 3778169689Skan *symbol_present = false; 3779169689Skan *var_present = true; 3780169689Skan 3781169689Skan cost = force_var_cost (data, e1, depends_on); 3782169689Skan cost += force_var_cost (data, e2, depends_on); 3783169689Skan cost += add_cost (Pmode); 3784169689Skan 3785169689Skan return cost; 3786169689Skan} 3787169689Skan 3788169689Skan/* Estimates cost of expressing difference E1 - E2 as 3789169689Skan var + symbol + offset. The value of offset is added to OFFSET, 3790169689Skan SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding 3791169689Skan part is missing. DEPENDS_ON is a set of the invariants the computation 3792169689Skan depends on. */ 3793169689Skan 3794169689Skanstatic unsigned 3795169689Skandifference_cost (struct ivopts_data *data, 3796169689Skan tree e1, tree e2, bool *symbol_present, bool *var_present, 3797169689Skan unsigned HOST_WIDE_INT *offset, bitmap *depends_on) 3798169689Skan{ 3799169689Skan unsigned cost; 3800169689Skan enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1)); 3801169689Skan unsigned HOST_WIDE_INT off1, off2; 3802169689Skan 3803169689Skan e1 = strip_offset (e1, &off1); 3804169689Skan e2 = strip_offset (e2, &off2); 3805169689Skan *offset += off1 - off2; 3806169689Skan 3807169689Skan STRIP_NOPS (e1); 3808169689Skan STRIP_NOPS (e2); 3809169689Skan 3810169689Skan if (TREE_CODE (e1) == ADDR_EXPR) 3811169689Skan return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset, 3812169689Skan depends_on); 3813169689Skan *symbol_present = false; 3814169689Skan 3815169689Skan if (operand_equal_p (e1, e2, 0)) 3816169689Skan { 3817169689Skan *var_present = false; 3818169689Skan return 0; 3819169689Skan } 3820169689Skan *var_present = true; 3821169689Skan if (zero_p (e2)) 3822169689Skan return force_var_cost (data, e1, depends_on); 3823169689Skan 3824169689Skan if (zero_p (e1)) 3825169689Skan { 3826169689Skan cost = force_var_cost (data, e2, depends_on); 3827169689Skan cost += multiply_by_cost (-1, mode); 3828169689Skan 3829169689Skan return cost; 3830169689Skan } 3831169689Skan 3832169689Skan cost = force_var_cost (data, e1, depends_on); 3833169689Skan cost += force_var_cost (data, e2, depends_on); 3834169689Skan cost += add_cost (mode); 3835169689Skan 3836169689Skan return cost; 3837169689Skan} 3838169689Skan 3839169689Skan/* Determines the cost of the computation by that USE is expressed 3840169689Skan from induction variable CAND. If ADDRESS_P is true, we just need 3841169689Skan to create an address from it, otherwise we want to get it into 3842169689Skan register. A set of invariants we depend on is stored in 3843169689Skan DEPENDS_ON. AT is the statement at that the value is computed. */ 3844169689Skan 3845169689Skanstatic unsigned 3846169689Skanget_computation_cost_at (struct ivopts_data *data, 3847169689Skan struct iv_use *use, struct iv_cand *cand, 3848169689Skan bool address_p, bitmap *depends_on, tree at) 3849169689Skan{ 3850169689Skan tree ubase = use->iv->base, ustep = use->iv->step; 3851169689Skan tree cbase, cstep; 3852169689Skan tree utype = TREE_TYPE (ubase), ctype; 3853169689Skan unsigned HOST_WIDE_INT ustepi, cstepi, offset = 0; 3854169689Skan HOST_WIDE_INT ratio, aratio; 3855169689Skan bool var_present, symbol_present; 3856169689Skan unsigned cost = 0, n_sums; 3857169689Skan 3858169689Skan *depends_on = NULL; 3859169689Skan 3860169689Skan /* Only consider real candidates. */ 3861169689Skan if (!cand->iv) 3862169689Skan return INFTY; 3863169689Skan 3864169689Skan cbase = cand->iv->base; 3865169689Skan cstep = cand->iv->step; 3866169689Skan ctype = TREE_TYPE (cbase); 3867169689Skan 3868169689Skan if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype)) 3869169689Skan { 3870169689Skan /* We do not have a precision to express the values of use. */ 3871169689Skan return INFTY; 3872169689Skan } 3873169689Skan 3874169689Skan if (address_p) 3875169689Skan { 3876169689Skan /* Do not try to express address of an object with computation based 3877169689Skan on address of a different object. This may cause problems in rtl 3878169689Skan level alias analysis (that does not expect this to be happening, 3879169689Skan as this is illegal in C), and would be unlikely to be useful 3880169689Skan anyway. */ 3881169689Skan if (use->iv->base_object 3882169689Skan && cand->iv->base_object 3883169689Skan && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0)) 3884169689Skan return INFTY; 3885169689Skan } 3886169689Skan 3887169689Skan if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype)) 3888169689Skan { 3889169689Skan /* TODO -- add direct handling of this case. */ 3890169689Skan goto fallback; 3891169689Skan } 3892169689Skan 3893169689Skan /* CSTEPI is removed from the offset in case statement is after the 3894169689Skan increment. If the step is not constant, we use zero instead. 3895169689Skan This is a bit imprecise (there is the extra addition), but 3896169689Skan redundancy elimination is likely to transform the code so that 3897169689Skan it uses value of the variable before increment anyway, 3898169689Skan so it is not that much unrealistic. */ 3899169689Skan if (cst_and_fits_in_hwi (cstep)) 3900169689Skan cstepi = int_cst_value (cstep); 3901169689Skan else 3902169689Skan cstepi = 0; 3903169689Skan 3904169689Skan if (cst_and_fits_in_hwi (ustep) 3905169689Skan && cst_and_fits_in_hwi (cstep)) 3906169689Skan { 3907169689Skan ustepi = int_cst_value (ustep); 3908169689Skan 3909169689Skan if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio)) 3910169689Skan return INFTY; 3911169689Skan } 3912169689Skan else 3913169689Skan { 3914169689Skan double_int rat; 3915169689Skan 3916169689Skan if (!constant_multiple_of (ustep, cstep, &rat)) 3917169689Skan return INFTY; 3918169689Skan 3919169689Skan if (double_int_fits_in_shwi_p (rat)) 3920169689Skan ratio = double_int_to_shwi (rat); 3921169689Skan else 3922169689Skan return INFTY; 3923169689Skan } 3924169689Skan 3925169689Skan /* use = ubase + ratio * (var - cbase). If either cbase is a constant 3926169689Skan or ratio == 1, it is better to handle this like 3927169689Skan 3928169689Skan ubase - ratio * cbase + ratio * var 3929169689Skan 3930169689Skan (also holds in the case ratio == -1, TODO. */ 3931169689Skan 3932169689Skan if (cst_and_fits_in_hwi (cbase)) 3933169689Skan { 3934169689Skan offset = - ratio * int_cst_value (cbase); 3935169689Skan cost += difference_cost (data, 3936169689Skan ubase, integer_zero_node, 3937169689Skan &symbol_present, &var_present, &offset, 3938169689Skan depends_on); 3939169689Skan } 3940169689Skan else if (ratio == 1) 3941169689Skan { 3942169689Skan cost += difference_cost (data, 3943169689Skan ubase, cbase, 3944169689Skan &symbol_present, &var_present, &offset, 3945169689Skan depends_on); 3946169689Skan } 3947169689Skan else 3948169689Skan { 3949169689Skan cost += force_var_cost (data, cbase, depends_on); 3950169689Skan cost += add_cost (TYPE_MODE (ctype)); 3951169689Skan cost += difference_cost (data, 3952169689Skan ubase, integer_zero_node, 3953169689Skan &symbol_present, &var_present, &offset, 3954169689Skan depends_on); 3955169689Skan } 3956169689Skan 3957169689Skan /* If we are after the increment, the value of the candidate is higher by 3958169689Skan one iteration. */ 3959169689Skan if (stmt_after_increment (data->current_loop, cand, at)) 3960169689Skan offset -= ratio * cstepi; 3961169689Skan 3962169689Skan /* Now the computation is in shape symbol + var1 + const + ratio * var2. 3963169689Skan (symbol/var/const parts may be omitted). If we are looking for an address, 3964169689Skan find the cost of addressing this. */ 3965169689Skan if (address_p) 3966169689Skan return cost + get_address_cost (symbol_present, var_present, offset, ratio); 3967169689Skan 3968169689Skan /* Otherwise estimate the costs for computing the expression. */ 3969169689Skan aratio = ratio > 0 ? ratio : -ratio; 3970169689Skan if (!symbol_present && !var_present && !offset) 3971169689Skan { 3972169689Skan if (ratio != 1) 3973169689Skan cost += multiply_by_cost (ratio, TYPE_MODE (ctype)); 3974169689Skan 3975169689Skan return cost; 3976169689Skan } 3977169689Skan 3978169689Skan if (aratio != 1) 3979169689Skan cost += multiply_by_cost (aratio, TYPE_MODE (ctype)); 3980169689Skan 3981169689Skan n_sums = 1; 3982169689Skan if (var_present 3983169689Skan /* Symbol + offset should be compile-time computable. */ 3984169689Skan && (symbol_present || offset)) 3985169689Skan n_sums++; 3986169689Skan 3987169689Skan return cost + n_sums * add_cost (TYPE_MODE (ctype)); 3988169689Skan 3989169689Skanfallback: 3990169689Skan { 3991169689Skan /* Just get the expression, expand it and measure the cost. */ 3992169689Skan tree comp = get_computation_at (data->current_loop, use, cand, at); 3993169689Skan 3994169689Skan if (!comp) 3995169689Skan return INFTY; 3996169689Skan 3997169689Skan if (address_p) 3998169689Skan comp = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (comp)), comp); 3999169689Skan 4000169689Skan return computation_cost (comp); 4001169689Skan } 4002169689Skan} 4003169689Skan 4004169689Skan/* Determines the cost of the computation by that USE is expressed 4005169689Skan from induction variable CAND. If ADDRESS_P is true, we just need 4006169689Skan to create an address from it, otherwise we want to get it into 4007169689Skan register. A set of invariants we depend on is stored in 4008169689Skan DEPENDS_ON. */ 4009169689Skan 4010169689Skanstatic unsigned 4011169689Skanget_computation_cost (struct ivopts_data *data, 4012169689Skan struct iv_use *use, struct iv_cand *cand, 4013169689Skan bool address_p, bitmap *depends_on) 4014169689Skan{ 4015169689Skan return get_computation_cost_at (data, 4016169689Skan use, cand, address_p, depends_on, use->stmt); 4017169689Skan} 4018169689Skan 4019169689Skan/* Determines cost of basing replacement of USE on CAND in a generic 4020169689Skan expression. */ 4021169689Skan 4022169689Skanstatic bool 4023169689Skandetermine_use_iv_cost_generic (struct ivopts_data *data, 4024169689Skan struct iv_use *use, struct iv_cand *cand) 4025169689Skan{ 4026169689Skan bitmap depends_on; 4027169689Skan unsigned cost; 4028169689Skan 4029169689Skan /* The simple case first -- if we need to express value of the preserved 4030169689Skan original biv, the cost is 0. This also prevents us from counting the 4031169689Skan cost of increment twice -- once at this use and once in the cost of 4032169689Skan the candidate. */ 4033169689Skan if (cand->pos == IP_ORIGINAL 4034169689Skan && cand->incremented_at == use->stmt) 4035169689Skan { 4036169689Skan set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE); 4037169689Skan return true; 4038169689Skan } 4039169689Skan 4040169689Skan cost = get_computation_cost (data, use, cand, false, &depends_on); 4041169689Skan set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE); 4042169689Skan 4043169689Skan return cost != INFTY; 4044169689Skan} 4045169689Skan 4046169689Skan/* Determines cost of basing replacement of USE on CAND in an address. */ 4047169689Skan 4048169689Skanstatic bool 4049169689Skandetermine_use_iv_cost_address (struct ivopts_data *data, 4050169689Skan struct iv_use *use, struct iv_cand *cand) 4051169689Skan{ 4052169689Skan bitmap depends_on; 4053169689Skan unsigned cost = get_computation_cost (data, use, cand, true, &depends_on); 4054169689Skan 4055169689Skan set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE); 4056169689Skan 4057169689Skan return cost != INFTY; 4058169689Skan} 4059169689Skan 4060169689Skan/* Computes value of induction variable IV in iteration NITER. */ 4061169689Skan 4062169689Skanstatic tree 4063169689Skaniv_value (struct iv *iv, tree niter) 4064169689Skan{ 4065169689Skan tree val; 4066169689Skan tree type = TREE_TYPE (iv->base); 4067169689Skan 4068169689Skan niter = fold_convert (type, niter); 4069169689Skan val = fold_build2 (MULT_EXPR, type, iv->step, niter); 4070169689Skan 4071169689Skan return fold_build2 (PLUS_EXPR, type, iv->base, val); 4072169689Skan} 4073169689Skan 4074169689Skan/* Computes value of candidate CAND at position AT in iteration NITER. */ 4075169689Skan 4076169689Skanstatic tree 4077169689Skancand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter) 4078169689Skan{ 4079169689Skan tree val = iv_value (cand->iv, niter); 4080169689Skan tree type = TREE_TYPE (cand->iv->base); 4081169689Skan 4082169689Skan if (stmt_after_increment (loop, cand, at)) 4083169689Skan val = fold_build2 (PLUS_EXPR, type, val, cand->iv->step); 4084169689Skan 4085169689Skan return val; 4086169689Skan} 4087169689Skan 4088169689Skan/* Returns period of induction variable iv. */ 4089169689Skan 4090169689Skanstatic tree 4091169689Skaniv_period (struct iv *iv) 4092169689Skan{ 4093169689Skan tree step = iv->step, period, type; 4094169689Skan tree pow2div; 4095169689Skan 4096169689Skan gcc_assert (step && TREE_CODE (step) == INTEGER_CST); 4097169689Skan 4098169689Skan /* Period of the iv is gcd (step, type range). Since type range is power 4099169689Skan of two, it suffices to determine the maximum power of two that divides 4100169689Skan step. */ 4101169689Skan pow2div = num_ending_zeros (step); 4102169689Skan type = unsigned_type_for (TREE_TYPE (step)); 4103169689Skan 4104169689Skan period = build_low_bits_mask (type, 4105169689Skan (TYPE_PRECISION (type) 4106169689Skan - tree_low_cst (pow2div, 1))); 4107169689Skan 4108169689Skan return period; 4109169689Skan} 4110169689Skan 4111169689Skan/* Returns the comparison operator used when eliminating the iv USE. */ 4112169689Skan 4113169689Skanstatic enum tree_code 4114169689Skaniv_elimination_compare (struct ivopts_data *data, struct iv_use *use) 4115169689Skan{ 4116169689Skan struct loop *loop = data->current_loop; 4117169689Skan basic_block ex_bb; 4118169689Skan edge exit; 4119169689Skan 4120169689Skan ex_bb = bb_for_stmt (use->stmt); 4121169689Skan exit = EDGE_SUCC (ex_bb, 0); 4122169689Skan if (flow_bb_inside_loop_p (loop, exit->dest)) 4123169689Skan exit = EDGE_SUCC (ex_bb, 1); 4124169689Skan 4125169689Skan return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR); 4126169689Skan} 4127169689Skan 4128169689Skan/* Check whether it is possible to express the condition in USE by comparison 4129169689Skan of candidate CAND. If so, store the value compared with to BOUND. */ 4130169689Skan 4131169689Skanstatic bool 4132169689Skanmay_eliminate_iv (struct ivopts_data *data, 4133169689Skan struct iv_use *use, struct iv_cand *cand, tree *bound) 4134169689Skan{ 4135169689Skan basic_block ex_bb; 4136169689Skan edge exit; 4137169689Skan tree nit, nit_type; 4138169689Skan tree wider_type, period, per_type; 4139169689Skan struct loop *loop = data->current_loop; 4140169689Skan 4141169689Skan if (TREE_CODE (cand->iv->step) != INTEGER_CST) 4142169689Skan return false; 4143169689Skan 4144169689Skan /* For now works only for exits that dominate the loop latch. TODO -- extend 4145169689Skan for other conditions inside loop body. */ 4146169689Skan ex_bb = bb_for_stmt (use->stmt); 4147169689Skan if (use->stmt != last_stmt (ex_bb) 4148169689Skan || TREE_CODE (use->stmt) != COND_EXPR) 4149169689Skan return false; 4150169689Skan if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb)) 4151169689Skan return false; 4152169689Skan 4153169689Skan exit = EDGE_SUCC (ex_bb, 0); 4154169689Skan if (flow_bb_inside_loop_p (loop, exit->dest)) 4155169689Skan exit = EDGE_SUCC (ex_bb, 1); 4156169689Skan if (flow_bb_inside_loop_p (loop, exit->dest)) 4157169689Skan return false; 4158169689Skan 4159169689Skan nit = niter_for_exit (data, exit); 4160169689Skan if (!nit) 4161169689Skan return false; 4162169689Skan 4163169689Skan nit_type = TREE_TYPE (nit); 4164169689Skan 4165169689Skan /* Determine whether we may use the variable to test whether niter iterations 4166169689Skan elapsed. This is the case iff the period of the induction variable is 4167169689Skan greater than the number of iterations. */ 4168169689Skan period = iv_period (cand->iv); 4169169689Skan if (!period) 4170169689Skan return false; 4171169689Skan per_type = TREE_TYPE (period); 4172169689Skan 4173169689Skan wider_type = TREE_TYPE (period); 4174169689Skan if (TYPE_PRECISION (nit_type) < TYPE_PRECISION (per_type)) 4175169689Skan wider_type = per_type; 4176169689Skan else 4177169689Skan wider_type = nit_type; 4178169689Skan 4179169689Skan if (!integer_nonzerop (fold_build2 (GE_EXPR, boolean_type_node, 4180169689Skan fold_convert (wider_type, period), 4181169689Skan fold_convert (wider_type, nit)))) 4182169689Skan return false; 4183169689Skan 4184169689Skan *bound = fold_affine_expr (cand_value_at (loop, cand, use->stmt, nit)); 4185169689Skan return true; 4186169689Skan} 4187169689Skan 4188169689Skan/* Determines cost of basing replacement of USE on CAND in a condition. */ 4189169689Skan 4190169689Skanstatic bool 4191169689Skandetermine_use_iv_cost_condition (struct ivopts_data *data, 4192169689Skan struct iv_use *use, struct iv_cand *cand) 4193169689Skan{ 4194169689Skan tree bound = NULL_TREE, op, cond; 4195169689Skan bitmap depends_on = NULL; 4196169689Skan unsigned cost; 4197169689Skan 4198169689Skan /* Only consider real candidates. */ 4199169689Skan if (!cand->iv) 4200169689Skan { 4201169689Skan set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE); 4202169689Skan return false; 4203169689Skan } 4204169689Skan 4205169689Skan if (may_eliminate_iv (data, use, cand, &bound)) 4206169689Skan { 4207169689Skan cost = force_var_cost (data, bound, &depends_on); 4208169689Skan 4209169689Skan set_use_iv_cost (data, use, cand, cost, depends_on, bound); 4210169689Skan return cost != INFTY; 4211169689Skan } 4212169689Skan 4213169689Skan /* The induction variable elimination failed; just express the original 4214169689Skan giv. If it is compared with an invariant, note that we cannot get 4215169689Skan rid of it. */ 4216169689Skan cost = get_computation_cost (data, use, cand, false, &depends_on); 4217169689Skan 4218169689Skan cond = *use->op_p; 4219169689Skan if (TREE_CODE (cond) != SSA_NAME) 4220169689Skan { 4221169689Skan op = TREE_OPERAND (cond, 0); 4222169689Skan if (TREE_CODE (op) == SSA_NAME && !zero_p (get_iv (data, op)->step)) 4223169689Skan op = TREE_OPERAND (cond, 1); 4224169689Skan if (TREE_CODE (op) == SSA_NAME) 4225169689Skan { 4226169689Skan op = get_iv (data, op)->base; 4227169689Skan fd_ivopts_data = data; 4228169689Skan walk_tree (&op, find_depends, &depends_on, NULL); 4229169689Skan } 4230169689Skan } 4231169689Skan 4232169689Skan set_use_iv_cost (data, use, cand, cost, depends_on, NULL); 4233169689Skan return cost != INFTY; 4234169689Skan} 4235169689Skan 4236169689Skan/* Determines cost of basing replacement of USE on CAND. Returns false 4237169689Skan if USE cannot be based on CAND. */ 4238169689Skan 4239169689Skanstatic bool 4240169689Skandetermine_use_iv_cost (struct ivopts_data *data, 4241169689Skan struct iv_use *use, struct iv_cand *cand) 4242169689Skan{ 4243169689Skan switch (use->type) 4244169689Skan { 4245169689Skan case USE_NONLINEAR_EXPR: 4246169689Skan return determine_use_iv_cost_generic (data, use, cand); 4247169689Skan 4248169689Skan case USE_ADDRESS: 4249169689Skan return determine_use_iv_cost_address (data, use, cand); 4250169689Skan 4251169689Skan case USE_COMPARE: 4252169689Skan return determine_use_iv_cost_condition (data, use, cand); 4253169689Skan 4254169689Skan default: 4255169689Skan gcc_unreachable (); 4256169689Skan } 4257169689Skan} 4258169689Skan 4259169689Skan/* Determines costs of basing the use of the iv on an iv candidate. */ 4260169689Skan 4261169689Skanstatic void 4262169689Skandetermine_use_iv_costs (struct ivopts_data *data) 4263169689Skan{ 4264169689Skan unsigned i, j; 4265169689Skan struct iv_use *use; 4266169689Skan struct iv_cand *cand; 4267169689Skan bitmap to_clear = BITMAP_ALLOC (NULL); 4268169689Skan 4269169689Skan alloc_use_cost_map (data); 4270169689Skan 4271169689Skan for (i = 0; i < n_iv_uses (data); i++) 4272169689Skan { 4273169689Skan use = iv_use (data, i); 4274169689Skan 4275169689Skan if (data->consider_all_candidates) 4276169689Skan { 4277169689Skan for (j = 0; j < n_iv_cands (data); j++) 4278169689Skan { 4279169689Skan cand = iv_cand (data, j); 4280169689Skan determine_use_iv_cost (data, use, cand); 4281169689Skan } 4282169689Skan } 4283169689Skan else 4284169689Skan { 4285169689Skan bitmap_iterator bi; 4286169689Skan 4287169689Skan EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi) 4288169689Skan { 4289169689Skan cand = iv_cand (data, j); 4290169689Skan if (!determine_use_iv_cost (data, use, cand)) 4291169689Skan bitmap_set_bit (to_clear, j); 4292169689Skan } 4293169689Skan 4294169689Skan /* Remove the candidates for that the cost is infinite from 4295169689Skan the list of related candidates. */ 4296169689Skan bitmap_and_compl_into (use->related_cands, to_clear); 4297169689Skan bitmap_clear (to_clear); 4298169689Skan } 4299169689Skan } 4300169689Skan 4301169689Skan BITMAP_FREE (to_clear); 4302169689Skan 4303169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4304169689Skan { 4305169689Skan fprintf (dump_file, "Use-candidate costs:\n"); 4306169689Skan 4307169689Skan for (i = 0; i < n_iv_uses (data); i++) 4308169689Skan { 4309169689Skan use = iv_use (data, i); 4310169689Skan 4311169689Skan fprintf (dump_file, "Use %d:\n", i); 4312169689Skan fprintf (dump_file, " cand\tcost\tdepends on\n"); 4313169689Skan for (j = 0; j < use->n_map_members; j++) 4314169689Skan { 4315169689Skan if (!use->cost_map[j].cand 4316169689Skan || use->cost_map[j].cost == INFTY) 4317169689Skan continue; 4318169689Skan 4319169689Skan fprintf (dump_file, " %d\t%d\t", 4320169689Skan use->cost_map[j].cand->id, 4321169689Skan use->cost_map[j].cost); 4322169689Skan if (use->cost_map[j].depends_on) 4323169689Skan bitmap_print (dump_file, 4324169689Skan use->cost_map[j].depends_on, "",""); 4325169689Skan fprintf (dump_file, "\n"); 4326169689Skan } 4327169689Skan 4328169689Skan fprintf (dump_file, "\n"); 4329169689Skan } 4330169689Skan fprintf (dump_file, "\n"); 4331169689Skan } 4332169689Skan} 4333169689Skan 4334169689Skan/* Determines cost of the candidate CAND. */ 4335169689Skan 4336169689Skanstatic void 4337169689Skandetermine_iv_cost (struct ivopts_data *data, struct iv_cand *cand) 4338169689Skan{ 4339169689Skan unsigned cost_base, cost_step; 4340169689Skan tree base; 4341169689Skan 4342169689Skan if (!cand->iv) 4343169689Skan { 4344169689Skan cand->cost = 0; 4345169689Skan return; 4346169689Skan } 4347169689Skan 4348169689Skan /* There are two costs associated with the candidate -- its increment 4349169689Skan and its initialization. The second is almost negligible for any loop 4350169689Skan that rolls enough, so we take it just very little into account. */ 4351169689Skan 4352169689Skan base = cand->iv->base; 4353169689Skan cost_base = force_var_cost (data, base, NULL); 4354169689Skan cost_step = add_cost (TYPE_MODE (TREE_TYPE (base))); 4355169689Skan 4356169689Skan cand->cost = cost_step + cost_base / AVG_LOOP_NITER (current_loop); 4357169689Skan 4358169689Skan /* Prefer the original iv unless we may gain something by replacing it; 4359169689Skan this is not really relevant for artificial ivs created by other 4360169689Skan passes. */ 4361169689Skan if (cand->pos == IP_ORIGINAL 4362169689Skan && !DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before))) 4363169689Skan cand->cost--; 4364169689Skan 4365169689Skan /* Prefer not to insert statements into latch unless there are some 4366169689Skan already (so that we do not create unnecessary jumps). */ 4367169689Skan if (cand->pos == IP_END 4368169689Skan && empty_block_p (ip_end_pos (data->current_loop))) 4369169689Skan cand->cost++; 4370169689Skan} 4371169689Skan 4372169689Skan/* Determines costs of computation of the candidates. */ 4373169689Skan 4374169689Skanstatic void 4375169689Skandetermine_iv_costs (struct ivopts_data *data) 4376169689Skan{ 4377169689Skan unsigned i; 4378169689Skan 4379169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4380169689Skan { 4381169689Skan fprintf (dump_file, "Candidate costs:\n"); 4382169689Skan fprintf (dump_file, " cand\tcost\n"); 4383169689Skan } 4384169689Skan 4385169689Skan for (i = 0; i < n_iv_cands (data); i++) 4386169689Skan { 4387169689Skan struct iv_cand *cand = iv_cand (data, i); 4388169689Skan 4389169689Skan determine_iv_cost (data, cand); 4390169689Skan 4391169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4392169689Skan fprintf (dump_file, " %d\t%d\n", i, cand->cost); 4393169689Skan } 4394169689Skan 4395169689Skanif (dump_file && (dump_flags & TDF_DETAILS)) 4396169689Skan fprintf (dump_file, "\n"); 4397169689Skan} 4398169689Skan 4399169689Skan/* Calculates cost for having SIZE induction variables. */ 4400169689Skan 4401169689Skanstatic unsigned 4402169689Skanivopts_global_cost_for_size (struct ivopts_data *data, unsigned size) 4403169689Skan{ 4404169689Skan return global_cost_for_size (size, data->regs_used, n_iv_uses (data)); 4405169689Skan} 4406169689Skan 4407169689Skan/* For each size of the induction variable set determine the penalty. */ 4408169689Skan 4409169689Skanstatic void 4410169689Skandetermine_set_costs (struct ivopts_data *data) 4411169689Skan{ 4412169689Skan unsigned j, n; 4413169689Skan tree phi, op; 4414169689Skan struct loop *loop = data->current_loop; 4415169689Skan bitmap_iterator bi; 4416169689Skan 4417169689Skan /* We use the following model (definitely improvable, especially the 4418169689Skan cost function -- TODO): 4419169689Skan 4420169689Skan We estimate the number of registers available (using MD data), name it A. 4421169689Skan 4422169689Skan We estimate the number of registers used by the loop, name it U. This 4423169689Skan number is obtained as the number of loop phi nodes (not counting virtual 4424169689Skan registers and bivs) + the number of variables from outside of the loop. 4425169689Skan 4426169689Skan We set a reserve R (free regs that are used for temporary computations, 4427169689Skan etc.). For now the reserve is a constant 3. 4428169689Skan 4429169689Skan Let I be the number of induction variables. 4430169689Skan 4431169689Skan -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage 4432169689Skan make a lot of ivs without a reason). 4433169689Skan -- if A - R < U + I <= A, the cost is I * PRES_COST 4434169689Skan -- if U + I > A, the cost is I * PRES_COST and 4435169689Skan number of uses * SPILL_COST * (U + I - A) / (U + I) is added. */ 4436169689Skan 4437169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4438169689Skan { 4439169689Skan fprintf (dump_file, "Global costs:\n"); 4440169689Skan fprintf (dump_file, " target_avail_regs %d\n", target_avail_regs); 4441169689Skan fprintf (dump_file, " target_small_cost %d\n", target_small_cost); 4442169689Skan fprintf (dump_file, " target_pres_cost %d\n", target_pres_cost); 4443169689Skan fprintf (dump_file, " target_spill_cost %d\n", target_spill_cost); 4444169689Skan } 4445169689Skan 4446169689Skan n = 0; 4447169689Skan for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi)) 4448169689Skan { 4449169689Skan op = PHI_RESULT (phi); 4450169689Skan 4451169689Skan if (!is_gimple_reg (op)) 4452169689Skan continue; 4453169689Skan 4454169689Skan if (get_iv (data, op)) 4455169689Skan continue; 4456169689Skan 4457169689Skan n++; 4458169689Skan } 4459169689Skan 4460169689Skan EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi) 4461169689Skan { 4462169689Skan struct version_info *info = ver_info (data, j); 4463169689Skan 4464169689Skan if (info->inv_id && info->has_nonlin_use) 4465169689Skan n++; 4466169689Skan } 4467169689Skan 4468169689Skan data->regs_used = n; 4469169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4470169689Skan fprintf (dump_file, " regs_used %d\n", n); 4471169689Skan 4472169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4473169689Skan { 4474169689Skan fprintf (dump_file, " cost for size:\n"); 4475169689Skan fprintf (dump_file, " ivs\tcost\n"); 4476169689Skan for (j = 0; j <= 2 * target_avail_regs; j++) 4477169689Skan fprintf (dump_file, " %d\t%d\n", j, 4478169689Skan ivopts_global_cost_for_size (data, j)); 4479169689Skan fprintf (dump_file, "\n"); 4480169689Skan } 4481169689Skan} 4482169689Skan 4483169689Skan/* Returns true if A is a cheaper cost pair than B. */ 4484169689Skan 4485169689Skanstatic bool 4486169689Skancheaper_cost_pair (struct cost_pair *a, struct cost_pair *b) 4487169689Skan{ 4488169689Skan if (!a) 4489169689Skan return false; 4490169689Skan 4491169689Skan if (!b) 4492169689Skan return true; 4493169689Skan 4494169689Skan if (a->cost < b->cost) 4495169689Skan return true; 4496169689Skan 4497169689Skan if (a->cost > b->cost) 4498169689Skan return false; 4499169689Skan 4500169689Skan /* In case the costs are the same, prefer the cheaper candidate. */ 4501169689Skan if (a->cand->cost < b->cand->cost) 4502169689Skan return true; 4503169689Skan 4504169689Skan return false; 4505169689Skan} 4506169689Skan 4507169689Skan/* Computes the cost field of IVS structure. */ 4508169689Skan 4509169689Skanstatic void 4510169689Skaniv_ca_recount_cost (struct ivopts_data *data, struct iv_ca *ivs) 4511169689Skan{ 4512169689Skan unsigned cost = 0; 4513169689Skan 4514169689Skan cost += ivs->cand_use_cost; 4515169689Skan cost += ivs->cand_cost; 4516169689Skan cost += ivopts_global_cost_for_size (data, ivs->n_regs); 4517169689Skan 4518169689Skan ivs->cost = cost; 4519169689Skan} 4520169689Skan 4521169689Skan/* Remove invariants in set INVS to set IVS. */ 4522169689Skan 4523169689Skanstatic void 4524169689Skaniv_ca_set_remove_invariants (struct iv_ca *ivs, bitmap invs) 4525169689Skan{ 4526169689Skan bitmap_iterator bi; 4527169689Skan unsigned iid; 4528169689Skan 4529169689Skan if (!invs) 4530169689Skan return; 4531169689Skan 4532169689Skan EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi) 4533169689Skan { 4534169689Skan ivs->n_invariant_uses[iid]--; 4535169689Skan if (ivs->n_invariant_uses[iid] == 0) 4536169689Skan ivs->n_regs--; 4537169689Skan } 4538169689Skan} 4539169689Skan 4540169689Skan/* Set USE not to be expressed by any candidate in IVS. */ 4541169689Skan 4542169689Skanstatic void 4543169689Skaniv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs, 4544169689Skan struct iv_use *use) 4545169689Skan{ 4546169689Skan unsigned uid = use->id, cid; 4547169689Skan struct cost_pair *cp; 4548169689Skan 4549169689Skan cp = ivs->cand_for_use[uid]; 4550169689Skan if (!cp) 4551169689Skan return; 4552169689Skan cid = cp->cand->id; 4553169689Skan 4554169689Skan ivs->bad_uses++; 4555169689Skan ivs->cand_for_use[uid] = NULL; 4556169689Skan ivs->n_cand_uses[cid]--; 4557169689Skan 4558169689Skan if (ivs->n_cand_uses[cid] == 0) 4559169689Skan { 4560169689Skan bitmap_clear_bit (ivs->cands, cid); 4561169689Skan /* Do not count the pseudocandidates. */ 4562169689Skan if (cp->cand->iv) 4563169689Skan ivs->n_regs--; 4564169689Skan ivs->n_cands--; 4565169689Skan ivs->cand_cost -= cp->cand->cost; 4566169689Skan 4567169689Skan iv_ca_set_remove_invariants (ivs, cp->cand->depends_on); 4568169689Skan } 4569169689Skan 4570169689Skan ivs->cand_use_cost -= cp->cost; 4571169689Skan 4572169689Skan iv_ca_set_remove_invariants (ivs, cp->depends_on); 4573169689Skan iv_ca_recount_cost (data, ivs); 4574169689Skan} 4575169689Skan 4576169689Skan/* Add invariants in set INVS to set IVS. */ 4577169689Skan 4578169689Skanstatic void 4579169689Skaniv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs) 4580169689Skan{ 4581169689Skan bitmap_iterator bi; 4582169689Skan unsigned iid; 4583169689Skan 4584169689Skan if (!invs) 4585169689Skan return; 4586169689Skan 4587169689Skan EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi) 4588169689Skan { 4589169689Skan ivs->n_invariant_uses[iid]++; 4590169689Skan if (ivs->n_invariant_uses[iid] == 1) 4591169689Skan ivs->n_regs++; 4592169689Skan } 4593169689Skan} 4594169689Skan 4595169689Skan/* Set cost pair for USE in set IVS to CP. */ 4596169689Skan 4597169689Skanstatic void 4598169689Skaniv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs, 4599169689Skan struct iv_use *use, struct cost_pair *cp) 4600169689Skan{ 4601169689Skan unsigned uid = use->id, cid; 4602169689Skan 4603169689Skan if (ivs->cand_for_use[uid] == cp) 4604169689Skan return; 4605169689Skan 4606169689Skan if (ivs->cand_for_use[uid]) 4607169689Skan iv_ca_set_no_cp (data, ivs, use); 4608169689Skan 4609169689Skan if (cp) 4610169689Skan { 4611169689Skan cid = cp->cand->id; 4612169689Skan 4613169689Skan ivs->bad_uses--; 4614169689Skan ivs->cand_for_use[uid] = cp; 4615169689Skan ivs->n_cand_uses[cid]++; 4616169689Skan if (ivs->n_cand_uses[cid] == 1) 4617169689Skan { 4618169689Skan bitmap_set_bit (ivs->cands, cid); 4619169689Skan /* Do not count the pseudocandidates. */ 4620169689Skan if (cp->cand->iv) 4621169689Skan ivs->n_regs++; 4622169689Skan ivs->n_cands++; 4623169689Skan ivs->cand_cost += cp->cand->cost; 4624169689Skan 4625169689Skan iv_ca_set_add_invariants (ivs, cp->cand->depends_on); 4626169689Skan } 4627169689Skan 4628169689Skan ivs->cand_use_cost += cp->cost; 4629169689Skan iv_ca_set_add_invariants (ivs, cp->depends_on); 4630169689Skan iv_ca_recount_cost (data, ivs); 4631169689Skan } 4632169689Skan} 4633169689Skan 4634169689Skan/* Extend set IVS by expressing USE by some of the candidates in it 4635169689Skan if possible. */ 4636169689Skan 4637169689Skanstatic void 4638169689Skaniv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs, 4639169689Skan struct iv_use *use) 4640169689Skan{ 4641169689Skan struct cost_pair *best_cp = NULL, *cp; 4642169689Skan bitmap_iterator bi; 4643169689Skan unsigned i; 4644169689Skan 4645169689Skan gcc_assert (ivs->upto >= use->id); 4646169689Skan 4647169689Skan if (ivs->upto == use->id) 4648169689Skan { 4649169689Skan ivs->upto++; 4650169689Skan ivs->bad_uses++; 4651169689Skan } 4652169689Skan 4653169689Skan EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi) 4654169689Skan { 4655169689Skan cp = get_use_iv_cost (data, use, iv_cand (data, i)); 4656169689Skan 4657169689Skan if (cheaper_cost_pair (cp, best_cp)) 4658169689Skan best_cp = cp; 4659169689Skan } 4660169689Skan 4661169689Skan iv_ca_set_cp (data, ivs, use, best_cp); 4662169689Skan} 4663169689Skan 4664169689Skan/* Get cost for assignment IVS. */ 4665169689Skan 4666169689Skanstatic unsigned 4667169689Skaniv_ca_cost (struct iv_ca *ivs) 4668169689Skan{ 4669169689Skan return (ivs->bad_uses ? INFTY : ivs->cost); 4670169689Skan} 4671169689Skan 4672169689Skan/* Returns true if all dependences of CP are among invariants in IVS. */ 4673169689Skan 4674169689Skanstatic bool 4675169689Skaniv_ca_has_deps (struct iv_ca *ivs, struct cost_pair *cp) 4676169689Skan{ 4677169689Skan unsigned i; 4678169689Skan bitmap_iterator bi; 4679169689Skan 4680169689Skan if (!cp->depends_on) 4681169689Skan return true; 4682169689Skan 4683169689Skan EXECUTE_IF_SET_IN_BITMAP (cp->depends_on, 0, i, bi) 4684169689Skan { 4685169689Skan if (ivs->n_invariant_uses[i] == 0) 4686169689Skan return false; 4687169689Skan } 4688169689Skan 4689169689Skan return true; 4690169689Skan} 4691169689Skan 4692169689Skan/* Creates change of expressing USE by NEW_CP instead of OLD_CP and chains 4693169689Skan it before NEXT_CHANGE. */ 4694169689Skan 4695169689Skanstatic struct iv_ca_delta * 4696169689Skaniv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp, 4697169689Skan struct cost_pair *new_cp, struct iv_ca_delta *next_change) 4698169689Skan{ 4699169689Skan struct iv_ca_delta *change = XNEW (struct iv_ca_delta); 4700169689Skan 4701169689Skan change->use = use; 4702169689Skan change->old_cp = old_cp; 4703169689Skan change->new_cp = new_cp; 4704169689Skan change->next_change = next_change; 4705169689Skan 4706169689Skan return change; 4707169689Skan} 4708169689Skan 4709169689Skan/* Joins two lists of changes L1 and L2. Destructive -- old lists 4710169689Skan are rewritten. */ 4711169689Skan 4712169689Skanstatic struct iv_ca_delta * 4713169689Skaniv_ca_delta_join (struct iv_ca_delta *l1, struct iv_ca_delta *l2) 4714169689Skan{ 4715169689Skan struct iv_ca_delta *last; 4716169689Skan 4717169689Skan if (!l2) 4718169689Skan return l1; 4719169689Skan 4720169689Skan if (!l1) 4721169689Skan return l2; 4722169689Skan 4723169689Skan for (last = l1; last->next_change; last = last->next_change) 4724169689Skan continue; 4725169689Skan last->next_change = l2; 4726169689Skan 4727169689Skan return l1; 4728169689Skan} 4729169689Skan 4730169689Skan/* Returns candidate by that USE is expressed in IVS. */ 4731169689Skan 4732169689Skanstatic struct cost_pair * 4733169689Skaniv_ca_cand_for_use (struct iv_ca *ivs, struct iv_use *use) 4734169689Skan{ 4735169689Skan return ivs->cand_for_use[use->id]; 4736169689Skan} 4737169689Skan 4738169689Skan/* Reverse the list of changes DELTA, forming the inverse to it. */ 4739169689Skan 4740169689Skanstatic struct iv_ca_delta * 4741169689Skaniv_ca_delta_reverse (struct iv_ca_delta *delta) 4742169689Skan{ 4743169689Skan struct iv_ca_delta *act, *next, *prev = NULL; 4744169689Skan struct cost_pair *tmp; 4745169689Skan 4746169689Skan for (act = delta; act; act = next) 4747169689Skan { 4748169689Skan next = act->next_change; 4749169689Skan act->next_change = prev; 4750169689Skan prev = act; 4751169689Skan 4752169689Skan tmp = act->old_cp; 4753169689Skan act->old_cp = act->new_cp; 4754169689Skan act->new_cp = tmp; 4755169689Skan } 4756169689Skan 4757169689Skan return prev; 4758169689Skan} 4759169689Skan 4760169689Skan/* Commit changes in DELTA to IVS. If FORWARD is false, the changes are 4761169689Skan reverted instead. */ 4762169689Skan 4763169689Skanstatic void 4764169689Skaniv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs, 4765169689Skan struct iv_ca_delta *delta, bool forward) 4766169689Skan{ 4767169689Skan struct cost_pair *from, *to; 4768169689Skan struct iv_ca_delta *act; 4769169689Skan 4770169689Skan if (!forward) 4771169689Skan delta = iv_ca_delta_reverse (delta); 4772169689Skan 4773169689Skan for (act = delta; act; act = act->next_change) 4774169689Skan { 4775169689Skan from = act->old_cp; 4776169689Skan to = act->new_cp; 4777169689Skan gcc_assert (iv_ca_cand_for_use (ivs, act->use) == from); 4778169689Skan iv_ca_set_cp (data, ivs, act->use, to); 4779169689Skan } 4780169689Skan 4781169689Skan if (!forward) 4782169689Skan iv_ca_delta_reverse (delta); 4783169689Skan} 4784169689Skan 4785169689Skan/* Returns true if CAND is used in IVS. */ 4786169689Skan 4787169689Skanstatic bool 4788169689Skaniv_ca_cand_used_p (struct iv_ca *ivs, struct iv_cand *cand) 4789169689Skan{ 4790169689Skan return ivs->n_cand_uses[cand->id] > 0; 4791169689Skan} 4792169689Skan 4793169689Skan/* Returns number of induction variable candidates in the set IVS. */ 4794169689Skan 4795169689Skanstatic unsigned 4796169689Skaniv_ca_n_cands (struct iv_ca *ivs) 4797169689Skan{ 4798169689Skan return ivs->n_cands; 4799169689Skan} 4800169689Skan 4801169689Skan/* Free the list of changes DELTA. */ 4802169689Skan 4803169689Skanstatic void 4804169689Skaniv_ca_delta_free (struct iv_ca_delta **delta) 4805169689Skan{ 4806169689Skan struct iv_ca_delta *act, *next; 4807169689Skan 4808169689Skan for (act = *delta; act; act = next) 4809169689Skan { 4810169689Skan next = act->next_change; 4811169689Skan free (act); 4812169689Skan } 4813169689Skan 4814169689Skan *delta = NULL; 4815169689Skan} 4816169689Skan 4817169689Skan/* Allocates new iv candidates assignment. */ 4818169689Skan 4819169689Skanstatic struct iv_ca * 4820169689Skaniv_ca_new (struct ivopts_data *data) 4821169689Skan{ 4822169689Skan struct iv_ca *nw = XNEW (struct iv_ca); 4823169689Skan 4824169689Skan nw->upto = 0; 4825169689Skan nw->bad_uses = 0; 4826169689Skan nw->cand_for_use = XCNEWVEC (struct cost_pair *, n_iv_uses (data)); 4827169689Skan nw->n_cand_uses = XCNEWVEC (unsigned, n_iv_cands (data)); 4828169689Skan nw->cands = BITMAP_ALLOC (NULL); 4829169689Skan nw->n_cands = 0; 4830169689Skan nw->n_regs = 0; 4831169689Skan nw->cand_use_cost = 0; 4832169689Skan nw->cand_cost = 0; 4833169689Skan nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1); 4834169689Skan nw->cost = 0; 4835169689Skan 4836169689Skan return nw; 4837169689Skan} 4838169689Skan 4839169689Skan/* Free memory occupied by the set IVS. */ 4840169689Skan 4841169689Skanstatic void 4842169689Skaniv_ca_free (struct iv_ca **ivs) 4843169689Skan{ 4844169689Skan free ((*ivs)->cand_for_use); 4845169689Skan free ((*ivs)->n_cand_uses); 4846169689Skan BITMAP_FREE ((*ivs)->cands); 4847169689Skan free ((*ivs)->n_invariant_uses); 4848169689Skan free (*ivs); 4849169689Skan *ivs = NULL; 4850169689Skan} 4851169689Skan 4852169689Skan/* Dumps IVS to FILE. */ 4853169689Skan 4854169689Skanstatic void 4855169689Skaniv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs) 4856169689Skan{ 4857169689Skan const char *pref = " invariants "; 4858169689Skan unsigned i; 4859169689Skan 4860169689Skan fprintf (file, " cost %d\n", iv_ca_cost (ivs)); 4861169689Skan bitmap_print (file, ivs->cands, " candidates ","\n"); 4862169689Skan 4863169689Skan for (i = 1; i <= data->max_inv_id; i++) 4864169689Skan if (ivs->n_invariant_uses[i]) 4865169689Skan { 4866169689Skan fprintf (file, "%s%d", pref, i); 4867169689Skan pref = ", "; 4868169689Skan } 4869169689Skan fprintf (file, "\n"); 4870169689Skan} 4871169689Skan 4872169689Skan/* Try changing candidate in IVS to CAND for each use. Return cost of the 4873169689Skan new set, and store differences in DELTA. Number of induction variables 4874169689Skan in the new set is stored to N_IVS. */ 4875169689Skan 4876169689Skanstatic unsigned 4877169689Skaniv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs, 4878169689Skan struct iv_cand *cand, struct iv_ca_delta **delta, 4879169689Skan unsigned *n_ivs) 4880169689Skan{ 4881169689Skan unsigned i, cost; 4882169689Skan struct iv_use *use; 4883169689Skan struct cost_pair *old_cp, *new_cp; 4884169689Skan 4885169689Skan *delta = NULL; 4886169689Skan for (i = 0; i < ivs->upto; i++) 4887169689Skan { 4888169689Skan use = iv_use (data, i); 4889169689Skan old_cp = iv_ca_cand_for_use (ivs, use); 4890169689Skan 4891169689Skan if (old_cp 4892169689Skan && old_cp->cand == cand) 4893169689Skan continue; 4894169689Skan 4895169689Skan new_cp = get_use_iv_cost (data, use, cand); 4896169689Skan if (!new_cp) 4897169689Skan continue; 4898169689Skan 4899169689Skan if (!iv_ca_has_deps (ivs, new_cp)) 4900169689Skan continue; 4901169689Skan 4902169689Skan if (!cheaper_cost_pair (new_cp, old_cp)) 4903169689Skan continue; 4904169689Skan 4905169689Skan *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta); 4906169689Skan } 4907169689Skan 4908169689Skan iv_ca_delta_commit (data, ivs, *delta, true); 4909169689Skan cost = iv_ca_cost (ivs); 4910169689Skan if (n_ivs) 4911169689Skan *n_ivs = iv_ca_n_cands (ivs); 4912169689Skan iv_ca_delta_commit (data, ivs, *delta, false); 4913169689Skan 4914169689Skan return cost; 4915169689Skan} 4916169689Skan 4917169689Skan/* Try narrowing set IVS by removing CAND. Return the cost of 4918169689Skan the new set and store the differences in DELTA. */ 4919169689Skan 4920169689Skanstatic unsigned 4921169689Skaniv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs, 4922169689Skan struct iv_cand *cand, struct iv_ca_delta **delta) 4923169689Skan{ 4924169689Skan unsigned i, ci; 4925169689Skan struct iv_use *use; 4926169689Skan struct cost_pair *old_cp, *new_cp, *cp; 4927169689Skan bitmap_iterator bi; 4928169689Skan struct iv_cand *cnd; 4929169689Skan unsigned cost; 4930169689Skan 4931169689Skan *delta = NULL; 4932169689Skan for (i = 0; i < n_iv_uses (data); i++) 4933169689Skan { 4934169689Skan use = iv_use (data, i); 4935169689Skan 4936169689Skan old_cp = iv_ca_cand_for_use (ivs, use); 4937169689Skan if (old_cp->cand != cand) 4938169689Skan continue; 4939169689Skan 4940169689Skan new_cp = NULL; 4941169689Skan 4942169689Skan if (data->consider_all_candidates) 4943169689Skan { 4944169689Skan EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, ci, bi) 4945169689Skan { 4946169689Skan if (ci == cand->id) 4947169689Skan continue; 4948169689Skan 4949169689Skan cnd = iv_cand (data, ci); 4950169689Skan 4951169689Skan cp = get_use_iv_cost (data, use, cnd); 4952169689Skan if (!cp) 4953169689Skan continue; 4954169689Skan if (!iv_ca_has_deps (ivs, cp)) 4955169689Skan continue; 4956169689Skan 4957169689Skan if (!cheaper_cost_pair (cp, new_cp)) 4958169689Skan continue; 4959169689Skan 4960169689Skan new_cp = cp; 4961169689Skan } 4962169689Skan } 4963169689Skan else 4964169689Skan { 4965169689Skan EXECUTE_IF_AND_IN_BITMAP (use->related_cands, ivs->cands, 0, ci, bi) 4966169689Skan { 4967169689Skan if (ci == cand->id) 4968169689Skan continue; 4969169689Skan 4970169689Skan cnd = iv_cand (data, ci); 4971169689Skan 4972169689Skan cp = get_use_iv_cost (data, use, cnd); 4973169689Skan if (!cp) 4974169689Skan continue; 4975169689Skan if (!iv_ca_has_deps (ivs, cp)) 4976169689Skan continue; 4977169689Skan 4978169689Skan if (!cheaper_cost_pair (cp, new_cp)) 4979169689Skan continue; 4980169689Skan 4981169689Skan new_cp = cp; 4982169689Skan } 4983169689Skan } 4984169689Skan 4985169689Skan if (!new_cp) 4986169689Skan { 4987169689Skan iv_ca_delta_free (delta); 4988169689Skan return INFTY; 4989169689Skan } 4990169689Skan 4991169689Skan *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta); 4992169689Skan } 4993169689Skan 4994169689Skan iv_ca_delta_commit (data, ivs, *delta, true); 4995169689Skan cost = iv_ca_cost (ivs); 4996169689Skan iv_ca_delta_commit (data, ivs, *delta, false); 4997169689Skan 4998169689Skan return cost; 4999169689Skan} 5000169689Skan 5001169689Skan/* Try optimizing the set of candidates IVS by removing candidates different 5002169689Skan from to EXCEPT_CAND from it. Return cost of the new set, and store 5003169689Skan differences in DELTA. */ 5004169689Skan 5005169689Skanstatic unsigned 5006169689Skaniv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs, 5007169689Skan struct iv_cand *except_cand, struct iv_ca_delta **delta) 5008169689Skan{ 5009169689Skan bitmap_iterator bi; 5010169689Skan struct iv_ca_delta *act_delta, *best_delta; 5011169689Skan unsigned i, best_cost, acost; 5012169689Skan struct iv_cand *cand; 5013169689Skan 5014169689Skan best_delta = NULL; 5015169689Skan best_cost = iv_ca_cost (ivs); 5016169689Skan 5017169689Skan EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, i, bi) 5018169689Skan { 5019169689Skan cand = iv_cand (data, i); 5020169689Skan 5021169689Skan if (cand == except_cand) 5022169689Skan continue; 5023169689Skan 5024169689Skan acost = iv_ca_narrow (data, ivs, cand, &act_delta); 5025169689Skan 5026169689Skan if (acost < best_cost) 5027169689Skan { 5028169689Skan best_cost = acost; 5029169689Skan iv_ca_delta_free (&best_delta); 5030169689Skan best_delta = act_delta; 5031169689Skan } 5032169689Skan else 5033169689Skan iv_ca_delta_free (&act_delta); 5034169689Skan } 5035169689Skan 5036169689Skan if (!best_delta) 5037169689Skan { 5038169689Skan *delta = NULL; 5039169689Skan return best_cost; 5040169689Skan } 5041169689Skan 5042169689Skan /* Recurse to possibly remove other unnecessary ivs. */ 5043169689Skan iv_ca_delta_commit (data, ivs, best_delta, true); 5044169689Skan best_cost = iv_ca_prune (data, ivs, except_cand, delta); 5045169689Skan iv_ca_delta_commit (data, ivs, best_delta, false); 5046169689Skan *delta = iv_ca_delta_join (best_delta, *delta); 5047169689Skan return best_cost; 5048169689Skan} 5049169689Skan 5050169689Skan/* Tries to extend the sets IVS in the best possible way in order 5051169689Skan to express the USE. */ 5052169689Skan 5053169689Skanstatic bool 5054169689Skantry_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs, 5055169689Skan struct iv_use *use) 5056169689Skan{ 5057169689Skan unsigned best_cost, act_cost; 5058169689Skan unsigned i; 5059169689Skan bitmap_iterator bi; 5060169689Skan struct iv_cand *cand; 5061169689Skan struct iv_ca_delta *best_delta = NULL, *act_delta; 5062169689Skan struct cost_pair *cp; 5063169689Skan 5064169689Skan iv_ca_add_use (data, ivs, use); 5065169689Skan best_cost = iv_ca_cost (ivs); 5066169689Skan 5067169689Skan cp = iv_ca_cand_for_use (ivs, use); 5068169689Skan if (cp) 5069169689Skan { 5070169689Skan best_delta = iv_ca_delta_add (use, NULL, cp, NULL); 5071169689Skan iv_ca_set_no_cp (data, ivs, use); 5072169689Skan } 5073169689Skan 5074169689Skan /* First try important candidates. Only if it fails, try the specific ones. 5075169689Skan Rationale -- in loops with many variables the best choice often is to use 5076169689Skan just one generic biv. If we added here many ivs specific to the uses, 5077169689Skan the optimization algorithm later would be likely to get stuck in a local 5078169689Skan minimum, thus causing us to create too many ivs. The approach from 5079169689Skan few ivs to more seems more likely to be successful -- starting from few 5080169689Skan ivs, replacing an expensive use by a specific iv should always be a 5081169689Skan win. */ 5082169689Skan EXECUTE_IF_SET_IN_BITMAP (data->important_candidates, 0, i, bi) 5083169689Skan { 5084169689Skan cand = iv_cand (data, i); 5085169689Skan 5086169689Skan if (iv_ca_cand_used_p (ivs, cand)) 5087169689Skan continue; 5088169689Skan 5089169689Skan cp = get_use_iv_cost (data, use, cand); 5090169689Skan if (!cp) 5091169689Skan continue; 5092169689Skan 5093169689Skan iv_ca_set_cp (data, ivs, use, cp); 5094169689Skan act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL); 5095169689Skan iv_ca_set_no_cp (data, ivs, use); 5096169689Skan act_delta = iv_ca_delta_add (use, NULL, cp, act_delta); 5097169689Skan 5098169689Skan if (act_cost < best_cost) 5099169689Skan { 5100169689Skan best_cost = act_cost; 5101169689Skan 5102169689Skan iv_ca_delta_free (&best_delta); 5103169689Skan best_delta = act_delta; 5104169689Skan } 5105169689Skan else 5106169689Skan iv_ca_delta_free (&act_delta); 5107169689Skan } 5108169689Skan 5109169689Skan if (best_cost == INFTY) 5110169689Skan { 5111169689Skan for (i = 0; i < use->n_map_members; i++) 5112169689Skan { 5113169689Skan cp = use->cost_map + i; 5114169689Skan cand = cp->cand; 5115169689Skan if (!cand) 5116169689Skan continue; 5117169689Skan 5118169689Skan /* Already tried this. */ 5119169689Skan if (cand->important) 5120169689Skan continue; 5121169689Skan 5122169689Skan if (iv_ca_cand_used_p (ivs, cand)) 5123169689Skan continue; 5124169689Skan 5125169689Skan act_delta = NULL; 5126169689Skan iv_ca_set_cp (data, ivs, use, cp); 5127169689Skan act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL); 5128169689Skan iv_ca_set_no_cp (data, ivs, use); 5129169689Skan act_delta = iv_ca_delta_add (use, iv_ca_cand_for_use (ivs, use), 5130169689Skan cp, act_delta); 5131169689Skan 5132169689Skan if (act_cost < best_cost) 5133169689Skan { 5134169689Skan best_cost = act_cost; 5135169689Skan 5136169689Skan if (best_delta) 5137169689Skan iv_ca_delta_free (&best_delta); 5138169689Skan best_delta = act_delta; 5139169689Skan } 5140169689Skan else 5141169689Skan iv_ca_delta_free (&act_delta); 5142169689Skan } 5143169689Skan } 5144169689Skan 5145169689Skan iv_ca_delta_commit (data, ivs, best_delta, true); 5146169689Skan iv_ca_delta_free (&best_delta); 5147169689Skan 5148169689Skan return (best_cost != INFTY); 5149169689Skan} 5150169689Skan 5151169689Skan/* Finds an initial assignment of candidates to uses. */ 5152169689Skan 5153169689Skanstatic struct iv_ca * 5154169689Skanget_initial_solution (struct ivopts_data *data) 5155169689Skan{ 5156169689Skan struct iv_ca *ivs = iv_ca_new (data); 5157169689Skan unsigned i; 5158169689Skan 5159169689Skan for (i = 0; i < n_iv_uses (data); i++) 5160169689Skan if (!try_add_cand_for (data, ivs, iv_use (data, i))) 5161169689Skan { 5162169689Skan iv_ca_free (&ivs); 5163169689Skan return NULL; 5164169689Skan } 5165169689Skan 5166169689Skan return ivs; 5167169689Skan} 5168169689Skan 5169169689Skan/* Tries to improve set of induction variables IVS. */ 5170169689Skan 5171169689Skanstatic bool 5172169689Skantry_improve_iv_set (struct ivopts_data *data, struct iv_ca *ivs) 5173169689Skan{ 5174169689Skan unsigned i, acost, best_cost = iv_ca_cost (ivs), n_ivs; 5175169689Skan struct iv_ca_delta *best_delta = NULL, *act_delta, *tmp_delta; 5176169689Skan struct iv_cand *cand; 5177169689Skan 5178169689Skan /* Try extending the set of induction variables by one. */ 5179169689Skan for (i = 0; i < n_iv_cands (data); i++) 5180169689Skan { 5181169689Skan cand = iv_cand (data, i); 5182169689Skan 5183169689Skan if (iv_ca_cand_used_p (ivs, cand)) 5184169689Skan continue; 5185169689Skan 5186169689Skan acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs); 5187169689Skan if (!act_delta) 5188169689Skan continue; 5189169689Skan 5190169689Skan /* If we successfully added the candidate and the set is small enough, 5191169689Skan try optimizing it by removing other candidates. */ 5192169689Skan if (n_ivs <= ALWAYS_PRUNE_CAND_SET_BOUND) 5193169689Skan { 5194169689Skan iv_ca_delta_commit (data, ivs, act_delta, true); 5195169689Skan acost = iv_ca_prune (data, ivs, cand, &tmp_delta); 5196169689Skan iv_ca_delta_commit (data, ivs, act_delta, false); 5197169689Skan act_delta = iv_ca_delta_join (act_delta, tmp_delta); 5198169689Skan } 5199169689Skan 5200169689Skan if (acost < best_cost) 5201169689Skan { 5202169689Skan best_cost = acost; 5203169689Skan iv_ca_delta_free (&best_delta); 5204169689Skan best_delta = act_delta; 5205169689Skan } 5206169689Skan else 5207169689Skan iv_ca_delta_free (&act_delta); 5208169689Skan } 5209169689Skan 5210169689Skan if (!best_delta) 5211169689Skan { 5212169689Skan /* Try removing the candidates from the set instead. */ 5213169689Skan best_cost = iv_ca_prune (data, ivs, NULL, &best_delta); 5214169689Skan 5215169689Skan /* Nothing more we can do. */ 5216169689Skan if (!best_delta) 5217169689Skan return false; 5218169689Skan } 5219169689Skan 5220169689Skan iv_ca_delta_commit (data, ivs, best_delta, true); 5221169689Skan gcc_assert (best_cost == iv_ca_cost (ivs)); 5222169689Skan iv_ca_delta_free (&best_delta); 5223169689Skan return true; 5224169689Skan} 5225169689Skan 5226169689Skan/* Attempts to find the optimal set of induction variables. We do simple 5227169689Skan greedy heuristic -- we try to replace at most one candidate in the selected 5228169689Skan solution and remove the unused ivs while this improves the cost. */ 5229169689Skan 5230169689Skanstatic struct iv_ca * 5231169689Skanfind_optimal_iv_set (struct ivopts_data *data) 5232169689Skan{ 5233169689Skan unsigned i; 5234169689Skan struct iv_ca *set; 5235169689Skan struct iv_use *use; 5236169689Skan 5237169689Skan /* Get the initial solution. */ 5238169689Skan set = get_initial_solution (data); 5239169689Skan if (!set) 5240169689Skan { 5241169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 5242169689Skan fprintf (dump_file, "Unable to substitute for ivs, failed.\n"); 5243169689Skan return NULL; 5244169689Skan } 5245169689Skan 5246169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 5247169689Skan { 5248169689Skan fprintf (dump_file, "Initial set of candidates:\n"); 5249169689Skan iv_ca_dump (data, dump_file, set); 5250169689Skan } 5251169689Skan 5252169689Skan while (try_improve_iv_set (data, set)) 5253169689Skan { 5254169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 5255169689Skan { 5256169689Skan fprintf (dump_file, "Improved to:\n"); 5257169689Skan iv_ca_dump (data, dump_file, set); 5258169689Skan } 5259169689Skan } 5260169689Skan 5261169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 5262169689Skan fprintf (dump_file, "Final cost %d\n\n", iv_ca_cost (set)); 5263169689Skan 5264169689Skan for (i = 0; i < n_iv_uses (data); i++) 5265169689Skan { 5266169689Skan use = iv_use (data, i); 5267169689Skan use->selected = iv_ca_cand_for_use (set, use)->cand; 5268169689Skan } 5269169689Skan 5270169689Skan return set; 5271169689Skan} 5272169689Skan 5273169689Skan/* Creates a new induction variable corresponding to CAND. */ 5274169689Skan 5275169689Skanstatic void 5276169689Skancreate_new_iv (struct ivopts_data *data, struct iv_cand *cand) 5277169689Skan{ 5278169689Skan block_stmt_iterator incr_pos; 5279169689Skan tree base; 5280169689Skan bool after = false; 5281169689Skan 5282169689Skan if (!cand->iv) 5283169689Skan return; 5284169689Skan 5285169689Skan switch (cand->pos) 5286169689Skan { 5287169689Skan case IP_NORMAL: 5288169689Skan incr_pos = bsi_last (ip_normal_pos (data->current_loop)); 5289169689Skan break; 5290169689Skan 5291169689Skan case IP_END: 5292169689Skan incr_pos = bsi_last (ip_end_pos (data->current_loop)); 5293169689Skan after = true; 5294169689Skan break; 5295169689Skan 5296169689Skan case IP_ORIGINAL: 5297169689Skan /* Mark that the iv is preserved. */ 5298169689Skan name_info (data, cand->var_before)->preserve_biv = true; 5299169689Skan name_info (data, cand->var_after)->preserve_biv = true; 5300169689Skan 5301169689Skan /* Rewrite the increment so that it uses var_before directly. */ 5302169689Skan find_interesting_uses_op (data, cand->var_after)->selected = cand; 5303169689Skan 5304169689Skan return; 5305169689Skan } 5306169689Skan 5307169689Skan gimple_add_tmp_var (cand->var_before); 5308169689Skan add_referenced_var (cand->var_before); 5309169689Skan 5310169689Skan base = unshare_expr (cand->iv->base); 5311169689Skan 5312169689Skan create_iv (base, unshare_expr (cand->iv->step), 5313169689Skan cand->var_before, data->current_loop, 5314169689Skan &incr_pos, after, &cand->var_before, &cand->var_after); 5315169689Skan} 5316169689Skan 5317169689Skan/* Creates new induction variables described in SET. */ 5318169689Skan 5319169689Skanstatic void 5320169689Skancreate_new_ivs (struct ivopts_data *data, struct iv_ca *set) 5321169689Skan{ 5322169689Skan unsigned i; 5323169689Skan struct iv_cand *cand; 5324169689Skan bitmap_iterator bi; 5325169689Skan 5326169689Skan EXECUTE_IF_SET_IN_BITMAP (set->cands, 0, i, bi) 5327169689Skan { 5328169689Skan cand = iv_cand (data, i); 5329169689Skan create_new_iv (data, cand); 5330169689Skan } 5331169689Skan} 5332169689Skan 5333169689Skan/* Removes statement STMT (real or a phi node). If INCLUDING_DEFINED_NAME 5334169689Skan is true, remove also the ssa name defined by the statement. */ 5335169689Skan 5336169689Skanstatic void 5337169689Skanremove_statement (tree stmt, bool including_defined_name) 5338169689Skan{ 5339169689Skan if (TREE_CODE (stmt) == PHI_NODE) 5340169689Skan { 5341169689Skan if (!including_defined_name) 5342169689Skan { 5343169689Skan /* Prevent the ssa name defined by the statement from being removed. */ 5344169689Skan SET_PHI_RESULT (stmt, NULL); 5345169689Skan } 5346169689Skan remove_phi_node (stmt, NULL_TREE); 5347169689Skan } 5348169689Skan else 5349169689Skan { 5350169689Skan block_stmt_iterator bsi = bsi_for_stmt (stmt); 5351169689Skan 5352169689Skan bsi_remove (&bsi, true); 5353169689Skan } 5354169689Skan} 5355169689Skan 5356169689Skan/* Rewrites USE (definition of iv used in a nonlinear expression) 5357169689Skan using candidate CAND. */ 5358169689Skan 5359169689Skanstatic void 5360169689Skanrewrite_use_nonlinear_expr (struct ivopts_data *data, 5361169689Skan struct iv_use *use, struct iv_cand *cand) 5362169689Skan{ 5363169689Skan tree comp; 5364169689Skan tree op, stmts, tgt, ass; 5365169689Skan block_stmt_iterator bsi, pbsi; 5366169689Skan 5367169689Skan /* An important special case -- if we are asked to express value of 5368169689Skan the original iv by itself, just exit; there is no need to 5369169689Skan introduce a new computation (that might also need casting the 5370169689Skan variable to unsigned and back). */ 5371169689Skan if (cand->pos == IP_ORIGINAL 5372169689Skan && cand->incremented_at == use->stmt) 5373169689Skan { 5374169689Skan tree step, ctype, utype; 5375169689Skan enum tree_code incr_code = PLUS_EXPR; 5376169689Skan 5377169689Skan gcc_assert (TREE_CODE (use->stmt) == MODIFY_EXPR); 5378169689Skan gcc_assert (TREE_OPERAND (use->stmt, 0) == cand->var_after); 5379169689Skan 5380169689Skan step = cand->iv->step; 5381169689Skan ctype = TREE_TYPE (step); 5382169689Skan utype = TREE_TYPE (cand->var_after); 5383169689Skan if (TREE_CODE (step) == NEGATE_EXPR) 5384169689Skan { 5385169689Skan incr_code = MINUS_EXPR; 5386169689Skan step = TREE_OPERAND (step, 0); 5387169689Skan } 5388169689Skan 5389169689Skan /* Check whether we may leave the computation unchanged. 5390169689Skan This is the case only if it does not rely on other 5391169689Skan computations in the loop -- otherwise, the computation 5392169689Skan we rely upon may be removed in remove_unused_ivs, 5393169689Skan thus leading to ICE. */ 5394169689Skan op = TREE_OPERAND (use->stmt, 1); 5395169689Skan if (TREE_CODE (op) == PLUS_EXPR 5396169689Skan || TREE_CODE (op) == MINUS_EXPR) 5397169689Skan { 5398169689Skan if (TREE_OPERAND (op, 0) == cand->var_before) 5399169689Skan op = TREE_OPERAND (op, 1); 5400169689Skan else if (TREE_CODE (op) == PLUS_EXPR 5401169689Skan && TREE_OPERAND (op, 1) == cand->var_before) 5402169689Skan op = TREE_OPERAND (op, 0); 5403169689Skan else 5404169689Skan op = NULL_TREE; 5405169689Skan } 5406169689Skan else 5407169689Skan op = NULL_TREE; 5408169689Skan 5409169689Skan if (op 5410169689Skan && (TREE_CODE (op) == INTEGER_CST 5411169689Skan || operand_equal_p (op, step, 0))) 5412169689Skan return; 5413169689Skan 5414169689Skan /* Otherwise, add the necessary computations to express 5415169689Skan the iv. */ 5416169689Skan op = fold_convert (ctype, cand->var_before); 5417169689Skan comp = fold_convert (utype, 5418169689Skan build2 (incr_code, ctype, op, 5419169689Skan unshare_expr (step))); 5420169689Skan } 5421169689Skan else 5422169689Skan comp = get_computation (data->current_loop, use, cand); 5423169689Skan 5424169689Skan switch (TREE_CODE (use->stmt)) 5425169689Skan { 5426169689Skan case PHI_NODE: 5427169689Skan tgt = PHI_RESULT (use->stmt); 5428169689Skan 5429169689Skan /* If we should keep the biv, do not replace it. */ 5430169689Skan if (name_info (data, tgt)->preserve_biv) 5431169689Skan return; 5432169689Skan 5433169689Skan pbsi = bsi = bsi_start (bb_for_stmt (use->stmt)); 5434169689Skan while (!bsi_end_p (pbsi) 5435169689Skan && TREE_CODE (bsi_stmt (pbsi)) == LABEL_EXPR) 5436169689Skan { 5437169689Skan bsi = pbsi; 5438169689Skan bsi_next (&pbsi); 5439169689Skan } 5440169689Skan break; 5441169689Skan 5442169689Skan case MODIFY_EXPR: 5443169689Skan tgt = TREE_OPERAND (use->stmt, 0); 5444169689Skan bsi = bsi_for_stmt (use->stmt); 5445169689Skan break; 5446169689Skan 5447169689Skan default: 5448169689Skan gcc_unreachable (); 5449169689Skan } 5450169689Skan 5451169689Skan op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt)); 5452169689Skan 5453169689Skan if (TREE_CODE (use->stmt) == PHI_NODE) 5454169689Skan { 5455169689Skan if (stmts) 5456169689Skan bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING); 5457169689Skan ass = build2 (MODIFY_EXPR, TREE_TYPE (tgt), tgt, op); 5458169689Skan bsi_insert_after (&bsi, ass, BSI_NEW_STMT); 5459169689Skan remove_statement (use->stmt, false); 5460169689Skan SSA_NAME_DEF_STMT (tgt) = ass; 5461169689Skan } 5462169689Skan else 5463169689Skan { 5464169689Skan if (stmts) 5465169689Skan bsi_insert_before (&bsi, stmts, BSI_SAME_STMT); 5466169689Skan TREE_OPERAND (use->stmt, 1) = op; 5467169689Skan } 5468169689Skan} 5469169689Skan 5470169689Skan/* Replaces ssa name in index IDX by its basic variable. Callback for 5471169689Skan for_each_index. */ 5472169689Skan 5473169689Skanstatic bool 5474169689Skanidx_remove_ssa_names (tree base, tree *idx, 5475169689Skan void *data ATTRIBUTE_UNUSED) 5476169689Skan{ 5477169689Skan tree *op; 5478169689Skan 5479169689Skan if (TREE_CODE (*idx) == SSA_NAME) 5480169689Skan *idx = SSA_NAME_VAR (*idx); 5481169689Skan 5482169689Skan if (TREE_CODE (base) == ARRAY_REF) 5483169689Skan { 5484169689Skan op = &TREE_OPERAND (base, 2); 5485169689Skan if (*op 5486169689Skan && TREE_CODE (*op) == SSA_NAME) 5487169689Skan *op = SSA_NAME_VAR (*op); 5488169689Skan op = &TREE_OPERAND (base, 3); 5489169689Skan if (*op 5490169689Skan && TREE_CODE (*op) == SSA_NAME) 5491169689Skan *op = SSA_NAME_VAR (*op); 5492169689Skan } 5493169689Skan 5494169689Skan return true; 5495169689Skan} 5496169689Skan 5497169689Skan/* Unshares REF and replaces ssa names inside it by their basic variables. */ 5498169689Skan 5499169689Skanstatic tree 5500169689Skanunshare_and_remove_ssa_names (tree ref) 5501169689Skan{ 5502169689Skan ref = unshare_expr (ref); 5503169689Skan for_each_index (&ref, idx_remove_ssa_names, NULL); 5504169689Skan 5505169689Skan return ref; 5506169689Skan} 5507169689Skan 5508169689Skan/* Extract the alias analysis info for the memory reference REF. There are 5509169689Skan several ways how this information may be stored and what precisely is 5510169689Skan its semantics depending on the type of the reference, but there always is 5511169689Skan somewhere hidden one _DECL node that is used to determine the set of 5512169689Skan virtual operands for the reference. The code below deciphers this jungle 5513169689Skan and extracts this single useful piece of information. */ 5514169689Skan 5515169689Skanstatic tree 5516169689Skanget_ref_tag (tree ref, tree orig) 5517169689Skan{ 5518169689Skan tree var = get_base_address (ref); 5519169689Skan tree aref = NULL_TREE, tag, sv; 5520169689Skan HOST_WIDE_INT offset, size, maxsize; 5521169689Skan 5522169689Skan for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0)) 5523169689Skan { 5524169689Skan aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize); 5525169689Skan if (ref) 5526169689Skan break; 5527169689Skan } 5528169689Skan 5529169689Skan if (aref && SSA_VAR_P (aref) && get_subvars_for_var (aref)) 5530169689Skan return unshare_expr (sv); 5531169689Skan 5532169689Skan if (!var) 5533169689Skan return NULL_TREE; 5534169689Skan 5535169689Skan if (TREE_CODE (var) == INDIRECT_REF) 5536169689Skan { 5537169689Skan /* If the base is a dereference of a pointer, first check its name memory 5538169689Skan tag. If it does not have one, use its symbol memory tag. */ 5539169689Skan var = TREE_OPERAND (var, 0); 5540169689Skan if (TREE_CODE (var) != SSA_NAME) 5541169689Skan return NULL_TREE; 5542169689Skan 5543169689Skan if (SSA_NAME_PTR_INFO (var)) 5544169689Skan { 5545169689Skan tag = SSA_NAME_PTR_INFO (var)->name_mem_tag; 5546169689Skan if (tag) 5547169689Skan return tag; 5548169689Skan } 5549169689Skan 5550169689Skan var = SSA_NAME_VAR (var); 5551169689Skan tag = var_ann (var)->symbol_mem_tag; 5552169689Skan gcc_assert (tag != NULL_TREE); 5553169689Skan return tag; 5554169689Skan } 5555169689Skan else 5556169689Skan { 5557169689Skan if (!DECL_P (var)) 5558169689Skan return NULL_TREE; 5559169689Skan 5560169689Skan tag = var_ann (var)->symbol_mem_tag; 5561169689Skan if (tag) 5562169689Skan return tag; 5563169689Skan 5564169689Skan return var; 5565169689Skan } 5566169689Skan} 5567169689Skan 5568169689Skan/* Copies the reference information from OLD_REF to NEW_REF. */ 5569169689Skan 5570169689Skanstatic void 5571169689Skancopy_ref_info (tree new_ref, tree old_ref) 5572169689Skan{ 5573169689Skan if (TREE_CODE (old_ref) == TARGET_MEM_REF) 5574169689Skan copy_mem_ref_info (new_ref, old_ref); 5575169689Skan else 5576169689Skan { 5577169689Skan TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref); 5578169689Skan TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref)); 5579169689Skan } 5580169689Skan} 5581169689Skan 5582169689Skan/* Rewrites USE (address that is an iv) using candidate CAND. */ 5583169689Skan 5584169689Skanstatic void 5585169689Skanrewrite_use_address (struct ivopts_data *data, 5586169689Skan struct iv_use *use, struct iv_cand *cand) 5587169689Skan{ 5588169689Skan struct affine_tree_combination aff; 5589169689Skan block_stmt_iterator bsi = bsi_for_stmt (use->stmt); 5590169689Skan tree ref; 5591169689Skan 5592169689Skan get_computation_aff (data->current_loop, use, cand, use->stmt, &aff); 5593169689Skan unshare_aff_combination (&aff); 5594169689Skan 5595169689Skan ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff); 5596169689Skan copy_ref_info (ref, *use->op_p); 5597169689Skan *use->op_p = ref; 5598169689Skan} 5599169689Skan 5600169689Skan/* Rewrites USE (the condition such that one of the arguments is an iv) using 5601169689Skan candidate CAND. */ 5602169689Skan 5603169689Skanstatic void 5604169689Skanrewrite_use_compare (struct ivopts_data *data, 5605169689Skan struct iv_use *use, struct iv_cand *cand) 5606169689Skan{ 5607169689Skan tree comp; 5608169689Skan tree *op_p, cond, op, stmts, bound; 5609169689Skan block_stmt_iterator bsi = bsi_for_stmt (use->stmt); 5610169689Skan enum tree_code compare; 5611169689Skan struct cost_pair *cp = get_use_iv_cost (data, use, cand); 5612169689Skan 5613169689Skan bound = cp->value; 5614169689Skan if (bound) 5615169689Skan { 5616169689Skan tree var = var_at_stmt (data->current_loop, cand, use->stmt); 5617169689Skan tree var_type = TREE_TYPE (var); 5618169689Skan 5619169689Skan compare = iv_elimination_compare (data, use); 5620169689Skan bound = fold_convert (var_type, bound); 5621169689Skan op = force_gimple_operand (unshare_expr (bound), &stmts, 5622169689Skan true, NULL_TREE); 5623169689Skan 5624169689Skan if (stmts) 5625169689Skan bsi_insert_before (&bsi, stmts, BSI_SAME_STMT); 5626169689Skan 5627169689Skan *use->op_p = build2 (compare, boolean_type_node, var, op); 5628169689Skan update_stmt (use->stmt); 5629169689Skan return; 5630169689Skan } 5631169689Skan 5632169689Skan /* The induction variable elimination failed; just express the original 5633169689Skan giv. */ 5634169689Skan comp = get_computation (data->current_loop, use, cand); 5635169689Skan 5636169689Skan cond = *use->op_p; 5637169689Skan op_p = &TREE_OPERAND (cond, 0); 5638169689Skan if (TREE_CODE (*op_p) != SSA_NAME 5639169689Skan || zero_p (get_iv (data, *op_p)->step)) 5640169689Skan op_p = &TREE_OPERAND (cond, 1); 5641169689Skan 5642169689Skan op = force_gimple_operand (comp, &stmts, true, SSA_NAME_VAR (*op_p)); 5643169689Skan if (stmts) 5644169689Skan bsi_insert_before (&bsi, stmts, BSI_SAME_STMT); 5645169689Skan 5646169689Skan *op_p = op; 5647169689Skan} 5648169689Skan 5649169689Skan/* Rewrites USE using candidate CAND. */ 5650169689Skan 5651169689Skanstatic void 5652169689Skanrewrite_use (struct ivopts_data *data, 5653169689Skan struct iv_use *use, struct iv_cand *cand) 5654169689Skan{ 5655169689Skan switch (use->type) 5656169689Skan { 5657169689Skan case USE_NONLINEAR_EXPR: 5658169689Skan rewrite_use_nonlinear_expr (data, use, cand); 5659169689Skan break; 5660169689Skan 5661169689Skan case USE_ADDRESS: 5662169689Skan rewrite_use_address (data, use, cand); 5663169689Skan break; 5664169689Skan 5665169689Skan case USE_COMPARE: 5666169689Skan rewrite_use_compare (data, use, cand); 5667169689Skan break; 5668169689Skan 5669169689Skan default: 5670169689Skan gcc_unreachable (); 5671169689Skan } 5672169689Skan mark_new_vars_to_rename (use->stmt); 5673169689Skan} 5674169689Skan 5675169689Skan/* Rewrite the uses using the selected induction variables. */ 5676169689Skan 5677169689Skanstatic void 5678169689Skanrewrite_uses (struct ivopts_data *data) 5679169689Skan{ 5680169689Skan unsigned i; 5681169689Skan struct iv_cand *cand; 5682169689Skan struct iv_use *use; 5683169689Skan 5684169689Skan for (i = 0; i < n_iv_uses (data); i++) 5685169689Skan { 5686169689Skan use = iv_use (data, i); 5687169689Skan cand = use->selected; 5688169689Skan gcc_assert (cand); 5689169689Skan 5690169689Skan rewrite_use (data, use, cand); 5691169689Skan } 5692169689Skan} 5693169689Skan 5694169689Skan/* Removes the ivs that are not used after rewriting. */ 5695169689Skan 5696169689Skanstatic void 5697169689Skanremove_unused_ivs (struct ivopts_data *data) 5698169689Skan{ 5699169689Skan unsigned j; 5700169689Skan bitmap_iterator bi; 5701169689Skan 5702169689Skan EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi) 5703169689Skan { 5704169689Skan struct version_info *info; 5705169689Skan 5706169689Skan info = ver_info (data, j); 5707169689Skan if (info->iv 5708169689Skan && !zero_p (info->iv->step) 5709169689Skan && !info->inv_id 5710169689Skan && !info->iv->have_use_for 5711169689Skan && !info->preserve_biv) 5712169689Skan remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true); 5713169689Skan } 5714169689Skan} 5715169689Skan 5716169689Skan/* Frees data allocated by the optimization of a single loop. */ 5717169689Skan 5718169689Skanstatic void 5719169689Skanfree_loop_data (struct ivopts_data *data) 5720169689Skan{ 5721169689Skan unsigned i, j; 5722169689Skan bitmap_iterator bi; 5723169689Skan tree obj; 5724169689Skan 5725169689Skan htab_empty (data->niters); 5726169689Skan 5727169689Skan EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi) 5728169689Skan { 5729169689Skan struct version_info *info; 5730169689Skan 5731169689Skan info = ver_info (data, i); 5732169689Skan if (info->iv) 5733169689Skan free (info->iv); 5734169689Skan info->iv = NULL; 5735169689Skan info->has_nonlin_use = false; 5736169689Skan info->preserve_biv = false; 5737169689Skan info->inv_id = 0; 5738169689Skan } 5739169689Skan bitmap_clear (data->relevant); 5740169689Skan bitmap_clear (data->important_candidates); 5741169689Skan 5742169689Skan for (i = 0; i < n_iv_uses (data); i++) 5743169689Skan { 5744169689Skan struct iv_use *use = iv_use (data, i); 5745169689Skan 5746169689Skan free (use->iv); 5747169689Skan BITMAP_FREE (use->related_cands); 5748169689Skan for (j = 0; j < use->n_map_members; j++) 5749169689Skan if (use->cost_map[j].depends_on) 5750169689Skan BITMAP_FREE (use->cost_map[j].depends_on); 5751169689Skan free (use->cost_map); 5752169689Skan free (use); 5753169689Skan } 5754169689Skan VEC_truncate (iv_use_p, data->iv_uses, 0); 5755169689Skan 5756169689Skan for (i = 0; i < n_iv_cands (data); i++) 5757169689Skan { 5758169689Skan struct iv_cand *cand = iv_cand (data, i); 5759169689Skan 5760169689Skan if (cand->iv) 5761169689Skan free (cand->iv); 5762169689Skan if (cand->depends_on) 5763169689Skan BITMAP_FREE (cand->depends_on); 5764169689Skan free (cand); 5765169689Skan } 5766169689Skan VEC_truncate (iv_cand_p, data->iv_candidates, 0); 5767169689Skan 5768169689Skan if (data->version_info_size < num_ssa_names) 5769169689Skan { 5770169689Skan data->version_info_size = 2 * num_ssa_names; 5771169689Skan free (data->version_info); 5772169689Skan data->version_info = XCNEWVEC (struct version_info, data->version_info_size); 5773169689Skan } 5774169689Skan 5775169689Skan data->max_inv_id = 0; 5776169689Skan 5777169689Skan for (i = 0; VEC_iterate (tree, decl_rtl_to_reset, i, obj); i++) 5778169689Skan SET_DECL_RTL (obj, NULL_RTX); 5779169689Skan 5780169689Skan VEC_truncate (tree, decl_rtl_to_reset, 0); 5781169689Skan} 5782169689Skan 5783169689Skan/* Finalizes data structures used by the iv optimization pass. LOOPS is the 5784169689Skan loop tree. */ 5785169689Skan 5786169689Skanstatic void 5787169689Skantree_ssa_iv_optimize_finalize (struct ivopts_data *data) 5788169689Skan{ 5789169689Skan free_loop_data (data); 5790169689Skan free (data->version_info); 5791169689Skan BITMAP_FREE (data->relevant); 5792169689Skan BITMAP_FREE (data->important_candidates); 5793169689Skan htab_delete (data->niters); 5794169689Skan 5795169689Skan VEC_free (tree, heap, decl_rtl_to_reset); 5796169689Skan VEC_free (iv_use_p, heap, data->iv_uses); 5797169689Skan VEC_free (iv_cand_p, heap, data->iv_candidates); 5798169689Skan} 5799169689Skan 5800169689Skan/* Optimizes the LOOP. Returns true if anything changed. */ 5801169689Skan 5802169689Skanstatic bool 5803169689Skantree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop) 5804169689Skan{ 5805169689Skan bool changed = false; 5806169689Skan struct iv_ca *iv_ca; 5807169689Skan edge exit; 5808169689Skan 5809169689Skan data->current_loop = loop; 5810169689Skan 5811169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 5812169689Skan { 5813169689Skan fprintf (dump_file, "Processing loop %d\n", loop->num); 5814169689Skan 5815169689Skan exit = single_dom_exit (loop); 5816169689Skan if (exit) 5817169689Skan { 5818169689Skan fprintf (dump_file, " single exit %d -> %d, exit condition ", 5819169689Skan exit->src->index, exit->dest->index); 5820169689Skan print_generic_expr (dump_file, last_stmt (exit->src), TDF_SLIM); 5821169689Skan fprintf (dump_file, "\n"); 5822169689Skan } 5823169689Skan 5824169689Skan fprintf (dump_file, "\n"); 5825169689Skan } 5826169689Skan 5827169689Skan /* For each ssa name determines whether it behaves as an induction variable 5828169689Skan in some loop. */ 5829169689Skan if (!find_induction_variables (data)) 5830169689Skan goto finish; 5831169689Skan 5832169689Skan /* Finds interesting uses (item 1). */ 5833169689Skan find_interesting_uses (data); 5834169689Skan if (n_iv_uses (data) > MAX_CONSIDERED_USES) 5835169689Skan goto finish; 5836169689Skan 5837169689Skan /* Finds candidates for the induction variables (item 2). */ 5838169689Skan find_iv_candidates (data); 5839169689Skan 5840169689Skan /* Calculates the costs (item 3, part 1). */ 5841169689Skan determine_use_iv_costs (data); 5842169689Skan determine_iv_costs (data); 5843169689Skan determine_set_costs (data); 5844169689Skan 5845169689Skan /* Find the optimal set of induction variables (item 3, part 2). */ 5846169689Skan iv_ca = find_optimal_iv_set (data); 5847169689Skan if (!iv_ca) 5848169689Skan goto finish; 5849169689Skan changed = true; 5850169689Skan 5851169689Skan /* Create the new induction variables (item 4, part 1). */ 5852169689Skan create_new_ivs (data, iv_ca); 5853169689Skan iv_ca_free (&iv_ca); 5854169689Skan 5855169689Skan /* Rewrite the uses (item 4, part 2). */ 5856169689Skan rewrite_uses (data); 5857169689Skan 5858169689Skan /* Remove the ivs that are unused after rewriting. */ 5859169689Skan remove_unused_ivs (data); 5860169689Skan 5861169689Skan /* We have changed the structure of induction variables; it might happen 5862169689Skan that definitions in the scev database refer to some of them that were 5863169689Skan eliminated. */ 5864169689Skan scev_reset (); 5865169689Skan 5866169689Skanfinish: 5867169689Skan free_loop_data (data); 5868169689Skan 5869169689Skan return changed; 5870169689Skan} 5871169689Skan 5872169689Skan/* Main entry point. Optimizes induction variables in LOOPS. */ 5873169689Skan 5874169689Skanvoid 5875169689Skantree_ssa_iv_optimize (struct loops *loops) 5876169689Skan{ 5877169689Skan struct loop *loop; 5878169689Skan struct ivopts_data data; 5879169689Skan 5880169689Skan tree_ssa_iv_optimize_init (&data); 5881169689Skan 5882169689Skan /* Optimize the loops starting with the innermost ones. */ 5883169689Skan loop = loops->tree_root; 5884169689Skan while (loop->inner) 5885169689Skan loop = loop->inner; 5886169689Skan 5887169689Skan /* Scan the loops, inner ones first. */ 5888169689Skan while (loop != loops->tree_root) 5889169689Skan { 5890169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 5891169689Skan flow_loop_dump (loop, dump_file, NULL, 1); 5892169689Skan 5893169689Skan tree_ssa_iv_optimize_loop (&data, loop); 5894169689Skan 5895169689Skan if (loop->next) 5896169689Skan { 5897169689Skan loop = loop->next; 5898169689Skan while (loop->inner) 5899169689Skan loop = loop->inner; 5900169689Skan } 5901169689Skan else 5902169689Skan loop = loop->outer; 5903169689Skan } 5904169689Skan 5905169689Skan tree_ssa_iv_optimize_finalize (&data); 5906169689Skan} 5907