Page MenuHomePhabricator

[NFC][InstructionCost]Migrate VectorCombine.cpp to use InstructionCost
ClosedPublic

Authored by CarolineConcatto on Jan 5 2021, 1:09 AM.

Details

Summary
This patch changes these functions:
  vectorizeLoadInsert
  isExtractExtractCheap
  foldExtractedCmps
  scalarizeBinopOrCmp
  getShuffleExtract
  foldBitcastShuf
  to use the class InstructionCost when calling TTI.get<something>Cost().

  This patch is part of a series of patches to use InstructionCost instead of
   unsigned/int for the cost model functions.
  See this thread for context:
      http://lists.llvm.org/pipermail/llvm-dev/2020-November/146408.html
  See this patch for the introduction of the type:
      https://reviews.llvm.org/D91174

Observation: 
 This patch adds the test || !NewCost.isValid(), because we want to
  return false when:
   !NewCost.isValid && !OldCost.isValid()->the cost to transform it expensive
  and
   !NewCost.isValid() && OldCost.isValid()
  Therefore for simplication we only add  test for !NewCost.isValid()

Diff Detail

Event Timeline

CarolineConcatto requested review of this revision.Jan 5 2021, 1:09 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 5 2021, 1:09 AM
CarolineConcatto retitled this revision from [NFC]Migrate VectorCombine.cpp to use InstructionCost to [NFC][InstructionCost]Migrate VectorCombine.cpp to use InstructionCost.Jan 5 2021, 1:18 AM
ctetreau added inline comments.Jan 5 2021, 9:30 AM
llvm/lib/Transforms/Vectorize/VectorCombine.cpp
201

the or is redundant.

259

Because of this assert, the branches will never be taken. This will result in different behavior in release vs debug mode.

Either remove the assert, or remove the two early returns.

Regardless, invalid costs are guaranteed to compare higher than valid costs, so the early returns are redundant.

321

can std::min be used here? InstructionCost has overloaded comparison operators and a total ordering.

Assuming it can be, we should probably get rid of InstructionCost::min and InstructionCost::max. That can be a different patch.

363–364

this is redundant. If OldCost is valid, and NewCost is invalid, then OldCost < NewCost returns true.

526

the or is redundant

636

the or is redundant

737

the or is redundant

david-arm added inline comments.
llvm/lib/Transforms/Vectorize/VectorCombine.cpp
259

Hi @ctetreau, after discussion during the last SVE sync call @paulwalker-arm thought we shouldn't be relying upon the lexicographical ordering that defines invalid costs to be infinitely expensive. He suggested that doing so is actually a bug in the code. So the route we've been taking so far is to either check for validity explicitly or assert that it's valid. If you think this is the wrong approach here then we can perhaps discuss it and agree on a consistent approach?

363–364

Again, @CarolineConcatto is just adding checks here as per discussion on the last SVE sync call, but we're happy to discuss the correct approach.

spatel added a comment.Jan 6 2021, 7:42 AM

I haven't followed the details enough to comment on the changes directly, but thanks for the cleanup! The mismatched signed/unsigned cost model APIs are/were a mess.

ctetreau added inline comments.Jan 6 2021, 9:49 AM
llvm/lib/Transforms/Vectorize/VectorCombine.cpp
259

I'm not sure how I missed that conversation, but as you may recall from the review thread for D91174, I fought hard for the total ordering to be added and documented so that it's guaranteed to be true. This is exactly the sort of case you'd want to this ordering for; the validity checks are guaranteed to be redundant with the greater-than checks. Additionally, adding the redundant validity checks is more error prone, because it's more operator-heavy lines of code you can mess up.

paulwalker-arm added inline comments.Jan 7 2021, 1:40 AM
llvm/lib/Transforms/Vectorize/VectorCombine.cpp
259

To be clear I have nothing against relying on the total ordering but I feel if the transformation is expecting instructions to have an actual cost then it should either assert or explicitly check for such. An example of this is LoopVectorize where there has already been extensive validation to ensure a loop is vectorisable and thus not being able to cost the loop is a sure sign there's either a bug in LoopVectorize's isLegal code or the cost functions themselves.

sdesmalen added inline comments.Jan 8 2021, 6:11 AM
llvm/lib/Transforms/Vectorize/VectorCombine.cpp
259

It seems that the algorithm requires at least one of the Costs to be valid (it has to choose either Ext0 or Ext1), so if the assert is changed to:

assert((Cost0.isValid() || Cost1.isValid()) && "At least one of Cost0 and Cost1 should be valid");

the existing code below should be sufficient and the two early returns that were added can be removed like @ctetreau suggested.

363–364

Similar to above, change the assert to check OldCost.isValid() || NewCost.isValid() and remove the early exit.

-remove redundat invalid check

CarolineConcatto marked 9 inline comments as done.Jan 11 2021, 1:35 AM

