[JumpThreading] Split select that has constant conditions coming from the PHI node

[haicheng]

Summary

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 and this later enables threading over bb.

The motivation example is as follows

class H
{
public:

int a;              
int b;  
int c;

};

inline int operator < (H& A, H& B)
{

return (A.a < B.a) ? 1 :
       (A.a > B.a) ? 0 :
       (A.b < B.b) ? 1 :
       (A.b > B.b) ? 0 :
        A.c < B.c;

}

int s(H *h, int j)
{

if (h[j] < h[j+1])  
    j+=2;

return j;

}

The generated assembly in AArch64 is like below. X86 assembly has similar problem.

If(h0.a < h1.a) goto bb0
if (h0.a > h1.a) goto bb1
If(h0.b < h1.b) goto bb2
if (h0.b > h1.b) goto bb3
flag = (h0.c < h1.c)
goto if_end
bb0: Flag = 1; Goto if_end
bb1: Flag = 0; Goto if_end
bb2: Flag = 1; Goto if_end
bb3: Flag = 0; Goto if_end
if_end: j = select flag, j+2, j

The trivial basic blocks bb0 – bb3 can cause performance penalty if the comparison (h[j] < h[j+1]) is in a hot loop. The IR code of if_end is like this

%cond = phi i1 [ false, … ], [ true, … ], [ false, … ], [ true, … ], [%flag, …]
%add = add i32 %j, 2
%j.add = select i1 %cond.i, i32 %j, i32 %add

Every bool constant in the phi becomes a trivial basic block in the assembly. select is generated by SpeculativelyExecuteBB() of simplifyCFG before function inlining and prevents jump-threading to further optimize the CFG.

[gberry]

I'm still looking over this but I had one question so far: would it make sense to unfold the select when the phi has any constant operands instead of all but one being constant?

[haicheng]

In D15508#310491, @gberry wrote:

I'm still looking over this but I had one question so far: would it make sense to unfold the select when the phi has any constant operands instead of all but one being constant?

My current logic is all but at most one being constant. It is the same as my motivation case, maybe it is too conservative. But I am not sure which is more efficient on different targets, select or branch structure, when the phi has more than one nonconstant.

[gberry]

I think it would make sense to do this unfolding if there is even one constant phi argument. This seems very similar to the code in SimplifyCFG.cpp:FoldCondBranchOnPHI, and that is the approach taken there.

One other possible approach to fixing this: the code that forms the select to begin with (SimplifyCFG.cpp:SpeculativelyExecuteBB), is trying to be very conservative with the amount of selects it generates. Perhaps we could make it more conservative by not doing the select conversion if the select condition is fed by a (non-intrinsic?) call? That seems to me to be in the spirit of what it is trying to achieve since presumably there won't be any instcombine-like optimizations exposed by doing the select conversion in this case. It would probably also be a simpler change.

[haicheng]

Now I split the select if the associated phi has at least one constant.

I am looking at SpeculativelyExecuteBB now, maybe we can do both.

[haicheng]

In D15508#311269, @haicheng wrote:

I am looking at SpeculativelyExecuteBB now, maybe we can do both.

I prevent SpeculativelyExecuteBB generating select if the select condition is call. Later, SimplifyCFG::FoldTwoEntryPHINode() generates the same select. I do same thing to SimplifyCFG::FoldTwoEntryPHINode() to not generate select in this case. But, after function inlining, SpeculativelyExecuteBB still can generate the same select because the cfg of the inlined function is not fully integrated yet.

I think it might be more general and simpler to make the changes in jumpthreading.

[gberry]

Hi Haicheng,

Your results from experimenting with preventing the select conversion in the first place sound reasonable to me. I've added a few comments below.

lib/Transforms/Scalar/JumpThreading.cpp

1895

Maybe add to this comment to indicate that you're just looking for at least one constant.

1954

I'm not sure I understand why this check is here. Are you actually duplicating any code in this transformation?

[haicheng]

I updated the comments.

[haicheng]

lib/Transforms/Scalar/JumpThreading.cpp

1954

Jumpthreading duplicates codes when it threads edges so that it checks the duplication cost before the transformation. The duplicated codes are usually optimized away afterwards.

I put the check here because I don't want to split select in a basic block that cannot be threaded. My check is actually a little conservative. I just need to check the instructions between phi and select rather than the whole basic block. Do you think it is worthwhile to change getJumpThreadDuplicationCost()?

[gberry]

lib/Transforms/Scalar/JumpThreading.cpp

1954

If you undo a select and no threading happens, won't it just get converted back into a select later? I'd be concerned about duplicating all of the logic that the threading code checks here.

[haicheng]

remove the duplication cost check

[haicheng]

