summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* IR: Add a shufflevector mask commutation helper function. NFC.Zvi Rackover2017-05-081-7/+1
| | | | | | | | | | | | | | | | Summary: Following up on Sanjay's suggetion in D32955, move this functionality into ShuffleVectornstruction. Reviewers: spatel, RKSimon Reviewed By: RKSimon Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32956 llvm-svn: 302420
* [SCEV] Use APInt::operator*=(uint64_t) to avoid a temporary APInt for a ↵Craig Topper2017-05-081-2/+1
| | | | | | constant. llvm-svn: 302404
* [SCEV] Have getRangeForAffineARHelper take StartRange by const reference to ↵Craig Topper2017-05-081-1/+1
| | | | | | avoid a copy in many of the cases. llvm-svn: 302398
* InstructionSimplify: Relanding r301766Zvi Rackover2017-05-071-20/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Re-applying r301766 with a fix to a typo and a regression test. The log message for r301766 was: ================================================================================== InstructionSimplify: Canonicalize shuffle operands. NFC-ish. 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 Reviewed By: spatel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32863 llvm-svn: 302373
* [SCEV] Use move semantics in ScalarEvolution::setRangeCraig Topper2017-05-071-3/+3
| | | | | | | | | | | | | | Summary: This makes setRange take ConstantRange by rvalue reference since most callers were passing an unnamed temporary ConstantRange. We can then move that ConstantRange into the DenseMap caches. For the callers that weren't passing a temporary, I've added std::move to to the local variable being passed. Reviewers: sanjoy, mzolotukhin, efriedma Reviewed By: sanjoy Subscribers: takuto.ikuta, llvm-commits Differential Revision: https://reviews.llvm.org/D32943 llvm-svn: 302371
* [InstSimplify] use ConstantRange to simplify or-of-icmpsSanjay Patel2017-05-071-19/+47
| | | | | | | | | | | | | We can simplify (or (icmp X, C1), (icmp X, C2)) to 'true' or 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 deleted code in instcombine was completely ignoring predicates with mismatched signedness. This is a follow-up to: https://reviews.llvm.org/rL301260 https://reviews.llvm.org/D32143 llvm-svn: 302370
* Remove unnecessary const_castSanjoy Das2017-05-071-7/+4
| | | | llvm-svn: 302368
* Use array_pod_sort instead of std::sortSanjoy Das2017-05-071-1/+1
| | | | llvm-svn: 302367
* [SCEV] Remove extra APInt copies from getRangeForAffineARHelper.Craig Topper2017-05-061-13/+10
| | | | | | This changes one parameter to be a const APInt& since we only read from it. Use std::move on local APInts once they are no longer needed so we can reuse their allocations. Lastly, use operator+=(uint64_t) instead of adding 1 to an APInt twice creating a new APInt each time. llvm-svn: 302335
* [SCEV] Use std::move to avoid some APInt copies.Craig Topper2017-05-061-5/+5
| | | | llvm-svn: 302334
* [SCEV] Use APInt's uint64_t operations instead of creating a temporary APInt ↵Craig Topper2017-05-061-3/+2
| | | | | | to hold 1. llvm-svn: 302333
* [SCEV] Avoid a couple APInt copies by capturing by reference since the ↵Craig Topper2017-05-061-2/+2
| | | | | | method returns a reference. llvm-svn: 302332
* [LazyValueInfo] Avoid unnecessary copies of ConstantRangesCraig Topper2017-05-061-7/+7
| | | | | | | | | | | | | | | | | | | | | Summary: ConstantRange contains two APInts which can allocate memory if their width is larger than 64-bits. So we shouldn't copy it when we can avoid it. This changes LVILatticeVal::getConstantRange() to return its internal ConstantRange by reference. This allows many places that just need a ConstantRange reference to avoid making a copy. Several places now capture the return value of getConstantRange() by reference so they can call methods on it that don't need a new object. Lastly it adds std::move in one place to capture to move a local ConstantRange into an LVILatticeVal. Reviewers: reames, dberlin, sanjoy, anna Reviewed By: reames Subscribers: grandinj, llvm-commits Differential Revision: https://reviews.llvm.org/D32884 llvm-svn: 302331
* TargetLibraryInfo: Introduce wcslenMatthias Braun2017-05-051-0/+4
| | | | | | | | | | | wcslen is part of the C99 and C++98 standards. - This introduces the function to TargetLibraryInfo. - Also set attributes for wcslen in llvm::inferLibFuncAttributes(). Differential Revision: https://reviews.llvm.org/D32837 llvm-svn: 302278
* [KnownBits] Add wrapper methods for setting and clear all bits in the ↵Craig Topper2017-05-052-34/+20
| | | | | | | | | | underlying APInts in KnownBits. This adds routines for reseting KnownBits to unknown, making the value all zeros or all ones. It also adds methods for querying if the value is zero, all ones or unknown. Differential Revision: https://reviews.llvm.org/D32637 llvm-svn: 302262
* [InstSimplify] add folds for or-of-casted-icmpsSanjay Patel2017-05-041-36/+46
| | | | | | | | | | | | | | | | | The sibling folds for 'and' with casts were added with https://reviews.llvm.org/rL273200. This is a preliminary step for adding the 'or' variants for the folds added with https://reviews.llvm.org/rL301260. The reason for the strange form with constant LHS in the 1st test is because there's another missing fold in that case for the inverted predicate. That should be fixed when we add the ConstantRange functionality for 'or-of-icmps' that already exists for 'and-of-icmps'. I'm hoping to share more code for the and/or cases, so we won't have these differences. This will allow us to remove code from InstCombine. It's also possible that we can remove some code here in InstSimplify. I think we have some duplicated folds because patterns are not matched in a general way. Differential Revision: https://reviews.llvm.org/D32876 llvm-svn: 302189
* [InstSimplify] move logic-of-icmps helper functions; NFCSanjay Patel2017-05-041-80/+80
| | | | | | | | Putting these next to each other should make it easier to see what's missing from each side. Patch to plug one of those holes should be posted soon. llvm-svn: 302178
* Re-apply r302108, "IR: Use pointers instead of GUIDs to represent edges in ↵Peter Collingbourne2017-05-041-20/+23
| | | | | | | | the module summary. NFCI." with a fix for the clang backend. llvm-svn: 302176
* Fix a typo.Michael Zolotukhin2017-05-041-2/+2
| | | | llvm-svn: 302175
* Revert "IR: Use pointers instead of GUIDs to represent edges in the module ↵Eric Liu2017-05-041-23/+20
| | | | | | | | | | summary. NFCI." This reverts commit r302108. This causes crash in clang bootstrap with LTO. Contacted the auther in the original commit. llvm-svn: 302140
* IR: Use pointers instead of GUIDs to represent edges in the module summary. ↵Peter Collingbourne2017-05-041-20/+23
| | | | | | | | | | | | | | | | | | | | NFCI. When profiling a no-op incremental link of Chromium I found that the functions computeImportForFunction and computeDeadSymbols were consuming roughly 10% of the profile. The goal of this change is to improve the performance of those functions by changing the map lookups that they were previously doing into pointer dereferences. This is achieved by changing the ValueInfo data structure to be a pointer to an element of the global value map owned by ModuleSummaryIndex, and changing reference lists in the GlobalValueSummary to hold ValueInfos instead of GUIDs. This means that a ValueInfo will take a client directly to the summary list for a given GUID. Differential Revision: https://reviews.llvm.org/D32471 llvm-svn: 302108
* [SCEV] createAddRecFromPHI: Optimize for the most common case.Michael Zolotukhin2017-05-031-2/+58
| | | | | | | | | | | | | | | | | | | Summary: The existing implementation creates a symbolic SCEV expression every time we analyze a phi node and then has to remove it, when the analysis is finished. This is very expensive, and in most of the cases it's also unnecessary. According to the data I collected, ~60-70% of analyzed phi nodes (measured on SPEC) have the following form: PN = phi(Start, OP(Self, Constant)) Handling such cases separately significantly speeds this up. Reviewers: sanjoy, pete Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32663 llvm-svn: 302096
* [KnownBits] Add methods for determining if KnownBits is a constant valueCraig Topper2017-05-032-7/+6
| | | | | | | | This patch adds isConstant and getConstant for determining if KnownBits represents a constant value and to retrieve the value. Use them to simplify code. Differential Revision: https://reviews.llvm.org/D32785 llvm-svn: 302091
* [ValueTracking] Remove handling for BitWidth being 0 in ComputeSignBit and ↵Craig Topper2017-05-031-12/+5
| | | | | | | | isKnownNonZero. I don't believe its possible to have non-zero values here since DataLayout became required. The APInt constructor inside of the KnownBits object will assert if this ever happens. llvm-svn: 302089
* [KnownBits] Add zext, sext, and trunc methods to KnownBitsCraig Topper2017-05-031-8/+4
| | | | | | | | This patch adds zext, sext, and trunc methods to KnownBits and uses them where possible. Differential Revision: https://reviews.llvm.org/D32784 llvm-svn: 302088
* [IR] Abstract away ArgNo+1 attribute indexing as much as possibleReid Kleckner2017-05-031-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Do three things to help with that: - Add AttributeList::FirstArgIndex, which is an enumerator currently set to 1. It allows us to change the indexing scheme with fewer changes. - Add addParamAttr/removeParamAttr. This just shortens addAttribute call sites that would otherwise need to spell out FirstArgIndex. - Remove some attribute-specific getters and setters from Function that take attribute list indices. Most of these were only used from BuildLibCalls, and doesNotAlias was only used to test or set if the return value is malloc-like. I'm happy to split the patch, but I think they are probably easier to review when taken together. This patch should be NFC, but it sets the stage to change the indexing scheme to this, which is more convenient when indexing into an array: 0: func attrs 1: retattrs 2...: arg attrs Reviewers: chandlerc, pete, javed.absar Subscribers: david2050, llvm-commits Differential Revision: https://reviews.llvm.org/D32811 llvm-svn: 302060
* Replace hardcoded intrinsic list with speculatable attribute.Matt Arsenault2017-05-031-60/+3
| | | | | | No change in which intrinsics should be speculated. llvm-svn: 301995
* Revert r295861, "[ModuleSummaryAnalysis] Don't crash when referencing ↵Peter Collingbourne2017-05-031-6/+0
| | | | | | | | | unnamed globals." We should always expect values to be named before running the module summary analysis (see NameAnonGlobals pass), so it's fine if we crash in that case. llvm-svn: 301991
* revert r301766: InstructionSimplify: Canonicalize shuffle operands. NFC-ishSanjay Patel2017-05-021-29/+20
| | | | | | | | | | | | Turns out this wasn't NFC-ish at all because there's a bug processing shuffles that change the size of their input vectors (that case always seems to trip us up). This should fix PR32872 while we investigate how it failed and reduce a testcase: https://bugs.llvm.org/show_bug.cgi?id=32872 llvm-svn: 301977
* 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
OpenPOWER on IntegriCloud