This is an archive of the discontinued LLVM Phabricator instance.

[LIR] Add CTTZ support part2
Needs ReviewPublic

Authored by ychen on Dec 18 2018, 7:20 PM.

Details

Summary

Add a second idiom recognition (BitScan idiom) where bits of input variable are scanned in order until hit a set bit:
scan-from-left-to-right means CTLZ; scan-from-right-to-left means CTTZ. The starting bit index do not have to be first bit if we could prove
from CFG that preceding bits are zero.

Diff Detail

Event Timeline

ychen created this revision.Dec 18 2018, 7:20 PM
ychen edited the summary of this revision. (Show Details)Dec 18 2018, 7:21 PM
ychen added reviewers: craig.topper, evstupac.
ychen added a parent revision: D55876: [LIR] Add CTTZ support.
ychen added a comment.Jan 5 2019, 6:55 PM

gentle ping

craig.topper added inline comments.Jan 7 2019, 5:22 PM
lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1511

Why are we doing this a different way than detectShiftUntilZeroIdiom? And why does the base need to be constant?

1578

Why can't we limit to just checking the preheader condition like the shiftUntilZero? Do you have more complex real world examples you're trying to handle?

1761

Can you write this as

bool FoundBitScanIdiom;
if (detectShiftUntilZero...)
  FoundBitScanIdiom = false;
else if (detectShiftUntilZero...)
  FoundBitCanIdiom = true;
else
  return false

That should make it easier to add a third idiom in the future.

ychen updated this revision to Diff 181219.Jan 11 2019, 1:01 AM
  • allow non-constant CntPhi base
ychen marked 3 inline comments as done.Jan 11 2019, 5:52 AM
ychen added inline comments.
lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1511

I thought they are an equivalent way to detect CntPhi and IMHO more clear to read than the way used by detectShiftUntilZeroIdiom.

Making the base constant is unintentional. Updated patch to reflect that.

1578

Other than checking the input is non-zero, a naive implementation of bitscan idiom like "cttz_bitscan_shl" and "cttz_bitscan_shl_phi" (in cttz.ll) have the preheader that checks the "first bit" of the input (check it is zero). Here is to generalize the native pattern 1: preheader is generalized to any block that dominates the loop; 2. "initial bit" is generalized to "first <x> bits where <x> is within the range of bit indexes that checked by the loop"

I don't have a complex real world example, but thought this help recognize cttz pattern out of more than just the naive implementation with a few more checks.

craig.topper added inline comments.Jan 15 2019, 2:52 PM
lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1511

I'm sure they are equivalent. I just think we should try to have consistent implementations for the same thing in the same area of the compiler.

ychen updated this revision to Diff 182252.Jan 17 2019, 4:38 AM
  • update
ychen marked 2 inline comments as done.Jan 17 2019, 4:39 AM
ychen added inline comments.
lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1511

updated

ychen marked an inline comment as done.Jan 17 2019, 6:35 AM