[ValueTracking] Improve isImpliedCondition for conditions with matching LHS operands and Immediate RHS operands.

[mcrosier]

Summary

This patch improves SimplifyCFG to catch things like:

if (a > 5) {
  if (a > 4) <- known to be true; remove branch
    alive();
}

and

if (a > 5) {
  if (a < 4) <- known to be false; remove branch and call
    dead();
}

This is very similar to (and has a dependency on) http://reviews.llvm.org/D18905.

Please take a look,
Chad

[haicheng]

Hi Chad,

I think LazyValueInfo can figure out the branch direction in your test cases and then JumpThreading can optimize the CFG.

The related JumpThreading code is

JumpThreading.cpp

bool JumpThreading::ProcessBlock(BasicBlock *BB)

if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst)) {
  // If we're branching on a conditional, LVI might be able to determine
  // it's value at the branch instruction.  We only handle comparisons
  // against a constant at this time.
  // TODO: This should be extended to handle switches as well.
  BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
  Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1));
  if (CondBr && CondConst && CondBr->isConditional()) {
    LazyValueInfo::Tristate Ret =
      LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
                          CondConst, CondBr);
    if (Ret != LazyValueInfo::Unknown) {
      unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
      unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;
      CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true);
      BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
      CondBr->eraseFromParent();
      if (CondCmp->use_empty())
        CondCmp->eraseFromParent();
      else if (CondCmp->getParent() == BB) {
        // If the fact we just learned is true for all uses of the
        // condition, replace it with a constant value
        auto *CI = Ret == LazyValueInfo::True ?
          ConstantInt::getTrue(CondCmp->getType()) :
          ConstantInt::getFalse(CondCmp->getType());
        CondCmp->replaceAllUsesWith(CI);
        CondCmp->eraseFromParent();
      }
      return true;
    }
  }

  if (CondBr && CondConst && TryToUnfoldSelect(CondCmp, BB))
    return true;
}

Best,

Haicheng

[mcrosier]

In D19073#400372, @haicheng wrote:

I think LazyValueInfo can figure out the branch direction in your test cases and then JumpThreading can optimize the CFG.

Correct! Regardless, enabling this type of optimization in SimplifyCFG is worth while because SimplifyCFG is called much more frequently then Jump Threading. This has the potential to expose more opportunities later in the pipeline. It can also remove unreachable code earlier in the pipeline, which can save some compile time because we no longer analyze unreachable code. Once D18905 I was hoping to make a change to make SimplifyCFG that would catch a lot more cases.

The unfortunate part is that I don't think I can easily reuse the logic in LVI here.

[reames]

lib/Analysis/ValueTracking.cpp

3791

Comments to explain what this function does?

3796

Shift this check into caller and pass in ConstantInt arguments as appropriate.

3808

A more general framing of a lot of this logic would be to use ConstantFoldICmp. This wouldn't require the code duplication and would be more general.

[mcrosier]

lib/Analysis/ValueTracking.cpp

3808

I'll all for no reinventing the wheel, but I'm not sure what code you're referring to. Can you please point me in the right direction, Philip?

[mcrosier]

@bmakam's ongoing work will supersede this patch.

lib/Analysis/ValueTracking.cpp

static bool isImpliedCondOperands(CmpInst::Predicate Pred, Value *ALHS,
   case CmpInst::ICMP_ULE:
     return isTruePredicate(CmpInst::ICMP_ULE, BLHS, ALHS, DL, Depth, AC, CxtI,
                            DT) &&
            isTruePredicate(CmpInst::ICMP_ULE, ARHS, BRHS, DL, Depth, AC, CxtI,
                            DT);
   }
 }
 
