This is an archive of the discontinued LLVM Phabricator instance.

Differential D99203

[RISCV] Add TTI support for cpop with Zbb
ClosedPublic

Authored by craig.topper on Mar 23 2021, 11:28 AM.

Details

Reviewers
frasercrmck
asb
luismarques
Commits
rGf24f09d256ae: [RISCV] Add TTI support for cpop with Zbb
Summary

This will tell loop idiom recognize that it can convert popcount loops
to intrinsics. I didn't bother checking for illegal types. Type legalization
knows how to split a ctpop into multiple ctops added together. Assuming we only
receive reasonable integer bit widths, a few cpop instructions added together
is probably better than the loop.

Diff Detail

Event Timeline

craig.topper created this revision.Mar 23 2021, 11:28 AM
Herald added subscribers: StephenFan, vkmr, evandro and 23 others. · View Herald TranscriptMar 23 2021, 11:28 AM
craig.topper requested review of this revision.Mar 23 2021, 11:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 23 2021, 11:28 AM
Herald added a subscriber: MaskRay. · View Herald Transcript
Harbormaster completed remote builds in B95313: Diff 332742.Mar 23 2021, 3:43 PM
frasercrmck added a comment.Mar 24 2021, 3:29 AM

Makes sense - nice. Should it test that we don't expect popcount without zbb enabled?

Sanity check: experimental-b implies experimental-zbb and so will also generate the popcount, right?

craig.topper updated this revision to Diff 333025.Mar 24 2021, 9:43 AM

Add more test RUN lines. Use update_test_checks.py because I'm not a big fan of -NOT checks.

frasercrmck added inline comments.Mar 24 2021, 10:40 AM
llvm/test/Transforms/LoopIdiom/RISCV/popcnt.ll
30

Maybe it's late in the day but I expected there not to be a loop here. Am I missing something?

craig.topper added inline comments.Mar 24 2021, 10:48 AM
llvm/test/Transforms/LoopIdiom/RISCV/popcnt.ll
30

LoopIdiomRecognize requires other passes to do the cleanup. The main goal of LoopIdiomRecognize is to rewrite the loop into countable form. It does this by putting the ctpop outside the loop and decrement it each iteration. Other passes will need to determine that the loop doesn't do anything else and remove it.

frasercrmck accepted this revision.Mar 24 2021, 10:51 AM

LGTM

llvm/test/Transforms/LoopIdiom/RISCV/popcnt.ll
30

Oh yes I see now how the PHIs in while.end.loopexit and while.end help show that. Thanks!

This revision is now accepted and ready to land.Mar 24 2021, 10:51 AM
This revision was landed with ongoing or failed builds.Mar 24 2021, 10:59 AM
Closed by commit rGf24f09d256ae: [RISCV] Add TTI support for cpop with Zbb (authored by craig.topper). · Explain Why
This revision was automatically updated to reflect the committed changes.
craig.topper added a commit: rGf24f09d256ae: [RISCV] Add TTI support for cpop with Zbb.
Harbormaster completed remote builds in B95518: Diff 333025.Mar 24 2021, 5:44 PM

Revision Contents

PathSize
llvm/
lib/
Target/
RISCV/
2 lines
6 lines
test/
Transforms/
LoopIdiom/
RISCV/
2 lines
322 lines

Diff 333053

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.h

