summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils
Commit message (Collapse)AuthorAgeFilesLines
* Simplify code. No functionality change.Benjamin Kramer2014-09-131-15/+3
| | | | llvm-svn: 217726
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-078-51/+77
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change, which allows @llvm.assume to be used from within computeKnownBits (and other associated functions in ValueTracking), adds some (optional) parameters to computeKnownBits and friends. These functions now (optionally) take a "context" instruction pointer, an AssumptionTracker pointer, and also a DomTree pointer, and most of the changes are just to pass this new information when it is easily available from InstSimplify, InstCombine, etc. As explained below, the significant conceptual change is that known properties of a value might depend on the control-flow location of the use (because we care that the @llvm.assume dominates the use because assumptions have control-flow dependencies). This means that, when we ask if bits are known in a value, we might get different answers for different uses. The significant changes are all in ValueTracking. Two main changes: First, as with the rest of the code, new parameters need to be passed around. To make this easier, I grouped them into a structure, and I made internal static versions of the relevant functions that take this structure as a parameter. The new code does as you might expect, it looks for @llvm.assume calls that make use of the value we're trying to learn something about (often indirectly), attempts to pattern match that expression, and uses the result if successful. By making use of the AssumptionTracker, the process of finding @llvm.assume calls is not expensive. Part of the structure being passed around inside ValueTracking is a set of already-considered @llvm.assume calls. This is to prevent a query using, for example, the assume(a == b), to recurse on itself. The context and DT params are used to find applicable assumptions. An assumption needs to dominate the context instruction, or come after it deterministically. In this latter case we only handle the specific case where both the assumption and the context instruction are in the same block, and we need to exclude assumptions from being used to simplify their own ephemeral values (those which contribute only to the assumption) because otherwise the assumption would prove its feeding comparison trivial and would be removed. This commit adds the plumbing and the logic for a simple masked-bit propagation (just enough to write a regression test). Future commits add more patterns (and, correspondingly, more regression tests). llvm-svn: 217342
* Add an Assumption-Tracking PassHal Finkel2014-09-072-1/+13
| | | | | | | | | | | | | | | | | | | | | | | | This adds an immutable pass, AssumptionTracker, which keeps a cache of @llvm.assume call instructions within a module. It uses callback value handles to keep stale functions and intrinsics out of the map, and it relies on any code that creates new @llvm.assume calls to notify it of the new instructions. The benefit is that code needing to find @llvm.assume intrinsics can do so directly, without scanning the function, thus allowing the cost of @llvm.assume handling to be negligible when none are present. The current design is intended to be lightweight. We don't keep track of anything until we need a list of assumptions in some function. The first time this happens, we scan the function. After that, we add/remove @llvm.assume calls from the cache in response to registration calls and ValueHandle callbacks. There are no new direct test cases for this pass, but because it calls it validation function upon module finalization, we'll pick up detectable inconsistencies from the other tests that touch @llvm.assume calls. This pass will be used by follow-up commits that make use of @llvm.assume. llvm-svn: 217334
* Enable noalias metadata by default and swap the order of the SLP and Loop ↵James Molloy2014-09-041-1/+1
| | | | | | | | vectorizers by default. After some time maturing, hopefully the flags themselves will be removed. llvm-svn: 217144
* Feed AA to the inliner and use AA->getModRefBehavior in AddAliasScopeMetadataHal Finkel2014-09-011-11/+17
| | | | | | | | | | | | This feeds AA through the IFI structure into the inliner so that AddAliasScopeMetadata can use AA->getModRefBehavior to figure out which functions only access their arguments (instead of just hard-coding some knowledge of memory intrinsics). Most of the information is only available from BasicAA; this is important for preserving alias scoping information for target-specific intrinsics when doing the noalias parameter attribute to metadata conversion. llvm-svn: 216866
* Fix AddAliasScopeMetadata again - alias.scope must be a complete descriptionHal Finkel2014-09-011-15/+37
| | | | | | | | | | | | | | | | | | | | | | | I thought that I had fixed this problem in r216818, but I did not do a very good job. The underlying issue is that when we add alias.scope metadata we are asserting that this metadata completely describes the aliasing relationships within the current aliasing scope domain, and so in the context of translating noalias argument attributes, the pointers must all be based on noalias arguments (as underlying objects) and have no other kind of underlying object. In r216818 excluding appropriate accesses from getting alias.scope metadata is done by looking for underlying objects that are not identified function-local objects -- but that's wrong because allocas, etc. are also function-local objects and we need to explicitly check that all underlying objects are the noalias arguments for which we're adding metadata aliasing scopes. This fixes the underlying-object check for adding alias.scope metadata, and does some refactoring of the related capture-checking eligibility logic (and adds more comments; hopefully making everything a bit clearer). Fixes self-hosting on x86_64 with -mllvm -enable-noalias-to-md-conversion (the feature is still disabled by default). llvm-svn: 216863
* Fix AddAliasScopeMetadata to not add scopes when deriving from unknown pointersHal Finkel2014-08-301-25/+51
| | | | | | | | | | | | | | | | | | | | | | | The previous implementation of AddAliasScopeMetadata, which adds noalias metadata to preserve noalias parameter attribute information when inlining had a flaw: it would add alias.scope metadata to accesses which might have been derived from pointers other than noalias function parameters. This was incorrect because even some access known not to alias with all noalias function parameters could easily alias with an access derived from some other pointer. Instead, when deriving from some unknown pointer, we cannot add alias.scope metadata at all. This fixes a miscompile of the test-suite's tramp3d-v4. Furthermore, we cannot add alias.scope to functions unless we know they access only argument-derived pointers (currently, we know this only for memory intrinsics). Also, we fix a theoretical problem with using the NoCapture attribute to skip the capture check. This is incorrect (as explained in the comment added), but would not matter in any code generated by Clang because we get only inferred nocapture attributes in Clang-generated IR. This functionality is not yet enabled by default. llvm-svn: 216818
* Fix a typo in AddAliasScopeMetadataHal Finkel2014-08-291-1/+1
| | | | llvm-svn: 216741
* Simplify creation of a bunch of ArrayRefs by using None, makeArrayRef or ↵Craig Topper2014-08-273-16/+8
| | | | | | just letting them be implicitly created. llvm-svn: 216525
* Remove dangling initializers in GlobalDCEBruno Cardoso Lopes2014-08-251-0/+3
| | | | | | | | | | | | | | GlobalDCE deletes global vars and updates their initializers to nullptr while leaving underlying constants to be cleaned up later by its uses. The clean up may never happen, fix this by forcing it every time it's safe to destroy constants. Final patch by Rafael Espindola http://reviews.llvm.org/D4931 <rdar://problem/17523868> llvm-svn: 216390
* Use range based for loops to avoid needing to re-mention SmallPtrSet size.Craig Topper2014-08-243-15/+10
| | | | llvm-svn: 216351
* Use DILexicalBlockFile, rather than DILexicalBlock, to track discriminator ↵David Blaikie2014-08-211-4/+2
| | | | | | | | | | | | | | | changes to ensure discriminator changes don't introduce new DWARF DW_TAG_lexical_blocks. Somewhat unnoticed in the original implementation of discriminators, but it could cause instructions to end up in new, small, DW_TAG_lexical_blocks due to the use of DILexicalBlock to track discriminator changes. Instead, use DILexicalBlockFile which we already use to track file changes without introducing new scopes, so it works well to track discriminator changes in the same way. llvm-svn: 216239
* Repace SmallPtrSet with SmallPtrSetImpl in function arguments to avoid ↵Craig Topper2014-08-216-10/+10
| | | | | | needing to mention the size. llvm-svn: 216158
* Revert "Repace SmallPtrSet with SmallPtrSetImpl in function arguments to ↵Craig Topper2014-08-186-10/+10
| | | | | | | | avoid needing to mention the size." Getting a weird buildbot failure that I need to investigate. llvm-svn: 215870
* Repace SmallPtrSet with SmallPtrSetImpl in function arguments to avoid ↵Craig Topper2014-08-176-10/+10
| | | | | | needing to mention the size. llvm-svn: 215868
* Introduce a helper to combine instruction metadata.Rafael Espindola2014-08-152-0/+44
| | | | | | | | | Replace the old code in GVN and BBVectorize with it. Update SimplifyCFG to use it. Patch by Björn Steinbrink! llvm-svn: 215723
* Copy noalias metadata from call sites to inlined instructionsHal Finkel2014-08-141-4/+28
| | | | | | | | | | | | | | When a call site with noalias metadata is inlined, that metadata can be propagated directly to the inlined instructions (only those that might access memory because it is not useful on the others). Prior to inlining, the noalias metadata could express that a call would not alias with some other memory access, which implies that no instruction within that called function would alias. By propagating the metadata to the inlined instructions, we preserve that knowledge. This should complete the enhancements requested in PR20500. llvm-svn: 215676
* Add noalias metadata for general calls (not just memory intrinsics) during ↵Hal Finkel2014-08-141-7/+18
| | | | | | | | | | | | | | | | inlining When preserving noalias function parameter attributes by adding noalias metadata in the inliner, we should do this for general function calls (not just memory intrinsics). The logic is very similar to what already existed (except that we want to add this metadata even for functions taking no relevant parameters). This metadata can be used by ModRef queries in the caller after inlining. This addresses the first part of PR20500. Adding noalias metadata during inlining is still turned off by default. llvm-svn: 215657
* utils: Fix segfault in flattencfgJan Vesely2014-08-131-4/+5
| | | | | | | | | | | | | | v2: continue iterating through the rest of the bb use for loop v3: initialize FlattenCFG pass in ScalarOps add test v4: split off initializing flattencfg to a separate patch add comment Signed-off-by: Jan Vesely <jan.vesely@rutgers.edu> llvm-svn: 215574
* Move helper for getting a terminating musttail call to BasicBlockReid Kleckner2014-08-121-30/+5
| | | | | | | | | | | No functional change. To be used in future commits that need to look for such instructions. Reviewed By: rafael Differential Revision: http://reviews.llvm.org/D4504 llvm-svn: 215413
* [SimplifyCFG] fix accessing deleted PHINodes in switch-to-table conversion.Manman Ren2014-08-021-1/+4
| | | | | | | | | When we have a covered lookup table, make sure we don't delete PHINodes that are cached in PHIs. rdar://17887153 llvm-svn: 214642
* SimplifyCFG: Avoid miscompilations due to removed lifetime intrinsics.Rafael Espindola2014-07-301-1/+1
| | | | | | | | | | | The lifetime intrinsics need some work in order to make it clear which optimizations are or are not valid. For now dropping this optimization avoids a miscompilation. Patch by Björn Steinbrink. llvm-svn: 214336
* Add @llvm.assume, lowering, and some basic propertiesHal Finkel2014-07-251-0/+28
| | | | | | | | | | | | | | | | | This is the first commit in a series that add an @llvm.assume intrinsic which can be used to provide the optimizer with a condition it may assume to be true (when the control flow would hit the intrinsic call). Some basic properties are added here: - llvm.invariant(true) is dead. - llvm.invariant(false) is unreachable (this directly corresponds to the documented behavior of MSVC's __assume(0)), so is llvm.invariant(undef). The intrinsic is tagged as writing arbitrarily, in order to maintain control dependencies. BasicAA has been updated, however, to return NoModRef for any particular location-based query so that we don't unnecessarily block code motion. llvm-svn: 213973
* Convert noalias parameter attributes into noalias metadata during inliningHal Finkel2014-07-251-0/+174
| | | | | | | | | | | | | | | | | | | | | | | This functionality is currently turned off by default. Part of the motivation for introducing scoped-noalias metadata is to enable the preservation of noalias parameter attribute information after inlining. Sometimes this can be inferred from the code in the caller after inlining, but often we simply lose valuable information. The overall process if fairly simple: 1. Create a new unqiue scope domain. 2. For each (used) noalias parameter, create a new alias scope. 3. For each pointer, collect the underlying objects. Add a noalias scope for each noalias parameter from which we're not derived (and has not been captured prior to that point). 4. Add an alias.scope for each noalias parameter from which we might be derived (or has been captured before that point). Note that the capture checks apply only if one of the underlying objects is not an identified function-local object. llvm-svn: 213949
* Feedback from Hans on r213815. No functionaility change.Manman Ren2014-07-241-10/+11
| | | | llvm-svn: 213895
* Add scoped-noalias metadataHal Finkel2014-07-241-0/+101
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit adds scoped noalias metadata. The primary motivations for this feature are: 1. To preserve noalias function attribute information when inlining 2. To provide the ability to model block-scope C99 restrict pointers Neither of these two abilities are added here, only the necessary infrastructure. In fact, there should be no change to existing functionality, only the addition of new features. The logic that converts noalias function parameters into this metadata during inlining will come in a follow-up commit. What is added here is the ability to generally specify noalias memory-access sets. Regarding the metadata, alias-analysis scopes are defined similar to TBAA nodes: !scope0 = metadata !{ metadata !"scope of foo()" } !scope1 = metadata !{ metadata !"scope 1", metadata !scope0 } !scope2 = metadata !{ metadata !"scope 2", metadata !scope0 } !scope3 = metadata !{ metadata !"scope 2.1", metadata !scope2 } !scope4 = metadata !{ metadata !"scope 2.2", metadata !scope2 } Loads and stores can be tagged with an alias-analysis scope, and also, with a noalias tag for a specific scope: ... = load %ptr1, !alias.scope !{ !scope1 } ... = load %ptr2, !alias.scope !{ !scope1, !scope2 }, !noalias !{ !scope1 } When evaluating an aliasing query, if one of the instructions is associated with an alias.scope id that is identical to the noalias scope associated with the other instruction, or is a descendant (in the scope hierarchy) of the noalias scope associated with the other instruction, then the two memory accesses are assumed not to alias. Note that is the first element of the scope metadata is a string, then it can be combined accross functions and translation units. The string can be replaced by a self-reference to create globally unqiue scope identifiers. [Note: This overview is slightly stylized, since the metadata nodes really need to just be numbers (!0 instead of !scope0), and the scope lists are also global unnamed metadata.] Existing noalias metadata in a callee is "cloned" for use by the inlined code. This is necessary because the aliasing scopes are unique to each call site (because of possible control dependencies on the aliasing properties). For example, consider a function: foo(noalias a, noalias b) { *a = *b; } that gets inlined into bar() { ... if (...) foo(a1, b1); ... if (...) foo(a2, b2); } -- now just because we know that a1 does not alias with b1 at the first call site, and a2 does not alias with b2 at the second call site, we cannot let inlining these functons have the metadata imply that a1 does not alias with b2. llvm-svn: 213864
* Fixing an MSVC conversion warning about implicitly converting the shift ↵Aaron Ballman2014-07-241-1/+1
| | | | | | results to 64-bits. No functional change intended. llvm-svn: 213863
* SimplifyCFG: fix a bug in switch to table conversionManman Ren2014-07-231-4/+13
| | | | | | | | | | | | | | | | | | | We use gep to access the global array "switch.table", and the table index should be treated as unsigned. When the highest bit is 1, this commit zero-extends the index to an integer type with larger size. For a switch on i2, we used to generate: %switch.tableidx = sub i2 %0, -2 getelementptr inbounds [4 x i64]* @switch.table, i32 0, i2 %switch.tableidx It is incorrect when %switch.tableidx is 2 or 3. The fix is to generate %switch.tableidx = sub i2 %0, -2 %switch.tableidx.zext = zext i2 %switch.tableidx to i3 getelementptr inbounds [4 x i64]* @switch.table, i32 0, i3 %switch.tableidx.zext rdar://17735071 llvm-svn: 213815
* Revert "[C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) ↵Duncan P. N. Exon Smith2014-07-2111-64/+94
| | | | | | | | | iterator ranges." This reverts commit r213474 (and r213475), which causes a miscompile on a stage2 LTO build. I'll reply on the list in a moment. llvm-svn: 213562
* [C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) iterator ↵Manuel Jacob2014-07-2011-94/+64
| | | | | | | | | | | | | | | | | | ranges. Summary: This patch introduces two new iterator ranges and updates existing code to use it. No functional change intended. Test Plan: All tests (make check-all) still pass. Reviewers: dblaikie Reviewed By: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4481 llvm-svn: 213474
* Give SplitBlockAndInsertIfThen the ability to update a domtree.Peter Collingbourne2014-07-151-1/+16
| | | | llvm-svn: 213045
* Fix an issue with the MergeBasicBlockIntoOnlyPred() helper function where it didOwen Anderson2014-07-121-0/+5
| | | | | | | | | | not properly handle the case where the predecessor block was the entry block to the function. The only in-tree client of this is JumpThreading, which worked around the issue in its own code. This patch moves the solution into the helper so that JumpThreading (and other clients) do not have to replicate the same fix everywhere. llvm-svn: 212875
* Fixup PHIs in LowerSwitch when a Leaf node is not emitted.Marcello Maggioni2014-07-111-10/+31
| | | | | | | | This commit fixes bug http://llvm.org/bugs/show_bug.cgi?id=20103. Thanks to Qwertyuiop for the report and the proposed fix. llvm-svn: 212802
* Partially fix PR20058: reduce compile time for loop unrolling with very high ↵Mark Heffernan2014-07-101-7/+17
| | | | | | count by reducing calls to SE->forgetLoop llvm-svn: 212782
* Feeding isSafeToSpeculativelyExecute its DataLayout pointerHal Finkel2014-07-103-31/+43
| | | | | | | | | | | | | | isSafeToSpeculativelyExecute can optionally take a DataLayout pointer. In the past, this was mainly used to make better decisions regarding divisions known not to trap, and so was not all that important for users concerned with "cheap" instructions. However, now it also helps look through bitcasts for dereferencable loads, and will also be important if/when we add a dereferencable pointer attribute. This is some initial work to feed a DataLayout pointer through to callers of isSafeToSpeculativelyExecute, generally where one was already available. llvm-svn: 212720
* Decouple llvm::SpecialCaseList text representation and its LLVM IR semantics.Alexey Samsonov2014-07-092-223/+0
| | | | | | | | | | | | | | | | Turn llvm::SpecialCaseList into a simple class that parses text files in a specified format and knows nothing about LLVM IR. Move this class into LLVMSupport library. Implement two users of this class: * DFSanABIList in DFSan instrumentation pass. * SanitizerBlacklist in Clang CodeGen library. The latter will be modified to use actual source-level information from frontend (source file names) instead of unstable LLVM IR things (LLVM Module identifier). Remove dependency edge from ClangCodeGen/ClangDriver to LLVMTransformUtils. No functionality change. llvm-svn: 212643
* Fix some Twine locals.Benjamin Kramer2014-07-081-5/+9
| | | | | | Two of those are use after frees. Found by clang-tidy, fixed by me. llvm-svn: 212537
* Fix for PR17073 ( http://llvm.org/pr17073 ), simplifycfg illegally hoists an ↵Sanjay Patel2014-07-071-3/+20
| | | | | | | | | | operation in a phi node that can trap. This patch adds to an existing loop over phi nodes in SimplifyCondBranchToCondBranch() to check for trapping ops and bails out of the optimization if we find one of those. The test cases verify that trapping ops are not hoisted and non-trapping ops are still optimized as expected. llvm-svn: 212490
* fixed some typos in commentsSanjay Patel2014-07-061-4/+4
| | | | llvm-svn: 212423
* Update the MemoryBuffer API to use ErrorOr.Rafael Espindola2014-07-061-3/+4
| | | | llvm-svn: 212405
* Minor stylistic fix in SimplifyCFG (test commit)Marcello Maggioni2014-07-031-1/+2
| | | | llvm-svn: 212259
* DebugInfo: Preserve debug location information when transforming a call into ↵David Blaikie2014-06-301-0/+1
| | | | | | | | | | | an invoke during inlining. This both improves basic debug info quality, but also fixes a larger hole whenever we inline a call/invoke without a location (debug info for the entire inlining is lost and other badness that the debug info emission code is currently working around but shouldn't have to). llvm-svn: 212065
* Revert "Introduce a string_ostream string builder facilty"Alp Toker2014-06-261-1/+2
| | | | | | Temporarily back out commits r211749, r211752 and r211754. llvm-svn: 211814
* Don't build switch tables for dllimport and TLS variables in GEPsHans Wennborg2014-06-261-2/+3
| | | | | | | This is a follow-up to r211331, which failed to notice that we were returning early from ValidLookupTableConstant for GEPs. llvm-svn: 211753
* Introduce a string_ostream string builder faciltyAlp Toker2014-06-261-2/+1
| | | | | | | | | | | | | | | | | | | | string_ostream is a safe and efficient string builder that combines opaque stack storage with a built-in ostream interface. small_string_ostream<bytes> additionally permits an explicit stack storage size other than the default 128 bytes to be provided. Beyond that, storage is transferred to the heap. This convenient class can be used in most places an std::string+raw_string_ostream pair or SmallString<>+raw_svector_ostream pair would previously have been used, in order to guarantee consistent access without byte truncation. The patch also converts much of LLVM to use the new facility. These changes include several probable bug fixes for truncated output, a programming error that's no longer possible with the new interface. llvm-svn: 211749
* LoopUnrollRuntime: Check for overflow in the trip count calculation.Benjamin Kramer2014-06-211-11/+12
| | | | | | Fixes PR19823. llvm-svn: 211436
* Don't build switch lookup tables for dllimport or TLS variablesHans Wennborg2014-06-201-0/+4
| | | | | | | | | | | | | We would previously put dllimport variables in switch lookup tables, which doesn't work because the address cannot be used in a constant initializer. This is basically the same problem that we have in PR19955. Putting TLS variables in switch tables also desn't work, because the address of such a variable is not constant. Differential Revision: http://reviews.llvm.org/D4220 llvm-svn: 211331
* LowerSwitch: track bounding range for the condition tree.Jim Grosbach2014-06-161-27/+102
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | When LowerSwitch transforms a switch instruction into a tree of ifs it is actually performing a binary search into the various case ranges, to see if the current value falls into one cases range of values. So, if we have a program with something like this: switch (a) { case 0: do0(); break; case 1: do1(); break; case 2: do2(); break; default: break; } the code produced is something like this: if (a < 1) { if (a == 0) { do0(); } } else { if (a < 2) { if (a == 1) { do1(); } } else { if (a == 2) { do2(); } } } This code is inefficient because the check (a == 1) to execute do1() is not needed. The reason is that because we already checked that (a >= 1) initially by checking that also (a < 2) we basically already inferred that (a == 1) without the need of an extra basic block spawned to check if actually (a == 1). The patch addresses this problem by keeping track of already checked bounds in the LowerSwitch algorithm, so that when the time arrives to produce a Leaf Block that checks the equality with the case value / range the algorithm can decide if that block is really needed depending on the already checked bounds . For example, the above with "a = 1" would work like this: the bounds start as LB: NONE , UB: NONE as (a < 1) is emitted the bounds for the else path become LB: 1 UB: NONE. This happens because by failing the test (a < 1) we know that the value "a" cannot be smaller than 1 if we enter the else branch. After the emitting the check (a < 2) the bounds in the if branch become LB: 1 UB: 1. This is because by checking that "a" is smaller than 2 then the upper bound becomes 2 - 1 = 1. When it is time to emit the leaf block for "case 1:" we notice that 1 can be squeezed exactly in between the LB and UB, which means that if we arrived to that block there is no need to emit a block that checks if (a == 1). Patch by: Marcello Maggioni <hayarms@gmail.com> llvm-svn: 211038
* Remove 'using std::errro_code' from lib.Rafael Espindola2014-06-131-2/+1
| | | | llvm-svn: 210871
* Don't use 'using std::error_code' in include/llvm.Rafael Espindola2014-06-121-0/+1
| | | | | | This should make sure that most new uses use the std prefix. llvm-svn: 210835
OpenPOWER on IntegriCloud