Select Elimination in InstCombine

[Gerolf]

Summary

Summary
In special cases select instructions can be eliminated by
replacing them with a cheaper bitwise operation even when the
select result is used outside its home block. The instances implemented
here are %x=icmp.eq; %y=select %x,%r, null; %z=icmp.eq|neq %y, null;
br %z,true, false ==> %x=icmp.ne; %y=icmp.eq %r,null; %z=or %x,%y; br
%z,true,false. The optimization is integrated into the instruction
combiner and performed only when all uses of the select result can
be replaced by the select operand proper. For this dominator information
is used. Integration into the combiner means that only the select-icmp is
transformed at first. Then the combiner iteratively works out the simpler
pattern. Note that the instruction combiner already handles the local pattern
when there is no use of the select result outside its home block.

[echristo]

A few nits in line, one question in line, and one more thought: Can't this replace a few of our other queries for instructions with dominator tree lookups? Is that a follow on patch or?

Thanks!

-eric

lib/Transforms/InstCombine/InstCombineCompares.cpp

2459

s/or/of

2463

Local variable naming style.

3067

Local variable naming style.

3097

Nit: Sentences begin with capital letters.

3099

Isn't this just a boolean then?

lib/Transforms/InstCombine/InstructionCombining.cpp

98

Probably don't need to have it as requires, but optional? i.e. if it doesn't exist then just don't do the transform in the way you've got?

[Gerolf]

Thanks, Eric! I think I have to rely on dominance optionally to get keep a few of the MCJIT tests running.

What specifically is on your mind wrt to other queries?

Cheers
Gerolf

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2482–2484

Why not perform a dyn_cast instead?

2487–2490

This will return true if IC is null, did is this intensional?

3077

s/int/unsigned

3094–3095

This is just llvm::ICmpInst::isEquality.

3099

I'd make this an unsigned, getSuccessor is asking which successor to take. It just so happens that we are only interested in cases where there are two successors.

[echristo]

Hi Gerolf,

One more comment in line.

As far as the dominance tree, you don't ever check to find out if you have dominance trees, you just require it. The leading question was: if it's not optional, then you can probably use it in more places in the pass. If it is optional then you're not actually checking for it before using it.

Thanks!

lib/Transforms/InstCombine/InstCombineCompares.cpp

3099

Yes. Makes sense that way. Might be better off just grabbing the correct successor rather than mucking with the integer.

[joey]

Drive-by comments.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2461

I'm wondering if this name is too general, or if the parameter types are too strict.

3079

I think you can use dyn_cast_or_null here to combine these two if statements, to reduce indentation.

3087

dyn_cast_or_null again.

[mcrosier]

test/Transforms/InstCombine/select-cmp-br.ll

2

Perhaps something like:
; Replace a 'select' with an 'or' in a 'select - cmp[eq|ne] - br' sequence when profitable.

68

CHECK-LABEL: @test3

93

newline

94

@test4

95

CHECK-LABEL: @test4

[mcrosier]

test/Transforms/InstCombine/select-cmp-br.ll

10

@test1

11

CHECK-LABEL: @test1

37

insert newline

38

@test2

39

CHECK-LABEL: @test2

65

newline

66

@test3

[chandlerc]

(most of the other reviewers are doing a great job on this patch, so I've only made a couple of specific comments... will leave the rest of the review to them)

lib/Transforms/InstCombine/InstCombineCompares.cpp

2461

Agreed. I Think the name is good, but it should be made a very generic property of an instruction.

I actually wonder whether this should be a method on DominatorTree itself.

lib/Transforms/InstCombine/InstructionCombining.cpp

98

I'm actually OK changing InstCombine so that it always requires dominator trees, but I think that should be a separate change.

I would add it as optional here, and then I would submit a follow-up patch to switch it over so we don't hold up the logic here on the debate about how often to require the analysis. Then the patch that makes it required can discuss the relevant concern by citing compile-item benchmarks showing it's not too expensive. =]

[Gerolf]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2459

Replaced by crisper comment.

2461

I generalized the signature to use instruction *.

2463

Fixed.

2482–2484

Right, thanks.

2487–2490

Excellent catch, thanks!

3067

Fixed.

3077

ok, unsigned.

3079

nice suggestion, thanks.

3087

dito

3094–3095

yes, thanks!

3097

Yop, fixed.

3099

Addressed as suggested.

lib/Transforms/InstCombine/InstructionCombining.cpp

98

We go for required. Open question is one or two commits.

test/Transforms/InstCombine/select-cmp-br.ll

2

Done.

10

done.

11

dito for this and the rest below.

[Gerolf]

Updates:

• Follow up on all your great reviews
• Note: patch still assumes that it is OK to enable DT by default
• New change in pr12338: when DT is default all arithmetic instructions in

that test get removed. This is fine. The purpose of the test is to protect
against an inifinite loop in the instruction combiner.

[majnemer]

lib/Transforms/InstCombine/InstCombine.h

249

It's unusual to capitalize all the letters in DEF and USE, it's more common to see Def and Use.

I think all arguments and the method could be const.

250

