Index: include/llvm/IR/BasicBlock.h =================================================================== --- include/llvm/IR/BasicBlock.h +++ include/llvm/IR/BasicBlock.h @@ -206,9 +206,19 @@ return const_cast(this)->getUniquePredecessor(); } - /// Return the successor of this block if it has a unique successor. - /// Otherwise return a null pointer. This method is analogous to - /// getUniquePredeccessor above. + /// \brief Return the successor of this block if it has a single successor. + /// Otherwise return a null pointer. + /// + /// This method is analogous to getSinglePredecessor above. + BasicBlock *getSingleSuccessor(); + const BasicBlock *getSingleSuccessor() const { + return const_cast(this)->getSingleSuccessor(); + } + + /// \brief Return the successor of this block if it has a unique successor. + /// Otherwise return a null pointer. + /// + /// This method is analogous to getUniquePredecessor above. BasicBlock *getUniqueSuccessor(); const BasicBlock *getUniqueSuccessor() const { return const_cast(this)->getUniqueSuccessor(); Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -255,6 +255,7 @@ void initializeSeparateConstOffsetFromGEPPass(PassRegistry &); void initializeSlotIndexesPass(PassRegistry&); void initializeSpillPlacementPass(PassRegistry&); +void initializeSpeculativeExecutionPass(PassRegistry&); void initializeStackProtectorPass(PassRegistry&); void initializeStackColoringPass(PassRegistry&); void initializeStackSlotColoringPass(PassRegistry&); Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h +++ include/llvm/LinkAllPasses.h @@ -170,6 +170,7 @@ (void) llvm::createPartiallyInlineLibCallsPass(); (void) llvm::createScalarizerPass(); (void) llvm::createSeparateConstOffsetFromGEPPass(); + (void) llvm::createSpeculativeExecutionPass(); (void) llvm::createRewriteSymbolsPass(); (void) llvm::createStraightLineStrengthReducePass(); (void) llvm::createMemDerefPrinter(); Index: include/llvm/Transforms/Scalar.h =================================================================== --- include/llvm/Transforms/Scalar.h +++ include/llvm/Transforms/Scalar.h @@ -423,6 +423,12 @@ //===----------------------------------------------------------------------===// // +// SpeculativeExecution - Speculatively execute instructions. +// +FunctionPass *createSpeculativeExecutionPass(); + +//===----------------------------------------------------------------------===// +// // LoadCombine - Combine loads into bigger loads. // BasicBlockPass *createLoadCombinePass(); Index: lib/IR/BasicBlock.cpp =================================================================== --- lib/IR/BasicBlock.cpp +++ lib/IR/BasicBlock.cpp @@ -238,6 +238,14 @@ return PredBB; } +BasicBlock *BasicBlock::getSingleSuccessor() { + succ_iterator SI = succ_begin(this), E = succ_end(this); + if (SI == E) return nullptr; // no successors + BasicBlock *TheSucc = *SI; + ++SI; + return (SI == E) ? TheSucc : nullptr /* multiple successors */; +} + BasicBlock *BasicBlock::getUniqueSuccessor() { succ_iterator SI = succ_begin(this), E = succ_end(this); if (SI == E) return NULL; // No successors Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -55,6 +55,10 @@ cl::init(true), cl::Hidden, cl::desc("Enable the new, experimental SROA pass")); +static cl::opt RunSpeculation( + "run-speculative-execution", cl::Hidden, cl::init(false), + cl::desc("Enable the experimental speculative execution pass.")); + static cl::opt RunLoopRerolling("reroll-loops", cl::Hidden, cl::desc("Run the loop rerolling pass")); @@ -227,6 +231,10 @@ MPM.add(createSROAPass(/*RequiresDomTree*/ false)); else MPM.add(createScalarReplAggregatesPass(-1, false)); + + if (RunSpeculation) + MPM.add(createSpeculativeExecutionPass()); + MPM.add(createEarlyCSEPass()); // Catch trivial redundancies MPM.add(createJumpThreadingPass()); // Thread jumps. MPM.add(createCorrelatedValuePropagationPass()); // Propagate conditionals Index: lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- lib/Transforms/Scalar/CMakeLists.txt +++ lib/Transforms/Scalar/CMakeLists.txt @@ -44,6 +44,7 @@ SeparateConstOffsetFromGEP.cpp SimplifyCFGPass.cpp Sink.cpp + SpeculativeExecution.cpp StraightLineStrengthReduce.cpp StructurizeCFG.cpp TailRecursionElimination.cpp Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -74,6 +74,7 @@ initializeSinkingPass(Registry); initializeTailCallElimPass(Registry); initializeSeparateConstOffsetFromGEPPass(Registry); + initializeSpeculativeExecutionPass(Registry); initializeStraightLineStrengthReducePass(Registry); initializeLoadCombinePass(Registry); initializePlaceBackedgeSafepointsImplPass(Registry); Index: lib/Transforms/Scalar/SpeculativeExecution.cpp =================================================================== --- /dev/null +++ lib/Transforms/Scalar/SpeculativeExecution.cpp @@ -0,0 +1,219 @@ +//===- SpeculativeExecution.cpp ---------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass does speculative execution aimed at GPU targets where branches +// are expensive. It currently works on simple if-then and if-then-else +// patterns. E.g. consider this code and assume that there is no addressing +// mode for multiplying by sizeof(*a): +// +// if (b > 0) +// c = a[i + 1] +// if (d > 0) +// e = a[i + 2] +// +// turns into +// +// p = &a[i + 1]; +// if (b > 0) +// c = *p; +// q = &a[i + 2]; +// if (d > 0) +// e = *q; +// +// which could later be optimized to +// +// r = &a[i]; +// if (b > 0) +// c = r[1]; +// if (d > 0) +// e = r[2]; +// +// Later passes sink back much of the speculated code that did not enable +// further optimization. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/SmallSet.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/Operator.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" + +using namespace llvm; + +#define DEBUG_TYPE "speculative-execution" + +// The risk that speculation will not pay off increases with the +// number of instructions speculated, so we put a limit on that. +static cl::opt SpecExecMaxSpeculationCost( + "spec-exec-max-speculation-cost", cl::init(7), cl::Hidden, + cl::desc("Speculative execution is not applied to basic blocks where " + "the cost of the instructions to speculatively execute " + "exceeds this limit.")); + +// Speculating just a few instructions from a larger block tends not +// to be profitable and this limit prevents that. A reason for that is +// that small basic blocks are more likely to be candidates for +// further optimization. +static cl::opt SpecExecMaxNotHoisted( + "spec-exec-max-not-hoisted", cl::init(5), cl::Hidden, + cl::desc("Speculative execution is not applied to basic blocks where the " + "number of instructions that would not be speculatively executed " + "exceeds this limit.")); + +class SpeculativeExecution : public FunctionPass { + public: + static char ID; + SpeculativeExecution(): FunctionPass(ID) {} + + bool runOnFunction(Function &F) override; + + private: + bool runOnBasicBlock(BasicBlock &B); + bool considerHoistingFromTo(BasicBlock &FromBlock, BasicBlock &ToBlock); +}; + +char SpeculativeExecution::ID = 0; +INITIALIZE_PASS(SpeculativeExecution, "speculative-execution", + "Speculatively execute instructions", false, false) + +bool SpeculativeExecution::runOnFunction(Function &F) { + if (skipOptnoneFunction(F)) + return false; + + bool Changed = false; + for (auto& B : F) { + Changed |= runOnBasicBlock(B); + } + return Changed; +} + +bool SpeculativeExecution::runOnBasicBlock(BasicBlock &B) { + BranchInst *BI = dyn_cast(B.getTerminator()); + if (BI == nullptr) + return false; + + if (BI->getNumSuccessors() != 2) + return false; + BasicBlock &Succ0 = *BI->getSuccessor(0); + BasicBlock &Succ1 = *BI->getSuccessor(1); + + if (&B == &Succ0 || &B == &Succ1 || &Succ0 == &Succ1) { + return false; + } + + // Hoist from if-then (triangle). + if (Succ0.getSinglePredecessor() != nullptr && + Succ0.getSingleSuccessor() == &Succ1) { + return considerHoistingFromTo(Succ0, B); + } + + // Hoist from if-else (triangle). + if (Succ1.getSinglePredecessor() != nullptr && + Succ1.getSingleSuccessor() == &Succ0) { + return considerHoistingFromTo(Succ1, B); + } + + // Hoist from if-then-else (diamond), but only if it is equivalent to + // an if-else or if-then due to one of the branches doing nothing. + if (Succ0.getSinglePredecessor() != nullptr && + Succ1.getSinglePredecessor() != nullptr && + Succ1.getSingleSuccessor() != nullptr && + Succ1.getSingleSuccessor() != &B && + Succ1.getSingleSuccessor() == Succ0.getSingleSuccessor()) { + // If a block has only one instruction, then that is a terminator + // instruction so that the block does nothing. This does happen. + if (Succ1.size() == 1) // equivalent to if-then + return considerHoistingFromTo(Succ0, B); + if (Succ0.size() == 1) // equivalent to if-else + return considerHoistingFromTo(Succ1, B); + } + + return false; +} + +static unsigned ComputeSpeculationCost(const User *I) { + // This selection of instructions and their cost is based on informal + // benchmarking. There is likely room for improvement. + switch (Operator::getOpcode(I)) { + case Instruction::GetElementPtr: + // GEPs are cheap if all indices are constant. + return cast(I)->hasAllConstantIndices() ? 1 : 2; + + case Instruction::Add: + case Instruction::Mul: + case Instruction::And: + case Instruction::Or: + case Instruction::Select: + case Instruction::Shl: + case Instruction::Sub: + case Instruction::LShr: + case Instruction::AShr: + case Instruction::Xor: + case Instruction::ZExt: + case Instruction::SExt: + return 1; // These are all cheap. + + default: + return UINT_MAX; // Disallow anything not whitelisted. + } +} + +bool SpeculativeExecution::considerHoistingFromTo(BasicBlock &FromBlock, + BasicBlock &ToBlock) { + SmallSet NotHoisted; + const auto AllPrecedingUsesFromBlockHoisted = [&NotHoisted](User *U) { + for (Value* V : U->operand_values()) { + if (Instruction *I = dyn_cast(V)) { + if (NotHoisted.count(I) > 0) + return false; + } + } + return true; + }; + + unsigned TotalSpeculationCost = 0; + for (auto& I : FromBlock) { + const unsigned Cost = ComputeSpeculationCost(&I); + if (Cost != UINT_MAX && isSafeToSpeculativelyExecute(&I) && + AllPrecedingUsesFromBlockHoisted(&I)) { + TotalSpeculationCost += Cost; + if (TotalSpeculationCost > SpecExecMaxSpeculationCost) + return false; // too much to hoist + } else { + NotHoisted.insert(&I); + if (NotHoisted.size() > SpecExecMaxNotHoisted) + return false; // too much left behind + } + } + + if (TotalSpeculationCost == 0) + return false; // nothing to hoist + + for (auto I = FromBlock.begin(); I != FromBlock.end();) { + // We have to increment I before moving Current as moving Current + // changes the list that I is iterating through. + auto Current = I; + ++I; + if (!NotHoisted.count(Current)) { + Current->moveBefore(ToBlock.getTerminator()); + } + } + return true; +} + +namespace llvm { + +FunctionPass *createSpeculativeExecutionPass() { + return new SpeculativeExecution(); +} + +} // namespace llvm Index: test/Transforms/SpeculativeExecution/spec.ll =================================================================== --- /dev/null +++ test/Transforms/SpeculativeExecution/spec.ll @@ -0,0 +1,195 @@ +; RUN: opt < %s -S -speculative-execution \ +; RUN: -spec-exec-max-speculation-cost 4 -spec-exec-max-not-hoisted 3 \ +; RUN: | FileCheck %s + +target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64" + +; Hoist in if-then pattern. +define void @ifThen() { +; CHECK-LABEL: @ifThen( +; CHECK: %x = add i32 2, 3 +; CHECK: br i1 true + br i1 true, label %a, label %b +; CHECK: a: +a: + %x = add i32 2, 3 +; CHECK: br label + br label %b +; CHECK: b: +b: +; CHECK: ret void + ret void +} + +; Hoist in if-else pattern. +define void @ifElse() { +; CHECK-LABEL: @ifElse( +; CHECK: %x = add i32 2, 3 +; CHECK: br i1 true + br i1 true, label %b, label %a +; CHECK: a: +a: + %x = add i32 2, 3 +; CHECK: br label + br label %b +; CHECK: b: +b: +; CHECK: ret void + ret void +} + +; Hoist in if-then-else pattern if it is equivalent to if-then. +define void @ifElseThenAsIfThen() { +; CHECK-LABEL: @ifElseThenAsIfThen( +; CHECK: %x = add i32 2, 3 +; CHECK: br + br i1 true, label %a, label %b +; CHECK: a: +a: + %x = add i32 2, 3 +; CHECK: br label + br label %c +; CHECK: b: +b: + br label %c +; CHECK: c +c: + ret void +} + +; Hoist in if-then-else pattern if it is equivalent to if-else. +define void @ifElseThenAsIfElse() { +; CHECK-LABEL: @ifElseThenAsIfElse( +; CHECK: %x = add i32 2, 3 +; CHECK: br + br i1 true, label %b, label %a +; CHECK: a: +a: + %x = add i32 2, 3 +; CHECK: br label + br label %c +; CHECK: b: +b: + br label %c +; CHECK: c +c: + ret void +} + +; Do not hoist if-then-else pattern if it is not equivalent to if-then +; or if-else. +define void @ifElseThen() { +; CHECK-LABEL: @ifElseThen( +; CHECK: br + br i1 true, label %a, label %b +; CHECK: a: +a: +; CHECK: %x = add + %x = add i32 2, 3 +; CHECK: br label + br label %c +; CHECK: b: +b: +; CHECK: %y = add + %y = add i32 2, 3 + br label %c +; CHECK: c +c: + ret void +} + +; Do not hoist loads and do not hoist an instruction past a definition of +; an operand. +define void @doNotHoistPastDef() { +; CHECK-LABEL: @doNotHoistPastDef( + br i1 true, label %b, label %a +; CHECK-NOT: load +; CHECK-NOT: add +; CHECK: a: +a: +; CHECK: %def = load + %def = load i32, i32* null +; CHECK: %use = add + %use = add i32 %def, 0 + br label %b +; CHECK: b: +b: + ret void +} + +; Case with nothing to speculate. +define void @nothingToSpeculate() { +; CHECK-LABEL: @nothingToSpeculate( + br i1 true, label %b, label %a +; CHECK: a: +a: +; CHECK: %def = load + %def = load i32, i32* null + br label %b +; CHECK: b: +b: + ret void +} + +; Still hoist if an operand is defined before the block or is itself hoisted. +define void @hoistIfNotPastDef() { +; CHECK-LABEL: @hoistIfNotPastDef( +; CHECK: %x = load + %x = load i32, i32* null +; CHECK: %y = add i32 %x, 1 +; CHECK: %z = add i32 %y, 1 +; CHECK: br + br i1 true, label %b, label %a +; CHECK: a: +a: + %y = add i32 %x, 1 + %z = add i32 %y, 1 + br label %b +; CHECK: b: +b: + ret void +} + +; Do not hoist if the speculation cost is too high. +define void @costTooHigh() { +; CHECK-LABEL: @costTooHigh( +; CHECK: br + br i1 true, label %b, label %a +; CHECK: a: +a: +; CHECK: %r1 = add + %r1 = add i32 1, 1 +; CHECK: %r2 = add + %r2 = add i32 1, 1 +; CHECK: %r3 = add + %r3 = add i32 1, 1 +; CHECK: %r4 = add + %r4 = add i32 1, 1 +; CHECK: %r5 = add + %r5 = add i32 1, 1 + br label %b +; CHECK: b: +b: + ret void +} + +; Do not hoist if too many instructions are left behind. +define void @tooMuchLeftBehind() { +; CHECK-LABEL: @tooMuchLeftBehind( +; CHECK: br + br i1 true, label %b, label %a +; CHECK: a: +a: +; CHECK: %x = load + %x = load i32, i32* null +; CHECK: %r1 = add + %r1 = add i32 %x, 1 +; CHECK: %r2 = add + %r2 = add i32 %x, 1 +; CHECK: %r3 = add + %r3 = add i32 %x, 1 + br label %b +; CHECK: b: +b: + ret void +}