summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [IR] Value: add replaceUsesWithIf() utilityRoman Lebedev2019-08-011-7/+4
| | | | | | | | | | | | | | | | | | | | | | Summary: While there is always a `Value::replaceAllUsesWith()`, sometimes the replacement needs to be conditional. I have only cleaned a few cases where `replaceUsesWithIf()` could be used, to both add test coverage, and show that it is actually useful. Reviewers: jdoerfert, spatel, RKSimon, craig.topper Reviewed By: jdoerfert Subscribers: dschuff, sbc100, jgravelle-google, hiraditya, aheejin, george.burgess.iv, asbirlea, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65528 llvm-svn: 367548
* [SCCP] Update condition to avoid overflow.Alina Sbirlea2019-07-311-1/+1
| | | | | | | | | | | | | | | | Summary: Update condition to remove addition that may cause an overflow. Resolves PR42814. Reviewers: sanjoy, RKSimon Subscribers: jlebar, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65417 llvm-svn: 367461
* [MemorySSA] Add additional verification for phis.Alina Sbirlea2019-07-312-1/+43
| | | | | | | | | | | | | | | | | | Summary: Verify that the incoming defs into phis are the last defs from the respective incoming blocks. When moving blocks, insertDef must RenameUses. Adding this verification makes GVNHoist tests fail that uncovered this issue. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63147 llvm-svn: 367451
* Recommit "[GVN] Preserve loop related analysis/canonical forms."Florian Hahn2019-07-311-2/+9
| | | | | | | This fixes some pipeline tests. This reverts commit d0b6f42936bfb6d56d325c732ae79400c9c6016a. llvm-svn: 367401
* [MemorySSA] Extend allowed behavior for simplified instructions.Alina Sbirlea2019-07-302-27/+51
| | | | | | | | | | | | | | | | Summary: LoopRotate may simplify instructions, leading to the new instructions not having memory accesses created for them. Allow this behavior, by allowing the new access to be null when the template is null, and looking upwards for the proper defined access when dealing with simplified instructions. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65338 llvm-svn: 367352
* [FunctionAttrs] Annotate "willreturn" for AssumeLikeInstHideto Ueno2019-07-301-4/+1
| | | | | | | | | | | | | | | | | Summary: In D37215, AssumeLikeInstruction are regarded as `willreturn`. In this patch, annotation is added to those which don't have `willreturn` now(`sideeffect, object_size, experimental_widenable_condition`). Reviewers: jdoerfert, nikic, sstefan1 Reviewed By: nikic Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65455 llvm-svn: 367342
* Revert [GVN] Preserve loop related analysis/canonical forms.Florian Hahn2019-07-301-9/+2
| | | | | | This reverts r367332 (git commit 2d7227ec3ac91f36fc32b1c21e72e2f1f5d030ad) llvm-svn: 367335
* [GVN] Preserve loop related analysis/canonical forms.Florian Hahn2019-07-301-2/+9
| | | | | | | | | | | | | | | | | | | | LoopInfo can be easily preserved by passing it to the functions that modify the CFG (SplitCriticalEdge and MergeBlockIntoPredecessor. SplitCriticalEdge also preserves LoopSimplify and LCSSA form when when passing in LoopInfo. The test case shows that we preserve LoopSimplify and LoopInfo. Adding addPreservedID(LCSSAID) did not preserve LCSSA for some reason. Also I am not sure if it is possible to preserve those in the new pass manager, as they aren't analysis passes. Reviewers: reames, hfinkel, davide, jdoerfert Reviewed By: jdoerfert Differential Revision: https://reviews.llvm.org/D65137 llvm-svn: 367332
* [ValueTracking] Remove volatile check in ↵Hideto Ueno2019-07-291-15/+2
| | | | | | | | | | | | | | | | | | isGuaranteedToTransferExecutionToSuccessor Summary: As clarified in D53184, volatile load and store do not trap. Therefore, we should remove volatile checks for instructions in `isGuaranteedToTransferExecutionToSuccessor`. Reviewers: jdoerfert, efriedma, nikic Reviewed By: nikic Subscribers: hiraditya, jfb, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65375 llvm-svn: 367226
* [DivergenceAnalysis] Add methods for querying divergence at useJay Foad2019-07-292-7/+32
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: The existing isDivergent(Value) methods query whether a value is divergent at its definition. However even if a value is uniform at its definition, a use of it in another basic block can be divergent because of divergent control flow between the def and the use. This patch adds new isDivergent(Use) methods to DivergenceAnalysis, LegacyDivergenceAnalysis and GPUDivergenceAnalysis. This might allow D63953 or other similar workarounds to be removed. Reviewers: alex-t, nhaehnle, arsenm, rtaylor, rampitec, simoll, jingyue Reviewed By: nhaehnle Subscribers: jfb, jvesely, wdng, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65141 llvm-svn: 367218
* [LOOPINFO] Introduce the loop guard API.Whitney Tsang2019-07-251-0/+35
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This is the first patch for the loop guard. We introduced getLoopGuardBranch() and isGuarded(). This currently only works on simplified loop, as it requires a preheader and a latch to identify the guard. It will work on loops of the form: /// GuardBB: /// br cond1, Preheader, ExitSucc <== GuardBranch /// Preheader: /// br Header /// Header: /// ... /// br Latch /// Latch: /// br cond2, Header, ExitBlock /// ExitBlock: /// br ExitSucc /// ExitSucc: Prior discussions leading upto the decision to introduce the loop guard API: http://lists.llvm.org/pipermail/llvm-dev/2019-May/132607.html Reviewer: reames, kbarton, hfinkel, jdoerfert, Meinersbur, dmgreen Reviewed By: reames Subscribers: wuzish, hiraditya, jsji, llvm-commits, bmahjour, etiotto Tag: LLVM Differential Revision: https://reviews.llvm.org/D63885 llvm-svn: 367033
* [InstSimplify] Rename SimplifyFPUnOp and SimplifyFPBinOpJay Foad2019-07-243-17/+15
| | | | | | | | | | | | | | | | | | | | | | Summary: SimplifyFPBinOp is a variant of SimplifyBinOp that lets you specify fast math flags, but the name is misleading because both functions can simplify both FP and non-FP ops. Instead, overload SimplifyBinOp so that you can optionally specify fast math flags. Likewise for SimplifyFPUnOp. Reviewers: spatel Reviewed By: spatel Subscribers: xbolva00, cameron.mcinally, eraman, hiraditya, haicheng, zzheng, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64902 llvm-svn: 366902
* Analysis: Don't look through aliases when simplifying GEPs.Peter Collingbourne2019-07-221-1/+1
| | | | | | | | | | | | | | | | | | | | It is not safe in general to replace an alias in a GEP with its aliasee if the alias can be replaced with another definition (i.e. via strong/weak resolution (linkonce_odr) or via symbol interposition (default visibility in ELF)) while the aliasee cannot. An example of how this can go wrong is in the included test case. I was concerned that this might be a load-bearing misoptimization (it's possible for us to use aliases to share vtables between base and derived classes, and on Windows, vtable symbols will always be aliases in RTTI mode, so this change could theoretically inhibit trivial devirtualization in some cases), so I built Chromium for Linux and Windows with and without this change. The file sizes of the resulting binaries were identical, so it doesn't look like this is going to be a problem. Differential Revision: https://reviews.llvm.org/D65118 llvm-svn: 366754
* [LAA] Re-check bit-width of pointers after stripping.Michael Liao2019-07-181-1/+14
| | | | | | | | | | | | | | | | Summary: - As the pointer stripping now tracks through `addrspacecast`, prepare to handle the bit-width difference from the result pointer. Reviewers: jdoerfert Subscribers: jvesely, nhaehnle, hiraditya, arphaman, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64928 llvm-svn: 366470
* [SCEV] add no wrap flag for SCEVAddExpr.Chen Zheng2019-07-181-1/+1
| | | | | | Differential Revision: https://reviews.llvm.org/D64868 llvm-svn: 366419
* Make DT a transitive dependency of LI.Evgeniy Stepanov2019-07-171-1/+1
| | | | | | | | | | | | | | | | | | Summary: LoopInfoWrapperPass::verify uses DT, which means DT must be alive even if it has no direct users. Fixes a crash in expensive checks mode. Reviewers: pcc, leonardchan Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64896 llvm-svn: 366388
* Basic codegen for MTE stack tagging.Evgeniy Stepanov2019-07-171-1/+2
| | | | | | | | | | | | Implement IR intrinsics for stack tagging. Generated code is very unoptimized for now. Two special intrinsics, llvm.aarch64.irg.sp and llvm.aarch64.tagp are used to implement a tagged stack frame pointer in a virtual register. Differential Revision: https://reviews.llvm.org/D64172 llvm-svn: 366360
* [AMDGPU] Tune inlining parameters for AMDGPU targetDaniil Fukalov2019-07-172-10/+5
| | | | | | | | | | | | | | | | | | | Summary: Since the target has no significant advantage of vectorization, vector instructions bous threshold bonus should be optional. amdgpu-inline-arg-alloca-cost parameter default value and the target InliningThresholdMultiplier value tuned then respectively. Reviewers: arsenm, rampitec Subscribers: kzhuravl, jvesely, wdng, nhaehnle, yaxunl, dstuttard, tpr, t-tye, eraman, hiraditya, haicheng, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64642 llvm-svn: 366348
* [InstructionSimplify] Apply sext/trunc after pointer strippingMichael Liao2019-07-161-0/+4
| | | | | | | | | | | | | | | | | Summary: - As the pointer stripping could trace through `addrspacecast` now, need to sext/trunc the offset to ensure it has the same width as the pointer after stripping. Reviewers: jdoerfert Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64768 llvm-svn: 366162
* [LoopUnroll+LoopUnswitch] do not transform loops containing callbrNick Desaulniers2019-07-151-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: There is currently a correctness issue when unrolling loops containing callbr's where their indirect targets are being updated correctly to the newly created labels, but their operands are not. This manifests in unrolled loops where the second and subsequent copies of callbr instructions have blockaddresses of the label from the first instance of the unrolled loop, which would result in nonsensical runtime control flow. For now, conservatively do not unroll the loop. In the future, I think we can pursue unrolling such loops provided we transform the cloned callbr's operands correctly. Such a transform and its legalities are being discussed in: https://reviews.llvm.org/D64101 Link: https://bugs.llvm.org/show_bug.cgi?id=42489 Link: https://groups.google.com/forum/#!topic/clang-built-linux/z-hRWP9KqPI Reviewers: fhahn, hfinkel, efriedma Reviewed By: fhahn, hfinkel, efriedma Subscribers: efriedma, hiraditya, zzheng, dmgreen, llvm-commits, pirama, kees, nathanchance, E5ten, craig.topper, chandlerc, glider, void, srhines Tags: #llvm Differential Revision: https://reviews.llvm.org/D64368 llvm-svn: 366130
* [ValueTracking] Look through constant Int2Ptr/Ptr2Int expressionsJohannes Doerfert2019-07-151-0/+9
| | | | | | | | | | | | | | | | Summary: This is analogous to the int2ptr/ptr2int instruction handling introduced in D54956. Reviewers: fhahn, efriedma, spatel, nlopes, sanjoy, lebedev.ri Subscribers: hiraditya, bollu, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64708 llvm-svn: 366036
* isBytewiseValue checks ConstantVector element by elementVitaly Buka2019-07-121-6/+1
| | | | | | | | | | | | | | | | Summary: Vector of the same value with few undefs will sill be considered "Bytewise" Reviewers: eugenis, pcc, jfb Reviewed By: jfb Subscribers: dexonsmith, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64031 llvm-svn: 365971
* [MemorySSA] Use SetVector to avoid nondeterminism.Alina Sbirlea2019-07-121-1/+1
| | | | | | | | | | | | | | | | Summary: Use a SetVector for DeadBlockSet. Resolves PR42574. Reviewers: george.burgess.iv, uabelho, dblaikie Subscribers: jlebar, Prazek, mgrang, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64601 llvm-svn: 365970
* Delete dead storesFangrui Song2019-07-121-7/+4
| | | | llvm-svn: 365903
* Return Undef from isBytewiseValue for empty arrays or structsVitaly Buka2019-07-121-0/+4
| | | | | | | | | | | | Reviewers: pcc, eugenis Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64052 llvm-svn: 365864
* Handle IntToPtr in isBytewiseValueVitaly Buka2019-07-121-0/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This helps with more efficient use of memset for pattern initialization From @pcc prototype for -ftrivial-auto-var-init=pattern optimizations Binary size change on CTMark, (with -fuse-ld=lld -Wl,--icf=all, similar results with default linker options) ``` master patch diff Os 8.238864e+05 8.238864e+05 0.0 O3 1.054797e+06 1.054797e+06 0.0 Os zero 8.292384e+05 8.292384e+05 0.0 O3 zero 1.062626e+06 1.062626e+06 0.0 Os pattern 8.579712e+05 8.338048e+05 -0.030299 O3 pattern 1.090502e+06 1.067574e+06 -0.020481 ``` Zero vs Pattern on master ``` zero pattern diff Os 8.292384e+05 8.579712e+05 0.036578 O3 1.062626e+06 1.090502e+06 0.025124 ``` Zero vs Pattern with the patch ``` zero pattern diff Os 8.292384e+05 8.338048e+05 0.003333 O3 1.062626e+06 1.067574e+06 0.003193 ``` Reviewers: pcc, eugenis Subscribers: hiraditya, cfe-commits, llvm-commits Tags: #clang, #llvm Differential Revision: https://reviews.llvm.org/D63967 llvm-svn: 365858
* OpaquePtr: switch to GlobalValue::getValueType in a few places. NFC.Tim Northover2019-07-111-1/+1
| | | | llvm-svn: 365770
* InstructionSimplify: Simplify InstructionSimplify. NFC.Tim Northover2019-07-111-42/+24
| | | | | | | | | | | The interface predates CallBase, so both it and implementation were significantly more complicated than they needed to be. There was even some redundancy that could be eliminated. Should also help with OpaquePointers by not trying to derive a function's type from it's PointerType. llvm-svn: 365767
* [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
OpenPOWER on IntegriCloud