Select elimination pass

[Gerolf]

Summary

In special cases select instructions can be eliminated by
replacing them with a cheaper bitwise operation. The instance implemented
by this pass is %x=icmp.eq; %y=select %x,%r, null; %z=icmp.eq %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 global and performed only when all uses
of the select result can be replaced by the select true value. For this
dominator information is used.

[chandlerc]

Why isn't this an instcombine on select instructions?

[majnemer]

lib/Transforms/Scalar/SelectElimination.cpp

129–132

auto would be more concise here, the type is also in the dyn_cast template argument.

146–147

You can fold this dyn_cast into the if.

174

Should be capitalized.

185–186

You can fold these together too.

[Gerolf]

Select Elimination Pass update

Improved readability and addressed review:

• moved code that replaces select into a function replaceSelectWithOr()
• moved the checks for the selection condition compare into functio isChainSelectCmpEQBranch().
• cleared up some clutter as David M. had suggested

[ributzka]

Hi Gerolf,

I added a few comments and questions inline.

-Juergen

lib/Transforms/Scalar/SelectElimination.cpp

80

Your pass doesn't preserve the CFG?

82

We don't add the function name in the comments anymore.

105

ditto

118

ditto

145

ditto

170

ditto

175

I would add an assert with isa<ICmpInst> and then use just cast<ICmpInst>, since you are not checking the result of the dyn_cast anyways.

212

Why is the iterator incremented in the loop?

214

You could combine this with dyn_cast to one line or you could invert the condition and add a continue to reduce the indentation of the code afterwards.

[mcrosier]

lib/Transforms/Scalar/SelectElimination.cpp

61

The command-line option should be in the PassManagerBuilder. Rather than return from the runOnFunction, we should not add the pass to the pass manager.

[Gerolf]

I integrate the optimization into InstCombine and close this review. @Juergen, Chad, Dave and Chandler - thank you for your review time and comments.

bindings/ocaml/transforms/scalar/scalar_opts_ocaml.c

 
 /* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
 CAMLprim value llvm_add_gvn(LLVMPassManagerRef PM) {
   LLVMAddGVNPass(PM);
   return Val_unit;
 }
 
 /* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
+CAMLprim value llvm_add_select_elimination(LLVMPassManagerRef PM) {
+  LLVMAddSelectEliminationPass(PM);
+  return Val_unit;
+}
+
+/* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
 CAMLprim value llvm_add_memcpy_opt(LLVMPassManagerRef PM) {
   LLVMAddMemCpyOptPass(PM);
   return Val_unit;
 }
 
 /* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
 CAMLprim value llvm_add_loop_deletion(LLVMPassManagerRef PM) {
   LLVMAddLoopDeletionPass(PM);

include/llvm-c/Transforms/Scalar.h

 void LLVMAddScalarizerPass(LLVMPassManagerRef PM);
 
 /** See llvm::createMergedLoadStoreMotionPass function. */
 void LLVMAddMergedLoadStoreMotionPass(LLVMPassManagerRef PM);
 
 /** See llvm::createGVNPass function. */
 void LLVMAddGVNPass(LLVMPassManagerRef PM);
 
+/** See llvm::createSelectEliminationPass function. */
+void LLVMAddSelectEliminationPass(LLVMPassManagerRef PM);
+
 /** See llvm::createIndVarSimplifyPass function. */
 void LLVMAddIndVarSimplifyPass(LLVMPassManagerRef PM);
 
 /** See llvm::createInstructionCombiningPass function. */
 void LLVMAddInstructionCombiningPass(LLVMPassManagerRef PM);
 
 /** See llvm::createJumpThreadingPass function. */
 void LLVMAddJumpThreadingPass(LLVMPassManagerRef PM);

