[llvm-dev] more reassociation in IR

Thu May 10 12:49:07 PDT 2018

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180510/2429409e/attachment.html>