From 5182ad54b24df52557c7c7170d4b874b6b156673 Mon Sep 17 00:00:00 2001 From: Gerolf Hoflehner Date: Fri, 21 Nov 2014 23:36:44 +0000 Subject: [PATCH] [InstCombine] Re-commit of r218721 (Optimize icmp-select-icmp sequence) Fixes the self-host fail. Note that this commit activates dominator analysis in the combiner by default (like the original commit did). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@222590 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/IR/Value.h | 7 + lib/IR/Value.cpp | 22 +++ lib/Transforms/InstCombine/InstCombine.h | 16 +- .../InstCombine/InstCombineCompares.cpp | 154 ++++++++++++++++- .../InstCombine/InstructionCombining.cpp | 8 +- test/Transforms/InstCombine/pr12338.ll | 2 +- test/Transforms/InstCombine/pr21199.ll | 25 +++ test/Transforms/InstCombine/pr21210.ll | 50 ++++++ test/Transforms/InstCombine/select-cmp-br.ll | 155 ++++++++++++++++++ 9 files changed, 428 insertions(+), 11 deletions(-) create mode 100644 test/Transforms/InstCombine/pr21199.ll create mode 100644 test/Transforms/InstCombine/pr21210.ll create mode 100644 test/Transforms/InstCombine/select-cmp-br.ll diff --git a/include/llvm/IR/Value.h b/include/llvm/IR/Value.h index 67665bea7c1..7541ffbe6e2 100644 --- a/include/llvm/IR/Value.h +++ b/include/llvm/IR/Value.h @@ -258,6 +258,13 @@ public: /// 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. // diff --git a/lib/IR/Value.cpp b/lib/IR/Value.cpp index 4e0c11f15f2..33b9ed20d14 100644 --- a/lib/IR/Value.cpp +++ b/lib/IR/Value.cpp @@ -353,6 +353,28 @@ void Value::replaceAllUsesWith(Value *New) { BB->replaceSuccessorsPhiUsesWith(cast(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(, 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(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 { diff --git a/lib/Transforms/InstCombine/InstCombine.h b/lib/Transforms/InstCombine/InstCombine.h index d4b252be15a..3e53b735ce5 100644 --- a/lib/Transforms/InstCombine/InstCombine.h +++ b/lib/Transforms/InstCombine/InstCombine.h @@ -14,6 +14,7 @@ #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" @@ -98,7 +99,7 @@ class LLVM_LIBRARY_VISIBILITY InstCombiner AssumptionTracker *AT; const DataLayout *DL; TargetLibraryInfo *TLI; - DominatorTree *DT; // not required + DominatorTree *DT; bool MadeIRChange; LibCallSimplifier *Simplifier; bool MinimizeSize; @@ -113,7 +114,8 @@ public: 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()); } @@ -245,6 +247,16 @@ public: // 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; diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp index 399f1c31755..6127eaaa4dd 100644 --- a/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "InstCombine.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" @@ -20,12 +21,20 @@ #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(C->getType()), 1); } @@ -2446,6 +2455,122 @@ static bool swapMayExposeCSEOpportunities(const Value * Op0, 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(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(BB->getTerminator()); + if (!BI || BI->getNumSuccessors() != 2) + return false; + auto *IC = dyn_cast(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 +/// ... +/// ;