Page MenuHomePhabricator

[LIR] Add CTTZ support part2
Needs ReviewPublic

Authored by tabloid.adroit 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

tabloid.adroit created this revision.Dec 18 2018, 7:20 PM
tabloid.adroit edited the summary of this revision. (Show Details)Dec 18 2018, 7:21 PM
craig.topper added inline comments.Jan 7 2019, 5:22 PM
lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1544

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

1611

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?

1749–1760

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.

  • allow non-constant CntPhi base
tabloid.adroit marked 3 inline comments as done.Jan 11 2019, 5:52 AM
tabloid.adroit added inline comments.
lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1544

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.

1611

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
1544

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.

tabloid.adroit marked 2 inline comments as done.Jan 17 2019, 4:39 AM
tabloid.adroit added inline comments.
lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1544

updated

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