[Speculation] Add a SpeculativeExecution mode where the pass does nothing unless TTI::hasBranchDivergence() is true.

[jlebar]

Summary

This lets us add this pass to the IR pass manager unconditionally; it
will simply not do anything on targets without branch divergence.

[tra]

lib/Transforms/Scalar/SpeculativeExecution.cpp

272 ↗

(On Diff #52130)

Could we pass an argument to createSpeculativeExecutionPass() instead of encoding it in the name?

[jlebar]

lib/Transforms/Scalar/SpeculativeExecution.cpp

272 ↗

(On Diff #52130)

We could, although I wouldn't want it to be a boolean; see my (by now quite old) rant about this: http://jlebar.com/2011/12/16/Boolean_parameters_to_API_functions_considered_harmful..html

I figured it wasn't worth exposing an enum into the llvm namespace, but if that's preferred, I can do it.

[mehdi_amini]

lib/Transforms/Scalar/SpeculativeExecution.cpp

272 ↗

(On Diff #52130)

Offtopic: I'm so glad to see your blog post entry. I'd had the same argument on a patch review once on llvm-commits! I'm trying to avoid it as much as possible.

[chandlerc]

Two high level comment:

1. I'd just add in the PassManagerBuilder change here...

2. Please add a pass-local flag that allows you to test the pass in both modes, and some test cases exercising the behavior here.

lib/Transforms/Scalar/SpeculativeExecution.cpp

96 ↗

(On Diff #52130)

LLVM doesn't use this style for enums.

However, I wouldn't use an enum here. I would just use a well named boolean.

272 ↗

(On Diff #52130)

While I'm sympathetic, and I think having separate public functions is fine, I wouldn't reach to the full power of an enum here.

Within LLVM and Clang we pretty commonly will use '/*MyFlagName*/ true' as the argument. There is even a clang-tidy check that will ensure the name in the argument and the name in the parameter match so you don't get the ugly bugs here. I'd just go with that pattern as it seems like a lot less overhead for something simple and localized to this file.

[jlebar]

lib/Transforms/Scalar/SpeculativeExecution.cpp

272 ↗

(On Diff #52130)

I'd just go with [the pass a "named bool" arg] pattern as it seems like a lot less overhead for something simple and localized to this file.

I think it's a question of the relative public-ness of APIs. For the API that's private to this file, sure, I agree that an enum is overkill, I'll change it to a named bool.

But for the public functions, it's a lot harder to guarantee that people are going to call them in a sane way. In fact, people can call them from outside the LLVM project entirely. So those are exactly the kinds of functions I was talking about in the blog post. I also like separate named functions over a public enum in this case.

(FWIW I don't think clang-tidy is relevant until it's run automatically as part of most peoples' workflows. At the moment, I think I'm one of the only ones who runs clang-*format* automatically, and I had to write a wrapper around arc to accomplish that. I haven't bothered to figure out clang-tidy, mostly because, eh, but also I think it's nontrivial because I'd need to give it -I paths. If you actually want to rely on clang-tidy in general, we should figure out how to incorporate it into everyone's workflows; otherwise, I can't rely on other people using it.

Moreover, the clang-tidy check I'm familiar with only ensures that, if you write the "named bool" comment in a certain way, the name is right. It doesn't ensure that you name the bool at all, and it doesn't catch all of the creative ways you could write the name. So even if it were running on every patch, it wouldn't prevent the problems described in that blog post.)

Anyway, I think we're on the same page here.

[jlebar]

Please add a pass-local flag that allows you to test the pass in both modes, and some test cases exercising the behavior here.

Chandler, how would you feel if I added a test to D18626 instead? (The test would check that we do the speculative execution only on the appropriate targets.)

Adding a flag to force speculative execution on (or off?) doesn't seem to test what we're actually after, namely that we do SpeculativeExecution iff the target has divergent branches.

[chandlerc]

In D18625#398483, @jlebar wrote:

Please add a pass-local flag that allows you to test the pass in both modes, and some test cases exercising the behavior here.

Chandler, how would you feel if I added a test to D18626 instead? (The test would check that we do the speculative execution only on the appropriate targets.)

You should also probably do some testing there, but...

Adding a flag to force speculative execution on (or off?) doesn't seem to test what we're actually after, namely that we do SpeculativeExecution iff the target has divergent branches.

I'm not suggesting you force speculation on or off here. I'm suggesting you toggle the two modes described in the comments: "always" vs "only if divergent arch". Essentially, a flag that simulates the two public functions you can call to construct the pass.

You can use a target that will trivially never have speculation enabled to ensure you can observe this.

I'm essentially saying you should test two different things:

1. The pass has an "always" mode that doesn't care about the target. That should involve a flag here.

2. Targets can differentially control this when not in the "always" mode. That can involve having a flag for a single target that swings it both ways, or a flag that swings all targets, or just comparing two known targets. However, the last of these makes it annoying because we have to disable the test if *either* of the targets are missing.

[chandlerc]

In D18625#398483, @jlebar wrote:

Please add a pass-local flag that allows you to test the pass in both modes, and some test cases exercising the behavior here.

Chandler, how would you feel if I added a test to D18626 instead? (The test would check that we do the speculative execution only on the appropriate targets.)

You should also probably do some testing there, but...

Adding a flag to force speculative execution on (or off?) doesn't seem to test what we're actually after, namely that we do SpeculativeExecution iff the target has divergent branches.

I'm not suggesting you force speculation on or off here. I'm suggesting you toggle the two modes described in the comments: "always" vs "only if divergent arch". Essentially, a flag that simulates the two public functions you can call to construct the pass.

You can use a target that will trivially never have speculation enabled to ensure you can observe this.

I'm essentially saying you should test two different things:

1. The pass has an "always" mode that doesn't care about the target. That should involve a flag here.

2. Targets can differentially control this when not in the "always" mode. That can involve having a flag for a single target that swings it both ways, or a flag that swings all targets, or just comparing two known targets. However, the last of these makes it annoying because we have to disable the test if *either* of the targets are missing.

[jlebar]

Add test, and flag for testing.

[jlebar]

OK, this what you had in mind?

[chandlerc]

Just some minor nits and tweaks to the testing below. Thanks. LGTM, feel free to submit with this stuff addressed, or ask for clarifications if any of it doesn't make sense.

lib/Transforms/Scalar/SpeculativeExecution.cpp

106–108 ↗

(On Diff #53455)

I would use either ...Arch or ...Target consistently.

Does it make sense to make the flag be the default argument rather than an ||? I don't feel strongly either way.

test/Transforms/SpeculativeExecution/divergent-target.ll

7 ↗

(On Diff #53455)

Maybe put this in '-mtriple' arguments to the two target specific ones? That way the "always" mode isn't tied to this target?

It would also make the '-march' above more clean as it could be a parallel '-mtriple=x86_64-...'

11 ↗

(On Diff #53455)

This looks stale?

[jlebar]

Address Chandler's comments.

[jlebar]

Thank you for the review, Chandler!

test/Transforms/SpeculativeExecution/divergent-target.ll

7 ↗

(On Diff #53455)

Much better, thanks. I'd been trying -mcpu and -march, but that didn't work, and I didn't look closely enough at opt.cpp to see that -mtriple would do the same.

llvm/trunk/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createInstructionSimplifierPass();
       (void) llvm::createLoopVectorizePass();
       (void) llvm::createSLPVectorizerPass();
       (void) llvm::createBBVectorizePass();
       (void) llvm::createPartiallyInlineLibCallsPass();
       (void) llvm::createScalarizerPass();
       (void) llvm::createSeparateConstOffsetFromGEPPass();
       (void) llvm::createSpeculativeExecutionPass();
+      (void) llvm::createSpeculativeExecutionIfHasBranchDivergencePass();
       (void) llvm::createRewriteSymbolsPass();
       (void) llvm::createStraightLineStrengthReducePass();
       (void) llvm::createMemDerefPrinter();
       (void) llvm::createFloat2IntPass();
       (void) llvm::createEliminateAvailableExternallyPass();
 
       (void)new llvm::IntervalPartition();
       (void)new llvm::ScalarEvolutionWrapperPass();

llvm/trunk/include/llvm/Transforms/Scalar.h

 
 //===----------------------------------------------------------------------===//
 //
 // SpeculativeExecution - Aggressively hoist instructions to enable
 // speculative execution on targets where branches are expensive.
 //
 FunctionPass *createSpeculativeExecutionPass();
 
+// Same as createSpeculativeExecutionPass, but does nothing unless
+// TargetTransformInfo::hasBranchDivergence() is true.
+FunctionPass *createSpeculativeExecutionIfHasBranchDivergencePass();
+
 //===----------------------------------------------------------------------===//
 //
 // LoadCombine - Combine loads into bigger loads.
 //
 BasicBlockPass *createLoadCombinePass();
 
 //===----------------------------------------------------------------------===//
 //

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

 // 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/ADT/SmallSet.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"

 // 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(0), 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 SpeculativeExecution : public FunctionPass {
  public:
    static char ID;
-  SpeculativeExecution(): FunctionPass(ID) {}
+   explicit SpeculativeExecution(bool OnlyIfDivergentTarget = false)
+       : FunctionPass(ID),
+         OnlyIfDivergentTarget(OnlyIfDivergentTarget ||
+                               SpecExecOnlyIfDivergentTarget) {}
 
    void getAnalysisUsage(AnalysisUsage &AU) const override;
    bool runOnFunction(Function &F) override;
 
+   const char *getPassName() const override {
+     if (OnlyIfDivergentTarget)
+       return "Speculatively execute instructions if target has divergent "
+              "branches";
+     return "Speculatively execute instructions";
+   }
+
  private:
   bool runOnBasicBlock(BasicBlock &B);
   bool considerHoistingFromTo(BasicBlock &FromBlock, BasicBlock &ToBlock);
 
+  // If true, this pass is a nop unless the target Targetitecture has branch
+  // divergence.
+  const bool OnlyIfDivergentTarget;
   const TargetTransformInfo *TTI = nullptr;
 };
 } // namespace
 
 char SpeculativeExecution::ID = 0;
 INITIALIZE_PASS_BEGIN(SpeculativeExecution, "speculative-execution",
                       "Speculatively execute instructions", false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(SpeculativeExecution, "speculative-execution",
-                      "Speculatively execute instructions", false, false)
 
 void SpeculativeExecution::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<TargetTransformInfoWrapperPass>();
 }
 
 bool SpeculativeExecution::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
+  if (OnlyIfDivergentTarget && !TTI->hasBranchDivergence()) {
+    DEBUG(dbgs() << "Not running SpeculativeExecution because "
+                    "TTI->hasBranchDivergence() is false.\n");
+    return false;
+  }
 
   bool Changed = false;
   for (auto& B : F) {
     Changed |= runOnBasicBlock(B);
   }
   return Changed;
 }
 

 }
 
 namespace llvm {
 
 FunctionPass *createSpeculativeExecutionPass() {
   return new SpeculativeExecution();
 }
 
+FunctionPass *createSpeculativeExecutionIfHasBranchDivergencePass() {
+  return new SpeculativeExecution(/* OnlyIfDivergentTarget = */ true);
+}
+
 }  // namespace llvm

llvm/trunk/test/Transforms/SpeculativeExecution/divergent-target.ll

+; RUN: opt < %s -S -mtriple=nvptx-nvidia-cuda -speculative-execution | \
+; RUN:   FileCheck --check-prefix=ON %s
+; RUN: opt < %s -S -mtriple=nvptx-nvidia-cuda -speculative-execution \
+; RUN:   -spec-exec-only-if-divergent-target | \
+; RUN:   FileCheck --check-prefix=ON %s
+; RUN: opt < %s -S -march=x86_64 -speculative-execution \
+; RUN:   -spec-exec-only-if-divergent-target | \
+; RUN:   FileCheck --check-prefix=OFF %s
+
+; Hoist in if-then pattern.
+define void @f() {
+; ON: %x = add i32 2, 3
+; ON: br i1 true
+; OFF: br i1 true
+; OFF: %x = add i32 2, 3
+  br i1 true, label %a, label %b
+a:
+  %x = add i32 2, 3
+  br label %b
+b:
+  ret void
+}