[JumpThreading] See through Cast Instructions

[haicheng]

Summary

This patch helps JumpThreading capture more optimization opportunities. No significant performance change in SpecINT.

[haicheng]

Fix a typo.

[gberry]

It is not clear to me from looking at the added test case what new optimization is being added. I would expect to see some CHECKs of new folded constants if I understand the change correctly.

test/Transforms/JumpThreading/basic.ll

495

These 3 lines are indented funny (tabs?)

[haicheng]

In D16809#344366, @gberry wrote:

It is not clear to me from looking at the added test case what new optimization is being added. I would expect to see some CHECKs of new folded constants if I understand the change correctly.

This patch allows the Entry block threads over the merge block. See the first CHECK-NEXT

[haicheng]

Fix the format of the test case. Thank you, Geoff.

[gberry]

test/Transforms/JumpThreading/basic.ll

493

It seems like this change to JumpThreading would not be needed if the Merge block code had been simplified to the following:

Merge:
  %B = phi i32 [1, %Entry], [%v1, %F1]
  %M = icmp eq i32 %B, 0 
  br i1 %M, label %T2, label %F2

Are we missing this simplification, or is there something more complex going on in the code this was extracted from that prevents it from happening?

[haicheng]

test/Transforms/JumpThreading/basic.ll

493

The simplification is missing. InstCombine can optimize it, but it is called after jumpthreading.

[bmakam]

test/Transforms/JumpThreading/basic.ll

493

InstSimplify can also optimize it. Have you considered just using the simplified value if the instruction can be simplified? This frequently happens due to phi translation and I think there is an instance where we use this in DuplicateCondBranchOnPHIIntoPred

[haicheng]

Thank you, Balaram. Is this the update that you suggest?

[majnemer]

lib/Transforms/Scalar/JumpThreading.cpp

413

Please use auto * for the left hand side of the assignment.

[bmakam]

LGTM once you've addressed the comments.

lib/Transforms/Scalar/JumpThreading.cpp

415

You might need to RAUW NewV,
NewV->replaceAllUsesWith(V);
V->eraseFromParent();

[bmakam]

lib/Transforms/Scalar/JumpThreading.cpp

415

I meant V->replaceAllUsesWith(NewV)

[haicheng]

Address David and Balaram's comments. Thank you.

[mcrosier]

Does this patch include the test case for r260110?

[haicheng]

In D16809#349908, @mcrosier wrote:

Does this patch include the test case for r260110?

test17 is the test case for r260110.

[mcrosier]

Seems reasonable to me, but I'll let @bmakam's or someone else more familiar with the patch give the final approval.

[gberry]

lib/Transforms/Scalar/JumpThreading.cpp

414

It seems like this block deserves a single-line comment explaining why it is being done.

test/Transforms/JumpThreading/basic.ll

514

Can you give some indication of what kind of crash/assert you are testing for here?

[haicheng]

Address Geoff's comments.

[haicheng]

Kindly ping.

[haicheng]

Kindly ping

[bmakam]

Sorry, did not realize this was waiting for my approval. LGTM.

[haicheng]

Committed in r261981.

lib/Transforms/Scalar/JumpThreading.cpp

public:
     bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock*> &PredBBs,
                     BasicBlock *SuccBB);
     bool DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB,
                                   const SmallVectorImpl<BasicBlock *> &PredBBs);
 
     bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
                                          PredValueInfo &Result,
                                          ConstantPreference Preference,
+                                         bool &Changed,
                                          Instruction *CxtI = nullptr);
     bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
                                 ConstantPreference Preference,
                                 Instruction *CxtI = nullptr);
 
     bool ProcessBranchOnPHI(PHINode *PN);
     bool ProcessBranchOnXOR(BinaryOperator *BO);
     bool ProcessImpliedCondition(BasicBlock *BB);

 
 /// ComputeValueKnownInPredecessors - Given a basic block BB and a value V, see
 /// if we can infer that the value is a known ConstantInt/BlockAddress or undef
 /// in any of our predecessors.  If so, return the known list of value and pred
 /// BB in the result vector.
 ///
 /// This returns true if there were any known values.
 ///