SI could be const as should the method itself.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2467–2468

Could be a little simpler with for (const Use &U : Def->uses()) {

2472–2473

You could make this a little easier to follow if you made this return false;

In fact, you could probably remove the continue; as well.

2475

This could just be return true;

2489–2491

You could make this return IC && IC->getOperand(0) == SI;

Are we interested in doing anything if the other operand to the ICmpInst is the SelectInst?

[Gerolf]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2467–2468

Done

2472–2473

Done

2475

Done

2489–2491

No, rhs is expected to be a constant.

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2489–2491

Where do we check this?

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2489–2491

Thinking about this, isChainSelectCmpBranch is very specific to this transform; I think this makes more sense as a static function instead of a member function.

[Gerolf]

Please see below.

[Gerolf]

Changes:

• a few more improvements to code readability
• isChainSelectCmpBranch() is now static
• const parameters and variables

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2468

DT is invariant of this loop, you could hoist it out of the loop (return false).

[Gerolf]

Sure. Anything else?

Cheers
Gerolf

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3078–3079

I think this reads easier as: !CI->isZero()

Speaking of which, why is it bad if the constant is zero?

[chandlerc]

I still think that we need to confirm there is not a compile time regression from requiring dom trees here...

Also, some code comments below. I think this code needs to be refactored a bit here. =/ It's already gotten pretty gnarly and this pushes it further.

Thanks for working on all of this though. I really like the result.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2458–2461

Please follow either the specific coding standards for doxygen comments or match the surrounding code. The function above has a pretty good example.

2466–2467

If all you need is the User, iterate over UI->users()?

3067

This whole large new block is pretty indicative that this needs to be refactored. I think you should extract a method for the entire transform guarded by this boolean (in a separate patch, should be super simple refactoring).

The existence of the boolean is a really clear sign that this will help -- you can use early exit rather than a boolean to guard falling through to the transform. It will reduce indentation and make everything much more readable.

[Gerolf]

Please see below.

[Gerolf]

Changes:

• added comments and increased smoothyness

[hfinkel]

lib/Transforms/InstCombine/InstCombine.h

249

80 cols.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2458

This is not quite right, the function actually asserts if the definition and the provided use are in different blocks (it does not check this condition).

2488

Can this really be called on un-inserted instructions?

2491

Or on instructions in incomplete blocks?

3091

Make this an else if?

3104

As we only actually perform the transform if I.isEquality(), can you host that part of the check up to be with the isChainSelectCmpBranch(SI) check?

lib/Transforms/InstCombine/InstructionCombining.cpp

98

Are you going to separate this into a follow-up patch, or are you planning to provide compile-time measurements to before committing this one?

[Gerolf]

lib/Transforms/InstCombine/InstCombine.h

249

ok

lib/Transforms/InstCombine/InstCombineCompares.cpp

2458

the assertion actually checks that the use + def are in the *same* block

2488

Yes, conservatively the optimization will not run.

2491

dito.

3091

Part of refactoring.

3104

Yes, thanks.

[Gerolf]

hfinkel: Are you going to separate this into a follow-up patch, or are you planning to provide compile-time measurements to before committing this one?

I guess I had said that compile-time is not impacted, but never showed any data. And then I had said many more things about compile-time measurements, our test suite and dominators, so the noise numbers should come as no surprise (all with 0.1-0.2 secs on x86):

Performance Regressions - Compile Time Δ Previous Current σ Δ (B) σ (B)
SingleSource/UnitTests/ObjC++/property-reference http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.202=2 4.37% 0.4192 0.4375 0.0003 0.00% 0.0003
SingleSource/Benchmarks/Shootout-C++/fibo http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.255=2 3.98% 0.2714 0.2822 0.0005 0.00% 0.0005
MultiSource/Applications/lemon/lemon http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.521=2 3.35% 0.5018 0.5186 0.0045 0.00% 0.0045
SingleSource/UnitTests/ObjC++/property-reference-object http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.62=2 3.05% 0.3375 0.3478 0.0002 0.00% 0.0002
MultiSource/Applications/sqlite3/sqlite3 http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.513=2 2.81% 7.1620 7.3631 0.0438 0.00% 0.0438
External/SPEC/CFP2006/444_namd/444_namd http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.163=2 2.15% 3.1007 3.1675 0.0021 0.00% 0.0021
MultiSource/Applications/oggenc/oggenc http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.537=2 1.73% 2.0891 2.1252 0.0065 0.00% 0.0065
External/SPEC/CINT2000/197_parser/197_parser http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.447=2 1.63% 1.1629 1.1819 0.0000 0.00% 0.0000
External/SPEC/CINT2000/176_gcc/176_gcc http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.333=2 1.60% 12.4641 12.6631 0.0030 0.00% 0.0030
External/SPEC/CINT95/099_go/099_go http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.528=2 1.51% 1.7386 1.7649 0.0020 0.00% 0.0020
External/SPEC/CINT2006/403_gcc/403_gcc http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.59=2 1.46% 30.0626 30.5019 0.0195 0.00% 0.0195
External/SPEC/CINT95/134_perl/134_perl http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.319=2 1.34% 2.5077 2.5413 0.0010 0.00% 0.0010
External/SPEC/CINT2006/400_perlbench/400_perlbench http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.280=2 1.31% 10.8686 11.0114 0.0005 0.00% 0.0005
External/SPEC/CINT2006/445_gobmk/445_gobmk http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.272=2 1.18% 7.7186 7.8093 0.0010 0.00% 0.0010
External/SPEC/CINT2000/253_perlbmk/253_perlbmk http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.241=2 1.11% 5.5141 5.5752 0.0047 0.00% 0.0047
External/SPEC/CINT2000/254_gap/254_gap http://ghoflehner.apple.com/perf/v4/nts/2/graph?test.99=2 1.03% 4.5858 4.6332 0.0058 0.00% 0.0058

[Gerolf]

The most notable change is a minor refactoring introducing
replacedSelectWithOperand() that replaces a select with one
of its operands when possible. Refactoring includes the follow-up on good
suggestions like Use isZero() (David), employ users() iterator (Chandler)
and hoist equality check (Hal).

[hfinkel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2478

If you mean for this to rule-out any other uses in the same block as the definition (I don't see anything else that might enforce that there is only one use in the parent block), should this be a call to properlyDominates?

[Gerolf]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2478

Very much agree. Done.

[hfinkel]

LGTM.

[Gerolf]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2478

Ups, I have to take it back. DB can be a successor block of the DI parent and it may contain a use. So dominates() must be used.

[hfinkel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2478

Alright, please make sure the function description comment is accurate and that this is noted.

[majnemer]

lib/Transforms/InstCombine/InstCombine.h

103

This change looks superfluous.

[Gerolf]

lib/Transforms/InstCombine/InstCombine.h

103

Good catch. Somehow I flipped TLI and DT. Done.
Also, the not // not required comment on DT is wrong now, so I removed it.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2478

Ok. I sharpened the comment and explicitly mention that there could a use of \p DI in \p DB.

[Gerolf]

Thanks, Hal + all co-reviewers. I never thought that landing this optimization could be that exciting! :-) Very much appreciate all your feedback!

Committed revision 218721

[Gerolf]

I need to re-open this for another round of reviews. Although the select-icmp
optmization had received pretty good reviews its commit got hit by
a self-host failure (pr21210) that exposed two issues. In addition to
the fixes there is a new function and some small refactoring.

Fixes:

f1) do not replace select by operand in the block that contains the select
f2) do not perform the optimization when a use of the select
could be reached on both paths out of the conditional block that
contains the select

Major changes:

• dominatesAllUses() fixes f1)
• replacedSelectWithOperand has a more natural interface and fixes f2)
• replaceUsesOutsideBlock() in lib/IR/Value.cpp
• test/Transforms/InstCombine/pr21210.ll

