summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [SCEV] teach SCEV symbolical execution about overflow intrinsics folding.Chen Zheng2019-07-112-1/+4
| | | | | | Differential Revision: https://reviews.llvm.org/D64422 llvm-svn: 365726
* Replace three "strip & accumulate" implementations with a single oneJohannes Doerfert2019-07-112-79/+2
| | | | | | | | | | | This patch replaces the three almost identical "strip & accumulate" implementations for constant pointer offsets with a single one, combining the respective functionalities. The old interfaces are kept for now. Differential Revision: https://reviews.llvm.org/D64468 llvm-svn: 365723
* NFC: Pass DataLayout into isBytewiseValueVitaly Buka2019-07-101-5/+6
| | | | | | | | | | | | | | | | | | Summary: We will need to handle IntToPtr which I will submit in a separate patch as it's not going to be NFC. Reviewers: eugenis, pcc Reviewed By: eugenis Subscribers: hiraditya, cfe-commits, llvm-commits Tags: #clang, #llvm Differential Revision: https://reviews.llvm.org/D63940 llvm-svn: 365709
* Revert "[HardwareLoops] NFC - move hardware loop checking code to ↵Jinsong Ji2019-07-091-32/+1
| | | | | | | | isHardwareLoopProfitable()" This reverts commit d95557306585404893d610784edb3e32f1bfce18. llvm-svn: 365520
* [HardwareLoops] NFC - move hardware loop checking code to ↵Chen Zheng2019-07-091-1/+32
| | | | | | | | isHardwareLoopProfitable() Differential Revision: https://reviews.llvm.org/D64197 llvm-svn: 365497
* OpaquePtr: add Type parameter to Loads analysis API.Tim Northover2019-07-093-13/+24
| | | | | | | | | | | | | This makes the functions in Loads.h require a type to be specified independently of the pointer Value so that when pointers have no structure other than address-space, it can still do its job. Most callers had an obvious memory operation handy to provide this type, but a SROA and ArgumentPromotion were doing more complicated analysis. They get updated to merge the properties of the various instructions they were considering. llvm-svn: 365468
* [SCEV] Fix for PR42397. SCEVExpander wrongly adds nsw to shl instruction.Denis Bakhvalov2019-07-081-2/+6
| | | | | Change-Id: I76c9f628c092ae3e6e78ebdaf55cec726e25d692 llvm-svn: 365363
* Add, and infer, a nofree function attributeBrian Homerding2019-07-081-18/+37
| | | | | | | | | | | | This patch adds a function attribute, nofree, to indicate that a function does not, directly or indirectly, call a memory-deallocation function (e.g., free, C++'s operator delete). Reviewers: jdoerfert Differential Revision: https://reviews.llvm.org/D49165 llvm-svn: 365336
* [ThinLTO] Attempt to recommit r365188 after alignment fixEugene Leviant2019-07-051-27/+95
| | | | llvm-svn: 365215
* Reverted r365188 due to alignment problems on i686-androidEugene Leviant2019-07-051-95/+27
| | | | llvm-svn: 365206
* [ThinLTO] Attempt to recommit r365040 after caching fixEugene Leviant2019-07-051-27/+95
| | | | | | | | | | | | | | It's possible that some function can load and store the same variable using the same constant expression: store %Derived* @foo, %Derived** bitcast (%Base** @bar to %Derived**) %42 = load %Derived*, %Derived** bitcast (%Base** @bar to %Derived**) The bitcast expression was mistakenly cached while processing loads, and never examined later when processing store. This caused @bar to be mistakenly treated as read-only variable. See load-store-caching.ll. llvm-svn: 365188
* Revert [ThinLTO] Optimize writeonly globals outReid Kleckner2019-07-041-83/+27
| | | | | | | | | This reverts r365040 (git commit 5cacb914758c7f436b47c8362100f10cef14bbc4) Speculatively reverting, since this appears to have broken check-lld on Linux. Partial analysis in https://crbug.com/981168. llvm-svn: 365097
* Teach ValueTracking that aarch64.irg result aliases its input.Evgeniy Stepanov2019-07-031-1/+2
| | | | | | | | | | | | Reviewers: javed.absar, olista01 Subscribers: kristof.beyls, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64103 llvm-svn: 365079
* [SCEV] Preserve flags on add/muls in getSCEVATScopePhilip Reames2019-07-031-2/+2
| | | | | | | | We haven't changed the set of users, just specialized an operand for those users. Given that, the previous wrap flags must still be correct. Sorry for the lack of test case. Noticed this while working on something else, and haven't figured out to exercise this standalone. llvm-svn: 365053
* [ThinLTO] Optimize writeonly globals outEugene Leviant2019-07-031-27/+83
| | | | | | Differential revision: https://reviews.llvm.org/D63444 llvm-svn: 365040
* [SCEV][LSR] Prevent using undefined value in binopsEugene Leviant2019-07-031-3/+1
| | | | | | | | | | | On some occasions ReuseOrCreateCast may convert previously expanded value to undefined. That value may be passed by SCEVExpander as an argument to InsertBinop making IV chain undefined. Differential revision: https://reviews.llvm.org/D63928 llvm-svn: 365009
* Revert [InlineCost] cleanup calculations of Cost and ThresholdJordan Rupprecht2019-07-031-15/+13
| | | | | | | | This reverts r364422 (git commit 1a3dc761860d620ac8ed7e32a4285952142f780b) The inlining cost calculation is incorrect, leading to stack overflow due to large stack frames from heavy inlining. llvm-svn: 365000
* [PowerPC] exclude ICmpZero in LSR if icmp can be replaced in later hardware ↵Chen Zheng2019-07-031-0/+7
| | | | | | | | | loop. Differential Revision: https://reviews.llvm.org/D63477 llvm-svn: 364993
* [ThinLTO] Add summary entries for index-based WPDTeresa Johnson2019-07-021-3/+110
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: If LTOUnit splitting is disabled, the module summary analysis computes the summary information necessary to perform single implementation devirtualization during the thin link with the index and no IR. The information collected from the regular LTO IR in the current hybrid WPD algorithm is summarized, including: 1) For vtable definitions, record the function pointers and their offset within the vtable initializer (subsumes the information collected from IR by tryFindVirtualCallTargets). 2) A record for each type metadata summarizing the vtable definitions decorated with that metadata (subsumes the TypeIdentiferMap collected from IR). Also added are the necessary bitcode records, and the corresponding assembly support. The follow-on index-based WPD patch is D55153. Depends on D53890. Reviewers: pcc Subscribers: mehdi_amini, Prazek, inglorion, eraman, steven_wu, dexonsmith, arphaman, llvm-commits Differential Revision: https://reviews.llvm.org/D54815 llvm-svn: 364960
* [IDF] Generalize IDFCalculator to be used with Clang's CFGKristof Umann2019-07-022-105/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | I'm currently working on a GSoC project that aims to improve the the bug reports of the analyzer. The main heuristic I plan to use is to explain values that are a control dependency of the bug location better. 01 bool b = messyComputation(); 02 int i = 0; 03 if (b) // control dependency of the bug site, let's explain why we assume val 04 // to be true 05 10 / i; // warn: division by zero Because of this, I'd like to generalize IDFCalculator so that I could use it for Clang's CFG: D62883. In detail: * Rename IDFCalculator to IDFCalculatorBase, make it take a general CFG node type as a template argument rather then strictly BasicBlock (but preserve ForwardIDFCalculator and ReverseIDFCalculator) * Move IDFCalculatorBase from llvm/include/llvm/Analysis to llvm/include/llvm/Support (but leave the BasicBlock variants in llvm/include/llvm/Analysis) * clang-format the file since this patch messes up git blame anyways * Change typedef to using * Add the new type ChildrenGetterTy, and store an instance of it in IDFCalculatorBase. This is important because I'll have to specialize it for Clang's CFG to filter out nullpointer successors, similarly to D62507. Differential Revision: https://reviews.llvm.org/D63389 llvm-svn: 364911
* Cleanup: llvm::bsearch -> llvm::partition_point after r364719Fangrui Song2019-06-301-2/+2
| | | | llvm-svn: 364720
* Use "willreturn" in isGuaranteedToTransferExecutionToSuccessorJohannes Doerfert2019-06-271-0/+5
| | | | | | | | | | | | | | | | | | | | | The `willreturn` function attribute guarantees that a function call will come back to the call site if the call is also known not to throw. Therefore, this attribute can be used in `isGuaranteedToTransferExecutionToSuccessor`. Patch by Hideto Ueno (@uenoku) Reviewers: jdoerfert, sstefan1 Reviewed By: jdoerfert Subscribers: hiraditya, jfb, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63372 llvm-svn: 364580
* Update -analyze -scalar-evolution output for multiple exit loops ↵Philip Reames2019-06-271-10/+14
| | | | | | | | w/computable exit values The previous output was next to useless if *any* exit was not computable. If we have more than one exit, show the exit count for each so that it's easier to see what's going from with SCEV analysis when debugging. llvm-svn: 364579
* [InlineCost] cleanup calculations of Cost and ThresholdFedor Sergeev2019-06-261-13/+15
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: Doing better separation of Cost and Threshold. Cost counts the abstract complexity of live instructions, while Threshold is an upper bound of complexity that inlining is comfortable to pay. There are two parts: - huge 15K last-call-to-static bonus is no longer subtracted from Cost but rather is now added to Threshold. That makes much more sense, as the cost of inlining (Cost) is not changed by the fact that internal function is called once. It only changes the likelyhood of this inlining being profitable (Threshold). - bonus for calls proved-to-be-inlinable into callee is no longer subtracted from Cost but added to Threshold instead. While calculations are somewhat different, overall InlineResult should stay the same since Cost >= Threshold compares the same. Reviewers: eraman, greened, chandlerc, yrouban, apilipenko Reviewed By: apilipenko Tags: #llvm Differential Revision: https://reviews.llvm.org/D60740 llvm-svn: 364422
* [HardwareLoops] NFC - move loop with irreducible control flow checking logic ↵Chen Zheng2019-06-261-7/+11
| | | | | | to HarewareLoopInfo. llvm-svn: 364415
* [HardwareLoops] NFC - move loop with irreducible control flow checking logic ↵Chen Zheng2019-06-261-1/+9
| | | | | | to isHardwareLoopProfitable() llvm-svn: 364397
* [ExpandMemCmp] Move all options to TargetTransformInfo.Clement Courbet2019-06-251-3/+3
| | | | | | Split off from D60318. llvm-svn: 364281
* [ConstantFolding] Use hasVectorInstrinsicScalarOpd. NFCBjorn Pettersson2019-06-241-16/+13
| | | | | | | | | | | | | | | | | | Summary: Use the hasVectorInstrinsicScalarOpd helper function in ConstantFoldVectorCall. Reviewers: rengolin, RKSimon, dblaikie Reviewed By: rengolin, RKSimon Subscribers: tschuett, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63705 llvm-svn: 364178
* [Scalarizer] Add scalarizer support for smul.fix.satBjorn Pettersson2019-06-241-4/+6
| | | | | | | | | | | | | | | | | | | | | | | Summary: Handle smul.fix.sat in the scalarizer. This is done by adding smul.fix.sat to the set of "isTriviallyVectorizable" intrinsics. The addition of smul.fix.sat in isTriviallyVectorizable and hasVectorInstrinsicScalarOpd can also be seen as a preparation to be able to use hasVectorInstrinsicScalarOpd in ConstantFolding. Reviewers: rengolin, RKSimon, dblaikie Reviewed By: rengolin Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63704 llvm-svn: 364177
* Simplify std::lower_bound with llvm::{bsearch,lower_bound}. NFCFangrui Song2019-06-211-4/+3
| | | | llvm-svn: 364006
* [InstSimplify] simplify power-of-2 (single bit set) sequencesSanjay Patel2019-06-201-0/+10
| | | | | | | | | | | | | | | | | | | | As discussed in PR42314: https://bugs.llvm.org/show_bug.cgi?id=42314 Improving the canonicalization for these patterns: rL363956 ...means we should adjust/enhance the related simplification. https://rise4fun.com/Alive/w1cp Name: isPow2 or zero %x = and i32 %xx, 2048 %a = add i32 %x, -1 %r = and i32 %a, %x => %r = i32 0 llvm-svn: 363997
* [MemorySSA] Cleanup trivial phis.Alina Sbirlea2019-06-191-5/+8
| | | | | | | | | | | | | | | | | | | Summary: This is unfortunately needed for correctness, if we are to extend the tolerance of the update API to the way simple loop unswitch is doing cloning. In simple loop unswitch (as opposed to loop unswitch), not all blocks are cloned. This can create unreachable cloned blocks (no predecessor), which are later cleaned up. In MemorySSA, the APIs for supporting these kind of updates (clone + update exit blocks), make certain assumption on the integrity of the CFG. When cloning, if something was not cloned, it's values in MemorySSA default to LiveOnEntry. When updating exit blocks, it is safe to assume that we can first insert phis in the blocks merging two clones, then add additional phis in the IDF of the blocks that received phis. This no longer holds true if one of the clones being merged comes from an unreachable block. We'd conservatively need to add all phis before filling in their incoming definitions. In practice this restriction can be relaxed if we clean up trivial phis after the first round of insertion. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63354 llvm-svn: 363880
* [MemorySSA] Use GraphDiff info when computing IDF.Alina Sbirlea2019-06-191-1/+1
| | | | | | | | | | | | | | | | Summary: When computing IDF for insert updates, ensure we use the snapshot CFG offered by GraphDiff. Caught by D63389. Reviewers: kuhar, george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits, Szelethus Tags: #llvm Differential Revision: https://reviews.llvm.org/D63443 llvm-svn: 363879
* [ConstantFolding] Add constant folding for smul.fix and smul.fix.satBjorn Pettersson2019-06-191-0/+46
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch teaches ConstantFolding to constant fold both scalar and vector variants of llvm.smul.fix and llvm.smul.fix.sat. As described in the LangRef rounding is unspecified for these instrinsics. If the result cannot be represented exactly the default behavior in ConstantFolding is to round down towards negative infinity. If a target has a preferred rounding that is different some kind of target hook would be needed (same strategy as used by the SelectionDAG legalizer). Reviewers: nikic, leonardchan, RKSimon Reviewed By: leonardchan Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63385 llvm-svn: 363811
* [ConstantFolding] Refactor ConstantFoldScalarCall. NFCBjorn Pettersson2019-06-191-469/+497
| | | | | | | | | | | This patch splits ConstantFoldScalarCall into several functions. Benefits: - Reduces indentation levels and avoids long if-statements. - Makes it easier to add support for > 3 operands. llvm-svn: 363810
* [ConstantFolding] Fix assertion failure on non-power-of-two vector load.Jay Foad2019-06-191-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | Summary: The test case does an (out of bounds) load from a global constant with type <3 x float>. InstSimplify tried to turn this into an integer load of the whole alloc size of the vector, which is 128 bits due to alignment padding, and then bitcast this to <3 x vector> which failed an assertion due to the type size mismatch. The fix is to do an integer load of the normal size of the vector, with no alignment padding. Reviewers: tpr, arsenm, majnemer, dstuttard Reviewed By: arsenm Subscribers: hfinkel, wdng, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63375 llvm-svn: 363784
* [NFC] move some hardware loop checking code to a common place for other using.Chen Zheng2019-06-191-0/+85
| | | | | | Differential Revision: https://reviews.llvm.org/D63478 llvm-svn: 363758
* [GlobalISel][Localizer] Rewrite localizer to run in 2 phases, inter & intra ↵Amara Emerson2019-06-171-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | block. Inter-block localization is the same as what currently happens, except now it only runs on the entry block because that's where the problematic constants with long live ranges come from. The second phase is a new intra-block localization phase which attempts to re-sink the already localized instructions further right before one of the multiple uses. One additional change is to also localize G_GLOBAL_VALUE as they're constants too. However, on some targets like arm64 it takes multiple instructions to materialize the value, so some additional heuristics with a TTI hook have been introduced attempt to prevent code size regressions when localizing these. Overall, these changes improve CTMark code size on arm64 by 1.2%. Full code size results: Program baseline new diff ------------------------------------------------------------------------------ test-suite...-typeset/consumer-typeset.test 1249984 1217216 -2.6% test-suite...:: CTMark/ClamAV/clamscan.test 1264928 1232152 -2.6% test-suite :: CTMark/SPASS/SPASS.test 1394092 1361316 -2.4% test-suite...Mark/mafft/pairlocalalign.test 731320 714928 -2.2% test-suite :: CTMark/lencod/lencod.test 1340592 1324200 -1.2% test-suite :: CTMark/kimwitu++/kc.test 3853512 3820420 -0.9% test-suite :: CTMark/Bullet/bullet.test 3406036 3389652 -0.5% test-suite...ark/tramp3d-v4/tramp3d-v4.test 8017000 8016992 -0.0% test-suite...TMark/7zip/7zip-benchmark.test 2856588 2856588 0.0% test-suite...:: CTMark/sqlite3/sqlite3.test 765704 765704 0.0% Geomean difference -1.2% Differential Revision: https://reviews.llvm.org/D63303 llvm-svn: 363632
* Teach getSCEVAtScope how to handle loop phis w/invariant operands in loops ↵Philip Reames2019-06-171-18/+26
| | | | | | | | | | | | w/taken backedges This patch really contains two pieces: Teach SCEV how to fold a phi in the header of a loop to the value on the backedge when a) the backedge is known to execute at least once, and b) the value is safe to use globally within the scope dominated by the original phi. Teach IndVarSimplify's rewriteLoopExitValues to allow loop invariant expressions which already exist (and thus don't need new computation inserted) even in loops where we can't optimize away other uses. Differential Revision: https://reviews.llvm.org/D63224 llvm-svn: 363619
* [MemorySSA] Don't use template when the clone is a simplified instruction.Alina Sbirlea2019-06-171-3/+11
| | | | | | | | | | | | | | | | | | | Summary: LoopRotate doesn't create a faithful clone of an instruction, it may simplify it beforehand. Hence the clone of an instruction that has a MemoryDef associated may not be a definition, but a use or not a memory alternig instruction. Don't rely on the template when the clone may be simplified. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63355 llvm-svn: 363597
* [MemorySSA] Add all MemoryPhis before filling their values.Alina Sbirlea2019-06-171-3/+13
| | | | | | | | | | | | | | | | | | Summary: Add all MemoryPhis in IDF before filling in their incomign values. Otherwise, a new Phi can be added that needs to become the incoming value of another Phi. Test fails the verification in verifyPrevDefInPhis. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, zzheng, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63353 llvm-svn: 363590
* [LV] Suppress vectorization in some nontemporal casesWarren Ristow2019-06-171-0/+10
| | | | | | | | | | | | | | | | | | | | | When considering a loop containing nontemporal stores or loads for vectorization, suppress the vectorization if the corresponding vectorized store or load with the aligment of the original scaler memory op is not supported with the nontemporal hint on the target. This adds two new functions: bool isLegalNTStore(Type *DataType, unsigned Alignment) const; bool isLegalNTLoad(Type *DataType, unsigned Alignment) const; to TTI, leaving the target independent default implementation as returning true, but with overriding implementations for X86 that check the legality based on available Subtarget features. This fixes https://llvm.org/PR40759 Differential Revision: https://reviews.llvm.org/D61764 llvm-svn: 363581
* [SCEV] Use NoWrapFlags when expanding a simple mulSam Parker2019-06-171-2/+2
| | | | | | | | | | Second functional change following on from rL362687. Pass the NoWrapFlags from the MulExpr to InsertBinop when we're generating a shl or mul. Differential Revision: https://reviews.llvm.org/D61934 llvm-svn: 363540
* [InstSimplify] Fix addo/subo undef folds (PR42209)Roman Lebedev2019-06-161-8/+11
| | | | | | | | | | | | | | | | Fix folds of addo and subo with an undef operand to be: `@llvm.{u,s}{add,sub}.with.overflow` all fold to `{ undef, false }`, as per LLVM undef rules. Same for commuted variants. Based on the original version of the patch by @nikic. Fixes [[ https://bugs.llvm.org/show_bug.cgi?id=42209 | PR42209 ]] Differential Revision: https://reviews.llvm.org/D63065 llvm-svn: 363522
* [SCEV] Use unsigned/signed intersection type in SCEVNikita Popov2019-06-151-19/+32
| | | | | | | | | | | | Based on D59959, this switches SCEV to use unsigned/signed range intersection based on the sign hint. This will prefer non-wrapping ranges in the relevant domain. I've left the one intersection in getRangeForAffineAR() to use the smallest intersection heuristic, as there doesn't seem to be any obvious preference there. Differential Revision: https://reviews.llvm.org/D60035 llvm-svn: 363490
* [ObjC][ARC] Delete ObjC runtime calls on global variables annotatedAkira Hatanaka2019-06-141-0/+35
| | | | | | | | | | | | with 'objc_arc_inert' Those calls are no-ops, so they can be safely deleted. rdar://problem/49839633 Differential Revision: https://reviews.llvm.org/D62433 llvm-svn: 363468
* SROA: Allow eliminating addrspacecasted allocasMatt Arsenault2019-06-141-1/+7
| | | | | | | | | | | | | | | | | | | There is a circular dependency between SROA and InferAddressSpaces today that requires running both multiple times in order to be able to eliminate all simple allocas and addrspacecasts. InferAddressSpaces can't remove addrspacecasts when written to memory, and SROA helps move pointers out of memory. This should avoid inserting new commuting addrspacecasts with GEPs, since there are unresolved questions about pointer wrapping between different address spaces. For now, don't replace volatile operations that don't match the alloca addrspace, as it would change the address space of the access. It may be still OK to insert an addrspacecast from the new alloca, but be more conservative for now. llvm-svn: 363462
* [SCEV] Pass NoWrapFlags when expanding an AddExprSam Parker2019-06-141-1/+1
| | | | | | | | | | | | InsertBinop now accepts NoWrapFlags, so pass them through when expanding a simple add expression. This is the first re-commit of the functional changes from rL362687, which was previously reverted. Differential Revision: https://reviews.llvm.org/D61934 llvm-svn: 363364
* [LangRef] Clarify poison semanticsNikita Popov2019-06-131-0/+2
| | | | | | | | | | | | | | | | | | | | | I find the current documentation of poison somewhat confusing, mainly because its use of "undefined behavior" doesn't seem to align with our usual interpretation (of immediate UB). Especially the sentence "any instruction that has a dependence on a poison value has undefined behavior" is very confusing. Clarify poison semantics by: * Replacing the introductory paragraph with the standard rationale for having poison values. * Spelling out that instructions depending on poison return poison. * Spelling out how we go from a poison value to immediate undefined behavior and give the two examples we currently use in ValueTracking. * Spelling out that side effects depending on poison are UB. Differential Revision: https://reviews.llvm.org/D63044 llvm-svn: 363320
* Add a clarifying comment about branching on poisonPhilip Reames2019-06-131-0/+4
| | | | | | I recently got this wrong (again), and I'm sure I'm not the only one. Put a comment in the logical place someone would look to "fix" the obvious "missed optimization" which arrises based on the common misunderstanding. Hopefully, this will save others time. :) llvm-svn: 363318
OpenPOWER on IntegriCloud