summaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAllocPBQP.cpp
Commit message (Collapse)AuthorAge
* CalcSpillWeights: give a better describing name to calculateSpillWeightsArnaud A. de Grandmaison2013-11-11
| | | | | | | | Besides, this relates it more obviously to the VirtRegAuxInfo::calculateSpillWeightAndHint. No functionnal change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194404 91177308-0d34-0410-b5e6-96231b3b80d8
* CalculateSpillWeights does not need to be a passArnaud A. de Grandmaison2013-11-10
| | | | | | | | | | Based on discussions with Lang Hames and Jakob Stoklund Olesen at the hacker's lab, and in the light of upcoming work on the PBQP register allocator, it was though that CalcSpillWeights does not need to be a pass. This change will enable to customize / tune the spill weight computation depending on the allocator. Update the documentation style while there. No functionnal change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194356 91177308-0d34-0410-b5e6-96231b3b80d8
* Re-apply r194300 with fixes for warnings.Lang Hames2013-11-09
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194311 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r194300 which broke the build.Nick Lewycky2013-11-09
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194308 91177308-0d34-0410-b5e6-96231b3b80d8
* Rewrite the PBQP graph data structure.Lang Hames2013-11-09
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The new graph structure replaces the node and edge linked lists with vectors. Free lists (well, free vectors) are used for fast insertion/deletion. The ultimate aim is to make PBQP graphs cheap to clone. The motivation is that the PBQP solver destructively consumes input graphs while computing a solution, forcing the graph to be fully reconstructed for each round of PBQP. This imposes a high cost on large functions, which often require several rounds of solving/spilling to find a final register allocation. If we can cheaply clone the PBQP graph and incrementally update it between rounds then hopefully we can reduce this cost. Further, once we begin pooling matrix/vector values (future work), we can cache some PBQP solver metadata and share it between cloned graphs, allowing the PBQP solver to re-use some of the computation done in earlier rounds. For now this is just a data structure update. The allocator and solver still use the graph the same way as before, fully reconstructing it between each round. I expect no material change from this update, although it may change the iteration order of the nodes, causing ties in the solver to break in different directions, and this could perturb the generated allocations (hopefully in a completely benign way). Thanks very much to Arnaud Allard de Grandmaison for encouraging me to get back to work on this, and for a lot of discussion and many useful PBQP test cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194300 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "CalculateSpillWeights does not need to be a pass"Arnaud A. de Grandmaison2013-11-08
| | | | | | Temporarily revert my previous commit until I understand why it breaks 3 target tests. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194272 91177308-0d34-0410-b5e6-96231b3b80d8
* CalculateSpillWeights does not need to be a passArnaud A. de Grandmaison2013-11-08
| | | | | | | | | | Based on discussions with Lang Hames and Jakob Stoklund Olesen at the hacker's lab, and in the light of upcoming work on the PBQP register allocator, it was though that CalcSpillWeights does not need to be a pass. This change will enable to customize / tune the spill weight computation depending on the allocator. Update the documentation style while there. No functionnal change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194269 91177308-0d34-0410-b5e6-96231b3b80d8
* Track new virtual registers by register number.Mark Lacey2013-08-14
| | | | | | | | | | Track new virtual registers by register number, rather than by the live interval created for them. This is the first step in separating the creation of new virtual registers and new live intervals. Eventually live intervals will be created and populated on demand after the virtual registers have been created and used in instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188434 91177308-0d34-0410-b5e6-96231b3b80d8
* Make PBQP require/preserve MachineLoopInfo - the spiller requires it.Lang Hames2013-07-01
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185378 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
* Replace uses of the deprecated std::auto_ptr with OwningPtr.Andy Gibbs2013-04-15
| | | | | | This is a rework of the broken parts in r179373 which were subsequently reverted in r179374 due to incompatibility with C++98 compilers. This version should be ok under C++98. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179520 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert broken pieces of r179373.Benjamin Kramer2013-04-12
| | | | | | | You can't copy an OwningPtr, and move semantics aren't available in C++98. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179374 91177308-0d34-0410-b5e6-96231b3b80d8
* Replace uses of the deprecated std::auto_ptr with OwningPtr.Andy Gibbs2013-04-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179373 91177308-0d34-0410-b5e6-96231b3b80d8
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-02
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
* Use MRI::getSimpleHint() instead of getRegAllocPref() in remaining cases.Jakob Stoklund Olesen2012-12-04
| | | | | | | | | Targets can provide multiple hints now, so getRegAllocPref() doesn't make sense any longer because it only returns one preferred register. Replace it with getSimpleHint() in the remaining heuristics. This function only git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169188 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-03
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
* Make the LiveRegMatrix analysis available to targets.Jakob Stoklund Olesen2012-11-28
| | | | | | | | | | | No functional change, just moved header files. Targets can inject custom passes between register allocation and rewriting. This makes it possible to tweak the register allocation before rewriting, using the full global interference checking available from LiveRegMatrix. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168806 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r168630, r168631, and r168633 as these are causing nightly test failures.Chad Rosier2012-11-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168751 91177308-0d34-0410-b5e6-96231b3b80d8
* Now that the X86 Maximal Stack Alignment Check pass has been removed (i.e.,Chad Rosier2012-11-26
| | | | | | | | | r168627), we no longer need to call the freezeReservedRegs() function a second time. Previously, this pass was conservatively adding the FP to the set of reserved registers, requiring the second update to the reserved registers. rdar://12719844 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168631 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unused typedef.Lang Hames2012-10-29
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166910 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove LIS::isAllocatable() and isReserved() helpers.Jakob Stoklund Olesen2012-10-15
| | | | | | All callers can simply use the corresponding MRI functions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165985 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch most getReservedRegs() clients to the MRI equivalent.Jakob Stoklund Olesen2012-10-15
| | | | | | | Using the cached bit vector in MRI avoids comstantly allocating and recomputing the reserved register bit vector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165983 91177308-0d34-0410-b5e6-96231b3b80d8
* My earlier "fix" for PBQP (see r165201) was incorrect. The real issue was thatLang Hames2012-10-10
| | | | | | | | | checkRegMaskInterference only initializes the bitmask on the first interference. This fixes PR14027 and (re)fixes PR13945. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165608 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix reg mask slot test, and preserve LiveIntervals and VirtRegMap in the PBQPLang Hames2012-10-04
| | | | | | | allocator. Fixes PR13945. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165201 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unused typedefs gcc4.8 warns about.Roman Divacky2012-09-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163225 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a getName function to MachineFunction. Use it in places that previously ↵Craig Topper2012-08-22
| | | | | | did getFunction()->getName(). Remove includes of Function.h that are no longer needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162347 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove LiveIntervals::trackingRegUnits().Jakob Stoklund Olesen2012-06-22
| | | | | | | | | With regunit liveness permanently enabled, this function would always return true. Also remove now obsolete code for checking physreg interference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159006 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove spurious typedefs.Jakob Stoklund Olesen2012-06-20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158878 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove the RenderMachineFunction HTML output pass.Jakob Stoklund Olesen2012-06-20
| | | | | | | I don't think anyone has been using this functionality for a while, and it is getting in the way of refactoring now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158876 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach PBQPBuilder::build() about regunit interference.Jakob Stoklund Olesen2012-06-20
| | | | | | | Filter out physreg candidates with regunit interferrence. Also compute regmask interference more efficiently. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158864 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid iterating with LiveIntervals::iterator.Jakob Stoklund Olesen2012-06-20
| | | | | | | | | | That is a DenseMap iterator keyed by pointers, so the iteration order is nondeterministic. I would like to replace the DenseMap with an IndexedMap which doesn't allow iteration. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158856 91177308-0d34-0410-b5e6-96231b3b80d8
* Also compute MBB live-in lists in the new rewriter pass.Jakob Stoklund Olesen2012-06-09
| | | | | | | | | This deduplicates some code from the optimizing register allocators, and it means that it is now possible to change the register allocators' solutions simply by editing the VirtRegMap between the register allocator pass and the rewriter. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158249 91177308-0d34-0410-b5e6-96231b3b80d8
* Reintroduce VirtRegRewriter.Jakob Stoklund Olesen2012-06-08
| | | | | | | | | | | | | | | | | | OK, not really. We don't want to reintroduce the old rewriter hacks. This patch extracts virtual register rewriting as a separate pass that runs after the register allocator. This is possible now that CodeGen/Passes.cpp can configure the full optimizing register allocator pipeline. The rewriter pass uses register assignments in VirtRegMap to rewrite virtual registers to physical registers, and it inserts kill flags based on live intervals. These finalization steps are the same for the optimizing register allocators: RABasic, RAGreedy, and PBQP. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158244 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unused private fields found by clang's new -Wunused-private-field.Benjamin Kramer2012-06-06
| | | | | | | | There are some that I didn't remove this round because they looked like obvious stubs. There are dead variables in gtest too, they should be fixed upstream. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158090 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch all register list clients to the new MC*Iterator interface.Jakob Stoklund Olesen2012-06-01
| | | | | | | | | | | | | No functional change intended. Sorry for the churn. The iterator classes are supposed to help avoid giant commits like this one in the future. The TableGen-produced register lists are getting quite large, and it may be necessary to change the table representation. This makes it possible to do so without changing all clients (again). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157854 91177308-0d34-0410-b5e6-96231b3b80d8
* Small fix for the debug output from PBQP (PR12822).Patrik Hägglund2012-05-23
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157319 91177308-0d34-0410-b5e6-96231b3b80d8
* Allow LiveRangeEdit to be created with a NULL parent.Jakob Stoklund Olesen2012-05-19
| | | | | | The dead code elimination with callbacks is still useful. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157100 91177308-0d34-0410-b5e6-96231b3b80d8
* Moved LiveRangeEdit.h so that it can be called from other parts of the ↵Pete Cooper2012-04-02
| | | | | | backend, not just libCodeGen git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153906 91177308-0d34-0410-b5e6-96231b3b80d8
* Refactored the LiveRangeEdit interface so that MachineFunction, ↵Pete Cooper2012-04-02
| | | | | | TargetInstrInfo, MachineRegisterInfo, LiveIntervals, and VirtRegMap are all passed into the constructor and stored as members instead of passed in to each method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153903 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a debug option to dump PBQP graphs during register allocation.Lang Hames2012-03-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153483 91177308-0d34-0410-b5e6-96231b3b80d8
* Add support for register masks to PBQP.Lang Hames2012-03-23
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153341 91177308-0d34-0410-b5e6-96231b3b80d8
* Use uint16_t to store register overlaps to reduce static data.Craig Topper2012-03-04
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152001 91177308-0d34-0410-b5e6-96231b3b80d8
* Use uint16_t instead of unsigned to store registers in reg classes. Reduces ↵Craig Topper2012-03-04
| | | | | | static data size. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151998 91177308-0d34-0410-b5e6-96231b3b80d8
* Clear virtual registers after they are no longer referenced.Andrew Trick2012-02-21
| | | | | | | | | | | | | Passes after RegAlloc should be able to rely on MRI->getNumVirtRegs() == 0. This makes sharing code for pre/postRA passes more robust. Now, to check if a pass is running before the RA pipeline begins, use MRI->isSSA(). To check if a pass is running after the RA pipeline ends, use !MRI->getNumVirtRegs(). PEI resets virtual regs when it's done scavenging. PTX will either have to provide its own PEI pass or assign physregs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@151032 91177308-0d34-0410-b5e6-96231b3b80d8
* RegAlloc superpass: includes phi elimination, coalescing, and scheduling.Andrew Trick2012-02-10
| | | | | | | | | | | | | | | | Creates a configurable regalloc pipeline. Ensure specific llc options do what they say and nothing more: -reglloc=... has no effect other than selecting the allocator pass itself. This patch introduces a new umbrella flag, "-optimize-regalloc", to enable/disable the optimizing regalloc "superpass". This allows for example testing coalscing and scheduling under -O0 or vice-versa. When a CodeGen pass requires the MachineFunction to have a particular property, we need to explicitly define that property so it can be directly queried rather than naming a specific Pass. For example, to check for SSA, use MRI->isSSA, not addRequired<PHIElimination>. CodeGen transformation passes are never "required" as an analysis ProcessImplicitDefs does not require LiveVariables. We have a plan to massively simplify some of the early passes within the regalloc superpass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150226 91177308-0d34-0410-b5e6-96231b3b80d8
* whitespaceAndrew Trick2012-02-10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150225 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert assert(0) to llvm_unreachableCraig Topper2012-02-05
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149816 91177308-0d34-0410-b5e6-96231b3b80d8
* Freeze reserved registers before starting register allocation.Jakob Stoklund Olesen2012-01-05
| | | | | | | | | | | The register allocators don't currently support adding reserved registers while they are running. Extend the MRI API to keep track of the set of reserved registers when register allocation started. Target hooks like hasFP() and needsStackRealignment() can look at this set to avoid reserving more registers during register allocation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147577 91177308-0d34-0410-b5e6-96231b3b80d8
* Kill off the LoopSplitter. It's not being used or maintained.Lang Hames2011-12-06
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145897 91177308-0d34-0410-b5e6-96231b3b80d8
* Update PBQP's analysis usage to reflect the requirements of the inline spiller.Lang Hames2011-12-06
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145893 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-17 01:54:07 +0000