Hi Geoff,

I removed the duplication cost check. Should I change anything else?

[gberry]

Haicheng,

I added a few additional comments. I think this is ready for review in the larger community after addressing them.

lib/Transforms/Scalar/JumpThreading.cpp

1903

The first part of this code (the CFG modification) could be replaced with a call to SplitBlockAndInsertIfThenElse (BasicBlockUtils.h), which also takes care of setting some additional state (e.g. debuglocs).

1939

I think you should reject vector selects here as well.

1948

Could you simplify this check to just be isa<ConstantInt>?

[junbuml]

lib/Transforms/Scalar/JumpThreading.cpp

1899

I think you need to comment why at least one constant.

1935

You can merger this if with the if right above.

1938

I think you can use PN->user_back(), instead of PN->use_begin()->getUser().

1946

Since InBB is only used in here, if (PN->getIncomingBlock(i) == BB) will be better .

1949

Looks like you can directly return here "return SI;". What if BB has multiple PHIs ? This code looks checking only the first PHI.

[haicheng]

lib/Transforms/Scalar/JumpThreading.cpp

1949

I check if any Incoming block of PHI is not BB itself so that I do not return early.

To make things simple, I unfold one select a time. If there is another phi/select pair in the BB, I will unfold the select in the next pass after the current unfolded select is jump-threaded.

[junbuml]

lib/Transforms/Scalar/JumpThreading.cpp

1949

I check if any Incoming block of PHI is not BB itself so that I do not return early.

This make sense to me.

1953

Shouldn't it be continue? instead of return? What if BB has two pairs of phi/select, and the first pair is not match with your condition, but the second is matched.

[haicheng]

Address the comments from Geoff and Jun Bum. Thank you, folks.

[mssimpso]

lib/Transforms/Scalar/JumpThreading.cpp

1898

Please reword the sentence beginning with "And expand..." as its confusing. I think you're saying that SimplifyCFG will perform the optimization you want if the select is unfolded?

1943

Adding "&& !hasConst" to the terminating condition will break the loop early if you find an incoming constant.

[junbuml]

lib/Transforms/Scalar/JumpThreading.cpp

1950–1953

I think you can return SI when hasConst is true :

if (hasConst)
  return SI;

[haicheng]

lib/Transforms/Scalar/JumpThreading.cpp

1943

I check if any Incoming block of PHI is not BB itself so that I do not break the loop early.

[haicheng]

Address Matt and Jun Bum's comments

[mcrosier]

lib/Transforms/Scalar/JumpThreading.cpp

1903

can -> will

1922

Honestly, I would get rid of this helper function and inline it into TryToUnfoldSelectInCurrBB(). It's highly unlikely this function will be reused and the current TryToUnfoldSelectInCurrBB implementation is trivially small..

1923

Please add a more verbose comment. Perhaps,

// If threading this would thread across a loop header, don't thread the edge.
// See the comments above FindLoopHeaders for justifications and caveats.

1927

Please maximize 80-column comments (i.e., only wrap the line after 80 chars).

Perhaps,

// Look for a Phi/Select pair in the same basic block.  The Phi feeds the
// condition of the Select and at least one the incoming values is a constant.

1949

Can't you remove the 'HasConst' bool entirely by returning SI here? This will also cause the loop to early exit.

[haicheng]

lib/Transforms/Scalar/JumpThreading.cpp

1949

I also check if any Incoming block of PHI is not BB itself so that I do not exit loop early here.

[mcrosier]

lib/Transforms/Scalar/JumpThreading.cpp

1949

Never mind, just ignore this comment. (Actually, I thought I deleted the comment before I submitted the review.)

[haicheng]

Address Chad's comments.

[mcrosier]

Adding Chandler and Phillip as they might have some general comments.

[mcrosier]

LGTM. Overall, I'm happy with this patch. We saw a number of non-trivial improvements on external tests with no slowdowns. The differences in the inline assembly across Spec and the test-suite didn't raise any concerns. Thanks for working on this, Haicheng.

[haicheng]

Committed in r257198.

lib/Transforms/Scalar/JumpThreading.cpp

bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
                                 Instruction *CxtI = nullptr);
 
     bool ProcessBranchOnPHI(PHINode *PN);
     bool ProcessBranchOnXOR(BinaryOperator *BO);
     bool ProcessImpliedCondition(BasicBlock *BB);
 
     bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
     bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
+    bool TryToUnfoldSelectInCurrBB(BasicBlock *BB);
+    SelectInst *ShouldUnfoldSelect(BasicBlock *BB);
 
   private:
     BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
                                 const char *Suffix);
     void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
                                       BasicBlock *NewBB, BasicBlock *SuccBB);
   };
 }
