+ use_loop = loop_outer (use_loop);
+ }
+}
+
+/* Returns from CACHE the value for VERSION instantiated below
+ INSTANTIATED_BELOW block. */
+
+static tree
+get_instantiated_value (htab_t cache, basic_block instantiated_below,
+ tree version)
+{
+ struct scev_info_str *info, pattern;
+
+ pattern.var = version;
+ pattern.instantiated_below = instantiated_below;
+ info = (struct scev_info_str *) htab_find (cache, &pattern);
+
+ if (info)
+ return info->chrec;
+ else
+ return NULL_TREE;
+}
+
+/* Sets in CACHE the value of VERSION instantiated below basic block
+ INSTANTIATED_BELOW to VAL. */
+
+static void
+set_instantiated_value (htab_t cache, basic_block instantiated_below,
+ tree version, tree val)
+{
+ struct scev_info_str *info, pattern;
+ PTR *slot;
+
+ pattern.var = version;
+ pattern.instantiated_below = instantiated_below;
+ slot = htab_find_slot (cache, &pattern, INSERT);
+
+ if (!*slot)
+ *slot = new_scev_info_str (instantiated_below, version);
+ info = (struct scev_info_str *) *slot;
+ info->chrec = val;
+}
+
+/* Return the closed_loop_phi node for VAR. If there is none, return
+ NULL_TREE. */
+
+static tree
+loop_closed_phi_def (tree var)
+{
+ struct loop *loop;
+ edge exit;
+ gimple phi;
+ gimple_stmt_iterator psi;
+
+ if (var == NULL_TREE
+ || TREE_CODE (var) != SSA_NAME)
+ return NULL_TREE;
+
+ loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
+ exit = single_exit (loop);
+ if (!exit)
+ return NULL_TREE;
+
+ for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
+ {
+ phi = gsi_stmt (psi);
+ if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
+ return PHI_RESULT (phi);
+ }
+
+ return NULL_TREE;
+}
+
+static tree instantiate_scev_r (basic_block, struct loop *, tree, bool,
+ htab_t, int);
+
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
+ and EVOLUTION_LOOP, that were left under a symbolic form.
+
+ CHREC is an SSA_NAME to be instantiated.
+
+ CACHE is the cache of already instantiated values.
+
+ FOLD_CONVERSIONS should be set to true when the conversions that
+ may wrap in signed/pointer type are folded, as long as the value of
+ the chrec is preserved.
+
+ SIZE_EXPR is used for computing the size of the expression to be
+ instantiated, and to stop if it exceeds some limit. */
+
+static tree
+instantiate_scev_name (basic_block instantiate_below,
+ struct loop *evolution_loop, tree chrec,
+ bool fold_conversions, htab_t cache, int size_expr)
+{
+ tree res;
+ struct loop *def_loop;
+ basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
+
+ /* A parameter (or loop invariant and we do not want to include
+ evolutions in outer loops), nothing to do. */
+ if (!def_bb
+ || loop_depth (def_bb->loop_father) == 0
+ || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
+ return chrec;
+
+ /* We cache the value of instantiated variable to avoid exponential
+ time complexity due to reevaluations. We also store the convenient
+ value in the cache in order to prevent infinite recursion -- we do
+ not want to instantiate the SSA_NAME if it is in a mixer
+ structure. This is used for avoiding the instantiation of
+ recursively defined functions, such as:
+
+ | a_2 -> {0, +, 1, +, a_2}_1 */
+
+ res = get_instantiated_value (cache, instantiate_below, chrec);
+ if (res)
+ return res;
+
+ res = chrec_dont_know;
+ set_instantiated_value (cache, instantiate_below, chrec, res);
+
+ def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
+
+ /* If the analysis yields a parametric chrec, instantiate the
+ result again. */
+ res = analyze_scalar_evolution (def_loop, chrec);
+
+ /* Don't instantiate default definitions. */
+ if (TREE_CODE (res) == SSA_NAME
+ && SSA_NAME_IS_DEFAULT_DEF (res))
+ ;
+
+ /* Don't instantiate loop-closed-ssa phi nodes. */
+ else if (TREE_CODE (res) == SSA_NAME
+ && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
+ > loop_depth (def_loop))
+ {
+ if (res == chrec)
+ res = loop_closed_phi_def (chrec);
+ else
+ res = chrec;
+
+ /* When there is no loop_closed_phi_def, it means that the
+ variable is not used after the loop: try to still compute the
+ value of the variable when exiting the loop. */
+ if (res == NULL_TREE)
+ {
+ loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
+ res = analyze_scalar_evolution (loop, chrec);
+ res = compute_overall_effect_of_inner_loop (loop, res);
+ res = instantiate_scev_r (instantiate_below, evolution_loop, res,
+ fold_conversions, cache, size_expr);
+ }
+ else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
+ gimple_bb (SSA_NAME_DEF_STMT (res))))
+ res = chrec_dont_know;
+ }
+
+ else if (res != chrec_dont_know)
+ res = instantiate_scev_r (instantiate_below, evolution_loop, res,
+ fold_conversions, cache, size_expr);
+
+ /* Store the correct value to the cache. */
+ set_instantiated_value (cache, instantiate_below, chrec, res);
+ return res;
+}
+
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
+ and EVOLUTION_LOOP, that were left under a symbolic form.
+
+ CHREC is a polynomial chain of recurrence to be instantiated.
+
+ CACHE is the cache of already instantiated values.
+
+ FOLD_CONVERSIONS should be set to true when the conversions that
+ may wrap in signed/pointer type are folded, as long as the value of
+ the chrec is preserved.
+
+ SIZE_EXPR is used for computing the size of the expression to be
+ instantiated, and to stop if it exceeds some limit. */
+
+static tree
+instantiate_scev_poly (basic_block instantiate_below,
+ struct loop *evolution_loop, tree chrec,
+ bool fold_conversions, htab_t cache, int size_expr)
+{
+ tree op1;
+ tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
+ CHREC_LEFT (chrec), fold_conversions, cache,
+ size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
+ op1 = instantiate_scev_r (instantiate_below, evolution_loop,
+ CHREC_RIGHT (chrec), fold_conversions, cache,
+ size_expr);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (CHREC_LEFT (chrec) != op0
+ || CHREC_RIGHT (chrec) != op1)
+ {
+ unsigned var = CHREC_VARIABLE (chrec);
+
+ /* When the instantiated stride or base has an evolution in an
+ innermost loop, return chrec_dont_know, as this is not a
+ valid SCEV representation. In the reduced testcase for
+ PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no
+ meaning. */
+ if ((tree_is_chrec (op0) && CHREC_VARIABLE (op0) > var)
+ || (tree_is_chrec (op1) && CHREC_VARIABLE (op1) > var))
+ return chrec_dont_know;
+
+ op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
+ chrec = build_polynomial_chrec (var, op0, op1);
+ }
+
+ return chrec;
+}
+
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
+ and EVOLUTION_LOOP, that were left under a symbolic form.
+
+ "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
+
+ CACHE is the cache of already instantiated values.
+
+ FOLD_CONVERSIONS should be set to true when the conversions that
+ may wrap in signed/pointer type are folded, as long as the value of
+ the chrec is preserved.
+
+ SIZE_EXPR is used for computing the size of the expression to be
+ instantiated, and to stop if it exceeds some limit. */
+
+static tree
+instantiate_scev_binary (basic_block instantiate_below,
+ struct loop *evolution_loop, tree chrec, enum tree_code code,
+ tree type, tree c0, tree c1,
+ bool fold_conversions, htab_t cache, int size_expr)
+{
+ tree op1;
+ tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
+ c0, fold_conversions, cache,
+ size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
+ op1 = instantiate_scev_r (instantiate_below, evolution_loop,
+ c1, fold_conversions, cache,
+ size_expr);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (c0 != op0
+ || c1 != op1)
+ {
+ op0 = chrec_convert (type, op0, NULL);
+ op1 = chrec_convert_rhs (type, op1, NULL);
+
+ switch (code)
+ {
+ case POINTER_PLUS_EXPR:
+ case PLUS_EXPR:
+ return chrec_fold_plus (type, op0, op1);
+
+ case MINUS_EXPR:
+ return chrec_fold_minus (type, op0, op1);
+
+ case MULT_EXPR:
+ return chrec_fold_multiply (type, op0, op1);
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ return chrec ? chrec : fold_build2 (code, type, c0, c1);
+}
+
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
+ and EVOLUTION_LOOP, that were left under a symbolic form.
+
+ "CHREC" is an array reference to be instantiated.
+
+ CACHE is the cache of already instantiated values.
+
+ FOLD_CONVERSIONS should be set to true when the conversions that
+ may wrap in signed/pointer type are folded, as long as the value of
+ the chrec is preserved.
+
+ SIZE_EXPR is used for computing the size of the expression to be
+ instantiated, and to stop if it exceeds some limit. */
+
+static tree
+instantiate_array_ref (basic_block instantiate_below,
+ struct loop *evolution_loop, tree chrec,
+ bool fold_conversions, htab_t cache, int size_expr)
+{
+ tree res;
+ tree index = TREE_OPERAND (chrec, 1);
+ tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, index,
+ fold_conversions, cache, size_expr);
+
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (chrec && op1 == index)
+ return chrec;
+
+ res = unshare_expr (chrec);
+ TREE_OPERAND (res, 1) = op1;
+ return res;