summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [LoopAccesses] Allow analysis to complete in the presence of uniform storesAdam Nemet2015-04-081-11/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | (Re-apply r234361 with a fix and a testcase for PR23157) Both run-time pointer checking and the dependence analysis are capable of dealing with uniform addresses. I.e. it's really just an orthogonal property of the loop that the analysis computes. Run-time pointer checking will only try to reason about SCEVAddRec pointers or else gives up. If the uniform pointer turns out the be a SCEVAddRec in an outer loop, the run-time checks generated will be correct (start and end bounds would be equal). In case of the dependence analysis, we work again with SCEVs. When compared against a loop-dependent address of the same underlying object, the difference of the two SCEVs won't be constant. This will result in returning an Unknown dependence for the pair. When compared against another uniform access, the difference would be constant and we should return the right type of dependence (forward/backward/etc). The changes also adds support to query this property of the loop and modify the vectorizer to use this. Patch by Ashutosh Nema! llvm-svn: 234424
* Revert "[LoopAccesses] Allow analysis to complete in the presence of uniform ↵Adam Nemet2015-04-081-8/+11
| | | | | | | | | | stores" This reverts commit r234361. It caused PR23157. llvm-svn: 234387
* [LoopAccesses] Allow analysis to complete in the presence of uniform storesAdam Nemet2015-04-071-11/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | Both run-time pointer checking and the dependence analysis are capable of dealing with uniform addresses. I.e. it's really just an orthogonal property of the loop that the analysis computes. Run-time pointer checking will only try to reason about SCEVAddRec pointers or else gives up. If the uniform pointer turns out the be a SCEVAddRec in an outer loop, the run-time checks generated will be correct (start and end bounds would be equal). In case of the dependence analysis, we work again with SCEVs. When compared against a loop-dependent address of the same underlying object, the difference of the two SCEVs won't be constant. This will result in returning an Unknown dependence for the pair. When compared against another uniform access, the difference would be constant and we should return the right type of dependence (forward/backward/etc). The changes also adds support to query this property of the loop and modify the vectorizer to use this. Patch by Ashutosh Nema! llvm-svn: 234361
* [LoopAccesses] New API to query if memchecks are necessary after partitioningAdam Nemet2015-04-071-0/+11
| | | | | | This is used by Loop Distribution. llvm-svn: 234283
* Transforms: Stop using DIDescriptor::is*() and auto-castingDuncan P. N. Exon Smith2015-04-061-4/+2
| | | | | | Same as r234255, but for lib/Analysis and lib/Transforms. llvm-svn: 234257
* [opaque pointer type] More GEP API migrations in IRBuilder usesDavid Blaikie2015-04-031-1/+1
| | | | | | | | | | | | | The plan here is to push the API changes out from the common components (like Constant::getGetElementPtr and IRBuilder::CreateGEP related functions) and just update callers to either pass the type if it's obvious, or pass null. Do this with LoadInst as well and anything else that comes up, then to start porting specific uses to not pass null anymore - this may require some refactoring in each case. llvm-svn: 234042
* [opaque pointer type] API migration for GEP constant factoriesDavid Blaikie2015-04-024-21/+29
| | | | | | | | | | | | | Require the pointee type to be passed explicitly and assert that it is correct. For now it's possible to pass nullptr here (and I've done so in a few places in this patch) but eventually that will be disallowed once all clients have been updated or removed. It'll be a long road to get all the way there... but if you have the cahnce to update your callers to pass the type explicitly without depending on a pointer's element type, that would be a good thing to do soon and a necessary thing to do eventually. llvm-svn: 233938
* [LoopAccesses] Handle case when no memchecks are needed after partitioningAdam Nemet2015-04-021-2/+4
| | | | llvm-svn: 233930
* [SCEV] Look at backedge dominating conditions (re-land r233447).Sanjoy Das2015-04-011-2/+62
| | | | | | | | | | | | | Summary: This change teaches ScalarEvolution::isLoopBackedgeGuardedByCond to look at edges within the loop body that dominate the latch. We don't do an exhaustive search for all possible edges, but only a quick walk up the dom tree. This re-lands r233447. r233447 was reverted because it caused massive compile-time regressions. This change has a fix for the same issue. llvm-svn: 233829
* Remove 4,096 loop scale limitation.Diego Novillo2015-04-011-21/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is part 1 of fixes to address the problems described in https://llvm.org/bugs/show_bug.cgi?id=22719. The restriction to limit loop scales to 4,096 does not really prevent overflows anymore, as the underlying algorithm has changed and does not seem to suffer from this problem. Additionally, artificially restricting loop scales to such a low number skews frequency information, making loops of equal hotness appear to have very different hotness properties. The only loops that are artificially restricted to a scale of 4096 are infinite loops (those loops with an exit mass of 0). This prevents infinite loops from skewing the frequencies of other regions in the CFG. At the end of propagation, frequencies are scaled to values that take no more than 64 bits to represent. When the range of frequencies to be represented fits within 61 bits, it pushes up the scaling factor to a minimum of 8 to better distinguish small frequency values. Otherwise, small frequency values are all saturated down at 1. Tested on x86_64. Reviewers: dexonsmith Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8718 llvm-svn: 233826
* [WinEH] Run cleanup handlers when an exception is thrownDavid Majnemer2015-03-301-3/+1
| | | | | | | | Generate tables in the .xdata section representing what actions to take when an exception is thrown. This currently fills in state for cleanups, catch handlers are still unfinished. llvm-svn: 233636
* [opaque pointer type] Change GetElementPtrInst::getIndexedType to take the ↵David Blaikie2015-03-303-5/+7
| | | | | | | | | | pointee type This pushes the use of PointerType::getElementType up into several callers - I'll essentially just have to keep pushing that up the stack until I can eliminate every call to it... llvm-svn: 233604
* Revert "[SCEV] Look at backedge dominating conditions."Daniel Jasper2015-03-301-40/+0
| | | | | | | This leads to terribly slow compile times under MSAN. More discussion on the commit thread of r233447. llvm-svn: 233529
* [SCEV] Look at backedge dominating conditions.Sanjoy Das2015-03-271-0/+40
| | | | | | | | | | | | | | | | Summary: This change teaches ScalarEvolution::isLoopBackedgeGuardedByCond to look at edges within the loop body that dominate the latch. We don't do an exhaustive search for all possible edges, but only a quick walk up the dom tree. Reviewers: atrick, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8627 llvm-svn: 233447
* Remove superfluous .str() and replace std::string concatenation with Twine.Yaron Keren2015-03-272-3/+3
| | | | llvm-svn: 233392
* [SCEV] Revert bailout added in r75511.Sanjoy Das2015-03-261-12/+11
| | | | | | | | | | | | | | Summary: With the introduction of MarkPendingLoopPredicates in r157092, I don't think the bailout is needed anymore. Reviewers: atrick, nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8624 llvm-svn: 233296
* [ValueTracking] Fix PR23011.Sanjoy Das2015-03-251-7/+16
| | | | | | | | | | | | | | Summary: `ComputeNumSignBits` returns incorrect results for `srem` instructions. This change fixes the issue and adds a test case. Reviewers: nadav, nicholas, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8600 llvm-svn: 233225
* [APInt] Add an isSplat helper and use it in some places.Benjamin Kramer2015-03-251-3/+1
| | | | | | | To complement getSplat. This is more general than the binary decomposition method as it also handles non-pow2 splat sizes. llvm-svn: 233195
* !invariant.load semantics with potentially clobbering callsPhilip Reames2015-03-241-0/+9
| | | | | | | | | | A load from an invariant location is assumed to not alias any otherwise potentially aliasing stores. Our implementation only applied this rule to store instructions themselves whereas they it should apply for any memory accessing instruction. This results in both FRE and PRE becoming more effective at eliminating invariant loads. Note that as a follow on change I will likely move this into AliasAnalysis itself. That's where the TBAA constant flag is handled and the semantics are essentially the same. I'd like to separate the semantic change from the refactoring and thus have extended the hack that's already in MemoryDependenceAnalysis for this change. Differential Revision: http://reviews.llvm.org/D8591 llvm-svn: 233140
* Opaque Pointer Types: GEP API migrations to specify the gep type explicitlyDavid Blaikie2015-03-241-2/+3
| | | | | | | | | | | | | | | | | | | | | The changes to InstCombine (& SCEV) do seem a bit silly - it doesn't make anything obviously better to have the caller access the pointers element type (the thing I'm trying to remove) than the GEP itself, but it's a helpful migration step. This will allow me to more obviously lock down GEP (& Load, etc) API usage, then fix all the code that accesses pointer element types except the places that need to be removed (most of the InstCombines) anyway - at which point I'll need to just remove all that code because it won't be meaningful anymore (there will be no pointer types, so no bitcasts to combine) SCEV looks like it'll need some restructuring - we'll have to do a bit more work for GEP canonicalization, since it'll depend on how it's used if we can even manage to canonicalize it to a non-ugly GEP. I guess we can do some fun stuff like voting (do 2 out of 3 load from the GEP with a certain type that gives a pretty GEP? Does every typed use of the GEP use either a specific type or a generic type (i8*, etc)?) llvm-svn: 233131
* Refactor: Simplify boolean expressions in lib/AnalysisDavid Blaikie2015-03-241-6/+3
| | | | | | | | | | | | Simplify boolean expressions using `true` and `false` with `clang-tidy` Patch by Richard Thomson. Reviewed By: nlewycky Differential Revision: http://reviews.llvm.org/D8528 llvm-svn: 233091
* Re-sort includes with sort-includes.py and insert raw_ostream.h where it's used.Benjamin Kramer2015-03-236-2/+8
| | | | llvm-svn: 232998
* Purge unused includes throughout libSupport.Benjamin Kramer2015-03-232-0/+2
| | | | | | NFC. llvm-svn: 232976
* ValueTracking: Forward getConstantStringInfo's TrimAtNul param into ↵Benjamin Kramer2015-03-211-2/+3
| | | | | | | | | | | recursive invocation Currently this is only used to tweak the backend's memcpy inlining heuristics, testing that isn't very helpful. A real test case will follow in the next commit, where this behavior would cause a real miscompilation. llvm-svn: 232895
* MemoryDependenceAnalysis: Don't miscompile atomicsDavid Majnemer2015-03-211-11/+4
| | | | | | | | | | | | r216771 introduced a change to MemoryDependenceAnalysis that allowed it to reason about acquire/release operations. However, this change does not ensure that the acquire/release operations pair. Unfortunately, this leads to miscompiles as we won't see an acquire load as properly memory effecting. This largely reverts r216771. This fixes PR22708. llvm-svn: 232889
* Correctly estimate SROA savings for store operands in inline cost analysis.Wei Mi2015-03-201-2/+2
| | | | | | | | | | | | When estimating SROA savings, we want to see if an address is derived off an alloca in the caller. For store instructions, operand 1 is the address operand, but the current code uses operand 0. Use getPointerOperand for loads and stores to fix this. Patch by Easwaran Raman. http://reviews.llvm.org/D8425 llvm-svn: 232827
* Small optimization to avoid getting pass info when we will not run loopDaniel Berlin2015-03-201-0/+3
| | | | llvm-svn: 232826
* Fix comment from r232794. NFCNick Lewycky2015-03-201-1/+1
| | | | llvm-svn: 232796
* When simplifying a SCEV truncate by distributing, consider it a ↵Nick Lewycky2015-03-201-4/+6
| | | | | | simplification to replace a cast, even if we end up with a trunc around the term. Fixes PR22960! llvm-svn: 232794
* [SCEV] Make isImpliedCond smarter.Sanjoy Das2015-03-181-0/+44
| | | | | | | | | | | | | | | | | | Summary: This change teaches isImpliedCond to infer things like "X sgt 0" => "X - 1 sgt -1". The `ConstantRange` class has the logic to do the heavy lifting, this change simply gets ScalarEvolution to exploit that when reasonable. Depends on D8345 Reviewers: atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8346 llvm-svn: 232576
* [ConstantRange] Split makeICmpRegion in two.Sanjoy Das2015-03-181-2/+2
| | | | | | | | | | | | | | | | | | | | Summary: This change splits `makeICmpRegion` into `makeAllowedICmpRegion` and `makeSatisfyingICmpRegion` with slightly different contracts. The first one is useful for determining what values some expression //may// take, given that a certain `icmp` evaluates to true. The second one is useful for determining what values are guaranteed to //satisfy// a given `icmp`. Reviewers: nlewycky Reviewed By: nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8345 llvm-svn: 232575
* TLI: Add addVectorizableFunctionsFromVecLib.Michael Zolotukhin2015-03-171-0/+34
| | | | | | | | Also, add several entries to vectorizable functions table, and corresponding tests. The table isn't complete, it'll be populated later. Review: http://reviews.llvm.org/D8131 llvm-svn: 232531
* LoopVectorize: teach loop vectorizer to vectorize calls.Michael Zolotukhin2015-03-171-0/+7
| | | | | | | The tests would be committed in a commit for http://reviews.llvm.org/D8131 Review: http://reviews.llvm.org/D8095 llvm-svn: 232530
* TTI: Add getCallInstrCost.Michael Zolotukhin2015-03-171-0/+5
| | | | | Review: http://reviews.llvm.org/D8094 llvm-svn: 232524
* TLI: Add interface for querying whether a function is vectorizable.Michael Zolotukhin2015-03-171-0/+70
| | | | | Review: http://reviews.llvm.org/D8093 llvm-svn: 232523
* Fix doxygen comments from r232268Duncan P. N. Exon Smith2015-03-161-8/+8
| | | | llvm-svn: 232388
* Made CFLAA agree with clang-format. NFC.George Burgess IV2015-03-151-9/+7
| | | | | | So everyone's lives are easier in the future llvm-svn: 232293
* [opaque pointer type] more gep API migrationDavid Blaikie2015-03-141-4/+3
| | | | llvm-svn: 232274
* Recover the ability to 'b CheckFailed' after r231577Duncan P. N. Exon Smith2015-03-141-7/+14
| | | | | | | | | | Given that the stated purpose of `CheckFailed()` is to provide a nice spot for a breakpoint, it'd be nice not to have to use a regex to break on it. Recover the ability to simply use `b CheckFailed` by specializing the message-only version, and by changing the variadic version to call into the message-only version. llvm-svn: 232268
* [SCEV] Fix PR22856.Sanjoy Das2015-03-131-3/+6
| | | | | | | | | | | | | | | | | | | | Summary: ScalarEvolutionExpander assumes that the header block of a loop is a legal place to have a use for a phi node. This is true only for phis that are either in the header or dominate the header block, but it is not true for phi nodes that are strictly internal to the loop body. This change teaches ScalarEvolutionExpander to place uses of PHI nodes in the basic block the PHI nodes belong to. This is always legal, and `hoistIVInc` ensures that the said position dominates `IsomorphicInc`. Reviewers: atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8311 llvm-svn: 232189
* Teach TBAA analysis to report errors on cyclic TBAA metadata rather than ↵Owen Anderson2015-03-131-4/+9
| | | | | | hanging. llvm-svn: 232144
* When forming an addrec out of a phi don't just look at the last computation ↵Nick Lewycky2015-03-131-5/+7
| | | | | | | | and steal its flags for our own, there may be other computations in the middle. Check whether the LHS of the computation is the phi itself and then we know it's safe to steal the flags. Fixes PR22795. There's a missed optimization opportunity where we could look at the full chain of computation and take the intersection of the flags instead of only looking one instruction deep. llvm-svn: 232134
* Stop calling DwarfEHPrepare from WinEHPrepareReid Kleckner2015-03-121-12/+0
| | | | | | | | Instead, run both EH preparation passes, and have them both ignore functions with unrecognized EH personalities. Pass delegation involved some hacky code for creating an AnalysisResolver that we don't need now. llvm-svn: 231995
* Infer known bits from dominating conditionsPhilip Reames2015-03-101-0/+212
| | | | | | | | | | | | | | | | | This patch adds limited support in ValueTracking for inferring known bits of a value from conditional expressions which must be true to reach the instruction we're trying to optimize. At this time, the feature is off by default. Once landed, I'm hoping for feedback from others on both profitability and compile time impact. Forms of conditional value propagation have been tried in LLVM before and have failed due to compile time problems. In an attempt to side step that, this patch only considers conditions where the edge leaving the branch dominates the context instruction. It does not attempt full dataflow. Even with that restriction, it handles many interesting cases: * Early exits from functions * Early exits from loops (for context instructions in the loop and after the check) * Conditions which control entry into loops, including multi-version loops (such as those produced during vectorization, IRCE, loop unswitch, etc..) Possible applications include optimizing using information provided by constructs such as: preconditions, assumptions, null checks, & range checks. This patch implements two approaches to the problem that need further benchmarking. Approach 1 is to directly walk the dominator tree looking for interesting conditions. Approach 2 is to inspect other uses of the value being queried for interesting comparisons. From initial benchmarking, it appears that Approach 2 is faster than Approach 1, but this needs to be further validated. Differential Revision: http://reviews.llvm.org/D7708 llvm-svn: 231879
* [LoopAccesses] Add debug message to indicate the result of the analysisAdam Nemet2015-03-101-4/+7
| | | | | | | | | | The debug message was pretty confusing here. It only reported the situation with memchecks without the result of the dependence analysis. Now it prints whether the loop is safe from the POV of the dependence analysis and if yes, whether we need memchecks. llvm-svn: 231854
* LoopAccessAnalysis: Silence -Wreturn-type diagnostic from GCCDavid Majnemer2015-03-101-0/+3
| | | | llvm-svn: 231836
* [LAA-memchecks] Comment improvementAdam Nemet2015-03-101-2/+2
| | | | | | I forgot to roll this into r231816. It was requested by Hal in D8122. llvm-svn: 231821
* [LAA-memchecks 3/3] Introduce pointer partitions for memchecksAdam Nemet2015-03-101-10/+36
| | | | | | | | | | | | | | | | | This is the final patch that actually introduces the new parameter of partition mapping to RuntimePointerCheck::needsChecking. Another API (LAI::getInstructionsForAccess) is also exposed that helps to map pointers to instructions because ultimately we partition instructions. The WIP version of the Loop Distribution pass in D6930 has been adapted to use all this. See for example, how InstrPartitionContainer::computePartitionSetForPointers sets up the partitions using the above API and then calls to LAI::addRuntimeCheck with the pointer partitions. llvm-svn: 231818
* [LAA-memchecks 2/3] Move number of memcheck threshold checking to LVAdam Nemet2015-03-101-27/+3
| | | | | | | | | | | | | | | | | | | | | Now the analysis won't "fail" if the memchecks exceed the threshold. It is the transform pass' responsibility to perform the check. This allows the transform pass to further analyze/eliminate the memchecks. E.g. in Loop distribution we only need to check pointers that end up in different partitions. Note that there is a slight change of functionality here. The logic in analyzeLoop is that if dependence checking fails due to non-constant distance between the pointers, another attempt is made to prove safety of the dependences purely using run-time checks. Before this patch we could fail the loop due to exceeding the memcheck threshold after the first step, now we only check the threshold in the client after the full analysis. There is no measurable compile-time effect but I wanted to record this here. llvm-svn: 231817
* [LAA-memchecks 1/3] Split out NumComparisons checks. NFCAdam Nemet2015-03-101-22/+30
| | | | | | | | | | | | | | | The check for the number of memchecks will be moved to the client of this analysis. Besides allowing for transform-specific thresholds, this also lets Loop Distribution post-process the memchecks; Loop Distribution only needs memchecks between pointers of different partitions. The motivation for this first patch is to untangle the CanDoRT check from the NumComparison check before moving the NumComparison part. CanDoRT means that we couldn't determine the bounds for the pointer. Note that NumComparison is set independent of this flag. llvm-svn: 231816
OpenPOWER on IntegriCloud