From f378ebf14df0952eae870c9865bab8326aa8f137 Mon Sep 17 00:00:00 2001 From: Dan Albert Date: Wed, 17 Jun 2015 11:09:54 -0700 Subject: Delete old versions of GCC. Change-Id: I710f125d905290e1024cbd67f48299861790c66c --- gcc-4.4.0/gcc/tree-predcom.c | 2672 ------------------------------------------ 1 file changed, 2672 deletions(-) delete mode 100644 gcc-4.4.0/gcc/tree-predcom.c (limited to 'gcc-4.4.0/gcc/tree-predcom.c') diff --git a/gcc-4.4.0/gcc/tree-predcom.c b/gcc-4.4.0/gcc/tree-predcom.c deleted file mode 100644 index 3d31423f7..000000000 --- a/gcc-4.4.0/gcc/tree-predcom.c +++ /dev/null @@ -1,2672 +0,0 @@ -/* Predictive commoning. - Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc. - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify it -under the terms of the GNU General Public License as published by the -Free Software Foundation; either version 3, or (at your option) any -later version. - -GCC is distributed in the hope that it will be useful, but WITHOUT -ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or -FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -. */ - -/* This file implements the predictive commoning optimization. Predictive - commoning can be viewed as CSE around a loop, and with some improvements, - as generalized strength reduction-- i.e., reusing values computed in - earlier iterations of a loop in the later ones. So far, the pass only - handles the most useful case, that is, reusing values of memory references. - If you think this is all just a special case of PRE, you are sort of right; - however, concentrating on loops is simpler, and makes it possible to - incorporate data dependence analysis to detect the opportunities, perform - loop unrolling to avoid copies together with renaming immediately, - and if needed, we could also take register pressure into account. - - Let us demonstrate what is done on an example: - - for (i = 0; i < 100; i++) - { - a[i+2] = a[i] + a[i+1]; - b[10] = b[10] + i; - c[i] = c[99 - i]; - d[i] = d[i + 1]; - } - - 1) We find data references in the loop, and split them to mutually - independent groups (i.e., we find components of a data dependence - graph). We ignore read-read dependences whose distance is not constant. - (TODO -- we could also ignore antidependences). In this example, we - find the following groups: - - a[i]{read}, a[i+1]{read}, a[i+2]{write} - b[10]{read}, b[10]{write} - c[99 - i]{read}, c[i]{write} - d[i + 1]{read}, d[i]{write} - - 2) Inside each of the group, we verify several conditions: - a) all the references must differ in indices only, and the indices - must all have the same step - b) the references must dominate loop latch (and thus, they must be - ordered by dominance relation). - c) the distance of the indices must be a small multiple of the step - We are then able to compute the difference of the references (# of - iterations before they point to the same place as the first of them). - Also, in case there are writes in the loop, we split the groups into - chains whose head is the write whose values are used by the reads in - the same chain. The chains are then processed independently, - making the further transformations simpler. Also, the shorter chains - need the same number of registers, but may require lower unrolling - factor in order to get rid of the copies on the loop latch. - - In our example, we get the following chains (the chain for c is invalid). - - a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2} - b[10]{read,+0}, b[10]{write,+0} - d[i + 1]{read,+0}, d[i]{write,+1} - - 3) For each read, we determine the read or write whose value it reuses, - together with the distance of this reuse. I.e. we take the last - reference before it with distance 0, or the last of the references - with the smallest positive distance to the read. Then, we remove - the references that are not used in any of these chains, discard the - empty groups, and propagate all the links so that they point to the - single root reference of the chain (adjusting their distance - appropriately). Some extra care needs to be taken for references with - step 0. In our example (the numbers indicate the distance of the - reuse), - - a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*) - b[10] --> (*) 1, b[10] (*) - - 4) The chains are combined together if possible. If the corresponding - elements of two chains are always combined together with the same - operator, we remember just the result of this combination, instead - of remembering the values separately. We may need to perform - reassociation to enable combining, for example - - e[i] + f[i+1] + e[i+1] + f[i] - - can be reassociated as - - (e[i] + f[i]) + (e[i+1] + f[i+1]) - - and we can combine the chains for e and f into one chain. - - 5) For each root reference (end of the chain) R, let N be maximum distance - of a reference reusing its value. Variables R0 upto RN are created, - together with phi nodes that transfer values from R1 .. RN to - R0 .. R(N-1). - Initial values are loaded to R0..R(N-1) (in case not all references - must necessarily be accessed and they may trap, we may fail here; - TODO sometimes, the loads could be guarded by a check for the number - of iterations). Values loaded/stored in roots are also copied to - RN. Other reads are replaced with the appropriate variable Ri. - Everything is put to SSA form. - - As a small improvement, if R0 is dead after the root (i.e., all uses of - the value with the maximum distance dominate the root), we can avoid - creating RN and use R0 instead of it. - - In our example, we get (only the parts concerning a and b are shown): - for (i = 0; i < 100; i++) - { - f = phi (a[0], s); - s = phi (a[1], f); - x = phi (b[10], x); - - f = f + s; - a[i+2] = f; - x = x + i; - b[10] = x; - } - - 6) Factor F for unrolling is determined as the smallest common multiple of - (N + 1) for each root reference (N for references for that we avoided - creating RN). If F and the loop is small enough, loop is unrolled F - times. The stores to RN (R0) in the copies of the loop body are - periodically replaced with R0, R1, ... (R1, R2, ...), so that they can - be coalesced and the copies can be eliminated. - - TODO -- copy propagation and other optimizations may change the live - ranges of the temporary registers and prevent them from being coalesced; - this may increase the register pressure. - - In our case, F = 2 and the (main loop of the) result is - - for (i = 0; i < ...; i += 2) - { - f = phi (a[0], f); - s = phi (a[1], s); - x = phi (b[10], x); - - f = f + s; - a[i+2] = f; - x = x + i; - b[10] = x; - - s = s + f; - a[i+3] = s; - x = x + i; - b[10] = x; - } - - TODO -- stores killing other stores can be taken into account, e.g., - for (i = 0; i < n; i++) - { - a[i] = 1; - a[i+2] = 2; - } - - can be replaced with - - t0 = a[0]; - t1 = a[1]; - for (i = 0; i < n; i++) - { - a[i] = 1; - t2 = 2; - t0 = t1; - t1 = t2; - } - a[n] = t0; - a[n+1] = t1; - - The interesting part is that this would generalize store motion; still, since - sm is performed elsewhere, it does not seem that important. - - Predictive commoning can be generalized for arbitrary computations (not - just memory loads), and also nontrivial transfer functions (e.g., replacing - i * i with ii_last + 2 * i + 1), to generalize strength reduction. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "tm.h" -#include "tree.h" -#include "tm_p.h" -#include "cfgloop.h" -#include "tree-flow.h" -#include "ggc.h" -#include "tree-data-ref.h" -#include "tree-scalar-evolution.h" -#include "tree-chrec.h" -#include "params.h" -#include "diagnostic.h" -#include "tree-pass.h" -#include "tree-affine.h" -#include "tree-inline.h" - -/* The maximum number of iterations between the considered memory - references. */ - -#define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8) - -/* Data references (or phi nodes that carry data reference values across - loop iterations). */ - -typedef struct dref -{ - /* The reference itself. */ - struct data_reference *ref; - - /* The statement in that the reference appears. */ - gimple stmt; - - /* In case that STMT is a phi node, this field is set to the SSA name - defined by it in replace_phis_by_defined_names (in order to avoid - pointing to phi node that got reallocated in the meantime). */ - tree name_defined_by_phi; - - /* Distance of the reference from the root of the chain (in number of - iterations of the loop). */ - unsigned distance; - - /* Number of iterations offset from the first reference in the component. */ - double_int offset; - - /* Number of the reference in a component, in dominance ordering. */ - unsigned pos; - - /* True if the memory reference is always accessed when the loop is - entered. */ - unsigned always_accessed : 1; -} *dref; - -DEF_VEC_P (dref); -DEF_VEC_ALLOC_P (dref, heap); - -/* Type of the chain of the references. */ - -enum chain_type -{ - /* The addresses of the references in the chain are constant. */ - CT_INVARIANT, - - /* There are only loads in the chain. */ - CT_LOAD, - - /* Root of the chain is store, the rest are loads. */ - CT_STORE_LOAD, - - /* A combination of two chains. */ - CT_COMBINATION -}; - -/* Chains of data references. */ - -typedef struct chain -{ - /* Type of the chain. */ - enum chain_type type; - - /* For combination chains, the operator and the two chains that are - combined, and the type of the result. */ - enum tree_code op; - tree rslt_type; - struct chain *ch1, *ch2; - - /* The references in the chain. */ - VEC(dref,heap) *refs; - - /* The maximum distance of the reference in the chain from the root. */ - unsigned length; - - /* The variables used to copy the value throughout iterations. */ - VEC(tree,heap) *vars; - - /* Initializers for the variables. */ - VEC(tree,heap) *inits; - - /* True if there is a use of a variable with the maximal distance - that comes after the root in the loop. */ - unsigned has_max_use_after : 1; - - /* True if all the memory references in the chain are always accessed. */ - unsigned all_always_accessed : 1; - - /* True if this chain was combined together with some other chain. */ - unsigned combined : 1; -} *chain_p; - -DEF_VEC_P (chain_p); -DEF_VEC_ALLOC_P (chain_p, heap); - -/* Describes the knowledge about the step of the memory references in - the component. */ - -enum ref_step_type -{ - /* The step is zero. */ - RS_INVARIANT, - - /* The step is nonzero. */ - RS_NONZERO, - - /* The step may or may not be nonzero. */ - RS_ANY -}; - -/* Components of the data dependence graph. */ - -struct component -{ - /* The references in the component. */ - VEC(dref,heap) *refs; - - /* What we know about the step of the references in the component. */ - enum ref_step_type comp_step; - - /* Next component in the list. */ - struct component *next; -}; - -/* Bitmap of ssa names defined by looparound phi nodes covered by chains. */ - -static bitmap looparound_phis; - -/* Cache used by tree_to_aff_combination_expand. */ - -static struct pointer_map_t *name_expansions; - -/* Dumps data reference REF to FILE. */ - -extern void dump_dref (FILE *, dref); -void -dump_dref (FILE *file, dref ref) -{ - if (ref->ref) - { - fprintf (file, " "); - print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM); - fprintf (file, " (id %u%s)\n", ref->pos, - DR_IS_READ (ref->ref) ? "" : ", write"); - - fprintf (file, " offset "); - dump_double_int (file, ref->offset, false); - fprintf (file, "\n"); - - fprintf (file, " distance %u\n", ref->distance); - } - else - { - if (gimple_code (ref->stmt) == GIMPLE_PHI) - fprintf (file, " looparound ref\n"); - else - fprintf (file, " combination ref\n"); - fprintf (file, " in statement "); - print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM); - fprintf (file, "\n"); - fprintf (file, " distance %u\n", ref->distance); - } - -} - -/* Dumps CHAIN to FILE. */ - -extern void dump_chain (FILE *, chain_p); -void -dump_chain (FILE *file, chain_p chain) -{ - dref a; - const char *chain_type; - unsigned i; - tree var; - - switch (chain->type) - { - case CT_INVARIANT: - chain_type = "Load motion"; - break; - - case CT_LOAD: - chain_type = "Loads-only"; - break; - - case CT_STORE_LOAD: - chain_type = "Store-loads"; - break; - - case CT_COMBINATION: - chain_type = "Combination"; - break; - - default: - gcc_unreachable (); - } - - fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain, - chain->combined ? " (combined)" : ""); - if (chain->type != CT_INVARIANT) - fprintf (file, " max distance %u%s\n", chain->length, - chain->has_max_use_after ? "" : ", may reuse first"); - - if (chain->type == CT_COMBINATION) - { - fprintf (file, " equal to %p %s %p in type ", - (void *) chain->ch1, op_symbol_code (chain->op), - (void *) chain->ch2); - print_generic_expr (file, chain->rslt_type, TDF_SLIM); - fprintf (file, "\n"); - } - - if (chain->vars) - { - fprintf (file, " vars"); - for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++) - { - fprintf (file, " "); - print_generic_expr (file, var, TDF_SLIM); - } - fprintf (file, "\n"); - } - - if (chain->inits) - { - fprintf (file, " inits"); - for (i = 0; VEC_iterate (tree, chain->inits, i, var); i++) - { - fprintf (file, " "); - print_generic_expr (file, var, TDF_SLIM); - } - fprintf (file, "\n"); - } - - fprintf (file, " references:\n"); - for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++) - dump_dref (file, a); - - fprintf (file, "\n"); -} - -/* Dumps CHAINS to FILE. */ - -extern void dump_chains (FILE *, VEC (chain_p, heap) *); -void -dump_chains (FILE *file, VEC (chain_p, heap) *chains) -{ - chain_p chain; - unsigned i; - - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) - dump_chain (file, chain); -} - -/* Dumps COMP to FILE. */ - -extern void dump_component (FILE *, struct component *); -void -dump_component (FILE *file, struct component *comp) -{ - dref a; - unsigned i; - - fprintf (file, "Component%s:\n", - comp->comp_step == RS_INVARIANT ? " (invariant)" : ""); - for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++) - dump_dref (file, a); - fprintf (file, "\n"); -} - -/* Dumps COMPS to FILE. */ - -extern void dump_components (FILE *, struct component *); -void -dump_components (FILE *file, struct component *comps) -{ - struct component *comp; - - for (comp = comps; comp; comp = comp->next) - dump_component (file, comp); -} - -/* Frees a chain CHAIN. */ - -static void -release_chain (chain_p chain) -{ - dref ref; - unsigned i; - - if (chain == NULL) - return; - - for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++) - free (ref); - - VEC_free (dref, heap, chain->refs); - VEC_free (tree, heap, chain->vars); - VEC_free (tree, heap, chain->inits); - - free (chain); -} - -/* Frees CHAINS. */ - -static void -release_chains (VEC (chain_p, heap) *chains) -{ - unsigned i; - chain_p chain; - - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) - release_chain (chain); - VEC_free (chain_p, heap, chains); -} - -/* Frees a component COMP. */ - -static void -release_component (struct component *comp) -{ - VEC_free (dref, heap, comp->refs); - free (comp); -} - -/* Frees list of components COMPS. */ - -static void -release_components (struct component *comps) -{ - struct component *act, *next; - - for (act = comps; act; act = next) - { - next = act->next; - release_component (act); - } -} - -/* Finds a root of tree given by FATHERS containing A, and performs path - shortening. */ - -static unsigned -component_of (unsigned fathers[], unsigned a) -{ - unsigned root, n; - - for (root = a; root != fathers[root]; root = fathers[root]) - continue; - - for (; a != root; a = n) - { - n = fathers[a]; - fathers[a] = root; - } - - return root; -} - -/* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the - components, A and B are components to merge. */ - -static void -merge_comps (unsigned fathers[], unsigned sizes[], unsigned a, unsigned b) -{ - unsigned ca = component_of (fathers, a); - unsigned cb = component_of (fathers, b); - - if (ca == cb) - return; - - if (sizes[ca] < sizes[cb]) - { - sizes[cb] += sizes[ca]; - fathers[ca] = cb; - } - else - { - sizes[ca] += sizes[cb]; - fathers[cb] = ca; - } -} - -/* Returns true if A is a reference that is suitable for predictive commoning - in the innermost loop that contains it. REF_STEP is set according to the - step of the reference A. */ - -static bool -suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step) -{ - tree ref = DR_REF (a), step = DR_STEP (a); - - if (!step - || !is_gimple_reg_type (TREE_TYPE (ref)) - || tree_could_throw_p (ref)) - return false; - - if (integer_zerop (step)) - *ref_step = RS_INVARIANT; - else if (integer_nonzerop (step)) - *ref_step = RS_NONZERO; - else - *ref_step = RS_ANY; - - return true; -} - -/* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */ - -static void -aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset) -{ - aff_tree delta; - - tree_to_aff_combination_expand (DR_OFFSET (dr), sizetype, offset, - &name_expansions); - aff_combination_const (&delta, sizetype, tree_to_double_int (DR_INIT (dr))); - aff_combination_add (offset, &delta); -} - -/* Determines number of iterations of the innermost enclosing loop before B - refers to exactly the same location as A and stores it to OFF. If A and - B do not have the same step, they never meet, or anything else fails, - returns false, otherwise returns true. Both A and B are assumed to - satisfy suitable_reference_p. */ - -static bool -determine_offset (struct data_reference *a, struct data_reference *b, - double_int *off) -{ - aff_tree diff, baseb, step; - tree typea, typeb; - - /* Check that both the references access the location in the same type. */ - typea = TREE_TYPE (DR_REF (a)); - typeb = TREE_TYPE (DR_REF (b)); - if (!useless_type_conversion_p (typeb, typea)) - return false; - - /* Check whether the base address and the step of both references is the - same. */ - if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0) - || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0)) - return false; - - if (integer_zerop (DR_STEP (a))) - { - /* If the references have loop invariant address, check that they access - exactly the same location. */ - *off = double_int_zero; - return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0) - && operand_equal_p (DR_INIT (a), DR_INIT (b), 0)); - } - - /* Compare the offsets of the addresses, and check whether the difference - is a multiple of step. */ - aff_combination_dr_offset (a, &diff); - aff_combination_dr_offset (b, &baseb); - aff_combination_scale (&baseb, double_int_minus_one); - aff_combination_add (&diff, &baseb); - - tree_to_aff_combination_expand (DR_STEP (a), sizetype, - &step, &name_expansions); - return aff_combination_constant_multiple_p (&diff, &step, off); -} - -/* Returns the last basic block in LOOP for that we are sure that - it is executed whenever the loop is entered. */ - -static basic_block -last_always_executed_block (struct loop *loop) -{ - unsigned i; - VEC (edge, heap) *exits = get_loop_exit_edges (loop); - edge ex; - basic_block last = loop->latch; - - for (i = 0; VEC_iterate (edge, exits, i, ex); i++) - last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src); - VEC_free (edge, heap, exits); - - return last; -} - -/* Splits dependence graph on DATAREFS described by DEPENDS to components. */ - -static struct component * -split_data_refs_to_components (struct loop *loop, - VEC (data_reference_p, heap) *datarefs, - VEC (ddr_p, heap) *depends) -{ - unsigned i, n = VEC_length (data_reference_p, datarefs); - unsigned ca, ia, ib, bad; - unsigned *comp_father = XNEWVEC (unsigned, n + 1); - unsigned *comp_size = XNEWVEC (unsigned, n + 1); - struct component **comps; - struct data_reference *dr, *dra, *drb; - struct data_dependence_relation *ddr; - struct component *comp_list = NULL, *comp; - dref dataref; - basic_block last_always_executed = last_always_executed_block (loop); - - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) - { - if (!DR_REF (dr)) - { - /* A fake reference for call or asm_expr that may clobber memory; - just fail. */ - goto end; - } - dr->aux = (void *) (size_t) i; - comp_father[i] = i; - comp_size[i] = 1; - } - - /* A component reserved for the "bad" data references. */ - comp_father[n] = n; - comp_size[n] = 1; - - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) - { - enum ref_step_type dummy; - - if (!suitable_reference_p (dr, &dummy)) - { - ia = (unsigned) (size_t) dr->aux; - merge_comps (comp_father, comp_size, n, ia); - } - } - - for (i = 0; VEC_iterate (ddr_p, depends, i, ddr); i++) - { - double_int dummy_off; - - if (DDR_ARE_DEPENDENT (ddr) == chrec_known) - continue; - - dra = DDR_A (ddr); - drb = DDR_B (ddr); - ia = component_of (comp_father, (unsigned) (size_t) dra->aux); - ib = component_of (comp_father, (unsigned) (size_t) drb->aux); - if (ia == ib) - continue; - - bad = component_of (comp_father, n); - - /* If both A and B are reads, we may ignore unsuitable dependences. */ - if (DR_IS_READ (dra) && DR_IS_READ (drb) - && (ia == bad || ib == bad - || !determine_offset (dra, drb, &dummy_off))) - continue; - - merge_comps (comp_father, comp_size, ia, ib); - } - - comps = XCNEWVEC (struct component *, n); - bad = component_of (comp_father, n); - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) - { - ia = (unsigned) (size_t) dr->aux; - ca = component_of (comp_father, ia); - if (ca == bad) - continue; - - comp = comps[ca]; - if (!comp) - { - comp = XCNEW (struct component); - comp->refs = VEC_alloc (dref, heap, comp_size[ca]); - comps[ca] = comp; - } - - dataref = XCNEW (struct dref); - dataref->ref = dr; - dataref->stmt = DR_STMT (dr); - dataref->offset = double_int_zero; - dataref->distance = 0; - - dataref->always_accessed - = dominated_by_p (CDI_DOMINATORS, last_always_executed, - gimple_bb (dataref->stmt)); - dataref->pos = VEC_length (dref, comp->refs); - VEC_quick_push (dref, comp->refs, dataref); - } - - for (i = 0; i < n; i++) - { - comp = comps[i]; - if (comp) - { - comp->next = comp_list; - comp_list = comp; - } - } - free (comps); - -end: - free (comp_father); - free (comp_size); - return comp_list; -} - -/* Returns true if the component COMP satisfies the conditions - described in 2) at the beginning of this file. LOOP is the current - loop. */ - -static bool -suitable_component_p (struct loop *loop, struct component *comp) -{ - unsigned i; - dref a, first; - basic_block ba, bp = loop->header; - bool ok, has_write = false; - - for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++) - { - ba = gimple_bb (a->stmt); - - if (!just_once_each_iteration_p (loop, ba)) - return false; - - gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp)); - bp = ba; - - if (!DR_IS_READ (a->ref)) - has_write = true; - } - - first = VEC_index (dref, comp->refs, 0); - ok = suitable_reference_p (first->ref, &comp->comp_step); - gcc_assert (ok); - first->offset = double_int_zero; - - for (i = 1; VEC_iterate (dref, comp->refs, i, a); i++) - { - if (!determine_offset (first->ref, a->ref, &a->offset)) - return false; - -#ifdef ENABLE_CHECKING - { - enum ref_step_type a_step; - ok = suitable_reference_p (a->ref, &a_step); - gcc_assert (ok && a_step == comp->comp_step); - } -#endif - } - - /* If there is a write inside the component, we must know whether the - step is nonzero or not -- we would not otherwise be able to recognize - whether the value accessed by reads comes from the OFFSET-th iteration - or the previous one. */ - if (has_write && comp->comp_step == RS_ANY) - return false; - - return true; -} - -/* Check the conditions on references inside each of components COMPS, - and remove the unsuitable components from the list. The new list - of components is returned. The conditions are described in 2) at - the beginning of this file. LOOP is the current loop. */ - -static struct component * -filter_suitable_components (struct loop *loop, struct component *comps) -{ - struct component **comp, *act; - - for (comp = &comps; *comp; ) - { - act = *comp; - if (suitable_component_p (loop, act)) - comp = &act->next; - else - { - dref ref; - unsigned i; - - *comp = act->next; - for (i = 0; VEC_iterate (dref, act->refs, i, ref); i++) - free (ref); - release_component (act); - } - } - - return comps; -} - -/* Compares two drefs A and B by their offset and position. Callback for - qsort. */ - -static int -order_drefs (const void *a, const void *b) -{ - const dref *const da = (const dref *) a; - const dref *const db = (const dref *) b; - int offcmp = double_int_scmp ((*da)->offset, (*db)->offset); - - if (offcmp != 0) - return offcmp; - - return (*da)->pos - (*db)->pos; -} - -/* Returns root of the CHAIN. */ - -static inline dref -get_chain_root (chain_p chain) -{ - return VEC_index (dref, chain->refs, 0); -} - -/* Adds REF to the chain CHAIN. */ - -static void -add_ref_to_chain (chain_p chain, dref ref) -{ - dref root = get_chain_root (chain); - double_int dist; - - gcc_assert (double_int_scmp (root->offset, ref->offset) <= 0); - dist = double_int_add (ref->offset, double_int_neg (root->offset)); - if (double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE), dist) <= 0) - { - free (ref); - return; - } - gcc_assert (double_int_fits_in_uhwi_p (dist)); - - VEC_safe_push (dref, heap, chain->refs, ref); - - ref->distance = double_int_to_uhwi (dist); - - if (ref->distance >= chain->length) - { - chain->length = ref->distance; - chain->has_max_use_after = false; - } - - if (ref->distance == chain->length - && ref->pos > root->pos) - chain->has_max_use_after = true; - - chain->all_always_accessed &= ref->always_accessed; -} - -/* Returns the chain for invariant component COMP. */ - -static chain_p -make_invariant_chain (struct component *comp) -{ - chain_p chain = XCNEW (struct chain); - unsigned i; - dref ref; - - chain->type = CT_INVARIANT; - - chain->all_always_accessed = true; - - for (i = 0; VEC_iterate (dref, comp->refs, i, ref); i++) - { - VEC_safe_push (dref, heap, chain->refs, ref); - chain->all_always_accessed &= ref->always_accessed; - } - - return chain; -} - -/* Make a new chain rooted at REF. */ - -static chain_p -make_rooted_chain (dref ref) -{ - chain_p chain = XCNEW (struct chain); - - chain->type = DR_IS_READ (ref->ref) ? CT_LOAD : CT_STORE_LOAD; - - VEC_safe_push (dref, heap, chain->refs, ref); - chain->all_always_accessed = ref->always_accessed; - - ref->distance = 0; - - return chain; -} - -/* Returns true if CHAIN is not trivial. */ - -static bool -nontrivial_chain_p (chain_p chain) -{ - return chain != NULL && VEC_length (dref, chain->refs) > 1; -} - -/* Returns the ssa name that contains the value of REF, or NULL_TREE if there - is no such name. */ - -static tree -name_for_ref (dref ref) -{ - tree name; - - if (is_gimple_assign (ref->stmt)) - { - if (!ref->ref || DR_IS_READ (ref->ref)) - name = gimple_assign_lhs (ref->stmt); - else - name = gimple_assign_rhs1 (ref->stmt); - } - else - name = PHI_RESULT (ref->stmt); - - return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE); -} - -/* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in - iterations of the innermost enclosing loop). */ - -static bool -valid_initializer_p (struct data_reference *ref, - unsigned distance, struct data_reference *root) -{ - aff_tree diff, base, step; - double_int off; - - /* Both REF and ROOT must be accessing the same object. */ - if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0)) - return false; - - /* The initializer is defined outside of loop, hence its address must be - invariant inside the loop. */ - gcc_assert (integer_zerop (DR_STEP (ref))); - - /* If the address of the reference is invariant, initializer must access - exactly the same location. */ - if (integer_zerop (DR_STEP (root))) - return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0) - && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0)); - - /* Verify that this index of REF is equal to the root's index at - -DISTANCE-th iteration. */ - aff_combination_dr_offset (root, &diff); - aff_combination_dr_offset (ref, &base); - aff_combination_scale (&base, double_int_minus_one); - aff_combination_add (&diff, &base); - - tree_to_aff_combination_expand (DR_STEP (root), sizetype, &step, - &name_expansions); - if (!aff_combination_constant_multiple_p (&diff, &step, &off)) - return false; - - if (!double_int_equal_p (off, uhwi_to_double_int (distance))) - return false; - - return true; -} - -/* Finds looparound phi node of LOOP that copies the value of REF, and if its - initial value is correct (equal to initial value of REF shifted by one - iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT - is the root of the current chain. */ - -static gimple -find_looparound_phi (struct loop *loop, dref ref, dref root) -{ - tree name, init, init_ref; - gimple phi = NULL, init_stmt; - edge latch = loop_latch_edge (loop); - struct data_reference init_dr; - gimple_stmt_iterator psi; - - if (is_gimple_assign (ref->stmt)) - { - if (DR_IS_READ (ref->ref)) - name = gimple_assign_lhs (ref->stmt); - else - name = gimple_assign_rhs1 (ref->stmt); - } - else - name = PHI_RESULT (ref->stmt); - if (!name) - return NULL; - - for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) - { - phi = gsi_stmt (psi); - if (PHI_ARG_DEF_FROM_EDGE (phi, latch) == name) - break; - } - - if (gsi_end_p (psi)) - return NULL; - - init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); - if (TREE_CODE (init) != SSA_NAME) - return NULL; - init_stmt = SSA_NAME_DEF_STMT (init); - if (gimple_code (init_stmt) != GIMPLE_ASSIGN) - return NULL; - gcc_assert (gimple_assign_lhs (init_stmt) == init); - - init_ref = gimple_assign_rhs1 (init_stmt); - if (!REFERENCE_CLASS_P (init_ref) - && !DECL_P (init_ref)) - return NULL; - - /* Analyze the behavior of INIT_REF with respect to LOOP (innermost - loop enclosing PHI). */ - memset (&init_dr, 0, sizeof (struct data_reference)); - DR_REF (&init_dr) = init_ref; - DR_STMT (&init_dr) = phi; - if (!dr_analyze_innermost (&init_dr)) - return NULL; - - if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref)) - return NULL; - - return phi; -} - -/* Adds a reference for the looparound copy of REF in PHI to CHAIN. */ - -static void -insert_looparound_copy (chain_p chain, dref ref, gimple phi) -{ - dref nw = XCNEW (struct dref), aref; - unsigned i; - - nw->stmt = phi; - nw->distance = ref->distance + 1; - nw->always_accessed = 1; - - for (i = 0; VEC_iterate (dref, chain->refs, i, aref); i++) - if (aref->distance >= nw->distance) - break; - VEC_safe_insert (dref, heap, chain->refs, i, nw); - - if (nw->distance > chain->length) - { - chain->length = nw->distance; - chain->has_max_use_after = false; - } -} - -/* For references in CHAIN that are copied around the LOOP (created previously - by PRE, or by user), add the results of such copies to the chain. This - enables us to remove the copies by unrolling, and may need less registers - (also, it may allow us to combine chains together). */ - -static void -add_looparound_copies (struct loop *loop, chain_p chain) -{ - unsigned i; - dref ref, root = get_chain_root (chain); - gimple phi; - - for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++) - { - phi = find_looparound_phi (loop, ref, root); - if (!phi) - continue; - - bitmap_set_bit (looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi))); - insert_looparound_copy (chain, ref, phi); - } -} - -/* Find roots of the values and determine distances in the component COMP. - The references are redistributed into CHAINS. LOOP is the current - loop. */ - -static void -determine_roots_comp (struct loop *loop, - struct component *comp, - VEC (chain_p, heap) **chains) -{ - unsigned i; - dref a; - chain_p chain = NULL; - - /* Invariants are handled specially. */ - if (comp->comp_step == RS_INVARIANT) - { - chain = make_invariant_chain (comp); - VEC_safe_push (chain_p, heap, *chains, chain); - return; - } - - qsort (VEC_address (dref, comp->refs), VEC_length (dref, comp->refs), - sizeof (dref), order_drefs); - - for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++) - { - if (!chain || !DR_IS_READ (a->ref)) - { - if (nontrivial_chain_p (chain)) - VEC_safe_push (chain_p, heap, *chains, chain); - else - release_chain (chain); - chain = make_rooted_chain (a); - continue; - } - - add_ref_to_chain (chain, a); - } - - if (nontrivial_chain_p (chain)) - { - add_looparound_copies (loop, chain); - VEC_safe_push (chain_p, heap, *chains, chain); - } - else - release_chain (chain); -} - -/* Find roots of the values and determine distances in components COMPS, and - separates the references to CHAINS. LOOP is the current loop. */ - -static void -determine_roots (struct loop *loop, - struct component *comps, VEC (chain_p, heap) **chains) -{ - struct component *comp; - - for (comp = comps; comp; comp = comp->next) - determine_roots_comp (loop, comp, chains); -} - -/* Replace the reference in statement STMT with temporary variable - NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of - the reference in the statement. IN_LHS is true if the reference - is in the lhs of STMT, false if it is in rhs. */ - -static void -replace_ref_with (gimple stmt, tree new_tree, bool set, bool in_lhs) -{ - tree val; - gimple new_stmt; - gimple_stmt_iterator bsi, psi; - - if (gimple_code (stmt) == GIMPLE_PHI) - { - gcc_assert (!in_lhs && !set); - - val = PHI_RESULT (stmt); - bsi = gsi_after_labels (gimple_bb (stmt)); - psi = gsi_for_stmt (stmt); - remove_phi_node (&psi, false); - - /* Turn the phi node into GIMPLE_ASSIGN. */ - new_stmt = gimple_build_assign (val, new_tree); - gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT); - return; - } - - /* Since the reference is of gimple_reg type, it should only - appear as lhs or rhs of modify statement. */ - gcc_assert (is_gimple_assign (stmt)); - - bsi = gsi_for_stmt (stmt); - - /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */ - if (!set) - { - gcc_assert (!in_lhs); - gimple_assign_set_rhs_from_tree (&bsi, new_tree); - stmt = gsi_stmt (bsi); - update_stmt (stmt); - return; - } - - if (in_lhs) - { - /* We have statement - - OLD = VAL - - If OLD is a memory reference, then VAL is gimple_val, and we transform - this to - - OLD = VAL - NEW = VAL - - Otherwise, we are replacing a combination chain, - VAL is the expression that performs the combination, and OLD is an - SSA name. In this case, we transform the assignment to - - OLD = VAL - NEW = OLD - - */ - - val = gimple_assign_lhs (stmt); - if (TREE_CODE (val) != SSA_NAME) - { - gcc_assert (gimple_assign_copy_p (stmt)); - val = gimple_assign_rhs1 (stmt); - } - } - else - { - /* VAL = OLD - - is transformed to - - VAL = OLD - NEW = VAL */ - - val = gimple_assign_lhs (stmt); - } - - new_stmt = gimple_build_assign (new_tree, unshare_expr (val)); - gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT); -} - -/* Returns the reference to the address of REF in the ITER-th iteration of - LOOP, or NULL if we fail to determine it (ITER may be negative). We - try to preserve the original shape of the reference (not rewrite it - as an indirect ref to the address), to make tree_could_trap_p in - prepare_initializers_chain return false more often. */ - -static tree -ref_at_iteration (struct loop *loop, tree ref, int iter) -{ - tree idx, *idx_p, type, val, op0 = NULL_TREE, ret; - affine_iv iv; - bool ok; - - if (handled_component_p (ref)) - { - op0 = ref_at_iteration (loop, TREE_OPERAND (ref, 0), iter); - if (!op0) - return NULL_TREE; - } - else if (!INDIRECT_REF_P (ref)) - return unshare_expr (ref); - - if (TREE_CODE (ref) == INDIRECT_REF) - { - ret = build1 (INDIRECT_REF, TREE_TYPE (ref), NULL_TREE); - idx = TREE_OPERAND (ref, 0); - idx_p = &TREE_OPERAND (ret, 0); - } - else if (TREE_CODE (ref) == COMPONENT_REF) - { - /* Check that the offset is loop invariant. */ - if (TREE_OPERAND (ref, 2) - && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2))) - return NULL_TREE; - - return build3 (COMPONENT_REF, TREE_TYPE (ref), op0, - unshare_expr (TREE_OPERAND (ref, 1)), - unshare_expr (TREE_OPERAND (ref, 2))); - } - else if (TREE_CODE (ref) == ARRAY_REF) - { - /* Check that the lower bound and the step are loop invariant. */ - if (TREE_OPERAND (ref, 2) - && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2))) - return NULL_TREE; - if (TREE_OPERAND (ref, 3) - && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 3))) - return NULL_TREE; - - ret = build4 (ARRAY_REF, TREE_TYPE (ref), op0, NULL_TREE, - unshare_expr (TREE_OPERAND (ref, 2)), - unshare_expr (TREE_OPERAND (ref, 3))); - idx = TREE_OPERAND (ref, 1); - idx_p = &TREE_OPERAND (ret, 1); - } - else - return NULL_TREE; - - ok = simple_iv (loop, loop, idx, &iv, true); - if (!ok) - return NULL_TREE; - iv.base = expand_simple_operations (iv.base); - if (integer_zerop (iv.step)) - *idx_p = unshare_expr (iv.base); - else - { - type = TREE_TYPE (iv.base); - if (POINTER_TYPE_P (type)) - { - val = fold_build2 (MULT_EXPR, sizetype, iv.step, - size_int (iter)); - val = fold_build2 (POINTER_PLUS_EXPR, type, iv.base, val); - } - else - { - val = fold_build2 (MULT_EXPR, type, iv.step, - build_int_cst_type (type, iter)); - val = fold_build2 (PLUS_EXPR, type, iv.base, val); - } - *idx_p = unshare_expr (val); - } - - return ret; -} - -/* Get the initialization expression for the INDEX-th temporary variable - of CHAIN. */ - -static tree -get_init_expr (chain_p chain, unsigned index) -{ - if (chain->type == CT_COMBINATION) - { - tree e1 = get_init_expr (chain->ch1, index); - tree e2 = get_init_expr (chain->ch2, index); - - return fold_build2 (chain->op, chain->rslt_type, e1, e2); - } - else - return VEC_index (tree, chain->inits, index); -} - -/* Marks all virtual operands of statement STMT for renaming. */ - -void -mark_virtual_ops_for_renaming (gimple stmt) -{ - ssa_op_iter iter; - tree var; - - if (gimple_code (stmt) == GIMPLE_PHI) - { - var = PHI_RESULT (stmt); - if (is_gimple_reg (var)) - return; - - if (TREE_CODE (var) == SSA_NAME) - var = SSA_NAME_VAR (var); - mark_sym_for_renaming (var); - return; - } - - update_stmt (stmt); - - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_VIRTUALS) - { - if (TREE_CODE (var) == SSA_NAME) - var = SSA_NAME_VAR (var); - mark_sym_for_renaming (var); - } -} - -/* Calls mark_virtual_ops_for_renaming for all members of LIST. */ - -static void -mark_virtual_ops_for_renaming_list (gimple_seq list) -{ - gimple_stmt_iterator gsi; - - for (gsi = gsi_start (list); !gsi_end_p (gsi); gsi_next (&gsi)) - mark_virtual_ops_for_renaming (gsi_stmt (gsi)); -} - -/* Returns a new temporary variable used for the I-th variable carrying - value of REF. The variable's uid is marked in TMP_VARS. */ - -static tree -predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars) -{ - tree type = TREE_TYPE (ref); - tree var = create_tmp_var (type, get_lsm_tmp_name (ref, i)); - - /* We never access the components of the temporary variable in predictive - commoning. */ - if (TREE_CODE (type) == COMPLEX_TYPE - || TREE_CODE (type) == VECTOR_TYPE) - DECL_GIMPLE_REG_P (var) = 1; - - add_referenced_var (var); - bitmap_set_bit (tmp_vars, DECL_UID (var)); - return var; -} - -/* Creates the variables for CHAIN, as well as phi nodes for them and - initialization on entry to LOOP. Uids of the newly created - temporary variables are marked in TMP_VARS. */ - -static void -initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars) -{ - unsigned i; - unsigned n = chain->length; - dref root = get_chain_root (chain); - bool reuse_first = !chain->has_max_use_after; - tree ref, init, var, next; - gimple phi; - gimple_seq stmts; - edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop); - - /* If N == 0, then all the references are within the single iteration. And - since this is an nonempty chain, reuse_first cannot be true. */ - gcc_assert (n > 0 || !reuse_first); - - chain->vars = VEC_alloc (tree, heap, n + 1); - - if (chain->type == CT_COMBINATION) - ref = gimple_assign_lhs (root->stmt); - else - ref = DR_REF (root->ref); - - for (i = 0; i < n + (reuse_first ? 0 : 1); i++) - { - var = predcom_tmp_var (ref, i, tmp_vars); - VEC_quick_push (tree, chain->vars, var); - } - if (reuse_first) - VEC_quick_push (tree, chain->vars, VEC_index (tree, chain->vars, 0)); - - for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++) - VEC_replace (tree, chain->vars, i, make_ssa_name (var, NULL)); - - for (i = 0; i < n; i++) - { - var = VEC_index (tree, chain->vars, i); - next = VEC_index (tree, chain->vars, i + 1); - init = get_init_expr (chain, i); - - init = force_gimple_operand (init, &stmts, true, NULL_TREE); - if (stmts) - { - mark_virtual_ops_for_renaming_list (stmts); - gsi_insert_seq_on_edge_immediate (entry, stmts); - } - - phi = create_phi_node (var, loop->header); - SSA_NAME_DEF_STMT (var) = phi; - add_phi_arg (phi, init, entry, UNKNOWN_LOCATION); - add_phi_arg (phi, next, latch, UNKNOWN_LOCATION); - } -} - -/* Create the variables and initialization statement for root of chain - CHAIN. Uids of the newly created temporary variables are marked - in TMP_VARS. */ - -static void -initialize_root (struct loop *loop, chain_p chain, bitmap tmp_vars) -{ - dref root = get_chain_root (chain); - bool in_lhs = (chain->type == CT_STORE_LOAD - || chain->type == CT_COMBINATION); - - initialize_root_vars (loop, chain, tmp_vars); - replace_ref_with (root->stmt, - VEC_index (tree, chain->vars, chain->length), - true, in_lhs); -} - -/* Initializes a variable for load motion for ROOT and prepares phi nodes and - initialization on entry to LOOP if necessary. The ssa name for the variable - is stored in VARS. If WRITTEN is true, also a phi node to copy its value - around the loop is created. Uid of the newly created temporary variable - is marked in TMP_VARS. INITS is the list containing the (single) - initializer. */ - -static void -initialize_root_vars_lm (struct loop *loop, dref root, bool written, - VEC(tree, heap) **vars, VEC(tree, heap) *inits, - bitmap tmp_vars) -{ - unsigned i; - tree ref = DR_REF (root->ref), init, var, next; - gimple_seq stmts; - gimple phi; - edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop); - - /* Find the initializer for the variable, and check that it cannot - trap. */ - init = VEC_index (tree, inits, 0); - - *vars = VEC_alloc (tree, heap, written ? 2 : 1); - var = predcom_tmp_var (ref, 0, tmp_vars); - VEC_quick_push (tree, *vars, var); - if (written) - VEC_quick_push (tree, *vars, VEC_index (tree, *vars, 0)); - - for (i = 0; VEC_iterate (tree, *vars, i, var); i++) - VEC_replace (tree, *vars, i, make_ssa_name (var, NULL)); - - var = VEC_index (tree, *vars, 0); - - init = force_gimple_operand (init, &stmts, written, NULL_TREE); - if (stmts) - { - mark_virtual_ops_for_renaming_list (stmts); - gsi_insert_seq_on_edge_immediate (entry, stmts); - } - - if (written) - { - next = VEC_index (tree, *vars, 1); - phi = create_phi_node (var, loop->header); - SSA_NAME_DEF_STMT (var) = phi; - add_phi_arg (phi, init, entry, UNKNOWN_LOCATION); - add_phi_arg (phi, next, latch, UNKNOWN_LOCATION); - } - else - { - gimple init_stmt = gimple_build_assign (var, init); - mark_virtual_ops_for_renaming (init_stmt); - gsi_insert_on_edge_immediate (entry, init_stmt); - } -} - - -/* Execute load motion for references in chain CHAIN. Uids of the newly - created temporary variables are marked in TMP_VARS. */ - -static void -execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars) -{ - VEC (tree, heap) *vars; - dref a; - unsigned n_writes = 0, ridx, i; - tree var; - - gcc_assert (chain->type == CT_INVARIANT); - gcc_assert (!chain->combined); - for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++) - if (!DR_IS_READ (a->ref)) - n_writes++; - - /* If there are no reads in the loop, there is nothing to do. */ - if (n_writes == VEC_length (dref, chain->refs)) - return; - - initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0, - &vars, chain->inits, tmp_vars); - - ridx = 0; - for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++) - { - bool is_read = DR_IS_READ (a->ref); - mark_virtual_ops_for_renaming (a->stmt); - - if (!DR_IS_READ (a->ref)) - { - n_writes--; - if (n_writes) - { - var = VEC_index (tree, vars, 0); - var = make_ssa_name (SSA_NAME_VAR (var), NULL); - VEC_replace (tree, vars, 0, var); - } - else - ridx = 1; - } - - replace_ref_with (a->stmt, VEC_index (tree, vars, ridx), - !is_read, !is_read); - } - - VEC_free (tree, heap, vars); -} - -/* Returns the single statement in that NAME is used, excepting - the looparound phi nodes contained in one of the chains. If there is no - such statement, or more statements, NULL is returned. */ - -static gimple -single_nonlooparound_use (tree name) -{ - use_operand_p use; - imm_use_iterator it; - gimple stmt, ret = NULL; - - FOR_EACH_IMM_USE_FAST (use, it, name) - { - stmt = USE_STMT (use); - - if (gimple_code (stmt) == GIMPLE_PHI) - { - /* Ignore uses in looparound phi nodes. Uses in other phi nodes - could not be processed anyway, so just fail for them. */ - if (bitmap_bit_p (looparound_phis, - SSA_NAME_VERSION (PHI_RESULT (stmt)))) - continue; - - return NULL; - } - else if (ret != NULL) - return NULL; - else - ret = stmt; - } - - return ret; -} - -/* Remove statement STMT, as well as the chain of assignments in that it is - used. */ - -static void -remove_stmt (gimple stmt) -{ - tree name; - gimple next; - gimple_stmt_iterator psi; - - if (gimple_code (stmt) == GIMPLE_PHI) - { - name = PHI_RESULT (stmt); - next = single_nonlooparound_use (name); - psi = gsi_for_stmt (stmt); - remove_phi_node (&psi, true); - - if (!next - || !gimple_assign_ssa_name_copy_p (next) - || gimple_assign_rhs1 (next) != name) - return; - - stmt = next; - } - - while (1) - { - gimple_stmt_iterator bsi; - - bsi = gsi_for_stmt (stmt); - - name = gimple_assign_lhs (stmt); - gcc_assert (TREE_CODE (name) == SSA_NAME); - - next = single_nonlooparound_use (name); - - mark_virtual_ops_for_renaming (stmt); - gsi_remove (&bsi, true); - release_defs (stmt); - - if (!next - || !gimple_assign_ssa_name_copy_p (next) - || gimple_assign_rhs1 (next) != name) - return; - - stmt = next; - } -} - -/* Perform the predictive commoning optimization for a chain CHAIN. - Uids of the newly created temporary variables are marked in TMP_VARS.*/ - -static void -execute_pred_commoning_chain (struct loop *loop, chain_p chain, - bitmap tmp_vars) -{ - unsigned i; - dref a, root; - tree var; - - if (chain->combined) - { - /* For combined chains, just remove the statements that are used to - compute the values of the expression (except for the root one). */ - for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++) - remove_stmt (a->stmt); - } - else - { - /* For non-combined chains, set up the variables that hold its value, - and replace the uses of the original references by these - variables. */ - root = get_chain_root (chain); - mark_virtual_ops_for_renaming (root->stmt); - - initialize_root (loop, chain, tmp_vars); - for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++) - { - mark_virtual_ops_for_renaming (a->stmt); - var = VEC_index (tree, chain->vars, chain->length - a->distance); - replace_ref_with (a->stmt, var, false, false); - } - } -} - -/* Determines the unroll factor necessary to remove as many temporary variable - copies as possible. CHAINS is the list of chains that will be - optimized. */ - -static unsigned -determine_unroll_factor (VEC (chain_p, heap) *chains) -{ - chain_p chain; - unsigned factor = 1, af, nfactor, i; - unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES); - - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) - { - if (chain->type == CT_INVARIANT || chain->combined) - continue; - - /* The best unroll factor for this chain is equal to the number of - temporary variables that we create for it. */ - af = chain->length; - if (chain->has_max_use_after) - af++; - - nfactor = factor * af / gcd (factor, af); - if (nfactor <= max) - factor = nfactor; - } - - return factor; -} - -/* Perform the predictive commoning optimization for CHAINS. - Uids of the newly created temporary variables are marked in TMP_VARS. */ - -static void -execute_pred_commoning (struct loop *loop, VEC (chain_p, heap) *chains, - bitmap tmp_vars) -{ - chain_p chain; - unsigned i; - - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) - { - if (chain->type == CT_INVARIANT) - execute_load_motion (loop, chain, tmp_vars); - else - execute_pred_commoning_chain (loop, chain, tmp_vars); - } - - update_ssa (TODO_update_ssa_only_virtuals); -} - -/* For each reference in CHAINS, if its defining statement is - phi node, record the ssa name that is defined by it. */ - -static void -replace_phis_by_defined_names (VEC (chain_p, heap) *chains) -{ - chain_p chain; - dref a; - unsigned i, j; - - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) - for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++) - { - if (gimple_code (a->stmt) == GIMPLE_PHI) - { - a->name_defined_by_phi = PHI_RESULT (a->stmt); - a->stmt = NULL; - } - } -} - -/* For each reference in CHAINS, if name_defined_by_phi is not - NULL, use it to set the stmt field. */ - -static void -replace_names_by_phis (VEC (chain_p, heap) *chains) -{ - chain_p chain; - dref a; - unsigned i, j; - - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) - for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++) - if (a->stmt == NULL) - { - a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi); - gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI); - a->name_defined_by_phi = NULL_TREE; - } -} - -/* Wrapper over execute_pred_commoning, to pass it as a callback - to tree_transform_and_unroll_loop. */ - -struct epcc_data -{ - VEC (chain_p, heap) *chains; - bitmap tmp_vars; -}; - -static void -execute_pred_commoning_cbck (struct loop *loop, void *data) -{ - struct epcc_data *const dta = (struct epcc_data *) data; - - /* Restore phi nodes that were replaced by ssa names before - tree_transform_and_unroll_loop (see detailed description in - tree_predictive_commoning_loop). */ - replace_names_by_phis (dta->chains); - execute_pred_commoning (loop, dta->chains, dta->tmp_vars); -} - -/* Returns true if we can and should unroll LOOP FACTOR times. Number - of iterations of the loop is returned in NITER. */ - -static bool -should_unroll_loop_p (struct loop *loop, unsigned factor, - struct tree_niter_desc *niter) -{ - edge exit; - - if (factor == 1) - return false; - - /* Check whether unrolling is possible. We only want to unroll loops - for that we are able to determine number of iterations. We also - want to split the extra iterations of the loop from its end, - therefore we require that the loop has precisely one - exit. */ - - exit = single_dom_exit (loop); - if (!exit) - return false; - - if (!number_of_iterations_exit (loop, exit, niter, false)) - return false; - - /* And of course, we must be able to duplicate the loop. */ - if (!can_duplicate_loop_p (loop)) - return false; - - /* The final loop should be small enough. */ - if (tree_num_loop_insns (loop, &eni_size_weights) * factor - > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS)) - return false; - - return true; -} - -/* Base NAME and all the names in the chain of phi nodes that use it - on variable VAR. The phi nodes are recognized by being in the copies of - the header of the LOOP. */ - -static void -base_names_in_chain_on (struct loop *loop, tree name, tree var) -{ - gimple stmt, phi; - imm_use_iterator iter; - edge e; - - SSA_NAME_VAR (name) = var; - - while (1) - { - phi = NULL; - FOR_EACH_IMM_USE_STMT (stmt, iter, name) - { - if (gimple_code (stmt) == GIMPLE_PHI - && flow_bb_inside_loop_p (loop, gimple_bb (stmt))) - { - phi = stmt; - BREAK_FROM_IMM_USE_STMT (iter); - } - } - if (!phi) - return; - - if (gimple_bb (phi) == loop->header) - e = loop_latch_edge (loop); - else - e = single_pred_edge (gimple_bb (stmt)); - - name = PHI_RESULT (phi); - SSA_NAME_VAR (name) = var; - } -} - -/* Given an unrolled LOOP after predictive commoning, remove the - register copies arising from phi nodes by changing the base - variables of SSA names. TMP_VARS is the set of the temporary variables - for those we want to perform this. */ - -static void -eliminate_temp_copies (struct loop *loop, bitmap tmp_vars) -{ - edge e; - gimple phi, stmt; - tree name, use, var; - gimple_stmt_iterator psi; - - e = loop_latch_edge (loop); - for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) - { - phi = gsi_stmt (psi); - name = PHI_RESULT (phi); - var = SSA_NAME_VAR (name); - if (!bitmap_bit_p (tmp_vars, DECL_UID (var))) - continue; - use = PHI_ARG_DEF_FROM_EDGE (phi, e); - gcc_assert (TREE_CODE (use) == SSA_NAME); - - /* Base all the ssa names in the ud and du chain of NAME on VAR. */ - stmt = SSA_NAME_DEF_STMT (use); - while (gimple_code (stmt) == GIMPLE_PHI - /* In case we could not unroll the loop enough to eliminate - all copies, we may reach the loop header before the defining - statement (in that case, some register copies will be present - in loop latch in the final code, corresponding to the newly - created looparound phi nodes). */ - && gimple_bb (stmt) != loop->header) - { - gcc_assert (single_pred_p (gimple_bb (stmt))); - use = PHI_ARG_DEF (stmt, 0); - stmt = SSA_NAME_DEF_STMT (use); - } - - base_names_in_chain_on (loop, use, var); - } -} - -/* Returns true if CHAIN is suitable to be combined. */ - -static bool -chain_can_be_combined_p (chain_p chain) -{ - return (!chain->combined - && (chain->type == CT_LOAD || chain->type == CT_COMBINATION)); -} - -/* Returns the modify statement that uses NAME. Skips over assignment - statements, NAME is replaced with the actual name used in the returned - statement. */ - -static gimple -find_use_stmt (tree *name) -{ - gimple stmt; - tree rhs, lhs; - - /* Skip over assignments. */ - while (1) - { - stmt = single_nonlooparound_use (*name); - if (!stmt) - return NULL; - - if (gimple_code (stmt) != GIMPLE_ASSIGN) - return NULL; - - lhs = gimple_assign_lhs (stmt); - if (TREE_CODE (lhs) != SSA_NAME) - return NULL; - - if (gimple_assign_copy_p (stmt)) - { - rhs = gimple_assign_rhs1 (stmt); - if (rhs != *name) - return NULL; - - *name = lhs; - } - else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)) - == GIMPLE_BINARY_RHS) - return stmt; - else - return NULL; - } -} - -/* Returns true if we may perform reassociation for operation CODE in TYPE. */ - -static bool -may_reassociate_p (tree type, enum tree_code code) -{ - if (FLOAT_TYPE_P (type) - && !flag_unsafe_math_optimizations) - return false; - - return (commutative_tree_code (code) - && associative_tree_code (code)); -} - -/* If the operation used in STMT is associative and commutative, go through the - tree of the same operations and returns its root. Distance to the root - is stored in DISTANCE. */ - -static gimple -find_associative_operation_root (gimple stmt, unsigned *distance) -{ - tree lhs; - gimple next; - enum tree_code code = gimple_assign_rhs_code (stmt); - tree type = TREE_TYPE (gimple_assign_lhs (stmt)); - unsigned dist = 0; - - if (!may_reassociate_p (type, code)) - return NULL; - - while (1) - { - lhs = gimple_assign_lhs (stmt); - gcc_assert (TREE_CODE (lhs) == SSA_NAME); - - next = find_use_stmt (&lhs); - if (!next - || gimple_assign_rhs_code (next) != code) - break; - - stmt = next; - dist++; - } - - if (distance) - *distance = dist; - return stmt; -} - -/* Returns the common statement in that NAME1 and NAME2 have a use. If there - is no such statement, returns NULL_TREE. In case the operation used on - NAME1 and NAME2 is associative and commutative, returns the root of the - tree formed by this operation instead of the statement that uses NAME1 or - NAME2. */ - -static gimple -find_common_use_stmt (tree *name1, tree *name2) -{ - gimple stmt1, stmt2; - - stmt1 = find_use_stmt (name1); - if (!stmt1) - return NULL; - - stmt2 = find_use_stmt (name2); - if (!stmt2) - return NULL; - - if (stmt1 == stmt2) - return stmt1; - - stmt1 = find_associative_operation_root (stmt1, NULL); - if (!stmt1) - return NULL; - stmt2 = find_associative_operation_root (stmt2, NULL); - if (!stmt2) - return NULL; - - return (stmt1 == stmt2 ? stmt1 : NULL); -} - -/* Checks whether R1 and R2 are combined together using CODE, with the result - in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1 - if it is true. If CODE is ERROR_MARK, set these values instead. */ - -static bool -combinable_refs_p (dref r1, dref r2, - enum tree_code *code, bool *swap, tree *rslt_type) -{ - enum tree_code acode; - bool aswap; - tree atype; - tree name1, name2; - gimple stmt; - - name1 = name_for_ref (r1); - name2 = name_for_ref (r2); - gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE); - - stmt = find_common_use_stmt (&name1, &name2); - - if (!stmt) - return false; - - acode = gimple_assign_rhs_code (stmt); - aswap = (!commutative_tree_code (acode) - && gimple_assign_rhs1 (stmt) != name1); - atype = TREE_TYPE (gimple_assign_lhs (stmt)); - - if (*code == ERROR_MARK) - { - *code = acode; - *swap = aswap; - *rslt_type = atype; - return true; - } - - return (*code == acode - && *swap == aswap - && *rslt_type == atype); -} - -/* Remove OP from the operation on rhs of STMT, and replace STMT with - an assignment of the remaining operand. */ - -static void -remove_name_from_operation (gimple stmt, tree op) -{ - tree other_op; - gimple_stmt_iterator si; - - gcc_assert (is_gimple_assign (stmt)); - - if (gimple_assign_rhs1 (stmt) == op) - other_op = gimple_assign_rhs2 (stmt); - else - other_op = gimple_assign_rhs1 (stmt); - - si = gsi_for_stmt (stmt); - gimple_assign_set_rhs_from_tree (&si, other_op); - - /* We should not have reallocated STMT. */ - gcc_assert (gsi_stmt (si) == stmt); - - update_stmt (stmt); -} - -/* Reassociates the expression in that NAME1 and NAME2 are used so that they - are combined in a single statement, and returns this statement. */ - -static gimple -reassociate_to_the_same_stmt (tree name1, tree name2) -{ - gimple stmt1, stmt2, root1, root2, s1, s2; - gimple new_stmt, tmp_stmt; - tree new_name, tmp_name, var, r1, r2; - unsigned dist1, dist2; - enum tree_code code; - tree type = TREE_TYPE (name1); - gimple_stmt_iterator bsi; - - stmt1 = find_use_stmt (&name1); - stmt2 = find_use_stmt (&name2); - root1 = find_associative_operation_root (stmt1, &dist1); - root2 = find_associative_operation_root (stmt2, &dist2); - code = gimple_assign_rhs_code (stmt1); - - gcc_assert (root1 && root2 && root1 == root2 - && code == gimple_assign_rhs_code (stmt2)); - - /* Find the root of the nearest expression in that both NAME1 and NAME2 - are used. */ - r1 = name1; - s1 = stmt1; - r2 = name2; - s2 = stmt2; - - while (dist1 > dist2) - { - s1 = find_use_stmt (&r1); - r1 = gimple_assign_lhs (s1); - dist1--; - } - while (dist2 > dist1) - { - s2 = find_use_stmt (&r2); - r2 = gimple_assign_lhs (s2); - dist2--; - } - - while (s1 != s2) - { - s1 = find_use_stmt (&r1); - r1 = gimple_assign_lhs (s1); - s2 = find_use_stmt (&r2); - r2 = gimple_assign_lhs (s2); - } - - /* Remove NAME1 and NAME2 from the statements in that they are used - currently. */ - remove_name_from_operation (stmt1, name1); - remove_name_from_operation (stmt2, name2); - - /* Insert the new statement combining NAME1 and NAME2 before S1, and - combine it with the rhs of S1. */ - var = create_tmp_var (type, "predreastmp"); - add_referenced_var (var); - new_name = make_ssa_name (var, NULL); - new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2); - - var = create_tmp_var (type, "predreastmp"); - add_referenced_var (var); - tmp_name = make_ssa_name (var, NULL); - - /* Rhs of S1 may now be either a binary expression with operation - CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1, - so that name1 or name2 was removed from it). */ - tmp_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (s1), - tmp_name, - gimple_assign_rhs1 (s1), - gimple_assign_rhs2 (s1)); - - bsi = gsi_for_stmt (s1); - gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name); - s1 = gsi_stmt (bsi); - update_stmt (s1); - - gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT); - gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT); - - return new_stmt; -} - -/* Returns the statement that combines references R1 and R2. In case R1 - and R2 are not used in the same statement, but they are used with an - associative and commutative operation in the same expression, reassociate - the expression so that they are used in the same statement. */ - -static gimple -stmt_combining_refs (dref r1, dref r2) -{ - gimple stmt1, stmt2; - tree name1 = name_for_ref (r1); - tree name2 = name_for_ref (r2); - - stmt1 = find_use_stmt (&name1); - stmt2 = find_use_stmt (&name2); - if (stmt1 == stmt2) - return stmt1; - - return reassociate_to_the_same_stmt (name1, name2); -} - -/* Tries to combine chains CH1 and CH2 together. If this succeeds, the - description of the new chain is returned, otherwise we return NULL. */ - -static chain_p -combine_chains (chain_p ch1, chain_p ch2) -{ - dref r1, r2, nw; - enum tree_code op = ERROR_MARK; - bool swap = false; - chain_p new_chain; - unsigned i; - gimple root_stmt; - tree rslt_type = NULL_TREE; - - if (ch1 == ch2) - return false; - if (ch1->length != ch2->length) - return NULL; - - if (VEC_length (dref, ch1->refs) != VEC_length (dref, ch2->refs)) - return NULL; - - for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1) - && VEC_iterate (dref, ch2->refs, i, r2)); i++) - { - if (r1->distance != r2->distance) - return NULL; - - if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type)) - return NULL; - } - - if (swap) - { - chain_p tmp = ch1; - ch1 = ch2; - ch2 = tmp; - } - - new_chain = XCNEW (struct chain); - new_chain->type = CT_COMBINATION; - new_chain->op = op; - new_chain->ch1 = ch1; - new_chain->ch2 = ch2; - new_chain->rslt_type = rslt_type; - new_chain->length = ch1->length; - - for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1) - && VEC_iterate (dref, ch2->refs, i, r2)); i++) - { - nw = XCNEW (struct dref); - nw->stmt = stmt_combining_refs (r1, r2); - nw->distance = r1->distance; - - VEC_safe_push (dref, heap, new_chain->refs, nw); - } - - new_chain->has_max_use_after = false; - root_stmt = get_chain_root (new_chain)->stmt; - for (i = 1; VEC_iterate (dref, new_chain->refs, i, nw); i++) - { - if (nw->distance == new_chain->length - && !stmt_dominates_stmt_p (nw->stmt, root_stmt)) - { - new_chain->has_max_use_after = true; - break; - } - } - - ch1->combined = true; - ch2->combined = true; - return new_chain; -} - -/* Try to combine the CHAINS. */ - -static void -try_combine_chains (VEC (chain_p, heap) **chains) -{ - unsigned i, j; - chain_p ch1, ch2, cch; - VEC (chain_p, heap) *worklist = NULL; - - for (i = 0; VEC_iterate (chain_p, *chains, i, ch1); i++) - if (chain_can_be_combined_p (ch1)) - VEC_safe_push (chain_p, heap, worklist, ch1); - - while (!VEC_empty (chain_p, worklist)) - { - ch1 = VEC_pop (chain_p, worklist); - if (!chain_can_be_combined_p (ch1)) - continue; - - for (j = 0; VEC_iterate (chain_p, *chains, j, ch2); j++) - { - if (!chain_can_be_combined_p (ch2)) - continue; - - cch = combine_chains (ch1, ch2); - if (cch) - { - VEC_safe_push (chain_p, heap, worklist, cch); - VEC_safe_push (chain_p, heap, *chains, cch); - break; - } - } - } -} - -/* Sets alias information based on data reference DR for REF, - if necessary. */ - -static void -set_alias_info (tree ref, struct data_reference *dr) -{ - tree var; - tree tag = DR_SYMBOL_TAG (dr); - - gcc_assert (tag != NULL_TREE); - - ref = get_base_address (ref); - if (!ref || !INDIRECT_REF_P (ref)) - return; - - var = SSA_NAME_VAR (TREE_OPERAND (ref, 0)); - if (var_ann (var)->symbol_mem_tag) - return; - - if (!MTAG_P (tag)) - new_type_alias (var, tag, ref); - else - var_ann (var)->symbol_mem_tag = tag; -} - -/* Prepare initializers for CHAIN in LOOP. Returns false if this is - impossible because one of these initializers may trap, true otherwise. */ - -static bool -prepare_initializers_chain (struct loop *loop, chain_p chain) -{ - unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length; - struct data_reference *dr = get_chain_root (chain)->ref; - tree init; - gimple_seq stmts; - dref laref; - edge entry = loop_preheader_edge (loop); - - /* Find the initializers for the variables, and check that they cannot - trap. */ - chain->inits = VEC_alloc (tree, heap, n); - for (i = 0; i < n; i++) - VEC_quick_push (tree, chain->inits, NULL_TREE); - - /* If we have replaced some looparound phi nodes, use their initializers - instead of creating our own. */ - for (i = 0; VEC_iterate (dref, chain->refs, i, laref); i++) - { - if (gimple_code (laref->stmt) != GIMPLE_PHI) - continue; - - gcc_assert (laref->distance > 0); - VEC_replace (tree, chain->inits, n - laref->distance, - PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry)); - } - - for (i = 0; i < n; i++) - { - if (VEC_index (tree, chain->inits, i) != NULL_TREE) - continue; - - init = ref_at_iteration (loop, DR_REF (dr), (int) i - n); - if (!init) - return false; - - if (!chain->all_always_accessed && tree_could_trap_p (init)) - return false; - - init = force_gimple_operand (init, &stmts, false, NULL_TREE); - if (stmts) - { - mark_virtual_ops_for_renaming_list (stmts); - gsi_insert_seq_on_edge_immediate (entry, stmts); - } - set_alias_info (init, dr); - - VEC_replace (tree, chain->inits, i, init); - } - - return true; -} - -/* Prepare initializers for CHAINS in LOOP, and free chains that cannot - be used because the initializers might trap. */ - -static void -prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains) -{ - chain_p chain; - unsigned i; - - for (i = 0; i < VEC_length (chain_p, chains); ) - { - chain = VEC_index (chain_p, chains, i); - if (prepare_initializers_chain (loop, chain)) - i++; - else - { - release_chain (chain); - VEC_unordered_remove (chain_p, chains, i); - } - } -} - -/* Performs predictive commoning for LOOP. Returns true if LOOP was - unrolled. */ - -static bool -tree_predictive_commoning_loop (struct loop *loop) -{ - VEC (data_reference_p, heap) *datarefs; - VEC (ddr_p, heap) *dependences; - struct component *components; - VEC (chain_p, heap) *chains = NULL; - unsigned unroll_factor; - struct tree_niter_desc desc; - bool unroll = false; - edge exit; - bitmap tmp_vars; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Processing loop %d\n", loop->num); - - /* Find the data references and split them into components according to their - dependence relations. */ - datarefs = VEC_alloc (data_reference_p, heap, 10); - dependences = VEC_alloc (ddr_p, heap, 10); - compute_data_dependences_for_loop (loop, true, &datarefs, &dependences); - if (dump_file && (dump_flags & TDF_DETAILS)) - dump_data_dependence_relations (dump_file, dependences); - - components = split_data_refs_to_components (loop, datarefs, dependences); - free_dependence_relations (dependences); - if (!components) - { - free_data_refs (datarefs); - return false; - } - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Initial state:\n\n"); - dump_components (dump_file, components); - } - - /* Find the suitable components and split them into chains. */ - components = filter_suitable_components (loop, components); - - tmp_vars = BITMAP_ALLOC (NULL); - looparound_phis = BITMAP_ALLOC (NULL); - determine_roots (loop, components, &chains); - release_components (components); - - if (!chains) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "Predictive commoning failed: no suitable chains\n"); - goto end; - } - prepare_initializers (loop, chains); - - /* Try to combine the chains that are always worked with together. */ - try_combine_chains (&chains); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Before commoning:\n\n"); - dump_chains (dump_file, chains); - } - - /* Determine the unroll factor, and if the loop should be unrolled, ensure - that its number of iterations is divisible by the factor. */ - unroll_factor = determine_unroll_factor (chains); - scev_reset (); - unroll = should_unroll_loop_p (loop, unroll_factor, &desc); - exit = single_dom_exit (loop); - - /* Execute the predictive commoning transformations, and possibly unroll the - loop. */ - if (unroll) - { - struct epcc_data dta; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Unrolling %u times.\n", unroll_factor); - - dta.chains = chains; - dta.tmp_vars = tmp_vars; - - update_ssa (TODO_update_ssa_only_virtuals); - - /* Cfg manipulations performed in tree_transform_and_unroll_loop before - execute_pred_commoning_cbck is called may cause phi nodes to be - reallocated, which is a problem since CHAINS may point to these - statements. To fix this, we store the ssa names defined by the - phi nodes here instead of the phi nodes themselves, and restore - the phi nodes in execute_pred_commoning_cbck. A bit hacky. */ - replace_phis_by_defined_names (chains); - - tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc, - execute_pred_commoning_cbck, &dta); - eliminate_temp_copies (loop, tmp_vars); - } - else - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "Executing predictive commoning without unrolling.\n"); - execute_pred_commoning (loop, chains, tmp_vars); - } - -end: ; - release_chains (chains); - free_data_refs (datarefs); - BITMAP_FREE (tmp_vars); - BITMAP_FREE (looparound_phis); - - free_affine_expand_cache (&name_expansions); - - return unroll; -} - -/* Runs predictive commoning. */ - -unsigned -tree_predictive_commoning (void) -{ - bool unrolled = false; - struct loop *loop; - loop_iterator li; - unsigned ret = 0; - - initialize_original_copy_tables (); - FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) - if (optimize_loop_for_speed_p (loop)) - { - unrolled |= tree_predictive_commoning_loop (loop); - } - - if (unrolled) - { - scev_reset (); - ret = TODO_cleanup_cfg; - } - free_original_copy_tables (); - - return ret; -} -- cgit v1.2.3