This is an archive of the discontinued LLVM Phabricator instance.

[LoopIdiomRecognize] Support for loops that use LSHR instruction added.
ClosedPublic

Authored by ovmold on Jun 20 2018, 2:55 AM.

Details

Summary

In the 'detectCTLZIdiom' function support for loops that use LSHR instruction instead of ASHR has been added.

The problem is that for the following piece of code no '@llvm.ctlz' instruction has been generated in the resulting test.ll file when compiling as "clang -S -O3 -march=core-avx2 -emit-llvm test.c". The reason for this is that the LSHR instruction is used instead of ASHR in the LLVM IR when we get into the 'detectCTLZIdiom' function.

int lzcnt(int x) {
     int count = 0;
     while (x > 0)  {
          count++;
          x = x >> 1;
     }
    return count;
}

int main() {
    int x;
    scanf("%d", &x);
    int y = lzcnt(x);
    printf("count  = %d\n", y);
    return 0;
}

Diff Detail

Repository
rL LLVM

Event Timeline

ovmold created this revision.Jun 20 2018, 2:55 AM
ovmold changed the repository for this revision from rC Clang to rL LLVM.Jun 20 2018, 3:43 AM
ovmold removed a project: Restricted Project.
ovmold removed a subscriber: cfe-commits.
craig.topper added inline comments.Jun 20 2018, 9:46 AM
lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1320 ↗(On Diff #152039)

Remove the FIXME rather than marking it done.

1405 ↗(On Diff #152039)

Remvoe the FIXME

1564 ↗(On Diff #152039)

Space after 'if' before paren

1566 ↗(On Diff #152039)

Line this up with the InitX on the line above.

1570 ↗(On Diff #152039)

Space before 'else'

test/Transforms/LoopIdiom/X86/ctlz.ll
118 ↗(On Diff #152039)

Where are the checks for this test case?

121 ↗(On Diff #152039)

Remove the first 3 instructions which calculate an absolute value. And use %n in place of %abs_n in the remaining code.

213 ↗(On Diff #152039)

Remvoe the absolute value

299 ↗(On Diff #152039)

Remove the absolute value

388 ↗(On Diff #152039)

Remove the absolute value.

ovmold updated this revision to Diff 152438.Jun 22 2018, 1:55 AM

Changes in code formatting and test cases according to the reviewer's comments.

This def seems to be relative to your previous patch and not relative to the current code in trunk.

Oops that should have said "diff" not "def"

ovmold updated this revision to Diff 152586.EditedJun 23 2018, 1:05 AM

One more attempt: two commits are combined in one patch file.

bryant added a subscriber: bryant.Jun 23 2018, 2:38 AM
  • Would you mind re-upping this with full context?
  • Could you clang-format your changes (not necessarily the entire file)?
  • Also, the below condition would not be necessary for LShr:
// Make sure the initial value can't be negative otherwise the ashr in the
// loop might never reach zero which would make the loop infinite.
// TODO: Support loops that use lshr and wouldn't need this check.
if (!isKnownNonNegative(InitX, *DL))
  return false;
ovmold updated this revision to Diff 152590.Jun 23 2018, 5:16 AM
  • Would you mind re-upping this with full context?

Diff with full context re-upped.

  • Could you clang-format your changes (not necessarily the entire file)?

Done.

  • Also, the below condition would not be necessary for LShr:

    Make sure the initial value can't be negative otherwise the ashr in the loop might never reach zero which would make the loop infinite. // TODO: Support loops that use lshr and wouldn't need this check. if (!isKnownNonNegative(InitX, *DL)) return false;

This has been already done by the first patch. In the current patch it is also present.

craig.topper added inline comments.Jun 24 2018, 6:23 PM
lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1569 ↗(On Diff #152590)

Can you add

else
  llvm_unreachable("Unexpected opcode!);

It should only be of the two shift opcodes and if for some reason that fails we should error. It also make the code behavior more obvious.

ovmold updated this revision to Diff 152836.Jun 25 2018, 10:25 PM

Can you add

else
  llvm_unreachable("Unexpected opcode!);

It should only be of the two shift opcodes and if for some reason that fails we should error. It also make the code behavior more obvious.

'llvm_unreachable("Unexpected opcode!")' added, code formatting done

This revision is now accepted and ready to land.Jun 25 2018, 10:37 PM

Who can commit my changes? I have no rights to commit myself.

craig.topper edited the summary of this revision. (Show Details)Jul 7 2018, 6:24 PM
This revision was automatically updated to reflect the committed changes.