summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen
Commit message (Collapse)AuthorAgeFilesLines
* Avoid dereferencing off the beginning of lists.Evan Cheng2011-11-141-7/+4
| | | | llvm-svn: 144569
* At -O0, multiple uses of a virtual registers in the same BB are being markedEvan Cheng2011-11-141-1/+2
| | | | | | | | "kill". This looks like a bug upstream. Since that's going to take some time to understand, loosen the assertion and disable the optimization when multiple kills are seen. llvm-svn: 144568
* Teach two-address pass to re-schedule two-address instructions (or the killEvan Cheng2011-11-141-19/+356
| | | | | | | | | instructions of the two-address operands) in order to avoid inserting copies. This fixes the few regressions introduced when the two-address hack was disabled (without regressing the improvements). rdar://10422688 llvm-svn: 144559
* Fix early-clobber handling in shrinkToUses.Jakob Stoklund Olesen2011-11-141-12/+8
| | | | | | | | I broke this in r144515, it affected most ARM testers. <rdar://problem/10441389> llvm-svn: 144547
* It helps to deallocate memory as well as allocate it. =] This actuallyChandler Carruth2011-11-141-0/+1
| | | | | | | | cleans up all the chains allocated during the processing of each function so that for very large inputs we don't just grow memory usage without bound. llvm-svn: 144533
* Remove an over-eager assert that was firing on one of the ARM regressionChandler Carruth2011-11-141-3/+6
| | | | | | | | | | | | | | tests when I forcibly enabled block placement. It is apparantly possible for an unanalyzable block to fallthrough to a non-loop block. I don't actually beleive this is correct, I believe that 'canFallThrough' is returning true needlessly for the code construct, and I've left a bit of a FIXME on the verification code to try to track down why this is coming up. Anyways, removing the assert doesn't degrade the correctness of the algorithm. llvm-svn: 144532
* Begin chipping away at one of the biggest quadratic-ish behaviors inChandler Carruth2011-11-141-2/+26
| | | | | | | | | | | | | | this pass. We're leaving already merged blocks on the worklist, and scanning them again and again only to determine each time through that indeed they aren't viable. We can instead remove them once we're going to have to scan the worklist. This is the easy way to implement removing them. If this remains on the profile (as I somewhat suspect it will), we can get a lot more clever here, as the worklist's order is essentially irrelevant. We can use swapping and fold the two loops to reduce overhead even when there are many blocks on the worklist but only a few of them are removed. llvm-svn: 144531
* Under the hood, MBPI is doing a linear scan of every successor everyChandler Carruth2011-11-141-4/+13
| | | | | | | | | | | | | | | | | | time it is queried to compute the probability of a single successor. This makes computing the probability of every successor of a block in sequence... really really slow. ;] This switches to a linear walk of the successors rather than a quadratic one. One of several quadratic behaviors slowing this pass down. I'm not really thrilled with moving the sum code into the public interface of MBPI, but I don't (at the moment) have ideas for a better interface. My direction I'm thinking in for a better interface is to have MBPI actually retain much more state and make *all* of these queries cheap. That's a lot of work, and would require invasive changes. Until then, this seems like the least bad (ie, least quadratic) solution. Suggestions welcome. llvm-svn: 144530
* Reuse the logic in getEdgeProbability within getHotSucc in order toChandler Carruth2011-11-141-11/+3
| | | | | | | | | | correctly handle blocks whose successor weights sum to more than UINT32_MAX. This is slightly less efficient, but the entire thing is already linear on the number of successors. Calling it within any hot routine is a mistake, and indeed no one is calling it. It also simplifies the code. llvm-svn: 144527
* Fix an overflow bug in MachineBranchProbabilityInfo. This pass relied onChandler Carruth2011-11-141-10/+26
| | | | | | | | | | | | | | | | | | | | | | | | | the sum of the edge weights not overflowing uint32, and crashed when they did. This is generally safe as BranchProbabilityInfo tries to provide this guarantee. However, the CFG can get modified during codegen in a way that grows the *sum* of the edge weights. This doesn't seem unreasonable (imagine just adding more blocks all with the default weight of 16), but it is hard to come up with a case that actually triggers 32-bit overflow. Fortuately, the single-source GCC build is good at this. The solution isn't very pretty, but its no worse than the previous code. We're already summing all of the edge weights on each query, we can sum them, check for an overflow, compute a scale, and sum them again. I've included a *greatly* reduced test case out of the GCC source that triggers it. It's a pretty lame test, as it clearly is just barely triggering the overflow. I'd like to have something that is much more definitive, but I don't understand the fundamental pattern that triggers an explosion in the edge weight sums. The buggy code is duplicated within this file. I'll colapse them into a single implementation in a subsequent commit. llvm-svn: 144526
* Use getVNInfoBefore() when it makes sense.Jakob Stoklund Olesen2011-11-144-8/+7
| | | | llvm-svn: 144517
* Teach machine block placement to cope with unnatural loops. These don'tChandler Carruth2011-11-141-21/+60
| | | | | | | | | | | | | | | | | | get loop info structures associated with them, and so we need some way to make forward progress selecting and placing basic blocks. The technique used here is pretty brutal -- it just scans the list of blocks looking for the first unplaced candidate. It keeps placing blocks like this until the CFG becomes tractable. The cost is somewhat unfortunate, it requires allocating a vector of all basic block pointers eagerly. I have some ideas about how to simplify and optimize this, but I'm trying to get the logic correct first. Thanks to Benjamin Kramer for the reduced test case out of GCC. Sadly there are other bugs that GCC is tickling that I'm reducing and working on now. llvm-svn: 144516
* Use kill slots instead of the previous slot in shrinkToUses.Jakob Stoklund Olesen2011-11-131-13/+14
| | | | | | It's more natural to use the actual end points. llvm-svn: 144515
* Cleanup some 80-columns violations and poor formatting. These snuck byChandler Carruth2011-11-131-5/+9
| | | | | | when I was reading through the code for style. llvm-svn: 144513
* Terminate all dead defs at the dead slot instead of the 'next' slot.Jakob Stoklund Olesen2011-11-133-8/+8
| | | | | | | | | | | | | | | | | | | This makes no difference for normal defs, but early clobber dead defs now look like: [Slot_EarlyClobber; Slot_Dead) instead of: [Slot_EarlyClobber; Slot_Register). Live ranges for normal dead defs look like: [Slot_Register; Slot_Dead) as before. llvm-svn: 144512
* Simplify early clobber slots a bit.Jakob Stoklund Olesen2011-11-131-12/+3
| | | | llvm-svn: 144507
* Enhance the assertion mechanisms in place to make it easier to catchChandler Carruth2011-11-131-5/+28
| | | | | | | | when we fail to place all the blocks of a loop. Currently this is happening for unnatural loops, and this logic helps more immediately point to the problem. llvm-svn: 144504
* Rename SlotIndexes to match how they are used.Jakob Stoklund Olesen2011-11-1313-103/+107
| | | | | | | | | | | | | | | | | | | | The old naming scheme (load/use/def/store) can be traced back to an old linear scan article, but the names don't match how slots are actually used. The load and store slots are not needed after the deferred spill code insertion framework was deleted. The use and def slots don't make any sense because we are using half-open intervals as is customary in C code, but the names suggest closed intervals. In reality, these slots were used to distinguish early-clobber defs from normal defs. The new naming scheme also has 4 slots, but the names match how the slots are really used. This is a purely mechanical renaming, but some of the code makes a lot more sense now. llvm-svn: 144503
* Teach MBP to force-merge layout successors for blocks with unanalyzableChandler Carruth2011-11-131-3/+20
| | | | | | | | | | | | | | | | | branches that also may involve fallthrough. In the case of blocks with no fallthrough, we can still re-order the blocks profitably. For example instruction decoding will in some cases continue past an indirect jump, making laying out its most likely successor there profitable. Note, no test case. I don't know how to write a test case that exercises this logic, but it matches the described desired semantics in discussions with Jakob and others. If anyone has a nice example of IR that will trigger this, that would be lovely. Also note, there are still assertion failures in real world code with this. I'm digging into those next, now that I know this isn't the cause. llvm-svn: 144499
* Hoist another gross nested loop into a helper method.Chandler Carruth2011-11-131-23/+44
| | | | llvm-svn: 144498
* Add a missing doxygen comment for a helper method.Chandler Carruth2011-11-131-0/+6
| | | | llvm-svn: 144497
* Hoist a nested loop into its own method.Chandler Carruth2011-11-131-33/+53
| | | | llvm-svn: 144496
* Rewrite #3 of machine block placement. This is based somewhat on theChandler Carruth2011-11-131-139/+256
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | second algorithm, but only loosely. It is more heavily based on the last discussion I had with Andy. It continues to walk from the inner-most loop outward, but there is a key difference. With this algorithm we ensure that as we visit each loop, the entire loop is merged into a single chain. At the end, the entire function is treated as a "loop", and merged into a single chain. This chain forms the desired sequence of blocks within the function. Switching to a single algorithm removes my biggest problem with the previous approaches -- they had different behavior depending on which system triggered the layout. Now there is exactly one algorithm and one basis for the decision making. The other key difference is how the chain is formed. This is based heavily on the idea Andy mentioned of keeping a worklist of blocks that are viable layout successors based on the CFG. Having this set allows us to consistently select the best layout successor for each block. It is expensive though. The code here remains very rough. There is a lot that needs to be done to clean up the code, and to make the runtime cost of this pass much lower. Very much WIP, but this was a giant chunk of code and I'd rather folks see it sooner than later. Everything remains behind a flag of course. I've added a couple of tests to exercise the issues that this iteration was motivated by: loop structure preservation. I've also fixed one test that was exhibiting the broken behavior of the previous version. llvm-svn: 144495
* Prune more RALinScan. RALinScan was also here!NAKAMURA Takumi2011-11-131-1/+0
| | | | llvm-svn: 144487
* More dead code elimination in VirtRegMap.Jakob Stoklund Olesen2011-11-132-26/+0
| | | | | | This thing is looking a lot like a virtual register map now. llvm-svn: 144486
* Stop tracking spill slot uses in VirtRegMap.Jakob Stoklund Olesen2011-11-136-82/+2
| | | | | | | Nobody cared, StackSlotColoring scans the instructions to find used stack slots. llvm-svn: 144485
* Remove dead code and data from VirtRegMap.Jakob Stoklund Olesen2011-11-132-324/+2
| | | | | | | Most of this stuff was supporting the old deferred spill code insertion mechanism. Modern spillers just edit machine code in place. llvm-svn: 144484
* Stop tracking unused registers in VirtRegMap.Jakob Stoklund Olesen2011-11-133-82/+3
| | | | | | | The information was only used by the register allocator in StackSlotColoring. llvm-svn: 144482
* Remove the -color-ss-with-regs option.Jakob Stoklund Olesen2011-11-131-306/+2
| | | | | | | | | It was off by default. The new register allocators don't have the problems that made it necessary to reallocate registers during stack slot coloring. llvm-svn: 144481
* Delete VirtRegRewriter.Jakob Stoklund Olesen2011-11-133-2666/+0
| | | | | | And there was much rejoicing. llvm-svn: 144480
* Switch PBQP to VRM's trivial rewriter.Jakob Stoklund Olesen2011-11-131-4/+1
| | | | | | The very complicated VirtRegRewriter is going away. llvm-svn: 144479
* Delete the old spilling framework from LiveIntervalAnalysis.Jakob Stoklund Olesen2011-11-121-1193/+0
| | | | | | This is dead code, all register allocators use InlineSpiller. llvm-svn: 144478
* Delete the 'standard' spiller with used the old spilling framework.Jakob Stoklund Olesen2011-11-121-45/+2
| | | | | | The current register allocators all use the inline spiller. llvm-svn: 144477
* Switch PBQP to the modern InlineSpiller framework.Jakob Stoklund Olesen2011-11-121-40/+11
| | | | | | | | | | | It is worth noting that the old spiller would split live ranges around basic blocks. The new spiller doesn't do that. PBQP should do its own live range splitting with SplitEditor::splitSingleBlock() if desired. See RAGreedy::tryBlockSplit(). llvm-svn: 144476
* Delete the linear scan register allocator.Jakob Stoklund Olesen2011-11-123-1549/+0
| | | | | | | | | RegAllocGreedy has been the default for six months now. Deleting RegAllocLinearScan makes it possible to also delete VirtRegRewriter and clean up the spiller code. llvm-svn: 144475
* The dwarf standard says that the only differences between a out-of-lineRafael Espindola2011-11-121-0/+7
| | | | | | | | | | | | | | instance and a concrete inlined instance are the use of DW_TAG_subprogram instead of DW_TAG_inlined_subroutine and the who owns the tree. We were also omitting DW_AT_inline from the abstract roots. To fix this, make sure we mark abstract instance roots with DW_AT_inline even when we have only out-of-line instances referring to them with DW_AT_abstract_origin. FileCheck is not a very good tool for tests like this, maybe we should add a -verify mode to llvm-dwarfdump. llvm-svn: 144441
* Don't try to form pre/post-indexed loads/stores until after LegalizeDAG ↵Eli Friedman2011-11-122-11/+11
| | | | | | runs. Fixes PR11029. llvm-svn: 144438
* Some cleanup and bulletproofing for node replacement in LegalizeDAG. To ↵Eli Friedman2011-11-111-57/+59
| | | | | | | | maintain LegalizeDAG invariants, whenever we a node is replaced, we must attempt to delete it, and if it still has uses after it is replaced (which can happen in rare cases due to CSE), we must revisit it. llvm-svn: 144432
* Add a custom safepoint method, in order for language implementers to decide ↵Nicolas Geoffray2011-11-111-2/+15
| | | | | | which machine instruction gets to be a safepoint. llvm-svn: 144399
* Initialize variable.Eric Christopher2011-11-111-1/+2
| | | | llvm-svn: 144360
* If we have a DIE with an AT_specification use that instead of the normalEric Christopher2011-11-111-7/+10
| | | | | | addr DIE when adding to the dwarf accelerator tables. llvm-svn: 144354
* Check in getOrCreateSubprogramDIE if a declaration exists and if so outputRafael Espindola2011-11-102-13/+12
| | | | | | | | it first. This is a more general fix to pr11300. llvm-svn: 144324
* Make types and namespaces take multiple DIEs for the accelerator tablesEric Christopher2011-11-102-14/+24
| | | | | | as well. llvm-svn: 144319
* Move type handling to make sure we get all created types that aren'tEric Christopher2011-11-101-7/+5
| | | | | | forward decls and have names into the dwarf accelerator types table. llvm-svn: 144306
* Rework adding function names to the dwarf accelerator tables, allowEric Christopher2011-11-103-71/+86
| | | | | | multiple dies per function and support C++ basenames. llvm-svn: 144304
* Use a bigger hammer to fix PR11314 by disabling the "forcing two-addressEvan Cheng2011-11-101-1/+5
| | | | | | | | | | | | | | | | instruction lower optimization" in the pre-RA scheduler. The optimization, rather the hack, was done before MI use-list was available. Now we should be able to implement it in a better way, perhaps in the two-address pass until a MI scheduler is available. Now that the scheduler has to backtrack to handle call sequences. Adding artificial scheduling constraints is just not safe. Furthermore, the hack is not taking all the other scheduling decisions into consideration so it's just as likely to pessimize code. So I view disabling this optimization goodness regardless of PR11314. llvm-svn: 144267
* Strip old implicit operands after foldMemoryOperand.Jakob Stoklund Olesen2011-11-101-2/+19
| | | | | | | | | | | | The TII.foldMemoryOperand hook preserves implicit operands from the original instruction. This is not what we want when those implicit operands refer to the register being spilled. Implicit operands referring to other registers are preserved. This fixes PR11347. llvm-svn: 144247
* Add check so we don't try to perform an impossible transformation. Fixes ↵Eli Friedman2011-11-091-1/+2
| | | | | | issue from PR11319. llvm-svn: 144216
* Add comments.Benjamin Kramer2011-11-091-1/+2
| | | | llvm-svn: 144194
* Speculatively revert commit 144124 (djg) in the hope that the 32 bitDuncan Sands2011-11-091-13/+3
| | | | | | | | | | | | | | dragonegg self-host buildbot will recover (it is complaining about object files differing between different build stages). Original commit message: Add a hack to the scheduler to disable pseudo-two-address dependencies in basic blocks containing calls. This works around a problem in which these artificial dependencies can get tied up in calling seqeunce scheduling in a way that makes the graph unschedulable with the current approach of using artificial physical register dependencies for calling sequences. This fixes PR11314. llvm-svn: 144188
OpenPOWER on IntegriCloud