[JumpThreading] Unfold selects that depend on the same condition

[pbarrio]

Summary

These are good candidates for jump threading. This enables later opts
(such as InstCombine) to combine instructions from the selects with
instructions out of the selects. SimplifyCFG will fold the select
again if unfolding wasn't worth it.

Patch by James Molloy and Pablo Barrio.

[jmolloy]

Hi Pablo,

I only have a couple of trivial comments, but I'm not able to approve this patch myself as I wrote part of it and because I'm not well enough versed in this pass to give the LGTM.

Adding another set of reviewers who hopefully will be able to.

James

include/llvm/Transforms/Scalar/JumpThreading.h

139 ↗

(On Diff #74260)

functions should start with a lowercase letter.

lib/Transforms/Scalar/JumpThreading.cpp

2048 ↗

(On Diff #74260)

Variables should start with an Uppercase letter.

[pbarrio]

James, thanks for the review and also for adding the new reviewers. I will change the lower/upper case problem with the next round of comments, when I get feedback from others.

[sebpop]

Please fix the few formating issues.
The patch looks good otherwise.

lib/Transforms/Scalar/JumpThreading.cpp

2030 ↗

(On Diff #74260)

Please run clang-format on your patch.

2033 ↗

(On Diff #74260)

Please add a continue statement here: there is nothing else executed in the loop.
This will make it easier to read the rest of the loop body.

2038 ↗

(On Diff #74260)

Let's move this comment close to the loop that looks for selects using the same bool... down...

2039 ↗

(On Diff #74260)

Also remove the "else" after adding the "continue" above.

You could even flip the if condition:

if (!I.getType()->isIntegerTy(1))
  continue;

making all the rest of the loop one less indentation level.

2041 ↗

(On Diff #74260)

... down here.

2047 ↗

(On Diff #74260)

No need for else after continue.

[haicheng]

The code looks good except the formatting issues.

lib/Transforms/Scalar/JumpThreading.cpp

1943–1953 ↗

(On Diff #74260)

Since you refactor the code of expanding select, maybe you want to refactor the code here, too.

[pbarrio]

Thanks all for the reviews. Could you please review the requested formatting changes and approve if appropriate?

[sebpop]

LGTM.

lib/Transforms/Scalar/JumpThreading.cpp

2017 ↗

(On Diff #75436)

Function names should start with lower case.

[thakis]

I've reverted this in r284979.

It seems to break selfhost on some bots, see e.g.
http://lab.llvm.org:8011/builders/clang-x86-windows-msvc2015/builds/21
http://lab.llvm.org:8011/builders/clang-ppc64be-linux-multistage/builds/20
http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/22

http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20161024/399484.html

[rengolin]

In D25477#577578, @thakis wrote:

It seems to break selfhost on some bots, see e.g.
http://lab.llvm.org:8011/builders/clang-x86-windows-msvc2015/builds/21
http://lab.llvm.org:8011/builders/clang-ppc64be-linux-multistage/builds/20
http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/22

Running the test-suite might be easier for you to test on the next iteration:

http://lab.llvm.org:8011/builders/clang-cmake-aarch64-quick/builds/23

It only broke 7zip.

cheers,
--renato

llvm/trunk/include/llvm/Transforms/Scalar/JumpThreading.h

 
 private:
   BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
                               const char *Suffix);
   void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
                                     BasicBlock *NewBB, BasicBlock *SuccBB);
   /// Check if the block has profile metadata for its outgoing edges.
   bool doesBlockHaveProfileData(BasicBlock *BB);
+  SelectInst *getSelectFedByPhi(PHINode *PN);
+  void expandSelect(SelectInst *SI);
 };
 
 } // end namespace llvm
 
 #endif

llvm/trunk/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
+/// GetSelectFedByPhi - 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
+/// And return the select. Unfolding it into a branch structure 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
-/// optimizations.
-bool JumpThreadingPass::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;
+/// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), return
+/// select if the associated PHI has at least one constant.
+SelectInst *JumpThreadingPass::getSelectFedByPhi(PHINode *PN) {
 
-  // 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;
+    return nullptr;
 
-    SelectInst *SI = dyn_cast<SelectInst>(PN->user_back());
-    if (!SI || SI->getParent() != BB)
-      continue;
+  BasicBlock *BB = PN->getParent();
+    return nullptr;
 
-    Value *Cond = SI->getCondition();
-    if (!Cond || Cond != PN || !Cond->getType()->isIntegerTy(1))
-      continue;
+    return nullptr;
 
-    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;
-    }
+      return nullptr;
+      return SI;
 
-    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 nullptr;
+}
+
+/// ExpandSelect - Expand a select into an if-then-else construct.
+void JumpThreadingPass::expandSelect(SelectInst *SI) {
+
+  BasicBlock *BB = SI->getParent();
+/// TryToUnfoldSelectInCurrBB - Unfold selects that could be jump-threaded were
+/// they if-then-elses. If the unfolded selects are not jump-threaded, it will
+/// be folded again in the later optimizations.
+bool JumpThreadingPass::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;
+
+  bool Changed = false;
+  for (auto &I : *BB) {
+
+    // 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.
+    PHINode *PN;
+    SelectInst *SI;
+    if ((PN = dyn_cast<PHINode>(&I)) && (SI = getSelectFedByPhi(PN))) {
+      expandSelect(SI);
+      Changed = true;
+      continue;
+    }
+
+    if (I.getType()->isIntegerTy(1)) {
+
+      SmallVector<SelectInst *, 4> Selects;
+
+      // Look for scalar booleans used in selects as conditions. If there are
+      // several selects that use the same boolean, they are candidates for jump
+      // threading and therefore we should unfold them.
+      for (Value *U : I.users())
+        if (auto *SI = dyn_cast<SelectInst>(U))
+          Selects.push_back(SI);
+      if (Selects.size() <= 1)
+        continue;
+
+      Changed = true;
+      for (auto *SI : Selects)
+        expandSelect(SI);
+    }
+  }
+
+  return Changed;
 }

llvm/trunk/test/Transforms/JumpThreading/unfold-selects-same-cond.ll

+; RUN: opt < %s -jump-threading -instcombine -simplifycfg  -S | FileCheck %s
+
+; The three selects are jump-threaded so that instcombine can optimize, and
+; simplifycfg should turn the result into a single select.
+define i32 @f(i32 %a, i32 %b) {
+; CHECK: select
+; CHECK-NOT: select
+entry:
+  %0 = and i32 %a, 1
+  %1 = and i32 %b, 1
+  %xor = xor i32 %1, %a
+  %shr32 = lshr i32 %a, 1
+  %cmp10 = icmp eq i32 %xor, 1
+  %2 = xor i32 %b, 12345
+  %b.addr.1 = select i1 %cmp10, i32 %2, i32 %b
+  %shr1633 = lshr i32 %b.addr.1, 1
+  %3 = or i32 %shr1633, 54321
+  %b.addr.2 = select i1 %cmp10, i32 %3, i32 %shr1633
+  %shr1634 = lshr i32 %b.addr.2, 2
+  %4 = or i32 %shr1634, 54320
+  %b.addr.3 = select i1 %cmp10, i32 %4, i32 %shr1634
+  ret i32 %b.addr.3
+}