@@ -276,8 +276,6 @@ void
path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
{
tree name = gimple_phi_result (phi);
- basic_block bb = gimple_bb (phi);
- unsigned nargs = gimple_phi_num_args (phi);
if (at_entry ())
{
@@ -287,6 +285,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
// Try to fold the phi exclusively with global or cached values.
// This will get things like PHI <5(99), 6(88)>. We do this by
// calling range_of_expr with no context.
+ unsigned nargs = gimple_phi_num_args (phi);
Value_Range arg_range (TREE_TYPE (name));
r.set_undefined ();
for (size_t i = 0; i < nargs; ++i)
@@ -303,36 +302,31 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
return;
}
+ basic_block bb = gimple_bb (phi);
basic_block prev = prev_bb ();
edge e_in = find_edge (prev, bb);
-
- for (size_t i = 0; i < nargs; ++i)
- if (e_in == gimple_phi_arg_edge (phi, i))
- {
- tree arg = gimple_phi_arg_def (phi, i);
- // Avoid using the cache for ARGs defined in this block, as
- // that could create an ordering problem.
- if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg))
- {
- if (m_resolve)
- {
- Value_Range tmp (TREE_TYPE (name));
- // Using both the range on entry to the path, and the
- // range on this edge yields significantly better
- // results.
- if (defined_outside_path (arg))
- range_on_path_entry (r, arg);
- else
- r.set_varying (TREE_TYPE (name));
- m_ranger->range_on_edge (tmp, e_in, arg);
- r.intersect (tmp);
- return;
- }
+ tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_in);
+ // Avoid using the cache for ARGs defined in this block, as
+ // that could create an ordering problem.
+ if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg))
+ {
+ if (m_resolve)
+ {
+ Value_Range tmp (TREE_TYPE (name));
+ // Using both the range on entry to the path, and the
+ // range on this edge yields significantly better
+ // results.
+ if (TREE_CODE (arg) == SSA_NAME
+ && defined_outside_path (arg))
+ range_on_path_entry (r, arg);
+ else
r.set_varying (TREE_TYPE (name));
- }
- return;
- }
- gcc_unreachable ();
+ m_ranger->range_on_edge (tmp, e_in, arg);
+ r.intersect (tmp);
+ return;
+ }
+ r.set_varying (TREE_TYPE (name));
+ }
}
// If NAME is defined in BB, set R to the range of NAME, and return
@@ -482,32 +482,76 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
{
// For further greedy searching we want to remove interesting
// names defined in BB but add ones on the PHI edges for the
- // respective edges. We do this by starting with all names
+ // respective edges and adding imports from those stmts.
+ // We do this by starting with all names
// not defined in BB as interesting, collecting a list of
// interesting PHIs in BB on the fly. Then we iterate over
// predecessor edges, adding interesting PHI edge defs to
// the set of interesting names to consider when processing it.
auto_bitmap new_interesting;
+ auto_vec<int, 16> new_imports;
auto_vec<gphi *, 4> interesting_phis;
bitmap_iterator bi;
unsigned i;
+ auto_vec<tree, 16> worklist;
EXECUTE_IF_SET_IN_BITMAP (interesting, 0, i, bi)
{
tree name = ssa_name (i);
gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+ /* Imports remain interesting. */
if (gimple_bb (def_stmt) != bb)
- bitmap_set_bit (new_interesting, i);
- else if (gphi *phi = dyn_cast<gphi *> (def_stmt))
{
- tree res = gimple_phi_result (phi);
- if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (res))
- interesting_phis.safe_push (phi);
+ bitmap_set_bit (new_interesting, i);
+ continue;
+ }
+ worklist.quick_push (name);
+ while (!worklist.is_empty ())
+ {
+ tree name = worklist.pop ();
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+ /* Newly discovered imports are interesting. */
+ if (gimple_bb (def_stmt) != bb)
+ {
+ bitmap_set_bit (new_interesting, SSA_NAME_VERSION (name));
+ continue;
+ }
+ /* Local PHIs participate in renaming below. */
+ if (gphi *phi = dyn_cast<gphi *> (def_stmt))
+ {
+ tree res = gimple_phi_result (phi);
+ if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (res))
+ interesting_phis.safe_push (phi);
+ }
+ /* For other local defs process their uses, amending
+ imports on the way. */
+ else if (is_gimple_assign (def_stmt))
+ {
+ for (unsigned j = 1; j < gimple_num_ops (def_stmt); ++j)
+ {
+ tree rhs = gimple_op (def_stmt, j);
+ if (TREE_CODE (rhs) == SSA_NAME
+ && bitmap_set_bit (m_imports,
+ SSA_NAME_VERSION (rhs)))
+ {
+ /* ??? We probably want to track a 'visited'
+ flag separately and add to imports only
+ when the def is handled by ranger. The
+ current way adds us defs that are neither
+ PHIs nor "interesting" assigns, like for
+ example loads. */
+ new_imports.safe_push (SSA_NAME_VERSION (rhs));
+ worklist.safe_push (rhs);
+ }
+ }
+ }
}
}
+ worklist.release ();
if (!bitmap_empty_p (new_interesting)
|| !interesting_phis.is_empty ())
{
- auto_vec<tree, 4> unwind (interesting_phis.length ());
+ auto_vec<int, 4> unwind (interesting_phis.length ());
+ auto_vec<int, 4> imports_unwind (interesting_phis.length ());
edge_iterator iter;
edge e;
FOR_EACH_EDGE (e, iter, bb->preds)
@@ -525,22 +569,31 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
{
tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
if (TREE_CODE (def) == SSA_NAME)
- if (bitmap_set_bit (new_interesting,
- SSA_NAME_VERSION (def)))
- {
- bitmap_set_bit (m_imports, SSA_NAME_VERSION (def));
- unwind.quick_push (def);
- }
+ {
+ int ver = SSA_NAME_VERSION (def);
+ if (bitmap_set_bit (new_interesting, ver))
+ {
+ if (bitmap_set_bit (m_imports, ver))
+ imports_unwind.quick_push (ver);
+ unwind.quick_push (ver);
+ }
+ }
}
find_paths_to_names (e->src, new_interesting, overall_paths);
- // Restore new_interesting. We leave m_imports alone since
- // we do not prune defs in BB from it and separately keeping
- // track of which bits to unwind isn't worth the trouble.
- for (tree def : unwind)
- bitmap_clear_bit (new_interesting, SSA_NAME_VERSION (def));
+ // Restore new_interesting.
+ for (int def : unwind)
+ bitmap_clear_bit (new_interesting, def);
unwind.truncate (0);
+ // Restore and m_imports.
+ for (int def : imports_unwind)
+ bitmap_clear_bit (m_imports, def);
+ imports_unwind.truncate (0);
}
}
+ /* m_imports tracks all interesting names on the path, so when
+ backtracking we have to restore it. */
+ for (int j : new_imports)
+ bitmap_clear_bit (m_imports, j);
}
else if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " FAIL: Search space limit %d reached.\n",
@@ -566,15 +619,24 @@ back_threader::find_paths (basic_block bb, tree name)
&& gimple_code (stmt) != GIMPLE_SWITCH))
return;
- if (EDGE_COUNT (bb->succs) > 1
- || single_succ_to_potentially_threadable_block (bb))
+ if (EDGE_COUNT (bb->succs) > 1)
{
m_last_stmt = stmt;
m_visited_bbs.empty ();
m_path.truncate (0);
m_name = name;
- m_solver->compute_imports (m_imports, bb);
+ // We compute imports of the path during discovery starting
+ // just with names used in the conditional.
+ bitmap_clear (m_imports);
+ ssa_op_iter iter;
+ FOR_EACH_SSA_TREE_OPERAND (name, stmt, iter, SSA_OP_USE)
+ bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
+
+ // Interesting is the set of imports we still not have see
+ // the definition of. So while imports only grow, the
+ // set of interesting defs dwindles and once empty we can
+ // stop searching.
auto_bitmap interesting;
bitmap_copy (interesting, m_imports);
find_paths_to_names (bb, interesting, 1);