summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms
Commit message (Collapse)AuthorAgeFilesLines
* [Attributor] Deducing existing nounwind attribute.Stefan Stipanovic2019-06-271-10/+85
| | | | | | | | | | | | Adding nounwind deduction in new attributor framework. Reviewers: jdoerfert, uenoku Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D63379 llvm-svn: 364521
* [SCCP] Fix non-deterministic uselists of return values (DenseMap -> MapVector)Gerolf Hoflehner2019-06-261-6/+7
| | | | llvm-svn: 364482
* [SLP] Look-ahead operand reordering heuristic.Vasileios Porpodas2019-06-261-46/+236
| | | | | | | | | | | | | | | | Summary: This patch introduces a new heuristic for guiding operand reordering. The new "look-ahead" heuristic can look beyond the immediate predecessors. This helps break ties when the immediate predecessors have identical opcodes (see lit test for an example). Reviewers: RKSimon, ABataev, dtemirbulatov, Ayal, hfinkel, rnk Reviewed By: RKSimon, dtemirbulatov Subscribers: rnk, rcorcs, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D60897 llvm-svn: 364478
* [WebAssembly] Implement Address Sanitizer for EmscriptenGuanzhong Chen2019-06-261-0/+4
| | | | | | | | | | | | | | | | | | | | | | Summary: This diff enables address sanitizer on Emscripten. On Emscripten, real memory starts at the value passed to --global-base. All memory before this is used as shadow memory, and thus the shadow mapping function is simply dividing by 8. Reviewers: tlively, aheejin, sbc100 Reviewed By: sbc100 Subscribers: dschuff, sbc100, jgravelle-google, hiraditya, sunfish, cfe-commits, llvm-commits Tags: #clang, #llvm Differential Revision: https://reviews.llvm.org/D63742 llvm-svn: 364468
* [IndVars] Kill a redundant bit of debug outputPhilip Reames2019-06-261-2/+0
| | | | llvm-svn: 364449
* [InstCombine] simplify code for inserts -> splat; NFCSanjay Patel2019-06-261-25/+17
| | | | llvm-svn: 364441
* Revert "r364412 [ExpandMemCmp][MergeICmps] Move passes out of CodeGen into ↵Clement Courbet2019-06-265-912/+1
| | | | | | | | | | | | | | opt pipeline." Breaks sanitizers: libFuzzer :: cxxstring.test libFuzzer :: memcmp.test libFuzzer :: recommended-dictionary.test libFuzzer :: strcmp.test libFuzzer :: value-profile-mem.test libFuzzer :: value-profile-strcmp.test llvm-svn: 364416
* [ExpandMemCmp][MergeICmps] Move passes out of CodeGen into opt pipeline.Clement Courbet2019-06-265-1/+912
| | | | | | | | | This allows later passes (in particular InstCombine) to optimize more cases. One that's important to us is `memcmp(p, q, constant) < 0` and memcmp(p, q, constant) > 0. llvm-svn: 364412
* [LoopUnroll] Add support for loops with exiting headers and uncond latches.Florian Hahn2019-06-261-60/+170
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch generalizes the UnrollLoop utility to support loops that exit from the header instead of the latch. Usually, LoopRotate would take care of must of those cases, but in some cases (e.g. -Oz), LoopRotate does not kick in. Codesize impact looks relatively neutral on ARM64 with -Oz + LTO. Program master patch diff External/S.../CFP2006/447.dealII/447.dealII 629060.00 627676.00 -0.2% External/SPEC/CINT2000/176.gcc/176.gcc 1245916.00 1244932.00 -0.1% MultiSourc...Prolangs-C/simulator/simulator 86100.00 86156.00 0.1% MultiSourc...arks/Rodinia/backprop/backprop 66212.00 66252.00 0.1% MultiSourc...chmarks/Prolangs-C++/life/life 67276.00 67312.00 0.1% MultiSourc...s/Prolangs-C/compiler/compiler 69824.00 69788.00 -0.1% MultiSourc...Prolangs-C/assembler/assembler 86672.00 86696.00 0.0% Reviewers: efriedma, vsk, paquette Reviewed By: paquette Differential Revision: https://reviews.llvm.org/D61962 llvm-svn: 364398
* [InstCombine] Simplify icmp ult/uge (shl %x, C2), C1 iff C1 is power of two ↵Huihui Zhang2019-06-251-0/+21
| | | | | | | | | | | | | | | | | | | | | | | -> icmp eq/ne (and %x, (lshr -C1, C2)), 0. Simplify 'shl' inequality test into 'and' equality test. This pattern happens in the middle-end while simplifying bitfield access, Exposed in https://reviews.llvm.org/D63505 https://rise4fun.com/Alive/6uz Reviewers: lebedev.ri, efriedma Reviewed By: lebedev.ri Subscribers: spatel, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63675 llvm-svn: 364348
* [LFTR] Adjust debug output to include extensions (if any)Philip Reames2019-06-251-7/+8
| | | | llvm-svn: 364346
* [InstCombine] reduce checks for power-of-2-or-zero using ctpopSanjay Patel2019-06-251-12/+10
| | | | | | | | | | | | | | | | | | | | | | | This follows up the transform from rL363956 to use the ctpop intrinsic when checking for power-of-2-or-zero. This is matching the isPowerOf2() patterns used in PR42314: https://bugs.llvm.org/show_bug.cgi?id=42314 But there's at least 1 instcombine follow-up needed to match the alternate form: (v & (v - 1)) == 0; We should have all of the backend expansions handled with: rL364319 (x86-specific changes still needed for optimal code based on subtarget) And the larger patterns to exclude zero as a power-of-2 are joining with this change after: rL364153 ( D63660 ) rL364246 Differential Revision: https://reviews.llvm.org/D63777 llvm-svn: 364341
* Expand cloneLoopWithPreheader() to support cloning loop nestWhitney Tsang2019-06-251-10/+31
| | | | | | | | | | | | Summary: cloneLoopWithPreheader() currently only support innermost loop, and assert otherwise. Reviewers: Meinersbur, fhahn, kbarton Reviewed By: Meinersbur Subscribers: hiraditya, jsji, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D63446 llvm-svn: 364310
* [ExpandMemCmp] Move all options to TargetTransformInfo.Clement Courbet2019-06-251-1/+1
| | | | | | Split off from D60318. llvm-svn: 364281
* [InstCombine] Fold icmp eq/ne (and %x, C), 0 iff (-C) is power of two -> %x ↵Huihui Zhang2019-06-251-11/+9
| | | | | | | | | | | | | | | | | | | | | | | | | u</u>= (-C) earlier. Summary: To generate simplified IR, make sure fold (X & ~C) ==/!= 0 --> X u</u>= C+1 is scheduled before fold ((X << Y) & C) == 0 -> (X & (C >> Y)) == 0. https://rise4fun.com/Alive/7ZN Reviewers: lebedev.ri, efriedma, spatel, craig.topper Reviewed By: lebedev.ri Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63505 llvm-svn: 364255
* [InstCombine] squash is-not-power-of-2 using ctpopSanjay Patel2019-06-241-5/+18
| | | | | | | | | | | | | | | | This is the Demorgan'd 'not' of the pattern handled in: D63660 / rL364153 This is another intermediate IR step towards solving PR42314: https://bugs.llvm.org/show_bug.cgi?id=42314 We can test if a value is not a power-of-2 using ctpop(X) > 1, so combining that with an is-zero check of the input is the same as testing if not exactly 1 bit is set: (X == 0) || (ctpop(X) u> 1) --> ctpop(X) != 1 llvm-svn: 364246
* [SLP] NFC: Fixed typo in commentVasileios Porpodas2019-06-241-1/+1
| | | | llvm-svn: 364237
* InstCombine: Preserve nuw when reassociating nuw ops [3/3]Matt Arsenault2019-06-241-15/+27
| | | | | | Alive says this is OK. llvm-svn: 364235
* InstCombine: Preserve nuw when reassociating nuw ops [2/3]Matt Arsenault2019-06-241-2/+10
| | | | | | Alive says this is OK. llvm-svn: 364234
* InstCombine: Preserve nuw when reassociating nuw ops [1/3]Matt Arsenault2019-06-241-4/+14
| | | | | | Alive says this is OK. llvm-svn: 364233
* [CVP] Reenable nowrap flag inferenceNikita Popov2019-06-241-1/+1
| | | | | | | | | | | Inference of nowrap flags in CVP has been disabled, because it triggered a bug in LFTR (https://bugs.llvm.org/show_bug.cgi?id=31181). This issue has been fixed in D60935, so we should be able to reenable nowrap flag inference now. Differential Revision: https://reviews.llvm.org/D62776 llvm-svn: 364228
* [SLP] Support unary FNeg vectorizationCameron McInally2019-06-241-2/+30
| | | | | | Differential Revision: https://reviews.llvm.org/D63609 llvm-svn: 364219
* [InstCombine] reduce funnel-shift i16 X, X, 8 to bswap XSanjay Patel2019-06-241-0/+7
| | | | | | | | | | Prefer the more exact intrinsic to remove a use of the input value and possibly make further transforms easier (we will still need to match patterns with funnel-shift of wider types as pieces of bswap, especially if we want to canonicalize to funnel-shift with constant shift amount). Discussed in D46760. llvm-svn: 364187
* [InstCombine] SliceUpIllegalIntegerPHI - bail on out of range shiftsSimon Pilgrim2019-06-241-0/+5
| | | | | | | | trunc(lshr) handling - if the shift is out of range (undefined) then bail like we do for non-constant shifts. Fixes OSS Fuzz #15217 llvm-svn: 364181
* Fix typo in comment; NFCSanjoy Das2019-06-231-1/+1
| | | | llvm-svn: 364159
* [IndVars] Remove dead instructions after folding trivial loop exitPhilip Reames2019-06-231-3/+5
| | | | | | In rL364135, I taught IndVars to fold exiting branches in loops with a zero backedge taken count (i.e. loops that only run one iteration). This extends that to eliminate the dead comparison left around. llvm-svn: 364155
* [InstCombine] squash is-power-of-2 that uses ctpopSanjay Patel2019-06-231-0/+23
| | | | | | | | | | | | | | | This is another intermediate IR step towards solving PR42314: https://bugs.llvm.org/show_bug.cgi?id=42314 We can test if a value is power-of-2-or-0 using ctpop(X) < 2, so combining that with a non-zero check of the input is the same as testing if exactly 1 bit is set: (X != 0) && (ctpop(X) u< 2) --> ctpop(X) == 1 Differential Revision: https://reviews.llvm.org/D63660 llvm-svn: 364153
* Exploit a zero LoopExit count to eliminate loop exitsPhilip Reames2019-06-221-2/+14
| | | | | | | | | | This turned out to be surprisingly effective. I was originally doing this just for completeness sake, but it seems like there are a lot of cases where SCEV's exit count reasoning is stronger than it's isKnownPredicate reasoning. Once this is in, I'm thinking about trying to build on the same infrastructure to eliminate provably untaken checks. There may be something generally interesting here. Differential Revision: https://reviews.llvm.org/D63618 llvm-svn: 364135
* [NewGVN] Fix copy/paste mistake in castNikita Popov2019-06-221-1/+1
| | | | llvm-svn: 364130
* [NewGVN] Remove dead SwitchEdges variable; NFCNikita Popov2019-06-221-4/+0
| | | | llvm-svn: 364129
* Revert [SLP] Look-ahead operand reordering heuristic.Reid Kleckner2019-06-211-232/+46
| | | | | | | | | This reverts r364084 (git commit 5698921be2d567f6abf925479ac9f5a376d6d74f) It caused crashes while compiling a file in Chrome. Reduction forthcoming. llvm-svn: 364111
* [ASan] Use dynamic shadow on 32-bit iOS and simulatorsJulian Lettner2019-06-211-10/+2
| | | | | | | | | | | | | | | | | | | | The VM layout on iOS is not stable between releases. On 64-bit iOS and its derivatives we use a dynamic shadow offset that enables ASan to search for a valid location for the shadow heap on process launch rather than hardcode it. This commit extends that approach for 32-bit iOS plus derivatives and their simulators. rdar://50645192 rdar://51200372 rdar://51767702 Reviewed By: delcypher Differential Revision: https://reviews.llvm.org/D63586 llvm-svn: 364105
* [SLP] Look-ahead operand reordering heuristic.Simon Pilgrim2019-06-211-46/+232
| | | | | | | | | | This patch introduces a new heuristic for guiding operand reordering. The new "look-ahead" heuristic can look beyond the immediate predecessors. This helps break ties when the immediate predecessors have identical opcodes (see lit test for an example). Committed on behalf of @vporpo (Vasileios Porpodas) Differential Revision: https://reviews.llvm.org/D60897 llvm-svn: 364084
* [InstCombine] (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1David Bolvansky2019-06-211-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: ``` %a = sub i32 31, %x %r = shl i32 1, %a => %d = shl i32 1, 31 %r = lshr i32 %d, %x Done: 1 Optimization is correct! ``` https://rise4fun.com/Alive/btZm Reviewers: spatel, lebedev.ri, nikic Reviewed By: lebedev.ri Subscribers: llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63652 llvm-svn: 364073
* [InstCombine] cttz(abs(x)) -> cttz(x)David Bolvansky2019-06-211-4/+15
| | | | | | | | | | | | Summary: Signedness does not change number of trailing zeros. Reviewers: spatel, lebedev.ri, nikic Reviewed By: lebedev.ri Differential Revision: https://reviews.llvm.org/D63546 llvm-svn: 364064
* [GVNSink] prevent crashing on mismatched instructions (PR42346)Sanjay Patel2019-06-211-0/+9
| | | | | | | Patch based on suggestion by James Molloy (@jmolloy) in: https://bugs.llvm.org/show_bug.cgi?id=42346 llvm-svn: 364062
* [Scalarizer] Propagate IR flagsJay Foad2019-06-211-4/+6
| | | | | | | | | | | | | | | | | | Summary: The motivation for this was to propagate fast-math flags like nnan and ninf on vector floating point operations to the corresponding scalar operations to take advantage of follow-on optimizations. But I think the same argument applies to all of our IR flags: if they apply to the vector operation then they also apply to all the individual scalar operations, and they might enable follow-on optimizations. Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63593 llvm-svn: 364051
* Simplify std::lower_bound with llvm::{bsearch,lower_bound}. NFCFangrui Song2019-06-214-6/+5
| | | | llvm-svn: 364006
* [Reassociate] Remove bogus assert reported in PR42349.Cameron McInally2019-06-201-5/+1
| | | | | | | | Also, add a FIXME for the unsafe transform on a unary FNeg. A unary FNeg can only be transformed to a FMul by -1.0 when the nnan flag is present. The unary FNeg project is a WIP, so the unsafe transformation is acceptable until that work is complete. The bogus assert with introduced in D63445. llvm-svn: 363998
* [profile] Solaris ld supports __start___llvm_prof_data etc. labelsRainer Orth2019-06-201-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Currently, many profiling tests on Solaris FAIL like Command Output (stderr): -- Undefined first referenced symbol in file __llvm_profile_register_names_function /tmp/lit_tmp_Nqu4eh/infinite_loop-9dc638.o __llvm_profile_register_function /tmp/lit_tmp_Nqu4eh/infinite_loop-9dc638.o Solaris 11.4 ld supports the non-standard GNU ld extension of adding __start_SECNAME and __stop_SECNAME labels to sections whose names are valid as C identifiers. Given that we already use Solaris 11.4-only features like ld -z gnu-version-script-compat and fully working .preinit_array support in compiler-rt, we don't need to worry about older versions of Solaris ld. The patch documents that support (although the comment in lib/Transforms/Instrumentation/InstrProfiling.cpp (needsRuntimeRegistrationOfSectionRange) is quite cryptic what it's actually about), and adapts the affected testcase not to expect the alternativeq __llvm_profile_register_functions and __llvm_profile_init. It fixes all affected tests. Tested on amd64-pc-solaris2.11. Differential Revision: https://reviews.llvm.org/D41111 llvm-svn: 363984
* [LICM & MSSA] Limit unsafe sinking and hoisting.Alina Sbirlea2019-06-201-10/+50
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The getClobberingMemoryAccess API checks for clobbering accesses in a loop by walking the backedge. This may check if a memory access is being clobbered by the loop in a previous iteration, depending how smart AA got over the course of the updates in MemorySSA (it does not occur when built from scratch). If no clobbering access is found inside the loop, it will optimize to an access outside the loop. This however does not mean that access is safe to sink. Given: ``` for i load a[i] store a[i] ``` The access corresponding to the load can be optimized to outside the loop, and the load can be hoisted. But it is incorrect to sink it. In order to sink the load, we'd need to check no Def clobbers the Use in the same iteration. With this patch we currently restrict sinking to either Defs not existing in the loop, or Defs preceding the load in the same block. An easy extension is to ensure the load (Use) post-dominates all Defs. Caught by PR42294. This issue also shed light on the converse problem: hoisting stores in this same scenario would be illegal. With this patch we restrict hoisting of stores to the case when their corresponding Defs are dominating all Uses in the loop. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63582 llvm-svn: 363982
* [InstCombine] fix typo in comment; NFCSanjay Patel2019-06-201-1/+1
| | | | llvm-svn: 363974
* [LFTR] Fix a (latent?) bug related to nested loopsPhilip Reames2019-06-201-0/+6
| | | | | | | | I can't actually come up with a test case this triggers on without an out of tree change, but in theory, it's a bug in the recently added multiple exit LFTR support. The root issue is that an exiting block common to two loops can (in theory) have computable exit counts for both loops. Rewriting the exit of an inner loop in terms of the outer loops IV would cause the inner loop to either a) run forever, or b) terminate on the first iteration. In practice, we appear to get lucky and not have the exit count computable for the outer loop, except when it's trivially zero. Given we bail on zero exit counts, we don't appear to ever trigger this. But I can't come up with a reason we *can't* compute an exit count for the outer loop on the common exiting block, so this may very well be triggering in some cases. llvm-svn: 363964
* [InstCombine] canonicalize check for power-of-2Sanjay Patel2019-06-201-0/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The form that compares against 0 is better because: 1. It removes a use of the input value. 2. It's the more standard form for this pattern: https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 3. It results in equal or better codegen (tested with x86, AArch64, ARM, PowerPC, MIPS). This is a root cause for PR42314, but probably doesn't completely answer the codegen request: https://bugs.llvm.org/show_bug.cgi?id=42314 Alive proof: https://rise4fun.com/Alive/9kG Name: is power-of-2 %neg = sub i32 0, %x %a = and i32 %neg, %x %r = icmp eq i32 %a, %x => %dec = add i32 %x, -1 %a2 = and i32 %dec, %x %r = icmp eq i32 %a2, 0 Name: is not power-of-2 %neg = sub i32 0, %x %a = and i32 %neg, %x %r = icmp ne i32 %a, %x => %dec = add i32 %x, -1 %a2 = and i32 %dec, %x %r = icmp ne i32 %a2, 0 llvm-svn: 363956
* [InstCombine] cttz(-x) -> cttz(x)David Bolvansky2019-06-201-0/+6
| | | | | | | | | | | | | | | | Summary: Signedness does not change number of trailing zeros. Reviewers: spatel, lebedev.ri, nikic Reviewed By: spatel Subscribers: llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63534 llvm-svn: 363951
* LFTR for multiple exit loopsPhilip Reames2019-06-191-17/+16
| | | | | | | | | | | | | | Teach IndVarSimply's LinearFunctionTestReplace transform to handle multiple exit loops. LFTR does two key things 1) it rewrites (all) exit tests in terms of a common IV potentially eliminating one in the process and 2) it moves any offset/indexing/f(i) style logic out of the loop. This turns out to actually be pretty easy to implement. SCEV already has all the information we need to know what the backedge taken count is for each individual exit. (We use that when computing the BE taken count for the loop as a whole.) We basically just need to iterate through the exiting blocks and apply the existing logic with the exit specific BE taken count. (The previously landed NFC makes this super obvious.) I chose to go ahead and apply this to all loop exits instead of only latch exits as originally proposed. After reviewing other passes, the only case I could find where LFTR form was harmful was LoopPredication. I've fixed the latch case, and guards aren't LFTRed anyways. We'll have some more work to do on the way towards widenable_conditions, but that's easily deferred. I do want to note that I added one bit after the review. When running tests, I saw a new failure (no idea why didn't see previously) which pointed out LFTR can rewrite a constant condition back to a loop varying one. This was theoretically possible with a single exit, but the zero case covered it in practice. With multiple exits, we saw this happening in practice for the eliminate-comparison.ll test case because we'd compute a ExitCount for one of the exits which was guaranteed to never actually be reached. Since LFTR ran after simplifyAndExtend, we'd immediately turn around and undo the simplication work we'd just done. The solution seemed obvious, so I didn't bother with another round of review. Differential Revision: https://reviews.llvm.org/D62625 llvm-svn: 363883
* [LFTR] Stylistic cleanup as suggested in last review comment of D62939 [NFC]Philip Reames2019-06-191-9/+9
| | | | | | (Resumbit of r363292 which was reverted along w/an earlier patch) llvm-svn: 363877
* [LFTR] Rename variable to minimize confusion [NFC]Philip Reames2019-06-191-15/+15
| | | | | | | | (Recommit of r363293 which was reverted when a dependent patch was.) As pointed out by Nikita in D62625, BackedgeTakenCount is generally used to refer to the backedge taken count of the loop. A conditional backedge taken count - one which only applies if a particular exit is taken - is called a ExitCount in SCEV code, so be consistent here. llvm-svn: 363875
* [InstCombine] Fold icmp eq/ne (and %x, signbit), 0 -> %x s>=/s< 0 earlierHuihui Zhang2019-06-191-10/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: To generate simplified IR, make sure fold ``` (X & signbit) ==/!= 0) -> X s>=/s< 0; ``` is scheduled before fold ``` ((X << Y) & C) == 0 -> (X & (C >> Y)) == 0. ``` https://rise4fun.com/Alive/fbdh Reviewers: lebedev.ri, efriedma, spatel, craig.topper Reviewed By: lebedev.ri Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63026 llvm-svn: 363845
* [DFSan] Add UnaryOperator visitor to DataFlowSanitizerCameron McInally2019-06-191-0/+5
| | | | | | Differential Revision: https://reviews.llvm.org/D62815 llvm-svn: 363814
OpenPOWER on IntegriCloud