include/llvm/InitializePasses.h

 void initializeRegionPrinterPass(PassRegistry&);
 void initializeRegionViewerPass(PassRegistry&);
 void initializeSCCPPass(PassRegistry&);
 void initializeSROAPass(PassRegistry&);
 void initializeSROA_DTPass(PassRegistry&);
 void initializeSROA_SSAUpPass(PassRegistry&);
 void initializeScalarEvolutionAliasAnalysisPass(PassRegistry&);
 void initializeScalarEvolutionPass(PassRegistry&);
+void initializeSelectEliminationPass(PassRegistry &);
 void initializeSimpleInlinerPass(PassRegistry&);
 void initializeRegisterCoalescerPass(PassRegistry&);
 void initializeSingleLoopExtractorPass(PassRegistry&);
 void initializeSinkingPass(PassRegistry&);
 void initializeSeparateConstOffsetFromGEPPass(PassRegistry &);
 void initializeSlotIndexesPass(PassRegistry&);
 void initializeSpillPlacementPass(PassRegistry&);
 void initializeStackProtectorPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createJumpThreadingPass();
       (void) llvm::createUnifyFunctionExitNodesPass();
       (void) llvm::createInstCountPass();
       (void) llvm::createConstantHoistingPass();
       (void) llvm::createCodeGenPreparePass();
       (void) llvm::createEarlyCSEPass();
       (void)llvm::createMergedLoadStoreMotionPass();
       (void) llvm::createGVNPass();
+      (void)llvm::createSelectEliminationPass();
       (void) llvm::createMemCpyOptPass();
       (void) llvm::createLoopDeletionPass();
       (void) llvm::createPostDomTree();
       (void) llvm::createInstructionNamerPass();
       (void) llvm::createMetaRenamerPass();
       (void) llvm::createFunctionAttrsPass();
       (void) llvm::createMergeFunctionsPass();
       (void) llvm::createPrintModulePass(*(llvm::raw_ostream*)nullptr);

include/llvm/Transforms/Scalar.h

 //
 // GVN - This pass performs global value numbering and redundant load
 // elimination cotemporaneously.
 //
 FunctionPass *createGVNPass(bool NoLoads = false);
 
 //===----------------------------------------------------------------------===//
 //
+// SelectElimination - This pass removes selects when possible.
+//
+FunctionPass *createSelectEliminationPass();
+
+//===----------------------------------------------------------------------===//
+//
 // MemCpyOpt - This pass performs optimizations related to eliminating memcpy
 // calls and/or combining multiple stores into memset's.
 //
 FunctionPass *createMemCpyOptPass();
 
 //===----------------------------------------------------------------------===//
 //
 // LoopDeletion - This pass performs DCE of non-infinite loops that it

lib/LTO/LTOCodeGenerator.cpp

