1169689Skan/* Reassociation for trees. 2169689Skan Copyright (C) 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Daniel Berlin <dan@dberlin.org> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanit under the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2, or (at your option) 10169689Skanany later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21169689Skan 22169689Skan#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26169689Skan#include "errors.h" 27169689Skan#include "ggc.h" 28169689Skan#include "tree.h" 29169689Skan#include "basic-block.h" 30169689Skan#include "diagnostic.h" 31169689Skan#include "tree-inline.h" 32169689Skan#include "tree-flow.h" 33169689Skan#include "tree-gimple.h" 34169689Skan#include "tree-dump.h" 35169689Skan#include "timevar.h" 36169689Skan#include "tree-iterator.h" 37169689Skan#include "tree-pass.h" 38169689Skan#include "alloc-pool.h" 39169689Skan#include "vec.h" 40169689Skan#include "langhooks.h" 41169689Skan 42169689Skan/* This is a simple global reassociation pass. It is, in part, based 43169689Skan on the LLVM pass of the same name (They do some things more/less 44169689Skan than we do, in different orders, etc). 45169689Skan 46169689Skan It consists of five steps: 47169689Skan 48169689Skan 1. Breaking up subtract operations into addition + negate, where 49169689Skan it would promote the reassociation of adds. 50169689Skan 51169689Skan 2. Left linearization of the expression trees, so that (A+B)+(C+D) 52169689Skan becomes (((A+B)+C)+D), which is easier for us to rewrite later. 53169689Skan During linearization, we place the operands of the binary 54169689Skan expressions into a vector of operand_entry_t 55169689Skan 56169689Skan 3. Optimization of the operand lists, eliminating things like a + 57169689Skan -a, a & a, etc. 58169689Skan 59169689Skan 4. Rewrite the expression trees we linearized and optimized so 60169689Skan they are in proper rank order. 61169689Skan 62169689Skan 5. Repropagate negates, as nothing else will clean it up ATM. 63169689Skan 64169689Skan A bit of theory on #4, since nobody seems to write anything down 65169689Skan about why it makes sense to do it the way they do it: 66169689Skan 67169689Skan We could do this much nicer theoretically, but don't (for reasons 68169689Skan explained after how to do it theoretically nice :P). 69169689Skan 70169689Skan In order to promote the most redundancy elimination, you want 71169689Skan binary expressions whose operands are the same rank (or 72169689Skan preferably, the same value) exposed to the redundancy eliminator, 73169689Skan for possible elimination. 74169689Skan 75169689Skan So the way to do this if we really cared, is to build the new op 76169689Skan tree from the leaves to the roots, merging as you go, and putting the 77169689Skan new op on the end of the worklist, until you are left with one 78169689Skan thing on the worklist. 79169689Skan 80169689Skan IE if you have to rewrite the following set of operands (listed with 81169689Skan rank in parentheses), with opcode PLUS_EXPR: 82169689Skan 83169689Skan a (1), b (1), c (1), d (2), e (2) 84169689Skan 85169689Skan 86169689Skan We start with our merge worklist empty, and the ops list with all of 87169689Skan those on it. 88169689Skan 89169689Skan You want to first merge all leaves of the same rank, as much as 90169689Skan possible. 91169689Skan 92169689Skan So first build a binary op of 93169689Skan 94169689Skan mergetmp = a + b, and put "mergetmp" on the merge worklist. 95169689Skan 96169689Skan Because there is no three operand form of PLUS_EXPR, c is not going to 97169689Skan be exposed to redundancy elimination as a rank 1 operand. 98169689Skan 99169689Skan So you might as well throw it on the merge worklist (you could also 100169689Skan consider it to now be a rank two operand, and merge it with d and e, 101169689Skan but in this case, you then have evicted e from a binary op. So at 102169689Skan least in this situation, you can't win.) 103169689Skan 104169689Skan Then build a binary op of d + e 105169689Skan mergetmp2 = d + e 106169689Skan 107169689Skan and put mergetmp2 on the merge worklist. 108169689Skan 109169689Skan so merge worklist = {mergetmp, c, mergetmp2} 110169689Skan 111169689Skan Continue building binary ops of these operations until you have only 112169689Skan one operation left on the worklist. 113169689Skan 114169689Skan So we have 115169689Skan 116169689Skan build binary op 117169689Skan mergetmp3 = mergetmp + c 118169689Skan 119169689Skan worklist = {mergetmp2, mergetmp3} 120169689Skan 121169689Skan mergetmp4 = mergetmp2 + mergetmp3 122169689Skan 123169689Skan worklist = {mergetmp4} 124169689Skan 125169689Skan because we have one operation left, we can now just set the original 126169689Skan statement equal to the result of that operation. 127169689Skan 128169689Skan This will at least expose a + b and d + e to redundancy elimination 129169689Skan as binary operations. 130169689Skan 131169689Skan For extra points, you can reuse the old statements to build the 132169689Skan mergetmps, since you shouldn't run out. 133169689Skan 134169689Skan So why don't we do this? 135169689Skan 136169689Skan Because it's expensive, and rarely will help. Most trees we are 137169689Skan reassociating have 3 or less ops. If they have 2 ops, they already 138169689Skan will be written into a nice single binary op. If you have 3 ops, a 139169689Skan single simple check suffices to tell you whether the first two are of the 140169689Skan same rank. If so, you know to order it 141169689Skan 142169689Skan mergetmp = op1 + op2 143169689Skan newstmt = mergetmp + op3 144169689Skan 145169689Skan instead of 146169689Skan mergetmp = op2 + op3 147169689Skan newstmt = mergetmp + op1 148169689Skan 149169689Skan If all three are of the same rank, you can't expose them all in a 150169689Skan single binary operator anyway, so the above is *still* the best you 151169689Skan can do. 152169689Skan 153169689Skan Thus, this is what we do. When we have three ops left, we check to see 154169689Skan what order to put them in, and call it a day. As a nod to vector sum 155169689Skan reduction, we check if any of ops are a really a phi node that is a 156169689Skan destructive update for the associating op, and keep the destructive 157169689Skan update together for vector sum reduction recognition. */ 158169689Skan 159169689Skan 160169689Skan/* Statistics */ 161169689Skanstatic struct 162169689Skan{ 163169689Skan int linearized; 164169689Skan int constants_eliminated; 165169689Skan int ops_eliminated; 166169689Skan int rewritten; 167169689Skan} reassociate_stats; 168169689Skan 169169689Skan/* Operator, rank pair. */ 170169689Skantypedef struct operand_entry 171169689Skan{ 172169689Skan unsigned int rank; 173169689Skan tree op; 174169689Skan} *operand_entry_t; 175169689Skan 176169689Skanstatic alloc_pool operand_entry_pool; 177169689Skan 178169689Skan 179169689Skan/* Starting rank number for a given basic block, so that we can rank 180169689Skan operations using unmovable instructions in that BB based on the bb 181169689Skan depth. */ 182169689Skanstatic unsigned int *bb_rank; 183169689Skan 184169689Skan/* Operand->rank hashtable. */ 185169689Skanstatic htab_t operand_rank; 186169689Skan 187169689Skan 188169689Skan/* Look up the operand rank structure for expression E. */ 189169689Skan 190169689Skanstatic operand_entry_t 191169689Skanfind_operand_rank (tree e) 192169689Skan{ 193169689Skan void **slot; 194169689Skan struct operand_entry vrd; 195169689Skan 196169689Skan vrd.op = e; 197169689Skan slot = htab_find_slot (operand_rank, &vrd, NO_INSERT); 198169689Skan if (!slot) 199169689Skan return NULL; 200169689Skan return ((operand_entry_t) *slot); 201169689Skan} 202169689Skan 203169689Skan/* Insert {E,RANK} into the operand rank hashtable. */ 204169689Skan 205169689Skanstatic void 206169689Skaninsert_operand_rank (tree e, unsigned int rank) 207169689Skan{ 208169689Skan void **slot; 209169689Skan operand_entry_t new_pair = pool_alloc (operand_entry_pool); 210169689Skan 211169689Skan new_pair->op = e; 212169689Skan new_pair->rank = rank; 213169689Skan slot = htab_find_slot (operand_rank, new_pair, INSERT); 214169689Skan gcc_assert (*slot == NULL); 215169689Skan *slot = new_pair; 216169689Skan} 217169689Skan 218169689Skan/* Return the hash value for a operand rank structure */ 219169689Skan 220169689Skanstatic hashval_t 221169689Skanoperand_entry_hash (const void *p) 222169689Skan{ 223169689Skan const operand_entry_t vr = (operand_entry_t) p; 224169689Skan return iterative_hash_expr (vr->op, 0); 225169689Skan} 226169689Skan 227169689Skan/* Return true if two operand rank structures are equal. */ 228169689Skan 229169689Skanstatic int 230169689Skanoperand_entry_eq (const void *p1, const void *p2) 231169689Skan{ 232169689Skan const operand_entry_t vr1 = (operand_entry_t) p1; 233169689Skan const operand_entry_t vr2 = (operand_entry_t) p2; 234169689Skan return vr1->op == vr2->op; 235169689Skan} 236169689Skan 237169689Skan/* Given an expression E, return the rank of the expression. */ 238169689Skan 239169689Skanstatic unsigned int 240169689Skanget_rank (tree e) 241169689Skan{ 242169689Skan operand_entry_t vr; 243169689Skan 244169689Skan /* Constants have rank 0. */ 245169689Skan if (is_gimple_min_invariant (e)) 246169689Skan return 0; 247169689Skan 248169689Skan /* SSA_NAME's have the rank of the expression they are the result 249169689Skan of. 250169689Skan For globals and uninitialized values, the rank is 0. 251169689Skan For function arguments, use the pre-setup rank. 252169689Skan For PHI nodes, stores, asm statements, etc, we use the rank of 253169689Skan the BB. 254169689Skan For simple operations, the rank is the maximum rank of any of 255169689Skan its operands, or the bb_rank, whichever is less. 256169689Skan I make no claims that this is optimal, however, it gives good 257169689Skan results. */ 258169689Skan 259169689Skan if (TREE_CODE (e) == SSA_NAME) 260169689Skan { 261169689Skan tree stmt; 262169689Skan tree rhs; 263169689Skan unsigned int rank, maxrank; 264169689Skan int i; 265169689Skan 266169689Skan if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL 267169689Skan && e == default_def (SSA_NAME_VAR (e))) 268169689Skan return find_operand_rank (e)->rank; 269169689Skan 270169689Skan stmt = SSA_NAME_DEF_STMT (e); 271169689Skan if (bb_for_stmt (stmt) == NULL) 272169689Skan return 0; 273169689Skan 274169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR 275169689Skan || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) 276169689Skan return bb_rank[bb_for_stmt (stmt)->index]; 277169689Skan 278169689Skan /* If we already have a rank for this expression, use that. */ 279169689Skan vr = find_operand_rank (e); 280169689Skan if (vr) 281169689Skan return vr->rank; 282169689Skan 283169689Skan /* Otherwise, find the maximum rank for the operands, or the bb 284169689Skan rank, whichever is less. */ 285169689Skan rank = 0; 286169689Skan maxrank = bb_rank[bb_for_stmt(stmt)->index]; 287169689Skan rhs = TREE_OPERAND (stmt, 1); 288169689Skan if (TREE_CODE_LENGTH (TREE_CODE (rhs)) == 0) 289169689Skan rank = MAX (rank, get_rank (rhs)); 290169689Skan else 291169689Skan { 292169689Skan for (i = 0; 293169689Skan i < TREE_CODE_LENGTH (TREE_CODE (rhs)) 294169689Skan && TREE_OPERAND (rhs, i) 295169689Skan && rank != maxrank; 296169689Skan i++) 297169689Skan rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i))); 298169689Skan } 299169689Skan 300169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 301169689Skan { 302169689Skan fprintf (dump_file, "Rank for "); 303169689Skan print_generic_expr (dump_file, e, 0); 304169689Skan fprintf (dump_file, " is %d\n", (rank + 1)); 305169689Skan } 306169689Skan 307169689Skan /* Note the rank in the hashtable so we don't recompute it. */ 308169689Skan insert_operand_rank (e, (rank + 1)); 309169689Skan return (rank + 1); 310169689Skan } 311169689Skan 312169689Skan /* Globals, etc, are rank 0 */ 313169689Skan return 0; 314169689Skan} 315169689Skan 316169689SkanDEF_VEC_P(operand_entry_t); 317169689SkanDEF_VEC_ALLOC_P(operand_entry_t, heap); 318169689Skan 319169689Skan/* We want integer ones to end up last no matter what, since they are 320169689Skan the ones we can do the most with. */ 321169689Skan#define INTEGER_CONST_TYPE 1 << 3 322169689Skan#define FLOAT_CONST_TYPE 1 << 2 323169689Skan#define OTHER_CONST_TYPE 1 << 1 324169689Skan 325169689Skan/* Classify an invariant tree into integer, float, or other, so that 326169689Skan we can sort them to be near other constants of the same type. */ 327169689Skanstatic inline int 328169689Skanconstant_type (tree t) 329169689Skan{ 330169689Skan if (INTEGRAL_TYPE_P (TREE_TYPE (t))) 331169689Skan return INTEGER_CONST_TYPE; 332169689Skan else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t))) 333169689Skan return FLOAT_CONST_TYPE; 334169689Skan else 335169689Skan return OTHER_CONST_TYPE; 336169689Skan} 337169689Skan 338169689Skan/* qsort comparison function to sort operand entries PA and PB by rank 339169689Skan so that the sorted array is ordered by rank in decreasing order. */ 340169689Skanstatic int 341169689Skansort_by_operand_rank (const void *pa, const void *pb) 342169689Skan{ 343169689Skan const operand_entry_t oea = *(const operand_entry_t *)pa; 344169689Skan const operand_entry_t oeb = *(const operand_entry_t *)pb; 345169689Skan 346169689Skan /* It's nicer for optimize_expression if constants that are likely 347169689Skan to fold when added/multiplied//whatever are put next to each 348169689Skan other. Since all constants have rank 0, order them by type. */ 349169689Skan if (oeb->rank == 0 && oea->rank == 0) 350169689Skan return constant_type (oeb->op) - constant_type (oea->op); 351169689Skan 352169689Skan /* Lastly, make sure the versions that are the same go next to each 353169689Skan other. We use SSA_NAME_VERSION because it's stable. */ 354169689Skan if ((oeb->rank - oea->rank == 0) 355169689Skan && TREE_CODE (oea->op) == SSA_NAME 356169689Skan && TREE_CODE (oeb->op) == SSA_NAME) 357169689Skan return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op); 358169689Skan 359169689Skan return oeb->rank - oea->rank; 360169689Skan} 361169689Skan 362169689Skan/* Add an operand entry to *OPS for the tree operand OP. */ 363169689Skan 364169689Skanstatic void 365169689Skanadd_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op) 366169689Skan{ 367169689Skan operand_entry_t oe = pool_alloc (operand_entry_pool); 368169689Skan 369169689Skan oe->op = op; 370169689Skan oe->rank = get_rank (op); 371169689Skan VEC_safe_push (operand_entry_t, heap, *ops, oe); 372169689Skan} 373169689Skan 374169689Skan/* Return true if STMT is reassociable operation containing a binary 375169689Skan operation with tree code CODE. */ 376169689Skan 377169689Skanstatic bool 378169689Skanis_reassociable_op (tree stmt, enum tree_code code) 379169689Skan{ 380169689Skan if (!IS_EMPTY_STMT (stmt) 381169689Skan && TREE_CODE (stmt) == MODIFY_EXPR 382169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == code 383169689Skan && has_single_use (TREE_OPERAND (stmt, 0))) 384169689Skan return true; 385169689Skan return false; 386169689Skan} 387169689Skan 388169689Skan 389169689Skan/* Given NAME, if NAME is defined by a unary operation OPCODE, return the 390169689Skan operand of the negate operation. Otherwise, return NULL. */ 391169689Skan 392169689Skanstatic tree 393169689Skanget_unary_op (tree name, enum tree_code opcode) 394169689Skan{ 395169689Skan tree stmt = SSA_NAME_DEF_STMT (name); 396169689Skan tree rhs; 397169689Skan 398169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 399169689Skan return NULL_TREE; 400169689Skan 401169689Skan rhs = TREE_OPERAND (stmt, 1); 402169689Skan if (TREE_CODE (rhs) == opcode) 403169689Skan return TREE_OPERAND (rhs, 0); 404169689Skan return NULL_TREE; 405169689Skan} 406169689Skan 407169689Skan/* If CURR and LAST are a pair of ops that OPCODE allows us to 408169689Skan eliminate through equivalences, do so, remove them from OPS, and 409169689Skan return true. Otherwise, return false. */ 410169689Skan 411169689Skanstatic bool 412169689Skaneliminate_duplicate_pair (enum tree_code opcode, 413169689Skan VEC (operand_entry_t, heap) **ops, 414169689Skan bool *all_done, 415169689Skan unsigned int i, 416169689Skan operand_entry_t curr, 417169689Skan operand_entry_t last) 418169689Skan{ 419169689Skan 420169689Skan /* If we have two of the same op, and the opcode is & |, min, or max, 421169689Skan we can eliminate one of them. 422169689Skan If we have two of the same op, and the opcode is ^, we can 423169689Skan eliminate both of them. */ 424169689Skan 425169689Skan if (last && last->op == curr->op) 426169689Skan { 427169689Skan switch (opcode) 428169689Skan { 429169689Skan case MAX_EXPR: 430169689Skan case MIN_EXPR: 431169689Skan case BIT_IOR_EXPR: 432169689Skan case BIT_AND_EXPR: 433169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 434169689Skan { 435169689Skan fprintf (dump_file, "Equivalence: "); 436169689Skan print_generic_expr (dump_file, curr->op, 0); 437169689Skan fprintf (dump_file, " [&|minmax] "); 438169689Skan print_generic_expr (dump_file, last->op, 0); 439169689Skan fprintf (dump_file, " -> "); 440169689Skan print_generic_stmt (dump_file, last->op, 0); 441169689Skan } 442169689Skan 443169689Skan VEC_ordered_remove (operand_entry_t, *ops, i); 444169689Skan reassociate_stats.ops_eliminated ++; 445169689Skan 446169689Skan return true; 447169689Skan 448169689Skan case BIT_XOR_EXPR: 449169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 450169689Skan { 451169689Skan fprintf (dump_file, "Equivalence: "); 452169689Skan print_generic_expr (dump_file, curr->op, 0); 453169689Skan fprintf (dump_file, " ^ "); 454169689Skan print_generic_expr (dump_file, last->op, 0); 455169689Skan fprintf (dump_file, " -> nothing\n"); 456169689Skan } 457169689Skan 458169689Skan reassociate_stats.ops_eliminated += 2; 459169689Skan 460169689Skan if (VEC_length (operand_entry_t, *ops) == 2) 461169689Skan { 462169689Skan VEC_free (operand_entry_t, heap, *ops); 463169689Skan *ops = NULL; 464169689Skan add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op), 465169689Skan integer_zero_node)); 466169689Skan *all_done = true; 467169689Skan } 468169689Skan else 469169689Skan { 470169689Skan VEC_ordered_remove (operand_entry_t, *ops, i-1); 471169689Skan VEC_ordered_remove (operand_entry_t, *ops, i-1); 472169689Skan } 473169689Skan 474169689Skan return true; 475169689Skan 476169689Skan default: 477169689Skan break; 478169689Skan } 479169689Skan } 480169689Skan return false; 481169689Skan} 482169689Skan 483169689Skan/* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression, 484169689Skan look in OPS for a corresponding positive operation to cancel it 485169689Skan out. If we find one, remove the other from OPS, replace 486169689Skan OPS[CURRINDEX] with 0, and return true. Otherwise, return 487169689Skan false. */ 488169689Skan 489169689Skanstatic bool 490169689Skaneliminate_plus_minus_pair (enum tree_code opcode, 491169689Skan VEC (operand_entry_t, heap) **ops, 492169689Skan unsigned int currindex, 493169689Skan operand_entry_t curr) 494169689Skan{ 495169689Skan tree negateop; 496169689Skan unsigned int i; 497169689Skan operand_entry_t oe; 498169689Skan 499169689Skan if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME) 500169689Skan return false; 501169689Skan 502169689Skan negateop = get_unary_op (curr->op, NEGATE_EXPR); 503169689Skan if (negateop == NULL_TREE) 504169689Skan return false; 505169689Skan 506169689Skan /* Any non-negated version will have a rank that is one less than 507169689Skan the current rank. So once we hit those ranks, if we don't find 508169689Skan one, we can stop. */ 509169689Skan 510169689Skan for (i = currindex + 1; 511169689Skan VEC_iterate (operand_entry_t, *ops, i, oe) 512169689Skan && oe->rank >= curr->rank - 1 ; 513169689Skan i++) 514169689Skan { 515169689Skan if (oe->op == negateop) 516169689Skan { 517169689Skan 518169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 519169689Skan { 520169689Skan fprintf (dump_file, "Equivalence: "); 521169689Skan print_generic_expr (dump_file, negateop, 0); 522169689Skan fprintf (dump_file, " + -"); 523169689Skan print_generic_expr (dump_file, oe->op, 0); 524169689Skan fprintf (dump_file, " -> 0\n"); 525169689Skan } 526169689Skan 527169689Skan VEC_ordered_remove (operand_entry_t, *ops, i); 528169689Skan add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op), 529169689Skan integer_zero_node)); 530169689Skan VEC_ordered_remove (operand_entry_t, *ops, currindex); 531169689Skan reassociate_stats.ops_eliminated ++; 532169689Skan 533169689Skan return true; 534169689Skan } 535169689Skan } 536169689Skan 537169689Skan return false; 538169689Skan} 539169689Skan 540169689Skan/* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a 541169689Skan bitwise not expression, look in OPS for a corresponding operand to 542169689Skan cancel it out. If we find one, remove the other from OPS, replace 543169689Skan OPS[CURRINDEX] with 0, and return true. Otherwise, return 544169689Skan false. */ 545169689Skan 546169689Skanstatic bool 547169689Skaneliminate_not_pairs (enum tree_code opcode, 548169689Skan VEC (operand_entry_t, heap) **ops, 549169689Skan unsigned int currindex, 550169689Skan operand_entry_t curr) 551169689Skan{ 552169689Skan tree notop; 553169689Skan unsigned int i; 554169689Skan operand_entry_t oe; 555169689Skan 556169689Skan if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR) 557169689Skan || TREE_CODE (curr->op) != SSA_NAME) 558169689Skan return false; 559169689Skan 560169689Skan notop = get_unary_op (curr->op, BIT_NOT_EXPR); 561169689Skan if (notop == NULL_TREE) 562169689Skan return false; 563169689Skan 564169689Skan /* Any non-not version will have a rank that is one less than 565169689Skan the current rank. So once we hit those ranks, if we don't find 566169689Skan one, we can stop. */ 567169689Skan 568169689Skan for (i = currindex + 1; 569169689Skan VEC_iterate (operand_entry_t, *ops, i, oe) 570169689Skan && oe->rank >= curr->rank - 1; 571169689Skan i++) 572169689Skan { 573169689Skan if (oe->op == notop) 574169689Skan { 575169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 576169689Skan { 577169689Skan fprintf (dump_file, "Equivalence: "); 578169689Skan print_generic_expr (dump_file, notop, 0); 579169689Skan if (opcode == BIT_AND_EXPR) 580169689Skan fprintf (dump_file, " & ~"); 581169689Skan else if (opcode == BIT_IOR_EXPR) 582169689Skan fprintf (dump_file, " | ~"); 583169689Skan print_generic_expr (dump_file, oe->op, 0); 584169689Skan if (opcode == BIT_AND_EXPR) 585169689Skan fprintf (dump_file, " -> 0\n"); 586169689Skan else if (opcode == BIT_IOR_EXPR) 587169689Skan fprintf (dump_file, " -> -1\n"); 588169689Skan } 589169689Skan 590169689Skan if (opcode == BIT_AND_EXPR) 591169689Skan oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node); 592169689Skan else if (opcode == BIT_IOR_EXPR) 593169689Skan oe->op = build_low_bits_mask (TREE_TYPE (oe->op), 594169689Skan TYPE_PRECISION (TREE_TYPE (oe->op))); 595169689Skan 596169689Skan reassociate_stats.ops_eliminated 597169689Skan += VEC_length (operand_entry_t, *ops) - 1; 598169689Skan VEC_free (operand_entry_t, heap, *ops); 599169689Skan *ops = NULL; 600169689Skan VEC_safe_push (operand_entry_t, heap, *ops, oe); 601169689Skan return true; 602169689Skan } 603169689Skan } 604169689Skan 605169689Skan return false; 606169689Skan} 607169689Skan 608169689Skan/* Use constant value that may be present in OPS to try to eliminate 609169689Skan operands. Note that this function is only really used when we've 610169689Skan eliminated ops for other reasons, or merged constants. Across 611169689Skan single statements, fold already does all of this, plus more. There 612169689Skan is little point in duplicating logic, so I've only included the 613169689Skan identities that I could ever construct testcases to trigger. */ 614169689Skan 615169689Skanstatic void 616169689Skaneliminate_using_constants (enum tree_code opcode, 617169689Skan VEC(operand_entry_t, heap) **ops) 618169689Skan{ 619169689Skan operand_entry_t oelast = VEC_last (operand_entry_t, *ops); 620169689Skan 621169689Skan if (oelast->rank == 0 && INTEGRAL_TYPE_P (TREE_TYPE (oelast->op))) 622169689Skan { 623169689Skan switch (opcode) 624169689Skan { 625169689Skan case BIT_AND_EXPR: 626169689Skan if (integer_zerop (oelast->op)) 627169689Skan { 628169689Skan if (VEC_length (operand_entry_t, *ops) != 1) 629169689Skan { 630169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 631169689Skan fprintf (dump_file, "Found & 0, removing all other ops\n"); 632169689Skan 633169689Skan reassociate_stats.ops_eliminated 634169689Skan += VEC_length (operand_entry_t, *ops) - 1; 635169689Skan 636169689Skan VEC_free (operand_entry_t, heap, *ops); 637169689Skan *ops = NULL; 638169689Skan VEC_safe_push (operand_entry_t, heap, *ops, oelast); 639169689Skan return; 640169689Skan } 641169689Skan } 642169689Skan else if (integer_all_onesp (oelast->op)) 643169689Skan { 644169689Skan if (VEC_length (operand_entry_t, *ops) != 1) 645169689Skan { 646169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 647169689Skan fprintf (dump_file, "Found & -1, removing\n"); 648169689Skan VEC_pop (operand_entry_t, *ops); 649169689Skan reassociate_stats.ops_eliminated++; 650169689Skan } 651169689Skan } 652169689Skan break; 653169689Skan case BIT_IOR_EXPR: 654169689Skan if (integer_all_onesp (oelast->op)) 655169689Skan { 656169689Skan if (VEC_length (operand_entry_t, *ops) != 1) 657169689Skan { 658169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 659169689Skan fprintf (dump_file, "Found | -1, removing all other ops\n"); 660169689Skan 661169689Skan reassociate_stats.ops_eliminated 662169689Skan += VEC_length (operand_entry_t, *ops) - 1; 663169689Skan 664169689Skan VEC_free (operand_entry_t, heap, *ops); 665169689Skan *ops = NULL; 666169689Skan VEC_safe_push (operand_entry_t, heap, *ops, oelast); 667169689Skan return; 668169689Skan } 669169689Skan } 670169689Skan else if (integer_zerop (oelast->op)) 671169689Skan { 672169689Skan if (VEC_length (operand_entry_t, *ops) != 1) 673169689Skan { 674169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 675169689Skan fprintf (dump_file, "Found | 0, removing\n"); 676169689Skan VEC_pop (operand_entry_t, *ops); 677169689Skan reassociate_stats.ops_eliminated++; 678169689Skan } 679169689Skan } 680169689Skan break; 681169689Skan case MULT_EXPR: 682169689Skan if (integer_zerop (oelast->op)) 683169689Skan { 684169689Skan if (VEC_length (operand_entry_t, *ops) != 1) 685169689Skan { 686169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 687169689Skan fprintf (dump_file, "Found * 0, removing all other ops\n"); 688169689Skan 689169689Skan reassociate_stats.ops_eliminated 690169689Skan += VEC_length (operand_entry_t, *ops) - 1; 691169689Skan VEC_free (operand_entry_t, heap, *ops); 692169689Skan *ops = NULL; 693169689Skan VEC_safe_push (operand_entry_t, heap, *ops, oelast); 694169689Skan return; 695169689Skan } 696169689Skan } 697169689Skan else if (integer_onep (oelast->op)) 698169689Skan { 699169689Skan if (VEC_length (operand_entry_t, *ops) != 1) 700169689Skan { 701169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 702169689Skan fprintf (dump_file, "Found * 1, removing\n"); 703169689Skan VEC_pop (operand_entry_t, *ops); 704169689Skan reassociate_stats.ops_eliminated++; 705169689Skan return; 706169689Skan } 707169689Skan } 708169689Skan break; 709169689Skan case BIT_XOR_EXPR: 710169689Skan case PLUS_EXPR: 711169689Skan case MINUS_EXPR: 712169689Skan if (integer_zerop (oelast->op)) 713169689Skan { 714169689Skan if (VEC_length (operand_entry_t, *ops) != 1) 715169689Skan { 716169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 717169689Skan fprintf (dump_file, "Found [|^+] 0, removing\n"); 718169689Skan VEC_pop (operand_entry_t, *ops); 719169689Skan reassociate_stats.ops_eliminated++; 720169689Skan return; 721169689Skan } 722169689Skan } 723169689Skan break; 724169689Skan default: 725169689Skan break; 726169689Skan } 727169689Skan } 728169689Skan} 729169689Skan 730169689Skan/* Perform various identities and other optimizations on the list of 731169689Skan operand entries, stored in OPS. The tree code for the binary 732169689Skan operation between all the operands is OPCODE. */ 733169689Skan 734169689Skanstatic void 735169689Skanoptimize_ops_list (enum tree_code opcode, 736169689Skan VEC (operand_entry_t, heap) **ops) 737169689Skan{ 738169689Skan unsigned int length = VEC_length (operand_entry_t, *ops); 739169689Skan unsigned int i; 740169689Skan operand_entry_t oe; 741169689Skan operand_entry_t oelast = NULL; 742169689Skan bool iterate = false; 743169689Skan 744169689Skan if (length == 1) 745169689Skan return; 746169689Skan 747169689Skan oelast = VEC_last (operand_entry_t, *ops); 748169689Skan 749169689Skan /* If the last two are constants, pop the constants off, merge them 750169689Skan and try the next two. */ 751169689Skan if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op)) 752169689Skan { 753169689Skan operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2); 754169689Skan 755169689Skan if (oelm1->rank == 0 756169689Skan && is_gimple_min_invariant (oelm1->op) 757169689Skan && lang_hooks.types_compatible_p (TREE_TYPE (oelm1->op), 758169689Skan TREE_TYPE (oelast->op))) 759169689Skan { 760169689Skan tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op), 761169689Skan oelm1->op, oelast->op); 762169689Skan 763169689Skan if (folded && is_gimple_min_invariant (folded)) 764169689Skan { 765169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 766169689Skan fprintf (dump_file, "Merging constants\n"); 767169689Skan 768169689Skan VEC_pop (operand_entry_t, *ops); 769169689Skan VEC_pop (operand_entry_t, *ops); 770169689Skan 771169689Skan add_to_ops_vec (ops, folded); 772169689Skan reassociate_stats.constants_eliminated++; 773169689Skan 774169689Skan optimize_ops_list (opcode, ops); 775169689Skan return; 776169689Skan } 777169689Skan } 778169689Skan } 779169689Skan 780169689Skan eliminate_using_constants (opcode, ops); 781169689Skan oelast = NULL; 782169689Skan 783169689Skan for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);) 784169689Skan { 785169689Skan bool done = false; 786169689Skan 787169689Skan if (eliminate_not_pairs (opcode, ops, i, oe)) 788169689Skan return; 789169689Skan if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast) 790169689Skan || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe))) 791169689Skan { 792169689Skan if (done) 793169689Skan return; 794169689Skan iterate = true; 795169689Skan oelast = NULL; 796169689Skan continue; 797169689Skan } 798169689Skan oelast = oe; 799169689Skan i++; 800169689Skan } 801169689Skan 802169689Skan length = VEC_length (operand_entry_t, *ops); 803169689Skan oelast = VEC_last (operand_entry_t, *ops); 804169689Skan 805169689Skan if (iterate) 806169689Skan optimize_ops_list (opcode, ops); 807169689Skan} 808169689Skan 809169689Skan/* Return true if OPERAND is defined by a PHI node which uses the LHS 810169689Skan of STMT in it's operands. This is also known as a "destructive 811169689Skan update" operation. */ 812169689Skan 813169689Skanstatic bool 814169689Skanis_phi_for_stmt (tree stmt, tree operand) 815169689Skan{ 816169689Skan tree def_stmt; 817169689Skan tree lhs = TREE_OPERAND (stmt, 0); 818169689Skan use_operand_p arg_p; 819169689Skan ssa_op_iter i; 820169689Skan 821169689Skan if (TREE_CODE (operand) != SSA_NAME) 822169689Skan return false; 823169689Skan 824169689Skan def_stmt = SSA_NAME_DEF_STMT (operand); 825169689Skan if (TREE_CODE (def_stmt) != PHI_NODE) 826169689Skan return false; 827169689Skan 828169689Skan FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE) 829169689Skan if (lhs == USE_FROM_PTR (arg_p)) 830169689Skan return true; 831169689Skan return false; 832169689Skan} 833169689Skan 834169689Skan/* Recursively rewrite our linearized statements so that the operators 835169689Skan match those in OPS[OPINDEX], putting the computation in rank 836169689Skan order. */ 837169689Skan 838169689Skanstatic void 839169689Skanrewrite_expr_tree (tree stmt, unsigned int opindex, 840169689Skan VEC(operand_entry_t, heap) * ops) 841169689Skan{ 842169689Skan tree rhs = TREE_OPERAND (stmt, 1); 843169689Skan operand_entry_t oe; 844169689Skan 845169689Skan /* If we have three operands left, then we want to make sure the one 846169689Skan that gets the double binary op are the ones with the same rank. 847169689Skan 848169689Skan The alternative we try is to see if this is a destructive 849169689Skan update style statement, which is like: 850169689Skan b = phi (a, ...) 851169689Skan a = c + b; 852169689Skan In that case, we want to use the destructive update form to 853169689Skan expose the possible vectorizer sum reduction opportunity. 854169689Skan In that case, the third operand will be the phi node. 855169689Skan 856169689Skan We could, of course, try to be better as noted above, and do a 857169689Skan lot of work to try to find these opportunities in >3 operand 858169689Skan cases, but it is unlikely to be worth it. */ 859169689Skan if (opindex + 3 == VEC_length (operand_entry_t, ops)) 860169689Skan { 861169689Skan operand_entry_t oe1, oe2, oe3; 862169689Skan 863169689Skan oe1 = VEC_index (operand_entry_t, ops, opindex); 864169689Skan oe2 = VEC_index (operand_entry_t, ops, opindex + 1); 865169689Skan oe3 = VEC_index (operand_entry_t, ops, opindex + 2); 866169689Skan 867169689Skan if ((oe1->rank == oe2->rank 868169689Skan && oe2->rank != oe3->rank) 869169689Skan || (is_phi_for_stmt (stmt, oe3->op) 870169689Skan && !is_phi_for_stmt (stmt, oe1->op) 871169689Skan && !is_phi_for_stmt (stmt, oe2->op))) 872169689Skan { 873169689Skan struct operand_entry temp = *oe3; 874169689Skan oe3->op = oe1->op; 875169689Skan oe3->rank = oe1->rank; 876169689Skan oe1->op = temp.op; 877169689Skan oe1->rank= temp.rank; 878169689Skan } 879169689Skan } 880169689Skan 881169689Skan /* The final recursion case for this function is that you have 882169689Skan exactly two operations left. 883169689Skan If we had one exactly one op in the entire list to start with, we 884169689Skan would have never called this function, and the tail recursion 885169689Skan rewrites them one at a time. */ 886169689Skan if (opindex + 2 == VEC_length (operand_entry_t, ops)) 887169689Skan { 888169689Skan operand_entry_t oe1, oe2; 889169689Skan 890169689Skan oe1 = VEC_index (operand_entry_t, ops, opindex); 891169689Skan oe2 = VEC_index (operand_entry_t, ops, opindex + 1); 892169689Skan 893169689Skan if (TREE_OPERAND (rhs, 0) != oe1->op 894169689Skan || TREE_OPERAND (rhs, 1) != oe2->op) 895169689Skan { 896169689Skan 897169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 898169689Skan { 899169689Skan fprintf (dump_file, "Transforming "); 900169689Skan print_generic_expr (dump_file, rhs, 0); 901169689Skan } 902169689Skan 903169689Skan TREE_OPERAND (rhs, 0) = oe1->op; 904169689Skan TREE_OPERAND (rhs, 1) = oe2->op; 905169689Skan update_stmt (stmt); 906169689Skan 907169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 908169689Skan { 909169689Skan fprintf (dump_file, " into "); 910169689Skan print_generic_stmt (dump_file, rhs, 0); 911169689Skan } 912169689Skan 913169689Skan } 914169689Skan return; 915169689Skan } 916169689Skan 917169689Skan /* If we hit here, we should have 3 or more ops left. */ 918169689Skan gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops)); 919169689Skan 920169689Skan /* Rewrite the next operator. */ 921169689Skan oe = VEC_index (operand_entry_t, ops, opindex); 922169689Skan 923169689Skan if (oe->op != TREE_OPERAND (rhs, 1)) 924169689Skan { 925169689Skan 926169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 927169689Skan { 928169689Skan fprintf (dump_file, "Transforming "); 929169689Skan print_generic_expr (dump_file, rhs, 0); 930169689Skan } 931169689Skan 932169689Skan TREE_OPERAND (rhs, 1) = oe->op; 933169689Skan update_stmt (stmt); 934169689Skan 935169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 936169689Skan { 937169689Skan fprintf (dump_file, " into "); 938169689Skan print_generic_stmt (dump_file, rhs, 0); 939169689Skan } 940169689Skan } 941169689Skan /* Recurse on the LHS of the binary operator, which is guaranteed to 942169689Skan be the non-leaf side. */ 943169689Skan rewrite_expr_tree (SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)), 944169689Skan opindex + 1, ops); 945169689Skan} 946169689Skan 947169689Skan/* Transform STMT, which is really (A +B) + (C + D) into the left 948169689Skan linear form, ((A+B)+C)+D. 949169689Skan Recurse on D if necessary. */ 950169689Skan 951169689Skanstatic void 952169689Skanlinearize_expr (tree stmt) 953169689Skan{ 954169689Skan block_stmt_iterator bsinow, bsirhs; 955169689Skan tree rhs = TREE_OPERAND (stmt, 1); 956169689Skan enum tree_code rhscode = TREE_CODE (rhs); 957169689Skan tree binrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1)); 958169689Skan tree binlhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)); 959169689Skan tree newbinrhs = NULL_TREE; 960169689Skan 961169689Skan gcc_assert (is_reassociable_op (binlhs, TREE_CODE (rhs)) 962169689Skan && is_reassociable_op (binrhs, TREE_CODE (rhs))); 963169689Skan 964169689Skan bsinow = bsi_for_stmt (stmt); 965169689Skan bsirhs = bsi_for_stmt (binrhs); 966169689Skan bsi_move_before (&bsirhs, &bsinow); 967169689Skan 968169689Skan TREE_OPERAND (rhs, 1) = TREE_OPERAND (TREE_OPERAND (binrhs, 1), 0); 969169689Skan if (TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME) 970169689Skan newbinrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1)); 971169689Skan TREE_OPERAND (TREE_OPERAND (binrhs, 1), 0) = TREE_OPERAND (binlhs, 0); 972169689Skan TREE_OPERAND (rhs, 0) = TREE_OPERAND (binrhs, 0); 973169689Skan 974169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 975169689Skan { 976169689Skan fprintf (dump_file, "Linearized: "); 977169689Skan print_generic_stmt (dump_file, rhs, 0); 978169689Skan } 979169689Skan 980169689Skan reassociate_stats.linearized++; 981169689Skan update_stmt (binrhs); 982169689Skan update_stmt (binlhs); 983169689Skan update_stmt (stmt); 984169689Skan TREE_VISITED (binrhs) = 1; 985169689Skan TREE_VISITED (binlhs) = 1; 986169689Skan TREE_VISITED (stmt) = 1; 987169689Skan 988169689Skan /* Tail recurse on the new rhs if it still needs reassociation. */ 989169689Skan if (newbinrhs && is_reassociable_op (newbinrhs, rhscode)) 990169689Skan linearize_expr (stmt); 991169689Skan 992169689Skan} 993169689Skan 994169689Skan/* If LHS has a single immediate use that is a MODIFY_EXPR, return 995169689Skan it. Otherwise, return NULL. */ 996169689Skan 997169689Skanstatic tree 998169689Skanget_single_immediate_use (tree lhs) 999169689Skan{ 1000169689Skan use_operand_p immuse; 1001169689Skan tree immusestmt; 1002169689Skan 1003169689Skan if (TREE_CODE (lhs) == SSA_NAME 1004169689Skan && single_imm_use (lhs, &immuse, &immusestmt)) 1005169689Skan { 1006169689Skan if (TREE_CODE (immusestmt) == RETURN_EXPR) 1007169689Skan immusestmt = TREE_OPERAND (immusestmt, 0); 1008169689Skan if (TREE_CODE (immusestmt) == MODIFY_EXPR) 1009169689Skan return immusestmt; 1010169689Skan } 1011169689Skan return NULL_TREE; 1012169689Skan} 1013169689Skanstatic VEC(tree, heap) *broken_up_subtracts; 1014169689Skan 1015169689Skan 1016169689Skan/* Recursively negate the value of TONEGATE, and return the SSA_NAME 1017169689Skan representing the negated value. Insertions of any necessary 1018169689Skan instructions go before BSI. 1019169689Skan This function is recursive in that, if you hand it "a_5" as the 1020169689Skan value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will 1021169689Skan transform b_3 + b_4 into a_5 = -b_3 + -b_4. */ 1022169689Skan 1023169689Skanstatic tree 1024169689Skannegate_value (tree tonegate, block_stmt_iterator *bsi) 1025169689Skan{ 1026169689Skan tree negatedef = tonegate; 1027169689Skan tree resultofnegate; 1028169689Skan 1029169689Skan if (TREE_CODE (tonegate) == SSA_NAME) 1030169689Skan negatedef = SSA_NAME_DEF_STMT (tonegate); 1031169689Skan 1032169689Skan /* If we are trying to negate a name, defined by an add, negate the 1033169689Skan add operands instead. */ 1034169689Skan if (TREE_CODE (tonegate) == SSA_NAME 1035169689Skan && TREE_CODE (negatedef) == MODIFY_EXPR 1036169689Skan && TREE_CODE (TREE_OPERAND (negatedef, 0)) == SSA_NAME 1037169689Skan && has_single_use (TREE_OPERAND (negatedef, 0)) 1038169689Skan && TREE_CODE (TREE_OPERAND (negatedef, 1)) == PLUS_EXPR) 1039169689Skan { 1040169689Skan block_stmt_iterator bsi; 1041169689Skan tree binop = TREE_OPERAND (negatedef, 1); 1042169689Skan 1043169689Skan bsi = bsi_for_stmt (negatedef); 1044169689Skan TREE_OPERAND (binop, 0) = negate_value (TREE_OPERAND (binop, 0), 1045169689Skan &bsi); 1046169689Skan bsi = bsi_for_stmt (negatedef); 1047169689Skan TREE_OPERAND (binop, 1) = negate_value (TREE_OPERAND (binop, 1), 1048169689Skan &bsi); 1049169689Skan update_stmt (negatedef); 1050169689Skan return TREE_OPERAND (negatedef, 0); 1051169689Skan } 1052169689Skan 1053169689Skan tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate); 1054169689Skan resultofnegate = force_gimple_operand_bsi (bsi, tonegate, true, 1055169689Skan NULL_TREE); 1056169689Skan VEC_safe_push (tree, heap, broken_up_subtracts, resultofnegate); 1057169689Skan return resultofnegate; 1058169689Skan 1059169689Skan} 1060169689Skan 1061169689Skan/* Return true if we should break up the subtract in STMT into an add 1062169689Skan with negate. This is true when we the subtract operands are really 1063169689Skan adds, or the subtract itself is used in an add expression. In 1064169689Skan either case, breaking up the subtract into an add with negate 1065169689Skan exposes the adds to reassociation. */ 1066169689Skan 1067169689Skanstatic bool 1068169689Skanshould_break_up_subtract (tree stmt) 1069169689Skan{ 1070169689Skan 1071169689Skan tree lhs = TREE_OPERAND (stmt, 0); 1072169689Skan tree rhs = TREE_OPERAND (stmt, 1); 1073169689Skan tree binlhs = TREE_OPERAND (rhs, 0); 1074169689Skan tree binrhs = TREE_OPERAND (rhs, 1); 1075169689Skan tree immusestmt; 1076169689Skan 1077169689Skan if (TREE_CODE (binlhs) == SSA_NAME 1078169689Skan && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR)) 1079169689Skan return true; 1080169689Skan 1081169689Skan if (TREE_CODE (binrhs) == SSA_NAME 1082169689Skan && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR)) 1083169689Skan return true; 1084169689Skan 1085169689Skan if (TREE_CODE (lhs) == SSA_NAME 1086169689Skan && (immusestmt = get_single_immediate_use (lhs)) 1087169689Skan && TREE_CODE (TREE_OPERAND (immusestmt, 1)) == PLUS_EXPR) 1088169689Skan return true; 1089169689Skan return false; 1090169689Skan 1091169689Skan} 1092169689Skan 1093169689Skan/* Transform STMT from A - B into A + -B. */ 1094169689Skan 1095169689Skanstatic void 1096169689Skanbreak_up_subtract (tree stmt, block_stmt_iterator *bsi) 1097169689Skan{ 1098169689Skan tree rhs = TREE_OPERAND (stmt, 1); 1099169689Skan 1100169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1101169689Skan { 1102169689Skan fprintf (dump_file, "Breaking up subtract "); 1103169689Skan print_generic_stmt (dump_file, stmt, 0); 1104169689Skan } 1105169689Skan 1106169689Skan TREE_SET_CODE (TREE_OPERAND (stmt, 1), PLUS_EXPR); 1107169689Skan TREE_OPERAND (rhs, 1) = negate_value (TREE_OPERAND (rhs, 1), bsi); 1108169689Skan 1109169689Skan update_stmt (stmt); 1110169689Skan} 1111169689Skan 1112169689Skan/* Recursively linearize a binary expression that is the RHS of STMT. 1113169689Skan Place the operands of the expression tree in the vector named OPS. */ 1114169689Skan 1115169689Skanstatic void 1116169689Skanlinearize_expr_tree (VEC(operand_entry_t, heap) **ops, tree stmt) 1117169689Skan{ 1118169689Skan block_stmt_iterator bsinow, bsilhs; 1119169689Skan tree rhs = TREE_OPERAND (stmt, 1); 1120169689Skan tree binrhs = TREE_OPERAND (rhs, 1); 1121169689Skan tree binlhs = TREE_OPERAND (rhs, 0); 1122169689Skan tree binlhsdef, binrhsdef; 1123169689Skan bool binlhsisreassoc = false; 1124169689Skan bool binrhsisreassoc = false; 1125169689Skan enum tree_code rhscode = TREE_CODE (rhs); 1126169689Skan 1127169689Skan TREE_VISITED (stmt) = 1; 1128169689Skan 1129169689Skan if (TREE_CODE (binlhs) == SSA_NAME) 1130169689Skan { 1131169689Skan binlhsdef = SSA_NAME_DEF_STMT (binlhs); 1132169689Skan binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode); 1133169689Skan } 1134169689Skan 1135169689Skan if (TREE_CODE (binrhs) == SSA_NAME) 1136169689Skan { 1137169689Skan binrhsdef = SSA_NAME_DEF_STMT (binrhs); 1138169689Skan binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode); 1139169689Skan } 1140169689Skan 1141169689Skan /* If the LHS is not reassociable, but the RHS is, we need to swap 1142169689Skan them. If neither is reassociable, there is nothing we can do, so 1143169689Skan just put them in the ops vector. If the LHS is reassociable, 1144169689Skan linearize it. If both are reassociable, then linearize the RHS 1145169689Skan and the LHS. */ 1146169689Skan 1147169689Skan if (!binlhsisreassoc) 1148169689Skan { 1149169689Skan tree temp; 1150169689Skan 1151169689Skan if (!binrhsisreassoc) 1152169689Skan { 1153169689Skan add_to_ops_vec (ops, binrhs); 1154169689Skan add_to_ops_vec (ops, binlhs); 1155169689Skan return; 1156169689Skan } 1157169689Skan 1158169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1159169689Skan { 1160169689Skan fprintf (dump_file, "swapping operands of "); 1161169689Skan print_generic_expr (dump_file, stmt, 0); 1162169689Skan } 1163169689Skan 1164169689Skan swap_tree_operands (stmt, &TREE_OPERAND (rhs, 0), 1165169689Skan &TREE_OPERAND (rhs, 1)); 1166169689Skan update_stmt (stmt); 1167169689Skan 1168169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1169169689Skan { 1170169689Skan fprintf (dump_file, " is now "); 1171169689Skan print_generic_stmt (dump_file, stmt, 0); 1172169689Skan } 1173169689Skan 1174169689Skan /* We want to make it so the lhs is always the reassociative op, 1175169689Skan so swap. */ 1176169689Skan temp = binlhs; 1177169689Skan binlhs = binrhs; 1178169689Skan binrhs = temp; 1179169689Skan } 1180169689Skan else if (binrhsisreassoc) 1181169689Skan { 1182169689Skan linearize_expr (stmt); 1183169689Skan gcc_assert (rhs == TREE_OPERAND (stmt, 1)); 1184169689Skan binlhs = TREE_OPERAND (rhs, 0); 1185169689Skan binrhs = TREE_OPERAND (rhs, 1); 1186169689Skan } 1187169689Skan 1188169689Skan gcc_assert (TREE_CODE (binrhs) != SSA_NAME 1189169689Skan || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), rhscode)); 1190169689Skan bsinow = bsi_for_stmt (stmt); 1191169689Skan bsilhs = bsi_for_stmt (SSA_NAME_DEF_STMT (binlhs)); 1192169689Skan bsi_move_before (&bsilhs, &bsinow); 1193169689Skan linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs)); 1194169689Skan add_to_ops_vec (ops, binrhs); 1195169689Skan} 1196169689Skan 1197169689Skan/* Repropagate the negates back into subtracts, since no other pass 1198169689Skan currently does it. */ 1199169689Skan 1200169689Skanstatic void 1201169689Skanrepropagate_negates (void) 1202169689Skan{ 1203169689Skan unsigned int i = 0; 1204169689Skan tree negate; 1205169689Skan 1206169689Skan for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++) 1207169689Skan { 1208169689Skan tree user = get_single_immediate_use (negate); 1209169689Skan 1210169689Skan /* The negate operand can be either operand of a PLUS_EXPR 1211169689Skan (it can be the LHS if the RHS is a constant for example). 1212169689Skan 1213169689Skan Force the negate operand to the RHS of the PLUS_EXPR, then 1214169689Skan transform the PLUS_EXPR into a MINUS_EXPR. */ 1215169689Skan if (user 1216169689Skan && TREE_CODE (user) == MODIFY_EXPR 1217169689Skan && TREE_CODE (TREE_OPERAND (user, 1)) == PLUS_EXPR) 1218169689Skan { 1219169689Skan tree rhs = TREE_OPERAND (user, 1); 1220169689Skan 1221169689Skan /* If the negated operand appears on the LHS of the 1222169689Skan PLUS_EXPR, exchange the operands of the PLUS_EXPR 1223169689Skan to force the negated operand to the RHS of the PLUS_EXPR. */ 1224169689Skan if (TREE_OPERAND (TREE_OPERAND (user, 1), 0) == negate) 1225169689Skan { 1226169689Skan tree temp = TREE_OPERAND (rhs, 0); 1227169689Skan TREE_OPERAND (rhs, 0) = TREE_OPERAND (rhs, 1); 1228169689Skan TREE_OPERAND (rhs, 1) = temp; 1229169689Skan } 1230169689Skan 1231169689Skan /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace 1232169689Skan the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR. */ 1233169689Skan if (TREE_OPERAND (TREE_OPERAND (user, 1), 1) == negate) 1234169689Skan { 1235169689Skan TREE_SET_CODE (rhs, MINUS_EXPR); 1236169689Skan TREE_OPERAND (rhs, 1) = get_unary_op (negate, NEGATE_EXPR); 1237169689Skan update_stmt (user); 1238169689Skan } 1239169689Skan } 1240169689Skan } 1241169689Skan} 1242169689Skan 1243169689Skan/* Break up subtract operations in block BB. 1244169689Skan 1245169689Skan We do this top down because we don't know whether the subtract is 1246169689Skan part of a possible chain of reassociation except at the top. 1247169689Skan 1248169689Skan IE given 1249169689Skan d = f + g 1250169689Skan c = a + e 1251169689Skan b = c - d 1252169689Skan q = b - r 1253169689Skan k = t - q 1254169689Skan 1255169689Skan we want to break up k = t - q, but we won't until we've transformed q 1256169689Skan = b - r, which won't be broken up until we transform b = c - d. */ 1257169689Skan 1258169689Skanstatic void 1259169689Skanbreak_up_subtract_bb (basic_block bb) 1260169689Skan{ 1261169689Skan block_stmt_iterator bsi; 1262169689Skan basic_block son; 1263169689Skan 1264169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1265169689Skan { 1266169689Skan tree stmt = bsi_stmt (bsi); 1267169689Skan 1268169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 1269169689Skan { 1270169689Skan tree lhs = TREE_OPERAND (stmt, 0); 1271169689Skan tree rhs = TREE_OPERAND (stmt, 1); 1272169689Skan 1273169689Skan TREE_VISITED (stmt) = 0; 1274169689Skan /* If unsafe math optimizations we can do reassociation for 1275169689Skan non-integral types. */ 1276169689Skan if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 1277169689Skan || !INTEGRAL_TYPE_P (TREE_TYPE (rhs))) 1278169689Skan && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs)) 1279169689Skan || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs)) 1280169689Skan || !flag_unsafe_math_optimizations)) 1281169689Skan continue; 1282169689Skan 1283169689Skan /* Check for a subtract used only in an addition. If this 1284169689Skan is the case, transform it into add of a negate for better 1285169689Skan reassociation. IE transform C = A-B into C = A + -B if C 1286169689Skan is only used in an addition. */ 1287169689Skan if (TREE_CODE (rhs) == MINUS_EXPR) 1288169689Skan if (should_break_up_subtract (stmt)) 1289169689Skan break_up_subtract (stmt, &bsi); 1290169689Skan } 1291169689Skan } 1292169689Skan for (son = first_dom_son (CDI_DOMINATORS, bb); 1293169689Skan son; 1294169689Skan son = next_dom_son (CDI_DOMINATORS, son)) 1295169689Skan break_up_subtract_bb (son); 1296169689Skan} 1297169689Skan 1298169689Skan/* Reassociate expressions in basic block BB and its post-dominator as 1299169689Skan children. */ 1300169689Skan 1301169689Skanstatic void 1302169689Skanreassociate_bb (basic_block bb) 1303169689Skan{ 1304169689Skan block_stmt_iterator bsi; 1305169689Skan basic_block son; 1306169689Skan 1307169689Skan for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 1308169689Skan { 1309169689Skan tree stmt = bsi_stmt (bsi); 1310169689Skan 1311169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 1312169689Skan { 1313169689Skan tree lhs = TREE_OPERAND (stmt, 0); 1314169689Skan tree rhs = TREE_OPERAND (stmt, 1); 1315169689Skan 1316169689Skan /* If this was part of an already processed tree, we don't 1317169689Skan need to touch it again. */ 1318169689Skan if (TREE_VISITED (stmt)) 1319169689Skan continue; 1320169689Skan 1321169689Skan /* If unsafe math optimizations we can do reassociation for 1322169689Skan non-integral types. */ 1323169689Skan if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 1324169689Skan || !INTEGRAL_TYPE_P (TREE_TYPE (rhs))) 1325169689Skan && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs)) 1326169689Skan || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs)) 1327169689Skan || !flag_unsafe_math_optimizations)) 1328169689Skan continue; 1329169689Skan 1330169689Skan if (associative_tree_code (TREE_CODE (rhs))) 1331169689Skan { 1332169689Skan VEC(operand_entry_t, heap) *ops = NULL; 1333169689Skan 1334169689Skan /* There may be no immediate uses left by the time we 1335169689Skan get here because we may have eliminated them all. */ 1336169689Skan if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs)) 1337169689Skan continue; 1338169689Skan 1339169689Skan TREE_VISITED (stmt) = 1; 1340169689Skan linearize_expr_tree (&ops, stmt); 1341169689Skan qsort (VEC_address (operand_entry_t, ops), 1342169689Skan VEC_length (operand_entry_t, ops), 1343169689Skan sizeof (operand_entry_t), 1344169689Skan sort_by_operand_rank); 1345169689Skan optimize_ops_list (TREE_CODE (rhs), &ops); 1346169689Skan 1347169689Skan if (VEC_length (operand_entry_t, ops) == 1) 1348169689Skan { 1349169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1350169689Skan { 1351169689Skan fprintf (dump_file, "Transforming "); 1352169689Skan print_generic_expr (dump_file, rhs, 0); 1353169689Skan } 1354169689Skan TREE_OPERAND (stmt, 1) = VEC_last (operand_entry_t, ops)->op; 1355169689Skan update_stmt (stmt); 1356169689Skan 1357169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1358169689Skan { 1359169689Skan fprintf (dump_file, " into "); 1360169689Skan print_generic_stmt (dump_file, 1361169689Skan TREE_OPERAND (stmt, 1), 0); 1362169689Skan } 1363169689Skan } 1364169689Skan else 1365169689Skan { 1366169689Skan rewrite_expr_tree (stmt, 0, ops); 1367169689Skan } 1368169689Skan 1369169689Skan VEC_free (operand_entry_t, heap, ops); 1370169689Skan } 1371169689Skan } 1372169689Skan } 1373169689Skan for (son = first_dom_son (CDI_POST_DOMINATORS, bb); 1374169689Skan son; 1375169689Skan son = next_dom_son (CDI_POST_DOMINATORS, son)) 1376169689Skan reassociate_bb (son); 1377169689Skan} 1378169689Skan 1379169689Skanvoid dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops); 1380169689Skanvoid debug_ops_vector (VEC (operand_entry_t, heap) *ops); 1381169689Skan 1382169689Skan/* Dump the operand entry vector OPS to FILE. */ 1383169689Skan 1384169689Skanvoid 1385169689Skandump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops) 1386169689Skan{ 1387169689Skan operand_entry_t oe; 1388169689Skan unsigned int i; 1389169689Skan 1390169689Skan for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++) 1391169689Skan { 1392169689Skan fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank); 1393169689Skan print_generic_stmt (file, oe->op, 0); 1394169689Skan } 1395169689Skan} 1396169689Skan 1397169689Skan/* Dump the operand entry vector OPS to STDERR. */ 1398169689Skan 1399169689Skanvoid 1400169689Skandebug_ops_vector (VEC (operand_entry_t, heap) *ops) 1401169689Skan{ 1402169689Skan dump_ops_vector (stderr, ops); 1403169689Skan} 1404169689Skan 1405169689Skanstatic void 1406169689Skando_reassoc (void) 1407169689Skan{ 1408169689Skan break_up_subtract_bb (ENTRY_BLOCK_PTR); 1409169689Skan reassociate_bb (EXIT_BLOCK_PTR); 1410169689Skan} 1411169689Skan 1412169689Skan/* Initialize the reassociation pass. */ 1413169689Skan 1414169689Skanstatic void 1415169689Skaninit_reassoc (void) 1416169689Skan{ 1417169689Skan int i; 1418169689Skan unsigned int rank = 2; 1419169689Skan tree param; 1420169689Skan int *bbs = XNEWVEC (int, last_basic_block + 1); 1421169689Skan 1422169689Skan memset (&reassociate_stats, 0, sizeof (reassociate_stats)); 1423169689Skan 1424169689Skan operand_entry_pool = create_alloc_pool ("operand entry pool", 1425169689Skan sizeof (struct operand_entry), 30); 1426169689Skan 1427169689Skan /* Reverse RPO (Reverse Post Order) will give us something where 1428169689Skan deeper loops come later. */ 1429169689Skan pre_and_rev_post_order_compute (NULL, bbs, false); 1430169689Skan bb_rank = XCNEWVEC (unsigned int, last_basic_block + 1); 1431169689Skan 1432169689Skan operand_rank = htab_create (511, operand_entry_hash, 1433169689Skan operand_entry_eq, 0); 1434169689Skan 1435169689Skan /* Give each argument a distinct rank. */ 1436169689Skan for (param = DECL_ARGUMENTS (current_function_decl); 1437169689Skan param; 1438169689Skan param = TREE_CHAIN (param)) 1439169689Skan { 1440169689Skan if (default_def (param) != NULL) 1441169689Skan { 1442169689Skan tree def = default_def (param); 1443169689Skan insert_operand_rank (def, ++rank); 1444169689Skan } 1445169689Skan } 1446169689Skan 1447169689Skan /* Give the chain decl a distinct rank. */ 1448169689Skan if (cfun->static_chain_decl != NULL) 1449169689Skan { 1450169689Skan tree def = default_def (cfun->static_chain_decl); 1451169689Skan if (def != NULL) 1452169689Skan insert_operand_rank (def, ++rank); 1453169689Skan } 1454169689Skan 1455169689Skan /* Set up rank for each BB */ 1456169689Skan for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++) 1457169689Skan bb_rank[bbs[i]] = ++rank << 16; 1458169689Skan 1459169689Skan free (bbs); 1460169689Skan calculate_dominance_info (CDI_DOMINATORS); 1461169689Skan calculate_dominance_info (CDI_POST_DOMINATORS); 1462169689Skan broken_up_subtracts = NULL; 1463169689Skan} 1464169689Skan 1465169689Skan/* Cleanup after the reassociation pass, and print stats if 1466169689Skan requested. */ 1467169689Skan 1468169689Skanstatic void 1469169689Skanfini_reassoc (void) 1470169689Skan{ 1471169689Skan 1472169689Skan if (dump_file && (dump_flags & TDF_STATS)) 1473169689Skan { 1474169689Skan fprintf (dump_file, "Reassociation stats:\n"); 1475169689Skan fprintf (dump_file, "Linearized: %d\n", 1476169689Skan reassociate_stats.linearized); 1477169689Skan fprintf (dump_file, "Constants eliminated: %d\n", 1478169689Skan reassociate_stats.constants_eliminated); 1479169689Skan fprintf (dump_file, "Ops eliminated: %d\n", 1480169689Skan reassociate_stats.ops_eliminated); 1481169689Skan fprintf (dump_file, "Statements rewritten: %d\n", 1482169689Skan reassociate_stats.rewritten); 1483169689Skan } 1484169689Skan htab_delete (operand_rank); 1485169689Skan 1486169689Skan free_alloc_pool (operand_entry_pool); 1487169689Skan free (bb_rank); 1488169689Skan VEC_free (tree, heap, broken_up_subtracts); 1489169689Skan free_dominance_info (CDI_POST_DOMINATORS); 1490169689Skan} 1491169689Skan 1492169689Skan/* Gate and execute functions for Reassociation. */ 1493169689Skan 1494169689Skanstatic unsigned int 1495169689Skanexecute_reassoc (void) 1496169689Skan{ 1497169689Skan init_reassoc (); 1498169689Skan 1499169689Skan do_reassoc (); 1500169689Skan repropagate_negates (); 1501169689Skan 1502169689Skan fini_reassoc (); 1503169689Skan return 0; 1504169689Skan} 1505169689Skan 1506169689Skanstruct tree_opt_pass pass_reassoc = 1507169689Skan{ 1508169689Skan "reassoc", /* name */ 1509169689Skan NULL, /* gate */ 1510169689Skan execute_reassoc, /* execute */ 1511169689Skan NULL, /* sub */ 1512169689Skan NULL, /* next */ 1513169689Skan 0, /* static_pass_number */ 1514169689Skan TV_TREE_REASSOC, /* tv_id */ 1515169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1516169689Skan 0, /* properties_provided */ 1517169689Skan 0, /* properties_destroyed */ 1518169689Skan 0, /* todo_flags_start */ 1519169689Skan TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ 1520169689Skan 0 /* letter */ 1521169689Skan}; 1522