summaryrefslogtreecommitdiffstats
path: root/llvm/test/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [AMDGPU] Fix bug introduced in 47a5c36b37f0dfukalov2019-11-071-4/+15
| | | | | | | | | | | | | | Summary: [AMDGPU] Fix bug introduced in 47a5c36b37f0 Reviewers: foad, arsenm Reviewed By: arsenm Subscribers: arsenm, kzhuravl, jvesely, wdng, nhaehnle, yaxunl, dstuttard, tpr, t-tye, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69915
* [CostModel][X86] Improve add vXi64 + fadd vXf64 reduction tests for SLMSimon Pilgrim2019-11-062-12/+12
| | | | As noted on D59710 we weren't handling the high costs of these operations on SLM.
* [CostModel][X86] Add add/fadd reduction tests for SLMSimon Pilgrim2019-11-062-0/+256
|
* [AMDGPU] Improve code size cost model (part 2)dfukalov2019-11-0610-1/+32
| | | | | | | | | | | | | | Summary: Added estimations for ShuffleVector, some cast and arithmetic instructions Reviewers: rampitec Reviewed By: rampitec Subscribers: arsenm, kzhuravl, jvesely, wdng, nhaehnle, yaxunl, dstuttard, tpr, t-tye, hiraditya, zzheng, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69629
* [X86] Lower the cost of avx512 horizontal bool and/or reductions to ↵Craig Topper2019-11-042-42/+42
| | | | | | | | | | | | | | | | | 2*log2(bitwidth)+1 for legal types. This better represents the kshift+binop we'd get for each stage before the final extract. Its likely we'll do even better by doing a kmov and a cmp with a GPR, but this is a good start. The default handling was costing a worst case single source permute shuffle of the vector before the binop. This worst case assumes the shuffle might have to be emulated with extracts and inserts. But since we know we're doing a reduction we can assume we'll get kshift lowering. There's still some room for improvement here, but this is much better than it was.
* [MustExecute] Forward iterate over conditional branchesJohannes Doerfert2019-10-311-2/+119
| | | | | | | | | | | | | | | | | | | Summary: If a conditional branch is encountered we can try to find a join block where the execution is known to continue. This means finding a suitable block, e.g., the immediate post dominator of the conditional branch, and proofing control will always reach that block. This patch implements different techniques that work with and without provided analysis. Reviewers: uenoku, sstefan1, hfinkel Subscribers: hiraditya, bollu, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D68933
* [ConstantFold] Fold extractelement of getelementptrJay Foad2019-10-281-1/+1
| | | | | | | | | | | | | | Summary: Getelementptr has vector type if any of its operands are vectors (the scalar operands being implicitly broadcast to all vector elements). Extractelement applied to a vector getelementptr can be folded by applying the extractelement in turn to all of the vector operands. Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69379
* [Analysis] Update Analysis/LazyValueAnalysis/lvi-after-jumpthreading.llRoman Lebedev2019-10-231-5/+5
| | | | | I should have updated it in 1f665046fbf3b9d47a229714f689cd941f6f1216 but i didn't even realize those tests were there.
* [SCEV] Simplify umin/max of zext and sext of the same valuePhilip Reames2019-10-194-48/+48
| | | | | | | | This is a common idiom which arises after induction variables are widened, and we have two or more exit conditions. Interestingly, we don't have instcombine or instsimplify support for this either. Differential Revision: https://reviews.llvm.org/D69006 llvm-svn: 375349
* [Test] Precommit test for D69006Philip Reames2019-10-171-0/+317
| | | | llvm-svn: 375190
* [AMDGPU] Improve code size cost modelDaniil Fukalov2019-10-173-18/+24
| | | | | | | | | | | | | | | | | | | Summary: Added estimation for zero size insertelement, extractelement and llvm.fabs operators. Updated inline/unroll parameters default values. Reviewers: rampitec, arsenm Reviewed By: arsenm Subscribers: kzhuravl, jvesely, wdng, nhaehnle, yaxunl, dstuttard, tpr, t-tye, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D68881 llvm-svn: 375109
* [MemorySSA] Update for partial unswitch.Alina Sbirlea2019-10-141-0/+22
| | | | | | | | Update MSSA for blocks cloned when doing partial unswitching. Enable additional testing with MSSA. Resolves PR43641. llvm-svn: 374850
* [Tests] Add a SCEV analysis test for llvm.widenable.conditionPhilip Reames2019-10-141-0/+45
| | | | | | Mostly because we don't appear to have one and a prototype patch I just saw would have broken the example committed. llvm-svn: 374835
* [CostModel][X86] Add CTLZ scalar costsSimon Pilgrim2019-10-141-31/+64
| | | | | | | | Add specific scalar costs for CTLZ instructions, we can't discriminate between CTLZ and CTLZ_ZERO_UNDEF so we have to assume the worst. Given how BSR is often a microcoded nightmare on some older targets we might still be underestimating it. For targets supporting LZCNT (Intel Haswell+ or AMD Fam10+), we provide overrides that assume 1cy costs. llvm-svn: 374786
* [CostModel][X86] Add CTPOP scalar costs (PR43656)Simon Pilgrim2019-10-141-4/+4
| | | | | | | | Add specific scalar costs for ctpop instructions, these are based on the llvm-mca's SLM throughput numbers (the oldest model we have). For targets supporting POPCNT, we provide overrides that assume 1cy costs. llvm-svn: 374775
* [CostModel][X86] Improve sum reduction costs.Simon Pilgrim2019-10-122-336/+141
| | | | | | | | I can't see any notable differences in costs between SSE2 and SSE42 arches for FADD/ADD reduction, so I've lowered the target to just SSE2. I've also added vXi8 sum reduction costs in line with the PSADBW codegen and discussions on PR42674. llvm-svn: 374655
* [MemorySSA] Update Phi simplification.Alina Sbirlea2019-10-101-0/+50
| | | | | | | | | | When simplifying a Phi to the unique value found incoming, check that there wasn't a Phi already created to break a cycle. If so, remove it. Resolves PR43541. Some additional nits included. llvm-svn: 374471
* [MemorySSA] Additional handling of unreachable blocks.Alina Sbirlea2019-10-101-0/+40
| | | | | | | | | | | | | | | | | | | | | Summary: Whenever we get the previous definition, the assumption is that the recursion starts ina reachable block. If the recursion starts in an unreachable block, we may recurse indefinitely. Handle this case by returning LoE if the block is unreachable. Resolves PR43426. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D68809 llvm-svn: 374447
* [MemorySSA] Make the use of moveAllAfterMergeBlocks consistent.Alina Sbirlea2019-10-091-0/+49
| | | | | | | | | | | | | | | | | | | | | | | | Summary: The rule for the moveAllAfterMergeBlocks API si for all instructions from `From` to have been moved to `To`, while keeping the CFG edges (and block terminators) unchanged. Update all the callsites for moveAllAfterMergeBlocks to follow this. Pending follow-up: since the same behavior is needed everytime, merge all callsites into one. The common denominator may be the call to `MergeBlockIntoPredecessor`. Resolves PR43569. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D68659 llvm-svn: 374177
* [CostModel][X86] Add tests for insertelement to non-immediate vector element ↵Simon Pilgrim2019-10-091-0/+74
| | | | | | indices llvm-svn: 374161
* [CostModel][X86] Add tests for extractelement from non-immediate vector ↵Simon Pilgrim2019-10-091-0/+74
| | | | | | element indices llvm-svn: 374160
* [MemorySSA] Don't hoist stores if interfering uses (as calls) exist.Alina Sbirlea2019-10-031-0/+34
| | | | llvm-svn: 373674
* [MemorySSA] Update Phi creation when inserting a Def.Alina Sbirlea2019-10-021-0/+42
| | | | | | | | | MemoryPhis should be added in the IDF of the blocks newly gaining Defs. This includes the blocks that gained a Phi and the block gaining a Def, if the block did not have one before. Resolves PR43427. llvm-svn: 373505
* [DDG] Data Dependence Graph - Root NodeBardia Mahjour2019-10-011-0/+52
| | | | | | | | | | | | | | | | | | | Summary: This patch adds Root Node to the DDG. The purpose of the root node is to create a single entry node that allows graph walk iterators to iterate through all nodes of the graph, making sure that no node is left unvisited during a graph walk (eg. SCC or DFS). Once the DDG is fully constructed it will have exactly one root node. Every node in the graph is reachable from the root. The algorithm for connecting the root node is based on depth-first-search that keeps track of visited nodes to try to avoid creating unnecessary edges. Authored By: bmahjour Reviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfert Reviewed By: Meinersbur Subscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto, ppc-slack Tag: #llvm Differential Revision: https://reviews.llvm.org/D67970 llvm-svn: 373386
* [MemorySSA] Check for unreachable blocks when getting last definition.Alina Sbirlea2019-10-011-0/+27
| | | | | | | | If a single predecessor is found, still check if the block is unreachable. The test that found this had a self loop unreachable block. Resolves PR43493. llvm-svn: 373383
* [MemorySSA] Update last_access_in_block check.Alina Sbirlea2019-10-011-0/+54
| | | | | | | | | | The check for "was there an access in this block" should be: is the last access in this block and is it not a newly inserted phi. Resolves new test in PR43438. Also fix a typo when simplifying trivial Phis to match the comment. llvm-svn: 373380
* [ConstantFolding] Fold constant calls to log2()Evandro Menezes2019-09-301-6/+4
| | | | | | | | Somehow, folding calls to `log2()` with a constant was missing. Differential revision: https://reviews.llvm.org/D67300 llvm-svn: 373262
* Revert "[SCEV] add no wrap flag for SCEVAddExpr."Tim Northover2019-09-304-7/+7
| | | | | | | | This reverts r366419 because the analysis performed is within the context of the loop and it's only valid to add wrapping flags to "global" expressions if they're always correct. llvm-svn: 373184
* [CostModel][X86] Fix SLM <2 x i64> icmp costsSimon Pilgrim2019-09-266-55/+285
| | | | | | | | SLM is 2 x slower for <2 x i64> comparison ops than other vector types, we should account for this like we do for SLM <2 x i64> add/sub/mul costs. This should remove some of the SLM codegen diffs in D43582 llvm-svn: 372954
* [MemorySSA] Avoid adding Phis in the presence of unreachable blocks.Alina Sbirlea2019-09-256-32/+83
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: If a block has all incoming values with the same MemoryAccess (ignoring incoming values from unreachable blocks), then use that incoming MemoryAccess and do not create a Phi in the first place. Revert IDF work-around added in rL372673; it should not be required unless the Def inserted is the first in its block. The patch also cleans up a series of tests, added during the many iterations on insertDef. The patch also fixes PR43438. The same issue that occurs in insertDef with "adding phis, hence the IDF of Phis is needed", can also occur in fixupDefs: the `getPreviousRecursive` call only adds Phis walking on the predecessor edges, which means there may be the case of a Phi added walking the CFG "backwards" which triggers the needs for an additional Phi in successor blocks. Such Phis are added during fixupDefs only in the presence of unreachable blocks. Hence this highlights the need to avoid adding Phis in blocks with unreachable predecessors in the first place. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67995 llvm-svn: 372932
* [MemorySSA] Update Phi insertion.Alina Sbirlea2019-09-231-0/+32
| | | | | | | | | | | | | | | | | | | | | | Summary: MemoryPhis may be needed following a Def insertion inthe IDF of all the new accesses added (phis + potentially a def). Ensure this also occurs when only the new MemoryPhis are the defining accesses. Note: The need for computing IDF here is because of new Phis added with edges incoming from unreachable code, Phis that had previously been simplified. The preferred solution is to not reintroduce such Phis. This patch is the needed fix while working on the preferred solution. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67927 llvm-svn: 372673
* [Cost][X86] Add more missing vector truncation costsSimon Pilgrim2019-09-221-49/+49
| | | | | | The AVX512 cases still need some work to correct recognise the PMOV truncation cases. llvm-svn: 372514
* [Cost][X86] Add v2i64 truncation costsSimon Pilgrim2019-09-224-105/+105
| | | | | | | | We are missing costs for a lot of truncation cases, I'm hoping to address all the 'zero cost' cases in trunc.ll I thought this was a vector widening side effect, but even before this we had some interesting LV decisions (notably over indvars) being made due to these zero costs. llvm-svn: 372498
* [SystemZ] Support z15 processor nameUlrich Weigand2019-09-203-41/+41
| | | | | | | | | | | The recently announced IBM z15 processor implements the architecture already supported as "arch13" in LLVM. This patch adds support for "z15" as an alternate architecture name for arch13. The patch also uses z15 in a number of places where we used arch13 as long as the official name was not yet announced. llvm-svn: 372435
* [Analysis] Allow -scalar-evolution-max-iterations more than onceShoaib Meenai2019-09-191-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | At present, `-scalar-evolution-max-iterations` is a `cl::Optional` option, which means it demands to be passed exactly zero or one times. Our build system makes it pretty tricky to guarantee this. We often accidentally pass the flag more than once (but always with the same value) which results in an error, after which compilation fails: ``` clang (LLVM option parsing): for the -scalar-evolution-max-iterations option: may only occur zero or one times! ``` It seems reasonable to allow -scalar-evolution-max-iterations to be passed more than once. Quoting the [[ http://llvm.org/docs/CommandLine.html#controlling-the-number-of-occurrences-required-and-allowed | documentation ]]: > The cl::ZeroOrMore modifier ... indicates that your program will allow the option to be specified zero or more times. > ... > If an option is specified multiple times for an option of the cl::opt class, only the last value will be retained. Original patch by: Enrico Bern Hardy Tanuwidjaja <etanuwid@fb.com> Differential Revision: https://reviews.llvm.org/D67512 llvm-svn: 372346
* Data Dependence Graph BasicsBardia Mahjour2019-09-183-0/+839
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is the first patch in a series of patches that will implement data dependence graph in LLVM. Many of the ideas used in this implementation are based on the following paper: D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe (1981). DEPENDENCE GRAPHS AND COMPILER OPTIMIZATIONS. This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges. The implementation takes a list of basic-blocks and only considers dependencies among instructions in those basic blocks. Any dependencies coming into or going out of instructions that do not belong to those basic blocks are ignored. The algorithm for building the graph involves the following steps in order: 1. For each instruction in the range of basic blocks to consider, create an atomic node in the resulting graph. 2. For each node in the graph establish def-use edges to/from other nodes in the graph. 3. For each pair of nodes containing memory instruction(s) create memory edges between them. This part of the algorithm goes through the instructions in lexicographical order and creates edges in reverse order if the sink of the dependence occurs before the source of it. Authored By: bmahjour Reviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfert Reviewed By: Meinersbur, fhahn, myhsu Subscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto Tag: #llvm Differential Revision: https://reviews.llvm.org/D65350 llvm-svn: 372238
* [SDA] Don't stop divergence propagation at the IPD.Jay Foad2019-09-181-0/+111
| | | | | | | | | | | | | | | | | | | Summary: This fixes B42473 and B42706. This patch makes the SDA propagate branch divergence until the end of the RPO traversal. Before, the SyncDependenceAnalysis propagated divergence only until the IPD in rpo order. RPO is incompatible with post dominance in the presence of loops. This made the SDA crash because blocks were missed in the propagation. Reviewers: foad, nhaehnle Reviewed By: foad Subscribers: jvesely, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65274 llvm-svn: 372223
* Revert "Data Dependence Graph Basics"Bardia Mahjour2019-09-173-839/+0
| | | | | | This reverts commit c98ec60993a7aa65073692b62f6d728b36e68ccd, which broke the sphinx-docs build. llvm-svn: 372168
* Data Dependence Graph BasicsBardia Mahjour2019-09-173-0/+839
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is the first patch in a series of patches that will implement data dependence graph in LLVM. Many of the ideas used in this implementation are based on the following paper: D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe (1981). DEPENDENCE GRAPHS AND COMPILER OPTIMIZATIONS. This patch contains support for a basic DDGs containing only atomic nodes (one node for each instruction). The edges are two fold: def-use edges and memory-dependence edges. The implementation takes a list of basic-blocks and only considers dependencies among instructions in those basic blocks. Any dependencies coming into or going out of instructions that do not belong to those basic blocks are ignored. The algorithm for building the graph involves the following steps in order: 1. For each instruction in the range of basic blocks to consider, create an atomic node in the resulting graph. 2. For each node in the graph establish def-use edges to/from other nodes in the graph. 3. For each pair of nodes containing memory instruction(s) create memory edges between them. This part of the algorithm goes through the instructions in lexicographical order and creates edges in reverse order if the sink of the dependence occurs before the source of it. Authored By: bmahjour Reviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfert Reviewed By: Meinersbur, fhahn, myhsu Subscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto Tag: #llvm Differential Revision: https://reviews.llvm.org/D65350 llvm-svn: 372162
* [MemorySSA] Fix phi insertion when inserting a def.Alina Sbirlea2019-09-171-0/+33
| | | | | | | | | | | | | | | | | | | Summary: When inserting a Def, the current algorithm is walking edges backward and inserting new Phis where needed. There may be additional Phis needed in the IDF of the newly inserted Def and Phis. Adding Phis in the IDF of the Def was added ina previous patch, but we may also need other Phis in the IDF of the newly added Phis. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67637 llvm-svn: 372138
* [MemorySSA] Update MSSA for non-conventional AA.Alina Sbirlea2019-09-171-0/+26
| | | | | | | | | | | | | | | | | | | Summary: Regularly when moving an instruction that may not read or write memory, the instruction is not modelled in MSSA, so not action is necessary. For a non-conventional AA pipeline, MSSA needs to explicitly check when creating accesses, so as to not model instructions that may not read and write memory. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67562 llvm-svn: 372137
* [SimplifyLibCalls] Mark known arguments with nonnullDavid Bolvansky2019-09-172-2/+2
| | | | | | | | | | | | Reviewers: efriedma, jdoerfert Reviewed By: jdoerfert Subscribers: ychen, rsmith, joerg, aaron.ballman, lebedev.ri, uenoku, jdoerfert, hfinkel, javed.absar, spatel, dmgreen, llvm-commits Differential Revision: https://reviews.llvm.org/D53342 llvm-svn: 372091
* [NFC] Test commit accessBardia Mahjour2019-09-161-0/+1
| | | | llvm-svn: 372033
* [SCEV] Add smin support to getRangeRefPhilip Reames2019-09-122-9/+15
| | | | | | | | We were failing to compute trip counts (both exact and maximum) for any loop which involved a comparison against either an umin or smin. It looks like this simply got missed when we added smin/umin to SCEV. (Note: umin was submitted separately earlier today. Turned out two folks hit this at the same time.) Differential Revision: https://reviews.llvm.org/D67514 llvm-svn: 371776
* [ConstantFolding] Expand folding of some library functionsEvandro Menezes2019-09-123-0/+306
| | | | | | | | | Expanding the folding of `nearbyint()`, `rint()` and `trunc()` to library functions, in addition to the current support for intrinsics. Differential revision: https://reviews.llvm.org/D67468 llvm-svn: 371774
* [SCEV] Support SCEVUMinExpr in getRangeRef.Florian Hahn2019-09-122-13/+13
| | | | | | | | | | | | | This patch adds support for SCEVUMinExpr to getRangeRef, similar to the support for SCEVUMaxExpr. Reviewers: sanjoy.google, efriedma, reames, nikic Reviewed By: sanjoy.google Differential Revision: https://reviews.llvm.org/D67177 llvm-svn: 371768
* Precommit tests for D67514Philip Reames2019-09-121-0/+115
| | | | llvm-svn: 371762
* [MemorySSA] Pass (for update) MSSAU when hoisting instructions.Alina Sbirlea2019-09-121-0/+26
| | | | | | | | | | | | | | Summary: Pass MSSAU to makeLoopInvariant in order to properly update MSSA. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, uabelho, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67470 llvm-svn: 371748
* [MemorySSA] Do not create memoryaccesses for debug info intrinsics.Alina Sbirlea2019-09-101-0/+54
| | | | | | | | | | | | | | | | Summary: Do not model debuginfo intrinsics in MemorySSA. Regularly these are non-memory modifying instructions. With -disable-basicaa, they were being modelled as Defs. Reviewers: george.burgess.iv Subscribers: aprantl, Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67307 llvm-svn: 371565
* [BPI] Adjust the probability for floating point unordered comparisonGuozhi Wei2019-09-101-0/+41
| | | | | | | | Since NaN is very rare in normal programs, so the probability for floating point unordered comparison should be extremely small. Current probability is 3/8, it is too large, this patch changes it to a tiny number. Differential Revision: https://reviews.llvm.org/D65303 llvm-svn: 371541
OpenPOWER on IntegriCloud