[hfinkel]

include/llvm/IR/Value.h

264

Add period after block and remove empty comment line.

The other differences from RAUW (as noted above the implementation) should also be noted here.

There is no need to name the BB argument ExceptionBB, BB is fine.

lib/IR/Value.cpp

360

We don't need to use the name ExceptionBB, or refer to this as the "exception block" in the assert below.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2566

I assume that Succ->getUniquePredecessor() is cheaper to evaluate than InstCombiner::dominatesAllUses(SI, Icmp, Succ), so I'd check that first. Also, you can drop the InstCombiner::

[Gerolf]

include/llvm/IR/Value.h

264

ok.

lib/IR/Value.cpp

360

ok.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2566

Good point. At least your assumption should be right :-)

[Gerolf]

Update with minor changes to comments etc suggested by Hal.

[hfinkel]

I think this is generally good (again). LGTM.

lib/IR/Value.cpp

357

We don't need this description here, we have a better one in the header.

lib/Transforms/InstCombine/InstCombineCompares.cpp

34

"Number of select opts" -> "Number of selects replaced by an operand"

[Gerolf]

Thanks, Hal!

Committed revision 222590.

include/llvm/IR/Value.h

public:
 
   /// \brief Change all uses of this to point to a new Value.
   ///
   /// Go through the uses list for this definition and make each use point to
   /// "V" instead of "this".  After this completes, 'this's use list is
   /// guaranteed to be empty.
   void replaceAllUsesWith(Value *V);
 
+  /// replaceUsesOutsideBlock - Go through the uses list for this definition and
+  /// make each use point to "V" instead of "this" when the use is outside the
+  /// block. 'This's use list is expected to have at least one element.
+  /// Unlike replaceAllUsesWith this function does not support basic block
+  /// values or constant users.
+  void replaceUsesOutsideBlock(Value *V, BasicBlock *BB);
+
   //----------------------------------------------------------------------
   // Methods for handling the chain of uses of this Value.
   //
   bool               use_empty() const { return UseList == nullptr; }
 
   typedef use_iterator_impl<Use>       use_iterator;
   typedef use_iterator_impl<const Use> const_use_iterator;
   use_iterator       use_begin()       { return use_iterator(UseList); }

lib/IR/Value.cpp