-bool JumpThreading::
-ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
-                                ConstantPreference Preference,
-                                Instruction *CxtI) {
+bool JumpThreading::ComputeValueKnownInPredecessors(
+    Value *V, BasicBlock *BB, PredValueInfo &Result,
+    ConstantPreference Preference, bool &Changed, Instruction *CxtI) {
   // This method walks up use-def chains recursively.  Because of this, we could
   // get into an infinite loop going around loops in the use-def chain.  To
   // prevent this, keep track of what (value, block) pairs we've already visited
   // and terminate the search if we loop back to them
   if (!RecursionSet.insert(std::make_pair(V, BB)).second)
     return false;
 
   // An RAII help to remove this pair from the recursion set once the recursion
   // stack pops back out again.
   RecursionSetRemover remover(RecursionSet, std::make_pair(V, BB));
 
+  // Simplify the instruction before inferring the value. 
+  Instruction *I = dyn_cast<Instruction>(V);
+  if (I && !isa<PHINode>(I))
+    if (auto *NewV = SimplifyInstruction(I, BB->getModule()->getDataLayout())) {
+      I->replaceAllUsesWith(NewV);
+      I->eraseFromParent();
+      V = NewV;
+      Changed = true;
+    }
+
   // If V is a constant, then it is known in all predecessors.
   if (Constant *KC = getKnownConstant(V, Preference)) {
     for (BasicBlock *Pred : predecessors(BB))
       Result.push_back(std::make_pair(KC, Pred));
 
     return !Result.empty();
   }
 
   // If V is a non-instruction value, or an instruction in a different block,
   // then it can't be derived from a PHI.
-  Instruction *I = dyn_cast<Instruction>(V);
+  I = dyn_cast<Instruction>(V);
   if (!I || I->getParent() != BB) {
 
     // Okay, if this is a live-in value, see if it has a known value at the end
     // of any of our predecessors.
     //
     // FIXME: This should be an edge property, not a block end property.
     /// TODO: Per PR2563, we could infer value range information about a
     /// predecessor based on its terminator.
bool JumpThreading::ComputeValueKnownInPredecessors(
   // Handle some boolean conditions.
   if (I->getType()->getPrimitiveSizeInBits() == 1) {
     assert(Preference == WantInteger && "One-bit non-integer type?");
     // X | true -> true
     // X & false -> false
     if (I->getOpcode() == Instruction::Or ||
         I->getOpcode() == Instruction::And) {
       ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals,
-                                      WantInteger, CxtI);
+                                      WantInteger, Changed, CxtI);
       ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals,
-                                      WantInteger, CxtI);
+                                      WantInteger, Changed, CxtI);
 
       if (LHSVals.empty() && RHSVals.empty())
         return false;
 
       ConstantInt *InterestingVal;
       if (I->getOpcode() == Instruction::Or)
         InterestingVal = ConstantInt::getTrue(I->getContext());
       else
if (I->getOpcode() == Instruction::Or ||
 
       return !Result.empty();
     }
 
     // Handle the NOT form of XOR.
     if (I->getOpcode() == Instruction::Xor &&
         isa<ConstantInt>(I->getOperand(1)) &&
         cast<ConstantInt>(I->getOperand(1))->isOne()) {
-      ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result,
-                                      WantInteger, CxtI);
+      ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result, WantInteger,
+                                      Changed, CxtI);
       if (Result.empty())
         return false;
 
       // Invert the known values.
       for (auto &R : Result)
         R.first = ConstantExpr::getNot(R.first);
 
       return true;
     }
 
   // Try to simplify some other binary operator values.
   } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
     assert(Preference != WantBlockAddress
             && "A binary operator creating a block address?");
     if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
       PredValueInfoTy LHSVals;
       ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals,
