summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Update BasicAliasAnalysis to understand that nothing aliases with undef values.Daniel Berlin2015-05-051-0/+5
| | | | | | | | | | It got this in some cases (if one of them was an identified object), but not in all cases. This caused stores to undef to block load-forwarding in some cases, etc. Added test to Transforms/GVN to verify optimization occurs as expected. llvm-svn: 236511
* Fix -Wpessimizing-move warnings by removing std::move calls.Richard Trieu2015-04-301-1/+1
| | | | llvm-svn: 236278
* [WinEH] Start EH preparation for 32-bit x86, it uses no argumentsReid Kleckner2015-04-291-2/+2
| | | | | | | | | | | | | | | | | | 32-bit x86 MSVC-style exceptions are functionaly similar to 64-bit, but they take no arguments. Instead, they implicitly use the value of EBP passed in by the caller as a pointer to the parent's frame. In LLVM, we can represent this as llvm.frameaddress(1), and feed that into all of our calls to llvm.framerecover. The next steps are: - Add an alloca to the fs:00 linked list of handlers - Add something like llvm.sjlj.lsda or generalize it to store in the alloca - Move state number calculation to WinEHPrepare, arrange for FunctionLoweringInfo to call it - Use the state numbers to insert explicit loads and stores in the IR llvm-svn: 236172
* IR: Give 'DI' prefix to debug info metadataDuncan P. N. Exon Smith2015-04-291-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Finish off PR23080 by renaming the debug info IR constructs from `MD*` to `DI*`. The last of the `DIDescriptor` classes were deleted in r235356, and the last of the related typedefs removed in r235413, so this has all baked for about a week. Note: If you have out-of-tree code (like a frontend), I recommend that you get everything compiling and tests passing with the *previous* commit before updating to this one. It'll be easier to keep track of what code is using the `DIDescriptor` hierarchy and what you've already updated, and I think you're extremely unlikely to insert bugs. YMMV of course. Back to *this* commit: I did this using the rename-md-di-nodes.sh upgrade script I've attached to PR23080 (both code and testcases) and filtered through clang-format-diff.py. I edited the tests for test/Assembler/invalid-generic-debug-node-*.ll by hand since the columns were off-by-three. It should work on your out-of-tree testcases (and code, if you've followed the advice in the previous paragraph). Some of the tests are in badly named files now (e.g., test/Assembler/invalid-mdcompositetype-missing-tag.ll should be 'dicompositetype'); I'll come back and move the files in a follow-up commit. llvm-svn: 236120
* Make getModRefInfo(Instruction *) not crash on certain types of instructionsDaniel Berlin2015-04-281-10/+13
| | | | llvm-svn: 236023
* Fix typo in comment.Diego Novillo2015-04-241-1/+1
| | | | llvm-svn: 235723
* [getUnderlyingOjbects] Analyze loop PHIs further to remove false positivesAdam Nemet2015-04-232-11/+57
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Specifically, if a pointer accesses different underlying objects in each iteration, don't look through the phi node defining the pointer. The motivating case is the underlyling-objects-2.ll testcase. Consider the loop nest: int **A; for (i) for (j) A[i][j] = A[i-1][j] * B[j] This loop is transformed by Load-PRE to stash away A[i] for the next iteration of the outer loop: Curr = A[0]; // Prev_0 for (i: 1..N) { Prev = Curr; // Prev = PHI (Prev_0, Curr) Curr = A[i]; for (j: 0..N) Curr[j] = Prev[j] * B[j] } Since A[i] and A[i-1] are likely to be independent pointers, getUnderlyingObjects should not assume that Curr and Prev share the same underlying object in the inner loop. If it did we would try to dependence-analyze Curr and Prev and the analysis of the corresponding SCEVs would fail with non-constant distance. To fix this, the getUnderlyingObjects API is extended with an optional LoopInfo parameter. This is effectively what controls whether we want the above behavior or the original. Currently, I only changed to use this approach for LoopAccessAnalysis. The other testcase is to guard the opposite case where we do want to look through the loop PHI. If we step through an array by incrementing a pointer, the underlying object is the incoming value of the phi as the loop is entered. Fixes rdar://problem/19566729 llvm-svn: 235634
* Move Value.isDereferenceablePointer to ValueTracking [NFC]Philip Reames2015-04-232-2/+143
| | | | | | | | | | | Move isDereferenceablePointer function to Analysis. This function recursively tracks dereferencability over a chain of values like other functions in ValueTracking. This refactoring is motivated by further changes to support dereferenceable_or_null attribute (http://reviews.llvm.org/D8650). isDereferenceablePointer will be extended to perform context-sensitive analysis and IR is not a good place to have such functionality. Patch by: Artur Pilipenko <apilipenko@azulsystems.com> Differential Revision: reviews.llvm.org/D9075 llvm-svn: 235611
* Fix a type mismatch assert in SCEV divisionBrendon Cahoon2015-04-221-0/+8
| | | | | | | | | | | | An assert was triggered when attempting to create a new SCEV with operands of different types in the visitAddRecExpr. In this test case, the operand types of the numerator and denominator are different. The SCEV division code should generate a conservative answer when this happens. Differential Revision: http://reviews.llvm.org/D9021 llvm-svn: 235511
* Revamp PredIteratorCache interface to be cleaner.Daniel Berlin2015-04-211-14/+11
| | | | | | | | | | | | | Summary: This lets us use range based for loops. Reviewers: chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9169 llvm-svn: 235416
* Move IDF Calculation to a separate file, expose an interface to it.Daniel Berlin2015-04-212-0/+96
| | | | | | | | | | | | | | | Summary: MemorySSA uses this algorithm as well, and this enables us to reuse the code in both places. There are no actual algorithm or datastructure changes in here, just code movement. Reviewers: qcolombet, chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9118 llvm-svn: 235406
* DebugInfo: Drop rest of DIDescriptor subclassesDuncan P. N. Exon Smith2015-04-211-1/+1
| | | | | | | Delete the remaining subclasses of (the already deleted) `DIDescriptor`. Part of PR23080. llvm-svn: 235404
* Recognize n/1 in the SCEV divide functionBrendon Cahoon2015-04-201-0/+7
| | | | | | | | | | | | n/1 generates a quotient equal to n and a remainder of 0. If this case is not recognized, then the SCEV divide() function can return a remainder that is greater than or equal to the denominator, which means the delinearized subscripts for the test case will be incorrect. Differential Revision: http://reviews.llvm.org/D9003 llvm-svn: 235311
* [LoopAccesses] Improve debug outputAdam Nemet2015-04-171-4/+8
| | | | llvm-svn: 235238
* DebugInfo: Gut DIType and subclassesDuncan P. N. Exon Smith2015-04-161-11/+11
| | | | | | | | Continuing PR23080, gut `DIType` and its various subclasses, leaving behind thin wrappers around the pointer types in the new debug info hierarchy. llvm-svn: 235064
* DebugInfo: Gut DICompileUnit and DIFileDuncan P. N. Exon Smith2015-04-151-4/+4
| | | | | | | Continuing gutting `DIDescriptor` subclasses; this edition, `DICompileUnit` and `DIFile`. In the name of PR23080. llvm-svn: 235055
* One more -Wrange-loop-analysis cleanup.Richard Trieu2015-04-151-1/+1
| | | | llvm-svn: 235044
* Add range iterators for post order and inverse post order. Use themDaniel Berlin2015-04-151-12/+10
| | | | llvm-svn: 235026
* Re-apply r234898 and fix tests.Daniel Jasper2015-04-151-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit makes LLVM not estimate branch probabilities when doing a single bit bitmask tests. The code that originally made me discover this is: if ((a & 0x1) == 0x1) { .. } In this case we don't actually have any branch probability information and should not assume to have any. LLVM transforms this into: %and = and i32 %a, 1 %tobool = icmp eq i32 %and, 0 So, in this case, the result of a bitwise and is compared against 0, but nevertheless, we should not assume to have probability information. CodeGen/ARM/2013-10-11-select-stalls.ll started failing because the changed probabilities changed the results of ARMBaseInstrInfo::isProfitableToIfCvt() and led to an Ifcvt of the diamond in the test. AFAICT, the test was never meant to test this and thus changing the test input slightly to not change the probabilities seems like the best way to preserve the meaning of the test. llvm-svn: 234979
* Change range-based for-loops to be -Wrange-loop-analysis clean.Richard Trieu2015-04-151-1/+1
| | | | | | No functionality change. llvm-svn: 234963
* [Inliner] Don't inline functions with frameescape callsReid Kleckner2015-04-141-8/+19
| | | | | | | | | | | Inlining such intrinsics is very difficult, since you need to simultaneously transform many calls to llvm.framerecover and potentially duplicate the functions containing them. Normally this intrinsic isn't added until EH preparation, which is part of the backend pass pipeline after inlining. However, if it were to get fed through the inliner, this change will ensure that it doesn't break the code. llvm-svn: 234937
* Revert "The code that originally made me discover this is:"Rafael Espindola2015-04-141-8/+0
| | | | | | | This reverts commit r234898. CodeGen/ARM/2013-10-11-select-stalls.ll was faling. llvm-svn: 234903
* Improve RefreshCallGraph to remove invalid call graph edge.Chad Rosier2015-04-141-4/+7
| | | | | | | | | | | | | With commit r219944, InstCombine can now turn a sqrtl into a llvm.fabs.f64. The call graph edge originally representing the call to sqrtl becomes invalid. This patch modifies CGPassManager::RefreshCallGraph() to remove the invalid call graph edge, which can triggers an assert in CallGraphNode::addCalledFunction(). Phabricator Review: http://reviews.llvm.org/D7705 Patch by Lawrence Hu <lawrence@codeaurora.org>. llvm-svn: 234902
* The code that originally made me discover this is:Daniel Jasper2015-04-141-0/+8
| | | | | | | | | | | | | | | | | | if ((a & 0x1) == 0x1) { .. } In this case we don't actually have any branch probability information and should not assume to have any. LLVM transforms this into: %and = and i32 %a, 1 %tobool = icmp eq i32 %and, 0 So, in this case, the result of a bitwise and is compared against 0, but nevertheless, we should not assume to have probability information. llvm-svn: 234898
* DebugInfo: Gut DISubprogram and DILexicalBlock*Duncan P. N. Exon Smith2015-04-141-5/+5
| | | | | | | Gut the `DIDescriptor` wrappers around `MDLocalScope` subclasses. Note that `DILexicalBlock` wraps `MDLexicalBlockBase`, not `MDLexicalBlock`. llvm-svn: 234850
* [SCEV] Strengthen SCEVExpander::isHighCostExpansion.Sanjoy Das2015-04-141-6/+17
| | | | | | | | | | | | | | | | | | Summary: Teach `isHighCostExpansion` to consider divisions by power-of-two constants as cheap and add a test case. This change is needed for a new user of `isHighCostExpansion` that will be added in a subsequent change. Depends on D8995. Reviewers: atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8993 llvm-svn: 234845
* [SCEV] Refactor out isHighCostExpansion. NFCI.Sanjoy Das2015-04-141-0/+56
| | | | | | | | | | | | | | Summary: Move isHighCostExpansion from IndVarSimplify to SCEVExpander. This exposed function will be used in a subsequent change. Reviewers: bogner, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8995 llvm-svn: 234844
* DebugInfo: Gut DIVariable and DIGlobalVariableDuncan P. N. Exon Smith2015-04-141-4/+4
| | | | | | | | | | Gut all the non-pointer API from the variable wrappers, except an implicit conversion from `DIGlobalVariable` to `DIDescriptor`. Note that if you're updating out-of-tree code, `DIVariable` wraps `MDLocalVariable` (`MDVariable` is a common base class shared with `MDGlobalVariable`). llvm-svn: 234840
* [LoopAccesses] Properly print whether memchecks are neededAdam Nemet2015-04-141-3/+3
| | | | | | | | | | | Fix oversight in -analyze output. PtrRtCheck contains the pointers that need to be checked against each other and not whether memchecks are necessary. For instance in the testcase PtrRtCheck has four elements but all no-alias so no checking is necessary. llvm-svn: 234833
* Add new getModRefInfo API to determine whether an Instruction and a call ↵Daniel Berlin2015-04-131-0/+17
| | | | | | modify the same memory llvm-svn: 234814
* Common some code from MemoryDependenceAnalysis that will be used in MemorySSADaniel Berlin2015-04-131-17/+1
| | | | llvm-svn: 234813
* Make getModRefInfo with a default location not crash.Daniel Berlin2015-04-131-9/+12
| | | | | | | Add getModRefInfo that works without location. Add unit tests. llvm-svn: 234811
* [inliner] Don't inline a function if it doesn't have exactly the sameAkira Hatanaka2015-04-131-4/+6
| | | | | | | | target-cpu and target-features attribute strings as the caller. Differential Revision: http://reviews.llvm.org/D8984 llvm-svn: 234773
* Use 'override/final' instead of 'virtual' for overridden methodsAlexander Kornienko2015-04-112-3/+3
| | | | | | | | | | | | | | The patch is generated using clang-tidy misc-use-override check. This command was used: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py \ -checks='-*,misc-use-override' -header-filter='llvm|clang' \ -j=32 -fix -format http://reviews.llvm.org/D8925 llvm-svn: 234679
* [CallSite] Make construction from Value* (or Instruction*) explicit.Benjamin Kramer2015-04-106-6/+6
| | | | | | | | | | | | | | | | | | | CallSite roughly behaves as a common base CallInst and InvokeInst. Bring the behavior closer to that model by making upcasts explicit. Downcasts remain implicit and work as before. Following dyn_cast as a mental model checking whether a Value *V isa CallSite now looks like this: if (auto CS = CallSite(V)) // think dyn_cast instead of: if (CallSite CS = V) This is an extra token but I think it is slightly clearer. Making the ctor explicit has the advantage of not accidentally creating nullptr CallSites, e.g. when you pass a Value * to a function taking a CallSite argument. llvm-svn: 234601
* Reduce dyn_cast<> to isa<> or cast<> where possible.Benjamin Kramer2015-04-101-3/+2
| | | | | | No functional change intended. llvm-svn: 234586
* Divergence analysis for GPU programsJingyue Wu2015-04-104-0/+343
| | | | | | | | | | | | | | | | | | | Summary: Some optimizations such as jump threading and loop unswitching can negatively affect performance when applied to divergent branches. The divergence analysis added in this patch conservatively estimates which branches in a GPU program can diverge. This information can then help LLVM to run certain optimizations selectively. Test Plan: test/Analysis/DivergenceAnalysis/NVPTX/diverge.ll Reviewers: resistor, hfinkel, eliben, meheff, jholewinski Subscribers: broune, bjarke.roune, madhur13490, tstellarAMD, dberlin, echristo, jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D8576 llvm-svn: 234567
* [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
OpenPOWER on IntegriCloud