llvm/llvm/lib/Transforms/Scalar/SpeculativeExecution.cpp

//===- SpeculativeExecution.cpp ---------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This pass hoists instructions to enable speculative execution on
// targets where branches are expensive. This is aimed at GPUs. It
// currently works on simple if-then and if-then-else
// patterns.
//
// Removing branches is not the only motivation for this
// pass. 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.
//
// This pass is more aggressive than the function SpeculativeyExecuteBB in
// SimplifyCFG. SimplifyCFG will not speculate if no selects are introduced and
// it will speculate at most one instruction. It also will not speculate if
// there is a value defined in the if-block that is only used in the then-block.
// These restrictions make sense since the speculation in SimplifyCFG seems
// aimed at introducing cheap selects, while this pass is intended to do more
// aggressive speculation while counting on later passes to either capitalize on
// that or clean it up.
//
// If the pass was created by calling
// createSpeculativeExecutionIfHasBranchDivergencePass or the
// -spec-exec-only-if-divergent-target option is present, this pass only has an
// effect on targets where TargetTransformInfo::hasBranchDivergence() is true;
// on other targets, it is a nop.
//
// This lets you include this pass unconditionally in the IR pass pipeline, but
// only enable it for relevant targets.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/SpeculativeExecution.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Operator.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Scalar.h"

usingnamespacellvm;

#define DEBUG_TYPE …

// 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<unsigned> 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<unsigned> 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."));

static cl::opt<bool> SpecExecOnlyIfDivergentTarget(
    "spec-exec-only-if-divergent-target", cl::init(false), cl::Hidden,
    cl::desc("Speculative execution is applied only to targets with divergent "
             "branches, even if the pass was configured to apply only to all "
             "targets."));

namespace {

class SpeculativeExecutionLegacyPass : public FunctionPass { … };
} // namespace

char SpeculativeExecutionLegacyPass::ID = …;
INITIALIZE_PASS_BEGIN(SpeculativeExecutionLegacyPass, "speculative-execution",
                      "Speculatively execute instructions", false, false)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_END(SpeculativeExecutionLegacyPass, "speculative-execution",
                    "Speculatively execute instructions", false, false)

void SpeculativeExecutionLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

bool SpeculativeExecutionLegacyPass::runOnFunction(Function &F) { … }

namespace llvm {

bool SpeculativeExecutionPass::runImpl(Function &F, TargetTransformInfo *TTI) { … }

bool SpeculativeExecutionPass::runOnBasicBlock(BasicBlock &B) { … }

static InstructionCost ComputeSpeculationCost(const Instruction *I,
                                              const TargetTransformInfo &TTI) { … }

// Do not hoist any debug info intrinsics.
// ...
// if (cond) {
//   x = y * z;
//   foo();
// }
// ...
// -------- Which then becomes:
// ...
// if.then:
//   %x = mul i32 %y, %z
//   call void @llvm.dbg.value(%x, !"x", !DIExpression())
//   call void foo()
//
// SpeculativeExecution might decide to hoist the 'y * z' calculation
// out of the 'if' block, because it is more efficient that way, so the
// '%x = mul i32 %y, %z' moves to the block above. But it might also
// decide to hoist the 'llvm.dbg.value' call.
// This is incorrect, because even if we've moved the calculation of
// 'y * z', we should not see the value of 'x' change unless we
// actually go inside the 'if' block.

bool SpeculativeExecutionPass::considerHoistingFromTo(
    BasicBlock &FromBlock, BasicBlock &ToBlock) { … }

FunctionPass *createSpeculativeExecutionPass() { … }

FunctionPass *createSpeculativeExecutionIfHasBranchDivergencePass() { … }

SpeculativeExecutionPass::SpeculativeExecutionPass(bool OnlyIfDivergentTarget)
    : … { … }

PreservedAnalyses SpeculativeExecutionPass::run(Function &F,
                                                FunctionAnalysisManager &AM) { … }

void SpeculativeExecutionPass::printPipeline(
    raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { … }
}  // namespace llvm