aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/PHIElimination.cpp
AgeCommit message (Collapse)AuthorFilesLines
2025-08-14[PHIElimination] Preserve MachinePostDominatorTree (#153346)Carl Ritson1-10/+12
Minor changes to allow preservation of post dominator tree through PHI elimination pass. Also remove duplicate retrieval of dominator tree analysis. This is a speculative change to support reworking on passes in AMDGPU backend.
2025-07-03[PHIElimination] Revert #131837 #146320 #146337 (#146850)Guy David1-14/+0
Reverting because mis-compiles: - https://github.com/llvm/llvm-project/pull/131837 - https://github.com/llvm/llvm-project/pull/146320 - https://github.com/llvm/llvm-project/pull/146337
2025-07-01[PHIElimination] Verify reappropriated COPY is of similar register class, ↵Guy David1-1/+5
update livevars. (#146337) Follow up to the second bug that https://github.com/llvm/llvm-project/pull/131837 introduced, described in https://github.com/llvm/llvm-project/pull/131837#issuecomment-3018777795.
2025-06-30[PHIElimination] Fix bug around $noreg assignment (#146320)Guy David1-2/+3
PR which introduced the bug: https://github.com/llvm/llvm-project/pull/131837. Fixes a crash around dead registers which started in f5c62ee0fa04 by verifying that the reused incoming register is also virtual.
2025-06-29[PHIElimination] Reuse existing COPY in predecessor basic block (#131837)Guy David1-0/+9
The insertion point of COPY isn't always optimal and could eventually lead to a worse block layout, see the regression test in the first commit. This change affects many architectures but the amount of total instructions in the test cases seems too be slightly lower.
2025-05-22[LLVM][CodeGen] Add convenience accessors for MachineFunctionProperties ↵users/pcc/spr/main.elf-add-branch-to-branch-optimizationRahul Joshi1-3/+2
(#140002) Add per-property has<Prop>/set<Prop>/reset<Prop> functions to MachineFunctionProperties.
2025-03-02[CodeGen] Use MCRegister and Register. NFCCraig Topper1-4/+4
2024-12-13Reapply "[DomTreeUpdater] Move critical edge splitting code to updater" ↵paperchalice1-9/+18
(#119547) This relands commit #115111. Use traditional way to update post dominator tree, i.e. break critical edge splitting into insert, insert, delete sequence. When splitting critical edges, the post dominator tree may change its root node, and `setNewRoot` only works in normal dominator tree... See https://github.com/llvm/llvm-project/blob/6c7e5827eda26990e872eb7c3f0d7866ee3c3171/llvm/include/llvm/Support/GenericDomTree.h#L684-L687
2024-12-11Revert "[DomTreeUpdater] Move critical edge splitting code to updater" (#119512)paperchalice1-18/+9
Reverts llvm/llvm-project#115111 Causes #119511
2024-12-11[DomTreeUpdater] Move critical edge splitting code to updater (#115111)paperchalice1-9/+18
Support critical edge splitting in dominator tree updater. Continue the work in #100856. Compile time check: https://llvm-compile-time-tracker.com/compare.php?from=87c35d782795b54911b3e3a91a5b738d4d870e55&to=42b3e5623a9ab4c3648564dc0926b36f3b438a3a&stat=instructions%3Au
2024-07-17[CodeGen][NewPM] Port `phi-node-elimination` to new pass manager (#98867)paperchalice1-36/+82
- Add `PHIEliminationPass `. - Support new pass manager in `MachineBasicBlock:: SplitCriticalEdge `
2024-07-11Revert "[CodeGen] Remove `applySplitCriticalEdges` in `MachineDominatorTree` ↵Nikita Popov1-0/+5
(#97055)" This reverts commit c5e5088033fed170068d818c54af6862e449b545. Causes large compile-time regressions.
2024-07-11[CodeGen] Remove `applySplitCriticalEdges` in `MachineDominatorTree` (#97055)paperchalice1-5/+0
Summary: - Remove wrappers in `MachineDominatorTree`. - Remove `MachineDominatorTree` update code in `MachineBasicBlock::SplitCriticalEdge`. - Use `MachineDomTreeUpdater` in passes which call `MachineBasicBlock::SplitCriticalEdge` and preserve `MachineDominatorTreeWrapperPass` or CFG analyses. Commit abea99f65a97248974c02a5544eaf25fc4240056 introduced related methods in 2014. Now we have SemiNCA based dominator tree in 2017 and dominator tree updater, the solution adopted here seems a bit outdated.
2024-07-10[CodeGen][NewPM] Port `LiveIntervals` to new pass manager (#98118)paperchalice1-2/+3
- Add `LiveIntervalsAnalysis`. - Add `LiveIntervalsPrinterPass`. - Use `LiveIntervalsWrapperPass` in legacy pass manager. - Use `std::unique_ptr` instead of raw pointer for `LICalc`, so destructor and default move constructor can handle it correctly. This would be the last analysis required by `PHIElimination`.
2024-07-10[CodeGen] Format `PHIElimination.cpp` NFC (#98289)paperchalice1-84/+84
clang-format will format entire class when `class PHIElimination : public MachineFunctionPass {` is changed. Format it firstly to reduce unnecessary changes when porting it to new pass manager.
2024-07-09[CodeGen][NewPM] Port `SlotIndexes` to new pass manager (#97941)paperchalice1-1/+1
- Add `SlotIndexesAnalysis`. - Add `SlotIndexesPrinterPass`. - Use `SlotIndexesWrapperPass` in legacy pass.
2024-07-09[CodeGen][NewPM] Port `LiveVariables` to new pass manager (#97880)paperchalice1-4/+5
- Port `LiveVariables` to new pass manager. - Convert to `LiveVariablesWrapperPass` in legacy pass manager.
2024-07-09[CodeGen][NewPM] Port `machine-loops` to new pass manager (#97793)paperchalice1-2/+4
- Add `MachineLoopAnalysis`. - Add `MachineLoopPrinterPass`. - Convert to `MachineLoopInfoWrapperPass` in legacy pass manager.
2024-07-03[CodeGen] Only deduplicate PHIs on critical edges (#97064)Alexis Engelke1-15/+42
PHIElim deduplicates identical PHI nodes to reduce the number of copies inserted. There are two cases: 1. Identical PHI nodes are in different blocks. That's the reason for this optimization; this can't be avoided at SSA-level. A necessary prerequisite for this is that the predecessors of all basic blocks (where such a PHI node could occur) are the same. This implies that all (>= 2) predecessors must have multiple successors, i.e. all edges into the block are critical edges. 2. Identical PHI nodes are in the same block. CSE can remove these. There are a few cases, however, where they still occur regardless: - expand-large-div-rem creates PHI nodes with large integers, which get lowered into one PHI per MVT. Later, some identical values (zeroes) get folded, resulting in identical PHI nodes. - peephole-opt occasionally inserts PHIs for the same value. - Some pseudo instruction emitters create redundant PHI nodes (e.g., AVR's insertShift), merging the same values more than once. In any case, this happens rarely and MachineCSE handles most cases anyway, so that PHIElim only gets to see very few of such cases (see changed test files). Currently, all PHI nodes are inserted into a DenseMap that checks equality not by pointer but by operands. This hash map is pretty expensive (hashing itself and the hash map), but only really useful in the first case. Avoid this expensive hashing most of the time by restricting it to basic blocks with only critical input edges. This improves performance for code with many PHI nodes, especially at -O0. (Note that Clang often doesn't generate PHI nodes and -O0 includes no mem2reg. Other compilers always generate PHI nodes.)
2024-06-11[CodeGen][NewPM] Split `MachineDominatorTree` into a concrete analysis ↵paperchalice1-3/+3
result (#94571) Prepare for new pass manager version of `MachineDominatorTreeAnalysis`. We may need a machine dominator tree version of `DomTreeUpdater` to handle `SplitCriticalEdge` in some CodeGen passes.
2024-04-24[CodeGen] Make the parameter TRI required in some functions. (#85968)Xu Zhang1-6/+7
Fixes #82659 There are some functions, such as `findRegisterDefOperandIdx` and `findRegisterDefOperand`, that have too many default parameters. As a result, we have encountered some issues due to the lack of TRI parameters, as shown in issue #82411. Following @RKSimon 's suggestion, this patch refactors 9 functions, including `{reads, kills, defines, modifies}Register`, `registerDefIsDead`, and `findRegister{UseOperandIdx, UseOperand, DefOperandIdx, DefOperand}`, adjusting the order of the TRI parameter and making it required. In addition, all the places that call these functions have also been updated correctly to ensure no additional impact. After this, the caller of these functions should explicitly know whether to pass the `TargetRegisterInfo` or just a `nullptr`.
2023-11-13[PHIElimination] Handle subranges in LiveInterval updates (#69429)Carl Ritson1-18/+45
Add subrange tracking and handling for LiveIntervals during PHI elimination. This requires extending MachineBasicBlock::SplitCriticalEdge to also update subrange intervals.
2023-10-16[CodeGen] Remove LiveVariables::{isPHIJoin,setPHIJoin} (#69128)Kazu Hirata1-3/+0
The last use of isPHIJoin was removed by: commit fac770b865f59cbe615241dad153ad20d5138b9e Author: Jakob Stoklund Olesen <stoklund@2pi.dk> Date: Sat Feb 9 00:04:07 2013 +0000 so there is no reason to maintain PHIJoins.
2023-09-11Revert "[PHIElimination] Handle subranges in LiveInterval updates"Vitaly Buka1-48/+18
Leaks memory. This reverts commit 3bff611068ae70e3273a46bbc72bc66b66f98c1c.
2023-09-11[PHIElimination] Handle subranges in LiveInterval updatesCarl Ritson1-18/+48
Add handling for subrange updates in LiveInterval preservation. This requires extending MachineBasicBlock::SplitCriticalEdge to also update subrange intervals. Reviewed By: arsenm Differential Revision: https://reviews.llvm.org/D158144
2023-04-17Fix uninitialized pointer members in CodeGenAkshay Khadse1-3/+3
This change initializes the members TSI, LI, DT, PSI, and ORE pointer feilds of the SelectOptimize class to nullptr. Reviewed By: LuoYuanke Differential Revision: https://reviews.llvm.org/D148303
2023-01-13[CodeGen] Remove uses of Register::isPhysicalRegister/isVirtualRegister. NFCCraig Topper1-1/+1
Use isPhysical/isVirtual methods. Reviewed By: foad Differential Revision: https://reviews.llvm.org/D141715
2022-12-07[NFC] Use Register instead of unsigned for variables that receive a Register ↵Gregory Alfonso1-1/+1
object Reviewed By: MaskRay Differential Revision: https://reviews.llvm.org/D139451
2022-03-16Cleanup codegen includesserge-sans-paille1-2/+0
This is a (fixed) recommit of https://reviews.llvm.org/D121169 after: 1061034926 before: 1063332844 Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup Differential Revision: https://reviews.llvm.org/D121681
2022-03-10Revert "Cleanup codegen includes"Nico Weber1-0/+2
This reverts commit 7f230feeeac8a67b335f52bd2e900a05c6098f20. Breaks CodeGenCUDA/link-device-bitcode.cu in check-clang, and many LLVM tests, see comments on https://reviews.llvm.org/D121169
2022-03-10Cleanup codegen includesserge-sans-paille1-2/+0
after: 1061034926 before: 1063332844 Differential Revision: https://reviews.llvm.org/D121169
2021-12-08[NFC] Rename MachineFunction::deleteMachineInstr (coding style)Mircea Trofin1-2/+2
2021-10-11[PHIElimination] Fix accounting for undef uses when updating LiveVariablesJay Foad1-7/+17
PHI elimination updates LiveVariables info as described here: // We only need to update the LiveVariables kill of SrcReg if this was the // last PHI use of SrcReg to be lowered on this CFG edge and it is not live // out of the predecessor. We can also ignore undef sources. Unfortunately if the last use also happened to be an undef use then it would fail to update the LiveVariables at all. Fix this by not counting undef uses in the VRegPHIUse map. Thanks to Mikael Holmén for the test case! Differential Revision: https://reviews.llvm.org/D111552
2021-10-07[PHIElimination] Account for INLINEASM_BR when inserting killsJay Foad1-8/+6
When PHIElimination adds kills after lowering PHIs to COPYs it knows that some instructions after the inserted COPY might use the same SrcReg, but it was only looking at the terminator instructions at the end of the block, not at other instructions like INLINEASM_BR that can appear after the COPY insertion point. Since we have already called findPHICopyInsertPoint, which knows about INLINEASM_BR, we might as well reuse the insertion point that it calculated when looking for instructions that might use SrcReg. This fixes a machine verification failure if you force machine verification to run after PHIElimination (currently it is disabled for other reasons) when running test/CodeGen/X86/callbr-asm-phi-placement.ll. Differential Revision: https://reviews.llvm.org/D110834
2021-10-05[PHIElimination] Update LiveVariables after handling an unspillable terminatorJay Foad1-0/+9
Update the LiveVariables analysis after the special handling for unspillable terminators which was added in D91358. This is just enough to fix some "Block should not be in AliveBlocks" / "Block missing from AliveBlocks" errors in the codegen test suite when machine verification is forced to run after PHIElimination (currently it is disabled). Differential Revision: https://reviews.llvm.org/D110939
2021-05-26[DebugInstrRef][1/3] Track PHI values through register allocationJeremy Morse1-0/+10
This patch introduces "DBG_PHI" instructions, a marker of where a PHI instruction used to be, before PHI elimination. Under the instruction referencing model, we want to know where every value in the function is defined -- and a PHI, even if implicit, is such a place. Just like instruction numbers, we can use this to identify a value to be used as a variable value, but we don't need to know what instruction defines that value, for example: bb1: DBG_PHI $rax, 1 [... more insts ... ] bb2: DBG_INSTR_REF 1, 0, !1234, !DIExpression() This specifies that on entry to bb1, whatever value is in $rax is known as value number one -- and the later DBG_INSTR_REF marks the position where variable !1234 should take on value number one. PHI locations are stored in MachineFunction for the duration of the regalloc phase in the DebugPHIPositions map. The map is populated by PHIElimination, and then flushed back into the instruction stream by virtregrewriter. A small amount of maintenence is needed in LiveDebugVariables to account for registers being split, but only for individual positions, not for entire ranges of blocks. Differential Revision: https://reviews.llvm.org/D86812
2021-04-20Make sure PHIElimination doesn't copy debug locations across basic blocks.Adrian Prantl1-3/+4
PHIElimination may insert copy instructions in multiple basic blocks. Moving debug locations across basic block boundaries would be misleading as illustrated by the test case. rdar://75463656 Differential Revision: https://reviews.llvm.org/D100886
2021-02-19[CodeGen] Use range-based for loops (NFC)Kazu Hirata1-3/+2
2021-01-16[llvm] Use *::empty (NFC)Kazu Hirata1-2/+1
2020-12-10[ARM][RegAlloc] Add t2LoopEndDecDavid Green1-0/+13
We currently have problems with the way that low overhead loops are specified, with LR being spilled between the t2LoopDec and the t2LoopEnd forcing the entire loop to be reverted late in the backend. As they will eventually become a single instruction, this patch introduces a t2LoopEndDec which is the combination of the two, combined before registry allocation to make sure this does not fail. Unfortunately this instruction is a terminator that produces a value (and also branches - it only produces the value around the branching edge). So this needs some adjustment to phi elimination and the register allocator to make sure that we do not spill this LR def around the loop (needing to put a spill after the terminator). We treat the loop very carefully, making sure that there is nothing else like calls that would break it's ability to use LR. For that, this adds a isUnspillableTerminator to opt in the new behaviour. There is a chance that this could cause problems, and so I have added an escape option incase. But I have not seen any problems in the testing that I've tried, and not reverting Low overhead loops is important for our performance. If this does work then we can hopefully do the same for t2WhileLoopStart and t2DoLoopStart instructions. This patch also contains the code needed to convert or revert the t2LoopEndDec in the backend (which just needs a subs; bne) and the code pre-ra to create them. Differential Revision: https://reviews.llvm.org/D91358
2020-11-02[NFC] Use [MC]Register in Live-ness trackingGaurav Jain1-5/+5
Differential Revision: https://reviews.llvm.org/D90611
2020-07-30[PHIElimination] Fix the killed flag for LowerPHINode()Kang Zhang1-13/+35
Summary: In the phi-node-elimination pass, we set the killed flag incorrectly. When we eliminate the PHI node, we replace the PHI with a copy for the incoming value. Before this patch, we will set incoming value as killed(PHICopy). And we will remove the killed flag from last using incoming value(OldKill). This is correct, only if the new PHICopy is after the OldKill. Reviewed By: bjope Differential Revision: https://reviews.llvm.org/D80886
2020-02-05[PHIElimination] Compile time optimization for huge functions.Jonas Paulsson1-7/+38
This is a compile-time optimization for PHIElimination (splitting of critical edges), which was reported at https://bugs.llvm.org/show_bug.cgi?id=44249. As discussed there, the way to remedy the slowdowns with huge functions is to pre-compute the live-in registers for each MBB in an efficient way in PHIElimination.cpp and then pass that information along to LiveVariabless::addNewBlock(). In all the huge test programs where this slowdown has been noticable, it has dissapeared entirely with this patch. Review: Björn Pettersson, Quentin Colombet. Differential Revision: https://reviews.llvm.org/D73152
2020-01-16Revert "[PHIEliminate] Move dbg values after phi and label"Jeremy Morse1-5/+0
Testing compiler-rt, a new assertion failure occurs when building the GwpAsanTestObjects object. I'm uploading a reproducer to D70597. This reverts commit 75188b01e9af3a89639d84be912f84610d6885ba.
2020-01-16[PHIEliminate] Move dbg values after phi and labelChris Ye1-0/+5
If there are DBG_VALUEs between phi and label (after phi and before label), DBG_VALUE will block PHI lowering after the LABEL. Moving all DBG_VALUEs after Labels in the function ScheduleDAGSDNodes::EmitSchedule to avoid impacting PHI lowering. before: PHI DBG_VALUE LABEL after: (move DBG_VALUE after label) PHI LABEL DBG_VALUE then: (phi lowering after label) LABEL COPY DBG_VALUE Fixes the issue: https://bugs.llvm.org/show_bug.cgi?id=43859 Differential Revision: https://reviews.llvm.org/D70597
2019-10-01[Dominators][CodeGen] Fix MachineDominatorTree preservation in PHIEliminationJakub Kuderski1-0/+5
Summary: PHIElimination modifies CFG and marks MachineDominatorTree as preserved. Therefore, it the CFG changes it should also update the MDT, when available. This patch teaches PHIElimination to recalculate MDT when necessary. This fixes the `tailmerging_in_mbp.ll` test failure discovered after switching to generic DomTree verification algorithm in MachineDominators in D67976. Reviewers: arsenm, hliao, alex-t, rampitec, vpykhtin, grosser Reviewed By: rampitec Subscribers: MatzeB, wdng, hiraditya, javed.absar, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D68154 llvm-svn: 373377
2019-09-17[AMDGPU]: PHI Elimination hooks added for custom COPY insertion. FixedAlexander Timofeev1-14/+14
Defferential Revision: https://reviews.llvm.org/D67101 Reviewers: rampitec, vpykhtin llvm-svn: 372086
2019-09-13Revert for: [AMDGPU]: PHI Elimination hooks added for custom COPY insertion.Alexander Timofeev1-14/+14
llvm-svn: 371873
2019-09-10[AMDGPU]: PHI Elimination hooks added for custom COPY insertion.Alexander Timofeev1-14/+14
Reviewers: rampitec, vpykhtin Differential Revision: https://reviews.llvm.org/D67101 llvm-svn: 371508
2019-08-15Apply llvm-prefer-register-over-unsigned from clang-tidy to LLVMDaniel Sanders1-4/+4
Summary: This clang-tidy check is looking for unsigned integer variables whose initializer starts with an implicit cast from llvm::Register and changes the type of the variable to llvm::Register (dropping the llvm:: where possible). Partial reverts in: X86FrameLowering.cpp - Some functions return unsigned and arguably should be MCRegister X86FixupLEAs.cpp - Some functions return unsigned and arguably should be MCRegister X86FrameLowering.cpp - Some functions return unsigned and arguably should be MCRegister HexagonBitSimplify.cpp - Function takes BitTracker::RegisterRef which appears to be unsigned& MachineVerifier.cpp - Ambiguous operator==() given MCRegister and const Register PPCFastISel.cpp - No Register::operator-=() PeepholeOptimizer.cpp - TargetInstrInfo::optimizeLoadInstr() takes an unsigned& MachineTraceMetrics.cpp - MachineTraceMetrics lacks a suitable constructor Manual fixups in: ARMFastISel.cpp - ARMEmitLoad() now takes a Register& instead of unsigned& HexagonSplitDouble.cpp - Ternary operator was ambiguous between unsigned/Register HexagonConstExtenders.cpp - Has a local class named Register, used llvm::Register instead of Register. PPCFastISel.cpp - PPCEmitLoad() now takes a Register& instead of unsigned& Depends on D65919 Reviewers: arsenm, bogner, craig.topper, RKSimon Reviewed By: arsenm Subscribers: RKSimon, craig.topper, lenary, aemerson, wuzish, jholewinski, MatzeB, qcolombet, dschuff, jyknight, dylanmckay, sdardis, nemanjai, jvesely, wdng, nhaehnle, sbc100, jgravelle-google, kristof.beyls, hiraditya, aheejin, kbarton, fedor.sergeev, javed.absar, asb, rbar, johnrusso, simoncook, apazos, sabuasal, niosHD, jrtc27, MaskRay, zzheng, edward-jones, atanasyan, rogfer01, MartinMosbeck, brucehoult, the_o, tpr, PkmX, jocewei, jsji, Petar.Avramovic, asbirlea, Jim, s.egerton, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65962 llvm-svn: 369041
generated by cgit v1.1 at 2025-10-09 04:58:35 +0000