summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [SCEV] Use `SCEV::isAllOnesValue` directly; NFC.Sanjoy Das2015-10-131-8/+4
| | | | | | | Instead of `dyn_cast` ing to `SCEVConstant` and checking the contained `ConstantInteger. llvm-svn: 250251
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-132-0/+13
| | | | | | | | Currently in JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250204
* [GlobalsAA] Don't assume anything about functions that may be overriddenJames Molloy2015-10-131-2/+2
| | | | | | | | Weak linkage and friends allow a symbol to be overriden outside the code generator's model, so GlobalsAA shouldn't assume that anything it can compute about such a symbol is valid. llvm-svn: 250156
* Revert 250089 due to bot failure. It failed when building clang itself with PGO.Manman Ren2015-10-132-13/+0
| | | | llvm-svn: 250145
* [SCEV] Put some utilites in the ScalarEvolution classSanjoy Das2015-10-131-18/+22
| | | | | | | | | | | In a later commit, `SplitBinaryAdd` will be used outside `IsConstDiff`, so lift that out. And lift out `IsConstDiff` as `computeConstantDifference` to keep things clean and to avoid playing C++ access specifier games. NFC. llvm-svn: 250143
* Update the branch weight metadata in JumpThreading pass.Cong Hou2015-10-122-0/+13
| | | | | | | | In JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB). Differential revision: http://reviews.llvm.org/D10979 llvm-svn: 250089
* [LoopVectorize] Shrink integer operations into the smallest type possibleJames Molloy2015-10-121-0/+130
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | C semantics force sub-int-sized values (e.g. i8, i16) to be promoted to int type (e.g. i32) whenever arithmetic is performed on them. For targets with native i8 or i16 operations, usually InstCombine can shrink the arithmetic type down again. However InstCombine refuses to create illegal types, so for targets without i8 or i16 registers, the lengthening and shrinking remains. Most SIMD ISAs (e.g. NEON) however support vectors of i8 or i16 even when their scalar equivalents do not, so during vectorization it is important to remove these lengthens and truncates when deciding the profitability of vectorization. The algorithm this uses starts at truncs and icmps, trawling their use-def chains until they terminate or instructions outside the loop are found (or unsafe instructions like inttoptr casts are found). If the use-def chains starting from different root instructions (truncs/icmps) meet, they are unioned. The demanded bits of each node in the graph are ORed together to form an overall mask of the demanded bits in the entire graph. The minimum bitwidth that graph can be truncated to is the bitwidth minus the number of leading zeroes in the overall mask. The intention is that this algorithm should "first do no harm", so it will never insert extra cast instructions. This is why the use-def graphs are unioned, so that subgraphs with different minimum bitwidths do not need casts inserted between them. This algorithm works hard to reduce compile time impact. DemandedBits are only queried if there are extends of illegal types and if a truncate to an illegal type is seen. In the general case, this results in a simple linear scan of the instructions in the loop. No non-noise compile time impact was seen on a clang bootstrap build. llvm-svn: 250032
* SCEV: Allow simple AddRec * Parameter products in delinearizationTobias Grosser2015-10-122-11/+85
| | | | | | | | | This patch also allows the -delinearize pass to delinearize expressions that do not have an outermost SCEVAddRec expression. The SCEV::delinearize infrastructure allowed this since r240952, but the -delinearize pass was not updated yet. llvm-svn: 250018
* Analysis: Remove implicit ilist iterator conversionsDuncan P. N. Exon Smith2015-10-1022-99/+99
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Remove implicit ilist iterator conversions from LLVMAnalysis. I came across something really scary in `llvm::isKnownNotFullPoison()` which relied on `Instruction::getNextNode()` being completely broken (not surprising, but scary nevertheless). This function is documented (and coded to) return `nullptr` when it gets to the sentinel, but with an `ilist_half_node` as a sentinel, the sentinel check looks into some other memory and we don't recognize we've hit the end. Rooting out these scary cases is the reason I'm removing the implicit conversions before doing anything else with `ilist`; I'm not at all surprised that clients rely on badness. I found another scary case -- this time, not relying on badness, just bad (but I guess getting lucky so far) -- in `ObjectSizeOffsetEvaluator::compute_()`. Here, we save out the insertion point, do some things, and then restore it. Previously, we let the iterator auto-convert to `Instruction*`, and then set it back using the `Instruction*` version: Instruction *PrevInsertPoint = Builder.GetInsertPoint(); /* Logic that may change insert point */ if (PrevInsertPoint) Builder.SetInsertPoint(PrevInsertPoint); The check for `PrevInsertPoint` doesn't protect correctly against bad accesses. If the insertion point has been set to the end of a basic block (i.e., `SetInsertPoint(SomeBB)`), then `GetInsertPoint()` returns an iterator pointing at the list sentinel. The version of `SetInsertPoint()` that's getting called will then call `PrevInsertPoint->getParent()`, which explodes horribly. The only reason this hasn't blown up is that it's fairly unlikely the builder is adding to the end of the block; usually, we're adding instructions somewhere before the terminator. llvm-svn: 249925
* [WinEH] Delete the old landingpad implementation of Windows EHReid Kleckner2015-10-091-188/+0
| | | | | | | | | | | The new implementation works at least as well as the old implementation did. Also delete the associated preparation tests. They don't exercise interesting corner cases of the new implementation. All the codegen tests of the EH tables have already been ported. llvm-svn: 249918
* ValueTracking: use getAlignment in isAlignedArtur Pilipenko2015-10-091-14/+1
| | | | | | | | Reviewed By: reames Differential Revision: http://reviews.llvm.org/D13517 llvm-svn: 249841
* [SCEV] Call `StrengthenNoWrapFlags` after `GroupByComplexity`; NFCISanjoy Das2015-10-091-4/+4
| | | | | | | | | The current implementation of `StrengthenNoWrapFlags` is agnostic to the order of `Ops`, so this commit should not change anything semantic. An upcoming change will make `StrengthenNoWrapFlags` sensitive to the order of `Ops`. llvm-svn: 249802
* [SCEV] Bring some methods up to coding style; NFCSanjoy Das2015-10-081-32/+27
| | | | | | | | - Start methods with lower case - Reflow a comment - Delete header comment repeated in .cpp file llvm-svn: 249716
* [SCEV] Remove comment repeated in cpp file; NFCSanjoy Das2015-10-081-5/+0
| | | | llvm-svn: 249713
* [SCEV] Pick backedge values for phi nodes correctlySanjoy Das2015-10-081-10/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively` assumed all phi nodes in the loop header have the same order of incoming values. This is not correct, and this commit changes `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively` to lookup the backedge value of a phi node using the loop's latch block. Unfortunately, there is still some code duplication `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`. At some point in the future we should extract out a helper class / method that can evolve constant evolution phi nodes across iterations. Fixes 25060. Thanks to Mattias Eriksson for the spot-on analysis! Depends on D13457. Reviewers: atrick, hfinkel Subscribers: materi, llvm-commits Differential Revision: http://reviews.llvm.org/D13458 llvm-svn: 249712
* [ValueTracking] teach computeKnownBits that a fabs() clears sign bitsSanjay Patel2015-10-081-2/+10
| | | | | | | | | | | | | This was requested in D13076: if we're going to canonicalize to fabs(), ValueTracking should know that fabs() clears sign bits. In this patch (as in D13076), we're not handling vectors yet even though computeKnownBits' fabs() case itself should be vector-ready via the splat in this patch. Fixing this will require follow-on patches to correct other logic that uses 'getScalarType'. Differential Revision: http://reviews.llvm.org/D13222 llvm-svn: 249701
* Compute demanded bits for icmp instructionsJames Molloy2015-10-081-0/+7
| | | | | | | | | Instead of bailing out when we see an icmp, we can instead at least say that if the upper bits of both operands are known zero, they are not demanded. This doesn't help with signed comparisons, but it's at least better than bailing out. llvm-svn: 249687
* Treat Mul just like Add and SubtractJames Molloy2015-10-081-0/+12
| | | | | | | | | | Like adds and subtracts, muls ripple only to the left so we can use the same logic. While we're here, add a print method to DemandedBits so it can be used with -analyze, which we'll use in the testcase. llvm-svn: 249686
* Make demanded bits lazyJames Molloy2015-10-081-7/+19
| | | | | | | | | | The algorithm itself is still eager, but it doesn't get run until a query function is called. This greatly reduces the compile-time impact of requiring DemandedBits when at runtime it is not often used. NFCI. llvm-svn: 249685
* [SCEV] Check `Pred` first in isKnownPredicateViaSplittingSanjoy Das2015-10-081-2/+2
| | | | | | | Comparing `Pred` with `ICmpInst::ICMP_ULT` is cheaper that memory access -- do that check before loading / storing `ProvingSplitPredicate`. llvm-svn: 249654
* [SCEV] Use `auto *` instead of `auto`; NFCISanjoy Das2015-10-081-7/+7
| | | | | | (As prescribed by the coding style document) llvm-svn: 249653
* Revert "Revert "This patch builds on top of D13378 to handle constant ↵Mehdi Amini2015-10-071-0/+5
| | | | | | | | | | condition."" This reverts commit r249528 and reapply r249431. The fix for the fallout has been commited in r249575. From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 249581
* [SCEV] Use some C++11'ism, NFCSanjoy Das2015-10-071-26/+21
| | | | | | | | | | Summary: Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13457 llvm-svn: 249574
* Teach computeKnownBits to use new align attribute/metadataArtur Pilipenko2015-10-071-3/+12
| | | | | | | | Reviewed By: reames Differential Revision: http://reviews.llvm.org/D13470 llvm-svn: 249557
* Revert "This patch builds on top of D13378 to handle constant condition."James Molloy2015-10-071-5/+0
| | | | | | This reverts commit r249431. This caused failures in sqlite3: http://lab.llvm.org:8011/builders/clang-native-arm-lnt/builds/14453 llvm-svn: 249528
* Fix Clang-tidy modernize-use-nullptr warnings in source directories and ↵Hans Wennborg2015-10-061-2/+3
| | | | | | | | | | generated files; other minor cleanups. Patch by Eugene Zelenko! Differential Revision: http://reviews.llvm.org/D13321 llvm-svn: 249482
* [WinEH] Recognize CoreCLR personality functionJoseph Tremoulet2015-10-061-0/+1
| | | | | | | | | | | | | | | Summary: - Add CoreCLR to if/else ladders and switches as appropriate. - Rename isMSVCEHPersonality to isFuncletEHPersonality to better reflect what it captures. Reviewers: majnemer, andrew.w.kaylor, rnk Subscribers: pgavlin, AndyAyers, llvm-commits Differential Revision: http://reviews.llvm.org/D13449 llvm-svn: 249455
* Extend known bits to understand @llvm.bswapPhilip Reames2015-10-061-0/+6
| | | | | | | | | | This is a cleaned up patch from the one written by John Regehr based on the findings of the Souper superoptimizer. When writing tests, I was surprised to find that instsimplify apparently doesn't know how to collapse bit test sequences based purely on known bits. This required me to split my tests across both instsimplify and instcombine. Differential Revision: http://reviews.llvm.org/D13250 llvm-svn: 249453
* Fix pr25040 - Handle vectors of i1s in recently added implication codePhilip Reames2015-10-061-4/+11
| | | | | | | | As mentioned in the bug, I'd missed the presence of a getScalarType in the caller of the new implies method. As a result, when we ended up with a implication over two vectors, we'd trip an assert and crash. Differential Revision: http://reviews.llvm.org/D13441 llvm-svn: 249442
* This patch builds on top of D13378 to handle constant condition.Mehdi Amini2015-10-061-0/+5
| | | | | | | | | | | | | | | | | | | | With this patch, clang -O3 optimizes correctly providing > 1000x speedup on this artificial benchmark): for (a=0; a<n; a++) for (b=0; b<n; b++) for (c=0; c<n; c++) for (d=0; d<n; d++) for (e=0; e<n; e++) for (f=0; f<n; f++) x++; From test-suite/SingleSource/Benchmarks/Shootout/nestedloop.c Reviewers: sanjoyd Differential Revision: http://reviews.llvm.org/D13390 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 249431
* Try to appease MSVC, NFCI.Sanjoy Das2015-10-031-90/+91
| | | | | | | | This time by lifting the lambda's in `createNodeFromSelectLikePHI` to the file scope. Looks like there are differences in capture rules between clang and MSVC? llvm-svn: 249222
* Try to appease the MSVC bots, NFCI.Sanjoy Das2015-10-031-1/+1
| | | | llvm-svn: 249219
* Try to appease the MSVC bots, NFC.Sanjoy Das2015-10-021-1/+2
| | | | llvm-svn: 249216
* [SCEV] Recognize simple br-phi patternsSanjoy Das2015-10-021-141/+284
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Teach SCEV to match patterns like ``` br %cond, label %left, label %right left: br label %merge right: br label %merge merge: V = phi [ %x, %left ], [ %y, %right ] ``` as "select %cond, %x, %y". Before this SCEV would match PHI nodes exclusively to add recurrences. This addresses PR25005. Reviewers: joker.eph, joker-eph, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13378 llvm-svn: 249211
* inariant.group handling in GVNPiotr Padlewski2015-10-021-0/+69
| | | | | | | | | | | | The most important part required to make clang devirtualization works ( ͡°͜ʖ ͡°). The code is able to find non local dependencies, but unfortunatelly because the caller can only handle local dependencies, I had to add some restrictions to look for dependencies only in the same BB. http://reviews.llvm.org/D12992 llvm-svn: 249196
* [SCEV] Refactor out a createNodeForSelectSanjoy Das2015-10-021-88/+100
| | | | | | | | | | | | | Summary: We will shortly re-use this for select-like br-phi pairs. Reviewers: atrick, joker-eph, joker.eph Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13377 llvm-svn: 249177
* [SCEV] Try to prove predicates by splitting themSanjoy Das2015-10-021-3/+33
| | | | | | | | | | | | | | | | | | | | | Summary: This change teaches SCEV that to prove `A u< B` it is sufficient to prove each of these facts individually: - B >= 0 - A s< B - A >= 0 In practice, SCEV sometimes finds it easier to prove these facts individually than to prove `A u< B` as one atomic step. Reviewers: reames, atrick, nlewycky, hfinkel Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13042 llvm-svn: 249168
* Refactor computeKnownBits alignment handling codeArtur Pilipenko2015-09-301-53/+38
| | | | | | | | Reviewed By: reames, hfinkel Differential Revision: http://reviews.llvm.org/D12958 llvm-svn: 248892
* [ValueTracking] Lower dom-conditions-dom-blocks and dom-conditions-max-uses ↵Igor Laevsky2015-09-291-2/+2
| | | | | | | | | | thresholds On some of our benchmarks this change shows about 50% compile time improvement without any noticeable performance difference. Differential Revision: http://reviews.llvm.org/D13248 llvm-svn: 248801
* [ValueTracking] Teach isKnownNonZero about monotonically increasing PHIsJames Molloy2015-09-291-0/+20
| | | | | | | | If a PHI starts at a non-negative constant, monotonically increases (only adds of a constant are supported at the moment) and that add does not wrap, then the PHI is known never to be zero. llvm-svn: 248796
* [SCEV] Don't crash on pointer comparisonsSanjoy Das2015-09-281-2/+1
| | | | | | | | | | | | `ScalarEvolution::isImpliedCondOperandsViaNoOverflow` tries to cast the operand type of the comparison it is given to an `IntegerType`. This is incorrect because it could actually be simplifying a comparison between two pointers. Switch it to using `getTypeSizeInBits` instead, which does the right thing for both pointers and integers. Fixed PR24956. llvm-svn: 248743
* Introduce !align metadata for load instructionArtur Pilipenko2015-09-281-0/+5
| | | | | | | | Reviewed By: hfinkel Differential Revision: http://reviews.llvm.org/D12853 llvm-svn: 248721
* [InstSimplify] Fold simple known implications to truePhilip Reames2015-09-281-0/+47
| | | | | | | | | | This was split off of http://reviews.llvm.org/D13040 to make it easier to test the correctness of the implication logic. For the moment, this only handles a single easy case which shows up when eliminating and combining range checks. In the (near) future, I plan to extend this for other cases which show up in range checks, but I wanted to make those changes incrementally once the framework was in place. At the moment, the implication logic will be used by three places. One in InstSimplify (this review) and two in SimplifyCFG (http://reviews.llvm.org/D13040 & http://reviews.llvm.org/D13070). Can anyone think of other locations this style of reasoning would make sense? Differential Revision: http://reviews.llvm.org/D13074 llvm-svn: 248719
* [SCEV] identical instructions don't compute equal valuesSanjoy Das2015-09-271-1/+8
| | | | | | | | | | | | Before this change `HasSameValue` would return true for distinct `alloca` instructions if they happened to be allocating the same type (`alloca` instructions are not specified as reading memory). This change adds an explicit whitelist of instruction types for which "identical" instructions compute the same value. Fixes PR24952. llvm-svn: 248690
* [Bug 24848] Use range metadata to constant fold comparisons between two valuesChen Li2015-09-261-0/+26
| | | | | | | | | | | | | | | Summary: This is the second part of fixing bug 24848 https://llvm.org/bugs/show_bug.cgi?id=24848. If both operands of a comparison have range metadata, they should be used to constant fold the comparison. Reviewers: sanjoy, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13177 llvm-svn: 248650
* [SCEV] Reapply 'Teach isLoopBackedgeGuardedByCond to exploit trip counts'Sanjoy Das2015-09-251-0/+16
| | | | | | | | | | | | | | | | | | | | | | Summary: If the trip count of a specific backedge is `N`, then we know that backedge is effectively guarded by the condition `{0,+,1} u< N`. This change teaches SCEV to use this condition to prove things in `isLoopBackedgeGuardedByCond`. Depends on D12948 Depends on D12949 The original checkin, r248608 had to be backed out due to an issue with a ObjCXX unit test. That issue is now fixed, so re-landing. Reviewers: atrick, reames, majnemer, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12950 llvm-svn: 248638
* [SCEV] Reapply 'Exploit A < B => (A+K) < (B+K) when possible'Sanjoy Das2015-09-251-0/+143
| | | | | | | | | | | | | | | | | | | | | | | Summary: This change teaches SCEV's `isImpliedCond` two new identities: A u< B u< -C => (A + C) u< (B + C) A s< B s< INT_MIN - C => (A + C) s< (B + C) While these are useful on their own, they're really intended to support D12950. The original checkin, r248606 had to be backed out due to an issue with a ObjCXX unit test. That issue is now fixed, so re-landing. Reviewers: atrick, reames, majnemer, nlewycky, hfinkel Subscribers: aadg, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12948 llvm-svn: 248637
* Revert two SCEV changes that caused test failures in clang.Sanjoy Das2015-09-251-159/+0
| | | | | | r248606: "[SCEV] Exploit A < B => (A+K) < (B+K) when possible" r248608: "[SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts." llvm-svn: 248614
* more space; NFCSanjay Patel2015-09-251-0/+1
| | | | llvm-svn: 248609
* [SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts.Sanjoy Das2015-09-251-0/+16
| | | | | | | | | | | | | | | | | | | Summary: If the trip count of a specific backedge is `N`, then we know that backedge is effectively guarded by the condition `{0,+,1} u< N`. This change teaches SCEV to use this condition to prove things in `isLoopBackedgeGuardedByCond`. Depends on D12948 Depends on D12949 Reviewers: atrick, reames, majnemer, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12950 llvm-svn: 248608
OpenPOWER on IntegriCloud