+static bool isImpliedCondImmOperands(CmpInst::Predicate APred, Value *ALHS,
+                                     Value *ARHS, CmpInst::Predicate BPred,
+                                     Value *BLHS, Value *BRHS,
+                                     bool &ImpliedTrue) {
+  // The below logic assumes the ALHS == BLHS and both RHS are constants.
+  if (ALHS != BLHS || !isa<ConstantInt>(ARHS) || !isa<ConstantInt>(BRHS))
+    return false;
+
+  // Both the LHSs and RHSs (i.e., constant operands) match.
+  if (ARHS == BRHS) {
+    // If the constant operands and predicates match the first condition imples
+    // the second condition is true.
+    if (APred == BPred) {
+      ImpliedTrue = true;
+      return true;
+    }
+
+    // If the constant operands match and the predicates are swapped we can
+    // infer the second condition is false because if, for example, A > 5 is
+    // true, then A < 5 must be false.
+    if (APred == ICmpInst::getSwappedPredicate(BPred)) {
+      switch (APred) {
+      default:
+        break;
+      case CmpInst::ICMP_UGT:
+      case CmpInst::ICMP_ULT:
+      case CmpInst::ICMP_SGT:
+      case CmpInst::ICMP_SLT:
+        ImpliedTrue = false;
+        return true;
+      }
+    }
+  }
+
+  if (APred == BPred) {
+    switch (APred) {
+    default:
+      break;
+    case CmpInst::ICMP_EQ:
+      // A == C implies A == C' is false.
+      if (ARHS != BRHS) {
+        ImpliedTrue = false;
+        return true;
+      }
+      break;
+    case CmpInst::ICMP_SGT:
+    case CmpInst::ICMP_SGE:
+      // A > C implies A > C' is true if C >= C'.
+      // A >= C implies A >= C' is true if C >= C'.
+      if (cast<ConstantInt>(ARHS)->getSExtValue() >=
+          cast<ConstantInt>(BRHS)->getSExtValue()) {
+        ImpliedTrue = true;
+        return true;
+      }
+      break;
+    case CmpInst::ICMP_UGT:
+    case CmpInst::ICMP_UGE:
+      // A > C implies A > C' is true if C >= C'.
+      // A >= C implies A >= C' is true if C >= C'.
+      if (cast<ConstantInt>(ARHS)->getZExtValue() >=
+          cast<ConstantInt>(BRHS)->getZExtValue()) {
+        ImpliedTrue = true;
+        return true;
+      }
+      break;
+    case CmpInst::ICMP_SLT:
+    case CmpInst::ICMP_SLE:
+      // A < C implies A < C' is true if C <= C'.
+      // A <= C implies A <= C' is true if C <= C'.
+      if (cast<ConstantInt>(ARHS)->getSExtValue() <=
+          cast<ConstantInt>(BRHS)->getSExtValue()) {
+        ImpliedTrue = true;
+        return true;
+      }
+      break;
+    case CmpInst::ICMP_ULT:
+    case CmpInst::ICMP_ULE:
+      // A < C implies A < C' is true if C < C'.
+      // A <= C implies A <= C' is true if C <= C'.
+      if (cast<ConstantInt>(ARHS)->getZExtValue() <=
+          cast<ConstantInt>(BRHS)->getZExtValue()) {
+        ImpliedTrue = true;
+        return true;
+      }
+      break;
+    }
+  }
+  // FIXME: Handle cases where APred != BPred.
+  return false;
+}
+
 /// Return true if "icmp2 Pred op1 op2" is known to be implied by "icmp1 Pred
 /// op1 op2".  The implication may be either true or false depending on the
 /// return value of ImpliedTrue.
 static bool isImpliedCondMatchingOperands(CmpInst::Predicate APred, Value *ALHS,
                                           Value *ARHS, CmpInst::Predicate BPred,
                                           Value *BLHS, Value *BRHS,
                                           bool &ImpliedTrue) {
   // The operands of the two compares must match.
bool llvm::isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue,
   ICmpInst::Predicate APred, BPred;
   Value *ALHS, *ARHS;
   Value *BLHS, *BRHS;
 
   if (!match(LHS, m_ICmp(APred, m_Value(ALHS), m_Value(ARHS))) ||
       !match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS))))
     return false;
 