while (!use_empty()) {
 
     U.set(New);
   }
 
   if (BasicBlock *BB = dyn_cast<BasicBlock>(this))
     BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New));
 }
 
+// Like replaceAllUsesWith except it does not handle constants or basic blocks.
+// This routine leaves uses within BB.
+void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) {
+  assert(New && "Value::replaceUsesOutsideBlock(<null>, BB) is invalid!");
+  assert(!contains(New, this) &&
+         "this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!");
+  assert(New->getType() == getType() &&
+         "replaceUses of value with new value of different type!");
+  assert(BB && "Basic block that may contain a use of 'New' must be defined\n");
+
+  use_iterator UI = use_begin(), E = use_end();
+  for (; UI != E;) {
+    Use &U = *UI;
+    ++UI;
+    auto *Usr = dyn_cast<Instruction>(U.getUser());
+    if (Usr && Usr->getParent() == BB)
+      continue;
+    U.set(New);
+  }
+  return;
+}
+
 namespace {
 // Various metrics for how much to strip off of pointers.
 enum PointerStripKind {
   PSK_ZeroIndices,
   PSK_ZeroIndicesAndAliases,
   PSK_InBoundsConstantIndices,
   PSK_InBounds
 };

lib/Transforms/InstCombine/InstCombine.h

 //===- InstCombine.h - Main InstCombine pass definition ---------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINE_H
 #define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINE_H
 
 #include "InstCombineWorklist.h"
 #include "llvm/Analysis/AssumptionTracker.h"
 #include "llvm/Analysis/TargetFolder.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
 

 
 /// InstCombiner - The -instcombine pass.
 class LLVM_LIBRARY_VISIBILITY InstCombiner
     : public FunctionPass,
       public InstVisitor<InstCombiner, Instruction *> {
   AssumptionTracker *AT;
   const DataLayout *DL;
   TargetLibraryInfo *TLI;
-  DominatorTree *DT; // not required
+  DominatorTree *DT;
   bool MadeIRChange;
   LibCallSimplifier *Simplifier;
   bool MinimizeSize;
 
 public:
   /// Worklist - All of the instructions that need to be simplified.
   InstCombineWorklist Worklist;
 
   /// Builder - This is an IRBuilder that automatically inserts new
   /// instructions into the worklist when they are created.
   typedef IRBuilder<true, TargetFolder, InstCombineIRInserter> BuilderTy;
   BuilderTy *Builder;
 
   static char ID; // Pass identification, replacement for typeid
-  InstCombiner() : FunctionPass(ID), DL(nullptr), Builder(nullptr) {
+  InstCombiner()
+      : FunctionPass(ID), DL(nullptr), DT(nullptr), Builder(nullptr) {
     MinimizeSize = false;
     initializeInstCombinerPass(*PassRegistry::getPassRegistry());
   }
 
 public:
   bool runOnFunction(Function &F) override;
 
   bool DoOneIteration(Function &F, unsigned ItNum);
public:
   Instruction *visitInsertElementInst(InsertElementInst &IE);
   Instruction *visitExtractElementInst(ExtractElementInst &EI);
   Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
   Instruction *visitExtractValueInst(ExtractValueInst &EV);
   Instruction *visitLandingPadInst(LandingPadInst &LI);
 
   // visitInstruction - Specify what to return for unhandled instructions...
   Instruction *visitInstruction(Instruction &I) { return nullptr; }
 
+  // True when DB dominates all uses of DI execpt UI.
+  // UI must be in the same block as DI.
+  // The routine checks that the DI parent and DB are different.
+  bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
+                        const BasicBlock *DB) const;
+
+  // Replace select with select operand SIOpd in SI-ICmp sequence when possible
+  bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
+                                 const unsigned SIOpd);
+
 private:
   bool ShouldChangeType(Type *From, Type *To) const;
   Value *dyn_castNegVal(Value *V) const;
   Value *dyn_castFNegVal(Value *V, bool NoSignedZero = false) const;
   Type *FindElementAtOffset(Type *PtrTy, int64_t Offset,
                             SmallVectorImpl<Value *> &NewIndices);
   Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
 

lib/Transforms/InstCombine/InstCombineCompares.cpp

 //===- InstCombineCompares.cpp --------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visitICmp and visitFCmp functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombine.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/Target/TargetLibraryInfo.h"
+
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "instcombine"
 
+// How many times is a select replaced by one of its operands?
+STATISTIC(NumSel, "Number of select opts");
+
+// Initialization Routines
+
 static ConstantInt *getOne(Constant *C) {
   return ConstantInt::get(cast<IntegerType>(C->getType()), 1);
 }
 
 static ConstantInt *ExtractElement(Constant *V, Constant *Idx) {
   return cast<ConstantInt>(ConstantExpr::getExtractElement(V, Idx));
 }
 
for (const User *U : Op0->users()) {
     }
     if (BinOp->getOperand(Op1Idx) != Op1)
       continue;
     GlobalSwapBenefits += LocalSwapBenefits;
   }
   return GlobalSwapBenefits > 0;
 }
 
