| 6d9fe79afe3a325fb05165758a20470475aca8e6 |
|
16-Jul-2013 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Reapply r185393.
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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 92879a8cb1490c90bf952a17a110dc45063832b0 |
|
02-Jul-2013 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Revert (most of) r185393 and r185395.
"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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 7babb052a68a35a7b21906280e67f06502846f9d |
|
02-Jul-2013 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Tweak some comments that referred to the old bias computations.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185395 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 74d2a3e1a014b93e9037a7b04e85dc92bfb54fa7 |
|
02-Jul-2013 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Remove floating point computations form 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@185393 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 4eed756153b84c211114a3e9186bf0cb55d4b394 |
|
17-Jun-2013 |
Benjamin Kramer <benny.kra@googlemail.com> |
Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.
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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| f31034db8c12197d00b3e356e1d2a702c2339d49 |
|
19-Mar-2013 |
Jakub Staszak <kubastaszak@gmail.com> |
Move #include of BitVector from .h to .cpp file.
Also remove unneeded #include and forward declaration.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177357 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 1dc12aa148f0ecb4135fa3e47e7a2ac81ceac394 |
|
21-May-2012 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Give a small negative bias to giant edge bundles.
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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| b87f91b063a0ac853735f2af3bd94fb8551a11ff |
|
04-Aug-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Be more conservative when forming compact regions.
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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 0e0a8806d49038b60a0c20427d9f410b01cbb012 |
|
02-Aug-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Extend the SpillPlacement interface with two new features.
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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| e60f103d2d3541e57a6ca8d788e959e03b615e5f |
|
23-Jul-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add a simple method for marking blocks with interference in and out.
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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0c |
|
09-Apr-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Build the Hopfield network incrementally when splitting global live ranges.
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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 0bd2bd9ecc8abd3c3ed91a51aa8c51aaab401b5d |
|
07-Apr-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Prefer multiplications to divisions.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129080 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 7b41fbe87234f3ceef6ae11209730cbed4b69092 |
|
07-Apr-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Extract SpillPlacement::addLinks for handling the special transparent blocks.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129079 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 70d4370b47cdd375bbea98e50452789fe4f1af04 |
|
06-Apr-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Keep track of the number of positively biased nodes when adding constraints.
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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 9efa2a263ea470caacef1c85f6ca45e32bf516d3 |
|
06-Apr-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Break the spill placement algorithm into three parts: prepare, 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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 40a42a2ccaaa19a109667ed7abf224cc8733cd9c |
|
04-Mar-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Precompute block frequencies, pow() isn't free.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126975 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| febb0bd0b9b75923dea4c34f22be7e4c7b6b501e |
|
18-Feb-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Trim debugging output.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125802 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 9590c7fbca2a3c18d0000676b2a6336f6458ed42 |
|
03-Feb-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Silence an MSVC warning
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124798 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| fc7d775178aa890f8bb5e9b1be0bf675dc7d29f4 |
|
20-Jan-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Divert Hopfield network debug output. It is very noisy.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123859 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| b5fa9333431673aac2ced8dea80152349a85cf6f |
|
18-Jan-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add RAGreedy methods for splitting live ranges around regions.
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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|
| 8bfe50871f9cb1b022483e0e1307ab5b8c9e5650 |
|
06-Jan-2011 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add the SpillPlacement analysis pass.
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
/external/llvm/lib/CodeGen/SpillPlacement.cpp
|