[llvm-dev] more reassociation in IR

Fri May 11 14:37:14 PDT 2018

On Thu, May 10, 2018 at 12:49 PM Daniel Berlin <dberlin at dberlin.org> wrote:

>
>
> On Thu, May 10, 2018 at 12:05 PM, Hiroshi Yamauchi <yamauchi at google.com>
> wrote:
>
>>
>>
>> On Wed, May 9, 2018 at 8:24 PM Daniel Berlin <dberlin at dberlin.org> wrote:
>>
>>>
>>>
>>> On Wed, May 9, 2018 at 10:39 AM, Hiroshi Yamauchi <yamauchi at google.com>
>>> wrote:
>>>
>>>>
>>>>
>>>> On Tue, May 8, 2018 at 11:15 AM Daniel Berlin <dberlin at dberlin.org>
>>>> wrote:
>>>>
>>>>>
>>>>>
>>>>> On Tue, May 8, 2018 at 10:38 AM, Hiroshi Yamauchi via llvm-dev <
>>>>> llvm-dev at lists.llvm.org> wrote:
>>>>>
>>>>>> (
>>>>>> I came across this issue in the context of
>>>>>>  D46336 <https://reviews.llvm.org/D46336>.
>>>>>>  
>>>>>> Thanks, Sanjay, for starting this discussion.)
>>>>>>
>>>>>> If
>>>>>> we will
>>>>>>  move
>>>>>> reassociation,
>>>>>> or keep additional ones
>>>>>> ,
>>>>>> out of instcombine,
>>>>>> open questions for me would be
>>>>>> :
>>>>>>
>>>>>>
>>>>>> 1. Since -reassociate isn't a fixed point pass,
>>>>>>
>>>>>
>>>>> This is fixable, fwiw, without fixpointing it.
>>>>>
>>>>
>>>> How?
>>>>
>>>
>>> Depends on specifically which part you would like to know about ;)
>>>
>>
>> Maybe I misunderstood what you meant by "This is fixable". Did you mean
>> that we won't somehow need to fixpoint between instcombine and reassociate,
>> or that the specific motivating examples from the above differentials
>> are foldable without fixpointing?
>>
>
> If by fixpointing you mean "fixpointing reassociate and instcombine", then
> yes, that is fixable without fixpointing reassociate and instcombine, but
> would require rewriting instcombine :)
>
>
>>
>> If the latter, that may be the case. The concern was that we may
>> encounter examples that may need many more iterations, if not fixpointing.
>> As long as it's feasible to fixpoint between instcombine and
>> reassociate, it seems to work, but I guess that would probably need some
>> pass management change.
>>
>>
>>>
>>>>
>>>>
>>>>>
>>>>>> we might need to repeat "-instcombine -reassociate" multiple times to
>>>>>> fold
>>>>>>  down to what we want (relating to my comment here
>>>>>> <https://reviews.llvm.org/D46336#1087082>). I assumed this isn't not
>>>>>> what we want to do
>>>>>> ? My impression is we don't do a fixed-point with passes?
>>>>>>
>>>>>
>>>>> Well, i mean there is no practical difference between passes that we
>>>>> fixpoint externally and fixpoint internally.
>>>>>
>>>> 
>>>> I had the following in mind: Does the pass manager support fixpointing
>>>> externally? Is there any performance difference? Are people okay with that
>>>> in general?
>>>>
>>>> But if there is no practical difference, I don't see any problem with
>>>> that :)
>>>>
>>>>
>>>>>
>>>>>>
>>>>>>
>>>>> 2.
>>>>>> Since -reassociate needs to come up with one operand order (at
>>>>>> least currently as the only reassociate pass), would there exist a
>>>>>> single, unique operand order that would enable all
>>>>>> reassociative/commutative foldings that we want?
>>>>>>
>>>>>
>>>>> In what way?
>>>>> Are you asking whether there is a single reassociation order that
>>>>> makes all foldings occur in the same operation or something?
>>>>> I don't feel like i understand what you are asking.
>>>>>
>>>>
>>>> Does this rephrase help: with the motivating examples (like
>>>> and-of-shifts or bit check patterns) from the above differentials in mind,
>>>> can we come up with a single reassociation order that solves all those
>>>> and all the others that may come up in the future? Would we need different reassociation
>>>> orders to fold different patterns?
>>>>
>>>
>>> It doesn't quite help.
>>> When stated that generally, there can be no such ordering at all, that's
>>> easy to prove.  It is a statically undecidable problem.
>>>
>>> There is however, a different question and answer to a few related
>>> problems that maybe you are really asking?
>>> 1. Is there a way to determine and apply the a maximal or nearly-maximal
>>> set of folds/graph transforms that could be applied to a given set of code
>>> in a sane and principled way -> yes
>>>
>>> (see, e.g., http://www.cs.cornell.edu/~ross/publications/eqsat/)
>>>
>>> 2. Is there a way to determine all expressions in the program as it
>>> exists that are equivalent or equivalent under constant time constant
>>> folding/reassociation, in a reasonable time bound -> yes
>>>
>>> (not a single easy link, happy to talk about it)
>>>
>>> Your original question is basically equivalent to
>>> Is there a way to determine all expressions in the program as it exists
>>> that are equivalent or could be made equivalent through any type of folding
>>> that one can think up?
>>> The answer to that is "no", it's provable that this is not statically
>>> decidable, so the time bound doesn't matter :)
>>>
>>> You have to limit the possible folding/evaluation you apply in various
>>> ways to make this decidable, and then further limit it to make the time
>>> bound reasonable.
>>>
>>> This all quickly devolves into herbrand equivalence and it's variations.
>>>
>>>
>>> 
>> Let me try one more time :) May we need multiple reassociate passes to
>> fold different reassociative patterns?
>>
>> A longer version: If Sanjay wants a particular reassociative pattern to
>> be folded (D45842), Omer wants another particular reassociative pattern
>> to be folded (D41574), and I want yet another particular reassociative
>> pattern to be folded (D46336), would we potentially need three
>> different reassociate passes with each combined with instcombine, rather
>> than just one that may be able to somehow handle those cases in one
>> shot, (assuming we don't want to put those in instcombine)?
>>
>> And it sounds like the answer is yes?
>>
>
> If you take the current instcombine as a base, then yes, that is correct.
>

> If you are willing to rearchitect instcombine, the answer is no, it's
> possible to do this all in a single pass in a relatively sane way.
>

I assume by rearchitect, you mean a major rewrite as per this comment: "Is
there a way to determine all expressions in the program as it exists that
are equivalent or equivalent under constant time constant
folding/reassociation, in a reasonable time bound -> yes". Any pointer or
time to chat?

I think that an approach like 
D

4

6

3

3

6

 /

D

4

6

5

9

5

 has a merit: it would adds a bit of complexity, but would not require:

1. a major rewrite of instcombine,
2. writing multiple (potentially many) reassociate passes and figuring out
how to fixpoint them with instcombine, or
3. writing a self-contained folding pass for a specific pattern

If you look at the diffs in the existing .ll files in
D46336
, it helps fold some previously-unfolded reassociation patterns beyond the
bit check patterns that it originally targeted.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180511/dee16b47/attachment-0001.html>