+/* Allocate the one-part auxiliary data structure for VAR, with enough
+ room for COUNT dependencies. */
+
+static void
+loc_exp_dep_alloc (variable var, int count)
+{
+ size_t allocsize;
+
+ gcc_checking_assert (var->onepart);
+
+ /* We can be called with COUNT == 0 to allocate the data structure
+ without any dependencies, e.g. for the backlinks only. However,
+ if we are specifying a COUNT, then the dependency list must have
+ been emptied before. It would be possible to adjust pointers or
+ force it empty here, but this is better done at an earlier point
+ in the algorithm, so we instead leave an assertion to catch
+ errors. */
+ gcc_checking_assert (!count
+ || VEC_empty (loc_exp_dep, VAR_LOC_DEP_VEC (var)));
+
+ if (VAR_LOC_1PAUX (var)
+ && VEC_space (loc_exp_dep, VAR_LOC_DEP_VEC (var), count))
+ return;
+
+ allocsize = offsetof (struct onepart_aux, deps)
+ + VEC_embedded_size (loc_exp_dep, count);
+
+ if (VAR_LOC_1PAUX (var))
+ {
+ VAR_LOC_1PAUX (var) = XRESIZEVAR (struct onepart_aux,
+ VAR_LOC_1PAUX (var), allocsize);
+ /* If the reallocation moves the onepaux structure, the
+ back-pointer to BACKLINKS in the first list member will still
+ point to its old location. Adjust it. */
+ if (VAR_LOC_DEP_LST (var))
+ VAR_LOC_DEP_LST (var)->pprev = VAR_LOC_DEP_LSTP (var);
+ }
+ else
+ {
+ VAR_LOC_1PAUX (var) = XNEWVAR (struct onepart_aux, allocsize);
+ *VAR_LOC_DEP_LSTP (var) = NULL;
+ VAR_LOC_FROM (var) = NULL;
+ VAR_LOC_DEPTH (var) = 0;
+ }
+ VEC_embedded_init (loc_exp_dep, VAR_LOC_DEP_VEC (var), count);
+}
+
+/* Remove all entries from the vector of active dependencies of VAR,
+ removing them from the back-links lists too. */
+
+static void
+loc_exp_dep_clear (variable var)
+{
+ while (!VEC_empty (loc_exp_dep, VAR_LOC_DEP_VEC (var)))
+ {
+ loc_exp_dep *led = VEC_last (loc_exp_dep, VAR_LOC_DEP_VEC (var));
+ if (led->next)
+ led->next->pprev = led->pprev;
+ if (led->pprev)
+ *led->pprev = led->next;
+ VEC_pop (loc_exp_dep, VAR_LOC_DEP_VEC (var));
+ }
+}
+
+/* Insert an active dependency from VAR on X to the vector of
+ dependencies, and add the corresponding back-link to X's list of
+ back-links in VARS. */
+
+static void
+loc_exp_insert_dep (variable var, rtx x, htab_t vars)
+{
+ decl_or_value dv;
+ variable xvar;
+ loc_exp_dep *led;
+
+ dv = dv_from_rtx (x);
+
+ /* ??? Build a vector of variables parallel to EXPANDING, to avoid
+ an additional look up? */
+ xvar = (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv));
+
+ if (!xvar)
+ {
+ xvar = variable_from_dropped (dv, NO_INSERT);
+ gcc_checking_assert (xvar);
+ }
+
+ /* No point in adding the same backlink more than once. This may
+ arise if say the same value appears in two complex expressions in
+ the same loc_list, or even more than once in a single
+ expression. */
+ if (VAR_LOC_DEP_LST (xvar) && VAR_LOC_DEP_LST (xvar)->dv == var->dv)
+ return;
+
+ VEC_quick_push (loc_exp_dep, VAR_LOC_DEP_VEC (var), NULL);
+ led = VEC_last (loc_exp_dep, VAR_LOC_DEP_VEC (var));
+ led->dv = var->dv;
+ led->value = x;
+
+ loc_exp_dep_alloc (xvar, 0);
+ led->pprev = VAR_LOC_DEP_LSTP (xvar);
+ led->next = *led->pprev;
+ if (led->next)
+ led->next->pprev = &led->next;
+ *led->pprev = led;
+}
+
+/* Create active dependencies of VAR on COUNT values starting at
+ VALUE, and corresponding back-links to the entries in VARS. Return
+ true if we found any pending-recursion results. */
+
+static bool
+loc_exp_dep_set (variable var, rtx result, rtx *value, int count, htab_t vars)
+{
+ bool pending_recursion = false;
+
+ gcc_checking_assert (VEC_empty (loc_exp_dep, VAR_LOC_DEP_VEC (var)));
+
+ /* Set up all dependencies from last_child (as set up at the end of
+ the loop above) to the end. */
+ loc_exp_dep_alloc (var, count);
+
+ while (count--)
+ {
+ rtx x = *value++;
+
+ if (!pending_recursion)
+ pending_recursion = !result && VALUE_RECURSED_INTO (x);
+
+ loc_exp_insert_dep (var, x, vars);
+ }
+
+ return pending_recursion;
+}
+
+/* Notify the back-links of IVAR that are pending recursion that we
+ have found a non-NIL value for it, so they are cleared for another
+ attempt to compute a current location. */
+
+static void
+notify_dependents_of_resolved_value (variable ivar, htab_t vars)
+{
+ loc_exp_dep *led, *next;
+
+ for (led = VAR_LOC_DEP_LST (ivar); led; led = next)
+ {
+ decl_or_value dv = led->dv;
+ variable var;
+
+ next = led->next;
+
+ if (dv_is_value_p (dv))
+ {
+ rtx value = dv_as_value (dv);
+
+ /* If we have already resolved it, leave it alone. */
+ if (!VALUE_RECURSED_INTO (value))
+ continue;
+
+ /* Check that VALUE_RECURSED_INTO, true from the test above,
+ implies NO_LOC_P. */
+ gcc_checking_assert (NO_LOC_P (value));
+
+ /* We won't notify variables that are being expanded,
+ because their dependency list is cleared before
+ recursing. */
+ NO_LOC_P (value) = false;
+ VALUE_RECURSED_INTO (value) = false;
+
+ gcc_checking_assert (dv_changed_p (dv));
+ }
+ else if (!dv_changed_p (dv))
+ continue;
+
+ var = (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv));
+
+ if (!var)
+ var = variable_from_dropped (dv, NO_INSERT);
+
+ if (var)
+ notify_dependents_of_resolved_value (var, vars);
+
+ if (next)
+ next->pprev = led->pprev;
+ if (led->pprev)
+ *led->pprev = next;
+ led->next = NULL;
+ led->pprev = NULL;
+ }
+}
+
+static rtx vt_expand_loc_callback (rtx x, bitmap regs,
+ int max_depth, void *data);
+
+/* Return the combined depth, when one sub-expression evaluated to
+ BEST_DEPTH and the previous known depth was SAVED_DEPTH. */
+
+static inline int
+update_depth (int saved_depth, int best_depth)
+{
+ /* If we didn't find anything, stick with what we had. */
+ if (!best_depth)
+ return saved_depth;
+
+ /* If we found hadn't found anything, use the depth of the current
+ expression. Do NOT add one extra level, we want to compute the
+ maximum depth among sub-expressions. We'll increment it later,
+ if appropriate. */
+ if (!saved_depth)
+ return best_depth;
+
+ if (saved_depth < best_depth)
+ return best_depth;
+ else
+ return saved_depth;
+}
+
+/* Expand VAR to a location RTX, updating its cur_loc. Use REGS and
+ DATA for cselib expand callback. If PENDRECP is given, indicate in
+ it whether any sub-expression couldn't be fully evaluated because
+ it is pending recursion resolution. */
+
+static inline rtx
+vt_expand_var_loc_chain (variable var, bitmap regs, void *data, bool *pendrecp)
+{
+ struct expand_loc_callback_data *elcd
+ = (struct expand_loc_callback_data *) data;
+ location_chain loc, next;
+ rtx result = NULL;
+ int first_child, result_first_child, last_child;
+ bool pending_recursion;
+ rtx loc_from = NULL;
+ struct elt_loc_list *cloc = NULL;
+ int depth = 0, saved_depth = elcd->depth;
+
+ /* Clear all backlinks pointing at this, so that we're not notified
+ while we're active. */
+ loc_exp_dep_clear (var);
+
+ if (var->onepart == ONEPART_VALUE)
+ {
+ cselib_val *val = CSELIB_VAL_PTR (dv_as_value (var->dv));
+
+ gcc_checking_assert (cselib_preserved_value_p (val));
+
+ cloc = val->locs;
+ }
+
+ first_child = result_first_child = last_child
+ = VEC_length (rtx, elcd->expanding);
+
+ /* Attempt to expand each available location in turn. */
+ for (next = loc = var->n_var_parts ? var->var_part[0].loc_chain : NULL;
+ loc || cloc; loc = next)
+ {
+ result_first_child = last_child;
+
+ if (!loc || (GET_CODE (loc->loc) == ENTRY_VALUE && cloc))
+ {
+ loc_from = cloc->loc;
+ next = loc;
+ cloc = cloc->next;
+ if (unsuitable_loc (loc_from))
+ continue;
+ }
+ else
+ {
+ loc_from = loc->loc;
+ next = loc->next;
+ }
+
+ gcc_checking_assert (!unsuitable_loc (loc_from));
+
+ elcd->depth = 0;
+ result = cselib_expand_value_rtx_cb (loc_from, regs, EXPR_DEPTH,
+ vt_expand_loc_callback, data);
+ last_child = VEC_length (rtx, elcd->expanding);
+
+ if (result)
+ {
+ depth = elcd->depth;
+
+ gcc_checking_assert (depth || result_first_child == last_child);
+
+ if (last_child - result_first_child != 1)
+ depth++;
+
+ if (depth <= EXPR_USE_DEPTH)
+ break;
+
+ result = NULL;
+ }
+
+ /* Set it up in case we leave the loop. */
+ depth = 0;
+ loc_from = NULL;
+ result_first_child = first_child;
+ }
+
+ /* Register all encountered dependencies as active. */
+ pending_recursion = loc_exp_dep_set
+ (var, result, VEC_address (rtx, elcd->expanding) + result_first_child,
+ last_child - result_first_child, elcd->vars);
+
+ VEC_truncate (rtx, elcd->expanding, first_child);
+
+ /* Record where the expansion came from. */
+ gcc_checking_assert (!result || !pending_recursion);
+ VAR_LOC_FROM (var) = loc_from;
+ VAR_LOC_DEPTH (var) = depth;
+
+ gcc_checking_assert (!depth == !result);
+
+ elcd->depth = update_depth (saved_depth, depth);
+
+ /* Indicate whether any of the dependencies are pending recursion
+ resolution. */
+ if (pendrecp)
+ *pendrecp = pending_recursion;
+
+ if (!pendrecp || !pending_recursion)
+ var->var_part[0].cur_loc = result;
+
+ return result;
+}
+