aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/ReachingDefAnalysis.cpp
AgeCommit message (Collapse)AuthorFilesLines
2022-02-26Use RegisterInfo::regsOverlaps instead of checking aliasesBenjamin Kramer1-12/+2
This is both less code and faster since it doesn't have to expand all the sub & superreg sets. NFCI.
2021-09-19[llvm] Use pop_back_val (NFC)Kazu Hirata1-2/+1
2021-08-04[RDA] Attempt to make RDA subreg awareDavid Green1-14/+30
This attempts to make more of RDA aware of potentially overlapping subregisters. Some of this was already in place, with it iterating through MCRegUnitIterators. This also replaces calls to LiveRegs.contains(..) with !LiveRegs.available(..), and updates the isValidRegUseOf and isValidRegDefOf to search subregs. Differential Revision: https://reviews.llvm.org/D107351
2021-05-18[RDA] Fix printing of regs / reg units. NFCDavid Green1-1/+1
It was printing RegUnits as Regs, leading to much confusion in the debug logs.
2021-02-28[llvm] Use set_is_subset (NFC)Kazu Hirata1-7/+4
2020-12-31[CodeGen] Construct SmallVector with iterator ranges (NFC)Kazu Hirata1-3/+1
2020-12-28[CodeGen] Use llvm::append_range (NFC)Kazu Hirata1-2/+1
2020-10-22[NFC][MC] Use MCRegister for ReachingDefAnalysis APIsMircea Trofin1-37/+43
Also updated the users of the APIs; and a drive-by small change to RDFRegister.cpp Differential Revision: https://reviews.llvm.org/D89912
2020-10-10[ARM] Attempt to make Tail predication / RDA more resilient to empty blocksDavid Green1-9/+15
There are a number of places in RDA where we assume the block will not be empty. This isn't necessarily true for tail predicated loops where we have removed instructions. This attempt to make the pass more resilient to empty blocks, not casting pointers to machine instructions where they would be invalid. The test contains a case that was previously failing, but recently been hidden on trunk. It contains an empty block to begin with to show a similar error. Differential Revision: https://reviews.llvm.org/D88926
2020-09-30[RDA] isSafeToDefRegAt: Look at global usesSam Parker1-1/+1
We weren't looking at global uses of a value, so we could happily overwrite the register incorrectly. Differential Revision: https://reviews.llvm.org/D88554
2020-09-30[ARM][LowOverheadLoops] TryRemove helper.Sam Parker1-0/+3
Make a helper function that wraps around RDA::isSafeToRemove and utilises the existing DCE IT block checks.
2020-09-30[RDA] Switch isSafeToMove iteratorsSam Parker1-3/+13
So forwards is forwards and backwards is reverse. Also add a check so that we know the instructions are in the expected order. Differential Revision: https://reviews.llvm.org/D88419
2020-09-25[ARM] Find VPT implicitly predicated by VCTPSam Parker1-1/+0
On failing to find a VCTP in the list of instructions that explicitly predicate the entry of a VPT block, inspect whether the block is controlled via VPT which is implicitly predicated due to it's predicated operand(s). Differential Revision: https://reviews.llvm.org/D87819
2020-09-16[RDA] Fix getUniqueReachingDef for self loopsSam Parker1-10/+6
We've fixed the case where this could return an instruction after the given instruction, but also means that we can falsely return a 'unique' def when they could be one coming from the backedge of a loop. Differential Revision: https://reviews.llvm.org/D87751
2020-08-28[ARM][LowOverheadLoops] Liveouts and reductionsSam Parker1-0/+13
Remove the code that tried to look for reduction patterns, since the vectorizer and isel can now produce predicated arithmetic instructios within the loop body. This has required some reorganisation and fixes around live-out and predication checks, as well as looking for cases where an input/output is initialised to zero. Differential Revision: https://reviews.llvm.org/D86613
2020-08-26[RDA] Don't visit the BB of the instruction in getReachingUniqueMIDefSam Tebbs1-1/+3
If the basic block of the instruction passed to getUniqueReachingMIDef is a transitive predecessor of itself and has a definition of the register, the function will return that definition even if it is after the instruction given to the function. This patch stops the function from scanning the instruction's basic block to prevent this. Differential Revision: https://reviews.llvm.org/D86607
2020-08-25[NFC][RDA] Add explicit def checkSam Parker1-2/+4
Explicitly check that there is a local def prior to the given instruction in getReachingLocalMIDef instead of just relying on a nullptr return from getInstFromId.
2020-08-11[RDA] Fix DBG_VALUE issuesSam Parker1-18/+18
We skip debug instructions in RDA so we cannot attempt to look them up in our instruction map without causing a crash. But some of the methods select the last instruction in the block and this instruction may be a debug instruction... So, use getLastNonDebugInstr instead of calling back on a MachineBasicBlock. MachineBasicBlock iterators have also been updated to use instructionsWithoutDebug so we can avoid the manual checks for debug instructions. Differential Revision: https://reviews.llvm.org/D85658
2020-07-01[ARM][LowOverheadLoops] Handle reductionsSam Parker1-0/+6
While validating live-out values, record instructions that look like a reduction. This will comprise of a vector op (for now only vadd), a vorr (vmov) which store the previous value of vadd and then a vpsel in the exit block which is predicated upon a vctp. This vctp will combine the last two iterations using the vmov and vadd into a vector which can then be consumed by a vaddv. Once we have determined that it's safe to perform tail-predication, we need to change this sequence of instructions so that the predication doesn't produce incorrect code. This involves changing the register allocation of the vadd so it updates itself and the predication on the final iteration will not update the falsely predicated lanes. This mimics what the vmov, vctp and vpsel do and so we then don't need any of those instructions. Differential Revision: https://reviews.llvm.org/D75533
2020-04-28[NFC] Correct spelling of "ambiguous"Casey Carter1-1/+1
2020-04-07[RDA] Avoid full reprocessing of blocks in loops (NFCI)Nikita Popov1-3/+62
RDA sometimes needs to visit blocks twice, to take into account reaching defs coming in along loop back edges. Currently it handles repeated visitation the same way as usual, which means that it will scan through all instructions and their reg unit defs again. Not only is this very inefficient, it also means that all reaching defs in loops are going to be inserted twice. We can do much better than this. The only thing we need to handle is a new reaching def from a predecessor, which either needs to be prepended to the reaching definitions (if there was no reaching def from a predecessor), or needs to replace an existing predecessor reaching def, if it is more recent. Since D77508 we only store the most recent predecessor reaching def, so that's the only one that may need updating. This also has the nice side-effect that reaching definitions are now automatically sorted and unique, so drop the llvm::sort() call in favor of an assertion. Differential Revision: https://reviews.llvm.org/D77511
2020-04-07[RDA] Don't pass down TraversedMBB (NFC)Nikita Popov1-14/+11
Only pass the MachineBasicBlock itself down to helper methods, they don't need to know about traversal. Move the debug print into the main method.
2020-04-07[RDA] Avoid inserting duplicate reaching defs (NFCI)Nikita Popov1-5/+9
An instruction may define the same reg unit multiple times, avoid inserting the same reaching def multiple times in that case. Also print the reg unit, rather than the super-register, in the debug code.
2020-04-06[RDA] Only store most recent reaching def from predecessors (NFCI)Nikita Popov1-5/+7
When entering a basic block, RDA inserts reaching definitions coming from predecessor blocks (which will be negative numbers) in a rather peculiar way. If you have incoming reaching definitions -4, -3, -2, -1, it will insert those. If you have incoming reaching definitions -1, -2, -3, -4, it will insert -1, -1, -1, -1, as the max is taken at each step. That's probably not what was intended... However, RDA only actually cares about the most recent reaching definition from a predecessor (to calculate clearance), so this ends up working fine as far as behavior is concerned. It does waste memory on unnecessary reaching definitions though. This patch changes the implementation to first compute the most recent reaching definition in one loop, and then insert only that one in a separate loop. Differential Revision: https://reviews.llvm.org/D77508
2020-04-06[RDA] Don't adjust ReachingDefDefaultVal (NFCI)Nikita Popov1-1/+2
At the end of a basic block, RDA adjusts all the reaching defs it found to be relative to the end of the basic block, rather than the start of it. However, it also does this to registers which don't have a reaching def, indicated by ReachingDefDefaultVal. This means that code checking against ReachingDefDefaultVal will not skip them, and may insert them into the reaching definition list. This is ultimately harmless, but causes unnecessary work and is logically not right. Differential Revision: https://reviews.llvm.org/D77506
2020-03-10Give helpers internal linkage. NFC.Benjamin Kramer1-5/+5
2020-03-03[RDA][ARM] collectKilledOperands across multiple blocksSam Parker1-10/+6
Use MIOperand in collectLocalKilledOperands to make the search global, as we already have to search for global uses too. This allows us to delete more dead code when tail predicating. Differential Revision: https://reviews.llvm.org/D75167
2020-03-03[ARM][RDA] Allow multiple killed usersSam Parker1-2/+5
In RDA, check against the already decided dead instructions when looking at users. This allows an instruction to be removed if it has multiple users, but they're all dead. This means that IT instructions can be considered killed once all the itstate using instructions are dead. Differential Revision: https://reviews.llvm.org/D75245
2020-02-28[RDA] Track implicit-defsSam Parker1-18/+40
Ensure that we're recording implicit defs, as well as visiting implicit uses and implicit defs when we're walking through operands. Differential Revision: https://reviews.llvm.org/D75185
2020-02-26[ARM][RDA] add getUniqueReachingMIDefSam Parker1-5/+58
Add getUniqueReachingMIDef to RDA which performs a global search for a machine instruction that produces a unique definition of a given register at a given point. Also add two helper functions (getMIOperand) that wrap around this functionality to get the incoming definition uses of a given instruction. These now replace the uses of getReachingMIDef in ARMLowOverheadLoops. getReachingMIDef has been renamed to getReachingLocalMIDef and has been made private along with getInstFromId. Differential Revision: https://reviews.llvm.org/D74605
2020-02-24[RDA][ARM][LowOverheadLoops] Iteration count IT blocksSam Parker1-0/+26
Change the way that we remove the redundant iteration count code in the presence of IT blocks. collectLocalKilledOperands has been introduced to scan an instructions operands, collecting the killed instructions and then visiting them too. This is used to delete the code in the preheader which calculates the iteration count. We also track any IT blocks within the preheader and, if we remove all the instructions from the IT block, we also remove the IT instruction. isSafeToRemove is used to remove any redundant uses of the iteration count within the loop body. Differential Revision: https://reviews.llvm.org/D74975
2020-02-20[NFC][RDA] Break-up initialization codeSam Parker1-19/+25
Separate out the initialization code from the loop traversal so that the analysis can be reset and re-run by a user.
2020-02-06[RDA] getInstFromId: find instructions. NFC.Sjoerd Meijer1-1/+3
To find the instruction in the block for a given ID, first a count and then a lookup was performed in the map, which is almost the same thing, thus doing double the work. Differential Revision: https://reviews.llvm.org/D73866
2020-02-06[ReachingDefs] Make isSafeToMove more strict.Sam Parker1-4/+12
Test that we're not moving the instruction through instructions with side-effects. Differential Revision: https://reviews.llvm.org/D74058
2020-01-29[RDA][ARM] Move functionality into RDASam Parker1-0/+138
Add several new helpers to RDA: - hasLocalDefBefore - isRegDefinedAfter - isSafeToDefRegAt And move two bits of logic from ARMLowOverheadLoops into RDA: - isSafeToMove - isSafeToRemove Both of these have some wrappers too to make them more convienent to use. Differential Revision: https://reviews.llvm.org/D73460
2020-01-28[NFC][RDA] typedef SmallPtrSetImpl<MachineInstr*>Sam Parker1-3/+3
2020-01-23[RDA] Skip debug valuesSam Parker1-0/+5
Skip debug instructions when iterating through a block to find uses. Differential Revision: https://reviews.llvm.org/D73273
2020-01-23[NFC][RDA] Make the interface constSam Parker1-17/+22
Make all the public query methods const.
2020-01-17[ARM][MVE] Tail Predicate IsSafeToRemoveSam Parker1-31/+43
Introduce a method to walk through use-def chains to decide whether it's possible to remove a given instruction and its users. These instructions are then stored in a set until the end of the transform when they're erased. This is now used to perform checks on the iteration count (LoopDec chain), element count (VCTP chain) and the possibly redundant iteration count. As well as being able to remove chains of instructions, we know also check that the sub feeding the vctp is producing the expected value. Differential Revision: https://reviews.llvm.org/D71837
2020-01-07[ARM][MVE] VPT Blocks: findVCMPToFoldIntoVPSSjoerd Meijer1-2/+0
This is a recommit of D71330, but with a few things fixed and changed: 1) ReachingDefAnalysis: this was not running with optnone as it was checking skipFunction(), which other analysis passes don't do. I guess this is a copy-paste from a codegen pass. 2) VPTBlockPass: here I've added skipFunction(), because like most/all optimisations, we don't want to run this with optnone. This fixes the issues with the initial/previous commit: the VPTBlockPass was running with optnone, but ReachingDefAnalysis wasn't, and so VPTBlockPass was crashing querying ReachingDefAnalysis. I've added test case mve-vpt-block-optnone.mir to check that we don't run VPTBlock with optnone. Differential Revision: https://reviews.llvm.org/D71470
2019-12-20[ARM][MVE] Fixes for tail predication.Sam Parker1-5/+41
1) Fix an issue with the incorrect value being used for the number of elements being passed to [d|w]lstp. We were trying to check that the value was available at LoopStart, but this doesn't consider that the last instruction in the block could also define the register. Two helpers have been added to RDA for this. 2) Insert some code to now try to move the element count def or the insertion point so that we can perform more tail predication. 3) Related to (1), the same off-by-one could prevent us from generating a low-overhead loop when a mov lr could have been the last instruction in the block. 4) Fix up some instruction attributes so that not all the low-overhead loop instructions are labelled as branches and terminators - as this is not true for dls/dlstp. Differential Revision: https://reviews.llvm.org/D71609
2019-12-11[ARM][LowOverheadLoops] Remove dead loop update instructions.Sjoerd Meijer1-1/+25
After creating a low-overhead loop, the loop update instruction was still lingering around hurting performance. This removes dead loop update instructions, which in our case are mostly SUBS instructions. To support this, some helper functions were added to MachineLoopUtils and ReachingDefAnalysis to analyse live-ins of loop exit blocks and find uses before a particular loop instruction, respectively. This is a first version that removes a SUBS instruction when there are no other uses inside and outside the loop block, but there are some more interesting cases in test/CodeGen/Thumb2/LowOverheadLoops/mve-tail-data-types.ll which shows that there is room for improvement. For example, we can't handle this case yet: .. dlstp.32 lr, r2 .LBB0_1: mov r3, r2 subs r2, #4 vldrh.u32 q2, [r1], #8 vmov q1, q0 vmla.u32 q0, q2, r0 letp lr, .LBB0_1 @ %bb.2: vctp.32 r3 .. which is a lot more tricky because r2 is not only used by the subs, but also by the mov to r3, which is used outside the low-overhead loop by the vctp instruction, and that requires a bit of a different approach, and I will follow up on this. Differential Revision: https://reviews.llvm.org/D71007
2019-11-26[ARM][ReachingDefs] Remove dead code in loloops.Sam Parker1-8/+35
Add some more helper functions to ReachingDefs to query the uses of a given MachineInstr and also to query whether two MachineInstrs use the same def of a register. For Arm, while tail-predicating, these helpers are used in the low-overhead loops to remove the dead code that calculates the number of loop iterations. Differential Revision: https://reviews.llvm.org/D70240
2019-11-26[ARM][ReachingDefs] RDA in LoLoopsSam Parker1-0/+52
Add several new methods to ReachingDefAnalysis: - getReachingMIDef, instead of returning an integer, return the MachineInstr that produces the def. - getInstFromId, return a MachineInstr for which the given integer corresponds to. - hasSameReachingDef, return whether two MachineInstr use the same def of a register. - isRegUsedAfter, return whether a register is used after a given MachineInstr. These methods have been used in ARMLowOverhead to replace searching for uses/defs. Differential Revision: https://reviews.llvm.org/D70009
2019-10-19Prune two MachineInstr.h includes, fix up depsReid Kleckner1-0/+1
MachineInstr.h included AliasAnalysis.h, which includes a world of IR constructs mostly unneeded in CodeGen. Prune it. Same for DebugInfoMetadata.h. Noticed with -ftime-trace. llvm-svn: 375311
2019-01-19Update the file headers across all of the LLVM projects in the monorepoChandler Carruth1-4/+3
to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
2018-09-27llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)Fangrui Song1-1/+1
Summary: The convenience wrapper in STLExtras is available since rL342102. Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb Subscribers: MatzeB, sanjoy, arsenm, dschuff, mehdi_amini, sdardis, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, eraman, aheejin, kbarton, JDevlieghere, javed.absar, gbedwell, jrtc27, mgrang, atanasyan, steven_wu, george.burgess.iv, dexonsmith, kristina, jsji, llvm-commits Differential Revision: https://reviews.llvm.org/D52573 llvm-svn: 343163
2018-05-14Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen1-7/+7
The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
2018-05-09[DebugInfo] Examine all uses of isDebugValue() for debug instructions.Shiva Chen1-2/+2
Because we create a new kind of debug instruction, DBG_LABEL, we need to check all passes which use isDebugValue() to check MachineInstr is debug instruction or not. When expelling debug instructions, we should expel both DBG_VALUE and DBG_LABEL. So, I create a new function, isDebugInstr(), in MachineInstr to check whether the MachineInstr is debug instruction or not. This patch has no new test case. I have run regression test and there is no difference in regression test. Differential Revision: https://reviews.llvm.org/D45342 Patch by Hsiangkai Wang. llvm-svn: 331844
2018-04-06[CodeGen] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang1-1/+1
Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer the comments section in D44363 for a list of all the required patches. Reviewers: bogner, rnk, MatzeB, RKSimon Reviewed By: rnk Subscribers: JDevlieghere, javed.absar, llvm-commits Differential Revision: https://reviews.llvm.org/D45133 llvm-svn: 329435
generated by cgit v1.1 at 2025-10-03 11:00:02 +0000