void LTOCodeGenerator::initializeLTOPasses() {
   initializeSROAPass(R);
   initializeSROA_DTPass(R);
   initializeSROA_SSAUpPass(R);
   initializeFunctionAttrsPass(R);
   initializeGlobalsModRefPass(R);
   initializeLICMPass(R);
   initializeMergedLoadStoreMotionPass(R);
   initializeGVNPass(R);
+  initializeSelectEliminationPass(R);
   initializeMemCpyOptPass(R);
   initializeDCEPass(R);
   initializeCFGSimplifyPassPass(R);
 }
 
 bool LTOCodeGenerator::addModule(LTOModule* mod, std::string& errMsg) {
   bool ret = IRLinker.linkInModule(&mod->getModule(), &errMsg);
 

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(PassManagerBase &MPM) {
   if (!DisableUnrollLoops)
     MPM.add(createSimpleLoopUnrollPass());    // Unroll small loops
   addExtensionsToPM(EP_LoopOptimizerEnd, MPM);
 
   if (OptLevel > 1) {
     MPM.add(createMergedLoadStoreMotionPass()); // Merge load/stores in diamond
     MPM.add(createGVNPass(DisableGVNLoadPRE));  // Remove redundancies
   }
+  MPM.add(createSelectEliminationPass());     // Remove selects
   MPM.add(createMemCpyOptPass());             // Remove memcpy / form memset
   MPM.add(createSCCPPass());                  // Constant prop with SCCP
 
   // Run instcombine after redundancy elimination to exploit opportunities
   // opened up by them.
   MPM.add(createInstructionCombiningPass());
   addExtensionsToPM(EP_Peephole, MPM);
   MPM.add(createJumpThreadingPass());         // Thread jumps
void PassManagerBuilder::addLTOOptimizationPasses(PassManagerBase &PM) {
 
   // Run a few AA driven optimizations here and now, to cleanup the code.
   PM.add(createFunctionAttrsPass()); // Add nocapture.
   PM.add(createGlobalsModRefPass()); // IP alias analysis.
 
   PM.add(createLICMPass());                 // Hoist loop invariants.
   PM.add(createMergedLoadStoreMotionPass()); // Merge load/stores in diamonds
   PM.add(createGVNPass(DisableGVNLoadPRE)); // Remove redundancies.
+  PM.add(createSelectEliminationPass());     // Remove selects
   PM.add(createMemCpyOptPass());            // Remove dead memcpys.
 
   // Nuke dead stores.
   PM.add(createDeadStoreEliminationPass());
 
   // More loops are countable; try to optimize them.
   PM.add(createIndVarSimplifyPass());
   PM.add(createLoopDeletionPass());

lib/Transforms/Scalar/CMakeLists.txt

add_llvm_library(LLVMScalarOpts
   Reassociate.cpp
   Reg2Mem.cpp
   SCCP.cpp
   SROA.cpp
   SampleProfile.cpp
   Scalar.cpp
   ScalarReplAggregates.cpp
   Scalarizer.cpp
+  SelectElimination.cpp
   SeparateConstOffsetFromGEP.cpp
   SimplifyCFGPass.cpp
   Sink.cpp
   StructurizeCFG.cpp
   TailRecursionElimination.cpp
   )
 
 add_dependencies(LLVMScalarOpts intrinsics_gen)

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeLowerAtomicPass(Registry);
   initializeLowerExpectIntrinsicPass(Registry);
   initializeMemCpyOptPass(Registry);
   initializeMergedLoadStoreMotionPass(Registry);
   initializePartiallyInlineLibCallsPass(Registry);
   initializeReassociatePass(Registry);
   initializeRegToMemPass(Registry);
   initializeSCCPPass(Registry);
+  initializeSelectEliminationPass(Registry);
   initializeIPSCCPPass(Registry);
   initializeSROAPass(Registry);
   initializeSROA_DTPass(Registry);
   initializeSROA_SSAUpPass(Registry);
   initializeCFGSimplifyPassPass(Registry);
   initializeStructurizeCFGPass(Registry);
   initializeSinkingPass(Registry);
   initializeTailCallElimPass(Registry);
void LLVMAddScalarReplAggregatesPassSSA(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createScalarReplAggregatesPass(-1, false));
 }
 
 void LLVMAddScalarReplAggregatesPassWithThreshold(LLVMPassManagerRef PM,
                                                   int Threshold) {
   unwrap(PM)->add(createScalarReplAggregatesPass(Threshold));
 }
 
+void LLVMAddSelectEliminationPass(LLVMPassManagerRef PM) {
+  unwrap(PM)->add(createSelectEliminationPass());
+}
+
 void LLVMAddSimplifyLibCallsPass(LLVMPassManagerRef PM) {
   // NOTE: The simplify-libcalls pass has been removed.
 }
 
 void LLVMAddTailCallEliminationPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createTailCallEliminationPass());
 }
 

lib/Transforms/Scalar/SelectElimination.cpp

