/* Induction variable optimizations.
- Copyright (C) 2003-2013 Free Software Foundation, Inc.
+ Copyright (C) 2003-2014 Free Software Foundation, Inc.
This file is part of GCC.
#include "tm_p.h"
#include "basic-block.h"
#include "gimple-pretty-print.h"
+#include "pointer-set.h"
+#include "hash-table.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "tree-eh.h"
+#include "gimple-expr.h"
+#include "is-a.h"
#include "gimple.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "tree-ssa.h"
#include "cfgloop.h"
#include "tree-pass.h"
-#include "ggc.h"
#include "insn-config.h"
-#include "pointer-set.h"
-#include "hash-table.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "cfgloop.h"
static void
mark_bivs (struct ivopts_data *data)
{
- gimple phi;
+ gimple phi, def;
tree var;
struct iv *iv, *incr_iv;
struct loop *loop = data->current_loop;
continue;
var = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
+ def = SSA_NAME_DEF_STMT (var);
+ /* Don't mark iv peeled from other one as biv. */
+ if (def
+ && gimple_code (def) == GIMPLE_PHI
+ && gimple_bb (def) == loop->header)
+ continue;
+
incr_iv = get_iv (data, var);
if (!incr_iv)
continue;
}
}
-/* Returns true if memory reference REF with step STEP may be unaligned. */
+/* Return true if memory reference REF with step STEP may be unaligned. */
static bool
may_be_unaligned_p (tree ref, tree step)
{
- tree base;
- tree base_type;
- HOST_WIDE_INT bitsize;
- HOST_WIDE_INT bitpos;
- tree toffset;
- enum machine_mode mode;
- int unsignedp, volatilep;
- unsigned base_align;
-
/* TARGET_MEM_REFs are translated directly to valid MEMs on the target,
thus they are not misaligned. */
if (TREE_CODE (ref) == TARGET_MEM_REF)
return false;
- /* The test below is basically copy of what expr.c:normal_inner_ref
- does to check whether the object must be loaded by parts when
- STRICT_ALIGNMENT is true. */
- base = get_inner_reference (ref, &bitsize, &bitpos, &toffset, &mode,
- &unsignedp, &volatilep, true);
- base_type = TREE_TYPE (base);
- base_align = get_object_alignment (base);
- base_align = MAX (base_align, TYPE_ALIGN (base_type));
-
- if (mode != BLKmode)
- {
- unsigned mode_align = GET_MODE_ALIGNMENT (mode);
-
- if (base_align < mode_align
- || (bitpos % mode_align) != 0
- || (bitpos % BITS_PER_UNIT) != 0)
- return true;
+ unsigned int align = TYPE_ALIGN (TREE_TYPE (ref));
- if (toffset
- && (highest_pow2_factor (toffset) * BITS_PER_UNIT) < mode_align)
- return true;
+ unsigned HOST_WIDE_INT bitpos;
+ unsigned int ref_align;
+ get_object_alignment_1 (ref, &ref_align, &bitpos);
+ if (ref_align < align
+ || (bitpos % align) != 0
+ || (bitpos % BITS_PER_UNIT) != 0)
+ return true;
- if ((highest_pow2_factor (step) * BITS_PER_UNIT) < mode_align)
- return true;
- }
+ unsigned int trailing_zeros = tree_ctz (step);
+ if (trailing_zeros < HOST_BITS_PER_INT
+ && (1U << trailing_zeros) * BITS_PER_UNIT < align)
+ return true;
return false;
}
/* Additionally record the possibility of leaving the original iv
untouched. */
def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
- cand = add_candidate_1 (data,
- iv->base, iv->step, true, IP_ORIGINAL, NULL,
- SSA_NAME_DEF_STMT (def));
- cand->var_before = iv->ssa_name;
- cand->var_after = def;
+ /* Don't add candidate if it's from another PHI node because
+ it's an affine iv appearing in the form of PEELED_CHREC. */
+ phi = SSA_NAME_DEF_STMT (def);
+ if (gimple_code (phi) != GIMPLE_PHI)
+ {
+ cand = add_candidate_1 (data,
+ iv->base, iv->step, true, IP_ORIGINAL, NULL,
+ SSA_NAME_DEF_STMT (def));
+ cand->var_before = iv->ssa_name;
+ cand->var_after = def;
+ }
+ else
+ gcc_assert (gimple_bb (phi) == data->current_loop->header);
}
}
static bool
get_computation_aff (struct loop *loop,
struct iv_use *use, struct iv_cand *cand, gimple at,
- struct affine_tree_combination *aff)
+ struct aff_tree *aff)
{
tree ubase = use->iv->base;
tree ustep = use->iv->step;
struct tree_niter_desc *niter)
{
tree cand_type, a, b, mbz, nit_type = TREE_TYPE (niter->niter), offset;
- struct affine_tree_combination nit, tmpa, tmpb;
+ struct aff_tree nit, tmpa, tmpb;
enum tree_code comp;
HOST_WIDE_INT step;
}
/* Try narrowing set IVS by removing CAND. Return the cost of
- the new set and store the differences in DELTA. */
+ the new set and store the differences in DELTA. START is
+ the candidate with which we start narrowing. */
static comp_cost
iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs,
- struct iv_cand *cand, struct iv_ca_delta **delta)
+ struct iv_cand *cand, struct iv_cand *start,
+ struct iv_ca_delta **delta)
{
unsigned i, ci;
struct iv_use *use;
struct cost_pair *old_cp, *new_cp, *cp;
bitmap_iterator bi;
struct iv_cand *cnd;
- comp_cost cost;
+ comp_cost cost, best_cost, acost;
*delta = NULL;
for (i = 0; i < n_iv_uses (data); i++)
if (old_cp->cand != cand)
continue;
- new_cp = NULL;
+ best_cost = iv_ca_cost (ivs);
+ /* Start narrowing with START. */
+ new_cp = get_use_iv_cost (data, use, start);
if (data->consider_all_candidates)
{
EXECUTE_IF_SET_IN_BITMAP (ivs->cands, 0, ci, bi)
{
- if (ci == cand->id)
+ if (ci == cand->id || (start && ci == start->id))
continue;
cnd = iv_cand (data, ci);
if (!cp)
continue;
- if (!iv_ca_has_deps (ivs, cp))
- continue;
-
- if (!cheaper_cost_pair (cp, new_cp))
- continue;
+ iv_ca_set_cp (data, ivs, use, cp);
+ acost = iv_ca_cost (ivs);
- new_cp = cp;
+ if (compare_costs (acost, best_cost) < 0)
+ {
+ best_cost = acost;
+ new_cp = cp;
+ }
}
}
else
{
EXECUTE_IF_AND_IN_BITMAP (use->related_cands, ivs->cands, 0, ci, bi)
{
- if (ci == cand->id)
+ if (ci == cand->id || (start && ci == start->id))
continue;
cnd = iv_cand (data, ci);
cp = get_use_iv_cost (data, use, cnd);
if (!cp)
continue;
- if (!iv_ca_has_deps (ivs, cp))
- continue;
- if (!cheaper_cost_pair (cp, new_cp))
- continue;
+ iv_ca_set_cp (data, ivs, use, cp);
+ acost = iv_ca_cost (ivs);
- new_cp = cp;
+ if (compare_costs (acost, best_cost) < 0)
+ {
+ best_cost = acost;
+ new_cp = cp;
+ }
}
}
+ /* Restore to old cp for use. */
+ iv_ca_set_cp (data, ivs, use, old_cp);
if (!new_cp)
{
if (cand == except_cand)
continue;
- acost = iv_ca_narrow (data, ivs, cand, &act_delta);
+ acost = iv_ca_narrow (data, ivs, cand, except_cand, &act_delta);
if (compare_costs (acost, best_cost) < 0)
{