[SimplifyCFG] don't sink common insts too soon (PR34603)

[spatel]

Summary

This is a minimal patch to solve PR34603:
https://bugs.llvm.org/show_bug.cgi?id=34603

As discussed there, we need to prevent SimplifyCFG from performing aggressive flattening before early-cse, GVN, and potentially other passes have had a chance to run because we may not be able to see through those transformations. In the example from the original bug report (PR28343), this prevents a whole series of optimizations: recognizing a 'max', vectorizing that max, unrolling a loop, etc.

I've opted to just keep going with the current -simplifycfg / -latesimplifycfg separation, but we could lift the individual options to the pass manager layer if that seems better.

[hfinkel]

This is a minimal patch to solve PR34603:
https://bugs.llvm.org/show_bug.cgi?id=34603

Can you please summarize here what's going on and how you arrived at this solution? Last I recall, in PR34603, we were discussing select formation, and how it might not be desirable to form selects early. By "aggressive flattening" do you mean select formation? What you're doing here seems like more than just disabling select formation, but sinking? I also think that we might not want to sink early, at least some things (because we can't later prove it safe to re-hoist), but it's not immediately clear how all of these things are related.

[spatel]

In D38566#889031, @hfinkel wrote:

This is a minimal patch to solve PR34603:
https://bugs.llvm.org/show_bug.cgi?id=34603

Can you please summarize here what's going on and how you arrived at this solution? Last I recall, in PR34603, we were discussing select formation, and how it might not be desirable to form selects early. By "aggressive flattening" do you mean select formation? What you're doing here seems like more than just disabling select formation, but sinking? I also think that we might not want to sink early, at least some things (because we can't later prove it safe to re-hoist), but it's not immediately clear how all of these things are related.

Sorry for the invented vocabulary. 'Aggressive flattening' was meant to include the select formation, but that's not actually the root of the problem. The sinking is the root of the problem, so that's why I'm proposing to disable that in the early incarnation of SimplifyCFG. My intent (probably needing refinement) is to delay the transform that was added with rL279460 ( SinkThenElseCodeToEnd ) because that's where we regressed the examples in the bug reports. Let me illustrate using the example in the test cases (it's a slightly simplified form of the motivating example in the bug report):

1. When we start, we have redundant values across multiple blocks:

entry:
%xi_ptr = getelementptr double, double* %x, i64 %i
%yi_ptr = getelementptr double, double* %y, i64 %i
%xi = load double, double* %xi_ptr
%yi = load double, double* %yi_ptr

if:
%xi_ptr_again = getelementptr double, double* %x, i64 %i
%xi_again = load double, double* %xi_ptr_again

else:
%yi_ptr_again = getelementptr double, double* %y, i64 %i
%yi_again = load double, double* %yi_ptr_again

early-cse can kill the redundant ops, so we just have the gep+load in 'entry' when it's done.

2. simplifycfg currently runs before early-cse in all -O# pipelines, and SinkThenElseCodeToEnd() applies this transform to create sunk ops in the 'end' block

entry:
  %xi_ptr = getelementptr double, double* %x, i64 %i
  %yi_ptr = getelementptr double, double* %y, i64 %i
  %xi = load double, double* %xi_ptr, align 8
  %yi = load double, double* %yi_ptr, align 8
  %cmp = fcmp ogt double %xi, %yi
  br i1 %cmp, label %if, label %end

if:                                          
  br label %end

end:                                           
  %y.sink = phi double* [ %x, %if ], [ %y, %entry ]    <--- sunk phi of gep base pointers
  %new_gep = getelementptr double, double* %y.sink, i64 %i  <--- redundant geps got killed
  %new_load = load double, double* %new_gep, align 8  <--- redundant loads got killed
  ret double %new_load

3. At this point, there are no CSE opportunities. The initial geps/loads are not the same as the 'common' sunk ops. SimplifyCFG carries on and turns the 2-case phi into a select:

%xi_ptr = getelementptr double, double* %x, i64 %i
%yi_ptr = getelementptr double, double* %y, i64 %i
%xi = load double, double* %xi_ptr
%yi = load double, double* %yi_ptr
%cmp = fcmp ogt double %xi, %yi
%y.sink = select i1 %cmp, double* %x, double* %y
%new_gep = getelementptr double, double* %y.sink, i64 %i
%new_load = load double, double* %new_gep
ret double %new_load

4. Based on https://bugs.llvm.org/show_bug.cgi?id=34603#c19 , I think we agreed that this is practically impossible to recover from in later passes. Therefore, I'm proposing to delay the initial sinking that creates 'common' ops out of potentially redundant ops. It's possible that we also, independently, want to delay select formation in other cases. It's also possible that I've used a sledgehammer where a chisel would've worked. :)

[hfinkel]

In D38566#889296, @spatel wrote:

In D38566#889031, @hfinkel wrote:

This is a minimal patch to solve PR34603:
https://bugs.llvm.org/show_bug.cgi?id=34603

Can you please summarize here what's going on and how you arrived at this solution? Last I recall, in PR34603, we were discussing select formation, and how it might not be desirable to form selects early. By "aggressive flattening" do you mean select formation? What you're doing here seems like more than just disabling select formation, but sinking? I also think that we might not want to sink early, at least some things (because we can't later prove it safe to re-hoist), but it's not immediately clear how all of these things are related.

Sorry for the invented vocabulary. 'Aggressive flattening' was meant to include the select formation, but that's not actually the root of the problem. The sinking is the root of the problem, so that's why I'm proposing to disable that in the early incarnation of SimplifyCFG. My intent (probably needing refinement) is to delay the transform that was added with rL279460 ( SinkThenElseCodeToEnd ) because that's where we regressed the examples in the bug reports. Let me illustrate using the example in the test cases (it's a slightly simplified form of the motivating example in the bug report):

Thanks for the explanation. So, to be clear, we're only delaying the "sinking through PHIs" type of sinking until late?

I'm a bit concerned about the fact that LateSimplyCFG currently runs right after the SLP vectorizer, but we probably want to do select formation aggressively before the SLP vectorizer. We might, in fact, want to form selects more aggressively before the loop vectorizer too. In short, I'm not sure that this variety of "late" is the same as our existing concept of "late" (which is something that interferes with loop structure, and thus, should come after vectorization (at least loop vectorization)).

[spatel]

In D38566#889637, @hfinkel wrote:

Thanks for the explanation. So, to be clear, we're only delaying the "sinking through PHIs" type of sinking until late?

Correct - everything is still here, but we're using the existing def of "late" to limit when it happens.

I'm a bit concerned about the fact that LateSimplyCFG currently runs right after the SLP vectorizer, but we probably want to do select formation aggressively before the SLP vectorizer. We might, in fact, want to form selects more aggressively before the loop vectorizer too. In short, I'm not sure that this variety of "late" is the same as our existing concept of "late" (which is something that interferes with loop structure, and thus, should come after vectorization (at least loop vectorization)).

Ok - it sounds like I should proceed with using the optional bits within the pass manager(s). I'll make it so that we're only preventing the sinking on the first instantiation of simplifycfg (the one before early-cse).

[spatel]

Patch updated:
Now that we have SimplifyCFGOptions exposed to the pass managers, we can use a precise disablement of sinking common instructions to only the first instantiation of -simplifycfg (the one that runs before early-cse).

Depending on your perspective, this is either a redefinition of "canonical form" or we've created a new "pre-canonical form".

Given the comments in PR34603, I suspect we want to limit simplifycfg sinking even more, but that should be a follow-up patch with more phase ordering tests, so we know exactly what kind of patterns we're affecting.

[hfinkel]

In D38566#910739, @spatel wrote:

Patch updated:
Now that we have SimplifyCFGOptions exposed to the pass managers, we can use a precise disablement of sinking common instructions to only the first instantiation of -simplifycfg (the one that runs before early-cse).

Why? The selects also hurt GVN, etc. I thought we were going to delay this until the end of the canonicalization phase. Only then might be have more "phases" in this sense.

Depending on your perspective, this is either a redefinition of "canonical form" or we've created a new "pre-canonical form".

Given the comments in PR34603, I suspect we want to limit simplifycfg sinking even more, but that should be a follow-up patch with more phase ordering tests, so we know exactly what kind of patterns we're affecting.

[spatel]

In D38566#911458, @hfinkel wrote:

In D38566#910739, @spatel wrote:

Patch updated:
Now that we have SimplifyCFGOptions exposed to the pass managers, we can use a precise disablement of sinking common instructions to only the first instantiation of -simplifycfg (the one that runs before early-cse).

Why? The selects also hurt GVN, etc. I thought we were going to delay this until the end of the canonicalization phase. Only then might be have more "phases" in this sense.

I might be overcautious here, but as I wrote in the last comment, I'd like to at least try to manufacture a GVN test case to show that difference. Also, I was hoping to get this diff in independently to reduce the risk of revert from unintended consequences from changing behavior in the later simplifycfg instantiations. If you feel more confident, I can flip the parameter in more places (or invert the default setting) in this patch.

Depending on your perspective, this is either a redefinition of "canonical form" or we've created a new "pre-canonical form".

Given the comments in PR34603, I suspect we want to limit simplifycfg sinking even more, but that should be a follow-up patch with more phase ordering tests, so we know exactly what kind of patterns we're affecting.

[spatel]

In D38566#911702, @spatel wrote:

In D38566#911458, @hfinkel wrote:

In D38566#910739, @spatel wrote:

I might be overcautious here, but as I wrote in the last comment, I'd like to at least try to manufacture a GVN test case to show that difference. Also, I was hoping to get this diff in independently to reduce the risk of revert from unintended consequences from changing behavior in the later simplifycfg instantiations. If you feel more confident, I can flip the parameter in more places (or invert the default setting) in this patch.

As evidence that my fear is not completely delusional, the preliminary patches for this change were recently reverted:
https://reviews.llvm.org/rL317444
...this even erased the commit that added the innocent bystander test case for this patch (sigh).

[spatel]

In D38566#916753, @spatel wrote:

As evidence that my fear is not completely delusional, the preliminary patches for this change were recently reverted:
https://reviews.llvm.org/rL317444
...this even erased the commit that added the innocent bystander test case for this patch (sigh).

I recommitted the preliminary patches at:
https://reviews.llvm.org/rL318299
https://reviews.llvm.org/rL318300

...so ping?

[davide]

The proliferation of cl::opt(s) maybe hints SimplifyCFG is growing a little too much? & might need to be split in separate passes.
SimplifyCFG is a pretty fundamental canonicalization pass & should be almost free to run. For sinking, we have a separate pass, so maybe it's worth taking a look at whether that's fixable instead of patching SimplifyCFG behaviour? I really would like to prevent SimplifyCFG to become the next Instcombine.

[davide]

Until ~ 1 year ago, SimplifyCFG was a single pass, and everything was fine (and IMHO, that's how it should be).
Then we found out it had bad interactions with inlining, so we decided to split in two passes. That's OK, as long as it's una tantum.
Keeping adding knobs to tweak the 4-5 different SimplifyCFG invocations in-tree is a slippery rope.

[spatel]

In D38566#926465, @davide wrote:

Until ~ 1 year ago, SimplifyCFG was a single pass, and everything was fine (and IMHO, that's how it should be).
Then we found out it had bad interactions with inlining, so we decided to split in two passes. That's OK, as long as it's una tantum.
Keeping adding knobs to tweak the 4-5 different SimplifyCFG invocations in-tree is a slippery rope.

I'm not opposed to splitting it up, but that's a larger effort / follow-up to this.
Creating a struct of options for this pass was discussed as a reasonable way to solve PR34603, so that's what I've implemented:
https://bugs.llvm.org/show_bug.cgi?id=34603#c20

[craig.topper]

One issue with the struct approach. Suppose I opt-bisect to a failure caused by one of these simplifyCFG passes. How do I invoke that specific version of simplifycfg from opt to debug it or even produce a reduced test case.

[spatel]

In D38566#926488, @craig.topper wrote:

One issue with the struct approach. Suppose I opt-bisect to a failure caused by one of these simplifyCFG passes. How do I invoke that specific version of simplifycfg from opt to debug it or even produce a reduced test case.

I haven't tried opt-bisect. Does it show the sequence of passes leading up to the failure, or just a single pass where the IR goes wrong? If you have the sequence, then you could cross-reference that to the pipeline manager's instantiation to see how it got invoked and mimic that with the cl::opt. That's not ideal of course, but this is a general problem for any pass that takes options, right?

[davide]

In D38566#926488, @craig.topper wrote:

One issue with the struct approach. Suppose I opt-bisect to a failure caused by one of these simplifyCFG passes. How do I invoke that specific version of simplifycfg from opt to debug it or even produce a reduced test case.

You need to remember the (now) 4, and possibly more flags and try all the combinations (at least this is what I did when I bisected https://bugs.llvm.org/show_bug.cgi?id=35246).
It's a little inconvenient, to put it lightly. That very same bug shows that several part of SimplifyCFG don't play nice with each other, FWIW.

[davide]

In D38566#926472, @spatel wrote:

In D38566#926465, @davide wrote:

Until ~ 1 year ago, SimplifyCFG was a single pass, and everything was fine (and IMHO, that's how it should be).
Then we found out it had bad interactions with inlining, so we decided to split in two passes. That's OK, as long as it's una tantum.
Keeping adding knobs to tweak the 4-5 different SimplifyCFG invocations in-tree is a slippery rope.

I'm not opposed to splitting it up, but that's a larger effort / follow-up to this.
Creating a struct of options for this pass was discussed as a reasonable way to solve PR34603, so that's what I've implemented:
https://bugs.llvm.org/show_bug.cgi?id=34603#c20

Once you end up adding n knobs people start relying on them and splitting the pass becomes more complicated, so "doing that as a follow-up" doesn't really work unless you have a clear plan in mind on how to split. If the majority thinks this is OK, I'm not going to argue further, but this combinatorial explosion of options introduced is clearly a symptom of a larger problem, IMHO.

[spatel]

Ping.

Note that there's another bug that I think will be helped by this patch - https://bugs.llvm.org/show_bug.cgi?id=35354 .
D40304 is proposing to fix that in instcombine.

[spatel]

Ping * 2.

[hfinkel]

In D38566#944355, @spatel wrote:

Ping * 2.

Can you please summarize where we are now with this? I still prefer to have only one form of SimplifyCFG during canonicalization. I feel that doing otherwise is a mistake, in part to make the canonical form understandable, and in part because canonicalization is iterative (now for devirtualization, but maybe in other ways in the future), and so it's much better if we don't think about phases within canonicalization itself.

[spatel]

In D38566#952038, @hfinkel wrote:

In D38566#944355, @spatel wrote:

Ping * 2.

Can you please summarize where we are now with this? I still prefer to have only one form of SimplifyCFG during canonicalization. I feel that doing otherwise is a mistake, in part to make the canonical form understandable, and in part because canonicalization is iterative (now for devirtualization, but maybe in other ways in the future), and so it's much better if we don't think about phases within canonicalization itself.

Sure - the patch is identical to when we discussed this around Oct 30,31. The preliminary steps were blamed for causing a bug ( https://bugs.llvm.org/show_bug.cgi?id=35210 ) and reverted, but subsequently the patches were exonerated, and the bug was fixed independently of this.

There was also concern that having options to passes makes it harder to track down bugs and is a sign of bad design. I don't disagree with that view, but we've already come this far, so I view a change of direction as a follow-up because that's significantly more work at this point. Also, this patch fixes a known regression (a significant performance hit), and I want to close that hole ASAP.

So we have the bare minimum to avoid the bug in the motivating case. But I see your point - having multiple canonical forms/phases will make things more complicated. I thought I might have a test case for the larger patch, but I haven't found an example yet. I'll update the patch as you've requested. If I can come up with a test for it, I'll include it. If not, hopefully, we can just proceed with the one test that's already here.

[spatel]

Patch updated:
As suggested, turn off sinking of common instructions by default because that's known to be potentially harmful to both early-cse and GVN. Enable that option after GVN has run, in the former "latesimplifycfg" invocation, and when invoked in the target-specific backend pipelines for ARM/AArch64 (there is an AArch64 regression test in test/CodeGen/AArch64/rm_redundant_cmp.ll that requires the sinking transform).

[hfinkel]

lib/Passes/PassBuilder.cpp

464

I don't think that we want this here. This is still during canonicalization. You already have this right after SLP vectorization (we might actually want this right before SLP vectorization - do we SLP vectorize things we'll turn into selects otherwise?). Is it bad if you don't have this here for some test case?

[spatel]

lib/Passes/PassBuilder.cpp

464

There are no regression test diffs if I remove the sinking from that invocation (here and the equivalent in the old pass manager).

But there is no SimplifyCFG ahead of the vectorizers in buildModuleOptimizationPipeline() (around line 685). Should I just add a SimplifyCFG with sinkCommonInsts ahead of the loop passes? I agree that we have the potential to miss vectorizations if we have not converted into select form before we get to the vectorization passes.

I tried to manufacture an -O2 PhaseOrdering test that would show the potential regression for SLP, but no luck yet.

[spatel]

Patch updated:

1. Removed the sinking option from the SimplifyCFG invocations that are part of the canonicalization phase.
2. Speculatively implemented what I suggested in the last comment - added a SimplifyCFG pass ahead of vectorization to allow the sinking transform (help the vectorizers by creating larger blocks with selects).

[hfinkel]

In D38566#954011, @spatel wrote:

Patch updated:

1. Removed the sinking option from the SimplifyCFG invocations that are part of the canonicalization phase.
2. Speculatively implemented what I suggested in the last comment - added a SimplifyCFG pass ahead of vectorization to allow the sinking transform (help the vectorizers by creating larger blocks with selects).

Thanks. I'm pretty sure that you want it after the loop vectorizer and before the SLP vectorizer. The reason is that the loop vectorizer does its own if conversion, and moreover, the selects on addresses tend to mess up vectorization (or, at least, I'm pretty sure that's what @craig.topper told me last month). Otherwise, I think this is good.

[spatel]

Patch updated:
This version just moves what was known as 'latesimplifycfg' before the SLP vectorizer (no extra passes are added as in the last rev).
SLP preserves the CFG, so there's no reason to wait to run SimplifyCFG after that.

[hfinkel]

In D38566#955625, @spatel wrote:

Patch updated:
This version just moves what was known as 'latesimplifycfg' before the SLP vectorizer (no extra passes are added as in the last rev).
SLP preserves the CFG, so there's no reason to wait to run SimplifyCFG after that.

Thanks. LGTM.

include/llvm/Transforms/Scalar.h

 
 //===----------------------------------------------------------------------===//
 //
 // CFGSimplification - Merge basic blocks, eliminate unreachable blocks,
 // simplify terminator instructions, convert switches to lookup tables, etc.
 //
 FunctionPass *createCFGSimplificationPass(
     unsigned Threshold = 1, bool ForwardSwitchCond = false,
-    bool ConvertSwitch = false, bool KeepLoops = true,
+    bool ConvertSwitch = false, bool KeepLoops = true, bool SinkCommon = false,
     std::function<bool(const Function &)> Ftor = nullptr);
 
 //===----------------------------------------------------------------------===//
 //
 // FlattenCFG - flatten CFG, reduce number of conditional branches by using
 // parallel-and and parallel-or mode, etc...
 //
 FunctionPass *createFlattenCFGPass();

include/llvm/Transforms/Scalar/SimplifyCFG.h

public:
   /// The default constructor sets the pass options to create canonical IR,
   /// rather than optimal IR. That is, by default we bypass transformations that
   /// are likely to improve performance but make analysis for other passes more
   /// difficult.
   SimplifyCFGPass()
       : SimplifyCFGPass(SimplifyCFGOptions()
                             .forwardSwitchCondToPhi(false)
                             .convertSwitchToLookupTable(false)
-                            .needCanonicalLoops(true)) {}
+                            .needCanonicalLoops(true)
+                            .sinkCommonInsts(false)) {}
 
 
   /// Construct a pass with optional optimizations.
   SimplifyCFGPass(const SimplifyCFGOptions &PassOptions);
 
   /// \brief Run the pass over the function.
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
 }
 
 #endif

include/llvm/Transforms/Utils/Local.h

 /// Options may change depending on the position in the optimization pipeline.
 /// For example, canonical form that includes switches and branches may later be
 /// replaced by lookup tables and selects.
 struct SimplifyCFGOptions {
   int BonusInstThreshold;
   bool ForwardSwitchCondToPhi;
   bool ConvertSwitchToLookupTable;
   bool NeedCanonicalLoop;
+  bool SinkCommonInsts;
   AssumptionCache *AC;
 
   SimplifyCFGOptions(unsigned BonusThreshold = 1,
                      bool ForwardSwitchCond = false,
                      bool SwitchToLookup = false, bool CanonicalLoops = true,
+                     bool SinkCommon = false,
                      AssumptionCache *AssumpCache = nullptr)
       : BonusInstThreshold(BonusThreshold),
         ForwardSwitchCondToPhi(ForwardSwitchCond),
         ConvertSwitchToLookupTable(SwitchToLookup),
-        NeedCanonicalLoop(CanonicalLoops), AC(AssumpCache) {}
+        NeedCanonicalLoop(CanonicalLoops),
+        SinkCommonInsts(SinkCommon),
+        AC(AssumpCache) {}
 
   // Support 'builder' pattern to set members by name at construction time.
   SimplifyCFGOptions &bonusInstThreshold(int I) {
     BonusInstThreshold = I;
     return *this;
   }
   SimplifyCFGOptions &forwardSwitchCondToPhi(bool B) {
     ForwardSwitchCondToPhi = B;
     return *this;
   }
   SimplifyCFGOptions &convertSwitchToLookupTable(bool B) {
     ConvertSwitchToLookupTable = B;
     return *this;
   }
   SimplifyCFGOptions &needCanonicalLoops(bool B) {
     NeedCanonicalLoop = B;
     return *this;
   }
+  SimplifyCFGOptions &sinkCommonInsts(bool B) {
+    SinkCommonInsts = B;
+    return *this;
+  }
   SimplifyCFGOptions &setAssumptionCache(AssumptionCache *Cache) {
     AC = Cache;
     return *this;
   }
 };
 
 //===----------------------------------------------------------------------===//
 //  Local constant propagation.

lib/Passes/PassBuilder.cpp

PassBuilder::buildFunctionSimplificationPipeline(OptimizationLevel Level,
   FPM.addPass(createFunctionToLoopPassAdaptor(LICMPass()));
 
   for (auto &C : ScalarOptimizerLateEPCallbacks)
     C(FPM, Level);
 
   // Finally, do an expensive DCE pass to catch all the dead code exposed by
   // the simplifications and basic cleanup after all the simplifications.
   FPM.addPass(ADCEPass());
-  FPM.addPass(SimplifyCFGPass());
+  // GVN has run, so allow more aggressive sinking and select formation.
+  FPM.addPass(SimplifyCFGPass(SimplifyCFGOptions().sinkCommonInsts(true)));
   FPM.addPass(InstCombinePass());
   invokePeepholeEPCallbacks(FPM, Level);
 
   return FPM;
 }
 
 void PassBuilder::addPGOInstrPasses(ModulePassManager &MPM, bool DebugLogging,
                                     PassBuilder::OptimizationLevel Level,
PassBuilder::buildModuleOptimizationPipeline(OptimizationLevel Level,
   OptimizePM.addPass(SLPVectorizerPass());
 
   // Cleanup after all of the vectorizers. Simplification passes like CVP and
   // GVN, loop transforms, and others have already run, so it's now better to
   // convert to more optimized IR using more aggressive simplify CFG options.
   OptimizePM.addPass(SimplifyCFGPass(SimplifyCFGOptions().
                                          forwardSwitchCondToPhi(true).
                                          convertSwitchToLookupTable(true).
-                                         needCanonicalLoops(false)));
+                                         needCanonicalLoops(false).
+                                         sinkCommonInsts(true)));
   OptimizePM.addPass(InstCombinePass());
 
   // Unroll small loops to hide loop backedge latency and saturate any parallel
   // execution resources of an out-of-order processor. We also then need to
   // clean up redundancies and loop invariant code.
   // FIXME: It would be really good to use a loop-integrated instruction
   // combiner for cleanup here so that the unrolling and LICM can be pipelined
   // across the loop nests.

lib/Target/AArch64/AArch64TargetMachine.cpp

void AArch64PassConfig::addIRPasses() {
   // Always expand atomic operations, we don't deal with atomicrmw or cmpxchg
   // ourselves.
   addPass(createAtomicExpandPass());
 
   // Cmpxchg instructions are often used with a subsequent comparison to
   // determine whether it succeeded. We can exploit existing control-flow in
   // ldrex/strex loops to simplify this, but it needs tidying up.
   if (TM->getOptLevel() != CodeGenOpt::None && EnableAtomicTidy)
-    addPass(createCFGSimplificationPass(1, true, true, false));
+    addPass(createCFGSimplificationPass(1, true, true, false, true));
 
   // Run LoopDataPrefetch
   //
   // Run this before LSR to remove the multiplies involved in computing the
   // pointer values N iterations ahead.
   if (TM->getOptLevel() != CodeGenOpt::None) {
     if (EnableLoopDataPrefetch)
       addPass(createLoopDataPrefetchPass());

lib/Target/ARM/ARMTargetMachine.cpp

void ARMPassConfig::addIRPasses() {
   else
     addPass(createAtomicExpandPass());
 
   // Cmpxchg instructions are often used with a subsequent comparison to
   // determine whether it succeeded. We can exploit existing control-flow in
   // ldrex/strex loops to simplify this, but it needs tidying up.
   if (TM->getOptLevel() != CodeGenOpt::None && EnableAtomicTidy)
     addPass(createCFGSimplificationPass(
-        1, false, false, true, [this](const Function &F) {
+        1, false, false, true, true, [this](const Function &F) {
           const auto &ST = this->TM->getSubtarget<ARMSubtarget>(F);
           return ST.hasAnyDataBarrier() && !ST.isThumb1Only();
         }));
 
   TargetPassConfig::addIRPasses();
 
   // Match interleaved memory accesses to ldN/stN intrinsics.
   if (TM->getOptLevel() != CodeGenOpt::None)

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addFunctionSimplificationPasses(
   addExtensionsToPM(EP_ScalarOptimizerLate, MPM);
 
   if (RerollLoops)
     MPM.add(createLoopRerollPass());
   if (!RunSLPAfterLoopVectorization && SLPVectorize)
     MPM.add(createSLPVectorizerPass()); // Vectorize parallel scalar chains.
 
   MPM.add(createAggressiveDCEPass());         // Delete dead instructions
-  MPM.add(createCFGSimplificationPass()); // Merge & remove BBs
+  // GVN has run, so allow more aggressive sinking and select formation.
+  MPM.add(createCFGSimplificationPass(1, false, false, true, true));
   // Clean up after everything.
   addInstructionCombiningPass(MPM);
   addExtensionsToPM(EP_Peephole, MPM);
 }
 
 void PassManagerBuilder::populateModulePassManager(
     legacy::PassManagerBase &MPM) {
   if (!PGOSampleUse.empty()) {
if (RunSLPAfterLoopVectorization && SLPVectorize) {
     if (OptLevel > 1 && ExtraVectorizerPasses) {
       MPM.add(createEarlyCSEPass());
     }
   }
 
   addExtensionsToPM(EP_Peephole, MPM);
   // Switches to lookup tables and other transforms that may not be considered
   // canonical by other IR passes.
-  MPM.add(createCFGSimplificationPass(1, true, true, false));
+  MPM.add(createCFGSimplificationPass(1, true, true, false, true));
   addInstructionCombiningPass(MPM);
 
   if (!DisableUnrollLoops) {
     MPM.add(createLoopUnrollPass(OptLevel));    // Unroll small loops
 
     // LoopUnroll may generate some redundency to cleanup.
     addInstructionCombiningPass(MPM);
 

lib/Transforms/Scalar/SimplifyCFGPass.cpp

 static cl::opt<bool> UserSwitchToLookup(
     "switch-to-lookup", cl::Hidden, cl::init(false),
     cl::desc("Convert switches to lookup tables (default = false)"));
 
 static cl::opt<bool> UserForwardSwitchCond(
     "forward-switch-cond", cl::Hidden, cl::init(false),
     cl::desc("Forward switch condition to phi ops (default = false)"));
 
+static cl::opt<bool> UserSinkCommonInsts(
+    "sink-common-insts", cl::Hidden, cl::init(false),
+    cl::desc("Sink common instructions (default = false)"));
+
+
 STATISTIC(NumSimpl, "Number of blocks simplified");
 
 /// If we have more than one empty (other than phi node) return blocks,
 /// merge them together to promote recursive block merging.
 static bool mergeEmptyReturnBlocks(Function &F) {
   bool Changed = false;
 
   BasicBlock *RetBlock = nullptr;
Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
                                        ? UserForwardSwitchCond
                                        : Opts.ForwardSwitchCondToPhi;
   Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
                                            ? UserSwitchToLookup
                                            : Opts.ConvertSwitchToLookupTable;
   Options.NeedCanonicalLoop = UserKeepLoops.getNumOccurrences()
                                   ? UserKeepLoops
                                   : Opts.NeedCanonicalLoop;
+  Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
+                                ? UserSinkCommonInsts
+                                : Opts.SinkCommonInsts;
 }
 
 PreservedAnalyses SimplifyCFGPass::run(Function &F,
                                        FunctionAnalysisManager &AM) {
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
   Options.AC = &AM.getResult<AssumptionAnalysis>(F);
   if (!simplifyFunctionCFG(F, TTI, Options))
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 namespace {
 struct CFGSimplifyPass : public FunctionPass {
   static char ID;
   SimplifyCFGOptions Options;
   std::function<bool(const Function &)> PredicateFtor;
 
   CFGSimplifyPass(unsigned Threshold = 1, bool ForwardSwitchCond = false,
                   bool ConvertSwitch = false, bool KeepLoops = true,
+                  bool SinkCommon = false,
                   std::function<bool(const Function &)> Ftor = nullptr)
       : FunctionPass(ID), PredicateFtor(std::move(Ftor)) {
 
     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
 
     // Check for command-line overrides of options for debug/customization.
     Options.BonusInstThreshold = UserBonusInstThreshold.getNumOccurrences()
                                     ? UserBonusInstThreshold
                                     : Threshold;
 
     Options.ForwardSwitchCondToPhi = UserForwardSwitchCond.getNumOccurrences()
                                          ? UserForwardSwitchCond
                                          : ForwardSwitchCond;
 
     Options.ConvertSwitchToLookupTable = UserSwitchToLookup.getNumOccurrences()
                                              ? UserSwitchToLookup
                                              : ConvertSwitch;
 
     Options.NeedCanonicalLoop =
         UserKeepLoops.getNumOccurrences() ? UserKeepLoops : KeepLoops;
+
+    Options.SinkCommonInsts = UserSinkCommonInsts.getNumOccurrences()
+                                  ? UserSinkCommonInsts
+                                  : SinkCommon;
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F)))
       return false;
 
     Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);

 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
                     false)
 
 // Public interface to the CFGSimplification pass
 FunctionPass *
 llvm::createCFGSimplificationPass(unsigned Threshold, bool ForwardSwitchCond,
                                   bool ConvertSwitch, bool KeepLoops,
+                                  bool SinkCommon,
                                   std::function<bool(const Function &)> Ftor) {
   return new CFGSimplifyPass(Threshold, ForwardSwitchCond, ConvertSwitch,
-                             KeepLoops, std::move(Ftor));
+                             KeepLoops, SinkCommon, std::move(Ftor));
 }

lib/Transforms/Utils/SimplifyCFG.cpp

static bool TryToMergeLandingPad(LandingPadInst *LPad, BranchInst *BI,
   return false;
 }
 
 bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI,
                                           IRBuilder<> &Builder) {
   BasicBlock *BB = BI->getParent();
   BasicBlock *Succ = BI->getSuccessor(0);
 
-  if (SinkCommon && SinkThenElseCodeToEnd(BI))
+  if (SinkCommon && Options.SinkCommonInsts && SinkThenElseCodeToEnd(BI))
     return true;
 
   // If the Terminator is the only non-phi instruction, simplify the block.
   // If LoopHeader is provided, check if the block or its successor is a loop
   // header. (This is for early invocations before loop simplify and
   // vectorization to keep canonical loop forms for nested loops. These blocks
   // can be eliminated when the pass is invoked later in the back-end.)
   bool NeedCanonicalLoop =

test/DebugInfo/Generic/simplifycfg_sink_last_inst.ll

-; RUN: opt -simplifycfg -S < %s | FileCheck %s
+; RUN: opt -simplifycfg -sink-common-insts -S < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Simplify CFG will try to sink the last instruction in a series of basic
 ; blocks, creating a "common" instruction in the successor block.  If the
 ; debug locations of the commoned instructions have different file/line
 ; numbers the debug location of the common instruction should not be set.

test/Transforms/PhaseOrdering/simplifycfg-options.ll

 define double @max_of_loads(double* %x, double* %y, i64 %i) {
 ; ALL-LABEL: @max_of_loads(
 ; ALL-NEXT:  entry:
 ; ALL-NEXT:    [[XI_PTR:%.*]] = getelementptr double, double* [[X:%.*]], i64 [[I:%.*]]
 ; ALL-NEXT:    [[YI_PTR:%.*]] = getelementptr double, double* [[Y:%.*]], i64 [[I]]
 ; ALL-NEXT:    [[XI:%.*]] = load double, double* [[XI_PTR]], align 8
 ; ALL-NEXT:    [[YI:%.*]] = load double, double* [[YI_PTR]], align 8
 ; ALL-NEXT:    [[CMP:%.*]] = fcmp ogt double [[XI]], [[YI]]
-; ALL-NEXT:    [[Y_SINK:%.*]] = select i1 [[CMP]], double* [[X]], double* [[Y]]
-; ALL-NEXT:    [[YI_PTR_AGAIN:%.*]] = getelementptr double, double* [[Y_SINK]], i64 [[I]]
-; ALL-NEXT:    [[YI_AGAIN:%.*]] = load double, double* [[YI_PTR_AGAIN]], align 8
-; ALL-NEXT:    ret double [[YI_AGAIN]]
+; ALL-NEXT:    [[XI_YI:%.*]] = select i1 [[CMP]], double [[XI]], double [[YI]]
+; ALL-NEXT:    ret double [[XI_YI]]
 ;
 entry:
   %xi_ptr = getelementptr double, double* %x, i64 %i
   %yi_ptr = getelementptr double, double* %y, i64 %i
   %xi = load double, double* %xi_ptr
   %yi = load double, double* %yi_ptr
   %cmp = fcmp ogt double %xi, %yi
   br i1 %cmp, label %if, label %else

test/Transforms/SimplifyCFG/no-md-sink.ll

-; RUN: opt < %s -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -simplifycfg -sink-common-insts -S | FileCheck %s
 
 define i1 @test1(i1 zeroext %flag, i8* %y) #0 {
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:
   %r = call i1 @llvm.type.test(i8* %y, metadata !0)
   br label %if.end

test/Transforms/SimplifyCFG/sink-common-code.ll

-; RUN: opt < %s -simplifycfg -S | FileCheck -enable-var-scope %s
+; RUN: opt < %s -simplifycfg -sink-common-insts -S | FileCheck -enable-var-scope %s
 
 define zeroext i1 @test1(i1 zeroext %flag, i32 %blksA, i32 %blksB, i32 %nblks) {
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 ; CHECK-LABEL: test1
 ; CHECK: add
 ; CHECK: select