-                                      WantInteger, CxtI);
+                                      WantInteger, Changed, CxtI);
 
       // Try to use constant folding to simplify the binary operator.
       for (const auto &LHSVal : LHSVals) {
         Constant *V = LHSVal.first;
         Constant *Folded = ConstantExpr::get(BO->getOpcode(), V, CI);
 
         if (Constant *KC = getKnownConstant(Folded, WantInteger))
           Result.push_back(std::make_pair(KC, LHSVal.second));
if (isa<Constant>(Cmp->getOperand(1)) && Cmp->getType()->isIntegerTy()) {
         return !Result.empty();
       }
 
       // Try to find a constant value for the LHS of a comparison,
       // and evaluate it statically if we can.
       if (Constant *CmpConst = dyn_cast<Constant>(Cmp->getOperand(1))) {
         PredValueInfoTy LHSVals;
         ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals,
-                                        WantInteger, CxtI);
+                                        WantInteger, Changed, CxtI);
 
         for (const auto &LHSVal : LHSVals) {
           Constant *V = LHSVal.first;
           Constant *Folded = ConstantExpr::getCompare(Cmp->getPredicate(),
                                                       V, CmpConst);
           if (Constant *KC = getKnownConstant(Folded, WantInteger))
             Result.push_back(std::make_pair(KC, LHSVal.second));
         }
 
         return !Result.empty();
       }
     }
   }
 
   if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
     // Handle select instructions where at least one operand is a known constant
     // and we can figure out the condition value for any predecessor block.
     Constant *TrueVal = getKnownConstant(SI->getTrueValue(), Preference);
     Constant *FalseVal = getKnownConstant(SI->getFalseValue(), Preference);
     PredValueInfoTy Conds;
     if ((TrueVal || FalseVal) &&
         ComputeValueKnownInPredecessors(SI->getCondition(), BB, Conds,
-                                        WantInteger, CxtI)) {
+                                        WantInteger, Changed, CxtI)) {
       for (auto &C : Conds) {
         Constant *Cond = C.first;
 
         // Figure out what value to use for the condition.
         bool KnownCond;
         if (ConstantInt *CI = dyn_cast<ConstantInt>(Cond)) {
           // A known boolean.
           KnownCond = CI->isOne();
bool JumpThreading::ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
                                            ConstantPreference Preference,
                                            Instruction *CxtI) {
   // If threading this would thread across a loop header, don't even try to
   // thread the edge.
   if (LoopHeaders.count(BB))
     return false;
 
   PredValueInfoTy PredValues;
-  if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference, CxtI))
-    return false;
+  bool Changed = false;
+  if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference,
+                                       Changed, CxtI))
+    return Changed;
 
   assert(!PredValues.empty() &&
          "ComputeValueKnownInPredecessors returned true with no values");
 
   DEBUG(dbgs() << "IN BB: " << *BB;
         for (const auto &PredValue : PredValues) {
           dbgs() << "  BB '" << BB->getName() << "': FOUND condition = "
             << *PredValue.first
for (const auto &PredValue : PredValues) {
     else if (OnlyDest != DestBB)
       OnlyDest = MultipleDestSentinel;
 
     PredToDestList.push_back(std::make_pair(Pred, DestBB));
   }
 
   // If all edges were unthreadable, we fail.
   if (PredToDestList.empty())
-    return false;
+    return Changed;
 
   // Determine which is the most common successor.  If we have many inputs and
   // this block is a switch, we want to start by threading the batch that goes
   // to the most popular destination first.  If we only know about one
   // threadable destination (the common case) we can avoid this.
   BasicBlock *MostPopularDest = OnlyDest;
 
   if (MostPopularDest == MultipleDestSentinel)
bool JumpThreading::ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
 
   // If the threadable edges are branching on an undefined value, we get to pick
   // the destination that these predecessors should get to.
   if (!MostPopularDest)
     MostPopularDest = BB->getTerminator()->
                             getSuccessor(GetBestDestForJumpOnUndef(BB));
 
   // Ok, try to thread it!
-  return ThreadEdge(BB, PredsToFactor, MostPopularDest);
+  Changed |= ThreadEdge(BB, PredsToFactor, MostPopularDest);
+  return Changed;
 }
 
 /// ProcessBranchOnPHI - We have an otherwise unthreadable conditional branch on
 /// a PHI node in the current block.  See if there are any simplifications we
 /// can do based on inputs to the phi node.
 ///
 bool JumpThreading::ProcessBranchOnPHI(PHINode *PN) {
   BasicBlock *BB = PN->getParent();
bool JumpThreading::ProcessBranchOnXOR(BinaryOperator *BO) {
   //
   // Into:
   //  BB':
   //    %Y = icmp ne i32 %A, %B
   //    br i1 %Y, ...
 
   PredValueInfoTy XorOpValues;
   bool isLHS = true;
+  bool Changed = false;
   if (!ComputeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues,
-                                       WantInteger, BO)) {
+                                       WantInteger, Changed, BO)) {
     assert(XorOpValues.empty());
     if (!ComputeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues,
-                                         WantInteger, BO))
-      return false;
+                                         WantInteger, Changed, BO))
+      return Changed;
     isLHS = false;
   }
 
   assert(!XorOpValues.empty() &&
          "ComputeValueKnownInPredecessors returned true with no values");
 
   // Scan the information to see which is most popular: true or false.  The
   // predecessors can be of the set true, false, or undef.