if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&
 
       LVI->eraseBlock(SinglePred);
       MergeBasicBlockIntoOnlyPred(BB);
 
       return true;
     }
   }
 
+  if (TryToUnfoldSelectInCurrBB(BB))
+    return true;
+
   // What kind of constant we're looking for.
   ConstantPreference Preference = WantInteger;
 
   // Look to see if the terminator is a conditional branch, switch or indirect
   // branch, if not we can't thread it.
   Value *Condition;
   Instruction *Terminator = BB->getTerminator();
   if (BranchInst *BI = dyn_cast<BranchInst>(Terminator)) {
if ((LHSFolds != LazyValueInfo::Unknown ||
            PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
         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 and this later enables
+/// threading over bb.  Unfold select if the associated PHI has at least one
+/// constant.
+bool JumpThreading::TryToUnfoldSelectInCurrBB(BasicBlock *BB) {
+  if (SelectInst *SI = ShouldUnfoldSelect(BB)) {
+    BasicBlock *BottomBB = SplitBlock(BB, SI);
+    BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold",
+                                           BB->getParent(), BottomBB);
+    BB->getTerminator()->eraseFromParent();
+    BranchInst::Create(BottomBB, NewBB, SI->getCondition(), BB);
+    BranchInst::Create(BottomBB, NewBB);
+    PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);
+    NewPN->addIncoming(SI->getTrueValue(), BB);
+    NewPN->addIncoming(SI->getFalseValue(), NewBB);
+    SI->replaceAllUsesWith(NewPN);
+    SI->eraseFromParent();
+    return true;
+  }
+
+  return false;
+}
+
+/// ShouldUnfoldSelect - find select that can be unfolded by
+/// TryToUnfoldSelectInCurrBB
+SelectInst *JumpThreading::ShouldUnfoldSelect(BasicBlock *BB) {
+  // Only searches BB that can be threaded
+  if (LoopHeaders.count(BB))
+    return nullptr;
+
+  // Look for the Phi/Select pair in the same basic block.
+  // PHI is the condition of the Select.
+  // The incoming values of phi has at least one constant.
+  for (BasicBlock::iterator BI = BB->begin();
+       PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
+    unsigned NumPHIValues = PN->getNumIncomingValues();
+    if (NumPHIValues == 0)
+      continue;
+    if (!PN->hasOneUse())
+      continue;
+
+    SelectInst *SI = dyn_cast<SelectInst>(PN->use_begin()->getUser());
+    if (!SI || SI->getParent() != BB || SI->getCondition() != PN)
+      continue;
+
+    bool hasConst = false;
+    for (unsigned i = 0; i != NumPHIValues; ++i) {
+      Value *InVal = PN->getIncomingValue(i);
+      BasicBlock *InBB = PN->getIncomingBlock(i);
+      if (InBB == BB)
+        return nullptr;
+      if (isa<Constant>(InVal) && !isa<ConstantExpr>(InVal))
+        hasConst = true;
+    }
+
+    if (!hasConst)
+      return nullptr;
+
+    return SI;
+  }
+
+  return nullptr;
+}

test/Transforms/JumpThreading/select.ll

if.end:                                           ; preds = %if.then, %cond.end4
   ret void
 
 ; CHECK-LABEL: @unfold2
 ; CHECK: br i1 %cmp, label %if.end, label %cond.false
 ; CHECK: br i1 %cmp1, label %if.then, label %cond.end4
 ; CHECK: br i1 %cmp6, label %if.then, label %if.end
 ; CHECK: br label %if.end
 }
+
+
+define i32 @unfold3(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
+  %phitmp = icmp sge i32 %y, %z
+  br label %.exit
+
+.exit:                                  ; preds = %entry, %cond.false.i, %cond.false.6.i, %cond.false.10.i, %cond.false.15.i
+  %cond23.i = phi i1 [ false, %entry ], [ true, %cond.false.i ], [ false, %cond.false.6.i ], [ %phitmp, %cond.false.15.i ], [ true, %cond.false.10.i ]
+  %j.add3 = select i1 %cond23.i, i32 %j, i32 %add3
+  ret i32 %j.add3
+
+; CHECK-LABEL: @unfold3
+; CHECK: br i1 %cmp.i, label %select.unfold, label %cond.false.i
+; CHECK: br i1 %cmp4.i, label %.exit.split, label %cond.false.6.i
+; CHECK: br i1 %cmp8.i, label %select.unfold, label %cond.false.10.i
+; CHECK: br i1 %cmp13.i, label %.exit.split, label %.exit
+; CHECK: br i1 %phitmp, label %.exit.split, label %select.unfold
+; CHECK: br label %.exit.split
+}