FailedChanges

Summary

  1. [PM/LoopUnswitch] Introduce a new, simpler loop unswitch pass. Currently, this pass only focuses on *trivial* loop unswitching. At that reduced problem it remains significantly better than the current loop unswitch: - Old pass is worse than cubic complexity. New pass is (I think) linear. - New pass is much simpler in its design by focusing on full unswitching. (See below for details on this). - New pass doesn't carry state for thresholds between pass iterations. - New pass doesn't carry state for correctness (both miscompile and infloop) between pass iterations. - New pass produces substantially better code after unswitching. - New pass can handle more trivial unswitch cases. - New pass doesn't recompute the dominator tree for the entire function and instead incrementally updates it. I've ported all of the trivial unswitching test cases from the old pass to the new one to make sure that major functionality isn't lost in the process. For several of the test cases I've worked to improve the precision and rigor of the CHECKs, but for many I've just updated them to handle the new IR produced. My initial motivation was the fact that the old pass carried state in very unreliable ways between pass iterations, and these mechansims were incompatible with the new pass manager. However, I discovered many more improvements to make along the way. This pass makes two very significant assumptions that enable most of these improvements: 1) Focus on *full* unswitching -- that is, completely removing whatever control flow construct is being unswitched from the loop. In the case of trivial unswitching, this means removing the trivial (exiting) edge. In non-trivial unswitching, this means removing the branch or switch itself. This is in opposition to *partial* unswitching where some part of the unswitched control flow remains in the loop. Partial unswitching only really applies to switches and to folded branches. These are very similar to full unrolling and partial unrolling. The full form is an effective canonicalization, the partial form needs a complex cost model, cannot be iterated, isn't canonicalizing, and should be a separate pass that runs very late (much like unrolling). 2) Leverage LLVM's Loop machinery to the fullest. The original unswitch dates from a time when a great deal of LLVM's loop infrastructure was missing, ineffective, and/or unreliable. As a consequence, a lot of complexity was added which we no longer need. With these two overarching principles, I think we can build a fast and effective unswitcher that fits in well in the new PM and in the canonicalization pipeline. Some of the remaining functionality around partial unswitching may not be relevant today (not many test cases or benchmarks I can find) but if they are I'd like to add support for them as a separate layer that runs very late in the pipeline. Purely to make reviewing and introducing this code more manageable, I've split this into first a trivial-unswitch-only pass and in the next patch I'll add support for full non-trivial unswitching against a *fixed* threshold, exactly like full unrolling. I even plan to re-use the unrolling thresholds, as these are incredibly similar cost tradeoffs: we're cloning a loop body in order to end up with simplified control flow. We should only do that when the total growth is reasonably small. One of the biggest changes with this pass compared to the previous one is that previously, each individual trivial exiting edge from a switch was unswitched separately as a branch. Now, we unswitch the entire switch at once, with cases going to the various destinations. This lets us unswitch multiple exiting edges in a single operation and also avoids numerous extremely bad behaviors, where we would introduce 1000s of branches to test for thousands of possible values, all of which would take the exact same exit path bypassing the loop. Now we will use a switch with 1000s of cases that can be efficiently lowered into a jumptable. This avoids relying on somehow forming a switch out of the branches or getting horrible code if that fails for any reason. Another significant change is that this pass actively updates the CFG based on unswitching. For trivial unswitching, this is actually very easy because of the definition of loop simplified form. Doing this makes the code coming out of loop unswitch dramatically more friendly. We still should run loop-simplifycfg (at the least) after this to clean up, but it will have to do a lot less work. Finally, this pass makes much fewer attempts to simplify instructions based on the unswitch. Something like loop-instsimplify, instcombine, or GVN can be used to do increasingly powerful simplifications based on the now dominating predicate. The old simplifications are things that something like loop-instsimplify should get today or a very, very basic loop-instcombine could get. Keeping that logic separate is a big simplifying technique. Most of the code in this pass that isn't in the old one has to do with achieving specific goals: - Updating the dominator tree as we go - Unswitching all cases in a switch in a single step. I think it is still shorter than just the trivial unswitching code in the old pass despite having this functionality. Differential Revision: https://reviews.llvm.org/D32409
  2. [GlobalOpt] Correctly update metadata when localizing a global. Just calling dropAllReferences leaves pointers to the ConstantExpr behind, so we would eventually crash with a null pointer dereference. Differential Revision: https://reviews.llvm.org/D32551
  3. Memory intrinsic value profile optimization: Improve debug output (NFC) Summary: Misc improvements to debug output. Fix a couple typos and also dump the value profile before we make any profitability checks. Reviewers: davidxl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32607
  4. Added an Importer test for in-class member initializers.
  5. Limit disabling of warnings emitted from r301571 by checking __GNUC__.
Revision 301576 by chandlerc:
[PM/LoopUnswitch] Introduce a new, simpler loop unswitch pass.