+  if (isImpliedCondImmOperands(APred, ALHS, ARHS, BPred, BLHS, BRHS,
+                               ImpliedTrue))
+    return true;
+
   if (isImpliedCondMatchingOperands(APred, ALHS, ARHS, BPred, BLHS, BRHS,
                                     ImpliedTrue))
     return true;
 
   if (APred == BPred) {
     ImpliedTrue = true;
     return isImpliedCondOperands(APred, ALHS, ARHS, BLHS, BRHS, DL, Depth, AC,
                                  CxtI, DT);
   }
 
   return false;
 }

test/Transforms/SimplifyCFG/implied-cond-imm.ll

+; RUN: opt %s -S -simplifycfg | FileCheck %s
+
+; A == C implies A == C is true.
+; CHECK-LABEL: @test_eq5_eq5
+; CHECK: %cmp = icmp eq i32 %a, 5
+; CHECK-NOT: %cmp1 = icmp eq i32 %a, 5
+; CHECK: ret void
+define void @test_eq5_eq5(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp eq i32 %a, 5
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A == C implies A == C' is false.
+; CHECK-LABEL: @test_eq5_eq6
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_eq5_eq6(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp eq i32 %a, 6
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A != C implies A != C is true.
+; CHECK-LABEL: @test_ne5_ne5
+; CHECK: %cmp = icmp ne i32 %a, 5
+; CHECK-NOT: %cmp1 = icmp ne i32 %a, 5
+; CHECK: ret void
+define void @test_ne5_ne5(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ne i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ne i32 %a, 5
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A > C implies A < C is false.
+; CHECK-LABEL: @test_ugt5_ult5
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_ugt5_ult5(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ult i32 %a, 5
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A < C implies A > C is false.
+; CHECK-LABEL: @test_slt5_sgt5
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_slt5_sgt5(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp slt i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sgt i32 %a, 5
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A > C implies A > C' is true if C >= C'.
+; CHECK-LABEL: @test_sgt5_sgt4
+; CHECK-NOT: %cmp1 = icmp sgt i32 %a, 4
+; CHECK: ret void
+define void @test_sgt5_sgt4(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp sgt i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sgt i32 %a, 4
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A >= C implies A >= C' is true if C >= C'.
+; CHECK-LABEL: @test_sge5_sge4
+; CHECK-NOT: %cmp1 = icmp sge i32 %a, 4
+; CHECK: ret void
+define void @test_sge5_sge4(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp sge i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sge i32 %a, 4
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A < C implies A < C' is true if C <= C'.
+; CHECK-LABEL: @test_slt5_slt6
+; CHECK-NOT: %cmp1 = icmp slt i32 %a, 6
+; CHECK: ret void
+define void @test_slt5_slt6(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp slt i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp slt i32 %a, 6
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A <= C implies A <= C' is true if C <= C'.
+; CHECK-LABEL: @test_sle5_sle6
+; CHECK-NOT: %cmp1 = icmp sle i32 %a, 6
+; CHECK: ret void
+define void @test_sle5_sle6(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp sle i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sle i32 %a, 6
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A > C implies A > C' is true if C >= C'.
+; CHECK-LABEL: @test_ugt5_ugt4
+; CHECK-NOT: %cmp1 = icmp ugt i32 %a, 4
+; CHECK: ret void
+define void @test_ugt5_ugt4(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ugt i32 %a, 4
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A >= C implies A >= C' is true if C >= C'.
+; CHECK-LABEL: @test_uge5_uge4
+; CHECK-NOT: %cmp1 = icmp uge i32 %a, 4
+; CHECK: ret void
+define void @test_uge5_uge4(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp uge i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp uge i32 %a, 4
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A < C implies A < C' is true if C <= C'.
+; CHECK-LABEL: @test_ult5_ult6
+; CHECK-NOT: %cmp1 = icmp ult i32 %a, 6
+; CHECK: ret void
+define void @test_ult5_ult6(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ult i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ult i32 %a, 6
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A <= C implies A <= C' is true if C <= C'.
+; CHECK-LABEL: @test_ule5_ule6
+; CHECK-NOT: %cmp1 = icmp ule i32 %a, 6
+; CHECK: ret void
+define void @test_ule5_ule6(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ule i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ule i32 %a, 6
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+declare void @dead()
+declare void @alive()