summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [SCEV] Introduce ScalarEvolution::getOne and getZero.Sanjoy Das2015-09-231-1/+1
| | | | | | | | | | | | | | | | | | Summary: It is fairly common to call SE->getConstant(Ty, 0) or SE->getConstant(Ty, 1); this change makes such uses a little bit briefer. I've refactored the call sites I could find easily to use getZero / getOne. Reviewers: hfinkel, majnemer, reames Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12947 llvm-svn: 248362
* [PM] Port ScalarEvolution to the new pass manager.Chandler Carruth2015-08-171-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change makes ScalarEvolution a stand-alone object and just produces one from a pass as needed. Making this work well requires making the object movable, using references instead of overwritten pointers in a number of places, and other refactorings. I've also wired it up to the new pass manager and added a RUN line to a test to exercise it under the new pass manager. This includes basic printing support much like with other analyses. But there is a big and somewhat scary change here. Prior to this patch ScalarEvolution was never *actually* invalidated!!! Re-running the pass just re-wired up the various other analyses and didn't remove any of the existing entries in the SCEV caches or clear out anything at all. This might seem OK as everything in SCEV that can uses ValueHandles to track updates to the values that serve as SCEV keys. However, this still means that as we ran SCEV over each function in the module, we kept accumulating more and more SCEVs into the cache. At the end, we would have a SCEV cache with every value that we ever needed a SCEV for in the entire module!!! Yowzers. The releaseMemory routine would dump all of this, but that isn't realy called during normal runs of the pipeline as far as I can see. To make matters worse, there *is* actually a key that we don't update with value handles -- there is a map keyed off of Loop*s. Because LoopInfo *does* release its memory from run to run, it is entirely possible to run SCEV over one function, then over another function, and then lookup a Loop* from the second function but find an entry inserted for the first function! Ouch. To make matters still worse, there are plenty of updates that *don't* trip a value handle. It seems incredibly unlikely that today GVN or another pass that invalidates SCEV can update values in *just* such a way that a subsequent run of SCEV will incorrectly find lookups in a cache, but it is theoretically possible and would be a nightmare to debug. With this refactoring, I've fixed all this by actually destroying and recreating the ScalarEvolution object from run to run. Technically, this could increase the amount of malloc traffic we see, but then again it is also technically correct. ;] I don't actually think we're suffering from tons of malloc traffic from SCEV because if we were, the fact that we never clear the memory would seem more likely to have come up as an actual problem before now. So, I've made the simple fix here. If in fact there are serious issues with too much allocation and deallocation, I can work on a clever fix that preserves the allocations (while clearing the data) between each run, but I'd prefer to do that kind of optimization with a test case / benchmark that shows why we need such cleverness (and that can test that we actually make it faster). It's possible that this will make some things faster by making the SCEV caches have higher locality (due to being significantly smaller) so until there is a clear benchmark, I think the simple change is best. Differential Revision: http://reviews.llvm.org/D12063 llvm-svn: 245193
* Roll forward r243250Jingyue Wu2015-07-261-0/+1
| | | | | | | | | r243250 appeared to break clang/test/Analysis/dead-store.c on one of the build slaves, but I couldn't reproduce this failure locally. Probably a false positive as I saw this test was broken by r243246 or r243247 too but passed later without people fixing anything. llvm-svn: 243253
* Revert r243250Jingyue Wu2015-07-261-1/+0
| | | | | | breaks tests llvm-svn: 243251
* [TTI/CostModel] improve TTI::getGEPCost and use it in ↵Jingyue Wu2015-07-261-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | CostModel::getInstructionCost Summary: This patch updates TargetTransformInfoImplCRTPBase::getGEPCost to consider addressing modes. It now returns TCC_Free when the GEP can be completely folded to an addresing mode. I started this patch as I refactored SLSR. Function isGEPFoldable looks common and is indeed used by some WIP of mine. So I extracted that logic to getGEPCost. Furthermore, I noticed getGEPCost wasn't directly tested anywhere. The best testing bed seems CostModel, but its getInstructionCost method invokes getAddressComputationCost for GEPs which provides very coarse estimation. So this patch also makes getInstructionCost call the updated getGEPCost for GEPs. This change inevitably breaks some tests because the cost model changes, but nothing looks seriously wrong -- if we believe the new cost model is the right way to go, these tests should be updated. This patch is not perfect yet -- the comments in some tests need to be updated. I want to know whether this is a right approach before fixing those details. Reviewers: chandlerc, hfinkel Subscribers: aschwaighofer, llvm-commits, aemerson Differential Revision: http://reviews.llvm.org/D9819 llvm-svn: 243250
* [SLSR] S's basis must have the same type as SJingyue Wu2015-06-281-2/+4
| | | | llvm-svn: 240910
* [NFC] more comments in SLSRJingyue Wu2015-06-181-0/+9
| | | | llvm-svn: 239984
* SLSR: Pass address space to isLegalAddressingModeMatt Arsenault2015-06-111-1/+3
| | | | | | | | | This only updates one of the uses. The other is used in cases that may never touch memory, so I'm not sure why this is even calling it. Perhaps there should be a new, similar hook for such cases or pass -1 for unknown address space. llvm-svn: 239540
* [ScalarEvolution] refactor: extract interface getGEPExprJingyue Wu2015-05-181-15/+18
| | | | | | | | | | | | | | | | | | Summary: This allows other passes (such as SLSR) to compute the SCEV expression for an imaginary GEP. Test Plan: no regression Reviewers: atrick, sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9786 llvm-svn: 237589
* [SLSR] handle (B | i) * SJingyue Wu2015-05-151-3/+21
| | | | | | | | | | | | | | | | Summary: Consider (B | i) * S as (B + i) * S if B and i have no bits set in common. Test Plan: @or in slsr-mul.ll Reviewers: broune, meheff Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9788 llvm-svn: 237456
* [SLSR] handles non-canonicalized Mul candidatesJingyue Wu2015-05-131-2/+2
| | | | | | | | such as (2 + B) * S. Tested by @non_canonicalized in slsr-mul.ll llvm-svn: 237216
* [SLSR] garbage-collect unused instructionsJingyue Wu2015-04-211-3/+13
| | | | | | | | | | | | | | | | | Summary: After we rewrite a candidate, the instructions used by the old form may become unused. This patch cleans up these unused instructions so that we needn't run DCE after SLSR. Test Plan: removed -dce in all the SLSR tests Reviewers: broune, meheff Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9101 llvm-svn: 235410
* [SLSR] handle candidate form (B + i * S)Jingyue Wu2015-04-151-91/+222
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: With this patch, SLSR may rewrite S1: X = B + i * S S2: Y = B + i' * S to S2: Y = X + (i' - i) * S A secondary improvement: if (i' - i) is a power of 2, emit Y as X + (S << log(i' - i)). (S << log(i' -i)) is in a canonical form and thus more likely GVN'ed than (i' - i) * S. Test Plan: slsr-add.ll Reviewers: hfinkel, sanjoy, meheff, broune, eliben Reviewed By: eliben Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8983 llvm-svn: 235019
* [SLSR] consider &B[S << i] as &B[(1 << i) * S]Jingyue Wu2015-04-061-2/+7
| | | | | | | | | | | | | | Summary: This reduces handling &B[(1 << i) * s] to handling &B[i * S]. Test Plan: slsr-gep.ll Reviewers: meheff Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D8837 llvm-svn: 234180
* [opaque pointer type] More GEP IRBuilder API migrations...David Blaikie2015-04-031-2/+3
| | | | llvm-svn: 234058
* [opaque pointer type] More GEP API migrations in IRBuilder usesDavid Blaikie2015-04-031-2/+2
| | | | | | | | | | | | | The plan here is to push the API changes out from the common components (like Constant::getGetElementPtr and IRBuilder::CreateGEP related functions) and just update callers to either pass the type if it's obvious, or pass null. Do this with LoadInst as well and anything else that comes up, then to start porting specific uses to not pass null anymore - this may require some refactoring in each case. llvm-svn: 234042
* [SLSR] handles off bounds GEPsJingyue Wu2015-04-021-5/+12
| | | | | | | | | | | | | | | | | | Summary: The old requirement on GEP candidates being in bounds is unnecessary. For off-bound GEPs, we still have &B[i * S] = B + (i * S) * e = B + (i * e) * S Test Plan: slsr_offbound_gep in slsr-gep.ll Reviewers: meheff Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8809 llvm-svn: 233949
* [SLSR] handle candidate form &B[i * S]Jingyue Wu2015-03-261-67/+328
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch enhances SLSR to handle another candidate form &B[i * S]. If we found two candidates S1: X = &B[i * S] S2: Y = &B[i' * S] and S1 dominates S2, we can replace S2 with Y = &X[(i' - i) * S] Test Plan: slsr-gep.ll X86/no-slsr.ll: verify that we do not run SLSR on GEPs that already fit into an addressing mode Reviewers: eliben, atrick, meheff, hfinkel Reviewed By: hfinkel Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D7459 llvm-svn: 233286
* Fixing a -Wsign-compare warning; NFCAaron Ballman2015-02-041-1/+1
| | | | llvm-svn: 228142
* Add straight-line strength reduction to LLVMJingyue Wu2015-02-031-0/+274
Summary: Straight-line strength reduction (SLSR) is implemented in GCC but not yet in LLVM. It has proven to effectively simplify statements derived from an unrolled loop, and can potentially benefit many other cases too. For example, LLVM unrolls #pragma unroll foo (int i = 0; i < 3; ++i) { sum += foo((b + i) * s); } into sum += foo(b * s); sum += foo((b + 1) * s); sum += foo((b + 2) * s); However, no optimizations yet reduce the internal redundancy of the three expressions: b * s (b + 1) * s (b + 2) * s With SLSR, LLVM can optimize these three expressions into: t1 = b * s t2 = t1 + s t3 = t2 + s This commit is only an initial step towards implementing a series of such optimizations. I will implement more (see TODO in the file commentary) in the near future. This optimization is enabled for the NVPTX backend for now. However, I am more than happy to push it to the standard optimization pipeline after more thorough performance tests. Test Plan: test/StraightLineStrengthReduce/slsr.ll Reviewers: eliben, HaoLiu, meheff, hfinkel, jholewinski, atrick Reviewed By: jholewinski, atrick Subscribers: karthikthecool, jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D7310 llvm-svn: 228016
OpenPOWER on IntegriCloud