Currently, this pass only focuses on *trivial* loop unswitching. At that
reduced problem it remains significantly better than the current loop
unswitch:
- Old pass is worse than cubic complexity. New pass is (I think) linear.
- New pass is much simpler in its design by focusing on full unswitching. (See
  below for details on this).
- New pass doesn't carry state for thresholds between pass iterations.
- New pass doesn't carry state for correctness (both miscompile and
  infloop) between pass iterations.
- New pass produces substantially better code after unswitching.
- New pass can handle more trivial unswitch cases.
- New pass doesn't recompute the dominator tree for the entire function
  and instead incrementally updates it.

I've ported all of the trivial unswitching test cases from the old pass
to the new one to make sure that major functionality isn't lost in the
process. For several of the test cases I've worked to improve the
precision and rigor of the CHECKs, but for many I've just updated them
to handle the new IR produced.

My initial motivation was the fact that the old pass carried state in
very unreliable ways between pass iterations, and these mechansims were
incompatible with the new pass manager. However, I discovered many more
improvements to make along the way.

This pass makes two very significant assumptions that enable most of these
improvements:

1) Focus on *full* unswitching -- that is, completely removing whatever
   control flow construct is being unswitched from the loop. In the case
   of trivial unswitching, this means removing the trivial (exiting)
   edge. In non-trivial unswitching, this means removing the branch or
   switch itself. This is in opposition to *partial* unswitching where
   some part of the unswitched control flow remains in the loop. Partial
   unswitching only really applies to switches and to folded branches.
   These are very similar to full unrolling and partial unrolling. The
   full form is an effective canonicalization, the partial form needs
   a complex cost model, cannot be iterated, isn't canonicalizing, and
   should be a separate pass that runs very late (much like unrolling).

2) Leverage LLVM's Loop machinery to the fullest. The original unswitch
   dates from a time when a great deal of LLVM's loop infrastructure was
   missing, ineffective, and/or unreliable. As a consequence, a lot of
   complexity was added which we no longer need.

With these two overarching principles, I think we can build a fast and
effective unswitcher that fits in well in the new PM and in the
canonicalization pipeline. Some of the remaining functionality around
partial unswitching may not be relevant today (not many test cases or
benchmarks I can find) but if they are I'd like to add support for them
as a separate layer that runs very late in the pipeline.

Purely to make reviewing and introducing this code more manageable, I've
split this into first a trivial-unswitch-only pass and in the next patch
I'll add support for full non-trivial unswitching against a *fixed*
threshold, exactly like full unrolling. I even plan to re-use the
unrolling thresholds, as these are incredibly similar cost tradeoffs:
we're cloning a loop body in order to end up with simplified control
flow. We should only do that when the total growth is reasonably small.

One of the biggest changes with this pass compared to the previous one
is that previously, each individual trivial exiting edge from a switch
was unswitched separately as a branch. Now, we unswitch the entire
switch at once, with cases going to the various destinations. This lets
us unswitch multiple exiting edges in a single operation and also avoids
numerous extremely bad behaviors, where we would introduce 1000s of
branches to test for thousands of possible values, all of which would
take the exact same exit path bypassing the loop. Now we will use
a switch with 1000s of cases that can be efficiently lowered into
a jumptable. This avoids relying on somehow forming a switch out of the
branches or getting horrible code if that fails for any reason.

Another significant change is that this pass actively updates the CFG
based on unswitching. For trivial unswitching, this is actually very
easy because of the definition of loop simplified form. Doing this makes
the code coming out of loop unswitch dramatically more friendly. We
still should run loop-simplifycfg (at the least) after this to clean up,
but it will have to do a lot less work.

Finally, this pass makes much fewer attempts to simplify instructions
based on the unswitch. Something like loop-instsimplify, instcombine, or
GVN can be used to do increasingly powerful simplifications based on the
now dominating predicate. The old simplifications are things that
something like loop-instsimplify should get today or a very, very basic
loop-instcombine could get. Keeping that logic separate is a big
simplifying technique.

Most of the code in this pass that isn't in the old one has to do with
achieving specific goals:
- Updating the dominator tree as we go
- Unswitching all cases in a switch in a single step.

I think it is still shorter than just the trivial unswitching code in
the old pass despite having this functionality.

