1914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen//===-------- InlineSpiller.cpp - Insert spills and restores inline -------===// 2914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen// 3914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 4914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen// 5914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 6914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 7914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen// 8914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 9914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen// 10914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen// The inline spiller modifies the machine function directly instead of 11914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen// inserting spills and restores in VirtRegMap. 12914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen// 13914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 14914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 15376dcbd6c2c7adb8281f89d045b307eee7bd682aJakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 16914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen#include "Spiller.h" 17914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen#include "VirtRegMap.h" 18e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 191ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen#include "llvm/ADT/TinyPtrVector.h" 20e93198af07517b92f276192c974ce3a6006ce998Jakob Stoklund Olesen#include "llvm/Analysis/AliasAnalysis.h" 21914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 22789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 230a12b801b546269b87c3806c6d4606cf2b287daaJakob Stoklund Olesen#include "llvm/CodeGen/LiveStackAnalysis.h" 2413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 2566c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen#include "llvm/CodeGen/MachineInstrBundle.h" 26914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFrameInfo.h" 27914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunction.h" 2813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 29914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 30914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 31914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 32b9edad0163296e02f7b4dbbc22b50615dede357cJakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 33914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen#include "llvm/Support/Debug.h" 34914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 35914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 36914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesenusing namespace llvm; 37914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 38e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumSpilledRanges, "Number of spilled live ranges"); 3979c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund OlesenSTATISTIC(NumSnippets, "Number of spilled snippets"); 40e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumSpills, "Number of spills inserted"); 4179c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund OlesenSTATISTIC(NumSpillsRemoved, "Number of spills removed"); 42e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumReloads, "Number of reloads inserted"); 4379c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund OlesenSTATISTIC(NumReloadsRemoved, "Number of reloads removed"); 44e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumFolded, "Number of folded stack accesses"); 45e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumFoldedLoads, "Number of folded loads"); 46e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund OlesenSTATISTIC(NumRemats, "Number of rematerialized defs for spilling"); 4779c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund OlesenSTATISTIC(NumOmitReloadSpill, "Number of omitted spills of reloads"); 4879c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund OlesenSTATISTIC(NumHoists, "Number of hoisted spills"); 49e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen 50b9edad0163296e02f7b4dbbc22b50615dede357cJakob Stoklund Olesenstatic cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden, 51b9edad0163296e02f7b4dbbc22b50615dede357cJakob Stoklund Olesen cl::desc("Disable inline spill hoisting")); 52b9edad0163296e02f7b4dbbc22b50615dede357cJakob Stoklund Olesen 53914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesennamespace { 54914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesenclass InlineSpiller : public Spiller { 55766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen MachineFunctionPass &Pass; 56766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen MachineFunction &MF; 57766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen LiveIntervals &LIS; 58766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen LiveStacks &LSS; 59766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen AliasAnalysis *AA; 6013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen MachineDominatorTree &MDT; 6113ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen MachineLoopInfo &Loops; 62766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen VirtRegMap &VRM; 63766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen MachineFrameInfo &MFI; 64766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen MachineRegisterInfo &MRI; 65766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen const TargetInstrInfo &TII; 66766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen const TargetRegisterInfo &TRI; 679e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen 689e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen // Variables that are valid during spill(), but used by multiple methods. 69766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen LiveRangeEdit *Edit; 70e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen LiveInterval *StackInt; 71766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen int StackSlot; 7213ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen unsigned Original; 73914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 74766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen // All registers to spill to StackSlot, including the main register. 7510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen SmallVector<unsigned, 8> RegsToSpill; 7610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 7710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // All COPY instructions to/from snippets. 7810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // They are ignored since both operands refer to the same stack slot. 7910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen SmallPtrSet<MachineInstr*, 8> SnippetCopies; 8010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 81080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen // Values that failed to remat at some point. 82766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen SmallPtrSet<VNInfo*, 8> UsedValues; 838de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 841ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesenpublic: 8513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // Information about a value that was defined by a copy from a sibling 8613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // register. 8713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen struct SibValueInfo { 8813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // True when all reaching defs were reloads: No spill is necessary. 8913ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen bool AllDefsAreReloads; 9013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 911ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // True when value is defined by an original PHI not from splitting. 921ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen bool DefByOrigPHI; 931ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 9469cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen // True when the COPY defining this value killed its source. 9569cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen bool KillsSource; 9669cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen 9713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // The preferred register to spill. 9813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen unsigned SpillReg; 9913ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 10013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // The value of SpillReg that should be spilled. 10113ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen VNInfo *SpillVNI; 10213ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 1031ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // The block where SpillVNI should be spilled. Currently, this must be the 1041ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // block containing SpillVNI->def. 1051ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen MachineBasicBlock *SpillMBB; 1061ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 10713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // A defining instruction that is not a sibling copy or a reload, or NULL. 10813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // This can be used as a template for rematerialization. 10913ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen MachineInstr *DefMI; 11013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 1111ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // List of values that depend on this one. These values are actually the 1121ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // same, but live range splitting has placed them in different registers, 1131ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // or SSA update needed to insert PHI-defs to preserve SSA form. This is 1141ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // copies of the current value and phi-kills. Usually only phi-kills cause 1151ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // more than one dependent value. 1161ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen TinyPtrVector<VNInfo*> Deps; 1171ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 11813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen SibValueInfo(unsigned Reg, VNInfo *VNI) 11969cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen : AllDefsAreReloads(true), DefByOrigPHI(false), KillsSource(false), 1201ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SpillReg(Reg), SpillVNI(VNI), SpillMBB(0), DefMI(0) {} 1211ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 1221ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Returns true when a def has been found. 1231ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen bool hasDef() const { return DefByOrigPHI || DefMI; } 12413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen }; 12513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 1261ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesenprivate: 12713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // Values in RegsToSpill defined by sibling copies. 1282a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen typedef DenseMap<VNInfo*, SibValueInfo> SibValueMap; 1292a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen SibValueMap SibValues; 1302a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 1312a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Dead defs generated during spilling. 1322a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen SmallVector<MachineInstr*, 8> DeadDefs; 13313ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 134914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen ~InlineSpiller() {} 135914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 136914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesenpublic: 137f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen InlineSpiller(MachineFunctionPass &pass, 138f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen MachineFunction &mf, 139f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen VirtRegMap &vrm) 140766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen : Pass(pass), 141766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen MF(mf), 142766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen LIS(pass.getAnalysis<LiveIntervals>()), 143766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen LSS(pass.getAnalysis<LiveStacks>()), 144766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen AA(&pass.getAnalysis<AliasAnalysis>()), 14513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen MDT(pass.getAnalysis<MachineDominatorTree>()), 14613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen Loops(pass.getAnalysis<MachineLoopInfo>()), 147766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen VRM(vrm), 148766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen MFI(*mf.getFrameInfo()), 149766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen MRI(mf.getRegInfo()), 150766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen TII(*mf.getTarget().getInstrInfo()), 151766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen TRI(*mf.getTarget().getRegisterInfo()) {} 152914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 153a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen void spill(LiveRangeEdit &); 154a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 1558de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesenprivate: 15610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen bool isSnippet(const LiveInterval &SnipLI); 15710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen void collectRegsToSpill(); 15810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 1592a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen bool isRegToSpill(unsigned Reg) { 1602a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen return std::find(RegsToSpill.begin(), 1612a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen RegsToSpill.end(), Reg) != RegsToSpill.end(); 1622a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen } 1632a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 1642a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen bool isSibling(unsigned Reg); 1652ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*); 1661ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen void propagateSiblingValue(SibValueMap::iterator, VNInfo *VNI = 0); 16713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen void analyzeSiblingValues(); 16813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 1692a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen bool hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI); 17001a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesen void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI); 1712a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 1722ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen void markValueUsed(LiveInterval*, VNInfo*); 1732ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen bool reMaterializeFor(LiveInterval&, MachineBasicBlock::iterator MI); 1748de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen void reMaterializeAll(); 1758de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 17610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen bool coalesceStackAccess(MachineInstr *MI, unsigned Reg); 17766c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr*, unsigned> >, 17883d1ba572815c92a74817cc68e2bb48c59a87b5dJakob Stoklund Olesen MachineInstr *LoadMI = 0); 1795d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen void insertReload(LiveInterval &NewLI, SlotIndex, 1805d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen MachineBasicBlock::iterator MI); 18110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen void insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI, 1825d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen SlotIndex, MachineBasicBlock::iterator MI); 18310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 18410a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen void spillAroundUses(unsigned Reg); 1856094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen void spillAll(); 186914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen}; 187914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen} 188914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 189914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesennamespace llvm { 190f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund OlesenSpiller *createInlineSpiller(MachineFunctionPass &pass, 191f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen MachineFunction &mf, 192f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen VirtRegMap &vrm) { 193f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen return new InlineSpiller(pass, mf, vrm); 194914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen} 195914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen} 196914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 19710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 19810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen// Snippets 19910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 20010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 20110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen// When spilling a virtual register, we also spill any snippets it is connected 20210a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen// to. The snippets are small live ranges that only have a single real use, 20310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen// leftovers from live range splitting. Spilling them enables memory operand 20410a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen// folding or tightens the live range around the single use. 20510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen// 20610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen// This minimizes register pressure and maximizes the store-to-load distance for 20710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen// spill slots which can be important in tight loops. 20810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 20910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen/// isFullCopyOf - If MI is a COPY to or from Reg, return the other register, 21010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen/// otherwise return 0. 21110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesenstatic unsigned isFullCopyOf(const MachineInstr *MI, unsigned Reg) { 212cfe5254cd34d9414d9f6b8aa02dc1239d71a703fRafael Espindola if (!MI->isFullCopy()) 21310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen return 0; 21410a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen if (MI->getOperand(0).getReg() == Reg) 21510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen return MI->getOperand(1).getReg(); 21610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen if (MI->getOperand(1).getReg() == Reg) 21710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen return MI->getOperand(0).getReg(); 21810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen return 0; 21910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen} 22010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 22110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen/// isSnippet - Identify if a live interval is a snippet that should be spilled. 22210a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen/// It is assumed that SnipLI is a virtual register with the same original as 223766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen/// Edit->getReg(). 22410a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesenbool InlineSpiller::isSnippet(const LiveInterval &SnipLI) { 225766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen unsigned Reg = Edit->getReg(); 22610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 22710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // A snippet is a tiny live range with only a single instruction using it 22810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // besides copies to/from Reg or spills/fills. We accept: 22910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // 23010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // %snip = COPY %Reg / FILL fi# 23110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // %snip = USE %snip 23210a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // %Reg = COPY %snip / SPILL %snip, fi# 23310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // 234766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI)) 23510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen return false; 23610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 23710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen MachineInstr *UseMI = 0; 23810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 23910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Check that all uses satisfy our criteria. 24010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen for (MachineRegisterInfo::reg_nodbg_iterator 241766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen RI = MRI.reg_nodbg_begin(SnipLI.reg); 24210a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen MachineInstr *MI = RI.skipInstruction();) { 24310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 24410a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Allow copies to/from Reg. 24510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen if (isFullCopyOf(MI, Reg)) 24610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen continue; 24710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 24810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Allow stack slot loads. 24910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen int FI; 250766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) 25110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen continue; 25210a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 25310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Allow stack slot stores. 254766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) 25510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen continue; 25610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 25710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Allow a single additional instruction. 25810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen if (UseMI && MI != UseMI) 25910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen return false; 26010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen UseMI = MI; 26110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen } 26210a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen return true; 26310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen} 26410a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 26510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen/// collectRegsToSpill - Collect live range snippets that only have a single 26610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen/// real use. 26710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesenvoid InlineSpiller::collectRegsToSpill() { 268766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen unsigned Reg = Edit->getReg(); 26910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 27010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Main register always spills. 27110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen RegsToSpill.assign(1, Reg); 27210a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen SnippetCopies.clear(); 27310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 27410a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Snippets all have the same original, so there can't be any for an original 27510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // register. 27613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen if (Original == Reg) 27710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen return; 27810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 279766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg); 28010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen MachineInstr *MI = RI.skipInstruction();) { 28110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen unsigned SnipReg = isFullCopyOf(MI, Reg); 2822a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen if (!isSibling(SnipReg)) 28310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen continue; 284766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen LiveInterval &SnipLI = LIS.getInterval(SnipReg); 28510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen if (!isSnippet(SnipLI)) 28610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen continue; 28710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen SnippetCopies.insert(MI); 288e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen if (isRegToSpill(SnipReg)) 289e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen continue; 290e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen RegsToSpill.push_back(SnipReg); 29110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n'); 292e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumSnippets; 29310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen } 29410a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen} 29510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 29613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 29713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 29813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen// Sibling Values 29913ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen//===----------------------------------------------------------------------===// 30013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 30113ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen// After live range splitting, some values to be spilled may be defined by 30213ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen// copies from sibling registers. We trace the sibling copies back to the 30313ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen// original value if it still exists. We need it for rematerialization. 30413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen// 30513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen// Even when the value can't be rematerialized, we still want to determine if 30613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen// the value has already been spilled, or we may want to hoist the spill from a 30713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen// loop. 30813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 3092a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesenbool InlineSpiller::isSibling(unsigned Reg) { 3102a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen return TargetRegisterInfo::isVirtualRegister(Reg) && 3112a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen VRM.getOriginal(Reg) == Original; 3122a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen} 3132a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 3141ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen#ifndef NDEBUG 3151ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesenstatic raw_ostream &operator<<(raw_ostream &OS, 3161ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen const InlineSpiller::SibValueInfo &SVI) { 3171ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen OS << "spill " << PrintReg(SVI.SpillReg) << ':' 3181ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen << SVI.SpillVNI->id << '@' << SVI.SpillVNI->def; 3191ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (SVI.SpillMBB) 3201ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen OS << " in BB#" << SVI.SpillMBB->getNumber(); 3211ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (SVI.AllDefsAreReloads) 3221ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen OS << " all-reloads"; 3231ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (SVI.DefByOrigPHI) 3241ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen OS << " orig-phi"; 32569cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen if (SVI.KillsSource) 32669cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen OS << " kill"; 3271ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen OS << " deps["; 3281ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen for (unsigned i = 0, e = SVI.Deps.size(); i != e; ++i) 3291ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen OS << ' ' << SVI.Deps[i]->id << '@' << SVI.Deps[i]->def; 3301ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen OS << " ]"; 3311ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (SVI.DefMI) 3321ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen OS << " def: " << *SVI.DefMI; 3331ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen else 3341ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen OS << '\n'; 3351ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen return OS; 3361ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen} 3371ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen#endif 3381ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3391ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen/// propagateSiblingValue - Propagate the value in SVI to dependents if it is 3401ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen/// known. Otherwise remember the dependency for later. 3411ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen/// 3421ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen/// @param SVI SibValues entry to propagate. 3431ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen/// @param VNI Dependent value, or NULL to propagate to all saved dependents. 3441ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesenvoid InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVI, 3451ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen VNInfo *VNI) { 3461ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // When VNI is non-NULL, add it to SVI's deps, and only propagate to that. 3471ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen TinyPtrVector<VNInfo*> FirstDeps; 3481ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (VNI) { 3491ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen FirstDeps.push_back(VNI); 3501ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SVI->second.Deps.push_back(VNI); 3511ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } 3521ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3531ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Has the value been completely determined yet? If not, defer propagation. 3541ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (!SVI->second.hasDef()) 3551ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen return; 3561ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3571ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Work list of values to propagate. It would be nice to use a SetVector 3581ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // here, but then we would be forced to use a SmallSet. 3591ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SmallVector<SibValueMap::iterator, 8> WorkList(1, SVI); 3601ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SmallPtrSet<VNInfo*, 8> WorkSet; 3611ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3621ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen do { 3631ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SVI = WorkList.pop_back_val(); 3641ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen WorkSet.erase(SVI->first); 3651ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen TinyPtrVector<VNInfo*> *Deps = VNI ? &FirstDeps : &SVI->second.Deps; 3661ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen VNI = 0; 3671ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3681ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SibValueInfo &SV = SVI->second; 3691ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (!SV.SpillMBB) 3701ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SV.SpillMBB = LIS.getMBBFromIndex(SV.SpillVNI->def); 3711ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3721ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DEBUG(dbgs() << " prop to " << Deps->size() << ": " 3731ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen << SVI->first->id << '@' << SVI->first->def << ":\t" << SV); 3741ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3751ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen assert(SV.hasDef() && "Propagating undefined value"); 3761ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3771ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Should this value be propagated as a preferred spill candidate? We don't 3781ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // propagate values of registers that are about to spill. 379b9edad0163296e02f7b4dbbc22b50615dede357cJakob Stoklund Olesen bool PropSpill = !DisableHoisting && !isRegToSpill(SV.SpillReg); 3801ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen unsigned SpillDepth = ~0u; 3811ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3821ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen for (TinyPtrVector<VNInfo*>::iterator DepI = Deps->begin(), 3831ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepE = Deps->end(); DepI != DepE; ++DepI) { 3841ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SibValueMap::iterator DepSVI = SibValues.find(*DepI); 3851ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen assert(DepSVI != SibValues.end() && "Dependent value not in SibValues"); 3861ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SibValueInfo &DepSV = DepSVI->second; 3871ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (!DepSV.SpillMBB) 3881ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepSV.SpillMBB = LIS.getMBBFromIndex(DepSV.SpillVNI->def); 3891ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3901ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen bool Changed = false; 3911ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3921ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Propagate defining instruction. 3931ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (!DepSV.hasDef()) { 3941ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen Changed = true; 3951ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepSV.DefMI = SV.DefMI; 3961ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepSV.DefByOrigPHI = SV.DefByOrigPHI; 3971ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } 3981ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 3991ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Propagate AllDefsAreReloads. For PHI values, this computes an AND of 4001ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // all predecessors. 4011ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (!SV.AllDefsAreReloads && DepSV.AllDefsAreReloads) { 4021ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen Changed = true; 4031ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepSV.AllDefsAreReloads = false; 4041ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } 4051ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 4061ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Propagate best spill value. 4071ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (PropSpill && SV.SpillVNI != DepSV.SpillVNI) { 4081ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (SV.SpillMBB == DepSV.SpillMBB) { 4091ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // DepSV is in the same block. Hoist when dominated. 41069cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen if (DepSV.KillsSource && SV.SpillVNI->def < DepSV.SpillVNI->def) { 4111ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // This is an alternative def earlier in the same MBB. 4121ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Hoist the spill as far as possible in SpillMBB. This can ease 4131ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // register pressure: 4141ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // 4151ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // x = def 4161ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // y = use x 4171ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // s = copy x 4181ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // 4191ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Hoisting the spill of s to immediately after the def removes the 4201ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // interference between x and y: 4211ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // 4221ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // x = def 4231ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // spill x 4241ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // y = use x<kill> 4251ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // 42669cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen // This hoist only helps when the DepSV copy kills its source. 4271ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen Changed = true; 4281ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepSV.SpillReg = SV.SpillReg; 4291ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepSV.SpillVNI = SV.SpillVNI; 4301ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepSV.SpillMBB = SV.SpillMBB; 4311ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } 4321ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } else { 4331ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // DepSV is in a different block. 4341ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (SpillDepth == ~0u) 4351ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SpillDepth = Loops.getLoopDepth(SV.SpillMBB); 4361ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 4371ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Also hoist spills to blocks with smaller loop depth, but make sure 4381ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // that the new value dominates. Non-phi dependents are always 4391ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // dominated, phis need checking. 4401ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if ((Loops.getLoopDepth(DepSV.SpillMBB) > SpillDepth) && 4411ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen (!DepSVI->first->isPHIDef() || 4421ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen MDT.dominates(SV.SpillMBB, DepSV.SpillMBB))) { 4431ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen Changed = true; 4441ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepSV.SpillReg = SV.SpillReg; 4451ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepSV.SpillVNI = SV.SpillVNI; 4461ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DepSV.SpillMBB = SV.SpillMBB; 4471ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } 4481ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } 4491ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } 4501ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 4511ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (!Changed) 4521ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen continue; 4531ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 4541ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Something changed in DepSVI. Propagate to dependents. 4551ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (WorkSet.insert(DepSVI->first)) 4561ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen WorkList.push_back(DepSVI); 4571ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 4581ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DEBUG(dbgs() << " update " << DepSVI->first->id << '@' 4591ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen << DepSVI->first->def << " to:\t" << DepSV); 4601ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } 4611ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } while (!WorkList.empty()); 4621ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen} 4631ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 46413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// traceSiblingValue - Trace a value that is about to be spilled back to the 46513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// real defining instructions by looking through sibling copies. Always stay 46613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// within the range of OrigVNI so the registers are known to carry the same 46713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// value. 46813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// 46913ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// Determine if the value is defined by all reloads, so spilling isn't 47013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// necessary - the value is already in the stack slot. 47113ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// 4722ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen/// Return a defining instruction that may be a candidate for rematerialization. 47313ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// 4742ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund OlesenMachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, 4752ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen VNInfo *OrigVNI) { 4761ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Check if a cached value already exists. 4771ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SibValueMap::iterator SVI; 4781ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen bool Inserted; 4791ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen tie(SVI, Inserted) = 4801ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SibValues.insert(std::make_pair(UseVNI, SibValueInfo(UseReg, UseVNI))); 4811ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (!Inserted) { 4821ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DEBUG(dbgs() << "Cached value " << PrintReg(UseReg) << ':' 4831ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen << UseVNI->id << '@' << UseVNI->def << ' ' << SVI->second); 4841ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen return SVI->second.DefMI; 4851ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen } 4861ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 48713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen DEBUG(dbgs() << "Tracing value " << PrintReg(UseReg) << ':' 48813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen << UseVNI->id << '@' << UseVNI->def << '\n'); 4891ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen 4901ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // List of (Reg, VNI) that have been inserted into SibValues, but need to be 4911ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // processed. 4922a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen SmallVector<std::pair<unsigned, VNInfo*>, 8> WorkList; 49313ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen WorkList.push_back(std::make_pair(UseReg, UseVNI)); 49413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 49513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen do { 49613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen unsigned Reg; 49713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen VNInfo *VNI; 49813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen tie(Reg, VNI) = WorkList.pop_back_val(); 4991ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DEBUG(dbgs() << " " << PrintReg(Reg) << ':' << VNI->id << '@' << VNI->def 5001ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen << ":\t"); 50113ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 5021ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // First check if this value has already been computed. 5031ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SVI = SibValues.find(VNI); 5041ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen assert(SVI != SibValues.end() && "Missing SibValues entry"); 50513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 50613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // Trace through PHI-defs created by live range splitting. 50713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen if (VNI->isPHIDef()) { 5086b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // Stop at original PHIs. We don't know the value at the predecessors. 50913ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen if (VNI->def == OrigVNI->def) { 5101ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DEBUG(dbgs() << "orig phi value\n"); 5111ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SVI->second.DefByOrigPHI = true; 5121ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SVI->second.AllDefsAreReloads = false; 5131ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen propagateSiblingValue(SVI); 51413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen continue; 51513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen } 5166b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen 5176b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // This is a PHI inserted by live range splitting. We could trace the 5186b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // live-out value from predecessor blocks, but that search can be very 5196b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // expensive if there are many predecessors and many more PHIs as 5206b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // generated by tail-dup when it sees an indirectbr. Instead, look at 5216b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // all the non-PHI defs that have the same value as OrigVNI. They must 5226b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // jointly dominate VNI->def. This is not optimal since VNI may actually 5236b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // be jointly dominated by a smaller subset of defs, so there is a change 5246b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // we will miss a AllDefsAreReloads optimization. 5256b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen 5266b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // Separate all values dominated by OrigVNI into PHIs and non-PHIs. 5276b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen SmallVector<VNInfo*, 8> PHIs, NonPHIs; 52813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen LiveInterval &LI = LIS.getInterval(Reg); 5296b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen LiveInterval &OrigLI = LIS.getInterval(Original); 5306b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen 5316b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen for (LiveInterval::vni_iterator VI = LI.vni_begin(), VE = LI.vni_end(); 5326b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen VI != VE; ++VI) { 5336b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen VNInfo *VNI2 = *VI; 5346b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen if (VNI2->isUnused()) 5356b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen continue; 5366b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen if (!OrigLI.containsOneValue() && 5376b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen OrigLI.getVNInfoAt(VNI2->def) != OrigVNI) 5381ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen continue; 5396b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen if (VNI2->isPHIDef() && VNI2->def != OrigVNI->def) 5406b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen PHIs.push_back(VNI2); 5416b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen else 5426b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen NonPHIs.push_back(VNI2); 5436b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen } 5446b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen DEBUG(dbgs() << "split phi value, checking " << PHIs.size() 5456b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen << " phi-defs, and " << NonPHIs.size() 5466b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen << " non-phi/orig defs\n"); 5476b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen 5486b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // Create entries for all the PHIs. Don't add them to the worklist, we 5496b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // are processing all of them in one go here. 5506b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 5516b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen SibValues.insert(std::make_pair(PHIs[i], SibValueInfo(Reg, PHIs[i]))); 5526b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen 5536b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // Add every PHI as a dependent of all the non-PHIs. 5546b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen for (unsigned i = 0, e = NonPHIs.size(); i != e; ++i) { 5556b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen VNInfo *NonPHI = NonPHIs[i]; 5566b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // Known value? Try an insertion. 5571ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen tie(SVI, Inserted) = 5586b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen SibValues.insert(std::make_pair(NonPHI, SibValueInfo(Reg, NonPHI))); 5596b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // Add all the PHIs as dependents of NonPHI. 5606b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen for (unsigned pi = 0, pe = PHIs.size(); pi != pe; ++pi) 5616b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen SVI->second.Deps.push_back(PHIs[pi]); 5626b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // This is the first time we see NonPHI, add it to the worklist. 5631ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (Inserted) 5646b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen WorkList.push_back(std::make_pair(Reg, NonPHI)); 5656b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen else 5666b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen // Propagate to all inserted PHIs, not just VNI. 5676b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen propagateSiblingValue(SVI); 56813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen } 5696b6e32d954233ddeeae7f99e358ff85059f1176aJakob Stoklund Olesen 5701ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Next work list item. 57113ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen continue; 57213ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen } 57313ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 57413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 57513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen assert(MI && "Missing def"); 57613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 57713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // Trace through sibling copies. 57813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen if (unsigned SrcReg = isFullCopyOf(MI, Reg)) { 5792a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen if (isSibling(SrcReg)) { 58013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen LiveInterval &SrcLI = LIS.getInterval(SrcReg); 5812debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen LiveRange *SrcLR = SrcLI.getLiveRangeContaining(VNI->def.getRegSlot(true)); 58269cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen assert(SrcLR && "Copy from non-existing value"); 58369cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen // Check if this COPY kills its source. 58469cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen SVI->second.KillsSource = (SrcLR->end == VNI->def); 58569cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen VNInfo *SrcVNI = SrcLR->valno; 5861ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DEBUG(dbgs() << "copy of " << PrintReg(SrcReg) << ':' 58769cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen << SrcVNI->id << '@' << SrcVNI->def 58869cf1cac3f62e60a50ff0aa9808ea4d317e273efJakob Stoklund Olesen << " kill=" << unsigned(SVI->second.KillsSource) << '\n'); 5891ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Known sibling source value? Try an insertion. 5901ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen tie(SVI, Inserted) = SibValues.insert(std::make_pair(SrcVNI, 5911ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SibValueInfo(SrcReg, SrcVNI))); 5921ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // This is the first time we see Src, add it to the worklist. 5931ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen if (Inserted) 5941ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen WorkList.push_back(std::make_pair(SrcReg, SrcVNI)); 5951ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen propagateSiblingValue(SVI, VNI); 5961ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Next work list item. 59713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen continue; 59813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen } 59913ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen } 60013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 60113ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // Track reachable reloads. 6021ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SVI->second.DefMI = MI; 6031ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SVI->second.SpillMBB = MI->getParent(); 60413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen int FI; 60513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen if (Reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) { 6061ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DEBUG(dbgs() << "reload\n"); 6071ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen propagateSiblingValue(SVI); 6081ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Next work list item. 60913ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen continue; 61013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen } 61113ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 61213ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // Potential remat candidate. 6131ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DEBUG(dbgs() << "def " << *MI); 6141ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SVI->second.AllDefsAreReloads = false; 6151ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen propagateSiblingValue(SVI); 61613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen } while (!WorkList.empty()); 61713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 6181ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // Look up the value we were looking for. We already did this lokup at the 6191ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen // top of the function, but SibValues may have been invalidated. 6201ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen SVI = SibValues.find(UseVNI); 6211ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen assert(SVI != SibValues.end() && "Didn't compute requested info"); 6221ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DEBUG(dbgs() << " traced to:\t" << SVI->second); 6231ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen return SVI->second.DefMI; 62413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen} 62513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 62613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// analyzeSiblingValues - Trace values defined by sibling copies back to 62713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen/// something that isn't a sibling copy. 6282ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen/// 6292ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen/// Keep track of values that may be rematerializable. 63013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesenvoid InlineSpiller::analyzeSiblingValues() { 63113ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen SibValues.clear(); 63213ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 63313ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen // No siblings at all? 63413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen if (Edit->getReg() == Original) 63513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen return; 63613ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 63713ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen LiveInterval &OrigLI = LIS.getInterval(Original); 63813ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 63913ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen unsigned Reg = RegsToSpill[i]; 64013ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen LiveInterval &LI = LIS.getInterval(Reg); 64113ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen for (LiveInterval::const_vni_iterator VI = LI.vni_begin(), 64213ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen VE = LI.vni_end(); VI != VE; ++VI) { 64313ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen VNInfo *VNI = *VI; 6442ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (VNI->isUnused()) 64513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen continue; 6462ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen MachineInstr *DefMI = 0; 6473b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (!VNI->isPHIDef()) { 6483b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen DefMI = LIS.getInstructionFromIndex(VNI->def); 6493b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen assert(DefMI && "No defining instruction"); 6503b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen } 6512ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen // Check possible sibling copies. 6523b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (VNI->isPHIDef() || DefMI->isCopy()) { 6532ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def); 6549693d4c3f0d0e8c91e4748eb1c18799b1de7551cJakob Stoklund Olesen assert(OrigVNI && "Def outside original live range"); 6552ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (OrigVNI->def != VNI->def) 6562ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen DefMI = traceSiblingValue(Reg, VNI, OrigVNI); 6572ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen } 6588a06af96698537377275dd7848db69915638dd26Pete Cooper if (DefMI && Edit->checkRematerializable(VNI, DefMI, AA)) { 6593b7d917dec53a742fcb14802557ee75d35185968Jakob Stoklund Olesen DEBUG(dbgs() << "Value " << PrintReg(Reg) << ':' << VNI->id << '@' 6603b7d917dec53a742fcb14802557ee75d35185968Jakob Stoklund Olesen << VNI->def << " may remat from " << *DefMI); 6613b7d917dec53a742fcb14802557ee75d35185968Jakob Stoklund Olesen } 66213ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen } 66313ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen } 66413ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen} 66513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen 6662a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen/// hoistSpill - Given a sibling copy that defines a value to be spilled, insert 6672a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen/// a spill at a better location. 6682a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesenbool InlineSpiller::hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI) { 6692a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(CopyMI); 6702debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot()); 6712debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy"); 6726ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen SibValueMap::iterator I = SibValues.find(VNI); 6732a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen if (I == SibValues.end()) 6742a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen return false; 6752a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 6762a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen const SibValueInfo &SVI = I->second; 6772a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 6782a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Let the normal folding code deal with the boring case. 6792a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen if (!SVI.AllDefsAreReloads && SVI.SpillVNI == VNI) 6802a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen return false; 6812a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 6826ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen // SpillReg may have been deleted by remat and DCE. 6836ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen if (!LIS.hasInterval(SVI.SpillReg)) { 6846ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen DEBUG(dbgs() << "Stale interval: " << PrintReg(SVI.SpillReg) << '\n'); 6856ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen SibValues.erase(I); 6866ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen return false; 6876ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen } 6886ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen 6896ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen LiveInterval &SibLI = LIS.getInterval(SVI.SpillReg); 6906ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen if (!SibLI.containsValue(SVI.SpillVNI)) { 6916ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen DEBUG(dbgs() << "Stale value: " << PrintReg(SVI.SpillReg) << '\n'); 6926ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen SibValues.erase(I); 6936ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen return false; 6946ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen } 6956ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen 6962a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Conservatively extend the stack slot range to the range of the original 6972a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // value. We may be able to do better with stack slot coloring by being more 6982a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // careful here. 699e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen assert(StackInt && "No stack slot assigned yet."); 7002a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen LiveInterval &OrigLI = LIS.getInterval(Original); 7012a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx); 702e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0)); 703c1655e1a3c3a566b91b0513b56d61b58da1e36baJakob Stoklund Olesen DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": " 704e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen << *StackInt << '\n'); 7052a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 7062a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Already spilled everywhere. 707e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen if (SVI.AllDefsAreReloads) { 7081ab7c8ea03d52c6fdae6fe0efae57a36c2f701c3Jakob Stoklund Olesen DEBUG(dbgs() << "\tno spill needed: " << SVI); 709e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumOmitReloadSpill; 7102a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen return true; 711e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen } 7122a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // We are going to spill SVI.SpillVNI immediately after its def, so clear out 7132a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // any later spills of the same value. 7146ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen eliminateRedundantSpills(SibLI, SVI.SpillVNI); 7152a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 7162a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(SVI.SpillVNI->def); 7172a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen MachineBasicBlock::iterator MII; 7182a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen if (SVI.SpillVNI->isPHIDef()) 7192a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen MII = MBB->SkipPHIsAndLabels(MBB->begin()); 7202a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen else { 7216ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen MachineInstr *DefMI = LIS.getInstructionFromIndex(SVI.SpillVNI->def); 7226ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen assert(DefMI && "Defining instruction disappeared"); 7236ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen MII = DefMI; 7242a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen ++MII; 7252a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen } 7262a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Insert spill without kill flag immediately after def. 727e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen TII.storeRegToStackSlot(*MBB, MII, SVI.SpillReg, false, StackSlot, 728e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen MRI.getRegClass(SVI.SpillReg), &TRI); 7292a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen --MII; // Point to store instruction. 7302a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen LIS.InsertMachineInstrInMaps(MII); 7312a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen DEBUG(dbgs() << "\thoisted: " << SVI.SpillVNI->def << '\t' << *MII); 732e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen 73379c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen ++NumSpills; 73479c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen ++NumHoists; 7352a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen return true; 7362a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen} 7372a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 73801a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesen/// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any 73901a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesen/// redundant spills of this value in SLI.reg and sibling copies. 74001a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesenvoid InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) { 741682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen assert(VNI && "Missing value"); 74201a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesen SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList; 74301a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesen WorkList.push_back(std::make_pair(&SLI, VNI)); 744e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen assert(StackInt && "No stack slot assigned yet."); 7452a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 7462a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen do { 74701a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesen LiveInterval *LI; 74801a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesen tie(LI, VNI) = WorkList.pop_back_val(); 74901a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesen unsigned Reg = LI->reg; 7506ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen DEBUG(dbgs() << "Checking redundant spills for " 7516ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen << VNI->id << '@' << VNI->def << " in " << *LI << '\n'); 7522a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 7532a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Regs to spill are taken care of. 7542a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen if (isRegToSpill(Reg)) 7552a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen continue; 7562a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 7572a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Add all of VNI's live range to StackInt. 758e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0)); 759e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n'); 7602a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 7612a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Find all spills and copies of VNI. 7622a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen for (MachineRegisterInfo::use_nodbg_iterator UI = MRI.use_nodbg_begin(Reg); 7632a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen MachineInstr *MI = UI.skipInstruction();) { 7645a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!MI->isCopy() && !MI->mayStore()) 7652a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen continue; 7662a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI); 76701a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesen if (LI->getVNInfoAt(Idx) != VNI) 7682a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen continue; 7692a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 7702a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Follow sibling copies down the dominator tree. 7712a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen if (unsigned DstReg = isFullCopyOf(MI, Reg)) { 7722a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen if (isSibling(DstReg)) { 7732a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen LiveInterval &DstLI = LIS.getInterval(DstReg); 7742debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot()); 7752a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen assert(DstVNI && "Missing defined value"); 7762debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot"); 77701a46c82e0b58f6c2d562282538556159806c4feJakob Stoklund Olesen WorkList.push_back(std::make_pair(&DstLI, DstVNI)); 7782a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen } 7792a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen continue; 7802a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen } 7812a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 7822a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Erase spills. 7832a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen int FI; 7842a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) { 7852a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << *MI); 7862a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // eliminateDeadDefs won't normally remove stores, so switch opcode. 7872a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen MI->setDesc(TII.get(TargetOpcode::KILL)); 7882a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen DeadDefs.push_back(MI); 78979c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen ++NumSpillsRemoved; 79079c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen --NumSpills; 7912a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen } 7922a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen } 7932a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen } while (!WorkList.empty()); 7942a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen} 7952a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 7962ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen 7972ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 7982ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen// Rematerialization 7992ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 8002ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen 8012ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen/// markValueUsed - Remember that VNI failed to rematerialize, so its defining 8022ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen/// instruction cannot be eliminated. See through snippet copies 8032ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesenvoid InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) { 8042ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList; 8052ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen WorkList.push_back(std::make_pair(LI, VNI)); 8062ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen do { 8072ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen tie(LI, VNI) = WorkList.pop_back_val(); 8082ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (!UsedValues.insert(VNI)) 8092ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen continue; 8102ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen 8112ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (VNI->isPHIDef()) { 8122ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 8132ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 8142ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 815194eb71a11a77c7fb576780783a77e64924dfb10Jakob Stoklund Olesen VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI)); 8162ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (PVNI) 8172ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen WorkList.push_back(std::make_pair(LI, PVNI)); 8182ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen } 8192ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen continue; 8202ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen } 8212ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen 8222ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen // Follow snippet copies. 8232ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 8242ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (!SnippetCopies.count(MI)) 8252ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen continue; 8262ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg()); 8272ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy"); 8282debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true)); 8292ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen assert(SnipVNI && "Snippet undefined before copy"); 8302ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen WorkList.push_back(std::make_pair(&SnipLI, SnipVNI)); 8312ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen } while (!WorkList.empty()); 8322ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen} 8332ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen 83475b5409d3a9eb9b7dadcd13fff69590df94122ddJakob Stoklund Olesen/// reMaterializeFor - Attempt to rematerialize before MI instead of reloading. 8352ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesenbool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, 8362ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen MachineBasicBlock::iterator MI) { 8372debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true); 8387941350101bdfa3b016dd8a5347a92064947dd31Jakob Stoklund Olesen VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex()); 839080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 8402ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (!ParentVNI) { 8418de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen DEBUG(dbgs() << "\tadding <undef> flags: "); 8429e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 8439e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 844cf610d07de3ba4929bb5d00e084877dd974b44a1Jakob Stoklund Olesen if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) 8459e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen MO.setIsUndef(); 8469e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen } 8478de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen DEBUG(dbgs() << UseIdx << '\t' << *MI); 8489e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen return true; 8499e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen } 850080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 8512ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (SnippetCopies.count(MI)) 85210a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen return false; 85310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 8542ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen // Use an OrigVNI from traceSiblingValue when ParentVNI is a sibling copy. 8552ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen LiveRangeEdit::Remat RM(ParentVNI); 8562ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen SibValueMap::const_iterator SibI = SibValues.find(ParentVNI); 8572ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (SibI != SibValues.end()) 8582ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen RM.OrigMI = SibI->second.DefMI; 8598a06af96698537377275dd7848db69915638dd26Pete Cooper if (!Edit->canRematerializeAt(RM, UseIdx, false)) { 8602ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen markValueUsed(&VirtReg, ParentVNI); 8618de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI); 8629e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen return false; 8638de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen } 8649e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen 865cf610d07de3ba4929bb5d00e084877dd974b44a1Jakob Stoklund Olesen // If the instruction also writes VirtReg.reg, it had better not require the 866cf610d07de3ba4929bb5d00e084877dd974b44a1Jakob Stoklund Olesen // same register for uses and defs. 86766c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops; 86866c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen MIBundleOperands::RegInfo RI = 86966c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen MIBundleOperands(MI).analyzeVirtReg(VirtReg.reg, &Ops); 87066c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen if (RI.Tied) { 87166c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen markValueUsed(&VirtReg, ParentVNI); 87266c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI); 87366c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen return false; 8749e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen } 8759e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen 87683d1ba572815c92a74817cc68e2bb48c59a87b5dJakob Stoklund Olesen // Before rematerializing into a register for a single instruction, try to 87783d1ba572815c92a74817cc68e2bb48c59a87b5dJakob Stoklund Olesen // fold a load into the instruction. That avoids allocating a new register. 8785a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (RM.OrigMI->canFoldAsLoad() && 87966c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen foldMemoryOperand(Ops, RM.OrigMI)) { 880766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen Edit->markRematerialized(RM.ParentVNI); 881e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumFoldedLoads; 88283d1ba572815c92a74817cc68e2bb48c59a87b5dJakob Stoklund Olesen return true; 88383d1ba572815c92a74817cc68e2bb48c59a87b5dJakob Stoklund Olesen } 88483d1ba572815c92a74817cc68e2bb48c59a87b5dJakob Stoklund Olesen 8858de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen // Alocate a new register for the remat. 8868a06af96698537377275dd7848db69915638dd26Pete Cooper LiveInterval &NewLI = Edit->createFrom(Original); 8878de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen NewLI.markNotSpillable(); 8888de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 8898de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen // Finally we can rematerialize OrigMI before MI. 890766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen SlotIndex DefIdx = Edit->rematerializeAt(*MI->getParent(), MI, NewLI.reg, RM, 8918a06af96698537377275dd7848db69915638dd26Pete Cooper TRI); 8927b1f498a7648b790929a4f97fd82228aa7ac7beaJakob Stoklund Olesen DEBUG(dbgs() << "\tremat: " << DefIdx << '\t' 893766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen << *LIS.getInstructionFromIndex(DefIdx)); 8948de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 8958de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen // Replace operands 8968de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 89766c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen MachineOperand &MO = MI->getOperand(Ops[i].second); 898cf610d07de3ba4929bb5d00e084877dd974b44a1Jakob Stoklund Olesen if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) { 899a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen MO.setReg(NewLI.reg); 9008de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen MO.setIsKill(); 9018de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen } 9028de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen } 9038de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen DEBUG(dbgs() << "\t " << UseIdx << '\t' << *MI); 9048de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 9053b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *DefVNI = NewLI.getNextValue(DefIdx, LIS.getVNInfoAllocator()); 9062debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen NewLI.addRange(LiveRange(DefIdx, UseIdx.getRegSlot(), DefVNI)); 9078de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); 908e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumRemats; 9099e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen return true; 9109e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen} 9119e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen 912a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen/// reMaterializeAll - Try to rematerialize as many uses as possible, 9138de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen/// and trim the live ranges after. 9148de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesenvoid InlineSpiller::reMaterializeAll() { 9152ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen // analyzeSiblingValues has already tested all relevant defining instructions. 9168a06af96698537377275dd7848db69915638dd26Pete Cooper if (!Edit->anyRematerializable(AA)) 9178de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen return; 9188de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 919766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen UsedValues.clear(); 920080c316ff8a066cd164d9a8f92df509d8cb63110Jakob Stoklund Olesen 9212ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen // Try to remat before all uses of snippets. 9228de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen bool anyRemat = false; 9232ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 9242ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen unsigned Reg = RegsToSpill[i]; 9252ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen LiveInterval &LI = LIS.getInterval(Reg); 9262ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen for (MachineRegisterInfo::use_nodbg_iterator 9272ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen RI = MRI.use_nodbg_begin(Reg); 92866c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen MachineInstr *MI = RI.skipBundle();) 9292ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen anyRemat |= reMaterializeFor(LI, MI); 9302ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen } 9318de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen if (!anyRemat) 9328de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen return; 9338de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 9348de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen // Remove any values that were completely rematted. 9352ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 9362ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen unsigned Reg = RegsToSpill[i]; 9372ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen LiveInterval &LI = LIS.getInterval(Reg); 9382ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end(); 9392ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen I != E; ++I) { 9402ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen VNInfo *VNI = *I; 941c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI)) 9422ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen continue; 9432ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def); 9442ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen MI->addRegisterDead(Reg, &TRI); 9452ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen if (!MI->allDefsAreDead()) 9463b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen continue; 9472ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << *MI); 9482ef661b0e8de0d4186c5f9cc990adce0a2493b17Jakob Stoklund Olesen DeadDefs.push_back(MI); 9493b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen } 9508de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen } 951c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen 952c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen // Eliminate dead code after remat. Note that some snippet copies may be 953c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen // deleted here. 954c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen if (DeadDefs.empty()) 955c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen return; 956c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n"); 9578a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->eliminateDeadDefs(DeadDefs, RegsToSpill); 958c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen 959c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen // Get rid of deleted and empty intervals. 960c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen for (unsigned i = RegsToSpill.size(); i != 0; --i) { 961c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen unsigned Reg = RegsToSpill[i-1]; 962c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen if (!LIS.hasInterval(Reg)) { 963c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen RegsToSpill.erase(RegsToSpill.begin() + (i - 1)); 964c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen continue; 965c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen } 966c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen LiveInterval &LI = LIS.getInterval(Reg); 967c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen if (!LI.empty()) 968c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen continue; 9698a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->eraseVirtReg(Reg); 970c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen RegsToSpill.erase(RegsToSpill.begin() + (i - 1)); 971c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen } 972c1d22d8adbd40c3e5d704fdae90f9ed2089bb67eJakob Stoklund Olesen DEBUG(dbgs() << RegsToSpill.size() << " registers to spill after remat.\n"); 9738de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen} 9748de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 9756094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen 9766094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 9776094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen// Spilling 9786094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 9796094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen 980766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen/// If MI is a load or store of StackSlot, it can be removed. 98110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesenbool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) { 9821a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen int FI = 0; 98379c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen unsigned InstrReg = TII.isLoadFromStackSlot(MI, FI); 98479c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen bool IsLoad = InstrReg; 98579c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen if (!IsLoad) 98679c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen InstrReg = TII.isStoreToStackSlot(MI, FI); 9871a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen 9881a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen // We have a stack access. Is it the right register and slot? 989766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen if (InstrReg != Reg || FI != StackSlot) 9901a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen return false; 9911a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen 9921a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen DEBUG(dbgs() << "Coalescing stack access: " << *MI); 993766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen LIS.RemoveMachineInstrFromMaps(MI); 9941a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen MI->eraseFromParent(); 99579c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen 99679c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen if (IsLoad) { 99779c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen ++NumReloadsRemoved; 99879c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen --NumReloads; 99979c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen } else { 100079c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen ++NumSpillsRemoved; 100179c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen --NumSpills; 100279c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen } 100379c40a011b15f59e5b128c870c04893c3f1eddf9Jakob Stoklund Olesen 10041a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen return true; 10051a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen} 10061a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen 100766c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen/// foldMemoryOperand - Try folding stack slot references in Ops into their 100866c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen/// instructions. 100966c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen/// 101066c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen/// @param Ops Operand indices from analyzeVirtReg(). 101183d1ba572815c92a74817cc68e2bb48c59a87b5dJakob Stoklund Olesen/// @param LoadMI Load instruction to use instead of stack slot when non-null. 101266c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen/// @return True on success. 101366c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesenbool InlineSpiller:: 101466c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund OlesenfoldMemoryOperand(ArrayRef<std::pair<MachineInstr*, unsigned> > Ops, 101566c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen MachineInstr *LoadMI) { 101666c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen if (Ops.empty()) 101766c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen return false; 101866c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen // Don't attempt folding in bundles. 101966c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen MachineInstr *MI = Ops.front().first; 102066c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen if (Ops.back().first != MI || MI->isBundled()) 102166c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen return false; 102266c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen 1023d205f7a940dd38480ff6283328c7d429201cdf27Jakob Stoklund Olesen bool WasCopy = MI->isCopy(); 102417afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen unsigned ImpReg = 0; 102517afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen 1026e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied 1027e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen // operands. 1028e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen SmallVector<unsigned, 8> FoldOps; 1029e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 103066c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen unsigned Idx = Ops[i].second; 1031e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(Idx); 103217afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen if (MO.isImplicit()) { 103317afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen ImpReg = MO.getReg(); 1034e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen continue; 103517afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen } 1036e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen // FIXME: Teach targets to deal with subregs. 1037e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen if (MO.getSubReg()) 1038e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen return false; 10397b1f498a7648b790929a4f97fd82228aa7ac7beaJakob Stoklund Olesen // We cannot fold a load instruction into a def. 10407b1f498a7648b790929a4f97fd82228aa7ac7beaJakob Stoklund Olesen if (LoadMI && MO.isDef()) 10417b1f498a7648b790929a4f97fd82228aa7ac7beaJakob Stoklund Olesen return false; 1042e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen // Tied use operands should not be passed to foldMemoryOperand. 1043e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen if (!MI->isRegTiedToDefOperand(Idx)) 1044e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen FoldOps.push_back(Idx); 1045e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen } 1046e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen 104783d1ba572815c92a74817cc68e2bb48c59a87b5dJakob Stoklund Olesen MachineInstr *FoldMI = 1048766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen LoadMI ? TII.foldMemoryOperand(MI, FoldOps, LoadMI) 1049766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen : TII.foldMemoryOperand(MI, FoldOps, StackSlot); 1050e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen if (!FoldMI) 1051e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen return false; 1052766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen LIS.ReplaceMachineInstrInMaps(MI, FoldMI); 1053e05442d50806e2850eae1571958816028093df85Jakob Stoklund Olesen MI->eraseFromParent(); 105417afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen 105517afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen // TII.foldMemoryOperand may have left some implicit operands on the 105617afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen // instruction. Strip them. 105717afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen if (ImpReg) 105817afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen for (unsigned i = FoldMI->getNumOperands(); i; --i) { 105917afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen MachineOperand &MO = FoldMI->getOperand(i - 1); 106017afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen if (!MO.isReg() || !MO.isImplicit()) 106117afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen break; 106217afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen if (MO.getReg() == ImpReg) 106317afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen FoldMI->RemoveOperand(i - 1); 106417afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen } 106517afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen 106617afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen DEBUG(dbgs() << "\tfolded: " << LIS.getInstructionIndex(FoldMI) << '\t' 106717afb0664861507c9bd968f1678d8cca69b2851dJakob Stoklund Olesen << *FoldMI); 1068d205f7a940dd38480ff6283328c7d429201cdf27Jakob Stoklund Olesen if (!WasCopy) 1069d205f7a940dd38480ff6283328c7d429201cdf27Jakob Stoklund Olesen ++NumFolded; 107066c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen else if (Ops.front().second == 0) 1071d205f7a940dd38480ff6283328c7d429201cdf27Jakob Stoklund Olesen ++NumSpills; 1072d205f7a940dd38480ff6283328c7d429201cdf27Jakob Stoklund Olesen else 1073d205f7a940dd38480ff6283328c7d429201cdf27Jakob Stoklund Olesen ++NumReloads; 1074e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen return true; 1075e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen} 1076e72a5c5e2e3d09ef02bae00620d499d3e59c8a7fJakob Stoklund Olesen 10779e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen/// insertReload - Insert a reload of NewLI.reg before MI. 10789e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesenvoid InlineSpiller::insertReload(LiveInterval &NewLI, 10795d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen SlotIndex Idx, 10809e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen MachineBasicBlock::iterator MI) { 10819e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen MachineBasicBlock &MBB = *MI->getParent(); 1082e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen TII.loadRegFromStackSlot(MBB, MI, NewLI.reg, StackSlot, 1083e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen MRI.getRegClass(NewLI.reg), &TRI); 10849e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen --MI; // Point to load instruction. 10852debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex LoadIdx = LIS.InsertMachineInstrInMaps(MI).getRegSlot(); 10869e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen DEBUG(dbgs() << "\treload: " << LoadIdx << '\t' << *MI); 10873b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, LIS.getVNInfoAllocator()); 10889e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI)); 1089e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumReloads; 10909e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen} 10919e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen 10929e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen/// insertSpill - Insert a spill of NewLI.reg after MI. 109310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesenvoid InlineSpiller::insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI, 10945d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen SlotIndex Idx, MachineBasicBlock::iterator MI) { 10959e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen MachineBasicBlock &MBB = *MI->getParent(); 1096e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen TII.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, StackSlot, 1097e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen MRI.getRegClass(NewLI.reg), &TRI); 10989e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen --MI; // Point to store instruction. 10992debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex StoreIdx = LIS.InsertMachineInstrInMaps(MI).getRegSlot(); 11009e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI); 11013b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *StoreVNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator()); 11029e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI)); 1103e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumSpills; 11049e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen} 11059e55afbf88f4853ac94b6a0ac021a89c5c929d6bJakob Stoklund Olesen 110610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen/// spillAroundUses - insert spill code around each use of Reg. 110710a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesenvoid InlineSpiller::spillAroundUses(unsigned Reg) { 1108443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen DEBUG(dbgs() << "spillAroundUses " << PrintReg(Reg) << '\n'); 1109766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen LiveInterval &OldLI = LIS.getInterval(Reg); 11108de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 111110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Iterate over instructions using Reg. 111266c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RegI = MRI.reg_begin(Reg); 111366c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen MachineInstr *MI = RegI.skipBundle();) { 1114914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 11153b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen // Debug values are not allowed to affect codegen. 11163b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen if (MI->isDebugValue()) { 11173b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen // Modify DBG_VALUE now that the value is in a spill slot. 11183b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen uint64_t Offset = MI->getOperand(1).getImm(); 11193b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen const MDNode *MDPtr = MI->getOperand(2).getMetadata(); 11203b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen DebugLoc DL = MI->getDebugLoc(); 1121766faf4b2b7fe2835181777fb50d9f4d1814aba5Jakob Stoklund Olesen if (MachineInstr *NewDV = TII.emitFrameIndexDebugValue(MF, StackSlot, 11223b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen Offset, MDPtr, DL)) { 11233b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); 11243b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen MachineBasicBlock *MBB = MI->getParent(); 11253b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen MBB->insert(MBB->erase(MI), NewDV); 11263b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen } else { 11273b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 11283b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen MI->eraseFromParent(); 11293b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen } 11303b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen continue; 11313b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen } 11323b9c7ebc444ccc311a5e4125b904f9767244577aJakob Stoklund Olesen 113310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Ignore copies to/from snippets. We'll delete them. 113410a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen if (SnippetCopies.count(MI)) 113510a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen continue; 113610a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 11371a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen // Stack slot accesses may coalesce away. 113810a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen if (coalesceStackAccess(MI, Reg)) 11391a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen continue; 11401a0f91b7c56fb49be0c5914333363320ac2a5f46Jakob Stoklund Olesen 1141914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen // Analyze instruction. 114266c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops; 114366c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen MIBundleOperands::RegInfo RI = 114466c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen MIBundleOperands(MI).analyzeVirtReg(Reg, &Ops); 1145914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 11465d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen // Find the slot index where this instruction reads and writes OldLI. 11475d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen // This is usually the def slot, except for tied early clobbers. 11482debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot(); 11492debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true))) 11505d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen if (SlotIndex::isSameInstr(Idx, VNI->def)) 11515d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen Idx = VNI->def; 11525d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen 11532a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Check for a sibling copy. 11542a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen unsigned SibReg = isFullCopyOf(MI, Reg); 1155682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen if (SibReg && isSibling(SibReg)) { 1156443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen // This may actually be a copy between snippets. 1157443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen if (isRegToSpill(SibReg)) { 1158443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen DEBUG(dbgs() << "Found new snippet copy: " << *MI); 1159443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen SnippetCopies.insert(MI); 1160443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen continue; 1161443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen } 116266c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen if (RI.Writes) { 1163682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen // Hoist the spill of a sib-reg copy. 1164682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen if (hoistSpill(OldLI, MI)) { 1165682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen // This COPY is now dead, the value is already in the stack slot. 1166682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen MI->getOperand(0).setIsDead(); 1167682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen DeadDefs.push_back(MI); 1168682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen continue; 1169682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen } 1170682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen } else { 1171682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen // This is a reload for a sib-reg copy. Drop spills downstream. 1172682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen LiveInterval &SibLI = LIS.getInterval(SibReg); 1173682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx)); 1174682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen // The COPY will fold to a reload below. 1175682eed0da8e42770a0e694390ba929fd4d241657Jakob Stoklund Olesen } 11762a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen } 11772a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 11788de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen // Attempt to fold memory ops. 117966c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen if (foldMemoryOperand(Ops)) 11808de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen continue; 11818de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 1182914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen // Allocate interval around instruction. 1183914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen // FIXME: Infer regclass from instruction alone. 11848a06af96698537377275dd7848db69915638dd26Pete Cooper LiveInterval &NewLI = Edit->createFrom(Reg); 1185914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen NewLI.markNotSpillable(); 1186914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 118766c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen if (RI.Reads) 11885d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen insertReload(NewLI, Idx, MI); 1189914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 1190914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen // Rewrite instruction operands. 1191914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen bool hasLiveDef = false; 1192914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 119366c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen MachineOperand &MO = Ops[i].first->getOperand(Ops[i].second); 1194a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen MO.setReg(NewLI.reg); 1195914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen if (MO.isUse()) { 119666c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen if (!Ops[i].first->isRegTiedToDefOperand(Ops[i].second)) 1197914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen MO.setIsKill(); 1198914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen } else { 1199914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen if (!MO.isDead()) 1200914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen hasLiveDef = true; 1201914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen } 1202914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen } 12035d5ef4a886290565570703747264cd47800765fcJakob Stoklund Olesen DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI); 1204914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 1205914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen // FIXME: Use a second vreg if instruction has no tied ops. 120666c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen if (RI.Writes) { 120766c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen if (hasLiveDef) 120866c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen insertSpill(NewLI, OldLI, Idx, MI); 120966c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen else { 121066c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen // This instruction defines a dead value. We don't need to spill it, 121166c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen // but do create a live range for the dead value. 121266c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen VNInfo *VNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator()); 121366c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen NewLI.addRange(LiveRange(Idx, Idx.getDeadSlot(), VNI)); 121466c994c2dbd1a76418fdd0acb138aa029538ffe5Jakob Stoklund Olesen } 1215a80444f88d88d88513b096c97474c453a4c3bcf6Jakob Stoklund Olesen } 1216914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen 1217914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); 1218914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen } 1219914f2ff9e6969214d84a75745ec2851f045000f7Jakob Stoklund Olesen} 122010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 12216094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen/// spillAll - Spill all registers remaining after rematerialization. 12226094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesenvoid InlineSpiller::spillAll() { 1223e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen // Update LiveStacks now that we are committed to spilling. 1224e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen if (StackSlot == VirtRegMap::NO_STACK_SLOT) { 122513ba2527f73554fff39ca31250803b253076afbaJakob Stoklund Olesen StackSlot = VRM.assignVirt2StackSlot(Original); 1226e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original)); 12273b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator()); 1228e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen } else 1229e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen StackInt = &LSS.getInterval(StackSlot); 123010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 12316094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen if (Original != Edit->getReg()) 12326094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot); 123310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 1234e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen assert(StackInt->getNumValNums() == 1 && "Bad stack interval values"); 1235b1adbd1f67125668ef1a87be62553e0f95cbc4d9Jakob Stoklund Olesen for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) 1236e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen StackInt->MergeRangesInAsValue(LIS.getInterval(RegsToSpill[i]), 1237e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen StackInt->getValNumInfo(0)); 1238e9c50732f71a6c2f6813f6c40743a9bfa3791ca8Jakob Stoklund Olesen DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n'); 123910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 124010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Spill around uses of all RegsToSpill. 124110a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) 124210a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen spillAroundUses(RegsToSpill[i]); 124310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 12442a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen // Hoisted spills may cause dead code. 12452a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen if (!DeadDefs.empty()) { 12462a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n"); 12478a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->eliminateDeadDefs(DeadDefs, RegsToSpill); 12482a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen } 12492a72bfa1b1a634ef6c5aa866cac1c0afda4534e4Jakob Stoklund Olesen 125010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen // Finally delete the SnippetCopies. 1251443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { 1252443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(RegsToSpill[i]); 1253443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen MachineInstr *MI = RI.skipInstruction();) { 1254443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen assert(SnippetCopies.count(MI) && "Remaining use wasn't a snippet copy"); 1255443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen // FIXME: Do this with a LiveRangeEdit callback. 1256443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen LIS.RemoveMachineInstrFromMaps(MI); 1257443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen MI->eraseFromParent(); 1258443443cc8399d6753cac828516ea27531e296769Jakob Stoklund Olesen } 125910a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen } 126010a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen 12616094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen // Delete all spilled registers. 12627792e980c43536814ea42448db9799b4da32fef6Jakob Stoklund Olesen for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) 12638a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->eraseVirtReg(RegsToSpill[i]); 12646094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen} 12656094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen 12666094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesenvoid InlineSpiller::spill(LiveRangeEdit &edit) { 1267e9bd4ea5fda4957c373a3bbc14803d9670041dccJakob Stoklund Olesen ++NumSpilledRanges; 12686094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen Edit = &edit; 12696094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen assert(!TargetRegisterInfo::isStackSlot(edit.getReg()) 12706094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen && "Trying to spill a stack slot."); 12716094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen // Share a stack slot among all descendants of Original. 12726094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen Original = VRM.getOriginal(edit.getReg()); 12736094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen StackSlot = VRM.getStackSlot(Original); 12746094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen StackInt = 0; 12756094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen 12766094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen DEBUG(dbgs() << "Inline spilling " 12776094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen << MRI.getRegClass(edit.getReg())->getName() 12786094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen << ':' << edit.getParent() << "\nFrom original " 12796094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen << LIS.getInterval(Original) << '\n'); 12806094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen assert(edit.getParent().isSpillable() && 12816094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen "Attempting to spill already spilled value."); 12826094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen assert(DeadDefs.empty() && "Previous spill didn't remove dead defs"); 12836094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen 12846094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen collectRegsToSpill(); 12856094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen analyzeSiblingValues(); 12866094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen reMaterializeAll(); 12876094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen 12886094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen // Remat may handle everything. 12896094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen if (!RegsToSpill.empty()) 12906094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen spillAll(); 12916094bd87d845afabba5b99ec4848fa6116bac682Jakob Stoklund Olesen 12928a06af96698537377275dd7848db69915638dd26Pete Cooper Edit->calculateRegClassAndHint(MF, Loops); 129310a433238fe4679c8da17f3eb19611466332e312Jakob Stoklund Olesen} 1294