Add comments

[oota-llvm.git] / lib / Transforms / Scalar / InstructionCombining.cpp

diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp
index 7054661244962aeee874b9fc2751156b43b6c3b5..6d5502533a042f87bdbc2147790ca70cb2679393 100644 (file)
--- a/lib/Transforms/Scalar/InstructionCombining.cpp
+++ b/lib/Transforms/Scalar/InstructionCombining.cpp
@@ -12,6 +12,15 @@
 //
 // This is a simple worklist driven algorithm.
 //
+// This pass guarantees that the following cannonicalizations are performed on
+// the program:
+//    1. If a binary operator has a constant operand, it is moved to the RHS
+//    2. Logical operators with constant operands are always grouped so that
+//       'or's are performed first, then 'and's, then 'xor's.
+//    3. SetCC instructions are converted from <,>,<=,>= to ==,!= if possible
+//    4. All SetCC instructions on boolean values are replaced with logical ops
+//    N. This list is incomplete
+//
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
@@ -497,23 +506,25 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
     if (RHS->isAllOnesValue())
       return ReplaceInstUsesWith(I, Op0);
 
-    if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0))
+    if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
+      Value *X = Op0I->getOperand(0);
       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
         if (Op0I->getOpcode() == Instruction::Xor) {
-          if (isOnlyUse(Op0)) {
+          if ((*RHS & *Op0CI)->isNullValue()) {
+            // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0
+            return BinaryOperator::create(Instruction::And, X, RHS);
+          } else if (isOnlyUse(Op0)) {
             // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
             std::string Op0Name = Op0I->getName(); Op0I->setName("");
             Instruction *And = BinaryOperator::create(Instruction::And,
-                                                      Op0I->getOperand(0), RHS,
-                                                      Op0Name);
+                                                      X, RHS, Op0Name);
             InsertNewInstBefore(And, I);
             return BinaryOperator::create(Instruction::Xor, And, *RHS & *Op0CI);
           }
         } else if (Op0I->getOpcode() == Instruction::Or) {
           // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0
           if ((*RHS & *Op0CI)->isNullValue())
-            return BinaryOperator::create(Instruction::And, Op0I->getOperand(0),
-                                          RHS);
+            return BinaryOperator::create(Instruction::And, X, RHS);
 
           Constant *Together = *RHS & *Op0CI;
           if (Together == RHS) // (X | C) & C --> C
@@ -523,14 +534,14 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
             if (Together != Op0CI) {
               // (X | C1) & C2 --> (X | (C1&C2)) & C2
               std::string Op0Name = Op0I->getName(); Op0I->setName("");
-              Instruction *Or = BinaryOperator::create(Instruction::Or,
-                                                        Op0I->getOperand(0),
-                                                        Together, Op0Name);
+              Instruction *Or = BinaryOperator::create(Instruction::Or, X,
+                                                       Together, Op0Name);
               InsertNewInstBefore(Or, I);
               return BinaryOperator::create(Instruction::And, Or, RHS);
             }
           }
         }
+    }
   }
 
   Value *Op0NotVal = dyn_castNotVal(Op0);
@@ -623,22 +634,28 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   if (Op0 == Op1)
     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 
-  if (ConstantIntegral *Op1C = dyn_cast<ConstantIntegral>(Op1)) {
+  if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
     // xor X, 0 == X
-    if (Op1C->isNullValue())
+    if (RHS->isNullValue())
       return ReplaceInstUsesWith(I, Op0);
 
-    // Is this a "NOT" instruction?
-    if (Op1C->isAllOnesValue()) {
-      // xor (xor X, -1), -1 = not (not X) = X
-      if (Value *X = dyn_castNotVal(Op0))
-        return ReplaceInstUsesWith(I, X);
-
+    if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
       // xor (setcc A, B), true = not (setcc A, B) = setncc A, B
-      if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0))
-        if (SCI->use_size() == 1)
+      if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0I))
+        if (RHS == ConstantBool::True && SCI->use_size() == 1)
           return new SetCondInst(SCI->getInverseCondition(),
                                  SCI->getOperand(0), SCI->getOperand(1));
+          
+      if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
+        if (Op0I->getOpcode() == Instruction::And) {
+          // (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0
+          if ((*RHS & *Op0CI)->isNullValue())
+            return BinaryOperator::create(Instruction::Or, Op0, RHS);
+        } else if (Op0I->getOpcode() == Instruction::Or) {
+          // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
+          if ((*RHS & *Op0CI) == RHS)
+            return BinaryOperator::create(Instruction::And, Op0, ~*RHS);
+        }
     }
   }