On Fri, Jan 20, 2017 at 8:48 PM, Jeff Law <l...@redhat.com> wrote:
> On 01/20/2017 01:17 AM, Richard Biener wrote:
>>
>> On Thu, Jan 19, 2017 at 5:53 PM, Martin Sebor <mse...@gmail.com> wrote:
>>>
>>> On 01/19/2017 05:45 AM, Richard Biener wrote:
>>>>
>>>>
>>>> On Thu, Jan 19, 2017 at 1:17 PM, Aldy Hernandez <al...@redhat.com>
>>>> wrote:
>>>>>
>>>>>
>>>>> In the attached testcase, we have a clearly bounded case of alloca
>>>>> which
>>>>> is
>>>>> being incorrectly reported:
>>>>>
>>>>> void g (int *p, int *q)
>>>>> {
>>>>> size_t n = (size_t)(p - q);
>>>>>
>>>>> if (n < 10)
>>>>> f (__builtin_alloca (n));
>>>>> }
>>>>>
>>>>> The problem is that VRP gives us an anti-range for `n' which may be out
>>>>> of
>>>>> range:
>>>>>
>>>>> # RANGE ~[2305843009213693952, 16140901064495857663]
>>>>> n_9 = (long unsigned int) _4;
>>>>>
>>>>> We do a less than stellar job with casts and VR_ANTI_RANGE's, mostly
>>>>> because
>>>>> we're trying various heuristics to make up for the fact that we have
>>>>> crappy
>>>>> range info from VRP. More specifically, we're basically punting on an
>>>>> VR_ANTI_RANGE and ignoring that the casted result (n_9) has a bound
>>>>> later
>>>>> on.
>>>>>
>>>>> Luckily, we already have code to check simple ranges coming into the
>>>>> alloca
>>>>> by looking into all the basic blocks feeding it. The attached patch
>>>>> delays
>>>>> the final decision on anti ranges until we have examined the basic
>>>>> blocks
>>>>> and determined for that we are definitely out of range.
>>>>>
>>>>> I expect all this to disappear with Andrew's upcoming range info
>>>>> overhaul.
>>>>>
>>>>> OK for trunk?
>>>>
>>>>
>>>>
>>>> I _really_ wonder why all the range consuming warnings are not emitted
>>>> from VRP itself (like we do for -Warray-bounds). There we'd still see
>>>> a range for the argument derived from the if () rather than needing to
>>>> do our own mini-VRP from the needessly "incomplete" range-info on
>>>> SSA vars.
>>>
>>>
>>>
>>> Can you explain why the range info is only available in VRP and
>>> not outside, via the get_range_info() API? It sounds as though
>>> the API shouldn't be relied on (it was virtually unused before
>>> GCC 7).
>>
>>
>> It's very simple. Look at the testcase from above
>>
>> void g (int *p, int *q)
>> {
>> size_t n = (size_t)(p - q);
>>
>> if (n < 10)
>> f (__builtin_alloca (n));
>> }
>>
>> The IL outside of VRP is
>>
>> <bb 2> [100.00%]:
>> p.0_1 = (long int) p_7(D);
>> q.1_2 = (long int) q_8(D);
>> _3 = p.0_1 - q.1_2;
>> _4 = _3 /[ex] 4;
>> n_9 = (size_t) _4;
>> if (n_9 <= 9)
>> goto <bb 3>; [36.64%]
>> else
>> goto <bb 4>; [63.36%]
>>
>> <bb 3> [36.64%]:
>> _5 = __builtin_alloca (n_9);
>> f (_5);
>>
>> so there is no SSA name we can tack a range to covering the n_9 <= 9
>> condition that dominates __builtin_alloca. Inside VRP we have
>>
>> <bb 2> [100.00%]:
>> p.0_1 = (long int) p_7(D);
>> q.1_2 = (long int) q_8(D);
>> _3 = p.0_1 - q.1_2;
>> _4 = _3 /[ex] 4;
>> n_9 = (size_t) _4;
>> if (n_9 <= 9)
>> goto <bb 3>; [36.64%]
>> else
>> goto <bb 4>; [63.36%]
>>
>> <bb 3> [36.64%]:
>> n_13 = ASSERT_EXPR <n_9, n_9 <= 9>;
>> _5 = __builtin_alloca (n_13);
>> f (_5);
>>
>> and viola - now the alloca call uses n_13 which is defined at a point
>> dominated by if (n_9 <= 9) and thus it has an improved range:
>>
>> n_13: [0, 9] EQUIVALENCES: { n_9 } (1 elements)
>>
>> When in EVRP you get similar behavior (well, there are some missed
>> cases I have patches queued for for GCC 8), but instead of modifying
>> the IL EVRP just temporarily sets the above range when it processes
>> BBs dominated by the condition.
>>
>> So while for VRP you can put the warning code after propagation for
>> EVRP you'd have to do warning processing during propagation itself
>> (and EVRP doesn't iterate).
>>
>>> To answer your question, the gimple-ssa-sprintf pass that depends
>>> heavily on ranges would also benefit from having access to the data
>>> computed in the strlen pass that's not available outside it.
>>>
>>> The -Wstringop-overflow and -Walloc-size-larger-than warnings depend
>>> on both VRP and tree-object-size.
>>>
>>> I have been thinking about how to integrate these passes in GCC 8
>>> to improve the overall quality. (By integrating I don't necessarily
>>> mean merging the code but rather having them share data or be able
>>> to make calls into one another.)
>>>
>>> I'd be very interested in your thoughts on this.
>>
>>
>> Well, my thought is that we should not have N SSA propagation and
>> M "DOM" propagation passes but one of each kind. My thought is
>> also that object-size and strlen are of either kind.
>>
>> So ideally DOM and EVRP would merge and CCP, copyprop and VRP
>> would merge. It's probably not possible (or wise) to merge their lattices
>> (maybe to some extent)
>
> DOM's equivalency tables could be easily superceded by other
> implementations. It's just two datastructures. A trivial const/copy table
> and a stack to allow unwinding the state of the const/copy table. Throwing
> away the basic const/copy table and replacing it with something built by
> copyprop ought to be trivial.
>
> The big thing that would be left would be the scoped hash table for tracking
> redundant expressions. But I don't think that we'd necessarily have to rip
> that out to merge DOM with one of hte other passes.
>
> Hell we know DOM can fit well in any dominator based walk -- we used to do
> it as part of the into-ssa transformation.
Sure.
The question is whether we want to make warning "passes" more expensive
by essentially doing a [E]VRP/DOM pass (but not doing any IL transform).
I believe doing that is more reasonable than doing their own hacky analysis.
Having less passes to choose to copy from for such static analysis (and the
ability to tame compile-time by some switches) would be a good thing to have.
Richard.
>
> Jeff
