aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar
AgeCommit message (Collapse)Author
2012-09-14Speculative change to try to fix older GCC versions that can't handleChandler Carruth
the injected class name of a dependent base class here. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163884 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-14Introduce a new SROA implementation.Chandler Carruth
This is essentially a ground up re-think of the SROA pass in LLVM. It was initially inspired by a few problems with the existing pass: - It is subject to the bane of my existence in optimizations: arbitrary thresholds. - It is overly conservative about which constructs can be split and promoted. - The vector value replacement aspect is separated from the splitting logic, missing many opportunities where splitting and vector value formation can work together. - The splitting is entirely based around the underlying type of the alloca, despite this type often having little to do with the reality of how that memory is used. This is especially prevelant with unions and base classes where we tail-pack derived members. - When splitting fails (often due to the thresholds), the vector value replacement (again because it is separate) can kick in for preposterous cases where we simply should have split the value. This results in forming i1024 and i2048 integer "bit vectors" that tremendously slow down subsequnet IR optimizations (due to large APInts) and impede the backend's lowering. The new design takes an approach that fundamentally is not susceptible to many of these problems. It is the result of a discusison between myself and Duncan Sands over IRC about how to premptively avoid these types of problems and how to do SROA in a more principled way. Since then, it has evolved and grown, but this remains an important aspect: it fixes real world problems with the SROA process today. First, the transform of SROA actually has little to do with replacement. It has more to do with splitting. The goal is to take an aggregate alloca and form a composition of scalar allocas which can replace it and will be most suitable to the eventual replacement by scalar SSA values. The actual replacement is performed by mem2reg (and in the future SSAUpdater). The splitting is divided into four phases. The first phase is an analysis of the uses of the alloca. This phase recursively walks uses, building up a dense datastructure representing the ranges of the alloca's memory actually used and checking for uses which inhibit any aspects of the transform such as the escape of a pointer. Once we have a mapping of the ranges of the alloca used by individual operations, we compute a partitioning of the used ranges. Some uses are inherently splittable (such as memcpy and memset), while scalar uses are not splittable. The goal is to build a partitioning that has the minimum number of splits while placing each unsplittable use in its own partition. Overlapping unsplittable uses belong to the same partition. This is the target split of the aggregate alloca, and it maximizes the number of scalar accesses which become accesses to their own alloca and candidates for promotion. Third, we re-walk the uses of the alloca and assign each specific memory access to all the partitions touched so that we have dense use-lists for each partition. Finally, we build a new, smaller alloca for each partition and rewrite each use of that partition to use the new alloca. During this phase the pass will also work very hard to transform uses of an alloca into a form suitable for promotion, including forming vector operations, speculating loads throguh PHI nodes and selects, etc. After splitting is complete, each newly refined alloca that is a candidate for promotion to a scalar SSA value is run through mem2reg. There are lots of reasonably detailed comments in the source code about the design and algorithms, and I'm going to be trying to improve them in subsequent commits to ensure this is well documented, as the new pass is in many ways more complex than the old one. Some of this is still a WIP, but the current state is reasonbly stable. It has passed bootstrap, the nightly test suite, and Duncan has run it successfully through the ACATS and DragonEgg test suites. That said, it remains behind a default-off flag until the last few pieces are in place, and full testing can be done. Specific areas I'm looking at next: - Improved comments and some code cleanup from reviews. - SSAUpdater and enabling this pass inside the CGSCC pass manager. - Some datastructure tuning and compile-time measurements. - More aggressive FCA splitting and vector formation. Many thanks to Duncan Sands for the thorough final review, as well as Benjamin Kramer for lots of review during the process of writing this pass, and Daniel Berlin for reviewing the data structures and algorithms and general theory of the pass. Also, several other people on IRC, over lunch tables, etc for lots of feedback and advice. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163883 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-13MemCpyOpt: When forming a memset from stores also take GEP constexprs into ↵Benjamin Kramer
account. This is common when storing to global variables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163809 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-13Fix Doxygen issues:Dmitri Gribenko
* wrap code blocks in \code ... \endcode; * refer to parameter names in paragraphs correctly (\arg is not what most people want -- it starts a new paragraph). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163790 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-12Detect overflow in the path count computation. rdar://12277446.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163739 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-12Release build: guard dump functions withManman Ren
"#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163344. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163679 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-09Move spaces to the right places. No functionality change.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163485 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-09DSE: Poking holes into a SetVector is expensive, avoid it if possible.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163480 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-06Release build: guard dump functions with "ifndef NDEBUG"Manman Ren
No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163344 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-06Update function names to conform to guidelines.Jim Grosbach
No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163279 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-04Make provenance checking conservative in cases whenDan Gohman
pointers-to-strong-pointers may be in play. These can lead to retains and releases happening in unstructured ways, foiling the optimizer. This fixes rdar://12150909. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163180 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-04Generic Bypass Slow DivPreston Gurd
- CodeGenPrepare pass for identifying div/rem ops - Backend specifies the type mapping using addBypassSlowDivType - Enabled only for Intel Atom with O2 32-bit -> 8-bit - Replace IDIV with instructions which test its value and use DIVB if the value is positive and less than 256. - In the case when the quotient and remainder of a divide are used a DIV and a REM instruction will be present in the IR. In the non-Atom case they are both lowered to IDIVs and CSE removes the redundant IDIV instruction, using the quotient and remainder from the first IDIV. However, due to this optimization CSE is not able to eliminate redundant IDIV instructions because they are located in different basic blocks. This is overcome by calculating both the quotient (DIV) and remainder (REM) in each basic block that is inserted by the optimization and reusing the result values when a subsequent DIV or REM instruction uses the same operands. - Test cases check for the presents of the optimization when calculating either the quotient, remainder, or both. Patch by Tyler Nowicki! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163150 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-04LICM may hoist an instruction with undefined behavior above a trap.Nadav Rotem
Scan the body of the loop and find instructions that may trap. Use this information when deciding if it is safe to hoist or sink instructions. Notice that we can optimize the search of instructions that may throw in the case of nested loops. rdar://11518836 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163132 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-02Not all targets have efficient ISel code generation for select instructions.Nadav Rotem
For example, the ARM target does not have efficient ISel handling for vector selects with scalar conditions. This patch adds a TLI hook which allows the different targets to report which selects are supported well and which selects should be converted to CF duting codegen prepare. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163093 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-02LoopRotation: Make the brute force DomTree update more brute force.Benjamin Kramer
We update until we hit a fixpoint. This is probably slow but also slightly simplifies the code. It should also fix the occasional invalid domtrees observed when building with expensive checking. I couldn't find a case where this had a measurable slowdown, but if someone finds a pathological case where it does we may have to find a cleverer way of updating dominators here. Thanks to Duncan for the test case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163091 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-01LoopRotation: Check some invariants of the dominator updating code.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163058 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-30LoopRotate: Also rotate loops with multiple exits.Benjamin Kramer
The old PHI updating code in loop-rotate was replaced with SSAUpdater a while ago, it has no problems with comples PHIs. What had to be fixed is detecting whether a loop was already rotated and updating dominators when multiple exits were present. This change increases overall code size a bit, mostly due to additional loop unrolling opportunities. Passes test-suite and selfhost with -verify-dom-info. Fixes PR7447. Thanks to Andy for the input on the domtree updating code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162912 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-29Make MemoryBuiltins aware of TargetLibraryInfo.Benjamin Kramer
This disables malloc-specific optimization when -fno-builtin (or -ffreestanding) is specified. This has been a problem for a long time but became more severe with the recent memory builtin improvements. Since the memory builtin functions are used everywhere, this required passing TLI in many places. This means that functions that now have an optional TLI argument, like RecursivelyDeleteTriviallyDeadFunctions, won't remove dead mallocs anymore if the TLI argument is missing. I've updated most passes to do the right thing. Fixes PR13694 and probably others. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162841 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-27Don't use for loops for code that is only intended to execute once. NoDan Gohman
intended functionality change. Thanks to Ahmed Charles for spotting it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162686 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-24GVN: Fix quadratic runtime on the number of switch cases.Benjamin Kramer
No intended behavior change. This was introduced in r162023. With the fixed algorithm a Release build of ARMInstPrinter.cpp goes from 16s to 10s on a 2011 MBP. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162559 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-22SimplifyLibCalls: Give all safely-shrinkable libcalls the same treatment.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162383 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-22Add a few float shrinking optimizations to SimplifyLibCalls. UnsafeChad Rosier
optimizations are guarded by the -enable-double-float-shrink LLVM option. Last bit of PR13574. Patch by Weiming Zhao <weimingz@codeaurora.org>. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162368 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-22Add a new helper function, AddOpt(F1, F1, Opt), as part of PR13574. NoChad Rosier
functional change intended. Patch by Weiming Zhao <weimingz@codeaurora.org>. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162363 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-21Don't bind a reference to a dereferenced null pointer (for return value of ↵Richard Smith
WeakVH::operator*). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162309 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-21Port the global copy optimization from the SROA pass to InstCombine.Chandler Carruth
This optimization is really just replacing allocas wholesale with globals, there is no scalarization. The underlying motivation for this patch is to simplify the SROA pass and focus it on splitting and promoting allocas. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162271 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-21revise debug output to avoid dangling pointerMichael Liao
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162256 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-18SimplifyLibcalls: Add fabs and trunc to the list of libcalls that are safe ↵Benjamin Kramer
to shrink from double to float. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162173 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-16Teach GVN to reason about edges dominating uses. This allows it to handle casesRafael Espindola
where some fact lake a=b dominates a use in a phi, but doesn't dominate the basic block itself. This feature could also be implemented by splitting critical edges, but at least with the current algorithm reasoning about the dominance directly is faster. The time for running "opt -O2" in the testcase in pr10584 is 1.003 times slower and on gcc as a single file it is 1.0007 times faster. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162023 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-15Remove dead flag.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161990 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-14Change greater than to greater than or equal so that an identical sized ↵Craig Topper
store to the same offset is treated as completing overwriting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161857 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-14During the CodeGenPrepare we often lower intrinsics (such as objsize)Nadav Rotem
and allow some optimizations to turn conditional branches into unconditional. This commit adds a simple control-flow optimization which merges two consecutive basic blocks which are connected by a single edge. This allows the codegen to operate on larger basic blocks. rdar://11973998 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161852 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-10Constify some basic blocks, no functionality change.Rafael Espindola
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161668 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-10Fix crash when when do lto on Bullet. Dynamic GEPs in SROA were incorrectly ↵Pete Cooper
being applied to all accesses to an alloca, not just the ones which read from the GEP. Thanks to Evan for reducing the test. rdar://11861001 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161654 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-08isAllocLikeFn is allowed to return true for functions which read memory; makeEli Friedman
sure we account for that correctly in DeadStoreElimination. Fixes a regression from r158919. PR13547. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161468 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-08Avoid recomputing the unique exit blocks and their insert points when doingDan Gohman
multiple scalar promotions on a single loop. This also has the effect of preserving the order of stores sunk out of loops, which is aesthetically pleasing, and it happens to fix the testcase in PR13542, though it doesn't fix the underlying problem. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161459 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-27Teach CodeGenPrep to look past bitcast when it's duplicating return instructionEvan Cheng
into predecessor blocks to enable tail call optimization. rdar://11958338 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160894 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-26do null checks for a few more Emit*() functions.Nuno Lopes
Thanks Eli for noticing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160787 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-26Stop reassociate from looking through expressions of arbitrary complexity. ThisDuncan Sands
is a temporary measure until my fix for PR13021 is ready. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160778 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-25make all Emit*() functions consult the TargetLibraryInfo information before ↵Nuno Lopes
creating a call to a library function. Update all clients to pass the TLI information around. Previous draft reviewed by Eli. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160733 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-24Clean whitespaces.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160668 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-23An objc_retain can serve as a may-use for a different pointer.Dan Gohman
rdar://11931823. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160637 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-23Suppress a warning.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160629 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-23Fix a typo (the the => the)Sylvestre Ledru
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160621 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-22Move the initialization of the bounds checking pass. The pass itselfChandler Carruth
moved earlier. This fixes some layering issues. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160611 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-20move the bounds checking pass to the instrumentation folder, where it ↵Nuno Lopes
belongs. I dunno why in the world I dropped it in the Scalar folder in the first place. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160587 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-20Fix assertion in jump threading (PR13405).Richard Osborne
GetBestDestForJumpOnUndef() assumes there is at least 1 successor, which isn't true if the block ends in an indirect branch with no successors. Fix this by bailing out earlier in this case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160546 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-18indvars: drive by heuristics fix.Andrew Trick
Minor oversight noticed by inspection. Sorry no unit test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160422 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-18indvars: Linear function test replace should avoid reusing undef.Andrew Trick
Fixes PR13371: indvars pass incorrectly substitutes 'undef' values. I do not like this fix. It's needed until/unless the meaning of undef changes. It attempts to be complete according to the IR spec, but I don't have much confidence in the implementation given the difficulty testing undefined behavior. Worse, this invalidates some of my hard-fought work on indvars and LSR to optimize pointer induction variables. It results benchmark regressions, which I'll track internally. On x86_64 no LTO I see: -3% huffbench -3% 400.perlbench -8% fhourstones My only suggestion for recovering is to change the meaning of undef. If we could trust an arbitrary instruction to produce a some real value that can be manipulated (e.g. incremented) according to non-undef rules, then this case could be easily handled with SCEV. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160421 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-17Reapply r160340. LSR: Limit CollectSubexprs.Andrew Trick
Speculatively fix crashes by code inspection. Can't reproduce them yet. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160344 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-17Revert "LSR: try not to blow up solving combinatorial problems brute force."Andrew Trick
Some units tests crashed on a different platform. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160341 91177308-0d34-0410-b5e6-96231b3b80d8