if (!SplitVal) {
       // If all preds provide 1, set the computed value to 1.
       BO->setOperand(!isLHS, SplitVal);
     }
 
     return true;
   }
 
   // Try to duplicate BB into PredBB.
-  return DuplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto);
+  Changed |= DuplicateCondBranchOnPHIIntoPred(BB, BlocksToFoldInto);
+  return Changed;
 }
 
 
 /// AddPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new
 /// predecessor to the PHIBB block.  If it has PHI nodes, add entries for
 /// NewPred using the entries from OldPred (suitably mapped).
 static void AddPHINodeEntriesForMappedBlock(BasicBlock *PHIBB,
                                             BasicBlock *OldPred,

test/Transforms/JumpThreading/basic.ll

 ; CHECK-NOT: ret i32 2
   ret i32 2
 
 exit1:
   ret i32 1
 ; CHECK: }
 }
 
+
+;;; Verify that we can handle constraint propagation through cast.
+define i32 @test16(i1 %cond) {
+Entry:
+; CHECK-LABEL: @test16(
+  br i1 %cond, label %Merge, label %F1
+
+; CHECK: Entry:
+; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
+
+F1:
+  %v1 = call i32 @f1()
+  br label %Merge
+
+Merge:
+  %B = phi i32 [1, %Entry], [%v1, %F1]
+  %M = icmp eq i32 %B, 0 
+  %M1 = zext i1 %M to i32
+  %N = icmp eq i32 %M1, 1 
+  br i1 %N, label %T2, label %F2
+
+; CHECK: Merge:
+; CHECK-NOT: phi
+; CHECK-NEXT:   %v1 = call i32 @f1()
+
+T2:
+  %Q = zext i1 %M to i32
+  ret i32 %Q
+
+F2:
+  ret i32 %B
+; CHECK: F2:
+; CHECK-NEXT: phi i32
+}
+
+;;; Just check that ComputeValueKnownInPredecessors() does not return true with
+;;; no values and triggers the assert in ProcessThreadableEdges().
+define i32 @test17() {
+entry:
+  %A = add i32 0, 1
+  %B = icmp eq i32 %A, 0
+  br i1 %B, label %T, label %F
+T:
+  %v1 = call i32 @f1()
+  ret i32 %v1
+F:
+  %v2 = call i32 @f2()
+  ret i32 %v2
+}
+
 ; In this test we check that block duplication is inhibited by the presence
 ; of a function with the 'noduplicate' attribute.
 
 declare void @g()
 declare void @j()
 declare void @k()
 
 ; CHECK-LABEL: define void @h(i32 %p) {