summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [SCEV] Be less conservative when extending bitwidths for computing ranges.Michael Zolotukhin2016-12-201-7/+6
| | | | | | | | | | | | | | | | | | | | | | | | Summary: In getRangeForAffineAR we compute ranges for affine exprs E = A + B*C, where ranges for A, B, and C are known. To avoid overflow, we need to operate on a bigger bitwidth, and originally we chose 2*x+1 for this (x being the original bitwidth). However, it is safe to use just 2*x: A+B*C <= (2^x - 1) + (2^x - 1)*(2^x - 1) = = 2^x - 1 + 2^2x - 2^x - 2^x + 1 = = 2^2x - 2^x <= 2^2x - 1 Unnecessary extending of bitwidths results in noticeable slowdowns: ranges perform arithmetic operations using APInt, which are much slower when bitwidths are bigger than 64. Reviewers: sanjoy, majnemer, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D27795 llvm-svn: 290211
* IR: Eliminate non-determinism in the module summary analysis.Peter Collingbourne2016-12-201-25/+23
| | | | | | | | | Also make the summary ref and call graph vectors immutable. This means a smaller API surface and fewer places to audit for non-determinism. Differential Revision: https://reviews.llvm.org/D27875 llvm-svn: 290200
* Use MaxDepth instead of repeating its valueMatt Arsenault2016-12-201-3/+3
| | | | llvm-svn: 290194
* Replace std::find_if with llvm::find_if. NFC.George Burgess IV2016-12-201-5/+4
| | | | llvm-svn: 290190
* [PM] Rework a loop in the CGSCC update logic to be more conservative andChandler Carruth2016-12-201-7/+11
| | | | | | | | | | clear. The current RefSCC can occur in exactly one position so we should just enforce that and leverage the property rather than checking for it anywhere. This addresses review comments made on another patch. llvm-svn: 290162
* [PM] Provide an initial, minimal port of the inliner to the new pass manager.Chandler Carruth2016-12-201-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This doesn't implement *every* feature of the existing inliner, but tries to implement the most important ones for building a functional optimization pipeline and beginning to sort out bugs, regressions, and other problems. Notable, but intentional omissions: - No alloca merging support. Why? Because it isn't clear we want to do this at all. Active discussion and investigation is going on to remove it, so for simplicity I omitted it. - No support for trying to iterate on "internally" devirtualized calls. Why? Because it adds what I suspect is inappropriate coupling for little or no benefit. We will have an outer iteration system that tracks devirtualization including that from function passes and iterates already. We should improve that rather than approximate it here. - Optimization remarks. Why? Purely to make the patch smaller, no other reason at all. The last one I'll probably work on almost immediately. But I wanted to skip it in the initial patch to try to focus the change as much as possible as there is already a lot of code moving around and both of these *could* be skipped without really disrupting the core logic. A summary of the different things happening here: 1) Adding the usual new PM class and rigging. 2) Fixing minor underlying assumptions in the inline cost analysis or inline logic that don't generally hold in the new PM world. 3) Adding the core pass logic which is in essence a loop over the calls in the nodes in the call graph. This is a bit duplicated from the old inliner, but only a handful of lines could realistically be shared. (I tried at first, and it really didn't help anything.) All told, this is only about 100 lines of code, and most of that is the mechanics of wiring up analyses from the new PM world. 4) Updating the LazyCallGraph (in the new PM) based on the *newly inlined* calls and references. This is very minimal because we cannot form cycles. 5) When inlining removes the last use of a function, eagerly nuking the body of the function so that any "one use remaining" inline cost heuristics are immediately refined, and queuing these functions to be completely deleted once inlining is complete and the call graph updated to reflect that they have become dead. 6) After all the inlining for a particular function, updating the LazyCallGraph and the CGSCC pass manager to reflect the function-local simplifications that are done immediately and internally by the inline utilties. These are the exact same fundamental set of CG updates done by arbitrary function passes. 7) Adding a bunch of test cases to specifically target CGSCC and other subtle aspects in the new PM world. Many thanks to the careful review from Easwaran and Sanjoy and others! Differential Revision: https://reviews.llvm.org/D24226 llvm-svn: 290161
* [IR] Remove the DIExpression field from DIGlobalVariable.Adrian Prantl2016-12-201-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch implements PR31013 by introducing a DIGlobalVariableExpression that holds a pair of DIGlobalVariable and DIExpression. Currently, DIGlobalVariables holds a DIExpression. This is not the best way to model this: (1) The DIGlobalVariable should describe the source level variable, not how to get to its location. (2) It makes it unsafe/hard to update the expressions when we call replaceExpression on the DIGLobalVariable. (3) It makes it impossible to represent a global variable that is in more than one location (e.g., a variable with multiple DW_OP_LLVM_fragment-s). We also moved away from attaching the DIExpression to DILocalVariable for the same reasons. This reapplies r289902 with additional testcase upgrades and a change to the Bitcode record for DIGlobalVariable, that makes upgrading the old format unambiguous also for variables without DIExpressions. <rdar://problem/29250149> https://llvm.org/bugs/show_bug.cgi?id=31013 Differential Revision: https://reviews.llvm.org/D26769 llvm-svn: 290153
* Add files I seem to have dropped in my revert (r290086).Daniel Jasper2016-12-191-0/+140
| | | | | | Sorry! llvm-svn: 290087
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-1914-420/+465
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Retry: [BPI] Use a safer constructor to calculate branch probabilitiesVedant Kumar2016-12-171-12/+12
| | | | | | | | | | | | | | | | | | | BPI may trigger signed overflow UB while computing branch probabilities for cold calls or to unreachables. For example, with our current choice of weights, we'll crash if there are >= 2^12 branches to an unreachable. Use a safer BranchProbability constructor which is better at handling fractions with large denominators. Changes since the initial commit: - Use explicit casts to ensure that multiplication operands are 64-bit ints. rdar://problem/29368161 Differential Revision: https://reviews.llvm.org/D27862 llvm-svn: 290022
* Revert "[BPI] Use a safer constructor to calculate branch probabilities"Vedant Kumar2016-12-171-12/+12
| | | | | | | | | | This reverts commit r290016. It breaks this bot, even though the test passes locally: http://bb.pgr.jp/builders/ninja-x64-msvc-RA-centos6/builds/32956/ AnalysisTests: /home/bb/ninja-x64-msvc-RA-centos6/llvm-project/llvm/lib/Support/BranchProbability.cpp:52: static llvm::BranchProbability llvm::BranchProbability::getBranchProbability(uint64_t, uint64_t): Assertion `Numerator <= Denominator && "Probability cannot be bigger than 1!"' failed. llvm-svn: 290019
* [BPI] Use a safer constructor to calculate branch probabilitiesVedant Kumar2016-12-171-12/+12
| | | | | | | | | | | | | | | BPI may trigger signed overflow UB while computing branch probabilities for cold calls or to unreachables. For example, with our current choice of weights, we'll crash if there are >= 2^12 branches to an unreachable. Use a safer BranchProbability constructor which is better at handling fractions with large denominators. rdar://problem/29368161 Differential Revision: https://reviews.llvm.org/D27862 llvm-svn: 290016
* ModuleSummaryAnalysis: Remove some duplicate code. NFCI.Peter Collingbourne2016-12-161-5/+0
| | | | llvm-svn: 290003
* Revert "[IR] Remove the DIExpression field from DIGlobalVariable."Adrian Prantl2016-12-161-2/+1
| | | | | | | | | | | | | | | | | This reverts commit 289920 (again). I forgot to implement a Bitcode upgrade for the case where a DIGlobalVariable has not DIExpression. Unfortunately it is not possible to safely upgrade these variables without adding a flag to the bitcode record indicating which version they are. My plan of record is to roll the planned follow-up patch that adds a unit: field to DIGlobalVariable into this patch before recomitting. This way we only need one Bitcode upgrade for both changes (with a version flag in the bitcode record to safely distinguish the record formats). Sorry for the churn! llvm-svn: 289982
* [IR] Remove the DIExpression field from DIGlobalVariable.Adrian Prantl2016-12-161-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch implements PR31013 by introducing a DIGlobalVariableExpression that holds a pair of DIGlobalVariable and DIExpression. Currently, DIGlobalVariables holds a DIExpression. This is not the best way to model this: (1) The DIGlobalVariable should describe the source level variable, not how to get to its location. (2) It makes it unsafe/hard to update the expressions when we call replaceExpression on the DIGLobalVariable. (3) It makes it impossible to represent a global variable that is in more than one location (e.g., a variable with multiple DW_OP_LLVM_fragment-s). We also moved away from attaching the DIExpression to DILocalVariable for the same reasons. This reapplies r289902 with additional testcase upgrades. <rdar://problem/29250149> https://llvm.org/bugs/show_bug.cgi?id=31013 Differential Revision: https://reviews.llvm.org/D26769 llvm-svn: 289920
* Revert "[IR] Remove the DIExpression field from DIGlobalVariable."Adrian Prantl2016-12-161-2/+1
| | | | | | This reverts commit 289902 while investigating bot berakage. llvm-svn: 289906
* [IR] Remove the DIExpression field from DIGlobalVariable.Adrian Prantl2016-12-161-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch implements PR31013 by introducing a DIGlobalVariableExpression that holds a pair of DIGlobalVariable and DIExpression. Currently, DIGlobalVariables holds a DIExpression. This is not the best way to model this: (1) The DIGlobalVariable should describe the source level variable, not how to get to its location. (2) It makes it unsafe/hard to update the expressions when we call replaceExpression on the DIGLobalVariable. (3) It makes it impossible to represent a global variable that is in more than one location (e.g., a variable with multiple DW_OP_LLVM_fragment-s). We also moved away from attaching the DIExpression to DILocalVariable for the same reasons. <rdar://problem/29250149> https://llvm.org/bugs/show_bug.cgi?id=31013 Differential Revision: https://reviews.llvm.org/D26769 llvm-svn: 289902
* [SimplifyLibCalls] Lower fls() to llvm.ctlz().Davide Italiano2016-12-151-3/+3
| | | | | | Differential Revision: https://reviews.llvm.org/D14590 llvm-svn: 289894
* [CostModel] Fix long standing bug with reverse shuffle mask detectionSimon Pilgrim2016-12-151-1/+1
| | | | | | Incorrect 'undef' mask index matching meant that broadcast shuffles could be detected as reverse shuffles llvm-svn: 289811
* Revert part of r289765 that is not necessaryHal Finkel2016-12-151-2/+2
| | | | | | | | CS.doesNotAccessMemory(ArgNo) and CS.onlyReadsMemory(ArgNo) calls dataOperandHasImpliedAttr, so revert this part of r289765 because it should not be necessary. llvm-svn: 289768
* Fix argument attribute queries with bundle operandsHal Finkel2016-12-152-4/+6
| | | | | | | When iterating over data operands in AA, don't make argument-attribute-specific queries on bundle operands. Trying to fix self hosting... llvm-svn: 289765
* Fix iterator-invalidation issueHal Finkel2016-12-151-1/+3
| | | | | | | | | Inserting a new key into a DenseMap potentially invalidates iterators into that map. Trying to fix an issue from r289755 triggering this assertion: Assertion `isHandleInSync() && "invalid iterator access!"' failed. llvm-svn: 289757
* Remove the AssumptionCacheHal Finkel2016-12-1515-500/+274
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* Make processing @llvm.assume more efficient by using operand bundlesHal Finkel2016-12-154-105/+144
| | | | | | | | | | | | | | | | | | | | | | | | | | | There was an efficiency problem with how we processed @llvm.assume in ValueTracking (and other places). The AssumptionCache tracked all of the assumptions in a given function. In order to find assumptions relevant to computing known bits, etc. we searched every assumption in the function. For ValueTracking, that means that we did O(#assumes * #values) work in InstCombine and other passes (with a constant factor that can be quite large because we'd repeat this search at every level of recursion of the analysis). Several of us discussed this situation at the last developers' meeting, and this implements the discussed solution: Make the values that an assume might affect operands of the assume itself. To avoid exposing this detail to frontends and passes that need not worry about it, I've used the new operand-bundle feature to add these extra call "operands" in a way that does not affect the intrinsic's signature. I think this solution is relatively clean. InstCombine adds these extra operands based on what ValueTracking, LVI, etc. will need and then those passes need only search the users of the values under consideration. This should fix the computational-complexity problem. At this point, no passes depend on the AssumptionCache, and so I'll remove that as a follow-up change. Differential Revision: https://reviews.llvm.org/D27259 llvm-svn: 289755
* Replace APFloatBase static fltSemantics data members with getter functionsStephan Bergmann2016-12-141-4/+4
| | | | | | | | | | | | | At least the plugin used by the LibreOffice build (<https://wiki.documentfoundation.org/Development/Clang_plugins>) indirectly uses those members (through inline functions in LLVM/Clang include files in turn using them), but they are not exported by utils/extract_symbols.py on Windows, and accessing data across DLL/EXE boundaries on Windows is generally problematic. Differential Revision: https://reviews.llvm.org/D26671 llvm-svn: 289647
* Revert "[SCEVExpand] do not hoist divisions by zero (PR30935)"Reid Kleckner2016-12-122-59/+31
| | | | | | | | | Reverts r289412. It caused an OOB PHI operand access in instcombine when ASan is enabled. Reduction in progress. Also reverts "[SCEVExpander] Add a test case related to r289412" llvm-svn: 289453
* [SCEVExpand] do not hoist divisions by zero (PR30935)Sebastian Pop2016-12-122-31/+59
| | | | | | | | | | | | | | | SCEVExpand computes the insertion point for the components of a SCEV to be code generated. When it comes to generating code for a division, SCEVexpand would not be able to check (at compilation time) all the conditions necessary to avoid a division by zero. The patch disables hoisting of expressions containing divisions by anything other than non-zero constants in order to avoid hoisting these expressions past conditions that should hold before doing the division. The patch passes check-all on x86_64-linux. Differential Revision: https://reviews.llvm.org/D27216 llvm-svn: 289412
* [TBAA] Don't generate invalid TBAA when merging nodesSanjoy Das2016-12-111-1/+5
| | | | | | | | | | | | | | Summary: Fix a corner case in `MDNode::getMostGenericTBAA` where we can sometimes generate invalid TBAA metadata. Reviewers: chandlerc, hfinkel, mehdi_amini, manmanren Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D26635 llvm-svn: 289403
* [SCEVExpander] Explicitly expand AddRec starts into loop preheaderSanjoy Das2016-12-111-5/+8
| | | | | | | | | | | | | | | | This is NFC today, but won't be once D27216 (or an equivalent patch) is in. This change fixes a design problem in SCEVExpander -- it relied on a hoisting optimization to generate correct code for add recurrences. This meant changing the hoisting optimization to not kick in under certain circumstances (to avoid speculating faulting instructions, say) would break correctness. The fix is to make the correctness requirements explicit, and have it not rely on the hoisting optimization for correctness. llvm-svn: 289397
* [InstSimplify] improve function name; NFCSanjay Patel2016-12-101-4/+6
| | | | llvm-svn: 289332
* [PM] Support invalidation of inner analysis managers from a pass over the ↵Chandler Carruth2016-12-102-3/+104
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | outer IR unit. Summary: This never really got implemented, and was very hard to test before a lot of the refactoring changes to make things more robust. But now we can test it thoroughly and cleanly, especially at the CGSCC level. The core idea is that when an inner analysis manager proxy receives the invalidation event for the outer IR unit, it needs to walk the inner IR units and propagate it to the inner analysis manager for each of those units. For example, each function in the SCC needs to get an invalidation event when the SCC gets one. The function / module interaction is somewhat boring here. This really becomes interesting in the face of analysis-backed IR units. This patch effectively handles all of the CGSCC layer's needs -- both invalidating SCC analysis and invalidating function analysis when an SCC gets invalidated. However, this second aspect doesn't really handle the LoopAnalysisManager well at this point. That one will need some change of design in order to fully integrate, because unlike the call graph, the entire function behind a LoopAnalysis's results can vanish out from under us, and we won't even have a cached API to access. I'd like to try to separate solving the loop problems into a subsequent patch though in order to keep this more focused so I've adapted them to the API and updated the tests that immediately fail, but I've not added the level of testing and validation at that layer that I have at the CGSCC layer. An important aspect of this change is that the proxy for the FunctionAnalysisManager at the SCC pass layer doesn't work like the other proxies for an inner IR unit as it doesn't directly manage the FunctionAnalysisManager and invalidation or clearing of it. This would create an ever worsening problem of dual ownership of this responsibility, split between the module-level FAM proxy and this SCC-level FAM proxy. Instead, this patch changes the SCC-level FAM proxy to work in terms of the module-level proxy and defer to it to handle much of the updates. It only does SCC-specific invalidation. This will become more important in subsequent patches that support more complex invalidaiton scenarios. Reviewers: jlebar Subscribers: mehdi_amini, mcrosier, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D27197 llvm-svn: 289317
* [Analysis] Fix typo in comment. NFCCraig Topper2016-12-091-1/+1
| | | | llvm-svn: 289171
* [LCG] Minor cleanup to the LCG walk over a function, NFC.Chandler Carruth2016-12-091-19/+22
| | | | | | | | This just hoists the check for declarations up a layer which allows various sets used in the walk to be smaller. Also moves the relevant comments to match, and catches a few other cleanups in this code. llvm-svn: 289163
* [InstSimplify] Add "X / 1.0" to SimplifyFDivInst.Zia Ansari2016-12-081-0/+6
| | | | | | Differential Revision: https://reviews.llvm.org/D27587 llvm-svn: 289153
* IR, X86: Understand !absolute_symbol metadata on global variables.Peter Collingbourne2016-12-081-4/+4
| | | | | | | | | | | | | | | | | Summary: Attaching !absolute_symbol to a global variable does two things: 1) Marks it as an absolute symbol reference. 2) Specifies the value range of that symbol's address. Teach the X86 backend to allow absolute symbols to appear in place of immediates by extending the relocImm and mov64imm32 matchers. Start using relocImm in more places where it is legal. As previously proposed on llvm-dev: http://lists.llvm.org/pipermail/llvm-dev/2016-October/105800.html Differential Revision: https://reviews.llvm.org/D25878 llvm-svn: 289087
* ConstantFolding: Don't crash when encountering vector GEPKeno Fischer2016-12-081-3/+4
| | | | | | | | | | | | | | ConstantFolding tried to cast one of the scalar indices to a vector type. Instead, use the vector type only for the first index (which is the only one allowed to be a vector) and use its scalar type otherwise. Fixes PR31250. Reviewers: majnemer Differential Revision: https://reviews.llvm.org/D27389 llvm-svn: 289073
* InstCombine: Fold bitcast of vector to FP scalarMatt Arsenault2016-12-071-23/+25
| | | | llvm-svn: 288978
* Reintroduce a check accidentally removed in 288873 to fix clang botsPhilip Reames2016-12-071-4/+12
| | | | | | I believe this is the cause of the failure, but have not been able to confirm. Note that this is a speculative fix; I'm still waiting for a full build to finish as I synced and ended up doing a clean build which takes 20+ minutes on my machine. llvm-svn: 288886
* Fix a warning introduced in r288874Philip Reames2016-12-071-1/+0
| | | | llvm-svn: 288884
* [LCG] Add basic verification of the parent set and fix bugs it uncovers.Chandler Carruth2016-12-071-4/+23
| | | | | | The existing unittests actually cover this now that we verify things. llvm-svn: 288875
* [LVI] Remove used return value from markX functionsPhilip Reames2016-12-071-28/+26
| | | | llvm-svn: 288874
* [LVI] Simplify mergeIn codePhilip Reames2016-12-071-24/+20
| | | | | | Remove the unused return type, use early return, use assignment operator. llvm-svn: 288873
* [LVI] Simplify obfuscated codePhilip Reames2016-12-071-14/+0
| | | | | | It doesn't matter why something is overdefined if it is... llvm-svn: 288871
* [InstSimplify] fixed (?) to not mutate icmpsSanjay Patel2016-12-061-10/+4
| | | | | | | | | | | | | | As Eli noted in the post-commit thread for r288833, the use of swapOperands() may not be allowed in InstSimplify, so I'm removing those calls here pending further review. The swap mutates the icmp, and there doesn't appear to be precedent for instruction mutation in InstSimplify. I didn't actually have any tests for those cases, so I'm adding a few here. llvm-svn: 288855
* [InstSimplify] add folds for and-of-icmps with same operandsSanjay Patel2016-12-061-0/+33
| | | | | | | | | | | All of these (and a few more) are already handled by InstCombine, but we shouldn't have to wait until then to simplify these because they're cheap to deal with here in InstSimplify. This is the 'and' sibling of the earlier 'or' patch: https://reviews.llvm.org/rL288833 llvm-svn: 288841
* [InstSimplify] add folds for or-of-icmps with same operandsSanjay Patel2016-12-061-2/+34
| | | | | | | | All of these (and a few more) are already handled by InstCombine, but we shouldn't have to wait until then to simplify these because they're cheap to deal with here in InstSimplify. llvm-svn: 288833
* [LCG] Add some much needed asserts and verify runs to uncoverChandler Carruth2016-12-061-4/+12
| | | | | | | | | | | | | | | | | a hilarious bug and fix it. We somehow were never verifying the RefSCCs newly formed when splitting an existing one apart, and when verifying them we weren't really checking the SCC indices mapping effectively. If we had been, it would have been blindingly obvious that right after putting something int `RC.SCCs` we should update `RC.SCCIndices` instead of `SCCIndices` which we were about to clear and rebuild anyways. =[ Anyways, this is thoroughly covered by existing tests now that we actually verify things properly. llvm-svn: 288795
* [PM] Basic cleanups to CGSCC update code, NFC.Chandler Carruth2016-12-061-41/+36
| | | | | | | Just using InstIterator, simpler loop structures, and making better use of the visit callback infrastructure. llvm-svn: 288790
* [LVI] Remove dead code in mergeInPhilip Reames2016-12-061-18/+0
| | | | | | Integers are expressed in the lattice via constant ranges. They can never be represented by constants or not-constants; those are reserved for non-integer types. This code has been dead for literaly years. llvm-svn: 288767
* [LVI] Extract a helper functionPhilip Reames2016-12-061-32/+22
| | | | | | Extracting a helper function out of solveBlockValue makes the contract around the cache much easier to understand. llvm-svn: 288766
OpenPOWER on IntegriCloud