Differential Revision: https://reviews.llvm.org/D32409
Change TypePath in RepositoryPath in Workspace
The file was modified/llvm/trunk/include/llvm/InitializePasses.h (diff)llvm-revision.src/llvm/trunk/include/llvm/InitializePasses.h
The file was added/llvm/trunk/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.hllvm-revision.src/llvm/trunk/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h
The file was modified/llvm/trunk/lib/Passes/PassBuilder.cpp (diff)llvm-revision.src/llvm/trunk/lib/Passes/PassBuilder.cpp
The file was modified/llvm/trunk/lib/Passes/PassRegistry.def (diff)llvm-revision.src/llvm/trunk/lib/Passes/PassRegistry.def
The file was modified/llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp (diff)llvm-revision.src/llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp
The file was modified/llvm/trunk/lib/Transforms/Scalar/CMakeLists.txt (diff)llvm-revision.src/llvm/trunk/lib/Transforms/Scalar/CMakeLists.txt
The file was modified/llvm/trunk/lib/Transforms/Scalar/Scalar.cpp (diff)llvm-revision.src/llvm/trunk/lib/Transforms/Scalar/Scalar.cpp
The file was added/llvm/trunk/lib/Transforms/Scalar/SimpleLoopUnswitch.cppllvm-revision.src/llvm/trunk/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitchllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2006-06-13-SingleEntryPHI.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2006-06-13-SingleEntryPHI.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2006-06-27-DeadSwitchCase.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2006-06-27-DeadSwitchCase.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-05-09-Unreachable.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-05-09-Unreachable.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-05-09-tl.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-05-09-tl.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-07-12-ExitDomInfo.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-07-12-ExitDomInfo.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-07-13-DomInfo.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-07-13-DomInfo.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-07-18-DomInfo.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-07-18-DomInfo.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-08-01-Dom.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-08-01-Dom.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-08-01-LCSSA.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-08-01-LCSSA.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-10-04-DomFrontier.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2007-10-04-DomFrontier.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2008-06-02-DomInfo.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2008-06-02-DomInfo.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2008-06-17-DomFrontier.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2008-06-17-DomFrontier.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2010-11-18-LCSSA.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2010-11-18-LCSSA.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2011-06-02-CritSwitch.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2011-06-02-CritSwitch.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2011-09-26-EHCrash.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2011-09-26-EHCrash.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2012-04-02-IndirectBr.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2012-04-02-IndirectBr.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2012-04-30-LoopUnswitch-LPad-Crash.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2012-04-30-LoopUnswitch-LPad-Crash.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2012-05-20-Phi.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2012-05-20-Phi.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2015-09-18-Addrspace.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/2015-09-18-Addrspace.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/LIV-loop-condtion.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/LIV-loop-condtion.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/basictest.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/basictest.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/cleanuppad.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/cleanuppad.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/copy-metadata.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/copy-metadata.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/crash.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/crash.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/exponential-behavior.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/exponential-behavior.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/infinite-loop.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/infinite-loop.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/msan.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/msan.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/preserve-analyses.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/preserve-analyses.ll
The file was added/llvm/trunk/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.llllvm-revision.src/llvm/trunk/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll
Revision 301575 by efriedma:
[GlobalOpt] Correctly update metadata when localizing a global.

Just calling dropAllReferences leaves pointers to the ConstantExpr
behind, so we would eventually crash with a null pointer dereference.

Differential Revision: https://reviews.llvm.org/D32551
Change TypePath in RepositoryPath in Workspace
The file was modified/llvm/trunk/lib/Transforms/IPO/GlobalOpt.cpp (diff)llvm-revision.src/llvm/trunk/lib/Transforms/IPO/GlobalOpt.cpp
The file was added/llvm/trunk/test/Transforms/GlobalOpt/localize-constexpr-debuginfo.llllvm-revision.src/llvm/trunk/test/Transforms/GlobalOpt/localize-constexpr-debuginfo.ll
Revision 301574 by tejohnson:
Memory intrinsic value profile optimization: Improve debug output (NFC)

Summary:
Misc improvements to debug output. Fix a couple typos and also dump the
value profile before we make any profitability checks.

Reviewers: davidxl

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D32607
Change TypePath in RepositoryPath in Workspace
The file was modified/llvm/trunk/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp (diff)llvm-revision.src/llvm/trunk/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp
Revision 301573 by Sean Callanan:
Added an Importer test for in-class member initializers.
Change TypePath in RepositoryPath in Workspace
The file was added/cfe/trunk/test/Import/in-class-initializerllvm-revision.src/cfe/trunk/test/Import/in-class-initializer
The file was added/cfe/trunk/test/Import/in-class-initializer/Inputsllvm-revision.src/cfe/trunk/test/Import/in-class-initializer/Inputs
The file was added/cfe/trunk/test/Import/in-class-initializer/Inputs/S.cppllvm-revision.src/cfe/trunk/test/Import/in-class-initializer/Inputs/S.cpp
The file was added/cfe/trunk/test/Import/in-class-initializer/test.cppllvm-revision.src/cfe/trunk/test/Import/in-class-initializer/test.cpp
Revision 301572 by marsupial:
Limit disabling of warnings emitted from r301571 by checking __GNUC__.
Change TypePath in RepositoryPath in Workspace
The file was modified/llvm/trunk/unittests/Support/DynamicLibrary/PipSqueak.cxx (diff)llvm-revision.src/llvm/trunk/unittests/Support/DynamicLibrary/PipSqueak.cxx