[llvm-dev] Multi-Threading Compilers

[Chris Lattner via llvm-dev]

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>