llvm dev - Mar 2020 - Multi-Threading Compilers

> On Mar 25, 2020, at 5:14 PM, Doerfert, Johannes <jdoerfert at
anl.gov> wrote:
> 
>>> Let's assume you
>>> walk the uses and we "removed" the use list so there are
none, what does
>>> that mean. I'd say, nothing much. If you inspect the Value and
see it's
>>> a Constant you have to assume it has Aliases that denote the same
value
>>> so direct uses are not really interesting anyway. If you inspect
further
>>> and see ConstantInt/Float/... you can deal with the missing use
list. If
>>> you don't inspect the Value you cannot really make much of an
empty use
>>> list, or can you? I doubt we ever call RAUW on a
ConstantInt/Float/...
>>> 
>>> Feel free to elaborate on your concerns.
>> 
>> 
>> Have you tested your thesis that no one walks the use-def chains?  You
>> could just add an assertion to the compiler (the methods like
>> use_begin() hasOneUse() etc), that aborts on constants, then run the
>> test suite.
> 
> That is what I suggested a few emails back. However, I never said it is
> safe because no one walks it but what I suggested is that it will
> actually not impact much if we don't remember the uses of Constants
> (except globals).
Sure, I was just curious what you base that opinion on.  Have you done an
experiment?

-Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200325/45c17b14/attachment-0001.html>

On 3/25/20 11:33 PM, Chris Lattner wrote:
 >
 >
 >> On Mar 25, 2020, at 5:14 PM, Doerfert, Johannes <jdoerfert at
anl.gov>
wrote:
 >>
 >>>> Let's assume you
 >>>> walk the uses and we "removed" the use list so there
are none,
what does
 >>>> that mean. I'd say, nothing much. If you inspect the Value
and see
it's
 >>>> a Constant you have to assume it has Aliases that denote the
same
value
 >>>> so direct uses are not really interesting anyway. If you
inspect
further
 >>>> and see ConstantInt/Float/... you can deal with the missing
use
list. If
 >>>> you don't inspect the Value you cannot really make much of
an
empty use
 >>>> list, or can you? I doubt we ever call RAUW on a
ConstantInt/Float/...
 >>>>
 >>>> Feel free to elaborate on your concerns.
 >>>
 >>>
 >>> Have you tested your thesis that no one walks the use-def chains? 
You
 >>> could just add an assertion to the compiler (the methods like
 >>> use_begin() hasOneUse() etc), that aborts on constants, then run
the
 >>> test suite.
 >>
 >> That is what I suggested a few emails back. However, I never said it
is
 >> safe because no one walks it but what I suggested is that it will
 >> actually not impact much if we don't remember the uses of
Constants
 >> (except globals).
 >
 > Sure, I was just curious what you base that opinion on.  Have you 
done an experiment?

I haven't but, I suggested a few emails back we should gather such data

(and I was hoping Nicholas was going to do it).


Could you elaborate on what you said earlier. Why is problematic to
remove the use-lists tracking from Constants, except globals? If you
have a use case in which an always empty use list for such constants
would be problematic it would be beneficial for us to consider it sooner
than later.

Thanks,
   Johannes



 >
 > -Chris

On Mar 26, 2020, at 8:10 AM, Doerfert, Johannes <jdoerfert at anl.gov>
wrote:
> 
>> 
>> Sure, I was just curious what you base that opinion on.  Have you 
> done an experiment?
> 
> I haven't but, I suggested a few emails back we should gather such data
> 
> (and I was hoping Nicholas was going to do it).
> 
> 
> Could you elaborate on what you said earlier. Why is problematic to
> remove the use-lists tracking from Constants, except globals? If you
> have a use case in which an always empty use list for such constants
> would be problematic it would be beneficial for us to consider it sooner
> than later.
Sure.  I think this changed, by at one point LLVM had a simple PRE algorithm
based on lexical equivalence.  The way this works is that you have to find all
instances of a computation (e.g. “x+y”) in a function, then see if any are
redundant, and move things around to eliminate them.

There is a simple way to implement this, in pseudo code, for binary operators:

findCandidatesLexicallyEquivalentTo(BinaryOperator *inst) {
  for (auto user : lhs->getOperand(0)->getUses())
    If (user->getOperand(1) == inst->getOperand(1) && 
        user->getParentFunction() == inst->getFunction())
      Found.push_back(user);
}

This fails if this is an operation like “sub(42, x)” when 42 doesn’t have a
use-def chain.

This has clear advantages and disadvantages, including:

1) It is sparse, defined over use-def chains instead of requiring dense scans of
the IR.  As such, it scales to larger functions better.
 2) There can be a constant on the LHS and you end up scanning everything in the
universe if you aren’t careful.

The right fix for this to make constants have instructions and unique them into
the entry block of the function (which is what MLIR does :-).

That said, my point isn’t about this algorithm in particular, it is that use-def
chains are a pervasive part of the IR and are used in lots of different ways. 
Making them work different will introduce bugs and inconsistencies in the
compiler that only show up in weird cases, which is not great for the long term
health of the project.

-Chris

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200326/649b698f/attachment.html>