summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
* [NaryReassociate] run NaryReassociate iterativelyJingyue Wu2015-04-171-7/+47
| | | | | | | | | | | | | | | | | | | | | | | Summary: An alternative is to use a worklist approach. However, that approach would break the traversing order so that we couldn't lookup SeenExprs efficiently. I don't see a clear winner here, so I picked the easier approach. Along with two minor improvements: 1. preserves ScalarEvolution by forgetting instructions replaced 2. removes dead code locally avoiding the need of running DCE afterwards Test Plan: add to slsr-add.ll a test that requires multiple iterations Reviewers: broune, dberlin, atrick, meheff Reviewed By: atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D9058 llvm-svn: 235151
* [NaryReassociate] speeds up candidate searchingJingyue Wu2015-04-161-9/+15
| | | | | | | | | | | | | | | | | | | | | Summary: This fixes a left-over efficiency issue in D8950. As Andrew and Daniel suggested, we can store the candidates in a stack and pop the top element when it does not dominate the current instruction. This reduces the worst-case time complexity to O(n). Test Plan: a new test in nary-add.ll that exercises this optimization. Reviewers: broune, dberlin, meheff, atrick Reviewed By: atrick Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D9055 llvm-svn: 235129
* DebugInfo: Require a DebugLoc in DIBuilder::insertDeclare()Duncan P. N. Exon Smith2015-04-152-10/+8
| | | | | | | | | | | | | | | | | | | | | Change `DIBuilder::insertDeclare()` and `insertDbgValueIntrinsic()` to take an `MDLocation*`/`DebugLoc` parameter which it attaches to the created intrinsic. Assert at creation time that the `scope:` field's subprogram matches the variable's. There's a matching `clang` commit to use the API. The context for this is PR22778, which is removing the `inlinedAt:` field from `MDLocalVariable`, instead deferring to the `!dbg` location attached to the debug info intrinsic. The best way to ensure we always have a `!dbg` attachment is to require one at creation time. I'll be adding verifier checks next, but this API change is the best way to shake out frontend bugs. Note: I added an `llvm_unreachable()` in `bindings/go` and passed in `nullptr` for the `DebugLoc`. The `llgo` folks will eventually need to pass a valid `DebugLoc` here. llvm-svn: 235041
* [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
* Change range-based for-loops to be -Wrange-loop-analysis clean.Richard Trieu2015-04-151-1/+1
| | | | | | No functionality change. llvm-svn: 234963
* Simplify n-ary adds by reassociationJingyue Wu2015-04-143-0/+208
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This transformation reassociates a n-ary add so that the add can partially reuse existing instructions. For example, this pass can simplify void foo(int a, int b) { bar(a + b); bar((a + 2) + b); } to void foo(int a, int b) { int t = a + b; bar(t); bar(t + 2); } saving one add instruction. Fixes PR22357 (https://llvm.org/bugs/show_bug.cgi?id=22357). Test Plan: nary-add.ll Reviewers: broune, dberlin, hfinkel, meheff, sanjoy, atrick Reviewed By: sanjoy, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8950 llvm-svn: 234855
* DebugInfo: Gut DISubprogram and DILexicalBlock*Duncan P. N. Exon Smith2015-04-141-2/+2
| | | | | | | Gut the `DIDescriptor` wrappers around `MDLocalScope` subclasses. Note that `DILexicalBlock` wraps `MDLexicalBlockBase`, not `MDLexicalBlock`. llvm-svn: 234850
* [LoopUnrollRuntime] Avoid high-cost trip count computation.Sanjoy Das2015-04-141-2/+3
| | | | | | | | | | | | | | | | | Summary: Runtime unrolling of loops needs to emit an expression to compute the loop's runtime trip-count. Avoid runtime unrolling if this computation will be expensive. Depends on D8993. Reviewers: atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8994 llvm-svn: 234846
* [SCEV] Refactor out isHighCostExpansion. NFCI.Sanjoy Das2015-04-141-56/+6
| | | | | | | | | | | | | | Summary: Move isHighCostExpansion from IndVarSimplify to SCEVExpander. This exposed function will be used in a subsequent change. Reviewers: bogner, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8995 llvm-svn: 234844
* DebugInfo: Gut DILocationDuncan P. N. Exon Smith2015-04-141-1/+1
| | | | | | | | This is along the same lines as r234832, but for `DILocation`. Clean out all accessors from `DILocation`. Any callers should be using `MDLocation` directly (e.g., via `operator->()`). llvm-svn: 234835
* DebugInfo: Gut DIExpressionDuncan P. N. Exon Smith2015-04-141-4/+4
| | | | | | | | | | | | | | | | Completely gut `DIExpression`, turning it into a simple wrapper around `MDExpression *`. There are two bits of magic left: - It's constructed from `const MDExpression*` but convertible to `MDExpression*`. - It's default-constructed to `nullptr`. Otherwise, it should behave quite like a raw pointer. Once I've done the same to the rest of the `DIDescriptor` subclasses, I'll come back to delete them entirely (and update call sites as necessary to deal with the missing magic). llvm-svn: 234832
* [RewriteStatepointsForGC] Delete dead code [NFC]Philip Reames2015-04-141-26/+4
| | | | | | | | | Before we had real liveness, we needed to track every value that base pointer insertion code created because these now might be live. We now just rerun the data flow liveness algorithm (which is actually faster!) and no longer need the associated code. llvm-svn: 234827
* [RwriteStatepointsForGC] Minor indentation and naming [NFC]Philip Reames2015-04-131-39/+30
| | | | | | Use early-return style that's preferred in LLVM and updating the naming in places I touched with other changes in the last few days. Hopefully, NFC. llvm-svn: 234785
* [RewriteStatepointsForGC] Avoid inserting empty holderPhilip Reames2015-04-131-0/+4
| | | | | | We use dummy calls to adjust the liveness of values over statepoints in the midst of the insertion. If there are no values which need held live, there's no point in actually inserting the holder. llvm-svn: 234779
* [RewriteStatepointsForGC] Fix a latent bug in normalization for invoke ↵Philip Reames2015-04-131-37/+40
| | | | | | | | | | statepoint [NFC] Since we're restructuring the CFG, we also need to make sure to update the analsis passes. While I'm touching the code, I dedicided to restructure it a bit. The code involved here was very confusing. This change moves the normalization to essentially being a pre-pass before the main insertion work and updates a few comments to actually say what is happening and *why*. The restructuring should be covered by existing tests. I couldn't easily see how to create a test for the invalidation bug. Suggestions welcome. llvm-svn: 234769
* [RewriteStatepointsForGC] Strengthen assertions around livenessPhilip Reames2015-04-131-0/+18
| | | | | | This is related to the issues addressed in 234651. These assertions check the properties ensured by that change at the place of use. Note that a similiar property is checked in checkBasicSSA, but without the reachability constraint. Technically, the liveness would be correct to include unreachable values, but this would be problematic for actual relocation. llvm-svn: 234766
* [RewriteStatepointsForGC] Move an expensive debugging check to XDEBUGPhilip Reames2015-04-131-33/+44
| | | | | | | | | | The check in question is attempting to help find cases where we haven't relocated a pointer at a safepoint we should have. It does this by coercing the value to null at any safepoint which doesn't relocate it. Unfortunately, this turns out to be rather expensive in terms of memory usage and time. The number of stores inserted can grow with O(number of values x number of statepoints). On at least one example I looked at, over half of peak memory usage was coming from this check. With this change, the check is no longer enabled by default in Asserts builds. It is enabled for expensive asserts builds and has a command line option to enable it in both Asserts and non-Asserts builds. llvm-svn: 234761
* Mark empty default constructors as =default if it makes the type PODBenjamin Kramer2015-04-112-3/+1
| | | | | | NFC llvm-svn: 234694
* Use 'override/final' instead of 'virtual' for overridden methodsAlexander Kornienko2015-04-111-2/+2
| | | | | | | | | | | | | | The patch is generated using clang-tidy misc-use-override check. This command was used: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py \ -checks='-*,misc-use-override' -header-filter='llvm|clang' \ -j=32 -fix -format http://reviews.llvm.org/D8925 llvm-svn: 234679
* [Statepoints] Fix a release only build failurePhilip Reames2015-04-111-2/+2
| | | | | | A function which is used only in Asserts builds needs to be defined only in Asserts builds. llvm-svn: 234667
* [RewriteStatepointsForGC] Use a SetVector for a worklist [NFC]Philip Reames2015-04-101-6/+4
| | | | | | Using a SetVector to replace equivelent but more verbose functionality. llvm-svn: 234662
* [RewriteStatepointsForGC] Use an actual liveness algorithmPhilip Reames2015-04-101-204/+294
| | | | | | | | When rewriting statepoints to make relocations explicit, we need to have a conservative but consistent notion of where a particular pointer is live at a particular site. The old code just used dominance, which is correct, but decidedly more conservative then it needed to be. This patch implements a simple dataflow algorithm that's run one per function (well, twice counting fixup after base pointer insertion). There's still lots of room to make this faster, but it's fast enough for all practical purposes today. Differential Revision: http://reviews.llvm.org/D8674 llvm-svn: 234657
* [RewriteStatepointsForGC] clang-format filePhilip Reames2015-04-101-58/+57
| | | | | | Format the entire file to reduce diff of change to follow. llvm-svn: 234656
* [RewriteStatepointsForGC] Missed review comment from 234651 & build fixPhilip Reames2015-04-101-3/+4
| | | | | | After submitting 234651, I noticed I hadn't responded to a review comment by mjacob. This patch addresses that comment and fixes a Release only build problem due to an unused variable. llvm-svn: 234653
* [RewriteStatepointsForGC] Preprocess the IR to remove unreachable blocks and ↵Philip Reames2015-04-101-6/+34
| | | | | | | | | | | | | | | single entry phis Two related small changes: Various dominance based queries about liveness can get confused if we're talking about unreachable blocks. To avoid reasoning about such cases, just remove them before rewriting statepoints. Remove single entry phis (likely left behind by LCSSA) to reduce the number of live values. Both of these are motivated by http://reviews.llvm.org/D8674 which will be submitted shortly. Differential Revision: http://reviews.llvm.org/D8675 llvm-svn: 234651
* [RewriteStatepointsForGC] Limited support for vectors of pointersPhilip Reames2015-04-101-25/+224
| | | | | | | | | | | | This patch adds limited support for inserting explicit relocations when there's a vector of pointers live over the statepoint. This doesn't handle the case where the vector contains a mix of base and non-base pointers; that's future work. The current implementation just scalarizes the vector over the gc.statepoint before doing the explicit rewrite. An alternate approach would be to plumb the vector all the way though the backend lowering, but doing that appears challenging. In particular, the size of the indirect spill slot is currently assumed to be sizeof(pointer) throughout the backend. In practice, this is enough to allow running the SLP and Loop vectorizers before RewriteStatepointsForGC. Differential Revision: http://reviews.llvm.org/D8671 llvm-svn: 234647
* [CallSite] Make construction from Value* (or Instruction*) explicit.Benjamin Kramer2015-04-103-8/+7
| | | | | | | | | | | | | | | | | | | CallSite roughly behaves as a common base CallInst and InvokeInst. Bring the behavior closer to that model by making upcasts explicit. Downcasts remain implicit and work as before. Following dyn_cast as a mental model checking whether a Value *V isa CallSite now looks like this: if (auto CS = CallSite(V)) // think dyn_cast instead of: if (CallSite CS = V) This is an extra token but I think it is slightly clearer. Making the ctor explicit has the advantage of not accidentally creating nullptr CallSites, e.g. when you pass a Value * to a function taking a CallSite argument. llvm-svn: 234601
* Transforms: Stop using DIDescriptor::is*() and auto-castingDuncan P. N. Exon Smith2015-04-061-2/+1
| | | | | | Same as r234255, but for lib/Analysis and lib/Transforms. llvm-svn: 234257
* [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 migrationsDavid Blaikie2015-04-031-1/+1
| | | | llvm-svn: 234064
* [opaque pointer type] More GEP IRBuilder API migrations...David Blaikie2015-04-032-6/+10
| | | | llvm-svn: 234058
* [opaque pointer type] More GEP API migrations in IRBuilder usesDavid Blaikie2015-04-034-6/+8
| | | | | | | | | | | | | 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
* [opaque pointer type] API migration for GEP constant factoriesDavid Blaikie2015-04-022-3/+6
| | | | | | | | | | | | | Require the pointee type to be passed explicitly and assert that it is correct. For now it's possible to pass nullptr here (and I've done so in a few places in this patch) but eventually that will be disallowed once all clients have been updated or removed. It'll be a long road to get all the way there... but if you have the cahnce to update your callers to pass the type explicitly without depending on a pointer's element type, that would be a good thing to do soon and a necessary thing to do eventually. llvm-svn: 233938
* Transforms: Use the new DebugLoc API, NFCDuncan P. N. Exon Smith2015-03-301-2/+2
| | | | | | Update lib/Analysis and lib/Transforms to use the new `DebugLoc` API. llvm-svn: 233587
* Reapply r233175 and r233183: float2int.James Molloy2015-03-273-0/+542
| | | | | | | | This re-adds float2int to the tree, after fixing PR23038. It turns out the argument to APSInt() is true-if-unsigned, rather than true-if-signed :(. Added testcase and explanatory comment. llvm-svn: 233370
* [NFC] Fix typo in comment.Sanjoy Das2015-03-271-1/+1
| | | | llvm-svn: 233363
* Code cleanup [NFC]Philip Reames2015-03-271-14/+12
| | | | | | The assertion here was more expensive then it needed to be. We're only inserting allocas in the entry block, so we only need to consider ones in the entry block. llvm-svn: 233362
* More code cleanup [NFC]Philip Reames2015-03-271-14/+7
| | | | llvm-svn: 233361
* More code cleanup [NFC]Philip Reames2015-03-271-12/+13
| | | | | | Minor naming, one potentially unsafe cast llvm-svn: 233359
* Code simplification and style cleanupPhilip Reames2015-03-271-97/+36
| | | | | | All the removed assertions are either implied locally by the assert at the top of the function or properties of the verifier. llvm-svn: 233358
* Revert r233175 and r233183 with it. This pulls float2int back out of the ↵Nick Lewycky2015-03-273-542/+0
| | | | | | tree, due to PR23038. llvm-svn: 233350
* [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
* [optnone] Skip pass Float2Int on optnone functions.Andrea Di Biagio2015-03-251-0/+3
| | | | | | | Added test Float2Int/float2int-optnone.ll to verify that pass Float2Int is not run on optnone functions. llvm-svn: 233183
* Reapply r233062: "float2int": Add a new pass to demote from float to int ↵James Molloy2015-03-253-0/+539
| | | | | | | | where possible. Now with a fix for PR23008 and extra regression test. llvm-svn: 233175
* Opaque Pointer Types: GEP API migrations to specify the gep type explicitlyDavid Blaikie2015-03-241-1/+1
| | | | | | | | | | | | | | The changes to InstCombine do seem a bit silly - it doesn't make anything obviously better to have the caller access the pointers element type (the thing I'm trying to remove) than the GEP itself, but it's a helpful migration step. This will allow me to more obviously lock down GEP (& Load, etc) API usage, then fix all the code that accesses pointer element types except the places that need to be removed (most of the InstCombines) anyway - at which point I'll need to just remove all that code because it won't be meaningful anymore (there will be no pointer types, so no bitcasts to combine) llvm-svn: 233126
* Revert r233062 ""float2int": Add a new pass to demote from float to int ↵Hans Wennborg2015-03-243-538/+0
| | | | | | | | | | | where possible." This caused PR23008, compiles failing with: "Use still stuck around after Def is destroyed: %.sroa.speculated" Also reverting follow-up r233064. llvm-svn: 233105
* [IRCE] Fix how IRCE checks for no-sign-overflow.Sanjoy Das2015-03-241-14/+24
| | | | | | | | | IRCE requires the induction variables it handles to not sign-overflow. The current scheme of checking if sext({X,+,S}) == {sext(X),+,sext(S)} fails when SCEV simplifies sext(X) too. After this change we //also// check no-signed-wrap by looking at the flags set on the SCEVAddRecExpr. llvm-svn: 233102
* [IRCE] Fix a regression introduced in r232444.Sanjoy Das2015-03-241-9/+20
| | | | | | | IRCE should not try to eliminate range checks that check an induction variable against a loop-varying length. llvm-svn: 233101
* [float2int] Sort includes and add missing raw_ostream include.Benjamin Kramer2015-03-241-6/+7
| | | | llvm-svn: 233064
OpenPOWER on IntegriCloud