On 10/12/20 8:39 AM, Martin Liška wrote:
On 10/6/20 4:12 PM, Jakub Jelinek wrote:
On Tue, Oct 06, 2020 at 03:48:38PM +0200, Martin Liška wrote:
On 10/6/20 9:47 AM, Richard Biener wrote:
But is it really extensible with the current implementation? I
doubt so.
I must agree with the statement. So let's make the pass properly.
I would need a help with the algorithm where I'm planning to do the
following
steps:
1) for each BB ending with a gcond, parse index variable and it's VR;
I'll support:
a) index == 123 ([123, 123])
b) 1 <= index && index <= 9 ([1, 9])
c) index == 123 || index == 12345 ([123, 123] [12345, 12345])
d) index != 1 ([1, 1])
e) index != 1 && index != 5 ([1, 1] [5, 5])
The fold_range_test created cases are essential to support, so
f) index - 123U < 456U ([123, 456+123])
g) (unsigned) index - 123U < 456U (ditto)
but the discovery should actually recurse on all of those forms, so
it will
handle
(unsigned) index - 123U < 456U || (unsigned) index - 16384U <= 32711U
etc.
You can see what reassoc init_range_entry does and do something similar?
All right, I started to use init_range_entry in combination with
linearize_expr_tree.
One thing I have problem with is that linearize_expr_tree doesn't
properly mark
all statements as visited for cases like:
<bb 4> :
index2.1_1 = (unsigned int) index2_16(D);
_2 = index2.1_1 + 4294967196;
_3 = _2 <= 100;
_5 = index2.1_1 + 4294966996;
_6 = _5 <= 33;
_7 = _3 | _6;
if (_7 != 0)
goto <bb 5>; [INV]
else
goto <bb 6>; [INV]
As seen, all statements in this BB are used by the final _7 != 0 and
it would
be handy for me to identify all statements that should be hoisted.
The ranger infrastructure includes definition chains for what can
potentially have a range calculated on an outgoing edge. It contains
all the ssa-names defined in the block for which we have range-ops
entries that allow us to potentially wind back thru a calculation. ie,
any name which is defined in the block whose value can be changed based
on which edge is taken...
I created:
foo (int index)
{
if (index - 123U < 456U || index - 16384U <= 32711U )
foo (42);
}
the exports range list contains
=========== BB 2 ============
index_9(D) int VARYING
<bb 2> :
index.0_1 = (unsigned int) index_9(D);
_2 = index.0_1 + 4294967173;
_3 = _2 <= 455;
_5 = index.0_1 + 4294950912;
_6 = _5 <= 32711;
_7 = _3 | _6;
if (_7 != 0)
goto <bb 3>; [INV]
else
goto <bb 4>; [INV]
2->3 (T) index.0_1 : unsigned int [123, 578][16384, 49095]
2->3 (T) _7 : _Bool [1, 1]
2->3 (T) index_9(D) : int [123, 578][16384, 49095]
2->4 (F) index.0_1 : unsigned int [0, 122][579, 16383][49096, +INF]
2->4 (F) _2 : unsigned int [456, +INF]
2->4 (F) _3 : _Bool [0, 0]
2->4 (F) _5 : unsigned int [32712, +INF]
2->4 (F) _6 : _Bool [0, 0]
2->4 (F) _7 : _Bool [0, 0]
2->4 (F) index_9(D) : int [-INF, 122][579, 16383][49096, +INF]
and importantly, the defchain structure which lists names which are used
to define this name looks like:
DUMPING GORI MAP
bb2 index.0_1 : index_9(D)
_2 : index.0_1 index_9(D)
_3 : index.0_1 _2 index_9(D)
_5 : index.0_1 index_9(D)
_6 : index.0_1 _5 index_9(D)
_7 : index.0_1 _2 _3 _5 _6 index_9(D)
exports: index.0_1 _2 _3 _5 _6 _7 index_9(D)
This indicates that if you are using _7 as the control name of the branch,
_7 : index.0_1 _2 _3 _5 _6 index_9(D)
is the list of names that _7 uses in its definition chain...and we can
calculate ranges for. index_9 is not defined in this BB, so it is
considered an import. you'd probably be looking for all the names in
this list whose SSA_NAME_DEF_STMT is in this block.. That looks a lot
like the list of statements you want to hoist.
Caveats are that
1) this is currently only used internally by the ranger, so there
are some minor warts that may currently limit its usefulness elsewhere
2) its is limited to only processing statements for which we have
range-ops understanding. which means we know how to calculate ranges
for the statement. Perhaps this is also not an issue since if there are
statements we cant generate a range for, perhaps you dont care.
This might be more ionfo than you need, but also
3) before the enxt stage 1 I plan to rework the GORI component, and I
plan to split this into additional "parts" in particualr, this entire
export list will still exist, but there will be 3 subcomponents which
form it:
a) control names : These are booleans which contribute to the
TRUE/FALSEness of the edge
b) direct exports : These are ssanames which are directly
affected by relations on the edge.. Ie, the edge gives them a range
c) calculable exports : These are other ssa_names which can be
calculated based on the direct exports. Ie, the direct export is used in
calculating this value
for the above block,
control names : _7, _6 and _3
direct exports : _5 and _2
calculable exports : index.0_1 index_9(D)
I bring it up because as IM reworking those bits, we can take into
account other requirements that might be needed that can make it useful
other places. And by anaylzing the names that are common between any
direct exports, you may find useful information.
Currently, the exports list is not exported from the ranger, nor is the
gori map, but that would be trivial to do. You basically get a bitmap
back..
The classes are not dependant on the ranger either, so you can roll your
own if you wanted to experiment. Since they are internal they are
currently located in gimple-range-gori.cc.. its basically the gori_map
class which tracks all this and uses the range_def_chain class to manage
the definition chains. I threw a number fo comments in there already.
Its lazily evaluated as queries are made.
If you think there is something useful, we can move those classes into
the gimple-range-gori.h header file and adjust the APIs as needed.
Thoughts how can I achieve that?
Thanks,
Martin
