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