+/// \brief Check that one use is in the same block as the definition and all
+/// other uses are in blocks dominated by a given block
+///
+/// \param DI Definition
+/// \param UI Use
+/// \param DB Block that must dominate all uses of \p DI outside
+///           the parent block
+/// \return true when \p UI is the only use of \p DI in the parent block
+/// and all other uses of \p DI are in blocks dominated by \p DB.
+///
+bool InstCombiner::dominatesAllUses(const Instruction *DI,
+                                    const Instruction *UI,
+                                    const BasicBlock *DB) const {
+  assert(DI && UI && "Instruction not defined\n");
+  // ignore incomplete definitions
+  if (!DI->getParent())
+    return false;
+  // DI and UI must be in the same block
+  if (DI->getParent() != UI->getParent())
+    return false;
+  // Protect from self-referencing blocks
+  if (DI->getParent() == DB)
+    return false;
+  // DominatorTree available?
+  if (!DT)
+    return false;
+  for (const User *U : DI->users()) {
+    auto *Usr = cast<Instruction>(U);
+    if (Usr != UI && !DT->dominates(DB, Usr->getParent()))
+      return false;
+  }
+  return true;
+}
+
+///
+/// true when the instruction sequence within a block is select-cmp-br.
+///
+static bool isChainSelectCmpBranch(const SelectInst *SI) {
+  const BasicBlock *BB = SI->getParent();
+  if (!BB)
+    return false;
+  auto *BI = dyn_cast_or_null<BranchInst>(BB->getTerminator());
+  if (!BI || BI->getNumSuccessors() != 2)
+    return false;
+  auto *IC = dyn_cast<ICmpInst>(BI->getCondition());
+  if (!IC || (IC->getOperand(0) != SI && IC->getOperand(1) != SI))
+    return false;
+  return true;
+}
+
+///
+/// \brief True when a select result is replaced by one of its operands
+/// in select-icmp sequence. This will eventually result in the elimination
+/// of the select.
+///
+/// \param SI    Select instruction
+/// \param Icmp  Compare instruction
+/// \param SIOpd Operand that replaces the select
+///
+/// Notes:
+/// - The replacement is global and requires dominator information
+/// - The caller is responsible for the actual replacement
+///
+/// Example:
+///
+/// entry:
+///  %4 = select i1 %3, %C* %0, %C* null
+///  %5 = icmp eq %C* %4, null
+///  br i1 %5, label %9, label %7
+///  ...
+///  ; <label>:7                                       ; preds = %entry
+///  %8 = getelementptr inbounds %C* %4, i64 0, i32 0
+///  ...
+///
+/// can be transformed to
+///
+///  %5 = icmp eq %C* %0, null
+///  %6 = select i1 %3, i1 %5, i1 true
+///  br i1 %6, label %9, label %7
+///  ...
+///  ; <label>:7                                       ; preds = %entry
+///  %8 = getelementptr inbounds %C* %0, i64 0, i32 0  // replace by %0!
+///
+/// Similar when the first operand of the select is a constant or/and
+/// the compare is for not equal rather than equal.
+///
+/// NOTE: The function is only called when the select and compare constants
+/// are equal, the optimization can work only for EQ predicates. This is not a
+/// major restriction since a NE compare should be 'normalized' to an equal
+/// compare, which usually happens in the combiner and test case
+/// select-cmp-br.ll
+/// checks for it.
+bool InstCombiner::replacedSelectWithOperand(SelectInst *SI,
+                                             const ICmpInst *Icmp,
+                                             const unsigned SIOpd) {
+  assert(SIOpd == 1 || SIOpd == 2 && "Invalid select operand!\n");
+  if (isChainSelectCmpBranch(SI) && Icmp->getPredicate() == ICmpInst::ICMP_EQ) {
+    BasicBlock *Succ = SI->getParent()->getTerminator()->getSuccessor(1);
+    // The check for the unique predecessor is not the best that can be
+    // done. But it protects efficiently against cases like  when SI's
+    // home block has two successors, Succ and Succ1, and Succ1 predecessor
+    // of Succ. Then SI can't be replaced by SIOpd because the use that gets
+    // replaced can be reached on either path. So the uniqueness check
+    // guarantees that the path all uses of SI (outside SI's parent) are on
+    // is disjoint from all other paths out of SI. But that information
+    // is more expensive to compute, and the trade-off here is in favor
+    // of compile-time.
+    if (Succ->getUniquePredecessor() && dominatesAllUses(SI, Icmp, Succ)) {
+      NumSel++;
+      SI->replaceUsesOutsideBlock(SI->getOperand(SIOpd), SI->getParent());
+      return true;
+    }
+  }
+  return false;
+}
+
 Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
   bool Changed = false;
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   unsigned Op0Cplxity = getComplexity(Op0);
   unsigned Op1Cplxity = getComplexity(Op1);
 
   /// Orders the operands of the compare so that they are listed from most
   /// complex to least complex.  This puts constants before unary operators,
