summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
Commit message (Collapse)AuthorAgeFilesLines
...
* [BDCE] Optimize find+insert with early insertFangrui Song2019-03-071-5/+5
| | | | llvm-svn: 355583
* [ConstantHoisting] avoid hang/crash from unreachable blocks (PR40930)Sanjay Patel2019-03-041-1/+6
| | | | | | | | | | | | | | | | | I'm not too familiar with this pass, so there might be a better solution, but this appears to fix the degenerate: PR40930 PR40931 PR40932 PR40934 ...without affecting any real-world code. As we've seen in several other passes, when we have unreachable blocks, they can contain semi-bogus IR and/or cause unexpected conditions. We would not typically expect these patterns to make it this far, but we have to guard against them anyway. llvm-svn: 355337
* [LICM] Infer proper alignment from loads during scalar promotionPhilip Reames2019-03-011-3/+23
| | | | | | | | | | This patch fixes an issue where we would compute an unnecessarily small alignment during scalar promotion when no store is not to be guaranteed to execute, but we've proven load speculation safety. Since speculating a load requires proving the existing alignment is valid at the new location (see Loads.cpp), we can use the alignment fact from the load. For non-atomics, this is a performance problem. For atomics, this is a correctness issue, though an *incredibly* rare one to see in practice. For atomics, we might not be able to lower an improperly aligned load or store (i.e. i32 align 1). If such an instruction makes it all the way to codegen, we *may* fail to codegen the operation, or we may simply generate a slow call to a library function. The part that makes this super hard to see in practice is that the memory location actually *is* well aligned, and instcombine knows that. So, to see a failure, you have to have a) hit the bug in LICM, b) somehow hit a depth limit in InstCombine/ValueTracking to avoid fixing the alignment, and c) then have generated an instruction which fails codegen rather than simply emitting a slow libcall. All around, pretty hard to hit. Differential Revision: https://reviews.llvm.org/D58809 llvm-svn: 355217
* [ConstantHoisting] Call cleanup() in ConstantHoistingPass::runImpl to avoid ↵Fangrui Song2019-03-011-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | dangling elements in ConstIntInfoVec for new PM Summary: ConstIntInfoVec contains elements extracted from the previous function. In new PM, releaseMemory() is not called and the dangling elements can cause segfault in findConstantInsertionPoint. Rename releaseMemory() to cleanup() to deliver the idea that it is mandatory and call cleanup() in ConstantHoistingPass::runImpl to fix this. Reviewers: ormris, zzheng, dmgreen, wmi Reviewed By: ormris, wmi Subscribers: llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58589 llvm-svn: 355174
* [MemorySSA] Make insertDef insert corresponding phi nodes.Alina Sbirlea2019-02-271-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The original assumption for the insertDef method was that it would not materialize Defs out of no-where, hence it will not insert phis needed after inserting a Def. However, when cloning an instruction (use case used in LICM), we do materialize Defs "out of no-where". If the block receiving a Def has at least one other Def, then no processing is needed. If the block just received its first Def, we must check where Phi placement is needed. The only new usage of insertDef is in LICM, hence the trigger for the bug. But the original goal of the method also fails to apply for the move() method. If we move a Def from the entry point of a diamond to either the left or right blocks, then the merge block must add a phi. While this usecase does not currently occur, or may be viewed as an incorrect transformation, MSSA must behave corectly given the scenario. Resolves PR40749 and PR40754. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, jdoerfert, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58652 llvm-svn: 355040
* [MemorySSA & SimpleLoopUnswitch] Update MemorySSA in ReplaceUsesOfWith.Alina Sbirlea2019-02-261-5/+9
| | | | | | | SimpleLoopUnswitch must update MemorySSA when removing instructions. Resolves PR39197. llvm-svn: 354919
* [DTU] Refine the interface and logic of applyUpdatesChijun Sima2019-02-223-14/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch separates two semantics of `applyUpdates`: 1. User provides an accurate CFG diff and the dominator tree is updated according to the difference of `the number of edge insertions` and `the number of edge deletions` to infer the status of an edge before and after the update. 2. User provides a sequence of hints. Updates mentioned in this sequence might never happened and even duplicated. Logic changes: Previously, removing invalid updates is considered a side-effect of deduplication and is not guaranteed to be reliable. To handle the second semantic, `applyUpdates` does validity checking before deduplication, which can cause updates that have already been applied to be submitted again. Then, different calls to `applyUpdates` might cause unintended consequences, for example, ``` DTU(Lazy) and Edge A->B exists. 1. DTU.applyUpdates({{Delete, A, B}, {Insert, A, B}}) // User expects these 2 updates result in a no-op, but {Insert, A, B} is queued 2. Remove A->B 3. DTU.applyUpdates({{Delete, A, B}}) // DTU cancels this update with {Insert, A, B} mentioned above together (Unintended) ``` But by restricting the precondition that updates of an edge need to be strictly ordered as how CFG changes were made, we can infer the initial status of this edge to resolve this issue. Interface changes: The second semantic of `applyUpdates` is separated to `applyUpdatesPermissive`. These changes enable DTU(Lazy) to use the first semantic if needed, which is quite useful in `transforms/utils`. Reviewers: kuhar, brzycki, dmgreen, grosser Reviewed By: brzycki Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58170 llvm-svn: 354669
* [MemorySSA & LoopPassManager] Resolve PR40038.Alina Sbirlea2019-02-221-3/+2
| | | | | | | | | | | | | | The correct edge being deleted is not to the unswitched exit block, but to the original block before it was split. That's the key in the map, not the value. The insert is correct. The new edge is to the .split block. The splitting turns OriginalBB into: OriginalBB -> OriginalBB.split. Assuming the orignal CFG edge: ParentBB->OriginalBB, we must now delete ParentBB->OriginalBB, not ParentBB->OriginalBB.split. llvm-svn: 354656
* [DTU] Deprecate insertEdge*/deleteEdge*Chijun Sima2019-02-224-5/+5
| | | | | | | | | | | | | | | | Summary: This patch converts all existing `insertEdge*/deleteEdge*` to `applyUpdates` and marks `insertEdge*/deleteEdge*` as deprecated. Reviewers: kuhar, brzycki Reviewed By: kuhar, brzycki Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58443 llvm-svn: 354652
* [MemorySSA & LoopPassManager] Update MemorySSA in formDedicatedExitBlocks.Alina Sbirlea2019-02-211-5/+13
| | | | | | | MemorySSA is now updated when forming dedicated exit blocks. Resolves PR40037. llvm-svn: 354623
* [LoopSimplifyCFG] Update MemorySSA after r353911.Alina Sbirlea2019-02-211-10/+17
| | | | | | | | | | | | | | | | | Summary: MemorySSA is not properly updated in LoopSimplifyCFG after recent changes. Use SplitBlock utility to resolve that and clear all updates once handleDeadExits is finished. All updates that follow are removal of edges which are safe to handle via the removeEdge() API. Also, deleting dead blocks is done correctly as is, i.e. delete from MemorySSA before updating the CFG and DT. Reviewers: mkazantsev, rtereshin Subscribers: sanjoy, jlebar, Prazek, george.burgess.iv, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58524 llvm-svn: 354613
* [EarlyCSE] Cleanup deadcode. [NFCI]Alina Sbirlea2019-02-211-5/+1
| | | | | | | | | | | | | | Summary: Cleanup nop assignments. Reviewers: george.burgess.iv, davide Subscribers: sanjoy, jlebar, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58308 llvm-svn: 354612
* [InferAddressSpaces] Fix fallthrough errorJoey Gouly2019-02-211-0/+1
| | | | llvm-svn: 354580
* [InferAddressSpaces] Fix crash on select of non-ptr operandsJoey Gouly2019-02-211-2/+5
| | | | | | | | | Check the operands of a select are pointers, to determine if it is an address expression or not. https://reviews.llvm.org/D58226 llvm-svn: 354576
* [LoopSimplifyCFG] Add missing MSSA edge deletionMax Kazantsev2019-02-211-0/+2
| | | | | | | | When we create fictive switch in preheader, we should take care about MSSA and delete edge between old preheader and header. llvm-svn: 354547
* [NFC] API for signaling that the current loop is being deletedMax Kazantsev2019-02-191-9/+30
| | | | | | | We are planning to be able to delete the current loop in LoopSimplifyCFG in the future. Add API to notify the loop pass manager that it happened. llvm-svn: 354314
* [NFC] Store loop header in a local to keep it available after the loop is ↵Max Kazantsev2019-02-191-11/+9
| | | | | | deleted llvm-svn: 354313
* [NFC] Teach getInnermostLoopFor walk up the loop treesMax Kazantsev2019-02-171-6/+10
| | | | | | | This should be NFC in current use case of this method, but it will help to use it for solving more compex tasks in follow-up patches. llvm-svn: 354227
* [NFC] Fix name and clarifying comment for factored-out functionMax Kazantsev2019-02-171-4/+5
| | | | llvm-svn: 354220
* [NFC] Factor out a function for future reuseMax Kazantsev2019-02-171-8/+15
| | | | llvm-svn: 354218
* [EarlyCSE & MSSA] Cap the clobbering calls in EarlyCSE.Alina Sbirlea2019-02-151-2/+13
| | | | | | | | | | | | | | | | | | | Summary: Unlimitted number of calls to getClobberingAccess can lead to high compile times in pathological cases. Limitting getClobberingAccess to a fairly high number. Can be adjusted based on users/need. Note: this is the only user of MemorySSA currently enabled by default. The same handling exists in LICM (disabled atm). As MemorySSA gains more users, this logic of capping will need to move inside MemorySSA. Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D58248 llvm-svn: 354182
* [MergeICmps] Make base ordering really deterministic.Clement Courbet2019-02-151-87/+107
| | | | | | | | | | | | | | | | | | Summary: The idea is that we now manipulate bases through a `unsigned BaseID` based on order of appearance in the comparison chain rather than through the `Value*`. Fixes 40714. Reviewers: gchatelet Subscribers: mgrang, jfb, jdoerfert, llvm-commits, hans Tags: #llvm Differential Revision: https://reviews.llvm.org/D58274 llvm-svn: 354131
* [MergeICmps][NFC] Improve doc.Clement Courbet2019-02-151-5/+28
| | | | llvm-svn: 354128
* [NFCI] Factor out block removal from stack of nested loopsMax Kazantsev2019-02-151-6/+14
| | | | llvm-svn: 354124
* Fix "field 'DFS' will be initialized after field 'DTU'" warning. NFCI.Simon Pilgrim2019-02-151-1/+1
| | | | llvm-svn: 354123
* [NFC] Promote DFS to field for further useMax Kazantsev2019-02-151-2/+2
| | | | llvm-svn: 354118
* [NFC] Refactor LICM code for better readabilityMax Kazantsev2019-02-141-6/+11
| | | | llvm-svn: 354013
* [NFC] Add const qualifiers where possibleMax Kazantsev2019-02-131-28/+29
| | | | llvm-svn: 353941
* [GuardWidening] Support widening of explicitly expressed guardsMax Kazantsev2019-02-131-3/+30
| | | | | | | | | | This patch adds support of guards expressed in explicit form via `widenable_condition` in Guard Widening pass. Differential Revision: https://reviews.llvm.org/D56075 Reviewed By: reames llvm-svn: 353932
* [LoopSimplifyCFG] Re-enable const branch folding by defaultMax Kazantsev2019-02-131-1/+1
| | | | | | | | Known underlying bugs have been fixed, intensive fuzz testing did not find any new problems. Re-enabling by default. Feel free to revert if it causes any functional failures. llvm-svn: 353911
* [MemorySSA & LoopPassManager] Add remaining book keeping [NFCI].Alina Sbirlea2019-02-121-2/+5
| | | | | | | | Add plumbing to get MemorySSA in the remaining loop passes. Also update unit test to add the dependency. [EnableMSSALoopDependency remains disabled]. llvm-svn: 353901
* [LICM] Cap the clobbering calls in LICM.Alina Sbirlea2019-02-121-25/+38
| | | | | | | | | | | | | | | | | | | Summary: Unlimitted number of calls to getClobberingAccess can lead to high compile times in pathological cases. Switching EnableLicmCap flag from bool to int, and enabling to default 100. (tested to be appropriate for current bechmarks) We can revisit this value when enabling MemorySSA. Reviewers: sanjoy, chandlerc, george.burgess.iv Subscribers: jlebar, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D57968 llvm-svn: 353897
* [IndVars] Fix corner case with unreachable Phi inputs. PR40454Max Kazantsev2019-02-121-6/+20
| | | | | | | | | | | | | | | Logic in `getInsertPointForUses` doesn't account for a corner case when `Def` only comes to a Phi user from unreachable blocks. In this case, the incoming value may be arbitrary (and not even available in the input block) and break the loop-related invariants that are asserted below. In fact, if we encounter this situation, no IR modification is needed. This Phi will be simplified away with nearest cleanup. Differential Revision: https://reviews.llvm.org/D58045 Reviewed By: spatel llvm-svn: 353816
* [LoopSimplifyCFG] Change logic of dead loops removal to avoid hitting assertsMax Kazantsev2019-02-121-4/+21
| | | | | | | | | | | | | | | | | | | | The function `LI.erase` has some invariants that need to be preserved when it tries to remove a loop which is not the top-level loop. In particular, it requires loop's preheader to be strictly in loop's parent. Our current logic of deletion of dead blocks may erase the information about preheader before we handle the loop, and therefore we may hit this assertion. This patch changes the logic of loop deletion: we make them top-level loops before we actually erase them. This allows us to trigger the simple branch of `erase` logic which just detatches blocks from the loop and does not try to do some complex stuff that need this invariant. Thanks to @uabelho for reporting this! Differential Revision: https://reviews.llvm.org/D57221 Reviewed By: fedor.sergeev llvm-svn: 353813
* Delete blocks from DTU to avoid dangling pointersMax Kazantsev2019-02-121-1/+1
| | | | llvm-svn: 353804
* [LoopSimplifyCFG] Pay respect to LCSSA when removing dead blocksMax Kazantsev2019-02-121-1/+1
| | | | | | | | | | | Utility function that we use for blocks deletion always unconditionally removes one-input Phis. In LoopSimplifyCFG, it can lead to breach of LCSSA form. This patch alters this function to keep them if needed. Differential Revision: https://reviews.llvm.org/D57231 Reviewed By: fedor.sergeev llvm-svn: 353803
* [NFC] Rename DontDeleteUselessPHIs --> KeepOneInputPHIsMax Kazantsev2019-02-122-5/+5
| | | | llvm-svn: 353801
* [LoopReroll] Fix reroll root legality checking.Eli Friedman2019-02-121-0/+10
| | | | | | | | | | | The code checked that the first root was an appropriate distance from the base value, but skipped checking the other roots. This could lead to rerolling a loop that can't be legally rerolled (at least, not without rewriting the loop in a non-trivial way). Differential Revision: https://reviews.llvm.org/D56812 llvm-svn: 353779
* [LICM&MSSA] Limit store hoisting.Alina Sbirlea2019-02-112-14/+39
| | | | | | | | | | | | | | | | | | | Summary: If there is no clobbering access for a store inside the loop, that store can only be hoisted if there are no interfearing loads. A more general verification introduced here: there are no loads that are not optimized to an access outside the loop. Addresses PR40586. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D57967 llvm-svn: 353734
* Update more files added with the old header to the new one.Chandler Carruth2019-02-111-4/+3
| | | | llvm-svn: 353667
* [CallSite removal] Migrate ConstantFolding APIs and implementation toChandler Carruth2019-02-111-2/+3
| | | | | | | | | `CallBase`. Users have been updated. You can see how to update any out-of-tree usages: pass `cast<CallBase>(CS.getInstruction())`. llvm-svn: 353661
* [CallSite removal] Migrate the statepoint GC infrastructure to use theChandler Carruth2019-02-112-117/+105
| | | | | | | | | | | | | | | `CallBase` class rather than `CallSite` wrappers. I pushed this change down through most of the statepoint infrastructure, completely removing the use of CallSite where I could reasonably do so. I ended up making a couple of cut-points: generic call handling (instcombine, TLI, SDAG). As soon as it hit truly generic handling with users outside the immediate code, I simply transitioned into or out of a `CallSite` to make this a reasonable sized chunk. Differential Revision: https://reviews.llvm.org/D56122 llvm-svn: 353660
* Implementation of asm-goto support in LLVMCraig Topper2019-02-083-6/+35
| | | | | | | | | | | | | | | | | | | | | | | | | This patch accompanies the RFC posted here: http://lists.llvm.org/pipermail/llvm-dev/2018-October/127239.html This patch adds a new CallBr IR instruction to support asm-goto inline assembly like gcc as used by the linux kernel. This instruction is both a call instruction and a terminator instruction with multiple successors. Only inline assembly usage is supported today. This also adds a new INLINEASM_BR opcode to SelectionDAG and MachineIR to represent an INLINEASM block that is also considered a terminator instruction. There will likely be more bug fixes and optimizations to follow this, but we felt it had reached a point where we would like to switch to an incremental development model. Patch by Craig Topper, Alexander Ivchenko, Mikhail Dvoretckii Differential Revision: https://reviews.llvm.org/D53765 llvm-svn: 353563
* [LoopSimplifyCFG] Use DTU.applyUpdates instead of insert/deleteEdgeMax Kazantsev2019-02-081-11/+22
| | | | | | | | | | | `insert/deleteEdge` methods in DTU can make updates incorrectly in some cases (see https://bugs.llvm.org/show_bug.cgi?id=40528), and it is recommended to use `applyUpdates` methods instead when it is needed to make a mass update in CFG. Differential Revision: https://reviews.llvm.org/D57316 Reviewed By: kuhar llvm-svn: 353502
* [LSR] Generate cross iteration indexesSam Parker2019-02-071-23/+67
| | | | | | | | | | | | | | Modify GenerateConstantOffsetsImpl to create offsets that can be used by indexed addressing modes. If formulae can be generated which result in the constant offset being the same size as the recurrence, we can generate a pre-indexed access. This allows the pointer to be updated via the single pre-indexed access so that (hopefully) no add/subs are required to update it for the next iteration. For small cores, this can significantly improve performance DSP-like loops. Differential Revision: https://reviews.llvm.org/D55373 llvm-svn: 353403
* [LICM/MSSA] Add promotion to scalars by building an AliasSetTracker with ↵Alina Sbirlea2019-02-061-42/+118
| | | | | | | | | | | | | | | | | | | | | | | | MemorySSA. Summary: Experimentally we found that promotion to scalars carries less benefits than sinking and hoisting in LICM. When using MemorySSA, we build an AliasSetTracker on demand in order to reuse the current infrastructure. We only build it if less than AccessCapForMSSAPromotion exist in the loop, a cap that is by default set to 250. This value ensures there are no runtime regressions, and there are small compile time gains for pathological cases. A much lower value (20) was found to yield a single regression in the llvm-test-suite and much higher benefits for compile times. Conservatively we set the current cap to a high value, but we will explore lowering it when MemorySSA is enabled by default. Reviewers: sanjoy, chandlerc Subscribers: nemanjai, jlebar, Prazek, george.burgess.iv, jfb, jsji, llvm-commits Differential Revision: https://reviews.llvm.org/D56625 llvm-svn: 353339
* [NFC] Simplify check in guard wideningMax Kazantsev2019-02-061-9/+3
| | | | llvm-svn: 353290
* [LoopSimplifyCFG] Do not count dead exit blocks twice, make CFG simplerMax Kazantsev2019-02-061-1/+3
| | | | llvm-svn: 353276
* Move DomTreeUpdater from IR to AnalysisRichard Trieu2019-02-067-7/+7
| | | | | | | | DomTreeUpdater depends on headers from Analysis, but is in IR. This is a layering violation since Analysis depends on IR. Relocate this code from IR to Analysis to fix the layering violation. llvm-svn: 353265
* [LSR] Check SCEV on isZero() after extend. PR40514Max Kazantsev2019-02-051-3/+21
| | | | | | | | | | | | | | | | | | | | | When LSR first adds SCEVs to BaseRegs, it only does it if `isZero()` has returned false. In the end, in invocation of `InsertFormula`, it asserts that all values there are still not zero constants. However between these two points, it makes some transformations, in particular extends them to wider type. SCEV does not give us guarantee that if `S` is not a constant zero, then `sext(S)` is also not a constant zero. It might have missed some optimizing transforms when it was calculating `S` and then made them when it took `sext`. For example, it may happen if previously optimizing transforms were limited by depth or somehow else. This patch adds a bailout when we may end up with a zero SCEV after extension. Differential Revision: https://reviews.llvm.org/D57565 Reviewed By: samparker llvm-svn: 353136
OpenPOWER on IntegriCloud