Fix urem instruction with power of two to compute known bit.

[akuharev]

Summary

Recursive computeKnownBits initiates parameters KnownZero and KnownOne
at the begining so we should use KnownZero2 and KnownOne2.
We should use computation for returned Known bits.
Despite of the comments, isPowerOf2 returns true for RA is power of two = 0, i.e. RA = 1,

[akuharev]

This patch fixes bug 19636

[akuharev]

For power of two urem similiar to and instruction

[• rafael]

LGTM with a code nit and a test change.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2191

This assignment is redundant. How about just

// The upper bits are all zero, the lower ones are unchanged.
KnownOne = KnownOne2 & LowBits;
KnownZero = KnowZero2 | ~LowBits;

test/CodeGen/Generic/computeKnownBits_urem.ll

1 ↗

(On Diff #9705)

This should probably also check the generated assembly. It is fine to move it to a cpu specific directory and use a -mtriple.

[akuharev]

Remove redundant lines

[akuharev]

I check asm output in new version by
llc -mtriple=i386-pc-win32 computeKnownBits_urem.ll
Result is very simple and right:

  _main:                                  # @main
  # BB#0:                                 # %entry
  	pushl	%eax
  	movl	$1, (%esp)
  	movl	$1, %eax
  	popl	%edx
  	retl

Algorithm is sufficiently complex and the same result in asm
can be obtained by the different ways with slightly different IR file.
Changed code works when simplification begins from not "urem" instruction.
Instructions "and" and "or" set KnownOne and KnownZero mutually.
Instruction "load" in computeKnownBits cuts initialization of %a.
Result of changed code work is simplification with message

Replacing.2 .......

if KnownOne and KnownZero leads to definite result
then next message is

With: 0x{{[0-9a-f]+}}: i32 = Constant ....

[akuharev]

I don't have commit access. Thanks for the review, and please commit.

[akuharev]

Variant with -mtriple=i386-pc-win32

[akuharev]

Changed patch according to changed trunk

[• rafael]

Sorry, I missed this.

I committed the patch (r209902 ). I just updated the test to check for
assembly (as opposed to just generating it).

Normally in LLVM we test that the result is valid, not exactly the
steps that a transformation is doing. Doing that gives more freedom at
modifying the passes in the future.

We do try to write small tests and test the smallest part of llvm that
we can. It is really unfortunate with codegen that such a large piece
of code needs to be run, but I don't think that checking deubg output
is the correct way to fix that.

[akuharev]

Thanks for the explanation.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
       }
     }
     break;
   case ISD::UREM: {
     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
       const APInt &RA = Rem->getAPIntValue();
       if (RA.isPowerOf2()) {
         APInt LowBits = (RA - 1);
-        KnownZero |= ~LowBits;
-        computeKnownBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
+        computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
+
+        // The upper bits are all zero, the lower ones are unchanged.
+        KnownZero = KnownZero2 | ~LowBits;
+        KnownOne = KnownOne2 & LowBits;        
         break;
       }
     }
 
     // Since the result is less than or equal to either operand, any leading
     // zero bits in either operand must also exist in the result.
     computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);

test/CodeGen/X86/computeKnownBits_urem.ll

+; RUN: llc -debug -mtriple=i386-pc-win32 %s -o /dev/null 2>&1 | FileCheck %s
+define i32 @main() #0 {
+entry:
+  %a = alloca i32, align 4
+  store i32 1, i32* %a, align 4
+  %0 = load i32* %a, align 4
+  %or = or i32 1, %0
+  %and = and i32 1, %or
+  %rem = urem i32 %and, 1
+  %add = add i32 %rem, 1
+  ret i32 %add
+}
+; CHECK: Replacing.2 0x{{[0-9a-f]+}}: i32 = urem 0x{{[0-9a-f]+}}, 0x{{[0-9a-f]+}} [ORD=7]
+; CHECK: With: 0x{{[0-9a-f]+}}: i32 = Constant<0>