+//===- SelectElimination.cpp - remove redundant select instructions     ---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// \file
+// \brief Eliminate select statements by replacing them with bit operations
+//
+//===----------------------------------------------------------------------===//
+//  Example:
+//
+// entry:
+//  ...
+//  %3 = icmp eq i64* %.m, %.n
+//  %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
+//  ...
+//
+//  Eliminate the binary select by
+//  a) inverting the first compare
+//  b) inserting or for the two compares
+//  c) propagting the true select value
+//
+// entry:
+//  ...
+//  %3 = icmp ne i64* %.m, %.n                          (a)
+//  %4 = icmp eq %C* %0, null
+//  %5 = or i1 %3, %4                                   (b)
+//  br i1 %5, label %9, label %7
+//
+//; <label>:7                                       ; preds = %entry
+//  %8 = getelementptr inbounds %C* %0, i64 0, i32 0    (c) -- replace %4 with
+// %0
+// <...>
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include <vector>
+using namespace llvm;
+
+#define DEBUG_TYPE "select-elim"
+
+//===----------------------------------------------------------------------===//
+//                         SelectElimination Pass
+//===----------------------------------------------------------------------===//
+static cl::opt<bool> EnableSE("enable-select-elim",
+                              cl::desc("Enable select elimination"),
+                              cl::init(true));
+
+namespace {
+class SelectElimination : public FunctionPass {
+  DominatorTree *DT;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+  explicit SelectElimination(void) : FunctionPass(ID), DT(nullptr) {
+    initializeSelectEliminationPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override;
+
+private:
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
+  }
+  // dominatesAllUses - true when \param I dominates all of its uses.
+  //
+  bool dominatesAllUses(SelectInst *SI, BasicBlock *D) {
+    bool dominates_all_uses = true;
+    BasicBlock *BB = SI->getParent();
+    for (auto I = SI->use_begin(), E = SI->use_end(); I != E;) {
+      Use &U = *I++;
+      Instruction *User = cast<Instruction>(U.getUser());
+      if (BB == User->getParent() || DT->dominates(D, User->getParent()))
+        continue;
+      dominates_all_uses = false;
+      break;
+    }
+    return dominates_all_uses;
+  }
+  bool isChainSelectCmpEQBranch(SelectInst *SI);
+  bool canReplaceSelectWithOr(SelectInst *SI);
+  void replaceSelectWithOr(SelectInst *SI);
+};
+char SelectElimination::ID = 0;
+}
+
+///
+/// \brief createSelectEliminationPass - The public interface to this file.
+///
+FunctionPass *llvm::createSelectEliminationPass() {
+  return new SelectElimination();
+}
+
+INITIALIZE_PASS_BEGIN(SelectElimination, "select-elim", "SelectElimination",
+                      false, false)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
+INITIALIZE_PASS_END(SelectElimination, "select-elim", "SelectElimination",
+                    false, false)
+
+///
+/// \brief isChainSelectCmpEQBranch - true when there is an icmp-select-icmp
+/// sequence in a basic block
+///
+bool SelectElimination::isChainSelectCmpEQBranch(SelectInst *SI) {
+  BasicBlock *BB = SI->getParent();
+  if (!BB)
+    return false;
+  auto IcmpD = dyn_cast<ICmpInst>(SI->getCondition());
+  if (IcmpD &&
+      (IcmpD->getPredicate() != ICmpInst::ICMP_EQ || !IcmpD->hasOneUse()))
+    return false;
+  if (IcmpD->getParent() != BB)
+    return false;
+  if (!isa<BranchInst>(BB->getTerminator()))
+    return false;
+  auto BI = cast<BranchInst>(BB->getTerminator());
+  if (BI->getNumSuccessors() != 2)
+    return false;
+  auto IC = dyn_cast<ICmpInst>(BI->getCondition());
+  if (IC && IC->getOperand(0) != SI)
+    return false;
+  if (IC->getParent() != BB)
+    return false;
+  return true;
+}
+
+///
+/// \brief canReplaceSelectWithOr - true when the false value of the select
+/// and the second operand of icmp.eq are the null pointer, and all
+/// uses of the select result are either within the basic block that
+/// contains the select or are dominated by the if.else of the compare
+///
+bool SelectElimination::canReplaceSelectWithOr(SelectInst *SI) {
+  auto BI = cast<BranchInst>(SI->getParent()->getTerminator());
+  if (auto IcmpU = dyn_cast<ICmpInst>(BI->getCondition())) {
+    ICmpInst::Predicate PredU = IcmpU->getPredicate();
+    Value *FalseVal = SI->getFalseValue();
+    Value *CmpRHS = IcmpU->getOperand(1);
+    // FIXME: This optimization works when FalseVal and CmpRHL values are
+    // identical.
+    if (PredU == ICmpInst::ICMP_EQ && isa<Constant>(FalseVal) &&
+        cast<Constant>(FalseVal)->isNullValue() && isa<Constant>(CmpRHS) &&
+        cast<Constant>(CmpRHS)->isNullValue())
+      if (SI->hasOneUse() ||
+          SelectElimination::dominatesAllUses(
+              SI, SI->getParent()->getTerminator()->getSuccessor(1)))
+        return true;
+  }
+  return false;
+}
+
+///
+/// \brief replaceSelectWithOr - converts icmp.eq - select - icmp.eq
+/// to icmp.ne - icmp.eq - or
+///
+void SelectElimination::replaceSelectWithOr(SelectInst *SI) {
+  DEBUG(dbgs() << "ICMP - SELECT - ICMP pattern found!\n";);
+  auto IcmpD = dyn_cast<ICmpInst>(SI->getCondition());
+  IcmpD->setPredicate(ICmpInst::ICMP_NE);
+  Value *TrueVal = SI->getTrueValue();
+  SI->replaceAllUsesWith(TrueVal);
+  auto BI = cast<BranchInst>(SI->getParent()->getTerminator());
+  auto IcmpU = cast<ICmpInst>(BI->getCondition());
+  Instruction *IOR = BinaryOperator::Create(Instruction::Or, IcmpD, IcmpU);
+  // Insert the new instruction into the basic block...
+  BasicBlock *InstParent = IcmpU->getParent();
+  BasicBlock::iterator InsertPos = IcmpU;
+
+  InstParent->getInstList().insertAfter(InsertPos, IOR);
+  // Replace all  uses of IcmpU with new predicate.
+  IcmpU->replaceAllUsesWith(IOR);
+  IOR->setOperand(1, IcmpU);
+  SI->eraseFromParent();
+  return;
+}
+
+///
+/// \brief Run the transformation for each function
+///
+bool SelectElimination::runOnFunction(Function &F) {
+
+  if (!EnableSE)
+    return false;
+
+  DEBUG(dbgs() << "Select Elimination\n");
+
+  bool Changed = false;
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+  // Walk all instructions.
+  // For each select check if it can be replaced.
+  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
+    for (BasicBlock::iterator II = BB->begin(), EE = BB->end(); II != EE;) {
+      Instruction *I = &*II;
+      II++;
+      if (isa<SelectInst>(I)) {
+        auto SI = cast<SelectInst>(I);
+        if (isChainSelectCmpEQBranch(SI)) {
+          if (canReplaceSelectWithOr(SI)) {
+            replaceSelectWithOr(SI);
+            Changed = true;
+          }
+        }
+      }
+    }
+  }
+  return Changed;
+}

test/Transforms/SelectElim/select-elim-or.ll

+; Checks if select is eliminated by means of an or operation
+; RUN: opt -select-elim -S < %s | FileCheck %s
+
+%C = type <{ %struct.S }>
+%struct.S = type { i64*, i32, i32 }
+
+declare void @bar(%struct.S *) #1
+
+define void @foo(%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
+; CHECK-NOT: select
+  %7 = select i1 %6, %C* %0, %C* null
+  %8 = icmp eq %C* %7, null
+; CHECK: or
+  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
+}