summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Refactor callsite cost computation into a helper function /NFCXinliang David Li2017-05-021-29/+35
| | | | | | | Makes code more readable. The function will also be used by the partial inlining's cost analysis. llvm-svn: 301899
* Revert r301880George Burgess IV2017-05-011-13/+0
| | | | | | | | | This change caused buildbot failures, apparently because we're not passing around types that InstSimplify is used to seeing. I'm not overly familiar with InstSimplify, so I'm reverting this until I can figure out what exactly is wrong. llvm-svn: 301885
* [InstSimplify] Handle selects of GEPs with 0 offsetGeorge Burgess IV2017-05-011-0/+13
| | | | | | | | | In particular (since it wouldn't fit nicely in the summary): (select (icmp eq V 0) P (getelementptr P V)) -> (getelementptr P V) Differential Revision: https://reviews.llvm.org/D31435 llvm-svn: 301880
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-013-8/+11
| | | | | | This relands r301424. llvm-svn: 301812
* Rename isKnownNotFullPoison to programUndefinedIfPoison; NFCSanjoy Das2017-04-302-2/+3
| | | | | | | | | | | | | | | | | Summary: programUndefinedIfPoison makes more sense, given what the function does; and I'm about to add a function with a name similar to isKnownNotFullPoison (so do the rename to avoid confusion). Reviewers: broune, majnemer, bjarke.roune Reviewed By: broune Subscribers: mcrosier, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D30444 llvm-svn: 301776
* InstructionSimplify: Canonicalize shuffle operands. NFC-ish.Zvi Rackover2017-04-301-20/+29
| | | | | | | | | | | | | | | | | | | | | | | | Summary: Apply canonicalization rules: 1. Input vectors with no elements selected from can be replaced with undef. 2. If only one input vector is constant it shall be the second one. This allows constant-folding to cover more ad-hoc simplifications that were in place and avoid duplication for RHS and LHS checks. There are more rules we may want to add in the future when we see a justification. e.g. mask elements that select undef elements can be replaced with undef. Reviewers: spatel, RKSimon, andreadb, davide Reviewed By: spatel, RKSimon Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32338 llvm-svn: 301766
* InstructionSimplify: One getShuffleMask() replacing multiple getMaskValue(). ↵Zvi Rackover2017-04-301-6/+9
| | | | | | | | | | | | | | | | NFC. Summary: This is a preparatory step for D32338. Reviewers: RKSimon, spatel Reviewed By: RKSimon, spatel Subscribers: spatel, llvm-commits Differential Revision: https://reviews.llvm.org/D32388 llvm-svn: 301765
* InstructionSimplify: Simplify a shuffle with a undef mask to undefZvi Rackover2017-04-301-0/+3
| | | | | | | | | | | | | | | | Summary: Following the discussion in pr32486, adding the simplification: shuffle %x, %y, undef -> undef Reviewers: spatel, RKSimon, andreadb, davide Reviewed By: spatel Subscribers: jroelofs, davide, llvm-commits Differential Revision: https://reviews.llvm.org/D32293 llvm-svn: 301764
* [KnownBits] Add methods for determining if the known bits represent a ↵Craig Topper2017-04-291-45/+45
| | | | | | | | | | | | | | | | negative/nonnegative number and add methods for changing the negative/nonnegative state Summary: This patch adds isNegative, isNonNegative for querying whether the sign bit is known. It also adds makeNegative and makeNonNegative for controlling the sign bit. Reviewers: RKSimon, spatel, davide Reviewed By: RKSimon Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32651 llvm-svn: 301747
* [SCEV] Use early exit in createAddRecFromPHI. NFC.Michael Zolotukhin2017-04-281-109/+110
| | | | llvm-svn: 301703
* [ValueTracking] Teach isSafeToSpeculativelyExecute() about the speculatable ↵Matt Arsenault2017-04-281-0/+6
| | | | | | | | attribute Patch by Tom Stellard llvm-svn: 301688
* Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin2017-04-285-15/+40
| | | | llvm-svn: 301673
* Use Argument::hasAttribute and AttributeList::ReturnIndex moreReid Kleckner2017-04-281-1/+1
| | | | | | | | | | | This eliminates many extra 'Idx' induction variables in loops over arguments in CodeGen/ and Target/. It also reduces the number of places where we assume that ReturnIndex is 0 and that we should add one to argument numbers to get the corresponding attribute list index. NFC llvm-svn: 301666
* [APInt] Add clearSignBit method. Use it and setSignBit in a few places. NFCICraig Topper2017-04-281-2/+2
| | | | llvm-svn: 301656
* [LazyValueInfo] Fix typo in comment. NFCCraig Topper2017-04-281-1/+1
| | | | llvm-svn: 301655
* [ValueTracking] Use APInt::isSubsetOf and APInt::intersects. NFCCraig Topper2017-04-281-2/+2
| | | | llvm-svn: 301654
* [InlineCost] Improve the cost heuristic for SwitchJun Bum Lim2017-04-282-5/+77
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The motivation example is like below which has 13 cases but only 2 distinct targets ``` lor.lhs.false2: ; preds = %if.then switch i32 %Status, label %if.then27 [ i32 -7012, label %if.end35 i32 -10008, label %if.end35 i32 -10016, label %if.end35 i32 15000, label %if.end35 i32 14013, label %if.end35 i32 10114, label %if.end35 i32 10107, label %if.end35 i32 10105, label %if.end35 i32 10013, label %if.end35 i32 10011, label %if.end35 i32 7008, label %if.end35 i32 7007, label %if.end35 i32 5002, label %if.end35 ] ``` which is compiled into a balanced binary tree like this on AArch64 (similar on X86) ``` .LBB853_9: // %lor.lhs.false2 mov w8, #10012 cmp w19, w8 b.gt .LBB853_14 // BB#10: // %lor.lhs.false2 mov w8, #5001 cmp w19, w8 b.gt .LBB853_18 // BB#11: // %lor.lhs.false2 mov w8, #-10016 cmp w19, w8 b.eq .LBB853_23 // BB#12: // %lor.lhs.false2 mov w8, #-10008 cmp w19, w8 b.eq .LBB853_23 // BB#13: // %lor.lhs.false2 mov w8, #-7012 cmp w19, w8 b.eq .LBB853_23 b .LBB853_3 .LBB853_14: // %lor.lhs.false2 mov w8, #14012 cmp w19, w8 b.gt .LBB853_21 // BB#15: // %lor.lhs.false2 mov w8, #-10105 add w8, w19, w8 cmp w8, #9 // =9 b.hi .LBB853_17 // BB#16: // %lor.lhs.false2 orr w9, wzr, #0x1 lsl w8, w9, w8 mov w9, #517 and w8, w8, w9 cbnz w8, .LBB853_23 .LBB853_17: // %lor.lhs.false2 mov w8, #10013 cmp w19, w8 b.eq .LBB853_23 b .LBB853_3 .LBB853_18: // %lor.lhs.false2 mov w8, #-7007 add w8, w19, w8 cmp w8, #2 // =2 b.lo .LBB853_23 // BB#19: // %lor.lhs.false2 mov w8, #5002 cmp w19, w8 b.eq .LBB853_23 // BB#20: // %lor.lhs.false2 mov w8, #10011 cmp w19, w8 b.eq .LBB853_23 b .LBB853_3 .LBB853_21: // %lor.lhs.false2 mov w8, #14013 cmp w19, w8 b.eq .LBB853_23 // BB#22: // %lor.lhs.false2 mov w8, #15000 cmp w19, w8 b.ne .LBB853_3 ``` However, the inline cost model estimates the cost to be linear with the number of distinct targets and the cost of the above switch is just 2 InstrCosts. The function containing this switch is then inlined about 900 times. This change use the general way of switch lowering for the inline heuristic. It etimate the number of case clusters with the suitability check for a jump table or bit test. Considering the binary search tree built for the clusters, this change modifies the model to be linear with the size of the balanced binary tree. The model is off by default for now : -inline-generic-switch-cost=false This change was originally proposed by Haicheng in D29870. Reviewers: hans, bmakam, chandlerc, eraman, haicheng, mcrosier Reviewed By: hans Subscribers: joerg, aemerson, llvm-commits, rengolin Differential Revision: https://reviews.llvm.org/D31085 llvm-svn: 301649
* [ValueTracking] Convert computeKnownBitsFromRangeMetadata to use KnownBits ↵Craig Topper2017-04-281-9/+8
| | | | | | struct. llvm-svn: 301626
* Kill the old Simplify* APIs, leave SimplifyInstruction for the momentDaniel Berlin2017-04-261-260/+0
| | | | llvm-svn: 301467
* PHITransAddr: Use new SimplifyQuery based API.Daniel Berlin2017-04-261-2/+2
| | | | llvm-svn: 301465
* [ValueTracking] Introduce a KnownBits struct to wrap the two APInts for ↵Craig Topper2017-04-266-507/+473
| | | | | | | | | | | | | | | | computeKnownBits This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows us to treat them as more of a unit. Initially I've just altered the signatures of computeKnownBits and InstCombine's simplifyDemandedBits to pass a KnownBits reference instead of two separate APInt references. I'll do similar to the SelectionDAG version of computeKnownBits/simplifyDemandedBits as a separate patch. I've added a constructor that allows initializing both APInts to the same bit width with a starting value of 0. This reduces the repeated pattern of initializing both APInts. Once place default constructed the APInts so I added a default constructor for those cases. Going forward I would like to add more methods that will work on the pairs. For example trunc, zext, and sext occur on both APInts together in several places. We should probably add a clear method that can be used to clear both pieces. Maybe a method to check for conflicting information. A method to return (Zero|One) so we don't write it out everywhere. Maybe a method for (Zero|One).isAllOnesValue() to determine if all bits are known. I'm sure there are many other methods we can come up with. Differential Revision: https://reviews.llvm.org/D32376 llvm-svn: 301432
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-263-12/+10
| | | | | | | | | | | | Commits were: "Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts" "Add a new WeakVH value handle; NFC" "Rename WeakVH to WeakTrackingVH; NFC" The changes assumed pointers are 8 byte aligned on all architectures. llvm-svn: 301429
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-04-263-10/+12
| | | | | | | | | | | | | | | | Summary: I plan to use WeakVH to mean "nulls itself out on deletion, but does not track RAUW" in a subsequent commit. Reviewers: dblaikie, davide Reviewed By: davide Subscribers: arsenm, mehdi_amini, mcrosier, mzolotukhin, jfb, llvm-commits, nhaehnle Differential Revision: https://reviews.llvm.org/D32266 llvm-svn: 301424
* InstructionSimplify: Use braced initializer list for SimplifyQuery creationDaniel Berlin2017-04-261-45/+36
| | | | llvm-svn: 301381
* InstructionSimplify: Have SimplifyFPBinOp pass FastMathFlags by value, like ↵Daniel Berlin2017-04-261-2/+2
| | | | | | we do everywhere else llvm-svn: 301380
* InstructionSimplify: End our long national nightmare of ever-growing ↵Daniel Berlin2017-04-261-158/+287
| | | | | | | | | | | | | | | | | | | | | Simplify* arguments. Summary: Expose the internal query structure, start using it. Note: This is the most minimal change possible i could create. I have trivial followups, like fixing the one use of const FastMathFlags &, the renaming of CtxI to be consistent, etc. This should be NFC. Reviewers: majnemer, davide Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32448 llvm-svn: 301379
* [APInt] Use isSubsetOf, intersects, and bit counting methods to reduce ↵Craig Topper2017-04-252-7/+6
| | | | | | | | | | | | | | temporary APInts This patch uses various APInt methods to reduce temporary APInt creation. This should be all of the unrelated cleanups that got buried in D32376(creating a KnownBits struct) as well as some pointed out by Simon during the review of that. Plus a few improvements to use counting instead of masking. I've left out any places where we do something like (KnownZero & KnownOne) != 0 as I plan to add a helper method to KnownBits to ask that question and didn't want to thrash that code an additional time. Differential Revision: https://reviews.llvm.org/D32495 llvm-svn: 301338
* [InstSimplify] Handle (~A & ~B) | (~A ^ B) -> ~A ^ BCraig Topper2017-04-251-4/+10
| | | | | | | | | | The code Sanjay Patel moved over from InstCombine doesn't work properly if the 'and' has both inputs as nots because we used a commuted op matcher on the 'and' first. But this will bind to the first 'not' on 'and' when there could be two 'not's. InstCombine could rely on DeMorgan to ensure the 'and' wouldn't have two 'not's eventually, but InstSimplify can't rely on that. This patch matches the xor first then checks for the ands and allows a not of either operand of the xor. Differential Revision: https://reviews.llvm.org/D32458 llvm-svn: 301329
* [ValueTracking] Use APInt::operator|=(uint64_t) instead of creating a ↵Craig Topper2017-04-251-2/+2
| | | | | | temporary APInt. NFC llvm-svn: 301325
* [ValueTracking] Use APInt instead of auto. NFCCraig Topper2017-04-251-1/+1
| | | | | | This is a pre-commit for a patch I'm working on to turn KnownZero/One into a struct. Once I do that the type here will be less obvious. llvm-svn: 301324
* [ValueTracking] Use BitWidth local variable instead of re-reading it from ↵Craig Topper2017-04-251-1/+1
| | | | | | | | KnownZero. NFC This is a pre-commit for a patch that I'm working on to merge KnownZero/KnownOne into a KnownBits struct which would have had to touch this line. llvm-svn: 301323
* [IVUsers] Don't bail out of normalizing non-affine add recsSanjoy Das2017-04-251-11/+1
| | | | | | | | | | | | | | | | | Summary: In a previous change I changed SCEV's normalization / denormalization to work with non-affine add recs. So the bailout in IVUsers can be removed. Reviewers: atrick, efriedma Reviewed By: atrick Subscribers: davide, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D32105 llvm-svn: 301298
* Teach SCEV normalization to de/normalize non-affine add recsSanjoy Das2017-04-251-32/+39
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Before this change, SCEV Normalization would incorrectly normalize non-affine add recurrences. To work around this there was (still is) a check in place to make sure we only tried to normalize affine add recurrences. We recently found a bug in aforementioned check to bail out of normalizing non-affine add recurrences. However, instead of fixing the bailout, I have decided to teach SCEV normalization to work correctly with non-affine add recurrences, making the bailout unnecessary (I'll remove it in a subsequent change). I've also added some unit tests (which would have failed before this change). Reviewers: atrick, sunfish, efriedma Reviewed By: atrick Subscribers: mcrosier, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D32104 llvm-svn: 301281
* [InstSimplify] use ConstantRange to simplify more and-of-icmpsSanjay Patel2017-04-241-2/+9
| | | | | | | | | | | | | We can simplify (and (icmp X, C1), (icmp X, C2)) to one of the icmps in many cases. I had to check some of these with Alive to prove to myself it's right, but everything seems to check out. Eg, the code in instcombine was completely ignoring predicates with mismatched signedness. Handling or-of-icmps would be a follow-up step. Differential Revision: https://reviews.llvm.org/D32143 llvm-svn: 301260
* Handle invariant.group.barrier in BasicAAPiotr Padlewski2017-04-241-6/+6
| | | | | | | | | | | | | | | | | | | | | Summary: llvm.invariant.group.barrier returns pointer that mustalias pointer it takes. It can't be marked with `returned` attribute, because it would be remove easily. The other reason is that only Alias Analysis can know about this, because if any other pass would know it, then the result would be replaced with it's argument, which would be invalid. We can think about returned pointer as something that mustalias, but it doesn't have to be bitwise the same as the argument. Reviewers: dberlin, chandlerc, hfinkel, sanjoy Subscribers: reames, nlewycky, rsmith, anna, amharc Differential Revision: https://reviews.llvm.org/D31585 llvm-svn: 301227
* [InstSimplify] move (A & ~B) | (A ^ B) -> (A ^ B) from InstCombineSanjay Patel2017-04-241-0/+13
| | | | | | | | | | | This is a straight cut and paste, but there's a bigger problem: if this fold exists for simplifyOr, there should be a DeMorganized version for simplifyAnd. But more than that, we have a patchwork of ad hoc logic optimizations in InstCombine. There should be some structure to ensure that we're not missing sibling folds across and/or/xor. llvm-svn: 301213
* [DomPrinter] Add a way to programmatically dump a dot representation.Davide Italiano2017-04-241-0/+16
| | | | | | Differential Revision: https://reviews.llvm.org/D32145 llvm-svn: 301205
* Revert "[SCEV] Enable SCEV verification by default in EXPENSIVE_CHECKS builds"Sanjoy Das2017-04-241-10/+3
| | | | | | | This reverts commit r301150. It breaks CodeGen/Hexagon/hwloop-wrap2.ll, reverting while I investigate. llvm-svn: 301154
* Fix unused variables / fields warnings in release buildsSanjoy Das2017-04-241-0/+6
| | | | llvm-svn: 301151
* [SCEV] Enable SCEV verification by default in EXPENSIVE_CHECKS buildsSanjoy Das2017-04-241-3/+10
| | | | llvm-svn: 301150
* [SCEV] Fix exponential time complexity by cachingSanjoy Das2017-04-241-19/+63
| | | | llvm-svn: 301149
* [SCEV] Move towards a verifier without false positivesSanjoy Das2017-04-231-68/+59
| | | | | | | | | | | | | | | This change reboots SCEV's current (off by default) verification logic to avoid false failures. Instead of stringifying trip counts, it maps old and new trip counts to the same ScalarEvolution "universe" and asks ScalarEvolution to compute the difference between them. If the difference comes out to be a non-zero constant, then (barring some corner cases) we *know* we messed up. I've not yet enabled this by default since it hits an exponential time issue in SCEV, but once I fix that, I'll flip it on by default in EXPENSIVE_CHECKS builds. llvm-svn: 301146
* Remove a repeated comment line. NFC.Easwaran Raman2017-04-211-1/+0
| | | | llvm-svn: 301059
* [ValueTracking] Use APInt::setAllBits and APInt::intersects to simplify some ↵Craig Topper2017-04-211-3/+4
| | | | | | code. NFC llvm-svn: 300997
* [MSSA] Clean up the updater a bit. NFCGeorge Burgess IV2017-04-211-5/+4
| | | | | | | | - Mark an internal function static - Remove the llvm namespace (just holding on to the `using namespace llvm;` Works on My Machine(TM)) llvm-svn: 300947
* Revert r300746 (SCEV analysis for or instructions).Eli Friedman2017-04-201-6/+22
| | | | | | | | There have been multiple reports of this causing problems: a compile-time explosion on the LLVM testsuite, and a stack overflow for an opencl kernel. llvm-svn: 300928
* [APInt] Rename getSignBit to getSignMaskCraig Topper2017-04-203-11/+11
| | | | | | | | getSignBit is a static function that creates an APInt with only the sign bit set. getSignMask seems like a better name to convey its functionality. In fact several places use it and then store in an APInt named SignMask. Differential Revision: https://reviews.llvm.org/D32108 llvm-svn: 300856
* [APInt] Cast calls to add/sub/mul overflow methods to void if only their ↵Craig Topper2017-04-192-3/+3
| | | | | | | | | | overflow bool out param is used. This is preparation for a clang change to improve the [[nodiscard]] warning to not be ignored on methods that return a class marked [[nodiscard]] that are defined in the class itself. See D32207. We should consider adding wrapper methods to APInt that return the overflow flag directly and discard the APInt result. This would eliminate the void casts and the need to create a bool before the call to pass to the out param. llvm-svn: 300758
* [SCEV] Make SCEV or modeling more aggressive.Eli Friedman2017-04-191-22/+6
| | | | | | | | | | Use haveNoCommonBitsSet to figure out whether an "or" instruction is equivalent to addition. This handles more cases than just checking for a constant on the RHS. Differential Revision: https://reviews.llvm.org/D32239 llvm-svn: 300746
* [InstSimplify] fold identity shuffles (recursing if needed)Sanjay Patel2017-04-191-1/+76
| | | | | | | | | | | | | | | | | This patch simplifies the examples from D31509 and D31927 (PR30630) and catches the basic identity shuffle tests that Zvi recently added. I'm not sure if we have something like this in DAGCombiner, but we should? It's worth noting that "MaxRecurse / RecursionLimit" is only 3 on entry at the moment. We might want to bump that up if there are longer shuffle chains like this in the wild. For now, we're ignoring shuffles that have undef mask elements because it's not clear how those should be handled. Differential Revision: https://reviews.llvm.org/D31960 llvm-svn: 300714
OpenPOWER on IntegriCloud