[InstSimplify] Accept more loop-invariant cases in ThreadBinOpOverPHI

[uweigand]

Summary

The ThreadBinOpOverPHI routine attempts to detect loop-invariant values
by ignoring a PHI node input that equals the PHI node itself.

However, we can accept a slightly more general case: if we perform
some operation on the PHI node, and the result of that operation on
the PHI input equals the operation performed on the PHI node itself,
the result of the operation is loop invariant (even if the PHI node
itself is not), and we can still do the simplifcation.

See the attached test case for an example, where "phi & -256" is
loop invariant and can be simplified even though phi itself is not.

lib/Analysis/InstructionSimplify.cpp

static Value *ThreadBinOpOverPHI(Instruction::BinaryOps Opcode, Value *LHS,
   // Evaluate the BinOp on the incoming phi values.
   Value *CommonValue = nullptr;
   for (Value *Incoming : PI->incoming_values()) {
     // If the incoming value is the phi node itself, it can safely be skipped.
     if (Incoming == PI) continue;
     Value *V = PI == LHS ?
       SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) :
       SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse);
+    // If the simplified operation is equal to the original operation on the
+    // PHI node, it can likewise be safely skipped.
+    if (BinaryOperator *Op = dyn_cast_or_null<BinaryOperator>(V))
+      if (Op->getOpcode() == Opcode &&
+          Op->getOperand(0) == LHS && Op->getOperand(1) == RHS)
+      continue;
     // If the operation failed to simplify, or simplified to a different value
     // to previously, then give up.
     if (!V || (CommonValue && V != CommonValue))
       return nullptr;
     CommonValue = V;
   }
 
   return CommonValue;

test/Transforms/InstSimplify/phi.ll

b:
   br label %c
 
 c:
   %cc = phi i32 [ %bb, %b ], [%aa, %a ]
   %d = urem i32 %cc, 2
   %e = icmp eq i32 %d, 0
   ret i1 %e
 }
+
+define i32 @test2(i1 %c1, i1 %c2, i32 %x) {
+; CHECK-LABEL: @test2
+; CHECK-NEXT:    [[Y:%.*]] = and i32 %x, -256
+; CHECK:    ret i32 [[Y]]
+;
+  %y = and i32 %x, -256
+  br i1 %c1, label %true, label %false
+true:
+  %a = or i32 %y, 1
+  br label %loop
+false:
+  %b = or i32 %y, 2
+  br label %loop
+loop:
+  %p = phi i32 [ %a, %true ], [ %b, %false ], [ %r, %loop ]
+  %r = and i32 %p, -256
+  br i1 %c2, label %ret, label %loop
+ret:
+  ret i32 %r
+}
+