summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
* [Reassociate] Canonicalize negative constants out of expressions.Chad Rosier2014-11-031-42/+101
| | | | | | | | | This gives CSE/GVN more options to eliminate duplicate expressions. This is a follow up patch to http://reviews.llvm.org/D4904. http://reviews.llvm.org/D5363 llvm-svn: 221171
* IR: MDNode => Value: Instruction::getAllMetadataOtherThanDebugLoc()Duncan P. N. Exon Smith2014-11-031-3/+2
| | | | | | | Change `Instruction::getAllMetadataOtherThanDebugLoc()` from a vector of `MDNode` to one of `Value`. Part of PR21433. llvm-svn: 221167
* Use ErrorOr for the ::create factory on instrumented and sample profilers.Diego Novillo2014-11-031-2/+3
| | | | | | | | | | | | | | | | | Summary: As discussed in http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20141027/242445.html, the creation of reader and writer instances is better done using ErrorOr. There are no functional changes, but several callers needed to be adjusted. Reviewers: bogner Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D6076 llvm-svn: 221120
* Use Alias Analysis to hoist 2 loads from diamond to the common predecessor ↵Elena Demikhovsky2014-11-021-47/+25
| | | | | | | | | | basic block. Alias Analysis allows to detect real barriers for load hoisting. Review in http://reviews.llvm.org/D5991 llvm-svn: 221091
* Fix Twine corruption problem with diagnostics.Diego Novillo2014-10-301-2/+1
| | | | | | | This fixes the autobuilders I broke with a recent patch. Thanks echristo and dblaikie for beating me with a clue stick. llvm-svn: 220918
* Add profile writing capabilities for sampling profiles.Diego Novillo2014-10-301-2/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch finishes up support for handling sampling profiles in both text and binary formats. The new binary format uses uleb128 encoding to represent numeric values. This makes profiles files about 25% smaller. The profile writer class can write profiles in the existing text and the new binary format. In subsequent patches, I will add the capability to read (and perhaps write) profiles in the gcov format used by GCC. Additionally, I will be adding support in llvm-profdata to manipulate sampling profiles. There was a bit of refactoring needed to separate some code that was in the reader files, but is actually common to both the reader and writer. The new test checks that reading the same profile encoded as text or raw, produces the same results. Reviewers: bogner, dexonsmith Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D6000 llvm-svn: 220915
* Do not simplifyLatch for loops where hoisting increments couldresult in ↵Yi Jiang2014-10-291-3/+30
| | | | | | extra live range interferance llvm-svn: 220872
* Transforms: reapply SVN r219899Saleem Abdulrasool2014-10-281-8/+2
| | | | | | | | | | | | | | | | This restores the commit from SVN r219899 with an additional change to ensure that the CodeGen is correct for the case that was identified as being incorrect (originally PR7272). In the case that during inlining we need to synthesize a value on the stack (i.e. for passing a value byval), then any function involving that alloca must be stripped of its tailness as the restriction that it does not access the parent's stack no longer holds. Unfortunately, a single alloca can cause a rippling effect through out the inlining as the value may be aliased or may be mutated through an escaped external call. As such, we simply track if an alloca has been introduced in the frame during inlining, and strip any tail calls. llvm-svn: 220811
* Reformat partially, where I touched for whitespace changes.NAKAMURA Takumi2014-10-281-6/+5
| | | | llvm-svn: 220773
* LoopRerollPass.cpp: Use range-based loop. NFC.NAKAMURA Takumi2014-10-281-11/+9
| | | | llvm-svn: 220772
* Untabify and whitespace cleanups.NAKAMURA Takumi2014-10-281-17/+16
| | | | llvm-svn: 220771
* LSR: Minor cleanup after Daniel's patch.Andrew Trick2014-10-251-4/+2
| | | | | | Combine the Inserted an Done sets into a Visited set. llvm-svn: 220623
* Fix LSR compile time.Andrew Trick2014-10-251-0/+5
| | | | | | | | | | | | This is a simple fix that brings the compilation time from 5min to 5s on a specific real-world example. It's a large chain of computation in a crypto routine (always a problem for SCEV). A unit test is not feasible and there would be no way to check it. The fix is just basic good practice for dealing with SCEVs, there's no risk of regression. Patch by Daniel Reynaud! llvm-svn: 220622
* [SeparateConstOffsetFromGEP] Fixed a bug related to unsigned moduloJingyue Wu2014-10-251-6/+6
| | | | | | | | | | | The dividend in "signed % unsigned" is treated as unsigned instead of signed, causing unexpected behavior such as -64 % (uint64_t)24 == 0. Added a regression test in split-gep.ll Patched by Hao Liu. llvm-svn: 220618
* [SeparateConstOffsetFromGEP] Fixed a bug in rebuilding OR expressionsJingyue Wu2014-10-251-2/+7
| | | | | | | | | | | | The two operands of the new OR expression should be NextInChain and TheOther instead of the two original operands. Added a regression test in split-gep.ll. Hao Liu reported this bug, and provded the test case and an initial patch. Thanks! llvm-svn: 220615
* Make getDISubprogram(const Function *F) available in LLVMTimur Iskhodzhanov2014-10-231-24/+1
| | | | | | Reviewed at http://reviews.llvm.org/D5950 llvm-svn: 220536
* Shorten auto iterators for function basic blocks.Diego Novillo2014-10-221-37/+36
| | | | | | | | Use consistent naming for basic block instances. No functional changes. llvm-svn: 220404
* Use auto iteration in lib/Transforms/Scalar/SampleProfile.cpp. No functional ↵Diego Novillo2014-10-221-18/+15
| | | | | | changes. llvm-svn: 220394
* Change error to warning when a profile cannot be found.Diego Novillo2014-10-221-1/+3
| | | | | | | | When the profile for a function cannot be applied, we use to emit an error. This seems extreme. The compiler can continue, it's just that the optimization opportunities won't include profile information. llvm-svn: 220386
* Support using sample profiles with partial debug info.Diego Novillo2014-10-221-12/+29
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When using a profile, we used to require the use -gmlt so that we could get access to the line locations. This is used to match line numbers in the input profile to the line numbers in the function's IR. But this is actually not necessary. The driver can provide source location tracking without the emission of debug information. In these cases, the annotation 'llvm.dbg.cu' is missing from the IR, but the actual line location annotations are still present. This patch adds a new way of looking for the start of the current function. Instead of looking through the compile units in llvm.dbg.cu, we can walk up the scope for the first instruction in the function with a debug loc. If that describes the function, we use it. Otherwise, we keep looking until we find one. If no such instruction is found, we then give up and produce an error. Reviewers: echristo, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D5887 llvm-svn: 220382
* Revert "Teach the load analysis to allow finding available values which ↵Hans Wennborg2014-10-211-4/+4
| | | | | | | | require" (r220277) This seems to have caused PR21330. llvm-svn: 220349
* Teach the load analysis to allow finding available values which requireChandler Carruth2014-10-211-4/+4
| | | | | | | | | | | | | | | | | | | | inttoptr or ptrtoint cast provided there is datalayout available. Eventually, the datalayout can just be required but in practice it will always be there today. To go with the ability to expose available values requiring a ptrtoint or inttoptr cast, helpers are added to perform one of these three casts. These smarts are necessary to finish canonicalizing loads and stores to the operational type requirements without regressing fundamental combines. I've added some test cases. These should actually improve as the load combining and store combining improves, but they may fundamentally be highlighting some missing combines for select in addition to exercising the specific added logic to load analysis. llvm-svn: 220277
* Introduce enum values for previously defined metadata types. (NFC)Philip Reames2014-10-211-1/+1
| | | | | | | | | | | Our metadata scheme lazily assigns IDs to string metadata, but we have a mechanism to preassign them as well. Using a preassigned ID is helpful since we get compile time type checking, and avoid some (minimal) string construction and comparison. This change adds enum value for three existing metadata types: + MD_nontemporal = 9, // "nontemporal" + MD_mem_parallel_loop_access = 10, // "llvm.mem.parallel_loop_access" + MD_nonnull = 11 // "nonnull" I went through an updated various uses as well. I made no attempt to get all uses; I focused on the ones which were easily grepable and easily to translate. For example, there were several items in LoopInfo.cpp I chose not to update. llvm-svn: 220248
* Fix a somewhat subtle pair of issues with JumpThreading I introduced inChandler Carruth2014-10-201-3/+6
| | | | | | | | | | | | | | | r220178. First, the creation routine doesn't insert prior to the terminator of the basic block provided, but really at the end of the basic block. Instead, get the terminator and insert before that. The next issue was that we need to ensure multiple PHI node entries for a single predecessor re-use the same cast instruction rather than creating new ones. All of the logic here was without tests previously. I've reduced and added a test case from the test suite that crashed without both of these fixes. llvm-svn: 220186
* Teach the load analysis driving core instcombine logic and other bits ofChandler Carruth2014-10-201-1/+10
| | | | | | | | | | | | | | | | | | | logic to look through pointer casts, making them trivially stronger in the face of loads and stores with intervening pointer casts. I've included a few test cases that demonstrate the kind of folding instcombine can do without pointer casts and then variations which obfuscate the logic through bitcasts. Without this patch, the variations all fail to optimize fully. This is more important now than it has been in the past as I've started moving the load canonicialization to more closely follow the value type requirements rather than the pointer type requirements and thus this needs to be prepared for more pointer casts. When I made the same change to stores several test cases regressed without logic along these lines so I wanted to systematically improve matters first. llvm-svn: 220178
* Fix a long-standing miscompile in the load analysis that was uncoveredChandler Carruth2014-10-191-1/+5
| | | | | | | | | | | | | | | | | | | by my refactoring of this code. The method isSafeToLoadUnconditionally assumes that the load will proceed with the preferred type alignment. Given that, it has to ensure that the alloca or global is at least that aligned. It has always done this historically when a datalayout is present, but has never checked it when the datalayout is absent. When I refactored the code in r220156, I exposed this path when datalayout was present and that turned the latent bug into a patent bug. This fixes the issue by just removing the special case which allows folding things without datalayout. This isn't worth the complexity of trying to tease apart when it is or isn't safe without actually knowing the preferred alignment. llvm-svn: 220161
* [SROA] Change how SROA does vector-based promotion of allocas to handleChandler Carruth2014-10-181-44/+128
| | | | | | | | | | | | | | | | | | | | | | | | | | | | cases where the alloca type, the load types, and the store types used all disagree. Previously, the only way that vector-based promotion occured was if the alloca type was a vector type. This was one of the *very* few remaining uses of the alloca's type to guide SROA/mem2reg left in LLVM. It turns out it was a bad idea. The alloca type can change very easily based on the mixture of types loaded and stored to that alloca. We shouldn't be relying on it as a signal for very much. Instead, the source of truth should be loads and stores. We should canonicalize the loads and stores as much as possible and then rely on them exclusively in SROA. When looking and loads and stores, we may find many different candidate vector types. This change will let SROA try all of them to find a vector type which is a viable way to promote the entire alloca to a vector register. With this change, it becomes possible to do better canonicalization and optimization of loads and stores without breaking SROA in random ways, and that should allow fixing a core source of performance loss in hot numerical loops such as those in Eigen. llvm-svn: 220116
* Revert "TRE: make TRE a bit more aggressive"Rafael Espindola2014-10-171-2/+8
| | | | | | | | | This reverts commit r219899. This also updates byval-tail-call.ll to make it clear what was breaking. Adding r219899 again will cause the load/store to disappear. llvm-svn: 220093
* [DSE] Remove no-data-layout-only type-based overlap checkingHal Finkel2014-10-171-8/+1
| | | | | | | | | | | | | | | | | DSE's overlap checking contained special logic, used only when no DataLayout was available, which inferred a complete overwrite when the pointee types were equal. This logic seems fine for regular loads/stores, but does not work for memcpy and friends. Instead of fixing this, I'm just removing it. Philosophically, transformations should not contain enhanced behavior used only when data layout is lacking (data layout should be strictly additive), and maintaining these rarely-tested code paths seems not worthwhile at this stage. Credit to Aliaksei Zasenka for the bug report and the diagnosis. The test case (slightly reduced from that provided by Aliaksei) replaces the original contents of test/Transforms/DeadStoreElimination/no-targetdata.ll -- a few other tests have been updated to have a data layout. llvm-svn: 220035
* [SROA] Switch the common variable name for the 'AllocaSlices' class toChandler Carruth2014-10-161-40/+42
| | | | | | | | | | | 'AS'. Using 'S' as this was a terrible idea. Arguably, 'AS' is not much better, but it at least follows the idea of using initialisms and removes active confusion about the AllocaSlices variable and a Slice variable. llvm-svn: 219963
* [SROA] More range-based cleanups to SROA, these brought to you byChandler Carruth2014-10-161-25/+12
| | | | | | | | | clang-modernize. I did have to clean up the variable types and whitespace a bit because the use of auto made the code much less readable here. llvm-svn: 219962
* [SROA] Switch a couple of overly complex iterator accessors to just beChandler Carruth2014-10-161-26/+10
| | | | | | | | | ArrayRef accessors. I think this even came up in review that this was over-engineered, and indeed it was. Time to un-build it. llvm-svn: 219958
* [SROA] Start more deeply moving SROA to use ranges rather than justChandler Carruth2014-10-161-45/+42
| | | | | | | | | | | | iterators. There are a ton of places where it essentially wants ranges rather than just iterators. This is just the first step that adds the core slice range typedefs and uses them in a couple of places. I still have to explicitly construct them because they've not been punched throughout the entire set of code. More range-based cleanups incoming. llvm-svn: 219955
* Allow call-slop optzn for destinations with a suitable dereferenceable attributeBjorn Steinbrink2014-10-161-14/+16
| | | | | | | | | | | | | | | Summary: Currently, call slot optimization requires that if the destination is an argument, the argument has the sret attribute. This is to ensure that the memory access won't trap. In addition to sret, we can also allow the optimization to happen for arguments that have the new dereferenceable attribute, which gives the same guarantee. Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D5832 llvm-svn: 219950
* TRE: make TRE a bit more aggressiveSaleem Abdulrasool2014-10-161-8/+2
| | | | | | | | | Make tail recursion elimination a bit more aggressive. This allows us to get tail recursion on functions that are just branches to a different function. The fact that the function takes a byval argument does not restrict it from being optimised into just a tail call. llvm-svn: 219899
* Fixing the build failure due to compiler warnings and unnecessary ↵Chris Bieneman2014-10-151-3/+2
| | | | | | disambiguation. llvm-svn: 219861
* Defining a new API for debug options that doesn't rely on static global ↵Chris Bieneman2014-10-151-9/+17
| | | | | | | | | | | | | | | | | | cl::opts. Summary: This is based on the discussions from the LLVMDev thread: http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-August/075886.html Reviewers: chandlerc Reviewed By: chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D5389 llvm-svn: 219854
* [SCEV] Add some asserts to the recently improved trip count computationChandler Carruth2014-10-111-7/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | routines and fix all of the bugs they expose. I hit a test case that crashed even without these asserts due to passing a non-exiting latch to the ExitingBlock parameter of the trip count computation machinery. However, when I add the nice asserts, it turns out we have plenty of coverage of these bugs, they just didn't manifest in crashers. The core problem seems to stem from an assumption that the latch *is* the exiting block. While this is often true, and somewhat the "normal" way to think about loops, it isn't necessarily true. The correct way to call the trip count routines in a *generic* fashion (that is, without a particular exit in mind) is to just use the loop's single exiting block if it has one. The trip count can't be computed generically unless it does. This works great for the loop vectorizer. The loop unroller actually *wants* to select the latch when it has to chose between multiple exits because for unrolling it is the latch trips that matter. But if this is the desire, it needs to explicitly guard for non-exiting latches and check for the generic trip count in that case. I've added the asserts, and added convenience APIs for querying the trip count generically that check for a single exit block. I've kept the APIs consistent between computing trip count and trip multiples. Thansk to Mark for the help debugging and tracking down the *right* fix here! llvm-svn: 219550
* [Reassociate] Don't canonicalize X - undef to X + (-undef).Chad Rosier2014-10-091-0/+4
| | | | | | | Phabricator Revision: http://reviews.llvm.org/D5674 PR21205 llvm-svn: 219434
* Give the Reassociate pass a bit more flexibility and autonomy when ↵Owen Anderson2014-10-051-2/+12
| | | | | | | | | | optimizing expressions. Particularly, it addresses cases where Reassociate breaks Subtracts but then fails to optimize combinations like I1 + -I2 where I1 and I2 have the same rank and are identical. Patch by Dmitri Shtilman. llvm-svn: 219092
* Remove unnecessary copying or replace it with moves in a bunch of places.Benjamin Kramer2014-10-041-2/+2
| | | | | | NFC. llvm-svn: 219061
* [BUG][INDVAR] Fix for PR21014: wrong SCEV operands commuting for ↵Zinovy Nis2014-10-021-3/+12
| | | | | | | | | | | | non-commutative instructions My commit rL216160 introduced a bug PR21014: IndVars widens code 'for (i = ; i < ...; i++) arr[ CONST - i]' into 'for (i = ; i < ...; i++) arr[ i - CONST]' thus inverting index expression. This patch fixes it. Thanks to Jörg Sonnenberger for pointing. Differential Revision: http://reviews.llvm.org/D5576 llvm-svn: 218867
* Move the complex address expression out of DIVariable and into an extraAdrian Prantl2014-10-012-5/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | argument of the llvm.dbg.declare/llvm.dbg.value intrinsics. Previously, DIVariable was a variable-length field that has an optional reference to a Metadata array consisting of a variable number of complex address expressions. In the case of OpPiece expressions this is wasting a lot of storage in IR, because when an aggregate type is, e.g., SROA'd into all of its n individual members, the IR will contain n copies of the DIVariable, all alike, only differing in the complex address reference at the end. By making the complex address into an extra argument of the dbg.value/dbg.declare intrinsics, all of the pieces can reference the same variable and the complex address expressions can be uniqued across the CU, too. Down the road, this will allow us to move other flags, such as "indirection" out of the DIVariable, too. The new intrinsics look like this: declare void @llvm.dbg.declare(metadata %storage, metadata %var, metadata %expr) declare void @llvm.dbg.value(metadata %storage, i64 %offset, metadata %var, metadata %expr) This patch adds a new LLVM-local tag to DIExpressions, so we can detect and pretty-print DIExpression metadata nodes. What this patch doesn't do: This patch does not touch the "Indirect" field in DIVariable; but moving that into the expression would be a natural next step. http://reviews.llvm.org/D4919 rdar://problem/17994491 Thanks to dblaikie and dexonsmith for reviewing this patch! Note: I accidentally committed a bogus older version of this patch previously. llvm-svn: 218787
* Revert r218778 while investigating buldbot breakage.Adrian Prantl2014-10-012-5/+5
| | | | | | "Move the complex address expression out of DIVariable and into an extra" llvm-svn: 218782
* Move the complex address expression out of DIVariable and into an extraAdrian Prantl2014-10-012-5/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | argument of the llvm.dbg.declare/llvm.dbg.value intrinsics. Previously, DIVariable was a variable-length field that has an optional reference to a Metadata array consisting of a variable number of complex address expressions. In the case of OpPiece expressions this is wasting a lot of storage in IR, because when an aggregate type is, e.g., SROA'd into all of its n individual members, the IR will contain n copies of the DIVariable, all alike, only differing in the complex address reference at the end. By making the complex address into an extra argument of the dbg.value/dbg.declare intrinsics, all of the pieces can reference the same variable and the complex address expressions can be uniqued across the CU, too. Down the road, this will allow us to move other flags, such as "indirection" out of the DIVariable, too. The new intrinsics look like this: declare void @llvm.dbg.declare(metadata %storage, metadata %var, metadata %expr) declare void @llvm.dbg.value(metadata %storage, i64 %offset, metadata %var, metadata %expr) This patch adds a new LLVM-local tag to DIExpressions, so we can detect and pretty-print DIExpression metadata nodes. What this patch doesn't do: This patch does not touch the "Indirect" field in DIVariable; but moving that into the expression would be a natural next step. http://reviews.llvm.org/D4919 rdar://problem/17994491 Thanks to dblaikie and dexonsmith for reviewing this patch! llvm-svn: 218778
* [SimplifyCFG] threshold for folding branches with common destinationJingyue Wu2014-09-301-7/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch adds a threshold that controls the number of bonus instructions allowed for folding branches with common destination. The original code allows at most one bonus instruction. With this patch, users can customize the threshold to allow multiple bonus instructions. The default threshold is still 1, so that the code behaves the same as before when users do not specify this threshold. The motivation of this change is that tuning this threshold significantly (up to 25%) improves the performance of some CUDA programs in our internal code base. In general, branch instructions are very expensive for GPU programs. Therefore, it is sometimes worth trading more arithmetic computation for a more straightened control flow. Here's a reduced example: __global__ void foo(int a, int b, int c, int d, int e, int n, const int *input, int *output) { int sum = 0; for (int i = 0; i < n; ++i) sum += (((i ^ a) > b) && (((i | c ) ^ d) > e)) ? 0 : input[i]; *output = sum; } The select statement in the loop body translates to two branch instructions "if ((i ^ a) > b)" and "if (((i | c) ^ d) > e)" which share a common destination. With the default threshold, SimplifyCFG is unable to fold them, because computing the condition of the second branch "(i | c) ^ d > e" requires two bonus instructions. With the threshold increased, SimplifyCFG can fold the two branches so that the loop body contains only one branch, making the code conceptually look like: sum += (((i ^ a) > b) & (((i | c ) ^ d) > e)) ? 0 : input[i]; Increasing the threshold significantly improves the performance of this particular example. In the configuration where both conditions are guaranteed to be true, increasing the threshold from 1 to 2 improves the performance by 18.24%. Even in the configuration where the first condition is false and the second condition is true, which favors shortcuts, increasing the threshold from 1 to 2 still improves the performance by 4.35%. We are still looking for a good threshold and maybe a better cost model than just counting the number of bonus instructions. However, according to the above numbers, we think it is at least worth adding a threshold to enable more experiments and tuning. Let me know what you think. Thanks! Test Plan: Added one test case to check the threshold is in effect Reviewers: nadav, eliben, meheff, resistor, hfinkel Reviewed By: hfinkel Subscribers: hfinkel, llvm-commits Differential Revision: http://reviews.llvm.org/D5529 llvm-svn: 218711
* [IndVarSimplify] Widen loop unsigned compares.Chad Rosier2014-09-301-6/+2
| | | | | | | This patch extends r217953 to handle unsigned comparison. Phabricator revision: http://reviews.llvm.org/D5526 llvm-svn: 218659
* [IndVar] Don't widen loop compare unless IV user is sign extended.Chad Rosier2014-09-261-2/+6
| | | | | | PR21030 llvm-svn: 218539
* Fix assertion in LICM doFinalization()David Peixotto2014-09-241-0/+13
| | | | | | | | | | | | | | | | The doFinalization method checks that the LoopToAliasSetMap is empty. LICM populates that map as it runs through the loop nest, deleting the entries for child loops as it goes. However, if a child loop is deleted by another pass (e.g. unrolling) then the loop will never be deleted from the map because LICM walks the loop nest to find entries it can delete. The fix is to delete the loop from the map and free the alias set when the loop is deleted from the loop nest. Differential Revision: http://reviews.llvm.org/D5305 llvm-svn: 218387
* Allow BB duplication threshold to be adjusted through JumpThreading's ctorMichael Liao2014-09-241-7/+10
| | | | | | | - BB duplication may not be desired on targets where there is no or small branch penalty and code duplication needs restrict control. llvm-svn: 218375
OpenPOWER on IntegriCloud