summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocPBQP.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Remove unnecessary TargetMachine.h includes.Eric Christopher2014-10-141-1/+0
| | | | llvm-svn: 219672
* [PBQP] Replace PBQPBuilder with composable constraints (PBQPRAConstraint).Lang Hames2014-10-091-355/+307
| | | | | | | | | | | | | | | | This patch removes the PBQPBuilder class and its subclasses and replaces them with a composable constraints class: PBQPRAConstraint. This allows constraints that are only required for optimisation (e.g. coalescing, soft pairing) to be mixed and matched. This patch also introduces support for target writers to supply custom constraints for their targets by overriding a TargetSubtargetInfo method: std::unique_ptr<PBQPRAConstraints> getCustomPBQPConstraints() const; This patch should have no effect on allocations. llvm-svn: 219421
* unique_ptrify PBQPBuilder::buildDavid Blaikie2014-09-021-13/+13
| | | | llvm-svn: 216918
* [PBQP] Only output debug information when requestedArnaud A. de Grandmaison2014-08-281-2/+2
| | | | llvm-svn: 216660
* Modernize raw_fd_ostream's constructor a bit.Rafael Espindola2014-08-251-2/+2
| | | | | | | | | | Take a StringRef instead of a "const char *". Take a "std::error_code &" instead of a "std::string &" for error. A create static method would be even better, but this patch is already a bit too big. llvm-svn: 216393
* Have MachineFunction cache a pointer to the subtarget to make lookupsEric Christopher2014-08-051-2/+1
| | | | | | | | | | | shorter/easier and have the DAG use that to do the same lookup. This can be used in the future for TargetMachine based caching lookups from the MachineFunction easily. Update the MIPS subtarget switching machinery to update this pointer at the same time it runs. llvm-svn: 214838
* Remove the TargetMachine forwards for TargetSubtargetInfo basedEric Christopher2014-08-041-4/+6
| | | | | | information and update all callers. No functional change. llvm-svn: 214781
* Sure up ownership passing of the PBQPBuilder by passing unique_ptrs by value ↵David Blaikie2014-07-191-7/+7
| | | | | | | | | rather than lvalue reference. Also removes an unnecessary '.release()' that should've been a std::move anyway. (I'm on a hunt for '.release()' calls) llvm-svn: 213464
* Convert more loops to range-based equivalentsAlexey Samsonov2014-04-301-12/+4
| | | | llvm-svn: 207714
* raw_ostream: Forward declare OpenFlags and include FileSystem.h only where ↵Benjamin Kramer2014-04-291-0/+1
| | | | | | necessary. llvm-svn: 207593
* [Modules] Remove potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-2/+2
| | | | | | | | | | | | 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. llvm-svn: 206837
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-141-1/+1
| | | | | | instead of comparing to nullptr. llvm-svn: 206142
* Make consistent use of MCPhysReg instead of uint16_t throughout the tree.Craig Topper2014-04-041-1/+1
| | | | llvm-svn: 205610
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-071-3/+3
| | | | | | class. llvm-svn: 203220
* Replace OwningPtr<T> with std::unique_ptr<T>.Ahmed Charles2014-03-061-13/+11
| | | | | | | | | | This compiles with no changes to clang/lld/lldb with MSVC and includes overloads to various functions which are used by those projects and llvm which have OwningPtr's as parameters. This should allow out of tree projects some time to move. There are also no changes to libs/Target, which should help out of tree targets have time to move, if necessary. llvm-svn: 203083
* [C++11] Replace OwningPtr::take() with OwningPtr::release().Ahmed Charles2014-03-051-3/+3
| | | | llvm-svn: 202957
* Re-apply r202551, which introduced new PBQP solver.Lang Hames2014-03-031-38/+38
| | | | llvm-svn: 202735
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-2/+2
| | | | | | Remove the old functions. llvm-svn: 202636
* Jumped the gun with r202551 and broke some bots that weren't yet C++11ified.Lang Hames2014-02-281-38/+38
| | | | | | Reverting until the C++11 switch is complete. llvm-svn: 202554
* New PBQP solver, and updates to the PBQP graph.Lang Hames2014-02-281-38/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The previous PBQP solver was very robust but consumed a lot of memory, performed a lot of redundant computation, and contained some unnecessarily tight coupling that prevented experimentation with novel solution techniques. This new solver is an attempt to address these shortcomings. Important/interesting changes: 1) The domain-independent PBQP solver class, HeuristicSolverImpl, is gone. It is replaced by a register allocation specific solver, PBQP::RegAlloc::Solver (see RegAllocSolver.h). The optimal reduction rules and the backpropagation algorithm have been extracted into stand-alone functions (see ReductionRules.h), which can be used to build domain specific PBQP solvers. This provides many more opportunities for domain-specific knowledge to inform the PBQP solvers' decisions. In theory this should allow us to generate better solutions. In practice, we can at least test out ideas now. As a side benefit, I believe the new solver is more readable than the old one. 2) The solver type is now a template parameter of the PBQP graph. This allows the graph to notify the solver of any modifications made (e.g. by domain independent rules) without the overhead of a virtual call. It also allows the solver to supply policy information to the graph (see below). 3) Significantly reduced memory overhead. Memory management policy is now an explicit property of the PBQP graph (via the CostAllocator typedef on the graph's solver template argument). Because PBQP graphs for register allocation tend to contain many redundant instances of single values (E.g. the value representing an interference constraint between GPRs), the new RASolver class uses a uniquing scheme. This massively reduces memory consumption for large register allocation problems. For example, looking at the largest interference graph in each of the SPEC2006 benchmarks (the largest graph will always set the memory consumption high-water mark for PBQP), the average memory reduction for the PBQP costs was 400x. That's times, not percent. The highest was 1400x. Yikes. So - this is fixed. "PBQP: No longer feasting upon every last byte of your RAM". Minor details: - Fully C++11'd. Never copy-construct another vector/matrix! - Cute tricks with cost metadata: Metadata that is derived solely from cost matrices/vectors is attached directly to the cost instances themselves. That way if you unique the costs you never have to recompute the metadata. 400x less memory means 400x less cost metadata (re)computation. Special thanks to Arnaud de Grandmaison, who has been the source of much encouragement, and of many very useful test cases. This new solver forms the basis for future work, of which there's plenty to do. I will be adding TODO notes shortly. - Lang. llvm-svn: 202551
* Replace the F_Binary flag with a F_Text one.Rafael Espindola2014-02-241-1/+1
| | | | | | | | | After this I will set the default back to F_None. The advantage is that before this patch forgetting to set F_Binary would corrupt a file on windows. Forgetting to set F_Text produces one that cannot be read in notepad, which is a better failure mode :-) llvm-svn: 202052
* Don't make F_None the default.Rafael Espindola2014-02-241-1/+1
| | | | | | This will make it easier to switch the default to being binary files. llvm-svn: 202042
* [block-freq] Refactor LiveInterals::getSpillWeight to use the new ↵Michael Gottesman2013-12-141-2/+1
| | | | | | | | | | | | | | | | | | | | | | | MachineBlockFrequencyInfo methods. This is slightly more interesting than the previous batch of changes. Specifically: 1. We refactor getSpillWeight to take a MachineBlockFrequencyInfo (MBFI) object. This enables us to completely encapsulate the actual manner we use the MachineBlockFrequencyInfo to get our spill weights. This yields cleaner code since one does not need to fetch the actual block frequency before getting the spill weight if all one wants it the spill weight. It also gives us access to entry frequency which we need for our computation. 2. Instead of having getSpillWeight take a MachineBasicBlock (as one might think) to look up the block frequency via the MBFI object, we instead take in a MachineInstr object. The reason for this is that the method is supposed to return the spill weight for an instruction according to the comments around the function. llvm-svn: 197296
* CalcSpillWeights: give a better describing name to calculateSpillWeightsArnaud A. de Grandmaison2013-11-111-1/+2
| | | | | | | | Besides, this relates it more obviously to the VirtRegAuxInfo::calculateSpillWeightAndHint. No functionnal change. llvm-svn: 194404
* CalculateSpillWeights does not need to be a passArnaud A. de Grandmaison2013-11-101-2/+2
| | | | | | | | | | 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. llvm-svn: 194356
* Re-apply r194300 with fixes for warnings.Lang Hames2013-11-091-14/+14
| | | | llvm-svn: 194311
* Revert r194300 which broke the build.Nick Lewycky2013-11-091-14/+14
| | | | llvm-svn: 194308
* Rewrite the PBQP graph data structure.Lang Hames2013-11-091-14/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 194300
* Revert "CalculateSpillWeights does not need to be a pass"Arnaud A. de Grandmaison2013-11-081-2/+2
| | | | | | Temporarily revert my previous commit until I understand why it breaks 3 target tests. llvm-svn: 194272
* CalculateSpillWeights does not need to be a passArnaud A. de Grandmaison2013-11-081-2/+2
| | | | | | | | | | 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. llvm-svn: 194269
* Track new virtual registers by register number.Mark Lacey2013-08-141-4/+5
| | | | | | | | | | 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. llvm-svn: 188434
* Make PBQP require/preserve MachineLoopInfo - the spiller requires it.Lang Hames2013-07-011-0/+3
| | | | llvm-svn: 185378
* Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.Benjamin Kramer2013-06-171-11/+10
| | | | | | | | | | | | | | | | | | 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). llvm-svn: 184105
* Replace uses of the deprecated std::auto_ptr with OwningPtr.Andy Gibbs2013-04-151-23/+22
| | | | | | 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. llvm-svn: 179520
* Revert broken pieces of r179373.Benjamin Kramer2013-04-121-16/+16
| | | | | | You can't copy an OwningPtr, and move semantics aren't available in C++98. llvm-svn: 179374
* Replace uses of the deprecated std::auto_ptr with OwningPtr.Andy Gibbs2013-04-121-16/+16
| | | | llvm-svn: 179373
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-1/+1
| | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 171366
* Use MRI::getSimpleHint() instead of getRegAllocPref() in remaining cases.Jakob Stoklund Olesen2012-12-041-1/+1
| | | | | | | | | 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 llvm-svn: 169188
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-4/+4
| | | | | | | | | | | | | | | | | 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. =] llvm-svn: 169131
* Make the LiveRegMatrix analysis available to targets.Jakob Stoklund Olesen2012-11-281-1/+1
| | | | | | | | | | | 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. llvm-svn: 168806
* Revert r168630, r168631, and r168633 as these are causing nightly test failures.Chad Rosier2012-11-281-0/+2
| | | | llvm-svn: 168751
* Now that the X86 Maximal Stack Alignment Check pass has been removed (i.e.,Chad Rosier2012-11-261-2/+0
| | | | | | | | | 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 llvm-svn: 168631
* Remove unused typedef.Lang Hames2012-10-291-1/+0
| | | | llvm-svn: 166910
* Remove LIS::isAllocatable() and isReserved() helpers.Jakob Stoklund Olesen2012-10-151-1/+1
| | | | | | All callers can simply use the corresponding MRI functions. llvm-svn: 165985
* Switch most getReservedRegs() clients to the MRI equivalent.Jakob Stoklund Olesen2012-10-151-3/+1
| | | | | | | Using the cached bit vector in MRI avoids comstantly allocating and recomputing the reserved register bit vector. llvm-svn: 165983
* My earlier "fix" for PBQP (see r165201) was incorrect. The real issue was thatLang Hames2012-10-101-2/+2
| | | | | | | | checkRegMaskInterference only initializes the bitmask on the first interference. This fixes PR14027 and (re)fixes PR13945. llvm-svn: 165608
* Fix reg mask slot test, and preserve LiveIntervals and VirtRegMap in the PBQPLang Hames2012-10-041-1/+3
| | | | | | allocator. Fixes PR13945. llvm-svn: 165201
* Remove unused typedefs gcc4.8 warns about.Roman Divacky2012-09-051-1/+0
| | | | llvm-svn: 163225
* Add a getName function to MachineFunction. Use it in places that previously ↵Craig Topper2012-08-221-2/+3
| | | | | | did getFunction()->getName(). Remove includes of Function.h that are no longer needed. llvm-svn: 162347
* Remove LiveIntervals::trackingRegUnits().Jakob Stoklund Olesen2012-06-221-51/+7
| | | | | | | | | With regunit liveness permanently enabled, this function would always return true. Also remove now obsolete code for checking physreg interference. llvm-svn: 159006
OpenPOWER on IntegriCloud