Page MenuHomePhabricator

PR41162 Implement LKK remainder and divisibility algorithms [srem]
Needs ReviewPublic

Authored by TG908 on Oct 6 2019, 3:48 PM.
This revision needs review, but there are no reviewers specified.



This patch implements the LKK algorithm for optimizing remainder computations with a constant divisor.
LKK is an improvement on the previously used Granlund-Montgomery-Warren approach.

UREM Patch
LKK Paper


  • I added functions foldSREM and foldUREM in DAGCombiner.cpp to handle signed and unsigned remainders.
  • Tests have been performed on x86 for every 8 bit signed and unsigned remainder operation.
  • Tests for 32 bit signed remainders have been performed on a large set of random integers.
  • I also added some llc code gen tests.
  • I am a bit unsure whether my isOperationLegalOrCustomOrPromote checks are too strict.

Diff Detail