Show First 20 Lines • Show All 42 Lines • ▼ Show 20 Linespublic:
int getIntImmCost(const APInt &Imm, Type *Ty, TTI::TargetCostKind CostKind); int getIntImmCost(const APInt &Imm, Type *Ty, TTI::TargetCostKind CostKind);
int getIntImmCostInst(unsigned Opcode, unsigned Idx, const APInt &Imm, int getIntImmCostInst(unsigned Opcode, unsigned Idx, const APInt &Imm,
Type *Ty, TTI::TargetCostKind CostKind, Type *Ty, TTI::TargetCostKind CostKind,
Instruction *Inst = nullptr); Instruction *Inst = nullptr);
int getIntImmCostIntrin(Intrinsic::ID IID, unsigned Idx, const APInt &Imm, int getIntImmCostIntrin(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
Type *Ty, TTI::TargetCostKind CostKind); Type *Ty, TTI::TargetCostKind CostKind);
TargetTransformInfo::PopcntSupportKind getPopcntSupport(unsigned TyWidth);
bool shouldExpandReduction(const IntrinsicInst *II) const; bool shouldExpandReduction(const IntrinsicInst *II) const;
bool supportsScalableVectors() const { return ST->hasStdExtV(); } bool supportsScalableVectors() const { return ST->hasStdExtV(); }
Optional<unsigned> getMaxVScale() const; Optional<unsigned> getMaxVScale() const;
TypeSize getRegisterBitWidth(TargetTransformInfo::RegisterKind K) const { TypeSize getRegisterBitWidth(TargetTransformInfo::RegisterKind K) const {
switch (K) { switch (K) {
case TargetTransformInfo::RGK_Scalar: case TargetTransformInfo::RGK_Scalar:
return TypeSize::getFixed(ST->getXLen()); return TypeSize::getFixed(ST->getXLen());
▲ Show 20 Lines • Show All 69 Lines • Show Last 20 Lines

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.cpp

Show First 20 Lines • Show All 89 Lines • ▼ Show 20 Lines
int RISCVTTIImpl::getIntImmCostIntrin(Intrinsic::ID IID, unsigned Idx, int RISCVTTIImpl::getIntImmCostIntrin(Intrinsic::ID IID, unsigned Idx,
const APInt &Imm, Type *Ty, const APInt &Imm, Type *Ty,
TTI::TargetCostKind CostKind) { TTI::TargetCostKind CostKind) {
// Prevent hoisting in unknown cases. // Prevent hoisting in unknown cases.
return TTI::TCC_Free; return TTI::TCC_Free;
} }
TargetTransformInfo::PopcntSupportKind
RISCVTTIImpl::getPopcntSupport(unsigned TyWidth) {
assert(isPowerOf2_32(TyWidth) && "Ty width must be power of 2");
return ST->hasStdExtZbb() ? TTI::PSK_FastHardware : TTI::PSK_Software;
}
bool RISCVTTIImpl::shouldExpandReduction(const IntrinsicInst *II) const { bool RISCVTTIImpl::shouldExpandReduction(const IntrinsicInst *II) const {
// Currently, the ExpandReductions pass can't expand scalable-vector // Currently, the ExpandReductions pass can't expand scalable-vector
// reductions, but we still request expansion as RVV doesn't support certain // reductions, but we still request expansion as RVV doesn't support certain
// reductions and the SelectionDAG can't legalize them either. // reductions and the SelectionDAG can't legalize them either.
switch (II->getIntrinsicID()) { switch (II->getIntrinsicID()) {
default: default:
return false; return false;
// These reductions have no equivalent in RVV // These reductions have no equivalent in RVV
Show All 31 Lines

llvm/test/Transforms/LoopIdiom/RISCV/lit.local.cfg

  • This file was added.
if not 'RISCV' in config.root.targets:
config.unsupported = True

llvm/test/Transforms/LoopIdiom/RISCV/popcnt.ll

  • This file was added.
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -loop-idiom -mtriple=riscv32 -mattr=+experimental-zbb -S < %s | FileCheck %s --check-prefixes=CPOP
; RUN: opt -loop-idiom -mtriple=riscv64 -mattr=+experimental-zbb -S < %s | FileCheck %s --check-prefixes=CPOP
; RUN: opt -loop-idiom -mtriple=riscv32 -mattr=+experimental-b -S < %s | FileCheck %s --check-prefixes=CPOP
; RUN: opt -loop-idiom -mtriple=riscv64 -mattr=+experimental-b -S < %s | FileCheck %s --check-prefixes=CPOP
; RUN: opt -loop-idiom -mtriple=riscv32 -S < %s | FileCheck %s --check-prefixes=NOCPOP
; RUN: opt -loop-idiom -mtriple=riscv64 -S < %s | FileCheck %s --check-prefixes=NOCPOP
; Mostly copied from AMDGPU version.
;To recognize this pattern:
;int popcount(unsigned long long a) {
; int c = 0;
; while (a) {
; c++;
; a &= a - 1;
; }
; return c;
;}
;
define i32 @popcount_i64(i64 %a) nounwind uwtable readnone ssp {
; CPOP-LABEL: @popcount_i64(
; CPOP-NEXT: entry:
; CPOP-NEXT: [[TMP0:%.*]] = call i64 @llvm.ctpop.i64(i64 [[A:%.*]])
; CPOP-NEXT: [[TMP1:%.*]] = trunc i64 [[TMP0]] to i32
; CPOP-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
; CPOP-NEXT: br i1 [[TMP2]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
; CPOP: while.body.preheader:
; CPOP-NEXT: br label [[WHILE_BODY:%.*]]
frasercrmckUnsubmitted
Not Done
ReplyInline Actions

Maybe it's late in the day but I expected there not to be a loop here. Am I missing something?

frasercrmck: Maybe it's late in the day but I expected there not to be a loop here. Am I missing something?
craig.topperAuthorUnsubmitted
Done
ReplyInline Actions

LoopIdiomRecognize requires other passes to do the cleanup. The main goal of LoopIdiomRecognize is to rewrite the loop into countable form. It does this by putting the ctpop outside the loop and decrement it each iteration. Other passes will need to determine that the loop doesn't do anything else and remove it.

craig.topper: LoopIdiomRecognize requires other passes to do the cleanup. The main goal of LoopIdiomRecognize…
frasercrmckUnsubmitted
Done
ReplyInline Actions

Oh yes I see now how the PHIs in while.end.loopexit and while.end help show that. Thanks!

frasercrmck: Oh yes I see now how the PHIs in `while.end.loopexit` and `while.end` help show that. Thanks!
; CPOP: while.body:
; CPOP-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]
; CPOP-NEXT: [[C_05:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
; CPOP-NEXT: [[A_ADDR_04:%.*]] = phi i64 [ [[AND:%.*]], [[WHILE_BODY]] ], [ [[A]], [[WHILE_BODY_PREHEADER]] ]
; CPOP-NEXT: [[INC]] = add nsw i32 [[C_05]], 1
; CPOP-NEXT: [[SUB:%.*]] = add i64 [[A_ADDR_04]], -1
; CPOP-NEXT: [[AND]] = and i64 [[SUB]], [[A_ADDR_04]]
; CPOP-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
; CPOP-NEXT: [[TOBOOL:%.*]] = icmp sle i32 [[TCDEC]], 0
; CPOP-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
; CPOP: while.end.loopexit:
; CPOP-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY]] ]
; CPOP-NEXT: br label [[WHILE_END]]
; CPOP: while.end:
; CPOP-NEXT: [[C_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; CPOP-NEXT: ret i32 [[C_0_LCSSA]]
;
; NOCPOP-LABEL: @popcount_i64(
; NOCPOP-NEXT: entry:
; NOCPOP-NEXT: [[TOBOOL3:%.*]] = icmp eq i64 [[A:%.*]], 0
; NOCPOP-NEXT: br i1 [[TOBOOL3]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
; NOCPOP: while.body.preheader:
; NOCPOP-NEXT: br label [[WHILE_BODY:%.*]]
; NOCPOP: while.body:
; NOCPOP-NEXT: [[C_05:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
; NOCPOP-NEXT: [[A_ADDR_04:%.*]] = phi i64 [ [[AND:%.*]], [[WHILE_BODY]] ], [ [[A]], [[WHILE_BODY_PREHEADER]] ]
; NOCPOP-NEXT: [[INC]] = add nsw i32 [[C_05]], 1
; NOCPOP-NEXT: [[SUB:%.*]] = add i64 [[A_ADDR_04]], -1
; NOCPOP-NEXT: [[AND]] = and i64 [[SUB]], [[A_ADDR_04]]
; NOCPOP-NEXT: [[TOBOOL:%.*]] = icmp eq i64 [[AND]], 0
; NOCPOP-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
; NOCPOP: while.end.loopexit:
; NOCPOP-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[INC]], [[WHILE_BODY]] ]
; NOCPOP-NEXT: br label [[WHILE_END]]
; NOCPOP: while.end:
; NOCPOP-NEXT: [[C_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; NOCPOP-NEXT: ret i32 [[C_0_LCSSA]]
;
entry:
%tobool3 = icmp eq i64 %a, 0
br i1 %tobool3, label %while.end, label %while.body
while.body: ; preds = %entry, %while.body
%c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
%a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]
%inc = add nsw i32 %c.05, 1
%sub = add i64 %a.addr.04, -1
%and = and i64 %sub, %a.addr.04
%tobool = icmp eq i64 %and, 0
br i1 %tobool, label %while.end, label %while.body
while.end: ; preds = %while.body, %entry
%c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
ret i32 %c.0.lcssa
}
define i32 @popcount_i32(i32 %a) nounwind uwtable readnone ssp {
; CPOP-LABEL: @popcount_i32(
; CPOP-NEXT: entry:
; CPOP-NEXT: [[TMP0:%.*]] = call i32 @llvm.ctpop.i32(i32 [[A:%.*]])
; CPOP-NEXT: [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0
; CPOP-NEXT: br i1 [[TMP1]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
; CPOP: while.body.preheader:
; CPOP-NEXT: br label [[WHILE_BODY:%.*]]
; CPOP: while.body:
; CPOP-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP0]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]
; CPOP-NEXT: [[C_05:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
; CPOP-NEXT: [[A_ADDR_04:%.*]] = phi i32 [ [[AND:%.*]], [[WHILE_BODY]] ], [ [[A]], [[WHILE_BODY_PREHEADER]] ]
; CPOP-NEXT: [[INC]] = add nsw i32 [[C_05]], 1
; CPOP-NEXT: [[SUB:%.*]] = add i32 [[A_ADDR_04]], -1
; CPOP-NEXT: [[AND]] = and i32 [[SUB]], [[A_ADDR_04]]
; CPOP-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
; CPOP-NEXT: [[TOBOOL:%.*]] = icmp sle i32 [[TCDEC]], 0
; CPOP-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
; CPOP: while.end.loopexit:
; CPOP-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[TMP0]], [[WHILE_BODY]] ]
; CPOP-NEXT: br label [[WHILE_END]]
; CPOP: while.end:
; CPOP-NEXT: [[C_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; CPOP-NEXT: ret i32 [[C_0_LCSSA]]
;
; NOCPOP-LABEL: @popcount_i32(
; NOCPOP-NEXT: entry:
; NOCPOP-NEXT: [[TOBOOL3:%.*]] = icmp eq i32 [[A:%.*]], 0
; NOCPOP-NEXT: br i1 [[TOBOOL3]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
; NOCPOP: while.body.preheader:
; NOCPOP-NEXT: br label [[WHILE_BODY:%.*]]
; NOCPOP: while.body:
; NOCPOP-NEXT: [[C_05:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
; NOCPOP-NEXT: [[A_ADDR_04:%.*]] = phi i32 [ [[AND:%.*]], [[WHILE_BODY]] ], [ [[A]], [[WHILE_BODY_PREHEADER]] ]
; NOCPOP-NEXT: [[INC]] = add nsw i32 [[C_05]], 1
; NOCPOP-NEXT: [[SUB:%.*]] = add i32 [[A_ADDR_04]], -1
; NOCPOP-NEXT: [[AND]] = and i32 [[SUB]], [[A_ADDR_04]]
; NOCPOP-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[AND]], 0
; NOCPOP-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
; NOCPOP: while.end.loopexit:
; NOCPOP-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[INC]], [[WHILE_BODY]] ]
; NOCPOP-NEXT: br label [[WHILE_END]]
; NOCPOP: while.end:
; NOCPOP-NEXT: [[C_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; NOCPOP-NEXT: ret i32 [[C_0_LCSSA]]
;
entry:
%tobool3 = icmp eq i32 %a, 0
br i1 %tobool3, label %while.end, label %while.body
while.body: ; preds = %entry, %while.body
%c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
%a.addr.04 = phi i32 [ %and, %while.body ], [ %a, %entry ]
%inc = add nsw i32 %c.05, 1
%sub = add i32 %a.addr.04, -1
%and = and i32 %sub, %a.addr.04
%tobool = icmp eq i32 %and, 0
br i1 %tobool, label %while.end, label %while.body
while.end: ; preds = %while.body, %entry
%c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
ret i32 %c.0.lcssa
}
define i32 @popcount_i128(i128 %a) nounwind uwtable readnone ssp {
; CPOP-LABEL: @popcount_i128(
; CPOP-NEXT: entry:
; CPOP-NEXT: [[TMP0:%.*]] = call i128 @llvm.ctpop.i128(i128 [[A:%.*]])
; CPOP-NEXT: [[TMP1:%.*]] = trunc i128 [[TMP0]] to i32
; CPOP-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
; CPOP-NEXT: br i1 [[TMP2]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
; CPOP: while.body.preheader:
; CPOP-NEXT: br label [[WHILE_BODY:%.*]]
; CPOP: while.body:
; CPOP-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]
; CPOP-NEXT: [[C_05:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
; CPOP-NEXT: [[A_ADDR_04:%.*]] = phi i128 [ [[AND:%.*]], [[WHILE_BODY]] ], [ [[A]], [[WHILE_BODY_PREHEADER]] ]
; CPOP-NEXT: [[INC]] = add nsw i32 [[C_05]], 1
; CPOP-NEXT: [[SUB:%.*]] = add i128 [[A_ADDR_04]], -1
; CPOP-NEXT: [[AND]] = and i128 [[SUB]], [[A_ADDR_04]]
; CPOP-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
; CPOP-NEXT: [[TOBOOL:%.*]] = icmp sle i32 [[TCDEC]], 0
; CPOP-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
; CPOP: while.end.loopexit:
; CPOP-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY]] ]
; CPOP-NEXT: br label [[WHILE_END]]
; CPOP: while.end:
; CPOP-NEXT: [[C_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; CPOP-NEXT: ret i32 [[C_0_LCSSA]]
;
; NOCPOP-LABEL: @popcount_i128(
; NOCPOP-NEXT: entry:
; NOCPOP-NEXT: [[TOBOOL3:%.*]] = icmp eq i128 [[A:%.*]], 0
; NOCPOP-NEXT: br i1 [[TOBOOL3]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
; NOCPOP: while.body.preheader:
; NOCPOP-NEXT: br label [[WHILE_BODY:%.*]]
; NOCPOP: while.body:
; NOCPOP-NEXT: [[C_05:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
; NOCPOP-NEXT: [[A_ADDR_04:%.*]] = phi i128 [ [[AND:%.*]], [[WHILE_BODY]] ], [ [[A]], [[WHILE_BODY_PREHEADER]] ]
; NOCPOP-NEXT: [[INC]] = add nsw i32 [[C_05]], 1
; NOCPOP-NEXT: [[SUB:%.*]] = add i128 [[A_ADDR_04]], -1
; NOCPOP-NEXT: [[AND]] = and i128 [[SUB]], [[A_ADDR_04]]
; NOCPOP-NEXT: [[TOBOOL:%.*]] = icmp eq i128 [[AND]], 0
; NOCPOP-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
; NOCPOP: while.end.loopexit:
; NOCPOP-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[INC]], [[WHILE_BODY]] ]
; NOCPOP-NEXT: br label [[WHILE_END]]
; NOCPOP: while.end:
; NOCPOP-NEXT: [[C_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; NOCPOP-NEXT: ret i32 [[C_0_LCSSA]]
;
entry:
%tobool3 = icmp eq i128 %a, 0
br i1 %tobool3, label %while.end, label %while.body
while.body: ; preds = %entry, %while.body
%c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
%a.addr.04 = phi i128 [ %and, %while.body ], [ %a, %entry ]
%inc = add nsw i32 %c.05, 1
%sub = add i128 %a.addr.04, -1
%and = and i128 %sub, %a.addr.04
%tobool = icmp eq i128 %and, 0
br i1 %tobool, label %while.end, label %while.body
while.end: ; preds = %while.body, %entry
%c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
ret i32 %c.0.lcssa
}
; To recognize this pattern:
;int popcount(unsigned long long a, int mydata1, int mydata2) {
; int c = 0;
; while (a) {
; c++;
; a &= a - 1;
; mydata1 *= c;
; mydata2 *= (int)a;
; }
; return c + mydata1 + mydata2;
;}
define i32 @popcount2(i64 %a, i32 %mydata1, i32 %mydata2) nounwind uwtable readnone ssp {
; CPOP-LABEL: @popcount2(
; CPOP-NEXT: entry:
; CPOP-NEXT: [[TMP0:%.*]] = call i64 @llvm.ctpop.i64(i64 [[A:%.*]])
; CPOP-NEXT: [[TMP1:%.*]] = trunc i64 [[TMP0]] to i32
; CPOP-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
; CPOP-NEXT: br i1 [[TMP2]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
; CPOP: while.body.preheader:
; CPOP-NEXT: br label [[WHILE_BODY:%.*]]
; CPOP: while.body:
; CPOP-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]
; CPOP-NEXT: [[C_013:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
; CPOP-NEXT: [[MYDATA2_ADDR_012:%.*]] = phi i32 [ [[MUL1:%.*]], [[WHILE_BODY]] ], [ [[MYDATA2:%.*]], [[WHILE_BODY_PREHEADER]] ]
; CPOP-NEXT: [[MYDATA1_ADDR_011:%.*]] = phi i32 [ [[MUL:%.*]], [[WHILE_BODY]] ], [ [[MYDATA1:%.*]], [[WHILE_BODY_PREHEADER]] ]
; CPOP-NEXT: [[A_ADDR_010:%.*]] = phi i64 [ [[AND:%.*]], [[WHILE_BODY]] ], [ [[A]], [[WHILE_BODY_PREHEADER]] ]
; CPOP-NEXT: [[INC]] = add nsw i32 [[C_013]], 1
; CPOP-NEXT: [[SUB:%.*]] = add i64 [[A_ADDR_010]], -1
; CPOP-NEXT: [[AND]] = and i64 [[SUB]], [[A_ADDR_010]]
; CPOP-NEXT: [[MUL]] = mul nsw i32 [[INC]], [[MYDATA1_ADDR_011]]
; CPOP-NEXT: [[CONV:%.*]] = trunc i64 [[AND]] to i32
; CPOP-NEXT: [[MUL1]] = mul nsw i32 [[CONV]], [[MYDATA2_ADDR_012]]
; CPOP-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
; CPOP-NEXT: [[TOBOOL:%.*]] = icmp sle i32 [[TCDEC]], 0
; CPOP-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
; CPOP: while.end.loopexit:
; CPOP-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY]] ]
; CPOP-NEXT: [[MUL_LCSSA:%.*]] = phi i32 [ [[MUL]], [[WHILE_BODY]] ]
; CPOP-NEXT: [[MUL1_LCSSA:%.*]] = phi i32 [ [[MUL1]], [[WHILE_BODY]] ]
; CPOP-NEXT: br label [[WHILE_END]]
; CPOP: while.end:
; CPOP-NEXT: [[C_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; CPOP-NEXT: [[MYDATA2_ADDR_0_LCSSA:%.*]] = phi i32 [ [[MYDATA2]], [[ENTRY]] ], [ [[MUL1_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; CPOP-NEXT: [[MYDATA1_ADDR_0_LCSSA:%.*]] = phi i32 [ [[MYDATA1]], [[ENTRY]] ], [ [[MUL_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; CPOP-NEXT: [[ADD:%.*]] = add i32 [[MYDATA2_ADDR_0_LCSSA]], [[MYDATA1_ADDR_0_LCSSA]]
; CPOP-NEXT: [[ADD2:%.*]] = add i32 [[ADD]], [[C_0_LCSSA]]
; CPOP-NEXT: ret i32 [[ADD2]]
;
; NOCPOP-LABEL: @popcount2(
; NOCPOP-NEXT: entry:
; NOCPOP-NEXT: [[TOBOOL9:%.*]] = icmp eq i64 [[A:%.*]], 0
; NOCPOP-NEXT: br i1 [[TOBOOL9]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
; NOCPOP: while.body.preheader:
; NOCPOP-NEXT: br label [[WHILE_BODY:%.*]]
; NOCPOP: while.body:
; NOCPOP-NEXT: [[C_013:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
; NOCPOP-NEXT: [[MYDATA2_ADDR_012:%.*]] = phi i32 [ [[MUL1:%.*]], [[WHILE_BODY]] ], [ [[MYDATA2:%.*]], [[WHILE_BODY_PREHEADER]] ]
; NOCPOP-NEXT: [[MYDATA1_ADDR_011:%.*]] = phi i32 [ [[MUL:%.*]], [[WHILE_BODY]] ], [ [[MYDATA1:%.*]], [[WHILE_BODY_PREHEADER]] ]
; NOCPOP-NEXT: [[A_ADDR_010:%.*]] = phi i64 [ [[AND:%.*]], [[WHILE_BODY]] ], [ [[A]], [[WHILE_BODY_PREHEADER]] ]
; NOCPOP-NEXT: [[INC]] = add nsw i32 [[C_013]], 1
; NOCPOP-NEXT: [[SUB:%.*]] = add i64 [[A_ADDR_010]], -1
; NOCPOP-NEXT: [[AND]] = and i64 [[SUB]], [[A_ADDR_010]]
; NOCPOP-NEXT: [[MUL]] = mul nsw i32 [[INC]], [[MYDATA1_ADDR_011]]
; NOCPOP-NEXT: [[CONV:%.*]] = trunc i64 [[AND]] to i32
; NOCPOP-NEXT: [[MUL1]] = mul nsw i32 [[CONV]], [[MYDATA2_ADDR_012]]
; NOCPOP-NEXT: [[TOBOOL:%.*]] = icmp eq i64 [[AND]], 0
; NOCPOP-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
; NOCPOP: while.end.loopexit:
; NOCPOP-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[INC]], [[WHILE_BODY]] ]
; NOCPOP-NEXT: [[MUL_LCSSA:%.*]] = phi i32 [ [[MUL]], [[WHILE_BODY]] ]
; NOCPOP-NEXT: [[MUL1_LCSSA:%.*]] = phi i32 [ [[MUL1]], [[WHILE_BODY]] ]
; NOCPOP-NEXT: br label [[WHILE_END]]
; NOCPOP: while.end:
; NOCPOP-NEXT: [[C_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; NOCPOP-NEXT: [[MYDATA2_ADDR_0_LCSSA:%.*]] = phi i32 [ [[MYDATA2]], [[ENTRY]] ], [ [[MUL1_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; NOCPOP-NEXT: [[MYDATA1_ADDR_0_LCSSA:%.*]] = phi i32 [ [[MYDATA1]], [[ENTRY]] ], [ [[MUL_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
; NOCPOP-NEXT: [[ADD:%.*]] = add i32 [[MYDATA2_ADDR_0_LCSSA]], [[MYDATA1_ADDR_0_LCSSA]]
; NOCPOP-NEXT: [[ADD2:%.*]] = add i32 [[ADD]], [[C_0_LCSSA]]
; NOCPOP-NEXT: ret i32 [[ADD2]]
;
entry:
%tobool9 = icmp eq i64 %a, 0
br i1 %tobool9, label %while.end, label %while.body
while.body: ; preds = %entry, %while.body
%c.013 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
%mydata2.addr.012 = phi i32 [ %mul1, %while.body ], [ %mydata2, %entry ]
%mydata1.addr.011 = phi i32 [ %mul, %while.body ], [ %mydata1, %entry ]
%a.addr.010 = phi i64 [ %and, %while.body ], [ %a, %entry ]
%inc = add nsw i32 %c.013, 1
%sub = add i64 %a.addr.010, -1
%and = and i64 %sub, %a.addr.010
%mul = mul nsw i32 %inc, %mydata1.addr.011
%conv = trunc i64 %and to i32
%mul1 = mul nsw i32 %conv, %mydata2.addr.012
%tobool = icmp eq i64 %and, 0
br i1 %tobool, label %while.end, label %while.body
while.end: ; preds = %while.body, %entry
%c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
%mydata2.addr.0.lcssa = phi i32 [ %mydata2, %entry ], [ %mul1, %while.body ]
%mydata1.addr.0.lcssa = phi i32 [ %mydata1, %entry ], [ %mul, %while.body ]
%add = add i32 %mydata2.addr.0.lcssa, %mydata1.addr.0.lcssa
%add2 = add i32 %add, %c.0.lcssa
ret i32 %add2
}