This is an archive of the discontinued LLVM Phabricator instance.

[TTI] Add OperandValueProperties::OP_NegatedPowerOf2 enum
ClosedPublic

Authored by RKSimon on Oct 17 2021, 11:21 AM.

Details

Summary

The mul by constant costmodels handle power-of-2 constants, but not negated-power-of-2, despite the backends handling both.

This patch adds the OperandValueProperties::OP_NegatedPowerOf2 enum and wires it for use for basic mul cost analysis and SLP handling.

Fixes https://bugs.llvm.org/show_bug.cgi?id=51436

Diff Detail

Event Timeline

RKSimon created this revision.Oct 17 2021, 11:21 AM
RKSimon requested review of this revision.Oct 17 2021, 11:21 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 17 2021, 11:21 AM
RKSimon added inline comments.Oct 17 2021, 11:21 AM
llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp
1397

@evandro You added pow2 support a while ago but I can't see any test coverage?

xbolva00 added inline comments.
llvm/include/llvm/Analysis/TargetTransformInfo.h
889

Mistake?

RKSimon added inline comments.Oct 17 2021, 11:49 AM
llvm/include/llvm/Analysis/TargetTransformInfo.h
889

yes - not quite sure how that happened.....

RKSimon updated this revision to Diff 380262.Oct 17 2021, 11:58 AM

Actually use the correct diff this time.......

dmgreen added inline comments.Oct 18 2021, 5:06 AM
llvm/lib/Analysis/TargetTransformInfo.cpp
693

This could do with brackets now.

RKSimon added inline comments.Oct 18 2021, 5:58 AM
llvm/lib/Analysis/TargetTransformInfo.cpp
673

I'm starting to think a APInt::isNegatedPowerOf2() wrapper might be useful?

RKSimon updated this revision to Diff 380375.Oct 18 2021, 6:47 AM

Add braces

RKSimon updated this revision to Diff 380685.Oct 19 2021, 7:12 AM
RKSimon edited the summary of this revision. (Show Details)

Rebased - use APInt::isNegatedPowerOf2()

dmgreen added inline comments.Oct 20 2021, 2:01 AM
llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp
1397

It looks like this goes back to https://reviews.llvm.org/D5469, and only included SLP vectorization tests. I have added some extra test coverage in rG862e8d7e5520. From what I could tell, the updated costs (when treating negpower2 same as power2) look OK.

RKSimon updated this revision to Diff 380887.Oct 20 2021, 3:25 AM

Thanks @dmgreen - updated with aarch64 test changes

RKSimon updated this revision to Diff 380920.Oct 20 2021, 5:56 AM
RKSimon edited the summary of this revision. (Show Details)

Add X86 mul by -pow2 handling

RKSimon updated this revision to Diff 380929.Oct 20 2021, 6:09 AM
RKSimon edited the summary of this revision. (Show Details)

Add SLP handling

RKSimon updated this revision to Diff 380953.Oct 20 2021, 7:43 AM

udiv/urem by -pow2 isn't as simple as shift/mask - fallback to the existing x86 udiv/urem by constant costs

AArch64 side looks OK to me, if you can find someone who knows the X86 part.

RKSimon planned changes to this revision.Oct 21 2021, 2:57 AM

I'm still looking at refining the x86 costs

Herald added a project: Restricted Project. · View Herald TranscriptMar 11 2022, 2:08 AM

I'm still looking at refining the x86 costs

Any status update?

I'll add this back to my backlog - it will need rewriting after the recent refactoring OperandValue refactoring and then I need to address the regressions in some of the pow2 logic

RKSimon updated this revision to Diff 462450.Sep 23 2022, 5:25 AM
RKSimon edited the summary of this revision. (Show Details)

rebased - removed div/rem handling for now to just focus on fixing PR51436

ABataev accepted this revision.Sep 23 2022, 5:47 AM

LG with a nit

llvm/include/llvm/Analysis/TargetTransformInfo.h
889

Add comma after the last enum item, common practice to reduce number of changes in future.

This revision is now accepted and ready to land.Sep 23 2022, 5:47 AM
RKSimon added inline comments.Sep 23 2022, 6:01 AM
llvm/lib/Analysis/TargetTransformInfo.cpp
707

Just realised that this doesn't set AllPow2 = AllNegPow2 = false if its not ConstantInt - will fix this in the commit.

Side note - we partly inverted canonicalization towards mul back to shl, so this pattern might come up less often after these patches:
0f32a5dea0e9
ee0bf6472291

We still change -(X << C) to X * -2**C for now since that replaces 2 IR instructions with 1.

If one form or the other is easier to deal with from the cost model perspective, that would help decide if we should change the canonicalization further.

If one form or the other is easier to deal with from the cost model perspective, that would help decide if we should change the canonicalization further.

div/rem by +/- pow2 will probably benefit from this more as we currently force most divisions by constants will scalarize even though there can be reasonable vector codegen - I need to finish cleaning up the cost tests though first - which is why I simplified this patch down to just the mul case. But as you said, apart from the simplest of cases (such as PR51436), we now canonicalize away from the mul

mstorsjo added inline comments.
llvm/lib/Analysis/TargetTransformInfo.cpp
671

GCC warns about this:

../lib/Analysis/TargetTransformInfo.cpp: In static member function ‘static llvm::TargetTransformInfo::OperandValueInfo llvm::TargetTransformInfo::getOperandInfo(const llvm::Value*)’:
../lib/Analysis/TargetTransformInfo.cpp:730:8: warning: suggest explicit braces to avoid ambiguous ‘else’ [-Wdangling-else]
  730 |     if (const auto *CI = dyn_cast<ConstantInt>(V))
      |        ^
../lib/Analysis/TargetTransformInfo.cpp:753:10: warning: suggest explicit braces to avoid ambiguous ‘else’ [-Wdangling-else]
  753 |       if (auto *CI = dyn_cast<ConstantInt>(Splat))
      |          ^