VRP1 is allowed to remove a __builtin_unreachable () if it determines
that the other edge in the branch dominates all uses of all exports from
the block.
ie
<bb 3>:
x_8 = 1 << i_7;
if (x_8 <= 0) <<-- this is the branch in BB3
goto <bb 4>; [INV]
else
goto <bb 5>; [INV]
<bb 4> :
__builtin_unreachable ();
we can remove the branch and edge to bb 4 if we can prove that there
are no uses of x_8 or i_7 in or dominated by the edge 3->5. We can then
set the global ranges of i_7 and x_8 and move along.
This PR demonstrates that this normally works, but with rangers ability
to recompute values, we also have to look at the dependencies of all the
exports.
IN this case i_7 is defined:
<bb 7> :
# i_2 = PHI <i_7(5), n_4(D)(2), i_7(6)>
i_7 = i_2 + -1;
if (i_2 > 0)
goto <bb 3>; [INV]
else
goto <bb 8>; [INV]
so althoug the uses of i_7 Are dominated by 3->5, it does NOT dominate
the use of i_2 in bb_7. When early removal changes the global value of
i_7, ranger happily recomputes i_2 in the branch and decides that if i_7
is now [0, +INF], i_2 must always be > 0 and removes the branch.
Which is clearly incorrect. This patch teaches the early removal code
that it can only remove the unreachable call if x_8, i_7 and ALL the
dependencies used to calculate either name are ALL dominated by the
edge. This information is all trivially available in GORI, so its
noly a minor tweak.
Performance impact over a build of GCC is minimal. a 0.03% slowdown in VRP.
In the PR I mentioned not removing it if any of the dependencies had
more than a single use, but that turned out to be too limiting. This
solution works much better.
Bootstraps on x86_64-pc-linux-gnu with no regressions. OK?
Andrew
From ddba65ac854772f82d3acdf589e756be7ff5a1b8 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <[email protected]>
Date: Tue, 6 Jan 2026 10:14:47 -0500
Subject: [PATCH 3/3] Early builtin_unreachable removal must examine
dependencies.
Even if all uses of a name are dominated by the unreachable branch,
recomputation of a value in the defintion of a name might be reachable.
PR tree-optimization/123300
gcc/
* gimple-range-gori.cc (gori_map::exports_and_deps): New.
* gimple-range-gori.h (exports_and_deps): New prototype.
(FOR_EACH_GORI_EXPORT_AND_DEP_NAME): New macro.
* tree-vrp.cc (remove_unreachable:remove_unreachable): Initialize
m_tmp bitmap.
(remove_unreachable:~remove_unreachable): Dispose of m_tmp bitmap.
(remove_unreachable:fully_replaceable): Move from static function
and check reachability of exports and dependencies.
gcc/testsuite/
* gcc.dg/pr123300.c: New.
---
gcc/gimple-range-gori.cc | 22 ++++++++++++++++++++++
gcc/gimple-range-gori.h | 9 ++++++++-
gcc/testsuite/gcc.dg/pr123300.c | 29 +++++++++++++++++++++++++++++
gcc/tree-vrp.cc | 16 ++++++++++------
4 files changed, 69 insertions(+), 7 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr123300.c
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 4955074dece..1c0a2b9f797 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -383,6 +383,28 @@ gori_map::exports (basic_block bb)
return m_outgoing[bb->index];
}
+// Return the bitmap vector of all exports AND their dependencies from BB
+// in TMPBIT. Calculate if necessary. Return TMPBIT.
+
+bitmap
+gori_map::exports_and_deps (basic_block bb, bitmap tmpbit)
+{
+ if (bb->index >= (signed int)m_outgoing.length () || !m_outgoing[bb->index])
+ calculate_gori (bb);
+ bitmap_copy (tmpbit, m_outgoing[bb->index]);
+ if (!bitmap_empty_p (tmpbit))
+ {
+ tree name;
+ FOR_EACH_GORI_EXPORT_NAME (this, bb, name)
+ {
+ bitmap dep = get_def_chain (name);
+ if (dep)
+ bitmap_ior_into (tmpbit, dep);
+ }
+ }
+ return tmpbit;
+}
+
// Return the bitmap vector of all imports to BB. Calculate if necessary.
bitmap
diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index 787cd5be844..d562c515a28 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -99,6 +99,7 @@ public:
bool is_export_p (tree name, basic_block bb = NULL);
bool is_import_p (tree name, basic_block bb);
bitmap exports (basic_block bb);
+ bitmap exports_and_deps (basic_block bb, bitmap tmpbit);
bitmap imports (basic_block bb);
void set_range_invariant (tree name, bool invariant = true);
@@ -223,7 +224,7 @@ bool gori_on_edge (class ssa_cache &r, edge e, range_query *query = NULL);
bool gori_name_on_edge (vrange &r, tree name, edge e, range_query *q = NULL);
// For each name that is an import into BB's exports..
-#define FOR_EACH_GORI_IMPORT_NAME(gorimap, bb, name) \
+#define FOR_EACH_GORI_IMPORT_NAME(gorimap, bb, name) \
for (gori_export_iterator iter ((gorimap)->imports ((bb))); \
((name) = iter.get_name ()); \
iter.next ())
@@ -234,6 +235,12 @@ bool gori_name_on_edge (vrange &r, tree name, edge e, range_query *q = NULL);
((name) = iter.get_name ()); \
iter.next ())
+// For each name and all their dependencies possibly exported from block BB.
+#define FOR_EACH_GORI_EXPORT_AND_DEP_NAME(gorimap, bb, name, bm) \
+ for (gori_export_iterator iter ((gorimap)->exports_and_deps ((bb),(bm))); \
+ ((name) = iter.get_name ()); \
+ iter.next ())
+
// Used to assist with iterating over the GORI export list in various ways
class gori_export_iterator {
public:
diff --git a/gcc/testsuite/gcc.dg/pr123300.c b/gcc/testsuite/gcc.dg/pr123300.c
new file mode 100644
index 00000000000..7309f3dd9c0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr123300.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+[[gnu::noipa]] void
+bar (int a, int b)
+{
+ if (a < 0)
+ __builtin_abort ();
+}
+
+[[gnu::noipa]] void
+foo (int n, bool p)
+{
+ for (int i = n; i-- > 0;)
+ {
+ const int x = 1 << i;
+ if (x <= 0)
+ __builtin_unreachable ();
+ if (p)
+ bar (i, x);
+ }
+}
+
+int
+main ()
+{
+ foo (4, true);
+}
+/* { dg-final { scan-tree-dump "__builtin_unreachable" "vrp1" } } */
+
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 25e4c114c7f..bee9cd9647e 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -87,15 +87,17 @@ along with GCC; see the file COPYING3. If not see
class remove_unreachable {
public:
remove_unreachable (range_query &r, bool all) : m_ranger (r), final_p (all)
- { m_list.create (30); }
- ~remove_unreachable () { m_list.release (); }
+ { m_list.create (30); m_tmp = BITMAP_ALLOC (NULL); }
+ ~remove_unreachable () { BITMAP_FREE (m_tmp); m_list.release (); }
void handle_early (gimple *s, edge e);
void maybe_register (gimple *s);
bool remove ();
bool remove_and_update_globals ();
+ bool fully_replaceable (tree name, basic_block bb);
vec<std::pair<int, int> > m_list;
range_query &m_ranger;
bool final_p;
+ bitmap m_tmp;
};
// Check if block BB has a __builtin_unreachable () call on one arm, and
@@ -141,8 +143,8 @@ remove_unreachable::maybe_register (gimple *s)
// goto <bb 3>; [0.00%]
// Any additional use of _1 or _2 in this block invalidates early replacement.
-static bool
-fully_replaceable (tree name, basic_block bb)
+bool
+remove_unreachable::fully_replaceable (tree name, basic_block bb)
{
use_operand_p use_p;
imm_use_iterator iter;
@@ -213,9 +215,11 @@ remove_unreachable::handle_early (gimple *s, edge e)
gcc_checking_assert (gimple_outgoing_range_stmt_p (e->src) == s);
gcc_checking_assert (!final_p);
- // Check if every export use is dominated by this branch.
+ // Check if every export and its dependencies are dominated by this branch.
+ // Dependencies are required as it needs to dominate potential
+ // recalculations. See PR 123300.
tree name;
- FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori_ssa (), e->src, name)
+ FOR_EACH_GORI_EXPORT_AND_DEP_NAME (m_ranger.gori_ssa (), e->src, name, m_tmp)
{
if (!fully_replaceable (name, e->src))
return;
--
2.45.0
