[LoopDeletion] Support selects when symbolically evaluating 1st iteration

[mkazantsev]

Summary

Adds support for selects for which we know value on the 1st iteration.

[mkazantsev]

Per underlying patch change

[mkazantsev]

Returning this patch from dark depths of oblivion.

[nikic]

LGTM

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

Value *RHS =
         getValueOnFirstIteration(BO->getOperand(1), FirstIterValue, SQ);
     FirstIterV = SimplifyBinOp(BO->getOpcode(), LHS, RHS, SQ);
   } else if (auto *Cmp = dyn_cast<ICmpInst>(V)) {
     Value *LHS =
         getValueOnFirstIteration(Cmp->getOperand(0), FirstIterValue, SQ);
     Value *RHS =
         getValueOnFirstIteration(Cmp->getOperand(1), FirstIterValue, SQ);
     FirstIterV = SimplifyICmpInst(Cmp->getPredicate(), LHS, RHS, SQ);
+  } else if (auto *Select = dyn_cast<SelectInst>(V)) {
+    Value *Cond =
+        getValueOnFirstIteration(Select->getCondition(), FirstIterValue, SQ);
+    if (auto *C = dyn_cast<ConstantInt>(Cond)) {
+      auto *Selected = C->isAllOnesValue() ? Select->getTrueValue()
+                                           : Select->getFalseValue();
+      FirstIterV = getValueOnFirstIteration(Selected, FirstIterValue, SQ);
+    }
   }
   if (!FirstIterV)
     FirstIterV = V;
   FirstIterValue[V] = FirstIterV;
   return FirstIterV;
 }
 
 // Try to prove that one of conditions that dominates the latch must exit on 1st

llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll

 done:                                             ; preds = %backedge
   %sum.next.lcssa = phi i32 [ %sum.next, %loop ]
   ret i32 %sum.next.lcssa
 
 failure:
   unreachable
 }
 
-; TODO: We can break the backedge here.
 define i32 @test_select_const(i32 %x) {
 ; CHECK-LABEL: @test_select_const(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
 ; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[IS_POSITIVE]], i32 [[SUB]], i32 [[X:%.*]]
 ; CHECK-NEXT:    [[SEL_COND:%.*]] = icmp sgt i32 [[SEL]], 0
-; CHECK-NEXT:    br i1 [[SEL_COND]], label [[BACKEDGE]], label [[IF_FALSE:%.*]]
+; CHECK-NEXT:    br i1 [[SEL_COND]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ]
-; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
+; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
+; CHECK-NEXT:    br label [[DONE:%.*]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:                                             ; preds = %backedge, %entry