if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
           if (Instruction *NV = FoldOpIntoPhi(I))
             return NV;
         break;
       case Instruction::Select: {
         // If either operand of the select is a constant, we can fold the
         // comparison into the select arms, which will cause one to be
         // constant folded and the select turned into a bitwise or.
         Value *Op1 = nullptr, *Op2 = nullptr;
-        if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1)))
+        ConstantInt *CI = 0;
+        if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) {
           Op1 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC);
-        if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2)))
+          CI = dyn_cast<ConstantInt>(Op1);
+        }
+        if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2))) {
           Op2 = ConstantExpr::getICmp(I.getPredicate(), C, RHSC);
+          CI = dyn_cast<ConstantInt>(Op2);
+        }
 
         // We only want to perform this transformation if it will not lead to
         // additional code. This is true if either both sides of the select
         // fold to a constant (in which case the icmp is replaced with a select
         // which will usually simplify) or this is the only user of the
         // select (in which case we are trading a select+icmp for a simpler
-        // select+icmp).
-        if ((Op1 && Op2) || (LHSI->hasOneUse() && (Op1 || Op2))) {
+        // select+icmp) or all uses of the select can be replaced based on
+        // dominance information ("Global cases").
+        bool Transform = false;
+        if (Op1 && Op2)
+          Transform = true;
+        else if (Op1 || Op2) {
+          // Local case
+          if (LHSI->hasOneUse())
+            Transform = true;
+          // Global cases
+          else if (CI && !CI->isZero())
+            // When Op1 is constant try replacing select with second operand.
+            // Otherwise Op2 is constant and try replacing select with first
+            // operand.
+            Transform = replacedSelectWithOperand(cast<SelectInst>(LHSI), &I,
+                                                  Op1 ? 2 : 1);
+        }
+        if (Transform) {
           if (!Op1)
             Op1 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(1),
                                       RHSC, I.getName());
           if (!Op2)
             Op2 = Builder->CreateICmp(I.getPredicate(), LHSI->getOperand(2),
                                       RHSC, I.getName());
           return SelectInst::Create(LHSI->getOperand(0), Op1, Op2);
         }
         break;
       }
       case Instruction::IntToPtr:
         // icmp pred inttoptr(X), null -> icmp pred X, 0
         if (RHSC->isNullValue() && DL &&
             DL->getIntPtrType(RHSC->getType()) ==
                LHSI->getOperand(0)->getType())
           return new ICmpInst(I.getPredicate(), LHSI->getOperand(0),
                         Constant::getNullValue(LHSI->getOperand(0)->getType()));
         break;
 
       case Instruction::Load:
         // Try to optimize things like "A[i] > 4" to index computations.
         if (GetElementPtrInst *GEP =
               dyn_cast<GetElementPtrInst>(LHSI->getOperand(0))) {
           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
             if (GV->isConstant() && GV->hasDefinitiveInitializer() &&
                 !cast<LoadInst>(LHSI)->isVolatile())
               if (Instruction *Res = FoldCmpLoadFromIndexedGlobal(GEP, GV, I))
                 return Res;
         }
         break;
       }
   }
 
   // If we can optimize a 'icmp GEP, P' or 'icmp P, GEP', do so now.
   if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op0))
     if (Instruction *NI = FoldGEPICmp(GEP, Op1, I.getPredicate(), I))
       return NI;
   if (GEPOperator *GEP = dyn_cast<GEPOperator>(Op1))
     if (Instruction *NI = FoldGEPICmp(GEP, Op0,
                            ICmpInst::getSwappedPredicate(I.getPredicate()), I))
       return NI;
 
   // Test to see if the operands of the icmp are casted versions of other
   // values.  If the ptr->ptr cast can be stripped off both arguments, we do so
   // now.
   if (BitCastInst *CI = dyn_cast<BitCastInst>(Op0)) {
     if (Op0->getType()->isPointerTy() &&
         (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
       // We keep moving the cast from the left operand over to the right
       // operand, where it can often be eliminated completely.
       Op0 = CI->getOperand(0);
 
       // If operand #1 is a bitcast instruction, it must also be a ptr->ptr cast
       // so eliminate it as well.

lib/Transforms/InstCombine/InstructionCombining.cpp

void LLVMInitializeInstCombine(LLVMPassRegistryRef R) {
   initializeInstCombine(*unwrap(R));
 }
 
 char InstCombiner::ID = 0;
 INITIALIZE_PASS_BEGIN(InstCombiner, "instcombine",
                 "Combine redundant instructions", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionTracker)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(InstCombiner, "instcombine",
                 "Combine redundant instructions", false, false)
 
 void InstCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addPreserved<LoopInfo>();
   AU.addRequired<AssumptionTracker>();
   AU.addRequired<TargetLibraryInfo>();
+  AU.addRequired<DominatorTreeWrapperPass>();
+  AU.addPreserved<DominatorTreeWrapperPass>();
 }
 
 
 Value *InstCombiner::EmitGEPOffset(User *GEP) {
   return llvm::EmitGEPOffset(Builder, *getDataLayout(), GEP);
 }
 
 /// ShouldChangeType - Return true if it is desirable to convert a computation

 
 bool InstCombiner::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
   AT = &getAnalysis<AssumptionTracker>();
   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
   DL = DLP ? &DLP->getDataLayout() : nullptr;
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   TLI = &getAnalysis<TargetLibraryInfo>();
 
-  DominatorTreeWrapperPass *DTWP =
-      getAnalysisIfAvailable<DominatorTreeWrapperPass>();
-  DT = DTWP ? &DTWP->getDomTree() : nullptr;
-
   // Minimizing size?
   MinimizeSize = F.getAttributes().hasAttribute(AttributeSet::FunctionIndex,
                                                 Attribute::MinSize);
 
   /// Builder - This is an IRBuilder that automatically inserts new
   /// instructions into the worklist when they are created.
   IRBuilder<true, TargetFolder, InstCombineIRInserter>
     TheBuilder(F.getContext(), TargetFolder(DL),

test/Transforms/InstCombine/pr12338.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define void @entry() nounwind {
 entry:
   br label %for.cond
 
+; CHECK: br label %for.cond
 for.cond:
   %local = phi <1 x i32> [ <i32 0>, %entry ], [ %phi2, %cond.end47 ]
   %phi3 = sub <1 x i32> zeroinitializer, %local
   br label %cond.end
 
 cond.false:
   br label %cond.end
 
 cond.end:
   %cond = phi <1 x i32> [ %phi3, %for.cond ], [ undef, %cond.false ]
   br label %cond.end47
 
 cond.end47:
   %sum = add <1 x i32> %cond, <i32 92>
-; CHECK: sub <1 x i32> <i32 -92>, %cond
   %phi2 = sub <1 x i32> zeroinitializer, %sum
   br label %for.cond
 }

test/Transforms/InstCombine/pr21199.ll

+; do not replace a 'select' with 'or' in 'select - cmp - br' sequence
+; RUN: opt -instcombine -S < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @f(i32)
+
+define void @test(i32 %len) {
+entry:
+  %cmp = icmp ult i32 %len, 8
+  %cond = select i1 %cmp, i32 %len, i32 8
+  %cmp11 = icmp ult i32 0, %cond
+  br i1 %cmp11, label %for.body, label %for.end
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.02 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  tail call void @f(i32 %cond)
+  %inc = add i32 %i.02, 1
+  %cmp1 = icmp ult i32 %inc, %cond
+  br i1 %cmp1, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+; CHECK: select
+}

test/Transforms/InstCombine/pr21210.ll

+; RUN: opt < %s -mtriple=x86_64-unknown-linux-gnu -instcombine -S | FileCheck %s
+; Checks that the select-icmp optimization is safe in two cases
+declare void @foo(i32)
+declare i32 @bar(i32)
+
+; don't replace 'cond' by 'len' in the home block ('bb') that
+; contains the select
+define void @test1(i32 %len) {
+entry:
+  br label %bb
+
+bb:
+  %cmp = icmp ult i32 %len, 8
+  %cond = select i1 %cmp, i32 %len, i32 8
+  call void @foo(i32 %cond)
+  %cmp11 = icmp eq i32 %cond, 8
+  br i1 %cmp11, label %for.end, label %bb
+
+for.end:
+  ret void
+; CHECK: select
+; CHECK: icmp eq i32 %cond, 8
+}
+
+; don't replace 'cond' by 'len' in a block ('b1') that dominates all uses
+; of the select outside the home block ('bb'), but can be reached from the home
+; block on another path ('bb -> b0 -> b1')
+define void @test2(i32 %len) {
+entry:
+  %0 = call i32 @bar(i32 %len);
+  %cmp = icmp ult i32 %len, 4
+  br i1 %cmp, label %bb, label %b1
+bb:
+  %cond = select i1 %cmp, i32 %len, i32 8
+  %cmp11 = icmp eq i32 %cond, 8
+  br i1 %cmp11, label %b0, label %b1
+
+b0:
+  call void @foo(i32 %len)
+  br label %b1
+
+b1:
+; CHECK: phi i32 [ %cond, %bb ], [ undef, %b0 ], [ %0, %entry ]
+  %1 = phi i32 [ %cond, %bb ], [ undef, %b0 ], [ %0, %entry ]
+  br label %ret
+
+ret:
+  call void @foo(i32 %1)
+  ret void
+}

test/Transforms/InstCombine/select-cmp-br.ll

+; Replace a 'select' with 'or' in 'select - cmp [eq|ne] - br' sequence
+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+%C = type <{ %struct.S }>
+%struct.S = type { i64*, i32, i32 }
+
+declare void @bar(%struct.S *) #1
+declare void @foobar()
+
+define void @test1(%C*) {
+entry:
+  %1 = getelementptr inbounds %C* %0, i64 0, i32 0, i32 0
+  %m = load i64** %1, align 8
+  %2 = getelementptr inbounds %C* %0, i64 1, i32 0, i32 0
+  %n = load i64** %2, align 8
+  %3 = getelementptr inbounds i64* %m, i64 9
+  %4 = bitcast i64* %3 to i64 (%C*)**
+  %5 = load i64 (%C*)** %4, align 8
+  %6 = icmp eq i64* %m, %n
+  %7 = select i1 %6, %C* %0, %C* null
+  %8 = icmp eq %C* %7, null
+  br i1 %8, label %12, label %10
+
+; <label>:9                                       ; preds = %10, %12
+  ret void
+
+; <label>:10                                      ; preds = %entry
+  %11 = getelementptr inbounds %C* %7, i64 0, i32 0
+  tail call void @bar(%struct.S* %11)
+  br label %9
+
+; <label>:12                                      ; preds = %entry
+  %13 = tail call i64 %5(%C* %0)
+  br label %9
+; CHECK-LABEL: @test1(
+; CHECK-NOT: select
+; CHECK: or
+; CHECK-NOT: select
+}
+
+define void @test2(%C*) {
+entry:
+  %1 = getelementptr inbounds %C* %0, i64 0, i32 0, i32 0
+  %m = load i64** %1, align 8
+  %2 = getelementptr inbounds %C* %0, i64 1, i32 0, i32 0
+  %n = load i64** %2, align 8
+  %3 = getelementptr inbounds i64* %m, i64 9
+  %4 = bitcast i64* %3 to i64 (%C*)**
+  %5 = load i64 (%C*)** %4, align 8
+  %6 = icmp eq i64* %m, %n
+  %7 = select i1 %6, %C* null, %C* %0
+  %8 = icmp eq %C* %7, null
+  br i1 %8, label %12, label %10
+
+; <label>:9                                       ; preds = %10, %12
+  ret void
+
+; <label>:10                                      ; preds = %entry
+  %11 = getelementptr inbounds %C* %7, i64 0, i32 0
+  tail call void @bar(%struct.S* %11)
+  br label %9
+
+; <label>:12                                      ; preds = %entry
+  %13 = tail call i64 %5(%C* %0)
+  br label %9
+; CHECK-LABEL: @test2(
+; CHECK-NOT: select
+; CHECK: or
+; CHECK-NOT: select
+}
+
+define void @test3(%C*) {
+entry:
+  %1 = getelementptr inbounds %C* %0, i64 0, i32 0, i32 0
+  %m = load i64** %1, align 8
+  %2 = getelementptr inbounds %C* %0, i64 1, i32 0, i32 0
+  %n = load i64** %2, align 8
+  %3 = getelementptr inbounds i64* %m, i64 9
+  %4 = bitcast i64* %3 to i64 (%C*)**
+  %5 = load i64 (%C*)** %4, align 8
+  %6 = icmp eq i64* %m, %n
+  %7 = select i1 %6, %C* %0, %C* null
+  %8 = icmp ne %C* %7, null
+  br i1 %8, label %10, label %12
+
+; <label>:9                                       ; preds = %10, %12
+  ret void
+
+; <label>:10                                      ; preds = %entry
+  %11 = getelementptr inbounds %C* %7, i64 0, i32 0
+  tail call void @bar(%struct.S* %11)
+  br label %9
+
+; <label>:12                                      ; preds = %entry
+  %13 = tail call i64 %5(%C* %0)
+  br label %9
+; CHECK-LABEL: @test3(
+; CHECK-NOT: select
+; CHECK: or
+; CHECK-NOT: select
+}
+
+define void @test4(%C*) {
+entry:
+  %1 = getelementptr inbounds %C* %0, i64 0, i32 0, i32 0
+  %m = load i64** %1, align 8
+  %2 = getelementptr inbounds %C* %0, i64 1, i32 0, i32 0
+  %n = load i64** %2, align 8
+  %3 = getelementptr inbounds i64* %m, i64 9
+  %4 = bitcast i64* %3 to i64 (%C*)**
+  %5 = load i64 (%C*)** %4, align 8
+  %6 = icmp eq i64* %m, %n
+  %7 = select i1 %6, %C* null, %C* %0
+  %8 = icmp ne %C* %7, null
+  br i1 %8, label %10, label %12
+
+; <label>:9                                       ; preds = %10, %12
+  ret void
+
+; <label>:10                                      ; preds = %entry
+  %11 = getelementptr inbounds %C* %7, i64 0, i32 0
+  tail call void @bar(%struct.S* %11)
+  br label %9
+
+; <label>:12                                      ; preds = %entry
+  %13 = tail call i64 %5(%C* %0)
+  br label %9
+; CHECK-LABEL: @test4(
+; CHECK-NOT: select
+; CHECK: or
+; CHECK-NOT: select
+}
+
+define void @test5(%C*, i1) {
+entry:
+  %2 = select i1 %1, %C* null, %C* %0
+  %3 = icmp ne %C* %2, null
+  br i1 %3, label %5, label %7
+
+; <label>:4                                       ; preds = %10, %12
+  ret void
+
+; <label>:5                                      ; preds = %entry
+  %6 = getelementptr inbounds %C* %2, i64 0, i32 0
+  tail call void @bar(%struct.S* %6)
+  br label %4
+
+; <label>:7                                      ; preds = %entry
+  tail call void @foobar()
+  br label %4
+; CHECK-LABEL: @test5(
+; CHECK-NOT: select
+; CHECK: or
+; CHECK-NOT: select
+}