* [PATCH 1/7] Allocate non_null_ref tables at creation.
2021-09-21 16:53 [PATCH 0/7] Add ability to resolve unknowns to path solver Aldy Hernandez
@ 2021-09-21 16:53 ` Aldy Hernandez
2021-09-21 16:53 ` [PATCH 2/7] Do not query SCEV in range_of_phi unless dominators are available Aldy Hernandez
` (5 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Aldy Hernandez @ 2021-09-21 16:53 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: GCC patches, Jeff Law, Aldy Hernandez
Preallocating the space is slightly cheaper than calling
safe_grow_cleared.
Committed.
gcc/ChangeLog:
* gimple-range-cache.cc (non_null_ref::non_null_ref): Use create
and quick_grow_cleared instead of safe_grow_cleared.
---
gcc/gimple-range-cache.cc | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index fbf0f95eef9..b856b212169 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -37,8 +37,8 @@ along with GCC; see the file COPYING3. If not see
non_null_ref::non_null_ref ()
{
- m_nn.create (0);
- m_nn.safe_grow_cleared (num_ssa_names);
+ m_nn.create (num_ssa_names);
+ m_nn.quick_grow_cleared (num_ssa_names);
bitmap_obstack_initialize (&m_bitmaps);
}
--
2.31.1
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH 2/7] Do not query SCEV in range_of_phi unless dominators are available.
2021-09-21 16:53 [PATCH 0/7] Add ability to resolve unknowns to path solver Aldy Hernandez
2021-09-21 16:53 ` [PATCH 1/7] Allocate non_null_ref tables at creation Aldy Hernandez
@ 2021-09-21 16:53 ` Aldy Hernandez
2021-09-21 17:05 ` Andrew MacLeod
2021-09-21 16:53 ` [PATCH 3/7] Move postfold_gcond_edges into fur_source Aldy Hernandez
` (4 subsequent siblings)
6 siblings, 1 reply; 12+ messages in thread
From: Aldy Hernandez @ 2021-09-21 16:53 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: GCC patches, Jeff Law, Aldy Hernandez
SCEV won't work without dominators and we can get called without
dominators from debug_ranger.
Another option would be to rename scev_initialized_p to something like
scev_available_p and move the check there. For now, this will do.
Committed.
gcc/ChangeLog:
* gimple-range-fold.cc (fold_using_range::range_of_phi): Check
dom_info_available_p.
---
gcc/gimple-range-fold.cc | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 997d02dd4b9..4dbf4188ec2 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -781,7 +781,9 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src)
}
// If SCEV is available, query if this PHI has any knonwn values.
- if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
+ if (dom_info_available_p (CDI_DOMINATORS)
+ && scev_initialized_p ()
+ && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
{
value_range loop_range;
class loop *l = loop_containing_stmt (phi);
--
2.31.1
^ permalink raw reply [flat|nested] 12+ messages in thread* Re: [PATCH 2/7] Do not query SCEV in range_of_phi unless dominators are available.
2021-09-21 16:53 ` [PATCH 2/7] Do not query SCEV in range_of_phi unless dominators are available Aldy Hernandez
@ 2021-09-21 17:05 ` Andrew MacLeod
2021-09-21 17:16 ` Aldy Hernandez
0 siblings, 1 reply; 12+ messages in thread
From: Andrew MacLeod @ 2021-09-21 17:05 UTC (permalink / raw)
To: Aldy Hernandez; +Cc: GCC patches, Jeff Law
On 9/21/21 12:53 PM, Aldy Hernandez wrote:
> SCEV won't work without dominators and we can get called without
> dominators from debug_ranger.
>
> Another option would be to rename scev_initialized_p to something like
> scev_available_p and move the check there. For now, this will do.
>
> Committed.
>
> gcc/ChangeLog:
>
> * gimple-range-fold.cc (fold_using_range::range_of_phi): Check
> dom_info_available_p.
> ---
> gcc/gimple-range-fold.cc | 4 +++-
> 1 file changed, 3 insertions(+), 1 deletion(-)
>
> diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
> index 997d02dd4b9..4dbf4188ec2 100644
> --- a/gcc/gimple-range-fold.cc
> +++ b/gcc/gimple-range-fold.cc
> @@ -781,7 +781,9 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src)
> }
>
> // If SCEV is available, query if this PHI has any knonwn values.
> - if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
> + if (dom_info_available_p (CDI_DOMINATORS)
> + && scev_initialized_p ()
> + && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
> {
> value_range loop_range;
> class loop *l = loop_containing_stmt (phi);
Im confused.. if scev doesn't work without dominators, how is
scev_initialized_p() true if there are no dominators? Are we
initializing it somewhere without dominators? Maybe there should be a
check in the scev init routine? seems like something else is amok.
void
scev_initialize (void)
{
gcc_assert (! scev_initialized_p ());
scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
for (auto loop : loops_list (cfun, 0))
loop->nb_iterations = NULL_TREE;
}
/* Return true if SCEV is initialized. */
bool
scev_initialized_p (void)
{
return scalar_evolution_info != NULL;
}
^ permalink raw reply [flat|nested] 12+ messages in thread* Re: [PATCH 2/7] Do not query SCEV in range_of_phi unless dominators are available.
2021-09-21 17:05 ` Andrew MacLeod
@ 2021-09-21 17:16 ` Aldy Hernandez
2021-09-22 8:05 ` Richard Biener
0 siblings, 1 reply; 12+ messages in thread
From: Aldy Hernandez @ 2021-09-21 17:16 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: GCC patches, Jeff Law
On 9/21/21 7:05 PM, Andrew MacLeod wrote:
> On 9/21/21 12:53 PM, Aldy Hernandez wrote:
>> SCEV won't work without dominators and we can get called without
>> dominators from debug_ranger.
>>
>> Another option would be to rename scev_initialized_p to something like
>> scev_available_p and move the check there. For now, this will do.
>>
>> Committed.
>>
>> gcc/ChangeLog:
>>
>> * gimple-range-fold.cc (fold_using_range::range_of_phi): Check
>> dom_info_available_p.
>> ---
>> gcc/gimple-range-fold.cc | 4 +++-
>> 1 file changed, 3 insertions(+), 1 deletion(-)
>>
>> diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
>> index 997d02dd4b9..4dbf4188ec2 100644
>> --- a/gcc/gimple-range-fold.cc
>> +++ b/gcc/gimple-range-fold.cc
>> @@ -781,7 +781,9 @@ fold_using_range::range_of_phi (irange &r, gphi
>> *phi, fur_source &src)
>> }
>> // If SCEV is available, query if this PHI has any knonwn values.
>> - if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
>> + if (dom_info_available_p (CDI_DOMINATORS)
>> + && scev_initialized_p ()
>> + && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
>> {
>> value_range loop_range;
>> class loop *l = loop_containing_stmt (phi);
>
> Im confused.. if scev doesn't work without dominators, how is
> scev_initialized_p() true if there are no dominators? Are we
> initializing it somewhere without dominators? Maybe there should be a
> check in the scev init routine? seems like something else is amok.
As I mentioned, this can happen from debug_ranger(), which is a
debugging construct, and I've been known to call it without dominators
:). And yes, I agree we could move it to scev_initialized_p.
Aldy
>
>
> void
> scev_initialize (void)
> {
> gcc_assert (! scev_initialized_p ());
>
> scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
>
> for (auto loop : loops_list (cfun, 0))
> loop->nb_iterations = NULL_TREE;
> }
>
> /* Return true if SCEV is initialized. */
>
> bool
> scev_initialized_p (void)
> {
> return scalar_evolution_info != NULL;
> }
>
>
^ permalink raw reply [flat|nested] 12+ messages in thread* Re: [PATCH 2/7] Do not query SCEV in range_of_phi unless dominators are available.
2021-09-21 17:16 ` Aldy Hernandez
@ 2021-09-22 8:05 ` Richard Biener
2021-09-23 11:07 ` Aldy Hernandez
0 siblings, 1 reply; 12+ messages in thread
From: Richard Biener @ 2021-09-22 8:05 UTC (permalink / raw)
To: Aldy Hernandez; +Cc: Andrew MacLeod, GCC patches
On Tue, Sep 21, 2021 at 7:17 PM Aldy Hernandez via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
>
>
> On 9/21/21 7:05 PM, Andrew MacLeod wrote:
> > On 9/21/21 12:53 PM, Aldy Hernandez wrote:
> >> SCEV won't work without dominators and we can get called without
> >> dominators from debug_ranger.
> >>
> >> Another option would be to rename scev_initialized_p to something like
> >> scev_available_p and move the check there. For now, this will do.
> >>
> >> Committed.
> >>
> >> gcc/ChangeLog:
> >>
> >> * gimple-range-fold.cc (fold_using_range::range_of_phi): Check
> >> dom_info_available_p.
> >> ---
> >> gcc/gimple-range-fold.cc | 4 +++-
> >> 1 file changed, 3 insertions(+), 1 deletion(-)
> >>
> >> diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
> >> index 997d02dd4b9..4dbf4188ec2 100644
> >> --- a/gcc/gimple-range-fold.cc
> >> +++ b/gcc/gimple-range-fold.cc
> >> @@ -781,7 +781,9 @@ fold_using_range::range_of_phi (irange &r, gphi
> >> *phi, fur_source &src)
> >> }
> >> // If SCEV is available, query if this PHI has any knonwn values.
> >> - if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
> >> + if (dom_info_available_p (CDI_DOMINATORS)
> >> + && scev_initialized_p ()
> >> + && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
> >> {
> >> value_range loop_range;
> >> class loop *l = loop_containing_stmt (phi);
> >
> > Im confused.. if scev doesn't work without dominators, how is
> > scev_initialized_p() true if there are no dominators? Are we
> > initializing it somewhere without dominators? Maybe there should be a
> > check in the scev init routine? seems like something else is amok.
>
> As I mentioned, this can happen from debug_ranger(), which is a
> debugging construct, and I've been known to call it without dominators
> :). And yes, I agree we could move it to scev_initialized_p.
But why is scev_initialized_p () true from debug_ranger()?
> Aldy
>
> >
> >
> > void
> > scev_initialize (void)
> > {
> > gcc_assert (! scev_initialized_p ());
> >
> > scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
> >
> > for (auto loop : loops_list (cfun, 0))
> > loop->nb_iterations = NULL_TREE;
> > }
> >
> > /* Return true if SCEV is initialized. */
> >
> > bool
> > scev_initialized_p (void)
> > {
> > return scalar_evolution_info != NULL;
> > }
> >
> >
>
^ permalink raw reply [flat|nested] 12+ messages in thread* Re: [PATCH 2/7] Do not query SCEV in range_of_phi unless dominators are available.
2021-09-22 8:05 ` Richard Biener
@ 2021-09-23 11:07 ` Aldy Hernandez
0 siblings, 0 replies; 12+ messages in thread
From: Aldy Hernandez @ 2021-09-23 11:07 UTC (permalink / raw)
To: Richard Biener; +Cc: Andrew MacLeod, GCC patches
[-- Attachment #1: Type: text/plain, Size: 2242 bytes --]
On 9/22/21 10:05 AM, Richard Biener wrote:
> On Tue, Sep 21, 2021 at 7:17 PM Aldy Hernandez via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>>
>>
>>
>> On 9/21/21 7:05 PM, Andrew MacLeod wrote:
>>> On 9/21/21 12:53 PM, Aldy Hernandez wrote:
>>>> SCEV won't work without dominators and we can get called without
>>>> dominators from debug_ranger.
>>>>
>>>> Another option would be to rename scev_initialized_p to something like
>>>> scev_available_p and move the check there. For now, this will do.
>>>>
>>>> Committed.
>>>>
>>>> gcc/ChangeLog:
>>>>
>>>> * gimple-range-fold.cc (fold_using_range::range_of_phi): Check
>>>> dom_info_available_p.
>>>> ---
>>>> gcc/gimple-range-fold.cc | 4 +++-
>>>> 1 file changed, 3 insertions(+), 1 deletion(-)
>>>>
>>>> diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
>>>> index 997d02dd4b9..4dbf4188ec2 100644
>>>> --- a/gcc/gimple-range-fold.cc
>>>> +++ b/gcc/gimple-range-fold.cc
>>>> @@ -781,7 +781,9 @@ fold_using_range::range_of_phi (irange &r, gphi
>>>> *phi, fur_source &src)
>>>> }
>>>> // If SCEV is available, query if this PHI has any knonwn values.
>>>> - if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
>>>> + if (dom_info_available_p (CDI_DOMINATORS)
>>>> + && scev_initialized_p ()
>>>> + && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
>>>> {
>>>> value_range loop_range;
>>>> class loop *l = loop_containing_stmt (phi);
>>>
>>> Im confused.. if scev doesn't work without dominators, how is
>>> scev_initialized_p() true if there are no dominators? Are we
>>> initializing it somewhere without dominators? Maybe there should be a
>>> check in the scev init routine? seems like something else is amok.
>>
>> As I mentioned, this can happen from debug_ranger(), which is a
>> debugging construct, and I've been known to call it without dominators
>> :). And yes, I agree we could move it to scev_initialized_p.
>
> But why is scev_initialized_p () true from debug_ranger()?
This seems to be an artifact of some internal diagnostic code I had
comparing the new work with the ASSERT_EXPR threads. I've reverted the
patch.
Sorry for the noise, and thanks for pointing it out.
Aldy
[-- Attachment #2: p.patch --]
[-- Type: text/x-patch, Size: 1401 bytes --]
commit e7797033a8f2bd9bcf455d796178f5c14d457513
Author: Aldy Hernandez <aldyh@redhat.com>
Date: Thu Sep 23 09:40:59 2021 +0200
Remove dominator check in fold_using_range::range_of_phi.
Revert the following patch, as it was an artifact of diagnostic code
being run with improper IL.
commit 64b80b8819f9ea74712625bceb0ec4388e25f67d
Author: Aldy Hernandez <aldyh@redhat.com>
Date: Tue Sep 21 08:28:28 2021 +0200
Do not query SCEV in range_of_phi unless dominators are available.
SCEV won't work without dominators and we can get called without
dominators from debug_ranger.
gcc/ChangeLog:
* gimple-range-fold.cc (fold_using_range::range_of_phi):
Remove dominator check.
diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 1da1befa9a2..35324fd72c2 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -826,9 +826,7 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src)
}
// If SCEV is available, query if this PHI has any knonwn values.
- if (dom_info_available_p (CDI_DOMINATORS)
- && scev_initialized_p ()
- && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
+ if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
{
value_range loop_range;
class loop *l = loop_containing_stmt (phi);
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 3/7] Move postfold_gcond_edges into fur_source.
2021-09-21 16:53 [PATCH 0/7] Add ability to resolve unknowns to path solver Aldy Hernandez
2021-09-21 16:53 ` [PATCH 1/7] Allocate non_null_ref tables at creation Aldy Hernandez
2021-09-21 16:53 ` [PATCH 2/7] Do not query SCEV in range_of_phi unless dominators are available Aldy Hernandez
@ 2021-09-21 16:53 ` Aldy Hernandez
2021-09-21 16:53 ` [PATCH 4/7] path solver: Add relation support Aldy Hernandez
` (3 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Aldy Hernandez @ 2021-09-21 16:53 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: GCC patches, Jeff Law, Aldy Hernandez
The code registering outgoing edges from a cond is living in
fold_using_range, which makes it difficult to be called from other
places. Also, it refuses to register relations on the outgoing
destinations that have more than one predecessor. This latter issue is
a problem because we would like to register outgoing edges along a path
in the path solver (regardless of single_pred_p).
Committed.
gcc/ChangeLog:
* gimple-range-fold.cc (fold_using_range::range_of_range_op):
Rename postfold_gcond_edges to register_outgoing_edges and
adapt.
(fold_using_range::postfold_gcond_edges): Rename...
(fur_source::register_outgoing_edges): ...to this.
* gimple-range-fold.h (postfold_gcond_edges): Rename to
register_outgoing_edges and move to fur_source.
---
gcc/gimple-range-fold.cc | 44 ++++++++++++++++++++--------------------
gcc/gimple-range-fold.h | 2 +-
2 files changed, 23 insertions(+), 23 deletions(-)
diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 4dbf4188ec2..921e8e3388f 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -651,7 +651,17 @@ fold_using_range::range_of_range_op (irange &r, gimple *s, fur_source &src)
}
}
else if (is_a<gcond *> (s))
- postfold_gcond_edges (as_a<gcond *> (s), r, src);
+ {
+ basic_block bb = gimple_bb (s);
+ edge e0 = EDGE_SUCC (bb, 0);
+ edge e1 = EDGE_SUCC (bb, 1);
+
+ if (!single_pred_p (e0->dest))
+ e0 = NULL;
+ if (!single_pred_p (e1->dest))
+ e1 = NULL;
+ src.register_outgoing_edges (as_a<gcond *> (s), r, e0, e1);
+ }
}
else
r.set_varying (type);
@@ -1353,8 +1363,7 @@ fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s,
// Register any outgoing edge relations from a conditional branch.
void
-fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range,
- fur_source &src)
+fur_source::register_outgoing_edges (gcond *s, irange &lhs_range, edge e0, edge e1)
{
int_range_max r;
int_range<2> e0_range, e1_range;
@@ -1366,10 +1375,7 @@ fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range,
if (!bb)
return;
- edge e0 = EDGE_SUCC (bb, 0);
- if (!single_pred_p (e0->dest))
- e0 = NULL;
- else
+ if (e0)
{
// If this edge is never taken, ignore it.
gcond_edge_range (e0_range, e0);
@@ -1379,10 +1385,7 @@ fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range,
}
- edge e1 = EDGE_SUCC (bb, 1);
- if (!single_pred_p (e1->dest))
- e1 = NULL;
- else
+ if (e1)
{
// If this edge is never taken, ignore it.
gcond_edge_range (e1_range, e1);
@@ -1391,7 +1394,6 @@ fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range,
e1 = NULL;
}
- // At least one edge needs to be single pred.
if (!e0 && !e1)
return;
@@ -1407,27 +1409,25 @@ fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range,
{
relation_kind relation = handler->op1_op2_relation (e0_range);
if (relation != VREL_NONE)
- src.register_relation (e0, relation, ssa1, ssa2);
+ register_relation (e0, relation, ssa1, ssa2);
}
if (e1)
{
relation_kind relation = handler->op1_op2_relation (e1_range);
if (relation != VREL_NONE)
- src.register_relation (e1, relation, ssa1, ssa2);
+ register_relation (e1, relation, ssa1, ssa2);
}
}
// Outgoing relations of GORI exports require a gori engine.
- if (!src.gori ())
+ if (!gori ())
return;
- range_query *q = src.query ();
// Now look for other relations in the exports. This will find stmts
// leading to the condition such as:
// c_2 = a_4 < b_7
// if (c_2)
-
- FOR_EACH_GORI_EXPORT_NAME (*(src.gori ()), bb, name)
+ FOR_EACH_GORI_EXPORT_NAME (*(gori ()), bb, name)
{
if (TREE_CODE (TREE_TYPE (name)) != BOOLEAN_TYPE)
continue;
@@ -1439,19 +1439,19 @@ fold_using_range::postfold_gcond_edges (gcond *s, irange& lhs_range,
tree ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt));
if (ssa1 && ssa2)
{
- if (e0 && src.gori ()->outgoing_edge_range_p (r, e0, name, *q)
+ if (e0 && gori ()->outgoing_edge_range_p (r, e0, name, *m_query)
&& r.singleton_p ())
{
relation_kind relation = handler->op1_op2_relation (r);
if (relation != VREL_NONE)
- src.register_relation (e0, relation, ssa1, ssa2);
+ register_relation (e0, relation, ssa1, ssa2);
}
- if (e1 && src.gori ()->outgoing_edge_range_p (r, e1, name, *q)
+ if (e1 && gori ()->outgoing_edge_range_p (r, e1, name, *m_query)
&& r.singleton_p ())
{
relation_kind relation = handler->op1_op2_relation (r);
if (relation != VREL_NONE)
- src.register_relation (e1, relation, ssa1, ssa2);
+ register_relation (e1, relation, ssa1, ssa2);
}
}
}
diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h
index ceed7ba48e1..d62d29b7133 100644
--- a/gcc/gimple-range-fold.h
+++ b/gcc/gimple-range-fold.h
@@ -129,6 +129,7 @@ public:
tree op2);
virtual void register_relation (edge e, relation_kind k, tree op1,
tree op2);
+ void register_outgoing_edges (gcond *, irange &lhs_range, edge e0, edge e1);
protected:
range_query *m_query;
gori_compute *m_gori;
@@ -188,6 +189,5 @@ protected:
void range_of_ssa_name_with_loop_info (irange &, tree, class loop *, gphi *,
fur_source &src);
void relation_fold_and_or (irange& lhs_range, gimple *s, fur_source &src);
- void postfold_gcond_edges (gcond *s, irange &lhs_range, fur_source &src);
};
#endif // GCC_GIMPLE_RANGE_FOLD_H
--
2.31.1
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH 4/7] path solver: Add relation support.
2021-09-21 16:53 [PATCH 0/7] Add ability to resolve unknowns to path solver Aldy Hernandez
` (2 preceding siblings ...)
2021-09-21 16:53 ` [PATCH 3/7] Move postfold_gcond_edges into fur_source Aldy Hernandez
@ 2021-09-21 16:53 ` Aldy Hernandez
2021-09-21 16:53 ` [PATCH 5/7] path solver: Remove useless code Aldy Hernandez
` (2 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Aldy Hernandez @ 2021-09-21 16:53 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: GCC patches, Jeff Law, Aldy Hernandez
This patch adds relational support to the path solver. It uses a
path_oracle that keeps track of relations within a path which are
augmented by relations on entry to the path. With it, range_of_stmt,
range_of_expr, and friends can give relation aware answers.
Committed.
gcc/ChangeLog:
* gimple-range-fold.h (class fur_source): Make oracle protected.
* gimple-range-path.cc (path_range_query::path_range_query): Add
resolve argument. Initialize oracle.
(path_range_query::~path_range_query): Delete oracle.
(path_range_query::range_of_stmt): Adapt to use relations.
(path_range_query::precompute_ranges): Pre-compute relations.
(class jt_fur_source): New
(jt_fur_source::jt_fur_source): New.
(jt_fur_source::register_relation): New.
(jt_fur_source::query_relation): New.
(path_range_query::precompute_relations): New.
(path_range_query::precompute_phi_relations): New.
* gimple-range-path.h (path_range_query): Add resolve argument.
Add oracle, precompute_relations, precompute_phi_relations.
* tree-ssa-threadbackward.c (back_threader::back_threader): Pass
resolve argument to solver.
---
gcc/gimple-range-fold.h | 2 +-
gcc/gimple-range-path.cc | 204 +++++++++++++++++++++++++++++++---
gcc/gimple-range-path.h | 15 ++-
gcc/tree-ssa-threadbackward.c | 2 +-
4 files changed, 200 insertions(+), 23 deletions(-)
diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h
index d62d29b7133..bc0874b5f31 100644
--- a/gcc/gimple-range-fold.h
+++ b/gcc/gimple-range-fold.h
@@ -160,7 +160,7 @@ public:
tree op2) OVERRIDE;
virtual void register_relation (edge e, relation_kind k, tree op1,
tree op2) OVERRIDE;
-private:
+protected:
relation_oracle *m_oracle;
};
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 10b018b5211..b3040c9bc00 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -30,11 +30,13 @@ along with GCC; see the file COPYING3. If not see
#include "tree-pretty-print.h"
#include "gimple-range-path.h"
#include "ssa.h"
+#include "tree-cfg.h"
+#include "gimple-iterator.h"
// Internal construct to help facilitate debugging of solver.
#define DEBUG_SOLVER (0 && dump_file)
-path_range_query::path_range_query (gimple_ranger &ranger)
+path_range_query::path_range_query (gimple_ranger &ranger, bool resolve)
: m_ranger (ranger)
{
if (DEBUG_SOLVER)
@@ -43,12 +45,15 @@ path_range_query::path_range_query (gimple_ranger &ranger)
m_cache = new ssa_global_cache;
m_has_cache_entry = BITMAP_ALLOC (NULL);
m_path = NULL;
+ m_resolve = resolve;
+ m_oracle = new path_oracle (ranger.oracle ());
}
path_range_query::~path_range_query ()
{
BITMAP_FREE (m_has_cache_entry);
delete m_cache;
+ delete m_oracle;
}
// Mark cache entry for NAME as unused.
@@ -161,22 +166,6 @@ path_range_query::unreachable_path_p ()
return m_undefined_path;
}
-// Return the range of STMT at the end of the path being analyzed.
-
-bool
-path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
-{
- tree type = gimple_range_type (stmt);
-
- if (!irange::supports_type_p (type))
- return false;
-
- if (!fold_range (r, stmt, this))
- r.set_varying (type);
-
- return true;
-}
-
// Initialize the current path to PATH. The current block is set to
// the entry block to the path.
//
@@ -371,6 +360,12 @@ path_range_query::precompute_ranges (const vec<basic_block> &path,
m_imports = imports;
m_undefined_path = false;
+ if (m_resolve)
+ {
+ m_oracle->reset_path ();
+ precompute_relations (path);
+ }
+
if (DEBUG_SOLVER)
{
fprintf (dump_file, "\npath_range_query: precompute_ranges for path: ");
@@ -400,3 +395,178 @@ path_range_query::precompute_ranges (const vec<basic_block> &path,
if (DEBUG_SOLVER)
dump (dump_file);
}
+
+// A folding aid used to register and query relations along a path.
+// When queried, it returns relations as they would appear on exit to
+// the path.
+//
+// Relations are registered on entry so the path_oracle knows which
+// block to query the root oracle at when a relation lies outside the
+// path. However, when queried we return the relation on exit to the
+// path, since the root_oracle ignores the registered.
+
+class jt_fur_source : public fur_depend
+{
+public:
+ jt_fur_source (gimple *s, path_range_query *, gori_compute *,
+ const vec<basic_block> &);
+ relation_kind query_relation (tree op1, tree op2) override;
+ void register_relation (gimple *, relation_kind, tree op1, tree op2) override;
+ void register_relation (edge, relation_kind, tree op1, tree op2) override;
+private:
+ basic_block m_entry;
+};
+
+jt_fur_source::jt_fur_source (gimple *s,
+ path_range_query *query,
+ gori_compute *gori,
+ const vec<basic_block> &path)
+ : fur_depend (s, gori, query)
+{
+ gcc_checking_assert (!path.is_empty ());
+
+ m_entry = path[path.length () - 1];
+
+ if (dom_info_available_p (CDI_DOMINATORS))
+ m_oracle = query->oracle ();
+ else
+ m_oracle = NULL;
+}
+
+// Ignore statement and register relation on entry to path.
+
+void
+jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2)
+{
+ if (m_oracle)
+ m_oracle->register_relation (m_entry, k, op1, op2);
+}
+
+// Ignore edge and register relation on entry to path.
+
+void
+jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2)
+{
+ if (m_oracle)
+ m_oracle->register_relation (m_entry, k, op1, op2);
+}
+
+relation_kind
+jt_fur_source::query_relation (tree op1, tree op2)
+{
+ if (!m_oracle)
+ return VREL_NONE;
+
+ if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
+ return VREL_NONE;
+
+ return m_oracle->query_relation (m_entry, op1, op2);
+}
+
+// Return the range of STMT at the end of the path being analyzed.
+
+bool
+path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
+{
+ tree type = gimple_range_type (stmt);
+
+ if (!irange::supports_type_p (type))
+ return false;
+
+ // If resolving unknowns, fold the statement as it would have
+ // appeared at the end of the path.
+ if (m_resolve)
+ {
+ fold_using_range f;
+ jt_fur_source src (stmt, this, &m_ranger.gori (), *m_path);
+ if (!f.fold_stmt (r, stmt, src))
+ r.set_varying (type);
+ }
+ // Otherwise, use the global ranger to fold it as it would appear in
+ // the original IL. This is more conservative, but faster.
+ else if (!fold_range (r, stmt, this))
+ r.set_varying (type);
+
+ return true;
+}
+
+// Precompute relations on a path. This involves two parts: relations
+// along the conditionals joining a path, and relations determined by
+// examining PHIs.
+
+void
+path_range_query::precompute_relations (const vec<basic_block> &path)
+{
+ if (!dom_info_available_p (CDI_DOMINATORS))
+ return;
+
+ jt_fur_source src (NULL, this, &m_ranger.gori (), path);
+ basic_block prev = NULL;
+ for (unsigned i = path.length (); i > 0; --i)
+ {
+ basic_block bb = path[i - 1];
+ gimple *stmt = last_stmt (bb);
+
+ precompute_phi_relations (bb, prev);
+
+ // Compute relations in outgoing edges along the path. Skip the
+ // final conditional which we don't know yet.
+ if (i > 1
+ && stmt
+ && gimple_code (stmt) == GIMPLE_COND
+ && irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (stmt))))
+ {
+ basic_block next = path[i - 2];
+ int_range<2> r;
+ gcond *cond = as_a<gcond *> (stmt);
+
+ if (EDGE_SUCC (bb, 0)->dest == next)
+ gcond_edge_range (r, EDGE_SUCC (bb, 0));
+ else if (EDGE_SUCC (bb, 1)->dest == next)
+ gcond_edge_range (r, EDGE_SUCC (bb, 1));
+ else
+ gcc_unreachable ();
+
+ edge e0 = EDGE_SUCC (bb, 0);
+ edge e1 = EDGE_SUCC (bb, 1);
+ src.register_outgoing_edges (cond, r, e0, e1);
+ }
+ prev = bb;
+ }
+}
+
+// Precompute relations for each PHI in BB. For example:
+//
+// x_5 = PHI<y_9(5),...>
+//
+// If the path flows through BB5, we can register that x_5 == y_9.
+
+void
+path_range_query::precompute_phi_relations (basic_block bb, basic_block prev)
+{
+ if (prev == NULL)
+ return;
+
+ basic_block entry = entry_bb ();
+ edge e_in = find_edge (prev, bb);
+ gcc_checking_assert (e_in);
+
+ for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
+ gsi_next (&iter))
+ {
+ gphi *phi = iter.phi ();
+ tree result = gimple_phi_result (phi);
+ unsigned nargs = gimple_phi_num_args (phi);
+
+ 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);
+
+ if (gimple_range_ssa_p (arg))
+ m_oracle->register_relation (entry, EQ_EXPR, arg, result);
+
+ break;
+ }
+ }
+}
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index c75721f6dc0..d12fd7743ca 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -35,13 +35,14 @@ along with GCC; see the file COPYING3. If not see
class path_range_query : public range_query
{
public:
- path_range_query (class gimple_ranger &ranger);
+ path_range_query (class gimple_ranger &ranger, bool resolve);
virtual ~path_range_query ();
void precompute_ranges (const vec<basic_block> &path,
const bitmap_head *imports);
bool range_of_expr (irange &r, tree name, gimple * = NULL) override;
bool range_of_stmt (irange &r, gimple *, tree name = NULL) override;
bool unreachable_path_p ();
+ path_oracle *oracle () { return m_oracle; }
void dump (FILE *) override;
void debug ();
@@ -58,6 +59,8 @@ private:
void precompute_ranges_in_block (basic_block bb);
void adjust_for_non_null_uses (basic_block bb);
void ssa_range_in_phi (irange &r, gphi *phi);
+ void precompute_relations (const vec<basic_block> &);
+ void precompute_phi_relations (basic_block bb, basic_block prev);
// Path navigation.
void set_path (const vec<basic_block> &);
@@ -79,12 +82,16 @@ private:
// Path being analyzed.
const vec<basic_block> *m_path;
- // Current path position.
- unsigned m_pos;
-
const bitmap_head *m_imports;
gimple_ranger &m_ranger;
non_null_ref m_non_null;
+ path_oracle *m_oracle;
+
+ // Current path position.
+ unsigned m_pos;
+
+ // Use ranger to resolve anything not known on entry.
+ bool m_resolve;
// Set if there were any undefined expressions while pre-calculating path.
bool m_undefined_path;
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index c6530d3a6bb..95542079faf 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -122,7 +122,7 @@ const edge back_threader::UNREACHABLE_EDGE = (edge) -1;
back_threader::back_threader (bool speed_p)
: m_registry (param_max_fsm_thread_paths),
m_profit (speed_p),
- m_solver (m_ranger)
+ m_solver (m_ranger, /*resolve=*/false)
{
m_last_stmt = NULL;
m_imports = BITMAP_ALLOC (NULL);
--
2.31.1
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH 5/7] path solver: Remove useless code.
2021-09-21 16:53 [PATCH 0/7] Add ability to resolve unknowns to path solver Aldy Hernandez
` (3 preceding siblings ...)
2021-09-21 16:53 ` [PATCH 4/7] path solver: Add relation support Aldy Hernandez
@ 2021-09-21 16:53 ` Aldy Hernandez
2021-09-21 16:53 ` [PATCH 6/7] path solver: Add related SSAs to solvable set Aldy Hernandez
2021-09-21 16:53 ` [PATCH 7/7] path solver: Use ranger to solve unknowns Aldy Hernandez
6 siblings, 0 replies; 12+ messages in thread
From: Aldy Hernandez @ 2021-09-21 16:53 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: GCC patches, Jeff Law, Aldy Hernandez
Committed.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::range_defined_in_block):
Remove useless code.
---
gcc/gimple-range-path.cc | 4 ----
1 file changed, 4 deletions(-)
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index b3040c9bc00..b86a76fa74b 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -246,10 +246,6 @@ path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb)
fprintf (dump_file, "\n");
}
- // We may have an artificial statement not in the IL.
- if (!bb && r.varying_p ())
- return false;
-
return true;
}
--
2.31.1
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH 6/7] path solver: Add related SSAs to solvable set.
2021-09-21 16:53 [PATCH 0/7] Add ability to resolve unknowns to path solver Aldy Hernandez
` (4 preceding siblings ...)
2021-09-21 16:53 ` [PATCH 5/7] path solver: Remove useless code Aldy Hernandez
@ 2021-09-21 16:53 ` Aldy Hernandez
2021-09-21 16:53 ` [PATCH 7/7] path solver: Use ranger to solve unknowns Aldy Hernandez
6 siblings, 0 replies; 12+ messages in thread
From: Aldy Hernandez @ 2021-09-21 16:53 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: GCC patches, Jeff Law, Aldy Hernandez
The path solver takes an initial set of SSA names which are deemed
interesting. These are then solved along the path. Adding any copies
of said SSA names to the list of interesting names yields significantly
better results. This patch adds said copies to the already provided
list.
Currently this code is guarded by "m_resolve", which is the more
expensive mode, but it would be reasonable to make it available always,
especially since adding more imports usually has minimal impact on the
processing time. I will investigate and make it universally available
if this is indeed the case.
Committed.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::add_to_imports): New.
(path_range_query::add_copies_to_imports): New.
(path_range_query::precompute_ranges): Call
add_copies_to_imports.
* gimple-range-path.h (class path_range_query): Add prototypes
for add_copies_to_imports and add_to_imports.
---
gcc/gimple-range-path.cc | 80 +++++++++++++++++++++++++++++++++++++++-
gcc/gimple-range-path.h | 4 +-
2 files changed, 82 insertions(+), 2 deletions(-)
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index b86a76fa74b..a8ead3da4dc 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -343,6 +343,71 @@ path_range_query::adjust_for_non_null_uses (basic_block bb)
}
}
+// If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS.
+
+bool
+path_range_query::add_to_imports (tree name, bitmap imports)
+{
+ if (TREE_CODE (name) == SSA_NAME
+ && irange::supports_type_p (TREE_TYPE (name)))
+ return bitmap_set_bit (imports, SSA_NAME_VERSION (name));
+ return false;
+}
+
+// Add the copies of any SSA names in IMPORTS to IMPORTS.
+//
+// These are hints for the solver. Adding more elements (within
+// reason) doesn't slow us down, because we don't solve anything that
+// doesn't appear in the path. On the other hand, not having enough
+// imports will limit what we can solve.
+
+void
+path_range_query::add_copies_to_imports ()
+{
+ auto_vec<tree> worklist (bitmap_count_bits (m_imports));
+ bitmap_iterator bi;
+ unsigned i;
+
+ EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+ {
+ tree name = ssa_name (i);
+ worklist.quick_push (name);
+ }
+
+ while (!worklist.is_empty ())
+ {
+ tree name = worklist.pop ();
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+
+ if (is_gimple_assign (def_stmt))
+ {
+ // ?? Adding assignment copies doesn't get us much. At the
+ // time of writing, we got 63 more threaded paths across the
+ // .ii files from a bootstrap.
+ add_to_imports (gimple_assign_rhs1 (def_stmt), m_imports);
+ tree rhs = gimple_assign_rhs2 (def_stmt);
+ if (rhs && add_to_imports (rhs, m_imports))
+ worklist.safe_push (rhs);
+ rhs = gimple_assign_rhs3 (def_stmt);
+ if (rhs && add_to_imports (rhs, m_imports))
+ worklist.safe_push (rhs);
+ }
+ else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
+ {
+ for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
+ {
+ edge e = gimple_phi_arg_edge (phi, i);
+ tree arg = gimple_phi_arg (phi, i)->def;
+
+ if (TREE_CODE (arg) == SSA_NAME
+ && m_path->contains (e->src)
+ && bitmap_set_bit (m_imports, SSA_NAME_VERSION (arg)))
+ worklist.safe_push (arg);
+ }
+ }
+ }
+}
+
// Precompute the ranges for IMPORTS along PATH.
//
// IMPORTS are the set of SSA names, any of which could potentially
@@ -353,11 +418,12 @@ path_range_query::precompute_ranges (const vec<basic_block> &path,
const bitmap_head *imports)
{
set_path (path);
- m_imports = imports;
+ bitmap_copy (m_imports, imports);
m_undefined_path = false;
if (m_resolve)
{
+ add_copies_to_imports ();
m_oracle->reset_path ();
precompute_relations (path);
}
@@ -379,6 +445,18 @@ path_range_query::precompute_ranges (const vec<basic_block> &path,
{
basic_block bb = curr_bb ();
+ if (m_resolve)
+ {
+ gori_compute &gori = m_ranger.gori ();
+ tree name;
+
+ // Exported booleans along the path, may help conditionals.
+ // Add them as interesting imports.
+ FOR_EACH_GORI_EXPORT_NAME (gori, bb, name)
+ if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
+ bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
+ }
+
precompute_ranges_in_block (bb);
adjust_for_non_null_uses (bb);
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index d12fd7743ca..f23cce18391 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -61,6 +61,8 @@ private:
void ssa_range_in_phi (irange &r, gphi *phi);
void precompute_relations (const vec<basic_block> &);
void precompute_phi_relations (basic_block bb, basic_block prev);
+ void add_copies_to_imports ();
+ bool add_to_imports (tree name, bitmap imports);
// Path navigation.
void set_path (const vec<basic_block> &);
@@ -82,7 +84,7 @@ private:
// Path being analyzed.
const vec<basic_block> *m_path;
- const bitmap_head *m_imports;
+ auto_bitmap m_imports;
gimple_ranger &m_ranger;
non_null_ref m_non_null;
path_oracle *m_oracle;
--
2.31.1
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH 7/7] path solver: Use ranger to solve unknowns.
2021-09-21 16:53 [PATCH 0/7] Add ability to resolve unknowns to path solver Aldy Hernandez
` (5 preceding siblings ...)
2021-09-21 16:53 ` [PATCH 6/7] path solver: Add related SSAs to solvable set Aldy Hernandez
@ 2021-09-21 16:53 ` Aldy Hernandez
6 siblings, 0 replies; 12+ messages in thread
From: Aldy Hernandez @ 2021-09-21 16:53 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: GCC patches, Jeff Law, Aldy Hernandez
The default behavior for the path solver is to resort to VARYING when
the range for an unknown SSA is outside the given path. This is both
cheap and fast, but fails to get a significant amount of ranges that
traditionally the DOM and VRP threaders could get.
This patch uses the ranger to resolve any unknown names upon entry to
the path. It also uses equivalences to improve ranges.
Committed.
gcc/ChangeLog:
* gimple-range-path.cc (path_range_query::defined_outside_path):
New.
(path_range_query::range_on_path_entry): New.
(path_range_query::internal_range_of_expr): Resolve unknowns
with ranger.
(path_range_query::improve_range_with_equivs): New.
(path_range_query::ssa_range_in_phi): Resolve unknowns with
ranger.
* gimple-range-path.h (class path_range_query): Add
defined_outside_path, range_on_path_entry, and
improve_range_with_equivs.
---
gcc/gimple-range-path.cc | 89 ++++++++++++++++++++++++++++++++++++++--
gcc/gimple-range-path.h | 3 ++
2 files changed, 88 insertions(+), 4 deletions(-)
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index a8ead3da4dc..e65c7996bb7 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -121,6 +121,34 @@ path_range_query::debug ()
dump (stderr);
}
+// Return TRUE if NAME is defined outside the current path.
+
+bool
+path_range_query::defined_outside_path (tree name)
+{
+ gimple *def = SSA_NAME_DEF_STMT (name);
+ basic_block bb = gimple_bb (def);
+
+ return !bb || !m_path->contains (bb);
+}
+
+// Return the range of NAME on entry to the path.
+
+void
+path_range_query::range_on_path_entry (irange &r, tree name)
+{
+ int_range_max tmp;
+ basic_block entry = entry_bb ();
+ r.set_undefined ();
+ for (unsigned i = 0; i < EDGE_COUNT (entry->preds); ++i)
+ {
+ edge e = EDGE_PRED (entry, i);
+ if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
+ && m_ranger.range_on_edge (tmp, e, name))
+ r.union_ (tmp);
+ }
+}
+
// Return the range of NAME at the end of the path being analyzed.
bool
@@ -132,6 +160,16 @@ path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt)
if (get_cache (r, name))
return true;
+ if (m_resolve && defined_outside_path (name))
+ {
+ range_on_path_entry (r, name);
+
+ if (r.varying_p ())
+ improve_range_with_equivs (r, name);
+
+ set_cache (r, name);
+ return true;
+ }
basic_block bb = stmt ? gimple_bb (stmt) : exit_bb ();
if (stmt && range_defined_in_block (r, name, bb))
@@ -139,6 +177,9 @@ path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt)
if (TREE_CODE (name) == SSA_NAME)
r.intersect (gimple_range_global (name));
+ if (m_resolve && r.varying_p ())
+ improve_range_with_equivs (r, name);
+
set_cache (r, name);
return true;
}
@@ -160,6 +201,33 @@ path_range_query::range_of_expr (irange &r, tree name, gimple *stmt)
return false;
}
+// Improve the range of NAME with the range of any of its equivalences.
+
+void
+path_range_query::improve_range_with_equivs (irange &r, tree name)
+{
+ if (TREE_CODE (name) != SSA_NAME)
+ return;
+
+ basic_block entry = entry_bb ();
+ relation_oracle *oracle = m_ranger.oracle ();
+
+ if (const bitmap_head *equivs = oracle->equiv_set (name, entry))
+ {
+ int_range_max t;
+ bitmap_iterator bi;
+ unsigned i;
+
+ EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi)
+ if (i != SSA_NAME_VERSION (name) && r.varying_p ())
+ {
+ tree equiv = ssa_name (i);
+ range_on_path_entry (t, equiv);
+ r.intersect (t);
+ }
+ }
+}
+
bool
path_range_query::unreachable_path_p ()
{
@@ -189,10 +257,11 @@ path_range_query::ssa_range_in_phi (irange &r, gphi *phi)
tree name = gimple_phi_result (phi);
basic_block bb = gimple_bb (phi);
- // We experimented with querying ranger's range_on_entry here, but
- // the performance penalty was too high, for hardly any improvements.
if (at_entry ())
{
+ if (m_resolve && m_ranger.range_of_expr (r, name, phi))
+ return;
+
// Try fold just in case we can resolve simple things like PHI <5(99), 6(88)>.
if (!fold_range (r, phi, this))
r.set_varying (TREE_TYPE (name));
@@ -210,8 +279,20 @@ path_range_query::ssa_range_in_phi (irange &r, gphi *phi)
tree arg = gimple_phi_arg_def (phi, i);
if (!get_cache (r, arg))
- r.set_varying (TREE_TYPE (name));
-
+ {
+ if (m_resolve)
+ {
+ int_range_max tmp;
+ // Using both the range on entry to the path, and the
+ // range on this edge yields significantly better
+ // results.
+ range_on_path_entry (r, arg);
+ m_ranger.range_on_edge (tmp, e_in, arg);
+ r.intersect (tmp);
+ return;
+ }
+ r.set_varying (TREE_TYPE (name));
+ }
return;
}
gcc_unreachable ();
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index f23cce18391..6f81f21d42f 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -48,6 +48,8 @@ public:
private:
bool internal_range_of_expr (irange &r, tree name, gimple *);
+ bool defined_outside_path (tree name);
+ void range_on_path_entry (irange &r, tree name);
// Cache manipulation.
void set_cache (const irange &r, tree name);
@@ -61,6 +63,7 @@ private:
void ssa_range_in_phi (irange &r, gphi *phi);
void precompute_relations (const vec<basic_block> &);
void precompute_phi_relations (basic_block bb, basic_block prev);
+ void improve_range_with_equivs (irange &r, tree name);
void add_copies_to_imports ();
bool add_to_imports (tree name, bitmap imports);
--
2.31.1
^ permalink raw reply [flat|nested] 12+ messages in thread