llvm dev - Jan 2010 - [LLVMdev] [llvm-commits] [llvm] r92458 - in /llvm/trunk: lib/Target/README.txt lib/Transforms/Scalar/InstructionCombining.cpp test/Transforms/InstCombine/or.ll

Hi Bill-

For what it's worth, a simple truth table proves Chris correct.

Alastair

On 5 Jan 2010, at 02:46, Bill Wendling wrote:
> On Jan 3, 2010, at 10:04 PM, Chris Lattner wrote:
> 
>> Author: lattner
>> Date: Mon Jan  4 00:03:59 2010
>> New Revision: 92458
>> 
>> URL: http://llvm.org/viewvc/llvm-project?rev=92458&view=rev
>> Log:
>> implement an instcombine xform needed by clang's codegen
>> on the example in PR4216.  This doesn't trigger in the testsuite,
>> so I'd really appreciate someone scrutinizing the logic for
>> correctness.
>> 
>> --- llvm/trunk/lib/Transforms/Scalar/InstructionCombining.cpp
(original)
>> +++ llvm/trunk/lib/Transforms/Scalar/InstructionCombining.cpp Mon Jan 
4 00:03:59 2010
>> @@ -5213,12 +5213,30 @@
>>            return ReplaceInstUsesWith(I, B);
>>        }
>>      }
>> -      V1 = 0; V2 = 0; V3 = 0;
>> +      
>> +      // ((V | N) & C1) | (V & C2) --> (V|N) & (C1|C2)
>> +      // iff (C1&C2) == 0 and (N&~C1) == 0
>> +      if ((C1->getValue() & C2->getValue()) == 0) {
>> +        if (match(A, m_Or(m_Value(V1), m_Value(V2))) &&
>> +            ((V1 == B && MaskedValueIsZero(V2,
~C1->getValue())) ||  // (V|N)
>> +             (V2 == B && MaskedValueIsZero(V1,
~C1->getValue()))))   // (N|V)
>> +          return BinaryOperator::CreateAnd(A,
>> +                               ConstantInt::get(A->getContext(),
>> +                                               
C1->getValue()|C2->getValue()));
>> +        // Or commutes, try both ways.
>> +        if (match(B, m_Or(m_Value(V1), m_Value(V2))) &&
>> +            ((V1 == A && MaskedValueIsZero(V2,
~C2->getValue())) ||  // (V|N)
>> +             (V2 == A && MaskedValueIsZero(V1,
~C2->getValue()))))   // (N|V)
>> +          return BinaryOperator::CreateAnd(B,
>> +                               ConstantInt::get(B->getContext(),
>> +                                               
C1->getValue()|C2->getValue()));
>> +      }
>>    }
>> 
> Hi Chris,
> 
> I'm having trouble verifying the logic here. I'm probably doing
something wrong. First a comment, if C1 and C2 are both zero, then this is zero.
It can also be simplified if either one is zero. I don't know if those
situations are caught before it gets to this point.
> 
> Okay. Here's my derivation of your transformation:
> 
>  [(V | N) & C1] | (V & C2)
> = {[(V | N) & C1] | V} & {[(V | N) & C1] | C2}
> = {[(V | N | V) & (C1 | V)]} & {[(V | N | C2) & (C1 | C2)]}
> = (V | N) & (V | C1) & (V | N | C2) & (C1 | C2)
> 
> Note that
> 
>  A & (A | B) = A
> 
> So, (V | N) & [(V | N) | C2] = (V | N)
> 
> Therefore, we have
> 
>  (V|N) & (V|C1) & (C1|C2)
> 
> Here's where I get stuck. I can expand out the (V|C1) term, but it
doesn't appear to get me closer to your result. I freely admit that I
probably made an error. :-)
> 
> Could you provide more insight into the result you got?
> 
> -bw
> 
> 
> _______________________________________________
> llvm-commits mailing list
> llvm-commits at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits