aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/MachineBlockPlacement.cpp
AgeCommit message (Collapse)AuthorFilesLines
2019-08-12Revert r368339 "[MBP] Disable aggressive loop rotate in plain mode"Hans Wennborg1-80/+36
It caused assertions to fire when building Chromium: lib/CodeGen/LiveDebugValues.cpp:331: bool {anonymous}::LiveDebugValues::OpenRangesSet::empty() const: Assertion `Vars.empty() == VarLocs.empty() && "open ranges are inconsistent"' failed. See https://crbug.com/992871#c3 for how to reproduce. > Patch https://reviews.llvm.org/D43256 introduced more aggressive loop layout optimization which depends on profile information. If profile information is not available, the statically estimated profile information(generated by BranchProbabilityInfo.cpp) is used. If user program doesn't behave as BranchProbabilityInfo.cpp expected, the layout may be worse. > > To be conservative this patch restores the original layout algorithm in plain mode. But user can still try the aggressive layout optimization with -force-precise-rotation-cost=true. > > Differential Revision: https://reviews.llvm.org/D65673 llvm-svn: 368579
2019-08-12Revert r368565: [CodeGen] Do the Simple Early Return in block-placement pass ↵Kang Zhang1-37/+0
to optimize the blocks llvm-svn: 368574
2019-08-12[CodeGen] Do the Simple Early Return in block-placement pass to optimize the ↵Kang Zhang1-0/+37
blocks Summary: In `block-placement` pass, it will create some patterns for unconditional we can do the simple early retrun. But the `early-ret` pass is before `block-placement`, we don't want to run it again. This patch is to do the simple early return to optimize the blocks at the last of `block-placement`. Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D63972 llvm-svn: 368565
2019-08-12Revert r368509 "[CodeGen] Do the Simple Early Return in block-placement pass ↵Hans Wennborg1-37/+0
to optimize the blocks" > In `block-placement` pass, it will create some patterns for unconditional we can do the simple early retrun. > But the `early-ret` pass is before `block-placement`, we don't want to run it again. > This patch is to do the simple early return to optimize the blocks at the last of `block-placement`. > > Reviewed By: efriedma > > Differential Revision: https://reviews.llvm.org/D63972 This also revertes follow-ups r368514 and r368532. llvm-svn: 368560
2019-08-11[NFC][CodeGen] Use while loop instead for loop in ↵Kang Zhang1-3/+4
MachineBlockPlacement::optimizeBranches() This will pass EXPENSIVE check. llvm-svn: 368532
2019-08-10[NFC][CodeGen] Modify the PI++ to ++PI in ↵Kang Zhang1-1/+1
MachineBlockPlacement::optimizeBranches() llvm-svn: 368514
2019-08-10[CodeGen] Do the Simple Early Return in block-placement pass to optimize the ↵Kang Zhang1-0/+36
blocks Summary: In `block-placement` pass, it will create some patterns for unconditional we can do the simple early retrun. But the `early-ret` pass is before `block-placement`, we don't want to run it again. This patch is to do the simple early return to optimize the blocks at the last of `block-placement`. Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D63972 llvm-svn: 368509
2019-08-08[MBP] Disable aggressive loop rotate in plain modeGuozhi Wei1-36/+80
Patch https://reviews.llvm.org/D43256 introduced more aggressive loop layout optimization which depends on profile information. If profile information is not available, the statically estimated profile information(generated by BranchProbabilityInfo.cpp) is used. If user program doesn't behave as BranchProbabilityInfo.cpp expected, the layout may be worse. To be conservative this patch restores the original layout algorithm in plain mode. But user can still try the aggressive layout optimization with -force-precise-rotation-cost=true. Differential Revision: https://reviews.llvm.org/D65673 llvm-svn: 368339
2019-07-26Some case eror for: detected memory leaksKang Zhang1-25/+0
llvm-svn: 367083
2019-07-26[PowerPC] Do the Simple Early Return in block-placement pass to optimize the ↵Kang Zhang1-0/+25
blocks Summary: In `block-placement` pass, it will create some patterns for unconditional we can do the simple early retrun. But the `early-ret` pass is before `block-placement`, we don't want to run it again. This patch is to do the simple early return to optimize the blocks at the last of `block-placement`. Below is an example ``` BB: | BB: XOR 3, 3, 4 | XOR 3, 3, 4 B TBB | B ChainBB ... | ... ChainBB: | ChainBB: B TBB | ADD 3, 3, 4 ... | BLR TBB: | ADD 3, 3, 4 | BLR | ``` Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D63972 llvm-svn: 367080
2019-07-16Fix parameter name comments using clang-tidy. NFC.Rui Ueyama1-1/+1
This patch applies clang-tidy's bugprone-argument-comment tool to LLVM, clang and lld source trees. Here is how I created this patch: $ git clone https://github.com/llvm/llvm-project.git $ cd llvm-project $ mkdir build $ cd build $ cmake -GNinja -DCMAKE_BUILD_TYPE=Debug \ -DLLVM_ENABLE_PROJECTS='clang;lld;clang-tools-extra' \ -DCMAKE_EXPORT_COMPILE_COMMANDS=On -DLLVM_ENABLE_LLD=On \ -DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang++ ../llvm $ ninja $ parallel clang-tidy -checks='-*,bugprone-argument-comment' \ -config='{CheckOptions: [{key: StrictMode, value: 1}]}' -fix \ ::: ../llvm/lib/**/*.{cpp,h} ../clang/lib/**/*.{cpp,h} ../lld/**/*.{cpp,h} llvm-svn: 366177
2019-06-14[MBP] Move a latch block with conditional exit and multi predecessors to top ↵Guozhi Wei1-50/+233
of loop Current findBestLoopTop can find and move one kind of block to top, a latch block has one successor. Another common case is: * a latch block * it has two successors, one is loop header, another is exit * it has more than one predecessors If it is below one of its predecessors P, only P can fall through to it, all other predecessors need a jump to it, and another conditional jump to loop header. If it is moved before loop header, all its predecessors jump to it, then fall through to loop header. So all its predecessors except P can reduce one taken branch. Differential Revision: https://reviews.llvm.org/D43256 llvm-svn: 363471
2019-04-23Use llvm::stable_sortFangrui Song1-11/+8
While touching the code, simplify if feasible. llvm-svn: 358996
2019-04-04[IR] Refactor attribute methods in Function class (NFC)Evandro Menezes1-4/+4
Rename the functions that query the optimization kind attributes. Differential revision: https://reviews.llvm.org/D60287 llvm-svn: 357731
2019-02-22[MBP] Factor out function hasViableTopFallthrough and enhancementGuozhi Wei1-9/+36
This patch factor out the function hasViableTopFallthrough from rotateLoop. It is also enhanced. Original code checks only if there is a block can be placed before current loop top. This patch also checks if the loop top is the most possible successor of its predecessor. The attached test case shows its effect. Differential Revision: https://reviews.llvm.org/D58393 llvm-svn: 354682
2019-01-25[MBP] Don't move bottom block before header if it can't reduce taken branchesGuozhi Wei1-0/+38
If bottom of block BB has only one successor OldTop, in most cases it is profitable to move it before OldTop, except the following case: -->OldTop<- | . | | . | | . | ---Pred | | | BB----- Move BB before OldTop can't reduce the number of taken branches, this patch detects this case and prevent the moving. Differential Revision: https://reviews.llvm.org/D57067 llvm-svn: 352236
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
2019-01-09[NFC] fix trivial typos in commentsHiroshi Inoue1-1/+1
llvm-svn: 350690
2018-09-13ARM: align loops to 4 bytes on Cortex-M3 and Cortex-M4.Tim Northover1-1/+2
The Technical Reference Manuals for these two CPUs state that branching to an unaligned 32-bit instruction incurs an extra pipeline reload penalty. That's bad. This also enables the optimization at -Os since it costs on average one byte per loop in return for 1 cycle per iteration, which is pretty good going. llvm-svn: 342127
2018-07-16[CodeGen] Fix inconsistent declaration parameter nameFangrui Song1-2/+2
llvm-svn: 337200
2018-06-20[NFC] fix trivial typos in commentsHiroshi Inoue1-1/+1
llvm-svn: 335096
2018-05-14Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen1-77/+84
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-01Remove \brief commands from doxygen comments.Adrian Prantl1-40/+40
We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
2018-03-30[BlockPlacement] Disable block placement tail duplciation in structured CFG.Tim Shen1-6/+11
Summary: Tail duplication easily breaks the structure of CFG, e.g. duplicating on a region entry. If the structure is intended to be preserved, then we may want to configure tail duplication, or disable it for structured CFG. From our benchmark results disabling it doesn't cause performance regression. Notice that this currently affects AMDGPU backend. In the next patch, I also plan to turn on requiresStructuredCFG for NVPTX. All unit tests still pass. Reviewers: jlebar, arsenm Subscribers: jholewinski, sanjoy, wdng, tpr, hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D45008 llvm-svn: 328884
2017-12-22Add hasProfileData() to check if a function has profile data. NFC.Easwaran Raman1-3/+3
Summary: This replaces calls to getEntryCount().hasValue() with hasProfileData that does the same thing. This refactoring is useful to do before adding synthetic function entry counts but also a useful cleanup IMO even otherwise. I have used hasProfileData instead of hasRealProfileData as David had earlier suggested since I think profile implies "real" and I use the phrase "synthetic entry count" and not "synthetic profile count" but I am fine calling it hasRealProfileData if you prefer. Reviewers: davidxl, silvas Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41461 llvm-svn: 321331
2017-12-15MachineFunction: Return reference from getFunction(); NFCMatthias Braun1-8/+8
The Function can never be nullptr so we can return a reference. llvm-svn: 320884
2017-12-04[CodeGen] Unify MBB reference format in both MIR and debug outputFrancis Visoiu Mistrih1-1/+1
As part of the unification of the debug format and the MIR format, print MBB references as '%bb.5'. The MIR printer prints the IR name of a MBB only for block definitions. * find . \( -name "*.mir" -o -name "*.cpp" -o -name "*.h" -o -name "*.ll" \) -type f -print0 | xargs -0 sed -i '' -E 's/BB#" << ([a-zA-Z0-9_]+)->getNumber\(\)/" << printMBBReference(*\1)/g' * find . \( -name "*.mir" -o -name "*.cpp" -o -name "*.h" -o -name "*.ll" \) -type f -print0 | xargs -0 sed -i '' -E 's/BB#" << ([a-zA-Z0-9_]+)\.getNumber\(\)/" << printMBBReference(\1)/g' * find . \( -name "*.txt" -o -name "*.s" -o -name "*.mir" -o -name "*.cpp" -o -name "*.h" -o -name "*.ll" \) -type f -print0 | xargs -0 sed -i '' -E 's/BB#([0-9]+)/%bb.\1/g' * grep -nr 'BB#' and fix Differential Revision: https://reviews.llvm.org/D40422 llvm-svn: 319665
2017-11-17Fix a bunch more layering of CodeGen headers that are in TargetDavid Blaikie1-2/+2
All these headers already depend on CodeGen headers so moving them into CodeGen fixes the layering (since CodeGen depends on Target, not the other way around). llvm-svn: 318490
2017-11-08Target/TargetInstrInfo.h -> CodeGen/TargetInstrInfo.h to match layeringDavid Blaikie1-1/+1
This header includes CodeGen headers, and is not, itself, included by any Target headers, so move it into CodeGen to match the layering of its implementation. llvm-svn: 317647
2017-10-05[MBP] Remove an invalid assert.Xin Tong1-6/+0
The patch that this assert comes with is fixing a bug in MBP. The assert is invalid however. Thanks to @sergey.k.okunev for finding this Currently this fails SPECCPU2006 LTO. I will add a test case when I do more investigation and have one. llvm-svn: 315032
2017-10-04[MachineBlockPlacement] Make sure PreferredLoopExit is cleared everytime new ↵Xin Tong1-0/+10
loop is processed Summary: Rotate on exit that actually exits the current loop. Reviewers: davidxl, danielcdh, iteratee, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D38563 llvm-svn: 314937
2017-08-24[CodeGen] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko1-30/+64
warnings; other minor fixes (NFC). llvm-svn: 311703
2017-08-23Add test case for r311511Matthias Braun1-1/+2
This also changes the TailDuplicator to be configured explicitely pre/post regalloc rather than relying on the isSSA() flag. This was necessary to have `llc -run-pass` work reliably. llvm-svn: 311520
2017-08-17Increase tail dup threshold for -O3 from 3 to 4.Richard Smith1-1/+1
We see a modest performance improvement from this slightly higher tail dup threshold. Differential Revision: https://reviews.llvm.org/D36775 llvm-svn: 311139
2017-08-04BlockPlacement: add a flag to force cold block outlining w/o a profile.Kyle Butt1-1/+6
NFC. llvm-svn: 310129
2017-07-11Revert Revert [MBP] do not rotate loop if it creates extra branchSerguei Katkov1-1/+36
This is a second attempt to land this patch. The first one resulted in a crash of clang sanitizer buildbot. The fix is here and regression test is added. This is a last fix for the corner case of PR32214. Actually this is not really corner case in general. We should not do a loop rotation if we create an additional branch due to it. Consider the case where we have a loop chain H, M, B, C , where H is header with viable fallthrough from pre-header and exit from the loop M - some middle block B - backedge to Header but with exit from the loop also. C - some cold block of the loop. Let's H is determined as a best exit. If we do a loop rotation M, B, C, H we can introduce the extra branch. Let's compute the change in number of branches: +1 branch from pre-header to header -1 branch from header to exit +1 branch from header to middle block if there is such -1 branch from cold bock to header if there is one So if C is not a predecessor of H then we introduce extra branch. This change actually prohibits rotation of the loop if both true Best Exit has next element in chain as successor. Last element in chain is not a predecessor of first element of chain. Reviewers: iteratee, xur, sammccall, chandlerc Reviewed By: iteratee Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34745 llvm-svn: 307631
2017-06-26This reverts commit r306272.Serguei Katkov1-29/+0
Revert "[MBP] do not rotate loop if it creates extra branch" It breaks the sanitizer build bots. Need to fix this. llvm-svn: 306276
2017-06-26[MBP] do not rotate loop if it creates extra branchSerguei Katkov1-0/+29
This is a last fix for the corner case of PR32214. Actually this is not really corner case in general. We should not do a loop rotation if we create an additional branch due to it. Consider the case where we have a loop chain H, M, B, C , where H is header with viable fallthrough from pre-header and exit from the loop M - some middle block B - backedge to Header but with exit from the loop also. C - some cold block of the loop. Let's H is determined as a best exit. If we do a loop rotation M, B, C, H we can introduce the extra branch. Let's compute the change in number of branches: +1 branch from pre-header to header -1 branch from header to exit +1 branch from header to middle block if there is such -1 branch from cold bock to header if there is one So if C is not a predecessor of H then we introduce extra branch. This change actually prohibits rotation of the loop if both true 1) Best Exit has next element in chain as successor. 2) Last element in chain is not a predecessor of first element of chain. Reviewers: iteratee, xur Reviewed By: iteratee Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34271 llvm-svn: 306272
2017-06-16[MachineBlockPlacement] trivial fix in comments, NFCHiroshi Inoue1-5/+5
- Topologocal is abbreviated as "topo" in comments, but "top" is used in only one comment. Modify it for consistency. - Capitalize "succ" and "pred" for consistency in one figure. - Other trivial fixes. llvm-svn: 305552
2017-06-06Sort the remaining #include lines in include/... and lib/....Chandler Carruth1-2/+2
I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
2017-05-25CodeGen: Rename DEBUG_TYPE to match passnamesMatthias Braun1-2/+2
Rename the DEBUG_TYPE to match the names of corresponding passes where it makes sense. Also establish the pattern of simply referencing DEBUG_TYPE instead of repeating the passname where possible. llvm-svn: 303921
2017-05-17CodeGen: BlockPlacement: Add Message strings to asserts. NFCKyle Butt1-16/+29
Add message strings to all the unlabeled asserts in the file. Differential Revision: https://reviews.llvm.org/D33078 llvm-svn: 303316
2017-05-15CodeGen: BlockPlacement: Increase tail duplication size for O3.Kyle Butt1-3/+27
At O3 we are more willing to increase size if we believe it will improve performance. The current threshold for tail-duplication of 2 instructions is conservative, and can be relaxed at O3. Benchmark results: llvm test-suite: 6% improvement in aha, due to duplication of loop latch 3% improvement in hexxagon 2% slowdown in lpbench. Seems related, but couldn't completely diagnose. Internal google benchmark: Produces 4% improvement on internal google protocol buffer serialization benchmarks. Differential-Revision: https://reviews.llvm.org/D32324 llvm-svn: 303084
2017-04-12CodeGen: BlockPlacement: Add comment about DenseMap Safety.Kyle Butt1-0/+3
The use of a DenseMap in precomputeTriangleChains does not cause non-determinism, even though it is iterated over, as the only thing the iteration does is to insert entries into a new DenseMap, which is not iterated. Comment only change. llvm-svn: 300088
2017-04-12[MachineBlockPlacment] Add an assert to ensure there is no order dependency ↵Benjamin Kramer1-3/+7
on DenseMap iteration order. llvm-svn: 300060
2017-04-12[MachineBlockPlacement] Clean up data structures a bit.Benjamin Kramer1-21/+17
No functionality change intended. llvm-svn: 300059
2017-04-12CodeGen: BlockPlacement: Clear ComputedEdges between functions.Kyle Butt1-2/+5
Not clearing was causing non-deterministic compiles for large files. Addresses for MachineBasicBlocks would end up colliding and we would lay out a block that we assumed had been pre-computed when it had not been. llvm-svn: 300022
2017-04-10CodeGen: BlockPlacement: Don't always tail-duplicate with no other successor.Kyle Butt1-5/+1
The math works out where it can actually be counter-productive. The probability calculations correctly handle the case where the alternative is 0 probability, rely on those calculations. Includes a test case that demonstrates the problem. llvm-svn: 299892
2017-04-10CodeGen: BlockPlacement: Minor probability changes.Kyle Butt1-24/+32
Qin may be large, and Succ may be more frequent than BB. Take these both into account when deciding if tail-duplication is profitable. llvm-svn: 299891
2017-03-23Fix trellis layout to avoid mis-identify triangle.Dehao Chen1-1/+6
Summary: For the following CFG: A->B B->C A->C If there is another edge B->D, then ABC should not be considered as triangle. Reviewers: davidxl, iteratee Reviewed By: iteratee Subscribers: nemanjai, llvm-commits Differential Revision: https://reviews.llvm.org/D31310 llvm-svn: 298661
generated by cgit v1.1 at 2025-10-02 09:28:02 +0000