[JumpThreading] Rewrite TryToUnfoldSelectInCurrBB() by using ComputeValueKnownInPredecessors()

[haicheng]

Summary

The benefit of this rewriting is splitting the select earlier or finding more select to split.

[mcrosier]

Are you actively pursing this change any longer, Haicheng?

[haicheng]

Not until GVN uses MemorySSA

[haicheng]

Abandon it since it is been here for a long time.

lib/Transforms/Scalar/JumpThreading.cpp

if ((LHSFolds != LazyValueInfo::Unknown ||
         if (Phi != CondLHS)
           Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
       return true;
     }
   }
   return false;
 }
 
-/// TryToUnfoldSelectInCurrBB - Look for PHI/Select in the same BB of the form
-/// bb:
-///   %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ...
-///   %s = select p, trueval, falseval
-///
-/// And expand the select into a branch structure. This later enables
-/// jump-threading over bb in this pass.
+/// TryToUnfoldSelectInCurrBB - Look for Select whose condition is known given a
+/// predecessor and expand the select into a branch structure. This later
+/// enables jump-threading over bb in this pass.
 ///
 /// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold
-/// select if the associated PHI has at least one constant.  If the unfolded
-/// select is not jump-threaded, it will be folded again in the later
+/// select if its condition is known for at least one predecessor.  If the
+/// unfolded select is not jump-threaded, it will be folded again in the later
 /// optimizations.
 bool JumpThreading::TryToUnfoldSelectInCurrBB(BasicBlock *BB) {
-  // If threading this would thread across a loop header, don't thread the edge.
-  // See the comments above FindLoopHeaders for justifications and caveats.
-  if (LoopHeaders.count(BB))
-    return false;
-
-  // Look for a Phi/Select pair in the same basic block.  The Phi feeds the
-  // condition of the Select and at least one of the incoming values is a
-  // constant.
-  for (BasicBlock::iterator BI = BB->begin();
-       PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
-    unsigned NumPHIValues = PN->getNumIncomingValues();
-    if (NumPHIValues == 0 || !PN->hasOneUse())
-      continue;
+  BasicBlock::iterator I = BB->getFirstNonPHI()->getIterator();
+  for (; !isa<TerminatorInst>(I); ++I) {
+    if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
 
-    SelectInst *SI = dyn_cast<SelectInst>(PN->user_back());
-    if (!SI || SI->getParent() != BB)
+      Value *Condition = SI->getCondition();
+      if (!Condition->getType()->isIntegerTy(1))
         continue;
 
-    Value *Cond = SI->getCondition();
-    if (!Cond || Cond != PN || !Cond->getType()->isIntegerTy(1))
+      PredValueInfoTy Conds;
+      if (!ComputeValueKnownInPredecessors(Condition, BB, Conds, WantInteger))
         continue;
 
-    bool HasConst = false;
-    for (unsigned i = 0; i != NumPHIValues; ++i) {
-      if (PN->getIncomingBlock(i) == BB)
-        return false;
-      if (isa<ConstantInt>(PN->getIncomingValue(i)))
-        HasConst = true;
-    }
+      assert(!Conds.empty() &&
+             "ComputeValueKnownInPredecessors returned true with no values");
 
-    if (HasConst) {
       // Expand the select.
       TerminatorInst *Term =
           SplitBlockAndInsertIfThen(SI->getCondition(), SI, false);
       PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);
       NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
       NewPN->addIncoming(SI->getFalseValue(), BB);
       SI->replaceAllUsesWith(NewPN);
       SI->eraseFromParent();
       return true;
     }
   }
-  
   return false;
 }

test/Transforms/JumpThreading/select.ll

 ; CHECK-LABEL: @unfold3
 ; CHECK: br i1 %cmp.i, label %.exit.thread2, label %cond.false.i 
 ; CHECK: br i1 %cmp4.i, label %.exit.thread, label %cond.false.6.i
 ; CHECK: br i1 %cmp8.i, label %.exit.thread2, label %cond.false.10.i
 ; CHECK: br i1 %cmp13.i, label %.exit.thread, label %.exit
 ; CHECK: br i1 %phitmp, label %.exit.thread, label %.exit.thread2
 ; CHECK: br label %.exit.thread2
 }
+
+define i32 @unfold4(i32 %u, i32 %v, i32 %w, i32 %x, i32 %y, i32 %z, i32 %j) nounwind {
+entry:
+  %add3 = add nsw i32 %j, 2
+  %cmp.i = icmp slt i32 %u, %v
+  br i1 %cmp.i, label %.exit, label %cond.false.i
+
+cond.false.i:                                     ; preds = %entry
+  %cmp4.i = icmp sgt i32 %u, %v
+  br i1 %cmp4.i, label %.exit, label %cond.false.6.i
+
+cond.false.6.i:                                   ; preds = %cond.false.i
+  %cmp8.i = icmp slt i32 %w, %x
+  br i1 %cmp8.i, label %.exit, label %cond.false.10.i
+
+cond.false.10.i:                                  ; preds = %cond.false.6.i
+  %cmp13.i = icmp sgt i32 %w, %x
+  br i1 %cmp13.i, label %.exit, label %cond.false.15.i
+
+cond.false.15.i:                                  ; preds = %cond.false.10.i
+  %cmp19.i = icmp sge i32 %y, %z
+  %conv = zext i1 %cmp19.i to i32
+  br label %.exit
+
+.exit:                                  ; preds = %entry, %cond.false.i, %cond.false.6.i, %cond.false.10.i, %cond.false.15.i
+  %cond23.i = phi i32 [ 1, %entry ], [ 0, %cond.false.i ], [ 1, %cond.false.6.i ], [ %conv, %cond.false.15.i ], [ 0, %cond.false.10.i ]
+  %lnot.i18 = icmp eq i32 %cond23.i, 0
+  %conv.i19 = zext i1 %lnot.i18 to i32
+  %tobool14 = icmp eq i32 %conv.i19, 0
+  %j.add3 = select i1 %tobool14, i32 %j, i32 %add3
+  ret i32 %j.add3
+
+; CHECK-LABEL: @unfold4
+; CHECK: br i1 %cmp.i, label %.exit.thread, label %cond.false.i 
+; CHECK: br i1 %cmp4.i, label %.exit.thread5, label %cond.false.6.i
+; CHECK: br i1 %cmp8.i, label %.exit.thread, label %cond.false.10.i
+; CHECK: br i1 %cmp13.i, label %.exit.thread5, label %.exit
+; CHECK: br i1 %tobool14, label %.exit.thread, label %.exit.thread5
+; CHECK: br label %.exit.thread5
+}