Lines Matching refs:cand
80 2) Add one doloop dedicated IV cand {(may_be_zero ? 1 : (niter + 1)), +, -1},
82 like biv. For cost determination between doloop IV cand and IV use, the
85 Zero cost is assigned to the pair between doloop IV cand and doloop IV
389 struct iv_cand *cand; /* The candidate. */
475 struct iv *orig_iv; /* The original iv if this cand is added from biv with
850 /* Dumps information about induction variable candidate CAND to FILE. */
853 dump_cand (FILE *file, struct iv_cand *cand)
855 struct iv *iv = cand->iv;
857 fprintf (file, "Candidate %d:\n", cand->id);
858 if (cand->inv_vars)
861 dump_bitmap (file, cand->inv_vars);
863 if (cand->inv_exprs)
866 dump_bitmap (file, cand->inv_exprs);
869 if (cand->var_before)
872 print_generic_expr (file, cand->var_before, TDF_SLIM);
875 if (cand->var_after)
878 print_generic_expr (file, cand->var_after, TDF_SLIM);
882 switch (cand->pos)
889 fprintf (file, " Incr POS: before use %d\n", cand->ainc_use->id);
893 fprintf (file, " Incr POS: after use %d\n", cand->ainc_use->id);
944 variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true
948 stmt_after_inc_pos (struct iv_cand *cand, gimple *stmt, bool true_if_equal)
950 basic_block cand_bb = gimple_bb (cand->incremented_at);
960 && gimple_uid (stmt) == gimple_uid (cand->incremented_at))
962 return gimple_uid (stmt) > gimple_uid (cand->incremented_at);
966 CAND is incremented in LOOP. */
969 stmt_after_increment (class loop *loop, struct iv_cand *cand, gimple *stmt)
971 switch (cand->pos)
981 return stmt_after_inc_pos (cand, stmt, false);
984 return stmt_after_inc_pos (cand, stmt, true);
3106 struct iv_cand *cand = NULL;
3148 cand = data->vcands[i];
3150 if (cand->pos != pos)
3153 if (cand->incremented_at != incremented_at
3155 && cand->ainc_use != use))
3158 if (operand_equal_p (base, cand->iv->base, 0)
3159 && operand_equal_p (step, cand->iv->step, 0)
3161 == TYPE_PRECISION (TREE_TYPE (cand->iv->base))))
3167 cand = XCNEW (struct iv_cand);
3168 cand->id = i;
3169 cand->iv = alloc_iv (data, base, step);
3170 cand->pos = pos;
3174 cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "doloop");
3176 cand->var_before = create_tmp_var_raw (TREE_TYPE (base), "ivtmp");
3177 cand->var_after = cand->var_before;
3179 cand->important = important;
3180 cand->involves_undefs = involves_undefs;
3181 cand->incremented_at = incremented_at;
3182 cand->doloop_p = doloop;
3183 data->vcands.safe_push (cand);
3187 find_inv_vars (data, &step, &cand->inv_vars);
3190 /* Share bitmap between inv_vars and inv_exprs for cand. */
3193 cand->inv_exprs = cand->inv_vars;
3194 cand->inv_vars = NULL;
3195 if (cand->inv_exprs)
3196 bitmap_clear (cand->inv_exprs);
3198 cand->inv_exprs = BITMAP_ALLOC (NULL);
3200 bitmap_set_bit (cand->inv_exprs, inv_expr->id);
3205 cand->ainc_use = use;
3207 cand->ainc_use = NULL;
3209 cand->orig_iv = orig_iv;
3211 dump_cand (dump_file, cand);
3214 cand->important |= important;
3215 cand->doloop_p |= doloop;
3221 return cand;
3353 struct iv_cand *cand;
3363 /* Add iv cand of same precision as index part in TARGET_MEM_REF. */
3365 /* Add iv cand of the original type only if it has nonlinear use. */
3390 cand = add_candidate_1 (data,
3393 if (cand)
3395 cand->var_before = iv->ssa_name;
3396 cand->var_after = def;
3626 struct iv_cand *cand = data->vcands[i];
3628 if (cand->important)
3671 /* Sets cost of (GROUP, CAND) pair to COST and record that it depends
3677 struct iv_group *group, struct iv_cand *cand,
3692 group->cost_map[cand->id].cand = cand;
3693 group->cost_map[cand->id].cost = cost;
3694 group->cost_map[cand->id].inv_vars = inv_vars;
3695 group->cost_map[cand->id].inv_exprs = inv_exprs;
3696 group->cost_map[cand->id].value = value;
3697 group->cost_map[cand->id].comp = comp;
3702 s = cand->id & (group->n_map_members - 1);
3704 if (!group->cost_map[i].cand)
3707 if (!group->cost_map[i].cand)
3713 group->cost_map[i].cand = cand;
3721 /* Gets cost of (GROUP, CAND) pair. */
3725 struct iv_cand *cand)
3730 if (!cand)
3735 ret = group->cost_map + cand->id;
3736 if (!ret->cand)
3743 s = cand->id & (group->n_map_members - 1);
3745 if (group->cost_map[i].cand == cand)
3747 else if (group->cost_map[i].cand == NULL)
3750 if (group->cost_map[i].cand == cand)
3752 else if (group->cost_map[i].cand == NULL)
3938 /* Returns variable containing the value of candidate CAND at statement AT. */
3941 var_at_stmt (class loop *loop, struct iv_cand *cand, gimple *stmt)
3943 if (stmt_after_increment (loop, cand, stmt))
3944 return cand->var_after;
3946 return cand->var_before;
3986 CAND at statement AT in LOOP. The expression is stored in two parts in a
3988 part in AFF_VAR. Store ratio of CAND.step over USE.step in PRAT if it's
3989 non-null. Returns false if USE cannot be expressed using CAND. */
3993 struct iv_cand *cand, class aff_tree *aff_inv,
3997 tree cbase = cand->iv->base, cstep = cand->iv->step;
4007 var = var_at_stmt (loop, cand, at);
4013 if (cand->orig_iv != NULL && CONVERT_EXPR_P (cbase)
4040 /* Ratio is 1 when computing the value of biv cand by itself.
4045 if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
4048 gcc_assert (use->iv->ssa_name == cand->var_after);
4049 gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after);
4071 if (stmt_after_increment (loop, cand, at))
4094 CAND at statement AT in LOOP. The expression is stored in a decomposed
4095 form into AFF. Returns false if USE cannot be expressed using CAND. */
4099 struct iv_cand *cand, class aff_tree *aff)
4103 cand, aff, &aff_var))
4133 CAND at statement AT in LOOP. The computation is unshared. */
4137 struct iv_use *use, struct iv_cand *cand)
4142 if (!get_computation_aff (loop, at, use, cand, &aff))
4153 struct iv_use *use, struct iv_cand *cand)
4155 if (tree ret = get_computation_at (loop, at, use, cand))
4159 tree cbase = cand->iv->base, cstep = cand->iv->step;
4184 /* If both IVs can wrap around and CAND doesn't have a power of two step,
4185 it is unsafe. Consider uint16_t CAND with step 9, when wrapping around,
4190 && !cand->iv->no_overflow
4197 if (!cand->iv->no_overflow
4201 var = var_at_stmt (loop, cand, at);
4211 if (stmt_after_increment (loop, cand, at))
4668 /* Return cost of computing USE's address expression by using CAND.
4674 steps of USE and CAND. If CAN_AUTOINC is nonNULL, store boolean
4679 struct iv_cand *cand, aff_tree *aff_inv,
4748 && ptrdiff_tree_p (cand->iv->step, &ainc_step))
4752 if (stmt_after_increment (data->current_loop, cand, use->stmt))
4854 from induction variable CAND. If ADDRESS_P is true, we just need
4863 struct iv_cand *cand, bool address_p, bitmap *inv_vars,
4867 tree ubase = use->iv->base, cbase = cand->iv->base;
4889 && cand->iv->base_object
4891 && POINTER_TYPE_P (TREE_TYPE (cand->iv->base_object))))
4899 && cand->iv->base_object
4900 && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
4905 cand, &aff_inv, &aff_var, &rat)
4912 cost = get_address_cost (data, use, cand, &aff_inv, &aff_var, ratio,
4915 /* For doloop IV cand, add on the extra cost. */
4916 cost += cand->doloop_p ? targetm.doloop_cost_for_address : 0;
4944 /* Need type narrowing to represent use with cand. */
4969 /* For doloop IV cand, add on the extra cost. */
4970 if (cand->doloop_p && use->type == USE_NONLINEAR_EXPR)
4976 /* Determines cost of computing the use in GROUP with CAND in a generic
4981 struct iv_group *group, struct iv_cand *cand)
4992 if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
4996 else if (cand->involves_undefs
4997 && (!use->iv || !operand_equal_p (cand->iv->base, use->iv->base, 0)))
5000 cost = get_computation_cost (data, use, cand, false,
5008 set_group_iv_cost (data, group, cand, cost, inv_vars,
5013 /* Determines cost of computing uses in GROUP with CAND in addresses. */
5017 struct iv_group *group, struct iv_cand *cand)
5026 cost = get_computation_cost (data, use, cand, true,
5035 if (!sum_cost.infinite_cost_p () && cand->ainc_use == use)
5038 sum_cost -= cand->cost_step;
5042 else if (cand->pos == IP_AFTER_USE || cand->pos == IP_BEFORE_USE)
5056 cost = get_computation_cost (data, next, cand, true,
5067 set_group_iv_cost (data, group, cand, sum_cost, inv_vars,
5073 /* Computes value of candidate CAND at position AT in iteration DESC->NITER,
5077 cand_value_at (class loop *loop, struct iv_cand *cand, gimple *at,
5081 struct iv *iv = cand->iv;
5084 bool after_adjust = stmt_after_increment (loop, cand, at);
5248 comparison with CAND. NITER describes the number of iterations of
5288 struct iv_cand *cand, enum tree_code *comp_p,
5300 cand_type = TREE_TYPE (cand->iv->base);
5301 if (cand->pos != IP_ORIGINAL || !nowrap_type_p (cand_type))
5312 if (!cst_and_fits_in_hwi (cand->iv->step))
5314 step = int_cst_value (cand->iv->step);
5359 /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
5361 offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
5362 cand->iv->step,
5363 fold_convert (TREE_TYPE (cand->iv->step), a));
5364 if (!difference_cannot_overflow_p (data, cand->iv->base, offset))
5380 of candidate CAND. If so, store the value compared with to BOUND, and the
5385 struct iv_use *use, struct iv_cand *cand, tree *bound,
5395 if (TREE_CODE (cand->iv->step) != INTEGER_CST)
5419 period = iv_period (cand->iv);
5425 if (stmt_after_increment (loop, cand, use->stmt))
5445 if (stmt_after_increment (loop, cand, use->stmt))
5465 /* For doloop IV cand, the bound would be zero. It's safe whether
5467 if (cand->doloop_p)
5469 *bound = build_int_cst (TREE_TYPE (cand->iv->base), 0);
5474 cand_value_at (loop, cand, use->stmt, desc, &bnd);
5476 *bound = fold_convert (TREE_TYPE (cand->iv->base),
5493 return iv_elimination_compare_lt (data, cand, comp, desc);
5516 /* Determines cost of computing the use in GROUP with CAND in a condition. */
5520 struct iv_group *group, struct iv_cand *cand)
5540 && may_eliminate_iv (data, use, cand, &bound, &comp))
5571 && (operand_equal_p (*control_var, cand->var_after, 0)
5572 || operand_equal_p (*control_var, cand->var_before, 0)))
5575 express_cost = get_computation_cost (data, use, cand, false,
5597 if (group->doloop_p && cand->doloop_p && elim_cost.cost > no_cost.cost)
5615 set_group_iv_cost (data, group, cand, cost,
5626 /* Determines cost of computing uses in GROUP with CAND. Returns false
5627 if USE cannot be represented with CAND. */
5631 struct iv_group *group, struct iv_cand *cand)
5636 return determine_group_iv_cost_generic (data, group, cand);
5640 return determine_group_iv_cost_address (data, group, cand);
5643 return determine_group_iv_cost_cond (data, group, cand);
5651 a possibility for the pair of USE and CAND, false otherwise. */
5655 struct iv_cand *cand)
5661 get_computation_cost (data, use, cand, true, NULL, &can_autoinc, NULL);
5675 struct iv_cand *cand = data->vcands[i];
5678 if (cand->pos != IP_ORIGINAL)
5687 if (gimple_bb (use->stmt) != gimple_bb (cand->incremented_at))
5690 if (uid < gimple_uid (cand->incremented_at)
5695 if (uid > gimple_uid (cand->incremented_at)
5702 && autoinc_possible_for_pair (data, closest_before, cand))
5703 cand->ainc_use = closest_before;
5705 && autoinc_possible_for_pair (data, closest_after, cand))
5706 cand->ainc_use = closest_after;
5863 fprintf (dump_file, "\n<Group, Cand> Related:\n");
5884 struct iv_cand *cand;
5898 cand = data->vcands[j];
5899 determine_group_iv_cost (data, group, cand);
5908 cand = data->vcands[j];
5909 if (!determine_group_iv_cost (data, group, cand))
5965 fprintf (dump_file, " cand\tcost\tcompl.\tinv.expr.\tinv.vars\n");
5968 if (!group->cost_map[j].cand
5973 group->cost_map[j].cand->id,
5996 /* Determines cost of the candidate CAND. */
5999 determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
6005 gcc_assert (cand->iv != NULL);
6011 base = cand->iv->base;
6019 if (cand->doloop_p)
6028 if ((cand->pos != IP_ORIGINAL
6029 || !SSA_NAME_VAR (cand->var_before)
6030 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
6032 && !cand->doloop_p)
6037 if (cand->pos == IP_END
6041 cand->cost = cost;
6042 cand->cost_step = cost_step;
6055 fprintf (dump_file, " cand\tcost\n");
6060 struct iv_cand *cand = data->vcands[i];
6062 determine_iv_cost (data, cand);
6065 fprintf (dump_file, " %d\t%d\n", i, cand->cost);
6195 if (a->cand->cost < b->cand->cost)
6268 cid = cp->cand->id;
6277 if (!cp->cand->doloop_p || !targetm.have_count_reg_decr_p)
6279 ivs->cand_cost -= cp->cand->cost;
6280 iv_ca_set_remove_invs (ivs, cp->cand->inv_vars, ivs->n_inv_var_uses);
6281 iv_ca_set_remove_invs (ivs, cp->cand->inv_exprs, ivs->n_inv_expr_uses);
6327 cid = cp->cand->id;
6335 if (!cp->cand->doloop_p || !targetm.have_count_reg_decr_p)
6337 ivs->cand_cost += cp->cand->cost;
6338 iv_ca_set_add_invs (ivs, cp->cand->inv_vars, ivs->n_inv_var_uses);
6339 iv_ca_set_add_invs (ivs, cp->cand->inv_exprs, ivs->n_inv_expr_uses);
6360 struct iv_cand *cand;
6368 cand = data->vcands[i];
6369 cp = get_group_iv_cost (data, group, cand);
6378 cand = data->vcands[i];
6379 cp = get_group_iv_cost (data, group, cand);
6501 /* Returns true if CAND is used in IVS. */
6504 iv_ca_cand_used_p (class iv_ca *ivs, struct iv_cand *cand)
6506 return ivs->n_cand_uses[cand->id] > 0;
6594 "%" PRId64 ",%d)\n", group->id, cp->cand->id,
6621 /* Try changing candidate in IVS to CAND for each use. Return cost of the
6628 struct iv_cand *cand, struct iv_ca_delta **delta,
6643 && old_cp->cand == cand)
6646 new_cp = get_group_iv_cost (data, group, cand);
6675 /* Try narrowing set IVS by removing CAND. Return the cost of
6681 struct iv_cand *cand, struct iv_cand *start,
6697 if (old_cp->cand != cand)
6708 if (ci == cand->id || (start && ci == start->id))
6731 if (ci == cand->id || (start && ci == start->id))
6781 struct iv_cand *cand;
6788 cand = data->vcands[i];
6790 if (cand == except_cand)
6793 acost = iv_ca_narrow (data, ivs, cand, except_cand, &act_delta);
6828 struct iv_cand *cand;
6835 cand = data->vcands[cand_idx];
6836 cp = get_group_iv_cost (data, group, cand);
6856 struct iv_cand *cand;
6870 cand = data->vcands[i];
6880 if (old_cp->cand != cand)
6887 old_cp->cand, best_cp);
6891 old_cp->cand, best_cp);
6932 struct iv_cand *cand;
6956 cand = data->vcands[i];
6958 if (originalp && cand->pos !=IP_ORIGINAL)
6961 if (!originalp && cand->iv->base_object != NULL_TREE)
6964 if (iv_ca_cand_used_p (ivs, cand))
6967 cp = get_group_iv_cost (data, group, cand);
6972 act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL,
6993 cand = cp->cand;
6994 if (!cand)
6998 if (cand->important)
7000 if (originalp && cand->pos == IP_ORIGINAL)
7002 if (!originalp && cand->iv->base_object == NULL_TREE)
7006 if (iv_ca_cand_used_p (ivs, cand))
7011 act_cost = iv_ca_extend (data, ivs, cand, &act_delta, NULL, true);
7065 struct iv_cand *cand;
7070 cand = data->vcands[i];
7072 if (iv_ca_cand_used_p (ivs, cand))
7075 acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs, false);
7084 acost = iv_ca_prune (data, ivs, cand, &tmp_delta);
7212 group->selected = iv_ca_cand_for_group (set, group)->cand;
7218 /* Creates a new induction variable corresponding to CAND. */
7221 create_new_iv (struct ivopts_data *data, struct iv_cand *cand)
7229 gcc_assert (cand->iv != NULL);
7231 switch (cand->pos)
7252 incr_pos = gsi_for_stmt (cand->incremented_at);
7257 name_info (data, cand->var_before)->preserve_biv = true;
7258 name_info (data, cand->var_after)->preserve_biv = true;
7261 use = find_interesting_uses_op (data, cand->var_after);
7263 group->selected = cand;
7267 gimple_add_tmp_var (cand->var_before);
7269 base = unshare_expr (cand->iv->base);
7271 create_iv (base, unshare_expr (cand->iv->step),
7272 cand->var_before, data->current_loop,
7273 &incr_pos, after, &cand->var_before, &cand->var_after);
7282 struct iv_cand *cand;
7287 cand = data->vcands[i];
7288 create_new_iv (data, cand);
7303 cand = data->vcands[i];
7304 dump_cand (dump_file, cand);
7311 using candidate CAND. */
7315 struct iv_use *use, struct iv_cand *cand)
7325 if (cand->pos == IP_ORIGINAL
7326 && cand->incremented_at == use->stmt)
7332 gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after);
7344 if (gimple_assign_rhs1 (use->stmt) == cand->var_before)
7346 else if (gimple_assign_rhs2 (use->stmt) == cand->var_before)
7386 use, cand, &aff_inv, &aff_var))
7464 adjustment of the offset. CAND is the selected IV_CAND.
7488 adjust_iv_update_pos (struct iv_cand *cand, struct iv_use *use)
7495 if (cand->pos != IP_NORMAL)
7498 var_after = cand->var_after;
7540 cand->pos = IP_BEFORE_USE;
7541 cand->incremented_at = use->stmt;
7569 /* Rewrites USE (address that is an iv) using candidate CAND. */
7573 struct iv_use *use, struct iv_cand *cand)
7578 adjust_iv_update_pos (cand, use);
7579 ok = get_computation_aff (data->current_loop, use->stmt, use, cand, &aff);
7594 tree iv = var_at_stmt (data->current_loop, cand, use->stmt);
7595 tree base_hint = (cand->iv->base_object) ? iv : NULL_TREE;
7641 candidate CAND. */
7645 struct iv_use *use, struct iv_cand *cand)
7651 class cost_pair *cp = get_group_iv_cost (data, group, cand);
7656 tree var = var_at_stmt (data->current_loop, cand, use->stmt);
7682 comp = get_computation_at (data->current_loop, use->stmt, use, cand);
7700 struct iv_cand *cand = group->selected;
7702 gcc_assert (cand);
7708 rewrite_use_nonlinear_expr (data, group->vuses[j], cand);
7716 rewrite_use_address (data, group->vuses[j], cand);
7726 rewrite_use_compare (data, group->vuses[j], cand);
7789 struct iv_cand *best_cand = NULL, *cand;
7797 cand = data->vgroups[i]->selected;
7798 if (cand == best_cand)
7800 cand_pref = operand_equal_p (cand->iv->step,
7804 += TYPE_MODE (TREE_TYPE (cand->iv->base))
7808 += TREE_CODE (cand->iv->base) == INTEGER_CST
7815 &dummy_use, cand);
7818 best_cand = cand;
7929 struct iv_cand *cand = data->vcands[i];
7931 if (cand->inv_vars)
7932 BITMAP_FREE (cand->inv_vars);
7933 if (cand->inv_exprs)
7934 BITMAP_FREE (cand->inv_exprs);
7935 free (cand);
Indexes created Wed May 13 00:24:45 UTC 2026