Thank you, everyone, for the review.
I have removed the redundant invalid check.
Also, thank you for making clear that invalid, atm, means as well high cost.
I'll have that in mind for the next patches.

Also, thank you for making clear that invalid, atm, means as well high cost.
I'll have that in mind for the next patches.

I would say "infinitely costly", not "high cost". Somebody may have "a lot" of LLVMBucks, nobody has infinity LLVMBucks.

Sorry to nitpick, but it's important to get these things right initially before everybody sees some flawed example and emulates it. If you need something to have a really high cost, you should just pick some really high valid cost. If you need something to never be within any cost budget, you should use invalid.

llvm/lib/Transforms/Vectorize/VectorCombine.cpp
259

To be clear I have nothing against relying on the total ordering but I feel if the transformation is expecting instructions to have an actual cost then it should either assert or explicitly check for such.

If it's an honest-to-gosh bug for some call to return invalid, then this is fine. I feel like this should never happen in any function that returns InstructionCost though. This would be akin to swallowing an exception and calling exit().

ctetreau added inline comments.Jan 11 2021, 9:38 AM
llvm/lib/Transforms/Vectorize/VectorCombine.cpp
200

Is this needed?

  • If the old cost is invalid, but the new cost is valid, then do the transform.
  • If neither cost is valid, then OldCost < NewCost will cause a return of false.
253

Reasonable to return nullptr?

If neither cost is valid, then neither of the inputs should be replaced

359–360

Would it be reasonable to return false here? If all costs involved are invalid, then I would say the transform is not cheap.

525

reasonable to return false here? If neither cost is valid, then do not do the transform

635

reasonable to return false?

736

reasonable to return false?

CarolineConcatto marked 3 inline comments as done.

-remove asserts for OldCost invalid
-add return if both costs are invalid

Hi @ctetreau,
Thank you for the review.
So I removed all the asserts and added the earlier return if both costs are invalid, because in this case it means that the transformation is not cheap.
If only OldCost is invalid I believe we should do nothing, for the same reason I removed the test for !NewCost.isValid().

llvm/lib/Transforms/Vectorize/VectorCombine.cpp
253

I think it is fine to add if the test if both are equal following the logic of if (Index0 == Index1)

359–360

If I remove the assert and leave the test to do its job the return will be false, because OldCost would be equal to NewCost.

635

If both are invalid, maybe.
But if OldCost is invalid I think you mean return true, because OldCost>NewCost
And in this last case I don't think we should add the earlier return because it is a change on the code path.

736

If both are invalid, maybe.
But if OldCost is invalid I think you mean return true, because OldCost>NewCost
And in this last case I don't think we should add the earlier return because it is a change on the code path.

-add missing invalid costs test for scalarizeBinopOrCmp

sdesmalen added inline comments.Jan 13 2021, 7:32 AM
llvm/lib/Transforms/Vectorize/VectorCombine.cpp
525

Does this assert need to be removed still?

-remove missed assert

CarolineConcatto marked an inline comment as done.Jan 13 2021, 9:28 AM
CarolineConcatto added inline comments.
llvm/lib/Transforms/Vectorize/VectorCombine.cpp
525

Yes, sorry missed that!

sdesmalen accepted this revision.Jan 14 2021, 6:36 AM

Added two nits, but LGTM otherwise.

llvm/lib/Transforms/Vectorize/VectorCombine.cpp
635

nit: || !NewCost.isValid() should be sufficient (see the other comment).

737

I don't think the or was redundant.

If the new cost is invalid, then it shouldn't do the transform. With only testing OldCost < NewCost, we'd get:

        isValid?
   OldCost  NewCost       (OldCost < NewCost)     result
--------------------------------------------------------
1.    true    true     OldCost.Val < NewCost.Val    ?
2.    true    false          Valid < Invalid       true
3.    false   true         Invalid < Valid        false
4.    false   false        Invalid < Invalid      false

However, 4. should be 'true' in order to return early from the function.

         isValid?
   OldCost  NewCost  (OldCost < NewCost || !NewCost.isValid)    result
-----------------------------------------------------------------------
1.    true    true      OldCost.Val < NewCost.Val || false        ?
2.    true    false           Valid < Invalid || true            true
3.    false   true          Invalid < Valid   || false          false
4.    false   false         Invalid < Invalid || true            true

Gives us the result we want.

nit: based on that I believe !OldCost.isValid() && is now redundant.

This revision is now accepted and ready to land.Jan 14 2021, 6:36 AM
CarolineConcatto marked an inline comment as done.

-replace (!NewCost.isValid && !OldCost.isvalid()) by !NewCost.isValid()

CarolineConcatto edited the summary of this revision. (Show Details)Jan 17 2021, 11:09 AM
CarolineConcatto marked an inline comment as done.
This revision was landed with ongoing or failed builds.Jan 18 2021, 5:37 AM
This revision was automatically updated to reflect the committed changes.