summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/MachineBlockPlacement.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Branch Folding: Accept explicit threshold for tail merge size.Kyle Butt2016-08-181-1/+3
| | | | | | | | This is prep work for allowing the threshold to be different during layout, and to enforce a single threshold between merging and duplicating during layout. No observable change intended. llvm-svn: 279117
* [MBP] do not reorder and move up loop latch blockSjoerd Meijer2016-08-161-0/+10
| | | | | | | | | | Do not reorder and move up a loop latch block before a loop header when optimising for size because this will generate an extra unconditional branch. Differential Revision: https://reviews.llvm.org/D22521 llvm-svn: 278840
* Use the range variant of remove_if instead of unpacking begin/endDavid Majnemer2016-08-121-4/+4
| | | | | | No functionality change is intended. llvm-svn: 278475
* Use the range variant of find instead of unpacking begin/endDavid Majnemer2016-08-111-3/+2
| | | | | | | | | If the result of the find is only used to compare against end(), just use is_contained instead. No functionality change is intended. llvm-svn: 278433
* Codegen: MachineBlockPlacement Improve probability layout.Kyle Butt2016-07-291-15/+45
| | | | | | | | | | | | | | | | | | | | | | | | | The following pattern was being layed out poorly: A / \ B C / \ / \ D E ? (Doesn't matter) Where A->B is far more likely than A->C, and prob(B->D) = prob(B->E) The current algorithm gives: A,B,C,E (D goes on worklist) It does this even if C has a frequency count of 0. This patch adjusts the layout calculation so that if freq(B->E) >> freq(C->E) then we go ahead and layout E rather than C. Fallthrough half the time is better than fallthrough never, or fallthrough very rarely. The resulting layout is: A,B,E, (C and D are in a worklist) llvm-svn: 277187
* [MBP] Added some more debug messages and some clean ups /NFCSjoerd Meijer2016-07-271-11/+31
| | | | | | Differential Revision: https://reviews.llvm.org/D22669 llvm-svn: 276849
* [MBP] Clean up of the comments, and a first attempt to better describe a partSjoerd Meijer2016-07-151-28/+49
| | | | | | | | of the algorithm. Differential Revision: https://reviews.llvm.org/D22364 llvm-svn: 275595
* Rename AnalyzeBranch* to analyzeBranch*.Jacques Pienaar2016-07-151-6/+6
| | | | | | | | | | | | Summary: NFC. Rename AnalyzeBranch/AnalyzeBranchPredicate to analyzeBranch/analyzeBranchPredicate to follow LLVM coding style and be consistent with TargetInstrInfo's analyzeCompare and analyzeSelect. Reviewers: tstellarAMD, mcrosier Subscribers: mcrosier, jholewinski, jfb, arsenm, dschuff, jyknight, dsanders, nemanjai Differential Revision: https://reviews.llvm.org/D22409 llvm-svn: 275564
* [MBP] method interface cleanupXinliang David Li2016-07-011-25/+20
| | | | | | | Make worklist and ehworklist member of the class so that they don't need to be passed around. llvm-svn: 274333
* Codegen: [MBP] Add messages to asserts. NFCKyle Butt2016-06-281-3/+4
| | | | llvm-svn: 274075
* [MBP] show function name in debug dumpXinliang David Li2016-06-241-0/+1
| | | | llvm-svn: 273744
* Codegen: [MBP] Add assert strings. NFCKyle Butt2016-06-171-2/+2
| | | | llvm-svn: 273067
* [MBP] add comments and bug fixXinliang David Li2016-06-151-3/+13
| | | | | | | | | | Document the new parameter and threshod computation model. Also fix a bug when the threshold parameter is set to be different from the default. llvm-svn: 272749
* Set machine block placement hot prob threshold for both static and runtime ↵Dehao Chen2016-06-141-8/+16
| | | | | | | | | | | | | | profile. Summary: With runtime profile, we have more confidence in branch probability, thus during basic block layout, we set a lower hot prob threshold so that blocks can be layouted optimally. Reviewers: djasper, davidxl Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D20991 llvm-svn: 272729
* [MBP] Interface cleanups /NFCXinliang David Li2016-06-131-59/+61
| | | | | | | | | | | | Save machine function pointer so that the reference does not need to be passed around. This also gives other methods access to machine function for information such as entry count etc. llvm-svn: 272594
* [MBP] Code cleanup #3 /NFCXinliang David Li2016-06-131-43/+137
| | | | | | | | | | | | | | | This is third patch to clean up the code. Included in this patch: 1. Further unclutter trace/chain formation main routine; 2. Isolate the logic to compute global cost/conflict detection into its own method; 3. Heavily document the selection algorithm; 4. Added helper hook to allow PGO specific logic to be added in the future. llvm-svn: 272582
* [MBP] Code cleanup /NFCXinliang David Li2016-06-121-43/+73
| | | | | | | | | | This is second patch to clean up the code. In this patch, the logic to determine block outlinining is refactored and more comments are added. llvm-svn: 272514
* [MBP] Code cleanup /NFCXinliang David Li2016-06-111-30/+59
| | | | | | | | | | | | This is one of the patches to clean up the code so that it is in a better form to make future enhancements easier. In htis patch, the logic to collect viable successors are extrated as a helper to unclutter the caller which gets very large recenty. Also cleaned up BP adjustment code. llvm-svn: 272482
* Reapply "[MBP] Reduce code size by running tail merging in MBP.""Haicheng Wu2016-06-091-3/+36
| | | | | | | | | | | | | | | | This reapplies commit r271930, r271915, r271923. They hit a bug in Thumb which is fixed in r272258 now. The original message: The code layout that TailMerging (inside BranchFolding) works on is not the final layout optimized based on the branch probability. Generally, after BlockPlacement, many new merging opportunities emerge. This patch calls Tail Merging after MBP and calls MBP again if Tail Merging merges anything. llvm-svn: 272267
* Revive http://reviews.llvm.org/D12778 to handle forward-hot-prob and ↵Dehao Chen2016-06-081-3/+10
| | | | | | | | | | | | | | | | | | | | | | | backward-hot-prob consistently. Summary: Consider the following diamond CFG: A / \ B C \/ D Suppose A->B and A->C have probabilities 81% and 19%. In block-placement, A->B is called a hot edge and the final placement should be ABDC. However, the current implementation outputs ABCD. This is because when choosing the next block of B, it checks if Freq(C->D) > Freq(B->D) * 20%, which is true (if Freq(A) = 100, then Freq(B->D) = 81, Freq(C->D) = 19, and 19 > 81*20%=16.2). Actually, we should use 25% instead of 20% as the probability here, so that we have 19 < 81*25%=20.25, and the desired ABDC layout will be generated. Reviewers: djasper, davidxl Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D20989 llvm-svn: 272203
* Revert "[MBP] Reduce code size by running tail merging in MBP."Haicheng Wu2016-06-071-36/+3
| | | | | | | This reverts commit r271930, r271915, r271923. They break a thumb selfhosting bot. llvm-svn: 272017
* [MBP] Reduce code size by running tail merging in MBP.Haicheng Wu2016-06-061-3/+36
| | | | | | | | | | | | | The code layout that TailMerging (inside BranchFolding) works on is not the final layout optimized based on the branch probability. Generally, after BlockPlacement, many new merging opportunities emerge. This patch calls Tail Merging after MBP and calls MBP again if Tail Merging merges anything. Differential Revision: http://reviews.llvm.org/D20276 llvm-svn: 271925
* Replace hard coded probability threshold with parameter /NFCXinliang David Li2016-06-031-1/+3
| | | | llvm-svn: 271751
* [MBP] Factor out the optimizations on branch conditions and unanalyzable ↵Haicheng Wu2016-05-241-44/+49
| | | | | | | | | | | | | | | | | | | | | branches. NFCI. The benefits of this patch are -- We call AnalyzeBranch() to optimize unanalyzable branches, but the result of AnalyzeBranch() is not used. Now the result is useful. -- Before the layout of all the MBBs is set, the result of AnalyzeBranch() is not correct and needs to be fixed before using it to optimize the branch conditions. Now this optimization is called after the layout, the code used to fix the result of AnalyzeBranch() is not needed. -- The branch condition of the last block is not optimized before. Now it is optimized. Differential Revision: http://reviews.llvm.org/D20177 llvm-svn: 270623
* [MBP] Remove a redundant skipFunction(). NFC.Haicheng Wu2016-05-181-3/+0
| | | | | | | | skipFunction() is called twice. Differential Revision: http://reviews.llvm.org/D20377 llvm-svn: 269994
* Fix option description /NFCXinliang David Li2016-05-121-2/+2
| | | | llvm-svn: 269307
* [Layout] Add a new option (NFC)Xinliang David Li2016-05-121-1/+7
| | | | | | | | | | Currently cost based loop rotation algo can only be turned on with two conditions: the function has real profile data, and -precise-rotation-cost flag is turned on. This is not convenient for developers to experiment when profile is not available. Add a new option to force the new rotation algorithm -force-precise-rotation-cost llvm-svn: 269266
* Add opt-bisect support to additional passes that can be skippedAndrew Kaylor2016-05-031-0/+3
| | | | | | Differential Revision: http://reviews.llvm.org/D19882 llvm-svn: 268457
* [MachineBlockPlacement] Let the target optimize the branches at the end.Quentin Colombet2016-05-021-0/+13
| | | | | | | | | | | | | | | After the layout of the basic blocks is set, the target may be able to get rid of unconditional branches to fallthrough blocks that the generic code does not catch. This happens any time TargetInstrInfo::AnalyzeBranch is not able to analyze all the branches involved in the terminators sequence, while still understanding a few of them. In such situation, AnalyzeBranch can directly modify the branches if it has been instructed to do so. This patch takes advantage of that. llvm-svn: 268328
* [MBP] Use Function::optForSize() instead of checking OptimizeForSize directly.Haicheng Wu2016-04-291-2/+1
| | | | | | Fix a FIXME. Disable loop alignment if compiled with -Oz now. llvm-svn: 268121
* [MBP] Split placement and alignment into two functions. NFC.Haicheng Wu2016-04-291-0/+5
| | | | | | Cut and Paste. llvm-svn: 268067
* Re-commit optimization bisect support (r267022) without new pass manager ↵Andrew Kaylor2016-04-221-1/+1
| | | | | | | | | | support. The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling). Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267231
* Revert "Initial implementation of optimization bisect support."Vedant Kumar2016-04-221-1/+1
| | | | | | | | This reverts commit r267022, due to an ASan failure: http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549 llvm-svn: 267115
* Initial implementation of optimization bisect support.Andrew Kaylor2016-04-211-1/+1
| | | | | | | | | | | | This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations. The bisection is enabled using a new command line option (-opt-bisect-limit). Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit. A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used. The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check. Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute. A new function call has been added for module and SCC passes that behaves in a similar way. Differential Revision: http://reviews.llvm.org/D19172 llvm-svn: 267022
* Do not select EhPad BB in MachineBlockPlacement when there is regular BB to ↵Amaury Sechet2016-04-071-12/+66
| | | | | | | | | | | | | | | | | schedule Summary: EHPad BB are not entered the classic way and therefor do not need to be placed after their predecessors. This patch make sure EHPad BB are not chosen amongst successors to form chains, and are selected as last resort when selecting the best candidate. EHPad are scheduled in reverse probability order in order to have them flow into each others naturally. Reviewers: chandlerc, majnemer, rafael, MatzeB, escha, silvas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D17625 llvm-svn: 265726
* [BlockPlacement] Remove an unnecessary continueAmaury Sechet2016-04-071-1/+0
| | | | | | NFC. llvm-svn: 265643
* [MBP] Remove an unused function parameterAmaury Sechet2016-04-071-5/+3
| | | | | | NFC. llvm-svn: 265642
* Revert "[BlockPlacement] Remove an unnecessary continue" and "[MBP] Remove ↵Amaury Sechet2016-04-071-3/+6
| | | | | | an unused function parameter" llvm-svn: 265638
* [MBP] Remove an unused function parameterHaicheng Wu2016-04-061-5/+3
| | | | | | NFC. llvm-svn: 265596
* [BlockPlacement] Remove an unnecessary continueHaicheng Wu2016-04-051-1/+0
| | | | | | NFC. llvm-svn: 265407
* Factor out MachineBlockPlacement::fillWorkLists. NFCAmaury Sechet2016-03-141-36/+39
| | | | | | | | | | | | Summary: There are places in MachineBlockPlacement where a worklist is filled in pretty much identical way. The code is duplicated. This refactor it so that the same code is used in both scenarii. Reviewers: chandlerc, majnemer, rafael, MatzeB, escha, silvas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D18077 llvm-svn: 263495
* Minor code cleanup. NFC.Junmo Park2016-03-111-1/+1
| | | | llvm-svn: 263196
* [MBP] Renaming a confusing variable and add clarifying commentsPhilip Reames2016-03-031-19/+24
| | | | | | Was discussed as part of http://reviews.llvm.org/D17830 llvm-svn: 262571
* [MBP] Avoid placing random blocks between loop preheader and headerPhilip Reames2016-03-031-1/+2
| | | | | | | | | | If we have a loop with a rarely taken path, we will prune that from the blocks which get added as part of the loop chain. The problem is that we weren't then recognizing the loop chain as schedulable when considering the preheader when forming the function chain. We'd then fall to various non-predecessors before finally scheduling the loop chain (as if the CFG was unnatural.) The net result was that there could be lots of garbage between a loop preheader and the loop, even though we could have directly fallen into the loop. It also meant we separated hot code with regions of colder code. The particular reason for the rejection of the loop chain was that we were scanning predecessor of the header, seeing the backedge, believing that was a globally more important predecessor (true), but forgetting to account for the fact the backedge precessor was already part of the existing loop chain (oops!. Differential Revision: http://reviews.llvm.org/D17830 llvm-svn: 262547
* [MBP] Remove overly verbose debug outputPhilip Reames2016-03-021-5/+2
| | | | llvm-svn: 262531
* [MBP] Adjust debug output to be more focused and approachablePhilip Reames2016-03-021-18/+9
| | | | llvm-svn: 262522
* Partially revert "Add command line options to force function/loop alignments."Chad Rosier2016-01-211-10/+0
| | | | | | This partially reverts r256571 in favor of the solution in r258409. llvm-svn: 258421
* [BlockPlacement] Add option to align all non-fall-through blocks.Geoff Berry2016-01-211-0/+16
| | | | | | | | | | | | Summary: This option is being added for testing purposes. Reviewers: mcrosier Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D16410 llvm-svn: 258409
* Add command line options to force function/loop alignments.Chad Rosier2015-12-291-0/+10
| | | | | | | These are being added for testing purposes. http://reviews.llvm.org/D15648 llvm-svn: 256571
* Replace all weight-based interfaces in MBB with probability-based ↵Cong Hou2015-12-011-41/+30
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | interfaces, and update all uses of old interfaces. (This is the second attempt to submit this patch. The first caused two assertion failures and was reverted. See https://llvm.org/bugs/show_bug.cgi?id=25687) The patch in http://reviews.llvm.org/D13745 is broken into four parts: 1. New interfaces without functional changes (http://reviews.llvm.org/D13908). 2. Use new interfaces in SelectionDAG, while in other passes treat probabilities as weights (http://reviews.llvm.org/D14361). 3. Use new interfaces in all other passes. 4. Remove old interfaces. This patch is 3+4 above. In this patch, MBB won't provide weight-based interfaces any more, which are totally replaced by probability-based ones. The interface addSuccessor() is redesigned so that the default probability is unknown. We allow unknown probabilities but don't allow using it together with known probabilities in successor list. That is to say, we either have a list of successors with all known probabilities, or all unknown probabilities. In the latter case, we assume each successor has 1/N probability where N is the number of successors. An assertion checks if the user is attempting to add a successor with the disallowed mixed use as stated above. This can help us catch many misuses. All uses of weight-based interfaces are now updated to use probability-based ones. Differential revision: http://reviews.llvm.org/D14973 llvm-svn: 254377
OpenPOWER on IntegriCloud