[llvm-dev] Multi-Threading Compilers

Johannes Doerfert via llvm-dev llvm-dev at lists.llvm.org
Fri Mar 27 00:00:39 PDT 2020


On 3/26/20 5:58 PM, Chris Lattner via llvm-dev wrote:
 > 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.

So, syntactic matching, if performed by traversing the use list, will in
the presence of constants not work "as good" as it could. How that is a
correctness issue (or why does it matter otherwise)?

 > 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.

I'm unsure what you want to say here. I think/hope we don't do the
matching you mention anymore. Even if, you can easily make this work
just fine, I mean, all of it points 1) and 2) in the absence of a use
lists for constants: Only follow users of non-constants, which is the
only thing you will be able to do anyway as constants won't have users.
If all operands are constants chances are the operation is as well or it
is not well-suited for syntactic-only transformations anyway.


 > 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
 > :-).

I know that MLIR does the right thing already. Nevertheless, I would
still like to talk about alternatives in a constructive way.


 > 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.

This is where I am not so sure. So far, and including the example above,
I'm still not aware of a soundness problem or drawback that would come
from constants without use-lists (except globals). Anyway, we gather
more data once we perform some experiments.

FTR, I'm not even sure this is a good idea but I think it is
      worth/interesting to discuss and investigate anyway.

Cheers,
   Johannes


 > -Chris
 >
 >
 >
 > _______________________________________________
 > LLVM Developers mailing list
 > llvm-dev at lists.llvm.org
 > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



More information about the llvm-dev mailing list