This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Refactor isHighCostExpansionHelper
ClosedPublic

Authored by samparker on Aug 17 2020, 1:41 AM.

Details

Summary

As discussed in D76434, to enable the cost of constants, the helper function has been reorganised:

  • A struct has been introduced to hold SCEV operand information so that we know the user of the operand, as well as the operand index. The Worklist now uses instead instead of a bare SCEV.
  • The costing of each SCEV, and collection of its operands, is now performed in a helper function.
  • Some SCEVExprs have been modified to provide methods that allow us to iterate through their operands.

Diff Detail

Event Timeline

samparker created this revision.Aug 17 2020, 1:41 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 17 2020, 1:41 AM
samparker requested review of this revision.Aug 17 2020, 1:41 AM
samparker updated this revision to Diff 285947.Aug 17 2020, 2:37 AM

Updated isHighCostExpansion to use a SCEVOperand instead of a SCEV.

samparker updated this revision to Diff 285952.Aug 17 2020, 3:20 AM

Moved AddRecExpr code into costAndCollectOperands.

lebedev.ri requested changes to this revision.Aug 17 2020, 6:43 AM

Please separate SCEV changes into preparatory review.

llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h
92 ↗(On Diff #285952)

Doesn't this return empty range?

276 ↗(On Diff #285952)

static_assert(sizeof(SmallVector<const SCEV*, 2>) == 4*sizeof(SCEV*), ""); holds, so this is a major bloat.
This should be std::array<>.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
44

The variables could use doxygen comments

236

Why std::unique_ptr?

This revision now requires changes to proceed.Aug 17 2020, 6:43 AM
samparker updated this revision to Diff 286028.Aug 17 2020, 8:30 AM
  • Extracted the SCEV changes and rebased.
  • Removed the use of unique_pointer.
  • Moved the cost adjustment for NAry operands into the helper. These now also use the extra operand checks that were performed for AddRecs.

Please can you explain why the calculated costs changed for those X86 tests?

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
47

/// LLVM IR instruction opcode

Please can you explain why the calculated costs changed for those X86 tests?

These were introduced once the Add and Mul expressions were costed in the same manner as when we're calculating for an AddRec. I'll remove the change for this patch and add it back in a follow-up.

  • Updated comment
  • Reverted back to the original costing for Add and Mul.
lebedev.ri added inline comments.Aug 23 2020, 11:15 PM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2056–2064

I guess i'm starting getting confused again and thus stalling, but.

Please can you explain why the calculated costs changed for those X86 tests?

These were introduced once the Add and Mul expressions were costed in the same manner as when we're calculating for an AddRec.

Right. But why was that done in the first place? Was that intentional?
That doesn't look correct to me.

Plain Add and Mul are *not* identical to AddRec.

I'll remove the change for this patch and add it back in a follow-up.

samparker added inline comments.Aug 23 2020, 11:20 PM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2056–2064

It was intentional... Why wouldn't we want to check for constant zero for plain Adds and constant one for plain Muls?

lebedev.ri added inline comments.Aug 23 2020, 11:28 PM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2056–2064

Why wouldn't we want to check for constant zero for plain Adds and constant one for plain Muls?

Because they shouldn't be there, they should be canonicalized away during SCEV creation.

But my main question is, why did that result in *higher* cost, as it can be seen from the blocked transforms?

samparker added inline comments.Aug 23 2020, 11:38 PM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2056–2064

I don't know, it didn't make sense to me. Anyway, it's not in the patch anymore.

lebedev.ri added inline comments.Aug 23 2020, 11:50 PM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2056–2064

I don't know, it didn't make sense to me.

Honestly, recalling how many of these costmodelling patches were there recently,
i'm now somewhat worried that i didn't pay attention to them..

@lebedev.ri Are you okay with this now?

lebedev.ri added inline comments.Aug 28 2020, 1:50 AM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2189–2200

Move this back into case scAddRecExpr: please

2223–2225

I'm sorry, but i don't like this.
The old code would loudly fail should anyone introduce a new SCEV type and forget to update this,
new code will silently treat such a case as free.

samparker added inline comments.Aug 28 2020, 1:53 AM
llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2223–2225

Ah, good point.

samparker updated this revision to Diff 288556.Aug 28 2020, 2:08 AM

Rebased and addressed comments.

Thanks, almost there i think.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
239

I'd maybe suggest (-1, -1, Expr) to really differentiate this case.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2189–2200

Please mark resolved comments as such.

2228

As a fixme, i suppose you might want to cost 1<<SC->getAPInt() constant?

2290–2291
for (auto I = enumerate(S->operands()))
  Worklist.emplace_back(Opc, I.index(), I.value());
2330–2343

This is very much not identical to the old code.
I think you want to do

// UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
// HowManyLessThans produced to compute a precise expression, rather than a
// UDiv from the user's code. If we can't find a UDiv in the code with some
// simple searching, we need to account for it's cost.

// At the beginning of this function we already tried to find existing
// value for plain 'S'. Now try to lookup 'S + 1' since it is common
// pattern involving division. This is just a simple search heuristic.
if (getRelatedExistingExpansion(
        SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L))
  return false; // Consider it to be free.

int Cost =
  costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist);
nikic added a subscriber: nikic.Aug 29 2020, 1:32 AM
nikic added inline comments.
llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
52

Nit: = nullptr here seems unnecessary, as the constructor always initializes it.

samparker updated this revision to Diff 290201.Sep 7 2020, 1:17 AM
samparker marked 3 inline comments as done.

Thanks, addressed comments.

samparker updated this revision to Diff 290215.Sep 7 2020, 2:12 AM
samparker marked an inline comment as done.

Removed nullptr assignment.

lebedev.ri accepted this revision.Sep 7 2020, 3:42 AM

Alright, i think this is NFC now..
Thanks

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
241–243

potentially const SCEVOperand WorkItem =

411

Here and elsewhere: const SCEVOperand &WorkItem - it shouldn't be ever mutated.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2187

Opcodes needs a good comment, even i'm currently having trouble understanding it.

This revision is now accepted and ready to land.Sep 7 2020, 3:42 AM
This revision was automatically updated to reflect the committed changes.

Thanks! Added a comment and const before committing.