summaryrefslogtreecommitdiff
path: root/lib/CodeGen/SpillPlacement.cpp
Commit message (Collapse)AuthorAge
* [Modules] Remove potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-22
| | | | | | | | | | | | define below all header includes in the lib/CodeGen/... tree. While the current modules implementation doesn't check for this kind of ODR violation yet, it is likely to grow support for it in the future. It also removes one layer of macro pollution across all the included headers. Other sub-trees will follow. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206837 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-14
| | | | | | instead of comparing to nullptr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206142 91177308-0d34-0410-b5e6-96231b3b80d8
* RegAlloc: Account for a variable entry block frequencyDuncan P. N. Exon Smith2014-04-08
| | | | | | | | | | | | | | | | | | | | Until r197284, the entry frequency was constant -- i.e., set to 2^14. Although current ToT still has a constant entry frequency, since r197284 that has been an implementation detail (which is soon going to change). - r204690 made the wrong assumption for the CSRCost metric. Adjust callee-saved register cost based on entry frequency. - r185393 made the wrong assumption (although it was valid at the time). Update SpillPlacement.cpp::Threshold to be relative to the entry frequency. Since ToT still has 2^14 entry frequency, this should have no observable functionality change. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@205789 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-02
| | | | | | Remove the old functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202636 91177308-0d34-0410-b5e6-96231b3b80d8
* SpillPlacement: fix a bug in iterate.Manman Ren2014-02-28
| | | | | | | | | | | | | Inside iterate, we scan backwards then scan forwards in a loop. When iteration is not zero, the last node was just updated so we can skip it. But when iteration is zero, we can't skip the last node. For the testing case, fixing this will save a spill and move register copies from hot path to cold path. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202557 91177308-0d34-0410-b5e6-96231b3b80d8
* [block-freq] Rename getEntryFrequency() -> getEntryFreq() to match ↵Michael Gottesman2013-12-14
| | | | | | getBlockFreq() in all *BlockFrequencyInfo*. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@197304 91177308-0d34-0410-b5e6-96231b3b80d8
* [block-freq] Store MBFI as a field on SpillPlacement so we can access it to ↵Michael Gottesman2013-12-14
| | | | | | get the entry frequency while processing data. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@197291 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply r185393.Jakob Stoklund Olesen2013-07-16
| | | | | | | | | | | | | | | | | | | | | | Original commit message: Remove floating point computations from SpillPlacement.cpp. Patch by Benjamin Kramer! Use the BlockFrequency class instead of floats in the Hopfield network computations. This rescales the node Bias field from a [-2;2] float range to two block frequencies BiasN and BiasP pulling in opposite directions. This construct has a more predictable behavior when block frequencies saturate. The per-node scaling factors are no longer necessary, assuming the block frequencies around a bundle are consistent. This patch can cause the register allocator to make different spilling decisions. The differences should be small. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186434 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert (most of) r185393 and r185395.Jakob Stoklund Olesen2013-07-02
| | | | | | | | | | | "Remove floating point computations form SpillPlacement.cpp." These commits caused test failures in lencod on clang-native-arm-lnt. I suspect these changes are only exposing an existing issue, but reverting anyway to keep the bots passing while we investigate. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185447 91177308-0d34-0410-b5e6-96231b3b80d8
* Tweak some comments that referred to the old bias computations.Jakob Stoklund Olesen2013-07-01
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185395 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove floating point computations form SpillPlacement.cpp.Jakob Stoklund Olesen2013-07-01
| | | | | | | | | | | | | | | | | | Patch by Benjamin Kramer! Use the BlockFrequency class instead of floats in the Hopfield network computations. This rescales the node Bias field from a [-2;2] float range to two block frequencies BiasN and BiasP pulling in opposite directions. This construct has a more predictable behavior when block frequencies saturate. The per-node scaling factors are no longer necessary, assuming the block frequencies around a bundle are consistent. This patch can cause the register allocator to make different spilling decisions. The differences should be small. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185393 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.Benjamin Kramer2013-06-17
| | | | | | | | | | | | | | | | | | The main advantages here are way better heuristics, taking into account not just loop depth but also __builtin_expect and other static heuristics and will eventually learn how to use profile info. Most of the work in this patch is pushing the MachineBlockFrequencyInfo analysis into the right places. This is good for a 5% speedup on zlib's deflate (x86_64), there were some very unfortunate spilling decisions in its hottest loop in longest_match(). Other benchmarks I tried were mostly neutral. This changes register allocation in subtle ways, update the tests for it. 2012-02-20-MachineCPBug.ll was deleted as it's very fragile and the instruction it looked for was gone already (but the FileCheck pattern picked up unrelated stuff). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@184105 91177308-0d34-0410-b5e6-96231b3b80d8
* Move #include of BitVector from .h to .cpp file.Jakub Staszak2013-03-18
| | | | | | | Also remove unneeded #include and forward declaration. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177357 91177308-0d34-0410-b5e6-96231b3b80d8
* Give a small negative bias to giant edge bundles.Jakob Stoklund Olesen2012-05-21
| | | | | | | | | | | | | | | | This helps compile time when the greedy register allocator splits live ranges in giant functions. Without the bias, we would try to grow regions through the giant edge bundles, usually to find out that the region became too big and expensive. If a live range has many uses in blocks near the giant bundle, the small negative bias doesn't make a big difference, and we still consider regions including the giant edge bundle. Giant edge bundles are usually connected to landing pads or indirect branches. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157174 91177308-0d34-0410-b5e6-96231b3b80d8
* Be more conservative when forming compact regions.Jakob Stoklund Olesen2011-08-03
| | | | | | | | | | | | | | | Apply twice the negative bias on transparent blocks when computing the compact regions. This excludes loop backedges from the region when only one of the loop blocks uses the register. Previously, we would include the backedge in the region if the loop preheader and the loop latch both used the register, but the loop header didn't. When both the header and latch blocks use the register, we still keep it live on the backedge. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136832 91177308-0d34-0410-b5e6-96231b3b80d8
* Extend the SpillPlacement interface with two new features.Jakob Stoklund Olesen2011-08-02
| | | | | | | | | | | | | | | | | | | | | | | | The PrefBoth constraint is used for blocks that ideally want a live-in value both on the stack and in a register. This would be used by a block that has a use before interference forces a spill. Secondly, add the ChangesValue flag to BlockConstraint. This tells SpillPlacement if a live-in value on the stack can be reused as a live-out stack value for free. If the block redefines the virtual register, a spill would be required for that. This extra information will be used by SpillPlacement to more accurately calculate spill costs when a value can exist both on the stack and in a register. The simplest example is a basic block that reads the virtual register, but doesn't change its value. Spilling around such a block requires a reload, but no spill in the block. The spiller already knows this, but the spill placer doesn't. That can sometimes lead to suboptimal regions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136731 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a simple method for marking blocks with interference in and out.Jakob Stoklund Olesen2011-07-23
| | | | | | | | | | This method matches addLinks - All the listed blocks are considered to have interference, so they add a negative bias to their bundles. This could also be done by addConstraints, but that requires building a separate BlockConstraint array. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135844 91177308-0d34-0410-b5e6-96231b3b80d8
* Build the Hopfield network incrementally when splitting global live ranges.Jakob Stoklund Olesen2011-04-09
| | | | | | | | | It is common for large live ranges to have few basic blocks with register uses and many live-through blocks without any uses. This approach grows the Hopfield network incrementally around the use blocks, completely avoiding checking interference for some through blocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129188 91177308-0d34-0410-b5e6-96231b3b80d8
* Prefer multiplications to divisions.Jakob Stoklund Olesen2011-04-07
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129080 91177308-0d34-0410-b5e6-96231b3b80d8
* Extract SpillPlacement::addLinks for handling the special transparent blocks.Jakob Stoklund Olesen2011-04-07
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129079 91177308-0d34-0410-b5e6-96231b3b80d8
* Keep track of the number of positively biased nodes when adding constraints.Jakob Stoklund Olesen2011-04-06
| | | | | | If there are no positive nodes, the algorithm can be aborted early. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129021 91177308-0d34-0410-b5e6-96231b3b80d8
* Break the spill placement algorithm into three parts: prepare, ↵Jakob Stoklund Olesen2011-04-06
| | | | | | | | addConstraints, and finish. This will allow us to abort the algorithm early if it is determined to be futile. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129020 91177308-0d34-0410-b5e6-96231b3b80d8
* Precompute block frequencies, pow() isn't free.Jakob Stoklund Olesen2011-03-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126975 91177308-0d34-0410-b5e6-96231b3b80d8
* Trim debugging output.Jakob Stoklund Olesen2011-02-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125802 91177308-0d34-0410-b5e6-96231b3b80d8
* Silence an MSVC warningJakob Stoklund Olesen2011-02-03
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124798 91177308-0d34-0410-b5e6-96231b3b80d8
* Divert Hopfield network debug output. It is very noisy.Jakob Stoklund Olesen2011-01-19
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123859 91177308-0d34-0410-b5e6-96231b3b80d8
* Add RAGreedy methods for splitting live ranges around regions.Jakob Stoklund Olesen2011-01-18
| | | | | | | | | | Analyze the live range's behavior entering and leaving basic blocks. Compute an interference pattern for each allocation candidate, and use SpillPlacement to find an optimal region where that register can be live. This code is still not enabled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123774 91177308-0d34-0410-b5e6-96231b3b80d8
* Add the SpillPlacement analysis pass.Jakob Stoklund Olesen2011-01-06
This pass precomputes CFG block frequency information that can be used by the register allocator to find optimal spill code placement. Given an interference pattern, placeSpills() will compute which basic blocks should have the current variable enter or exit in a register, and which blocks prefer the stack. The algorithm is ready to consume block frequencies from profiling data, but for now it gets by with the static estimates used for spill weights. This is a work in progress and still not hooked up to RegAllocGreedy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122938 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-29 06:16:16 +0000