Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1 | //===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
Alkis Evlogimenos | 50c047d | 2004-01-04 23:09:24 +0000 | [diff] [blame] | 10 | // This file implements the TwoAddress instruction pass which is used |
| 11 | // by most register allocators. Two-Address instructions are rewritten |
| 12 | // from: |
| 13 | // |
| 14 | // A = B op C |
| 15 | // |
| 16 | // to: |
| 17 | // |
| 18 | // A = B |
Alkis Evlogimenos | 14be640 | 2004-02-04 22:17:40 +0000 | [diff] [blame] | 19 | // A op= C |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 20 | // |
Alkis Evlogimenos | 14be640 | 2004-02-04 22:17:40 +0000 | [diff] [blame] | 21 | // Note that if a register allocator chooses to use this pass, that it |
| 22 | // has to be capable of handling the non-SSA nature of these rewritten |
| 23 | // virtual registers. |
| 24 | // |
| 25 | // It is also worth noting that the duplicate operand of the two |
| 26 | // address instruction is removed. |
Chris Lattner | bd91c1c | 2004-01-31 21:07:15 +0000 | [diff] [blame] | 27 | // |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 28 | //===----------------------------------------------------------------------===// |
| 29 | |
| 30 | #define DEBUG_TYPE "twoaddrinstr" |
Chris Lattner | bd91c1c | 2004-01-31 21:07:15 +0000 | [diff] [blame] | 31 | #include "llvm/CodeGen/Passes.h" |
Chris Lattner | 1e31363 | 2004-07-21 23:17:57 +0000 | [diff] [blame] | 32 | #include "llvm/Function.h" |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 33 | #include "llvm/CodeGen/LiveVariables.h" |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 34 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 35 | #include "llvm/CodeGen/MachineInstr.h" |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 36 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
Chris Lattner | 84bc542 | 2007-12-31 04:13:23 +0000 | [diff] [blame] | 37 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Dan Gohman | a70dca1 | 2009-10-09 23:27:56 +0000 | [diff] [blame] | 38 | #include "llvm/Analysis/AliasAnalysis.h" |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 39 | #include "llvm/MC/MCInstrItineraries.h" |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 40 | #include "llvm/Target/TargetRegisterInfo.h" |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 41 | #include "llvm/Target/TargetInstrInfo.h" |
| 42 | #include "llvm/Target/TargetMachine.h" |
Owen Anderson | 95dad83 | 2008-10-07 20:22:28 +0000 | [diff] [blame] | 43 | #include "llvm/Target/TargetOptions.h" |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 44 | #include "llvm/Support/Debug.h" |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 45 | #include "llvm/Support/ErrorHandling.h" |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 46 | #include "llvm/ADT/BitVector.h" |
| 47 | #include "llvm/ADT/DenseMap.h" |
Dan Gohman | d68a076 | 2009-01-05 17:59:02 +0000 | [diff] [blame] | 48 | #include "llvm/ADT/SmallSet.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 49 | #include "llvm/ADT/Statistic.h" |
| 50 | #include "llvm/ADT/STLExtras.h" |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 51 | using namespace llvm; |
| 52 | |
Chris Lattner | cd3245a | 2006-12-19 22:41:21 +0000 | [diff] [blame] | 53 | STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); |
| 54 | STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 55 | STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted"); |
Chris Lattner | cd3245a | 2006-12-19 22:41:21 +0000 | [diff] [blame] | 56 | STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 57 | STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 58 | STATISTIC(NumReMats, "Number of instructions re-materialized"); |
Evan Cheng | 28c7ce3 | 2009-02-21 03:14:25 +0000 | [diff] [blame] | 59 | STATISTIC(NumDeletes, "Number of dead instructions deleted"); |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 60 | STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up"); |
| 61 | STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down"); |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 62 | |
| 63 | namespace { |
Nick Lewycky | 6726b6d | 2009-10-25 06:33:48 +0000 | [diff] [blame] | 64 | class TwoAddressInstructionPass : public MachineFunctionPass { |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 65 | const TargetInstrInfo *TII; |
| 66 | const TargetRegisterInfo *TRI; |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 67 | const InstrItineraryData *InstrItins; |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 68 | MachineRegisterInfo *MRI; |
| 69 | LiveVariables *LV; |
Dan Gohman | a70dca1 | 2009-10-09 23:27:56 +0000 | [diff] [blame] | 70 | AliasAnalysis *AA; |
Evan Cheng | c3aa7c5 | 2011-11-16 18:44:48 +0000 | [diff] [blame] | 71 | CodeGenOpt::Level OptLevel; |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 72 | |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 73 | // DistanceMap - Keep track the distance of a MI from the start of the |
| 74 | // current basic block. |
| 75 | DenseMap<MachineInstr*, unsigned> DistanceMap; |
| 76 | |
| 77 | // SrcRegMap - A map from virtual registers to physical registers which |
| 78 | // are likely targets to be coalesced to due to copies from physical |
| 79 | // registers to virtual registers. e.g. v1024 = move r0. |
| 80 | DenseMap<unsigned, unsigned> SrcRegMap; |
| 81 | |
| 82 | // DstRegMap - A map from virtual registers to physical registers which |
| 83 | // are likely targets to be coalesced to due to copies to physical |
| 84 | // registers from virtual registers. e.g. r1 = move v1024. |
| 85 | DenseMap<unsigned, unsigned> DstRegMap; |
| 86 | |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 87 | /// RegSequences - Keep track the list of REG_SEQUENCE instructions seen |
| 88 | /// during the initial walk of the machine function. |
| 89 | SmallVector<MachineInstr*, 16> RegSequences; |
| 90 | |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 91 | bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI, |
| 92 | unsigned Reg, |
| 93 | MachineBasicBlock::iterator OldPos); |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 94 | |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 95 | bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC, |
Evan Cheng | 601ca4b | 2008-06-25 01:16:38 +0000 | [diff] [blame] | 96 | MachineInstr *MI, MachineInstr *DefMI, |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 97 | MachineBasicBlock *MBB, unsigned Loc); |
Evan Cheng | 8191371 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 98 | |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 99 | bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist, |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 100 | unsigned &LastDef); |
| 101 | |
Evan Cheng | e9ccb3a | 2009-04-28 02:12:36 +0000 | [diff] [blame] | 102 | MachineInstr *FindLastUseInMBB(unsigned Reg, MachineBasicBlock *MBB, |
| 103 | unsigned Dist); |
| 104 | |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 105 | bool isProfitableToCommute(unsigned regB, unsigned regC, |
| 106 | MachineInstr *MI, MachineBasicBlock *MBB, |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 107 | unsigned Dist); |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 108 | |
Evan Cheng | 8191371 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 109 | bool CommuteInstruction(MachineBasicBlock::iterator &mi, |
| 110 | MachineFunction::iterator &mbbi, |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 111 | unsigned RegB, unsigned RegC, unsigned Dist); |
| 112 | |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 113 | bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB); |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 114 | |
| 115 | bool ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, |
| 116 | MachineBasicBlock::iterator &nmi, |
| 117 | MachineFunction::iterator &mbbi, |
Evan Cheng | 4d96c63 | 2011-02-10 02:20:55 +0000 | [diff] [blame] | 118 | unsigned RegA, unsigned RegB, unsigned Dist); |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 119 | |
Bob Wilson | 326f438 | 2009-09-01 22:51:08 +0000 | [diff] [blame] | 120 | typedef std::pair<std::pair<unsigned, bool>, MachineInstr*> NewKill; |
| 121 | bool canUpdateDeletedKills(SmallVector<unsigned, 4> &Kills, |
| 122 | SmallVector<NewKill, 4> &NewKills, |
| 123 | MachineBasicBlock *MBB, unsigned Dist); |
| 124 | bool DeleteUnusedInstr(MachineBasicBlock::iterator &mi, |
| 125 | MachineBasicBlock::iterator &nmi, |
Jakob Stoklund Olesen | 0b25ae1 | 2009-11-18 21:33:35 +0000 | [diff] [blame] | 126 | MachineFunction::iterator &mbbi, unsigned Dist); |
Bob Wilson | 326f438 | 2009-09-01 22:51:08 +0000 | [diff] [blame] | 127 | |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 128 | bool isDefTooClose(unsigned Reg, unsigned Dist, |
| 129 | MachineInstr *MI, MachineBasicBlock *MBB); |
| 130 | |
| 131 | bool RescheduleMIBelowKill(MachineBasicBlock *MBB, |
| 132 | MachineBasicBlock::iterator &mi, |
| 133 | MachineBasicBlock::iterator &nmi, |
| 134 | unsigned Reg); |
| 135 | bool RescheduleKillAboveMI(MachineBasicBlock *MBB, |
| 136 | MachineBasicBlock::iterator &mi, |
| 137 | MachineBasicBlock::iterator &nmi, |
| 138 | unsigned Reg); |
| 139 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 140 | bool TryInstructionTransform(MachineBasicBlock::iterator &mi, |
| 141 | MachineBasicBlock::iterator &nmi, |
| 142 | MachineFunction::iterator &mbbi, |
| 143 | unsigned SrcIdx, unsigned DstIdx, |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 144 | unsigned Dist, |
| 145 | SmallPtrSet<MachineInstr*, 8> &Processed); |
| 146 | |
| 147 | void ScanUses(unsigned DstReg, MachineBasicBlock *MBB, |
| 148 | SmallPtrSet<MachineInstr*, 8> &Processed); |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 149 | |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 150 | void ProcessCopy(MachineInstr *MI, MachineBasicBlock *MBB, |
| 151 | SmallPtrSet<MachineInstr*, 8> &Processed); |
Evan Cheng | 3a3cce5 | 2009-08-07 00:28:58 +0000 | [diff] [blame] | 152 | |
Evan Cheng | 53c779b | 2010-05-17 20:57:12 +0000 | [diff] [blame] | 153 | void CoalesceExtSubRegs(SmallVector<unsigned,4> &Srcs, unsigned DstReg); |
| 154 | |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 155 | /// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as part |
| 156 | /// of the de-ssa process. This replaces sources of REG_SEQUENCE as |
| 157 | /// sub-register references of the register defined by REG_SEQUENCE. |
| 158 | bool EliminateRegSequences(); |
Evan Cheng | c6dcce3 | 2010-05-17 23:24:12 +0000 | [diff] [blame] | 159 | |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 160 | public: |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 161 | static char ID; // Pass identification, replacement for typeid |
Owen Anderson | 081c34b | 2010-10-19 17:21:58 +0000 | [diff] [blame] | 162 | TwoAddressInstructionPass() : MachineFunctionPass(ID) { |
| 163 | initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry()); |
| 164 | } |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 165 | |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 166 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Dan Gohman | 845012e | 2009-07-31 23:37:33 +0000 | [diff] [blame] | 167 | AU.setPreservesCFG(); |
Dan Gohman | a70dca1 | 2009-10-09 23:27:56 +0000 | [diff] [blame] | 168 | AU.addRequired<AliasAnalysis>(); |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 169 | AU.addPreserved<LiveVariables>(); |
| 170 | AU.addPreservedID(MachineLoopInfoID); |
| 171 | AU.addPreservedID(MachineDominatorsID); |
Cameron Zwarich | d959da9 | 2010-12-19 18:03:27 +0000 | [diff] [blame] | 172 | AU.addPreservedID(PHIEliminationID); |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 173 | MachineFunctionPass::getAnalysisUsage(AU); |
| 174 | } |
Alkis Evlogimenos | 4c08086 | 2003-12-18 22:40:24 +0000 | [diff] [blame] | 175 | |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 176 | /// runOnMachineFunction - Pass entry point. |
Misha Brukman | 75fa4e4 | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 177 | bool runOnMachineFunction(MachineFunction&); |
| 178 | }; |
Chris Lattner | d74ea2b | 2006-05-24 17:04:05 +0000 | [diff] [blame] | 179 | } |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 180 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 181 | char TwoAddressInstructionPass::ID = 0; |
Owen Anderson | 2ab36d3 | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 182 | INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, "twoaddressinstruction", |
| 183 | "Two-Address instruction pass", false, false) |
| 184 | INITIALIZE_AG_DEPENDENCY(AliasAnalysis) |
| 185 | INITIALIZE_PASS_END(TwoAddressInstructionPass, "twoaddressinstruction", |
Owen Anderson | ce665bd | 2010-10-07 22:25:06 +0000 | [diff] [blame] | 186 | "Two-Address instruction pass", false, false) |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 187 | |
Owen Anderson | 90c579d | 2010-08-06 18:33:48 +0000 | [diff] [blame] | 188 | char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID; |
Alkis Evlogimenos | 4c08086 | 2003-12-18 22:40:24 +0000 | [diff] [blame] | 189 | |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 190 | /// Sink3AddrInstruction - A two-address instruction has been converted to a |
| 191 | /// three-address instruction to avoid clobbering a register. Try to sink it |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 192 | /// past the instruction that would kill the above mentioned register to reduce |
| 193 | /// register pressure. |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 194 | bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, |
| 195 | MachineInstr *MI, unsigned SavedReg, |
| 196 | MachineBasicBlock::iterator OldPos) { |
Eli Friedman | bde81d5 | 2011-09-23 22:41:57 +0000 | [diff] [blame] | 197 | // FIXME: Shouldn't we be trying to do this before we three-addressify the |
| 198 | // instruction? After this transformation is done, we no longer need |
| 199 | // the instruction to be in three-address form. |
| 200 | |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 201 | // Check if it's safe to move this instruction. |
| 202 | bool SeenStore = true; // Be conservative. |
Evan Cheng | ac1abde | 2010-03-02 19:03:01 +0000 | [diff] [blame] | 203 | if (!MI->isSafeToMove(TII, AA, SeenStore)) |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 204 | return false; |
| 205 | |
| 206 | unsigned DefReg = 0; |
| 207 | SmallSet<unsigned, 4> UseRegs; |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 208 | |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 209 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 210 | const MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | d735b80 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 211 | if (!MO.isReg()) |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 212 | continue; |
| 213 | unsigned MOReg = MO.getReg(); |
| 214 | if (!MOReg) |
| 215 | continue; |
| 216 | if (MO.isUse() && MOReg != SavedReg) |
| 217 | UseRegs.insert(MO.getReg()); |
| 218 | if (!MO.isDef()) |
| 219 | continue; |
| 220 | if (MO.isImplicit()) |
| 221 | // Don't try to move it if it implicitly defines a register. |
| 222 | return false; |
| 223 | if (DefReg) |
| 224 | // For now, don't move any instructions that define multiple registers. |
| 225 | return false; |
| 226 | DefReg = MO.getReg(); |
| 227 | } |
| 228 | |
| 229 | // Find the instruction that kills SavedReg. |
| 230 | MachineInstr *KillMI = NULL; |
Evan Cheng | f1250ee | 2010-03-23 20:36:12 +0000 | [diff] [blame] | 231 | for (MachineRegisterInfo::use_nodbg_iterator |
| 232 | UI = MRI->use_nodbg_begin(SavedReg), |
| 233 | UE = MRI->use_nodbg_end(); UI != UE; ++UI) { |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 234 | MachineOperand &UseMO = UI.getOperand(); |
| 235 | if (!UseMO.isKill()) |
| 236 | continue; |
| 237 | KillMI = UseMO.getParent(); |
| 238 | break; |
| 239 | } |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 240 | |
Eli Friedman | bde81d5 | 2011-09-23 22:41:57 +0000 | [diff] [blame] | 241 | // If we find the instruction that kills SavedReg, and it is in an |
| 242 | // appropriate location, we can try to sink the current instruction |
| 243 | // past it. |
| 244 | if (!KillMI || KillMI->getParent() != MBB || KillMI == MI || |
| 245 | KillMI->getDesc().isTerminator()) |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 246 | return false; |
| 247 | |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 248 | // If any of the definitions are used by another instruction between the |
| 249 | // position and the kill use, then it's not safe to sink it. |
| 250 | // |
| 251 | // FIXME: This can be sped up if there is an easy way to query whether an |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 252 | // instruction is before or after another instruction. Then we can use |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 253 | // MachineRegisterInfo def / use instead. |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 254 | MachineOperand *KillMO = NULL; |
| 255 | MachineBasicBlock::iterator KillPos = KillMI; |
| 256 | ++KillPos; |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 257 | |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 258 | unsigned NumVisited = 0; |
Chris Lattner | 7896c9f | 2009-12-03 00:50:42 +0000 | [diff] [blame] | 259 | for (MachineBasicBlock::iterator I = llvm::next(OldPos); I != KillPos; ++I) { |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 260 | MachineInstr *OtherMI = I; |
Dale Johannesen | 3bfef03 | 2010-02-11 18:22:31 +0000 | [diff] [blame] | 261 | // DBG_VALUE cannot be counted against the limit. |
| 262 | if (OtherMI->isDebugValue()) |
| 263 | continue; |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 264 | if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost. |
| 265 | return false; |
| 266 | ++NumVisited; |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 267 | for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { |
| 268 | MachineOperand &MO = OtherMI->getOperand(i); |
Dan Gohman | d735b80 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 269 | if (!MO.isReg()) |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 270 | continue; |
| 271 | unsigned MOReg = MO.getReg(); |
| 272 | if (!MOReg) |
| 273 | continue; |
| 274 | if (DefReg == MOReg) |
| 275 | return false; |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 276 | |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 277 | if (MO.isKill()) { |
| 278 | if (OtherMI == KillMI && MOReg == SavedReg) |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 279 | // Save the operand that kills the register. We want to unset the kill |
| 280 | // marker if we can sink MI past it. |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 281 | KillMO = &MO; |
| 282 | else if (UseRegs.count(MOReg)) |
| 283 | // One of the uses is killed before the destination. |
| 284 | return false; |
| 285 | } |
| 286 | } |
| 287 | } |
| 288 | |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 289 | // Update kill and LV information. |
| 290 | KillMO->setIsKill(false); |
| 291 | KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); |
| 292 | KillMO->setIsKill(true); |
Owen Anderson | 802af11 | 2008-07-02 21:28:58 +0000 | [diff] [blame] | 293 | |
Evan Cheng | 9f1c831 | 2008-07-03 09:09:37 +0000 | [diff] [blame] | 294 | if (LV) |
| 295 | LV->replaceKillInstruction(SavedReg, KillMI, MI); |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 296 | |
| 297 | // Move instruction to its destination. |
| 298 | MBB->remove(MI); |
| 299 | MBB->insert(KillPos, MI); |
| 300 | |
| 301 | ++Num3AddrSunk; |
| 302 | return true; |
| 303 | } |
| 304 | |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 305 | /// isTwoAddrUse - Return true if the specified MI is using the specified |
| 306 | /// register as a two-address operand. |
| 307 | static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) { |
Evan Cheng | e837dea | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 308 | const MCInstrDesc &MCID = UseMI->getDesc(); |
| 309 | for (unsigned i = 0, e = MCID.getNumOperands(); i != e; ++i) { |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 310 | MachineOperand &MO = UseMI->getOperand(i); |
Dan Gohman | d735b80 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 311 | if (MO.isReg() && MO.getReg() == Reg && |
Evan Cheng | a24752f | 2009-03-19 20:30:06 +0000 | [diff] [blame] | 312 | (MO.isDef() || UseMI->isRegTiedToDefOperand(i))) |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 313 | // Earlier use is a two-address one. |
| 314 | return true; |
| 315 | } |
| 316 | return false; |
| 317 | } |
| 318 | |
| 319 | /// isProfitableToReMat - Return true if the heuristics determines it is likely |
| 320 | /// to be profitable to re-materialize the definition of Reg rather than copy |
| 321 | /// the register. |
| 322 | bool |
| 323 | TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg, |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 324 | const TargetRegisterClass *RC, |
| 325 | MachineInstr *MI, MachineInstr *DefMI, |
| 326 | MachineBasicBlock *MBB, unsigned Loc) { |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 327 | bool OtherUse = false; |
Evan Cheng | f1250ee | 2010-03-23 20:36:12 +0000 | [diff] [blame] | 328 | for (MachineRegisterInfo::use_nodbg_iterator UI = MRI->use_nodbg_begin(Reg), |
| 329 | UE = MRI->use_nodbg_end(); UI != UE; ++UI) { |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 330 | MachineOperand &UseMO = UI.getOperand(); |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 331 | MachineInstr *UseMI = UseMO.getParent(); |
Evan Cheng | 601ca4b | 2008-06-25 01:16:38 +0000 | [diff] [blame] | 332 | MachineBasicBlock *UseMBB = UseMI->getParent(); |
| 333 | if (UseMBB == MBB) { |
| 334 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); |
| 335 | if (DI != DistanceMap.end() && DI->second == Loc) |
| 336 | continue; // Current use. |
| 337 | OtherUse = true; |
| 338 | // There is at least one other use in the MBB that will clobber the |
| 339 | // register. |
| 340 | if (isTwoAddrUse(UseMI, Reg)) |
| 341 | return true; |
| 342 | } |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 343 | } |
Evan Cheng | 601ca4b | 2008-06-25 01:16:38 +0000 | [diff] [blame] | 344 | |
| 345 | // If other uses in MBB are not two-address uses, then don't remat. |
| 346 | if (OtherUse) |
| 347 | return false; |
| 348 | |
| 349 | // No other uses in the same block, remat if it's defined in the same |
| 350 | // block so it does not unnecessarily extend the live range. |
| 351 | return MBB == DefMI->getParent(); |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 352 | } |
| 353 | |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 354 | /// NoUseAfterLastDef - Return true if there are no intervening uses between the |
| 355 | /// last instruction in the MBB that defines the specified register and the |
| 356 | /// two-address instruction which is being processed. It also returns the last |
| 357 | /// def location by reference |
| 358 | bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg, |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 359 | MachineBasicBlock *MBB, unsigned Dist, |
| 360 | unsigned &LastDef) { |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 361 | LastDef = 0; |
| 362 | unsigned LastUse = Dist; |
| 363 | for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg), |
| 364 | E = MRI->reg_end(); I != E; ++I) { |
| 365 | MachineOperand &MO = I.getOperand(); |
| 366 | MachineInstr *MI = MO.getParent(); |
Chris Lattner | 518bb53 | 2010-02-09 19:54:29 +0000 | [diff] [blame] | 367 | if (MI->getParent() != MBB || MI->isDebugValue()) |
Dale Johannesen | d94998f | 2010-02-09 02:01:46 +0000 | [diff] [blame] | 368 | continue; |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 369 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); |
| 370 | if (DI == DistanceMap.end()) |
| 371 | continue; |
| 372 | if (MO.isUse() && DI->second < LastUse) |
| 373 | LastUse = DI->second; |
| 374 | if (MO.isDef() && DI->second > LastDef) |
| 375 | LastDef = DI->second; |
| 376 | } |
| 377 | |
| 378 | return !(LastUse > LastDef && LastUse < Dist); |
| 379 | } |
| 380 | |
Evan Cheng | e9ccb3a | 2009-04-28 02:12:36 +0000 | [diff] [blame] | 381 | MachineInstr *TwoAddressInstructionPass::FindLastUseInMBB(unsigned Reg, |
| 382 | MachineBasicBlock *MBB, |
| 383 | unsigned Dist) { |
Lang Hames | a7c9dea | 2009-05-14 04:26:30 +0000 | [diff] [blame] | 384 | unsigned LastUseDist = 0; |
Evan Cheng | e9ccb3a | 2009-04-28 02:12:36 +0000 | [diff] [blame] | 385 | MachineInstr *LastUse = 0; |
| 386 | for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg), |
| 387 | E = MRI->reg_end(); I != E; ++I) { |
| 388 | MachineOperand &MO = I.getOperand(); |
| 389 | MachineInstr *MI = MO.getParent(); |
Chris Lattner | 518bb53 | 2010-02-09 19:54:29 +0000 | [diff] [blame] | 390 | if (MI->getParent() != MBB || MI->isDebugValue()) |
Dale Johannesen | d94998f | 2010-02-09 02:01:46 +0000 | [diff] [blame] | 391 | continue; |
Evan Cheng | e9ccb3a | 2009-04-28 02:12:36 +0000 | [diff] [blame] | 392 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); |
| 393 | if (DI == DistanceMap.end()) |
| 394 | continue; |
Lang Hames | a7c9dea | 2009-05-14 04:26:30 +0000 | [diff] [blame] | 395 | if (DI->second >= Dist) |
| 396 | continue; |
| 397 | |
| 398 | if (MO.isUse() && DI->second > LastUseDist) { |
Evan Cheng | e9ccb3a | 2009-04-28 02:12:36 +0000 | [diff] [blame] | 399 | LastUse = DI->first; |
| 400 | LastUseDist = DI->second; |
| 401 | } |
| 402 | } |
| 403 | return LastUse; |
| 404 | } |
| 405 | |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 406 | /// isCopyToReg - Return true if the specified MI is a copy instruction or |
| 407 | /// a extract_subreg instruction. It also returns the source and destination |
| 408 | /// registers and whether they are physical registers by reference. |
| 409 | static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, |
| 410 | unsigned &SrcReg, unsigned &DstReg, |
| 411 | bool &IsSrcPhys, bool &IsDstPhys) { |
| 412 | SrcReg = 0; |
| 413 | DstReg = 0; |
Jakob Stoklund Olesen | 04c528a | 2010-07-16 04:45:42 +0000 | [diff] [blame] | 414 | if (MI.isCopy()) { |
| 415 | DstReg = MI.getOperand(0).getReg(); |
| 416 | SrcReg = MI.getOperand(1).getReg(); |
| 417 | } else if (MI.isInsertSubreg() || MI.isSubregToReg()) { |
| 418 | DstReg = MI.getOperand(0).getReg(); |
| 419 | SrcReg = MI.getOperand(2).getReg(); |
| 420 | } else |
| 421 | return false; |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 422 | |
Jakob Stoklund Olesen | 04c528a | 2010-07-16 04:45:42 +0000 | [diff] [blame] | 423 | IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); |
| 424 | IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); |
| 425 | return true; |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 426 | } |
| 427 | |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 428 | /// isKilled - Test if the given register value, which is used by the given |
| 429 | /// instruction, is killed by the given instruction. This looks through |
| 430 | /// coalescable copies to see if the original value is potentially not killed. |
| 431 | /// |
| 432 | /// For example, in this code: |
| 433 | /// |
| 434 | /// %reg1034 = copy %reg1024 |
| 435 | /// %reg1035 = copy %reg1025<kill> |
| 436 | /// %reg1036 = add %reg1034<kill>, %reg1035<kill> |
| 437 | /// |
| 438 | /// %reg1034 is not considered to be killed, since it is copied from a |
| 439 | /// register which is not killed. Treating it as not killed lets the |
| 440 | /// normal heuristics commute the (two-address) add, which lets |
| 441 | /// coalescing eliminate the extra copy. |
| 442 | /// |
| 443 | static bool isKilled(MachineInstr &MI, unsigned Reg, |
| 444 | const MachineRegisterInfo *MRI, |
| 445 | const TargetInstrInfo *TII) { |
| 446 | MachineInstr *DefMI = &MI; |
| 447 | for (;;) { |
| 448 | if (!DefMI->killsRegister(Reg)) |
| 449 | return false; |
| 450 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) |
| 451 | return true; |
| 452 | MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); |
| 453 | // If there are multiple defs, we can't do a simple analysis, so just |
| 454 | // go with what the kill flag says. |
Chris Lattner | 7896c9f | 2009-12-03 00:50:42 +0000 | [diff] [blame] | 455 | if (llvm::next(Begin) != MRI->def_end()) |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 456 | return true; |
| 457 | DefMI = &*Begin; |
| 458 | bool IsSrcPhys, IsDstPhys; |
| 459 | unsigned SrcReg, DstReg; |
| 460 | // If the def is something other than a copy, then it isn't going to |
| 461 | // be coalesced, so follow the kill flag. |
| 462 | if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) |
| 463 | return true; |
| 464 | Reg = SrcReg; |
| 465 | } |
| 466 | } |
| 467 | |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 468 | /// isTwoAddrUse - Return true if the specified MI uses the specified register |
| 469 | /// as a two-address use. If so, return the destination register by reference. |
| 470 | static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { |
Evan Cheng | e837dea | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 471 | const MCInstrDesc &MCID = MI.getDesc(); |
| 472 | unsigned NumOps = MI.isInlineAsm() |
| 473 | ? MI.getNumOperands() : MCID.getNumOperands(); |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 474 | for (unsigned i = 0; i != NumOps; ++i) { |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 475 | const MachineOperand &MO = MI.getOperand(i); |
| 476 | if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) |
| 477 | continue; |
Evan Cheng | a24752f | 2009-03-19 20:30:06 +0000 | [diff] [blame] | 478 | unsigned ti; |
| 479 | if (MI.isRegTiedToDefOperand(i, &ti)) { |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 480 | DstReg = MI.getOperand(ti).getReg(); |
| 481 | return true; |
| 482 | } |
| 483 | } |
| 484 | return false; |
| 485 | } |
| 486 | |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 487 | /// findLocalKill - Look for an instruction below MI in the MBB that kills the |
| 488 | /// specified register. Returns null if there are any other Reg use between the |
| 489 | /// instructions. |
| 490 | static |
| 491 | MachineInstr *findLocalKill(unsigned Reg, MachineBasicBlock *MBB, |
| 492 | MachineInstr *MI, MachineRegisterInfo *MRI, |
| 493 | DenseMap<MachineInstr*, unsigned> &DistanceMap) { |
| 494 | MachineInstr *KillMI = 0; |
| 495 | for (MachineRegisterInfo::use_nodbg_iterator |
| 496 | UI = MRI->use_nodbg_begin(Reg), |
| 497 | UE = MRI->use_nodbg_end(); UI != UE; ++UI) { |
| 498 | MachineInstr *UseMI = &*UI; |
| 499 | if (UseMI == MI || UseMI->getParent() != MBB) |
| 500 | continue; |
| 501 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); |
| 502 | if (DI != DistanceMap.end()) |
| 503 | continue; |
| 504 | if (!UI.getOperand().isKill()) |
| 505 | return 0; |
Evan Cheng | 14117c4 | 2011-11-16 18:32:14 +0000 | [diff] [blame] | 506 | if (KillMI) |
| 507 | return 0; // -O0 kill markers cannot be trusted? |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 508 | KillMI = UseMI; |
| 509 | } |
| 510 | |
| 511 | return KillMI; |
| 512 | } |
| 513 | |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 514 | /// findOnlyInterestingUse - Given a register, if has a single in-basic block |
| 515 | /// use, return the use instruction if it's a copy or a two-address use. |
| 516 | static |
| 517 | MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, |
| 518 | MachineRegisterInfo *MRI, |
| 519 | const TargetInstrInfo *TII, |
Evan Cheng | 87d696a | 2009-04-14 00:32:25 +0000 | [diff] [blame] | 520 | bool &IsCopy, |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 521 | unsigned &DstReg, bool &IsDstPhys) { |
Evan Cheng | 1423c70 | 2010-03-03 21:18:38 +0000 | [diff] [blame] | 522 | if (!MRI->hasOneNonDBGUse(Reg)) |
| 523 | // None or more than one use. |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 524 | return 0; |
Evan Cheng | 1423c70 | 2010-03-03 21:18:38 +0000 | [diff] [blame] | 525 | MachineInstr &UseMI = *MRI->use_nodbg_begin(Reg); |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 526 | if (UseMI.getParent() != MBB) |
| 527 | return 0; |
| 528 | unsigned SrcReg; |
| 529 | bool IsSrcPhys; |
Evan Cheng | 87d696a | 2009-04-14 00:32:25 +0000 | [diff] [blame] | 530 | if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) { |
| 531 | IsCopy = true; |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 532 | return &UseMI; |
Evan Cheng | 87d696a | 2009-04-14 00:32:25 +0000 | [diff] [blame] | 533 | } |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 534 | IsDstPhys = false; |
Evan Cheng | 87d696a | 2009-04-14 00:32:25 +0000 | [diff] [blame] | 535 | if (isTwoAddrUse(UseMI, Reg, DstReg)) { |
| 536 | IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 537 | return &UseMI; |
Evan Cheng | 87d696a | 2009-04-14 00:32:25 +0000 | [diff] [blame] | 538 | } |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 539 | return 0; |
| 540 | } |
| 541 | |
| 542 | /// getMappedReg - Return the physical register the specified virtual register |
| 543 | /// might be mapped to. |
| 544 | static unsigned |
| 545 | getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) { |
| 546 | while (TargetRegisterInfo::isVirtualRegister(Reg)) { |
| 547 | DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg); |
| 548 | if (SI == RegMap.end()) |
| 549 | return 0; |
| 550 | Reg = SI->second; |
| 551 | } |
| 552 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) |
| 553 | return Reg; |
| 554 | return 0; |
| 555 | } |
| 556 | |
| 557 | /// regsAreCompatible - Return true if the two registers are equal or aliased. |
| 558 | /// |
| 559 | static bool |
| 560 | regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { |
| 561 | if (RegA == RegB) |
| 562 | return true; |
| 563 | if (!RegA || !RegB) |
| 564 | return false; |
| 565 | return TRI->regsOverlap(RegA, RegB); |
| 566 | } |
| 567 | |
| 568 | |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 569 | /// isProfitableToReMat - Return true if it's potentially profitable to commute |
| 570 | /// the two-address instruction that's being processed. |
| 571 | bool |
| 572 | TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC, |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 573 | MachineInstr *MI, MachineBasicBlock *MBB, |
| 574 | unsigned Dist) { |
Evan Cheng | c3aa7c5 | 2011-11-16 18:44:48 +0000 | [diff] [blame] | 575 | if (OptLevel == CodeGenOpt::None) |
| 576 | return false; |
| 577 | |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 578 | // Determine if it's profitable to commute this two address instruction. In |
| 579 | // general, we want no uses between this instruction and the definition of |
| 580 | // the two-address register. |
| 581 | // e.g. |
| 582 | // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 |
| 583 | // %reg1029<def> = MOV8rr %reg1028 |
| 584 | // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> |
| 585 | // insert => %reg1030<def> = MOV8rr %reg1028 |
| 586 | // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> |
| 587 | // In this case, it might not be possible to coalesce the second MOV8rr |
| 588 | // instruction if the first one is coalesced. So it would be profitable to |
| 589 | // commute it: |
| 590 | // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 |
| 591 | // %reg1029<def> = MOV8rr %reg1028 |
| 592 | // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> |
| 593 | // insert => %reg1030<def> = MOV8rr %reg1029 |
| 594 | // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead> |
| 595 | |
| 596 | if (!MI->killsRegister(regC)) |
| 597 | return false; |
| 598 | |
| 599 | // Ok, we have something like: |
| 600 | // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> |
| 601 | // let's see if it's worth commuting it. |
| 602 | |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 603 | // Look for situations like this: |
| 604 | // %reg1024<def> = MOV r1 |
| 605 | // %reg1025<def> = MOV r0 |
| 606 | // %reg1026<def> = ADD %reg1024, %reg1025 |
| 607 | // r0 = MOV %reg1026 |
| 608 | // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. |
| 609 | unsigned FromRegB = getMappedReg(regB, SrcRegMap); |
| 610 | unsigned FromRegC = getMappedReg(regC, SrcRegMap); |
| 611 | unsigned ToRegB = getMappedReg(regB, DstRegMap); |
| 612 | unsigned ToRegC = getMappedReg(regC, DstRegMap); |
Evan Cheng | 4d96c63 | 2011-02-10 02:20:55 +0000 | [diff] [blame] | 613 | if ((FromRegB && ToRegB && !regsAreCompatible(FromRegB, ToRegB, TRI)) && |
Evan Cheng | bbc726d | 2010-12-14 21:34:53 +0000 | [diff] [blame] | 614 | ((!FromRegC && !ToRegC) || |
| 615 | regsAreCompatible(FromRegB, ToRegC, TRI) || |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 616 | regsAreCompatible(FromRegC, ToRegB, TRI))) |
| 617 | return true; |
| 618 | |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 619 | // If there is a use of regC between its last def (could be livein) and this |
| 620 | // instruction, then bail. |
| 621 | unsigned LastDefC = 0; |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 622 | if (!NoUseAfterLastDef(regC, MBB, Dist, LastDefC)) |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 623 | return false; |
| 624 | |
| 625 | // If there is a use of regB between its last def (could be livein) and this |
| 626 | // instruction, then go ahead and make this transformation. |
| 627 | unsigned LastDefB = 0; |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 628 | if (!NoUseAfterLastDef(regB, MBB, Dist, LastDefB)) |
Evan Cheng | d498c8f | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 629 | return true; |
| 630 | |
| 631 | // Since there are no intervening uses for both registers, then commute |
| 632 | // if the def of regC is closer. Its live interval is shorter. |
| 633 | return LastDefB && LastDefC && LastDefC > LastDefB; |
| 634 | } |
| 635 | |
Evan Cheng | 8191371 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 636 | /// CommuteInstruction - Commute a two-address instruction and update the basic |
| 637 | /// block, distance map, and live variables if needed. Return true if it is |
| 638 | /// successful. |
| 639 | bool |
| 640 | TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi, |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 641 | MachineFunction::iterator &mbbi, |
| 642 | unsigned RegB, unsigned RegC, unsigned Dist) { |
Evan Cheng | 8191371 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 643 | MachineInstr *MI = mi; |
David Greene | eb00b18 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 644 | DEBUG(dbgs() << "2addr: COMMUTING : " << *MI); |
Evan Cheng | 8191371 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 645 | MachineInstr *NewMI = TII->commuteInstruction(MI); |
| 646 | |
| 647 | if (NewMI == 0) { |
David Greene | eb00b18 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 648 | DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n"); |
Evan Cheng | 8191371 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 649 | return false; |
| 650 | } |
| 651 | |
David Greene | eb00b18 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 652 | DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI); |
Evan Cheng | 8191371 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 653 | // If the instruction changed to commute it, update livevar. |
| 654 | if (NewMI != MI) { |
| 655 | if (LV) |
| 656 | // Update live variables |
| 657 | LV->replaceKillInstruction(RegC, MI, NewMI); |
| 658 | |
| 659 | mbbi->insert(mi, NewMI); // Insert the new inst |
| 660 | mbbi->erase(mi); // Nuke the old inst. |
| 661 | mi = NewMI; |
| 662 | DistanceMap.insert(std::make_pair(NewMI, Dist)); |
| 663 | } |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 664 | |
| 665 | // Update source register map. |
| 666 | unsigned FromRegC = getMappedReg(RegC, SrcRegMap); |
| 667 | if (FromRegC) { |
| 668 | unsigned RegA = MI->getOperand(0).getReg(); |
| 669 | SrcRegMap[RegA] = FromRegC; |
| 670 | } |
| 671 | |
Evan Cheng | 8191371 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 672 | return true; |
| 673 | } |
| 674 | |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 675 | /// isProfitableToConv3Addr - Return true if it is profitable to convert the |
| 676 | /// given 2-address instruction to a 3-address one. |
| 677 | bool |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 678 | TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){ |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 679 | // Look for situations like this: |
| 680 | // %reg1024<def> = MOV r1 |
| 681 | // %reg1025<def> = MOV r0 |
| 682 | // %reg1026<def> = ADD %reg1024, %reg1025 |
| 683 | // r2 = MOV %reg1026 |
| 684 | // Turn ADD into a 3-address instruction to avoid a copy. |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 685 | unsigned FromRegB = getMappedReg(RegB, SrcRegMap); |
| 686 | if (!FromRegB) |
| 687 | return false; |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 688 | unsigned ToRegA = getMappedReg(RegA, DstRegMap); |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 689 | return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI)); |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 690 | } |
| 691 | |
| 692 | /// ConvertInstTo3Addr - Convert the specified two-address instruction into a |
| 693 | /// three address one. Return true if this transformation was successful. |
| 694 | bool |
| 695 | TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, |
| 696 | MachineBasicBlock::iterator &nmi, |
| 697 | MachineFunction::iterator &mbbi, |
Evan Cheng | 4d96c63 | 2011-02-10 02:20:55 +0000 | [diff] [blame] | 698 | unsigned RegA, unsigned RegB, |
| 699 | unsigned Dist) { |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 700 | MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV); |
| 701 | if (NewMI) { |
David Greene | eb00b18 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 702 | DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi); |
| 703 | DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI); |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 704 | bool Sunk = false; |
| 705 | |
| 706 | if (NewMI->findRegisterUseOperand(RegB, false, TRI)) |
| 707 | // FIXME: Temporary workaround. If the new instruction doesn't |
| 708 | // uses RegB, convertToThreeAddress must have created more |
| 709 | // then one instruction. |
| 710 | Sunk = Sink3AddrInstruction(mbbi, NewMI, RegB, mi); |
| 711 | |
| 712 | mbbi->erase(mi); // Nuke the old inst. |
| 713 | |
| 714 | if (!Sunk) { |
| 715 | DistanceMap.insert(std::make_pair(NewMI, Dist)); |
| 716 | mi = NewMI; |
Chris Lattner | 7896c9f | 2009-12-03 00:50:42 +0000 | [diff] [blame] | 717 | nmi = llvm::next(mi); |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 718 | } |
Evan Cheng | 4d96c63 | 2011-02-10 02:20:55 +0000 | [diff] [blame] | 719 | |
| 720 | // Update source and destination register maps. |
| 721 | SrcRegMap.erase(RegA); |
| 722 | DstRegMap.erase(RegB); |
Evan Cheng | e6f350d | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 723 | return true; |
| 724 | } |
| 725 | |
| 726 | return false; |
| 727 | } |
| 728 | |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 729 | /// ScanUses - Scan forward recursively for only uses, update maps if the use |
| 730 | /// is a copy or a two-address instruction. |
| 731 | void |
| 732 | TwoAddressInstructionPass::ScanUses(unsigned DstReg, MachineBasicBlock *MBB, |
| 733 | SmallPtrSet<MachineInstr*, 8> &Processed) { |
| 734 | SmallVector<unsigned, 4> VirtRegPairs; |
| 735 | bool IsDstPhys; |
| 736 | bool IsCopy = false; |
| 737 | unsigned NewReg = 0; |
| 738 | unsigned Reg = DstReg; |
| 739 | while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy, |
| 740 | NewReg, IsDstPhys)) { |
| 741 | if (IsCopy && !Processed.insert(UseMI)) |
| 742 | break; |
| 743 | |
| 744 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); |
| 745 | if (DI != DistanceMap.end()) |
| 746 | // Earlier in the same MBB.Reached via a back edge. |
| 747 | break; |
| 748 | |
| 749 | if (IsDstPhys) { |
| 750 | VirtRegPairs.push_back(NewReg); |
| 751 | break; |
| 752 | } |
| 753 | bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second; |
| 754 | if (!isNew) |
| 755 | assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!"); |
| 756 | VirtRegPairs.push_back(NewReg); |
| 757 | Reg = NewReg; |
| 758 | } |
| 759 | |
| 760 | if (!VirtRegPairs.empty()) { |
| 761 | unsigned ToReg = VirtRegPairs.back(); |
| 762 | VirtRegPairs.pop_back(); |
| 763 | while (!VirtRegPairs.empty()) { |
| 764 | unsigned FromReg = VirtRegPairs.back(); |
| 765 | VirtRegPairs.pop_back(); |
| 766 | bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; |
| 767 | if (!isNew) |
| 768 | assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!"); |
| 769 | ToReg = FromReg; |
| 770 | } |
| 771 | bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second; |
| 772 | if (!isNew) |
| 773 | assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!"); |
| 774 | } |
| 775 | } |
| 776 | |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 777 | /// ProcessCopy - If the specified instruction is not yet processed, process it |
| 778 | /// if it's a copy. For a copy instruction, we find the physical registers the |
| 779 | /// source and destination registers might be mapped to. These are kept in |
| 780 | /// point-to maps used to determine future optimizations. e.g. |
| 781 | /// v1024 = mov r0 |
| 782 | /// v1025 = mov r1 |
| 783 | /// v1026 = add v1024, v1025 |
| 784 | /// r1 = mov r1026 |
| 785 | /// If 'add' is a two-address instruction, v1024, v1026 are both potentially |
| 786 | /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is |
| 787 | /// potentially joined with r1 on the output side. It's worthwhile to commute |
| 788 | /// 'add' to eliminate a copy. |
| 789 | void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI, |
| 790 | MachineBasicBlock *MBB, |
| 791 | SmallPtrSet<MachineInstr*, 8> &Processed) { |
| 792 | if (Processed.count(MI)) |
| 793 | return; |
| 794 | |
| 795 | bool IsSrcPhys, IsDstPhys; |
| 796 | unsigned SrcReg, DstReg; |
| 797 | if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) |
| 798 | return; |
| 799 | |
| 800 | if (IsDstPhys && !IsSrcPhys) |
| 801 | DstRegMap.insert(std::make_pair(SrcReg, DstReg)); |
| 802 | else if (!IsDstPhys && IsSrcPhys) { |
Evan Cheng | 3005ed6 | 2009-04-13 20:04:24 +0000 | [diff] [blame] | 803 | bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second; |
| 804 | if (!isNew) |
| 805 | assert(SrcRegMap[DstReg] == SrcReg && |
| 806 | "Can't map to two src physical registers!"); |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 807 | |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 808 | ScanUses(DstReg, MBB, Processed); |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 809 | } |
| 810 | |
| 811 | Processed.insert(MI); |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 812 | return; |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 813 | } |
| 814 | |
Evan Cheng | 28c7ce3 | 2009-02-21 03:14:25 +0000 | [diff] [blame] | 815 | /// isSafeToDelete - If the specified instruction does not produce any side |
| 816 | /// effects and all of its defs are dead, then it's safe to delete. |
Jakob Stoklund Olesen | 0b25ae1 | 2009-11-18 21:33:35 +0000 | [diff] [blame] | 817 | static bool isSafeToDelete(MachineInstr *MI, |
Evan Cheng | e9ccb3a | 2009-04-28 02:12:36 +0000 | [diff] [blame] | 818 | const TargetInstrInfo *TII, |
| 819 | SmallVector<unsigned, 4> &Kills) { |
Evan Cheng | e837dea | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 820 | const MCInstrDesc &MCID = MI->getDesc(); |
| 821 | if (MCID.mayStore() || MCID.isCall()) |
Evan Cheng | 28c7ce3 | 2009-02-21 03:14:25 +0000 | [diff] [blame] | 822 | return false; |
Evan Cheng | e837dea | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 823 | if (MCID.isTerminator() || MI->hasUnmodeledSideEffects()) |
Evan Cheng | 28c7ce3 | 2009-02-21 03:14:25 +0000 | [diff] [blame] | 824 | return false; |
| 825 | |
| 826 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 827 | MachineOperand &MO = MI->getOperand(i); |
Evan Cheng | e9ccb3a | 2009-04-28 02:12:36 +0000 | [diff] [blame] | 828 | if (!MO.isReg()) |
Evan Cheng | 28c7ce3 | 2009-02-21 03:14:25 +0000 | [diff] [blame] | 829 | continue; |
Evan Cheng | e9ccb3a | 2009-04-28 02:12:36 +0000 | [diff] [blame] | 830 | if (MO.isDef() && !MO.isDead()) |
Evan Cheng | 28c7ce3 | 2009-02-21 03:14:25 +0000 | [diff] [blame] | 831 | return false; |
Jakob Stoklund Olesen | 0b25ae1 | 2009-11-18 21:33:35 +0000 | [diff] [blame] | 832 | if (MO.isUse() && MO.isKill()) |
Evan Cheng | e9ccb3a | 2009-04-28 02:12:36 +0000 | [diff] [blame] | 833 | Kills.push_back(MO.getReg()); |
Evan Cheng | 28c7ce3 | 2009-02-21 03:14:25 +0000 | [diff] [blame] | 834 | } |
Evan Cheng | 28c7ce3 | 2009-02-21 03:14:25 +0000 | [diff] [blame] | 835 | return true; |
| 836 | } |
| 837 | |
Bob Wilson | 326f438 | 2009-09-01 22:51:08 +0000 | [diff] [blame] | 838 | /// canUpdateDeletedKills - Check if all the registers listed in Kills are |
| 839 | /// killed by instructions in MBB preceding the current instruction at |
| 840 | /// position Dist. If so, return true and record information about the |
| 841 | /// preceding kills in NewKills. |
| 842 | bool TwoAddressInstructionPass:: |
| 843 | canUpdateDeletedKills(SmallVector<unsigned, 4> &Kills, |
| 844 | SmallVector<NewKill, 4> &NewKills, |
| 845 | MachineBasicBlock *MBB, unsigned Dist) { |
| 846 | while (!Kills.empty()) { |
| 847 | unsigned Kill = Kills.back(); |
| 848 | Kills.pop_back(); |
| 849 | if (TargetRegisterInfo::isPhysicalRegister(Kill)) |
| 850 | return false; |
| 851 | |
| 852 | MachineInstr *LastKill = FindLastUseInMBB(Kill, MBB, Dist); |
| 853 | if (!LastKill) |
| 854 | return false; |
| 855 | |
Evan Cheng | 1015ba7 | 2010-05-21 20:53:24 +0000 | [diff] [blame] | 856 | bool isModRef = LastKill->definesRegister(Kill); |
Bob Wilson | 326f438 | 2009-09-01 22:51:08 +0000 | [diff] [blame] | 857 | NewKills.push_back(std::make_pair(std::make_pair(Kill, isModRef), |
| 858 | LastKill)); |
| 859 | } |
| 860 | return true; |
| 861 | } |
| 862 | |
| 863 | /// DeleteUnusedInstr - If an instruction with a tied register operand can |
| 864 | /// be safely deleted, just delete it. |
| 865 | bool |
| 866 | TwoAddressInstructionPass::DeleteUnusedInstr(MachineBasicBlock::iterator &mi, |
| 867 | MachineBasicBlock::iterator &nmi, |
| 868 | MachineFunction::iterator &mbbi, |
Bob Wilson | 326f438 | 2009-09-01 22:51:08 +0000 | [diff] [blame] | 869 | unsigned Dist) { |
| 870 | // Check if the instruction has no side effects and if all its defs are dead. |
| 871 | SmallVector<unsigned, 4> Kills; |
Jakob Stoklund Olesen | 0b25ae1 | 2009-11-18 21:33:35 +0000 | [diff] [blame] | 872 | if (!isSafeToDelete(mi, TII, Kills)) |
Bob Wilson | 326f438 | 2009-09-01 22:51:08 +0000 | [diff] [blame] | 873 | return false; |
| 874 | |
| 875 | // If this instruction kills some virtual registers, we need to |
| 876 | // update the kill information. If it's not possible to do so, |
| 877 | // then bail out. |
| 878 | SmallVector<NewKill, 4> NewKills; |
| 879 | if (!canUpdateDeletedKills(Kills, NewKills, &*mbbi, Dist)) |
| 880 | return false; |
| 881 | |
| 882 | if (LV) { |
| 883 | while (!NewKills.empty()) { |
| 884 | MachineInstr *NewKill = NewKills.back().second; |
| 885 | unsigned Kill = NewKills.back().first.first; |
| 886 | bool isDead = NewKills.back().first.second; |
| 887 | NewKills.pop_back(); |
| 888 | if (LV->removeVirtualRegisterKilled(Kill, mi)) { |
| 889 | if (isDead) |
| 890 | LV->addVirtualRegisterDead(Kill, NewKill); |
| 891 | else |
| 892 | LV->addVirtualRegisterKilled(Kill, NewKill); |
| 893 | } |
| 894 | } |
Bob Wilson | 326f438 | 2009-09-01 22:51:08 +0000 | [diff] [blame] | 895 | } |
| 896 | |
| 897 | mbbi->erase(mi); // Nuke the old inst. |
| 898 | mi = nmi; |
| 899 | return true; |
| 900 | } |
| 901 | |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 902 | /// RescheduleMIBelowKill - If there is one more local instruction that reads |
| 903 | /// 'Reg' and it kills 'Reg, consider moving the instruction below the kill |
| 904 | /// instruction in order to eliminate the need for the copy. |
| 905 | bool |
| 906 | TwoAddressInstructionPass::RescheduleMIBelowKill(MachineBasicBlock *MBB, |
| 907 | MachineBasicBlock::iterator &mi, |
| 908 | MachineBasicBlock::iterator &nmi, |
| 909 | unsigned Reg) { |
| 910 | MachineInstr *MI = &*mi; |
| 911 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); |
| 912 | if (DI == DistanceMap.end()) |
| 913 | // Must be created from unfolded load. Don't waste time trying this. |
| 914 | return false; |
| 915 | |
| 916 | MachineInstr *KillMI = findLocalKill(Reg, MBB, mi, MRI, DistanceMap); |
| 917 | if (!KillMI || KillMI->isCopy() || KillMI->isCopyLike()) |
| 918 | // Don't mess with copies, they may be coalesced later. |
| 919 | return false; |
| 920 | |
| 921 | const MCInstrDesc &MCID = KillMI->getDesc(); |
| 922 | if (MCID.hasUnmodeledSideEffects() || MCID.isCall() || MCID.isBranch() || |
| 923 | MCID.isTerminator()) |
| 924 | // Don't move pass calls, etc. |
| 925 | return false; |
| 926 | |
| 927 | unsigned DstReg; |
| 928 | if (isTwoAddrUse(*KillMI, Reg, DstReg)) |
| 929 | return false; |
| 930 | |
Evan Cheng | f178418 | 2011-11-15 06:26:51 +0000 | [diff] [blame] | 931 | bool SeenStore = true; |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 932 | if (!MI->isSafeToMove(TII, AA, SeenStore)) |
| 933 | return false; |
| 934 | |
| 935 | if (TII->getInstrLatency(InstrItins, MI) > 1) |
| 936 | // FIXME: Needs more sophisticated heuristics. |
| 937 | return false; |
| 938 | |
| 939 | SmallSet<unsigned, 2> Uses; |
Evan Cheng | 9bad88a | 2011-11-16 03:47:42 +0000 | [diff] [blame] | 940 | SmallSet<unsigned, 2> Kills; |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 941 | SmallSet<unsigned, 2> Defs; |
| 942 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 943 | const MachineOperand &MO = MI->getOperand(i); |
| 944 | if (!MO.isReg()) |
| 945 | continue; |
| 946 | unsigned MOReg = MO.getReg(); |
| 947 | if (!MOReg) |
| 948 | continue; |
| 949 | if (MO.isDef()) |
| 950 | Defs.insert(MOReg); |
Evan Cheng | 9bad88a | 2011-11-16 03:47:42 +0000 | [diff] [blame] | 951 | else { |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 952 | Uses.insert(MOReg); |
Evan Cheng | 9bad88a | 2011-11-16 03:47:42 +0000 | [diff] [blame] | 953 | if (MO.isKill() && MOReg != Reg) |
| 954 | Kills.insert(MOReg); |
| 955 | } |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 956 | } |
| 957 | |
| 958 | // Move the copies connected to MI down as well. |
| 959 | MachineBasicBlock::iterator From = MI; |
| 960 | MachineBasicBlock::iterator To = llvm::next(From); |
| 961 | while (To->isCopy() && Defs.count(To->getOperand(1).getReg())) { |
| 962 | Defs.insert(To->getOperand(0).getReg()); |
| 963 | ++To; |
| 964 | } |
| 965 | |
| 966 | // Check if the reschedule will not break depedencies. |
| 967 | unsigned NumVisited = 0; |
| 968 | MachineBasicBlock::iterator KillPos = KillMI; |
| 969 | ++KillPos; |
| 970 | for (MachineBasicBlock::iterator I = To; I != KillPos; ++I) { |
| 971 | MachineInstr *OtherMI = I; |
| 972 | // DBG_VALUE cannot be counted against the limit. |
| 973 | if (OtherMI->isDebugValue()) |
| 974 | continue; |
| 975 | if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. |
| 976 | return false; |
| 977 | ++NumVisited; |
| 978 | const MCInstrDesc &OMCID = OtherMI->getDesc(); |
| 979 | if (OMCID.hasUnmodeledSideEffects() || OMCID.isCall() || OMCID.isBranch() || |
| 980 | OMCID.isTerminator()) |
| 981 | // Don't move pass calls, etc. |
| 982 | return false; |
| 983 | for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { |
| 984 | const MachineOperand &MO = OtherMI->getOperand(i); |
| 985 | if (!MO.isReg()) |
| 986 | continue; |
| 987 | unsigned MOReg = MO.getReg(); |
| 988 | if (!MOReg) |
| 989 | continue; |
| 990 | if (MO.isDef()) { |
| 991 | if (Uses.count(MOReg)) |
| 992 | // Physical register use would be clobbered. |
| 993 | return false; |
| 994 | if (!MO.isDead() && Defs.count(MOReg)) |
| 995 | // May clobber a physical register def. |
| 996 | // FIXME: This may be too conservative. It's ok if the instruction |
| 997 | // is sunken completely below the use. |
| 998 | return false; |
| 999 | } else { |
| 1000 | if (Defs.count(MOReg)) |
| 1001 | return false; |
Evan Cheng | 9bad88a | 2011-11-16 03:47:42 +0000 | [diff] [blame] | 1002 | if (MOReg != Reg && |
| 1003 | ((MO.isKill() && Uses.count(MOReg)) || Kills.count(MOReg))) |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1004 | // Don't want to extend other live ranges and update kills. |
| 1005 | return false; |
| 1006 | } |
| 1007 | } |
| 1008 | } |
| 1009 | |
| 1010 | // Move debug info as well. |
Evan Cheng | 8aee7d8 | 2011-11-14 21:11:15 +0000 | [diff] [blame] | 1011 | while (From != MBB->begin() && llvm::prior(From)->isDebugValue()) |
| 1012 | --From; |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1013 | |
| 1014 | // Copies following MI may have been moved as well. |
| 1015 | nmi = To; |
| 1016 | MBB->splice(KillPos, MBB, From, To); |
| 1017 | DistanceMap.erase(DI); |
| 1018 | |
| 1019 | if (LV) { |
| 1020 | // Update live variables |
| 1021 | LV->removeVirtualRegisterKilled(Reg, KillMI); |
| 1022 | LV->addVirtualRegisterKilled(Reg, MI); |
| 1023 | } else { |
| 1024 | for (unsigned i = 0, e = KillMI->getNumOperands(); i != e; ++i) { |
| 1025 | MachineOperand &MO = KillMI->getOperand(i); |
| 1026 | if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) |
| 1027 | continue; |
| 1028 | MO.setIsKill(false); |
| 1029 | } |
| 1030 | MI->addRegisterKilled(Reg, 0); |
| 1031 | } |
| 1032 | |
| 1033 | return true; |
| 1034 | } |
| 1035 | |
| 1036 | /// isDefTooClose - Return true if the re-scheduling will put the given |
| 1037 | /// instruction too close to the defs of its register dependencies. |
| 1038 | bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist, |
| 1039 | MachineInstr *MI, |
| 1040 | MachineBasicBlock *MBB) { |
| 1041 | for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(Reg), |
| 1042 | DE = MRI->def_end(); DI != DE; ++DI) { |
| 1043 | MachineInstr *DefMI = &*DI; |
| 1044 | if (DefMI->getParent() != MBB || DefMI->isCopy() || DefMI->isCopyLike()) |
| 1045 | continue; |
| 1046 | if (DefMI == MI) |
| 1047 | return true; // MI is defining something KillMI uses |
| 1048 | DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(DefMI); |
| 1049 | if (DDI == DistanceMap.end()) |
| 1050 | return true; // Below MI |
| 1051 | unsigned DefDist = DDI->second; |
| 1052 | assert(Dist > DefDist && "Visited def already?"); |
| 1053 | if (TII->getInstrLatency(InstrItins, DefMI) > (int)(Dist - DefDist)) |
| 1054 | return true; |
| 1055 | } |
| 1056 | return false; |
| 1057 | } |
| 1058 | |
| 1059 | /// RescheduleKillAboveMI - If there is one more local instruction that reads |
| 1060 | /// 'Reg' and it kills 'Reg, consider moving the kill instruction above the |
| 1061 | /// current two-address instruction in order to eliminate the need for the |
| 1062 | /// copy. |
| 1063 | bool |
| 1064 | TwoAddressInstructionPass::RescheduleKillAboveMI(MachineBasicBlock *MBB, |
| 1065 | MachineBasicBlock::iterator &mi, |
| 1066 | MachineBasicBlock::iterator &nmi, |
| 1067 | unsigned Reg) { |
| 1068 | MachineInstr *MI = &*mi; |
| 1069 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); |
| 1070 | if (DI == DistanceMap.end()) |
| 1071 | // Must be created from unfolded load. Don't waste time trying this. |
| 1072 | return false; |
| 1073 | |
| 1074 | MachineInstr *KillMI = findLocalKill(Reg, MBB, mi, MRI, DistanceMap); |
| 1075 | if (!KillMI || KillMI->isCopy() || KillMI->isCopyLike()) |
| 1076 | // Don't mess with copies, they may be coalesced later. |
| 1077 | return false; |
| 1078 | |
| 1079 | unsigned DstReg; |
| 1080 | if (isTwoAddrUse(*KillMI, Reg, DstReg)) |
| 1081 | return false; |
| 1082 | |
Evan Cheng | f178418 | 2011-11-15 06:26:51 +0000 | [diff] [blame] | 1083 | bool SeenStore = true; |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1084 | if (!KillMI->isSafeToMove(TII, AA, SeenStore)) |
| 1085 | return false; |
| 1086 | |
| 1087 | SmallSet<unsigned, 2> Uses; |
| 1088 | SmallSet<unsigned, 2> Kills; |
| 1089 | SmallSet<unsigned, 2> Defs; |
| 1090 | SmallSet<unsigned, 2> LiveDefs; |
| 1091 | for (unsigned i = 0, e = KillMI->getNumOperands(); i != e; ++i) { |
| 1092 | const MachineOperand &MO = KillMI->getOperand(i); |
| 1093 | if (!MO.isReg()) |
| 1094 | continue; |
| 1095 | unsigned MOReg = MO.getReg(); |
| 1096 | if (MO.isUse()) { |
| 1097 | if (!MOReg) |
| 1098 | continue; |
| 1099 | if (isDefTooClose(MOReg, DI->second, MI, MBB)) |
| 1100 | return false; |
| 1101 | Uses.insert(MOReg); |
| 1102 | if (MO.isKill() && MOReg != Reg) |
| 1103 | Kills.insert(MOReg); |
| 1104 | } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) { |
| 1105 | Defs.insert(MOReg); |
| 1106 | if (!MO.isDead()) |
| 1107 | LiveDefs.insert(MOReg); |
| 1108 | } |
| 1109 | } |
| 1110 | |
| 1111 | // Check if the reschedule will not break depedencies. |
| 1112 | unsigned NumVisited = 0; |
| 1113 | MachineBasicBlock::iterator KillPos = KillMI; |
| 1114 | for (MachineBasicBlock::iterator I = mi; I != KillPos; ++I) { |
| 1115 | MachineInstr *OtherMI = I; |
| 1116 | // DBG_VALUE cannot be counted against the limit. |
| 1117 | if (OtherMI->isDebugValue()) |
| 1118 | continue; |
| 1119 | if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. |
| 1120 | return false; |
| 1121 | ++NumVisited; |
| 1122 | const MCInstrDesc &MCID = OtherMI->getDesc(); |
| 1123 | if (MCID.hasUnmodeledSideEffects() || MCID.isCall() || MCID.isBranch() || |
| 1124 | MCID.isTerminator()) |
| 1125 | // Don't move pass calls, etc. |
| 1126 | return false; |
Evan Cheng | ae7db7a | 2011-11-16 03:05:12 +0000 | [diff] [blame] | 1127 | SmallVector<unsigned, 2> OtherDefs; |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1128 | for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { |
| 1129 | const MachineOperand &MO = OtherMI->getOperand(i); |
| 1130 | if (!MO.isReg()) |
| 1131 | continue; |
| 1132 | unsigned MOReg = MO.getReg(); |
| 1133 | if (!MOReg) |
| 1134 | continue; |
| 1135 | if (MO.isUse()) { |
| 1136 | if (Defs.count(MOReg)) |
| 1137 | // Moving KillMI can clobber the physical register if the def has |
| 1138 | // not been seen. |
| 1139 | return false; |
| 1140 | if (Kills.count(MOReg)) |
| 1141 | // Don't want to extend other live ranges and update kills. |
| 1142 | return false; |
| 1143 | } else { |
Evan Cheng | ae7db7a | 2011-11-16 03:05:12 +0000 | [diff] [blame] | 1144 | OtherDefs.push_back(MOReg); |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1145 | } |
| 1146 | } |
Evan Cheng | ae7db7a | 2011-11-16 03:05:12 +0000 | [diff] [blame] | 1147 | |
| 1148 | for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) { |
| 1149 | unsigned MOReg = OtherDefs[i]; |
| 1150 | if (Uses.count(MOReg)) |
| 1151 | return false; |
| 1152 | if (TargetRegisterInfo::isPhysicalRegister(MOReg) && |
| 1153 | LiveDefs.count(MOReg)) |
| 1154 | return false; |
| 1155 | // Physical register def is seen. |
| 1156 | Defs.erase(MOReg); |
| 1157 | } |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1158 | } |
| 1159 | |
| 1160 | // Move the old kill above MI, don't forget to move debug info as well. |
| 1161 | MachineBasicBlock::iterator InsertPos = mi; |
Evan Cheng | 8aee7d8 | 2011-11-14 21:11:15 +0000 | [diff] [blame] | 1162 | while (InsertPos != MBB->begin() && llvm::prior(InsertPos)->isDebugValue()) |
| 1163 | --InsertPos; |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1164 | MachineBasicBlock::iterator From = KillMI; |
| 1165 | MachineBasicBlock::iterator To = llvm::next(From); |
| 1166 | while (llvm::prior(From)->isDebugValue()) |
| 1167 | --From; |
| 1168 | MBB->splice(InsertPos, MBB, From, To); |
| 1169 | |
Evan Cheng | 2bee6a8 | 2011-11-16 03:33:08 +0000 | [diff] [blame] | 1170 | nmi = llvm::prior(InsertPos); // Backtrack so we process the moved instr. |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1171 | DistanceMap.erase(DI); |
| 1172 | |
| 1173 | if (LV) { |
| 1174 | // Update live variables |
| 1175 | LV->removeVirtualRegisterKilled(Reg, KillMI); |
| 1176 | LV->addVirtualRegisterKilled(Reg, MI); |
| 1177 | } else { |
| 1178 | for (unsigned i = 0, e = KillMI->getNumOperands(); i != e; ++i) { |
| 1179 | MachineOperand &MO = KillMI->getOperand(i); |
| 1180 | if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) |
| 1181 | continue; |
| 1182 | MO.setIsKill(false); |
| 1183 | } |
| 1184 | MI->addRegisterKilled(Reg, 0); |
| 1185 | } |
| 1186 | return true; |
| 1187 | } |
| 1188 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1189 | /// TryInstructionTransform - For the case where an instruction has a single |
| 1190 | /// pair of tied register operands, attempt some transformations that may |
| 1191 | /// either eliminate the tied operands or improve the opportunities for |
| 1192 | /// coalescing away the register copy. Returns true if the tied operands |
| 1193 | /// are eliminated altogether. |
| 1194 | bool TwoAddressInstructionPass:: |
| 1195 | TryInstructionTransform(MachineBasicBlock::iterator &mi, |
| 1196 | MachineBasicBlock::iterator &nmi, |
| 1197 | MachineFunction::iterator &mbbi, |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 1198 | unsigned SrcIdx, unsigned DstIdx, unsigned Dist, |
| 1199 | SmallPtrSet<MachineInstr*, 8> &Processed) { |
Evan Cheng | c3aa7c5 | 2011-11-16 18:44:48 +0000 | [diff] [blame] | 1200 | if (OptLevel == CodeGenOpt::None) |
| 1201 | return false; |
| 1202 | |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1203 | MachineInstr &MI = *mi; |
| 1204 | const MCInstrDesc &MCID = MI.getDesc(); |
| 1205 | unsigned regA = MI.getOperand(DstIdx).getReg(); |
| 1206 | unsigned regB = MI.getOperand(SrcIdx).getReg(); |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1207 | |
| 1208 | assert(TargetRegisterInfo::isVirtualRegister(regB) && |
| 1209 | "cannot make instruction into two-address form"); |
| 1210 | |
| 1211 | // If regA is dead and the instruction can be deleted, just delete |
| 1212 | // it so it doesn't clobber regB. |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1213 | bool regBKilled = isKilled(MI, regB, MRI, TII); |
| 1214 | if (!regBKilled && MI.getOperand(DstIdx).isDead() && |
Jakob Stoklund Olesen | 0b25ae1 | 2009-11-18 21:33:35 +0000 | [diff] [blame] | 1215 | DeleteUnusedInstr(mi, nmi, mbbi, Dist)) { |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1216 | ++NumDeletes; |
| 1217 | return true; // Done with this instruction. |
| 1218 | } |
| 1219 | |
| 1220 | // Check if it is profitable to commute the operands. |
| 1221 | unsigned SrcOp1, SrcOp2; |
| 1222 | unsigned regC = 0; |
| 1223 | unsigned regCIdx = ~0U; |
| 1224 | bool TryCommute = false; |
| 1225 | bool AggressiveCommute = false; |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1226 | if (MCID.isCommutable() && MI.getNumOperands() >= 3 && |
| 1227 | TII->findCommutedOpIndices(&MI, SrcOp1, SrcOp2)) { |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1228 | if (SrcIdx == SrcOp1) |
| 1229 | regCIdx = SrcOp2; |
| 1230 | else if (SrcIdx == SrcOp2) |
| 1231 | regCIdx = SrcOp1; |
| 1232 | |
| 1233 | if (regCIdx != ~0U) { |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1234 | regC = MI.getOperand(regCIdx).getReg(); |
| 1235 | if (!regBKilled && isKilled(MI, regC, MRI, TII)) |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1236 | // If C dies but B does not, swap the B and C operands. |
| 1237 | // This makes the live ranges of A and C joinable. |
| 1238 | TryCommute = true; |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1239 | else if (isProfitableToCommute(regB, regC, &MI, mbbi, Dist)) { |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1240 | TryCommute = true; |
| 1241 | AggressiveCommute = true; |
| 1242 | } |
| 1243 | } |
| 1244 | } |
| 1245 | |
| 1246 | // If it's profitable to commute, try to do so. |
| 1247 | if (TryCommute && CommuteInstruction(mi, mbbi, regB, regC, Dist)) { |
| 1248 | ++NumCommuted; |
| 1249 | if (AggressiveCommute) |
| 1250 | ++NumAggrCommuted; |
| 1251 | return false; |
| 1252 | } |
| 1253 | |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1254 | // If there is one more use of regB later in the same MBB, consider |
| 1255 | // re-schedule this MI below it. |
| 1256 | if (RescheduleMIBelowKill(mbbi, mi, nmi, regB)) { |
| 1257 | ++NumReSchedDowns; |
| 1258 | return true; |
| 1259 | } |
| 1260 | |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 1261 | if (TargetRegisterInfo::isVirtualRegister(regA)) |
| 1262 | ScanUses(regA, &*mbbi, Processed); |
| 1263 | |
Evan Cheng | e837dea | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 1264 | if (MCID.isConvertibleTo3Addr()) { |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1265 | // This instruction is potentially convertible to a true |
| 1266 | // three-address instruction. Check if it is profitable. |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 1267 | if (!regBKilled || isProfitableToConv3Addr(regA, regB)) { |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1268 | // Try to convert it. |
Evan Cheng | 4d96c63 | 2011-02-10 02:20:55 +0000 | [diff] [blame] | 1269 | if (ConvertInstTo3Addr(mi, nmi, mbbi, regA, regB, Dist)) { |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1270 | ++NumConvertedTo3Addr; |
| 1271 | return true; // Done with this instruction. |
| 1272 | } |
| 1273 | } |
| 1274 | } |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1275 | |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1276 | // If there is one more use of regB later in the same MBB, consider |
| 1277 | // re-schedule it before this MI if it's legal. |
| 1278 | if (RescheduleKillAboveMI(mbbi, mi, nmi, regB)) { |
| 1279 | ++NumReSchedUps; |
| 1280 | return true; |
| 1281 | } |
| 1282 | |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1283 | // If this is an instruction with a load folded into it, try unfolding |
| 1284 | // the load, e.g. avoid this: |
| 1285 | // movq %rdx, %rcx |
| 1286 | // addq (%rax), %rcx |
| 1287 | // in favor of this: |
| 1288 | // movq (%rax), %rcx |
| 1289 | // addq %rdx, %rcx |
| 1290 | // because it's preferable to schedule a load than a register copy. |
Evan Cheng | e837dea | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 1291 | if (MCID.mayLoad() && !regBKilled) { |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1292 | // Determine if a load can be unfolded. |
| 1293 | unsigned LoadRegIndex; |
| 1294 | unsigned NewOpc = |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1295 | TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1296 | /*UnfoldLoad=*/true, |
| 1297 | /*UnfoldStore=*/false, |
| 1298 | &LoadRegIndex); |
| 1299 | if (NewOpc != 0) { |
Evan Cheng | e837dea | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 1300 | const MCInstrDesc &UnfoldMCID = TII->get(NewOpc); |
| 1301 | if (UnfoldMCID.getNumDefs() == 1) { |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1302 | MachineFunction &MF = *mbbi->getParent(); |
| 1303 | |
| 1304 | // Unfold the load. |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1305 | DEBUG(dbgs() << "2addr: UNFOLDING: " << MI); |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1306 | const TargetRegisterClass *RC = |
Evan Cheng | e837dea | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 1307 | TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI); |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1308 | unsigned Reg = MRI->createVirtualRegister(RC); |
| 1309 | SmallVector<MachineInstr *, 2> NewMIs; |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1310 | if (!TII->unfoldMemoryOperand(MF, &MI, Reg, |
Evan Cheng | 98ec91e | 2010-07-02 20:36:18 +0000 | [diff] [blame] | 1311 | /*UnfoldLoad=*/true,/*UnfoldStore=*/false, |
| 1312 | NewMIs)) { |
| 1313 | DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); |
| 1314 | return false; |
| 1315 | } |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1316 | assert(NewMIs.size() == 2 && |
| 1317 | "Unfolded a load into multiple instructions!"); |
| 1318 | // The load was previously folded, so this is the only use. |
| 1319 | NewMIs[1]->addRegisterKilled(Reg, TRI); |
| 1320 | |
| 1321 | // Tentatively insert the instructions into the block so that they |
| 1322 | // look "normal" to the transformation logic. |
| 1323 | mbbi->insert(mi, NewMIs[0]); |
| 1324 | mbbi->insert(mi, NewMIs[1]); |
| 1325 | |
| 1326 | DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0] |
| 1327 | << "2addr: NEW INST: " << *NewMIs[1]); |
| 1328 | |
| 1329 | // Transform the instruction, now that it no longer has a load. |
| 1330 | unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA); |
| 1331 | unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB); |
| 1332 | MachineBasicBlock::iterator NewMI = NewMIs[1]; |
| 1333 | bool TransformSuccess = |
| 1334 | TryInstructionTransform(NewMI, mi, mbbi, |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 1335 | NewSrcIdx, NewDstIdx, Dist, Processed); |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1336 | if (TransformSuccess || |
| 1337 | NewMIs[1]->getOperand(NewSrcIdx).isKill()) { |
| 1338 | // Success, or at least we made an improvement. Keep the unfolded |
| 1339 | // instructions and discard the original. |
| 1340 | if (LV) { |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1341 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
| 1342 | MachineOperand &MO = MI.getOperand(i); |
Jakob Stoklund Olesen | c9df025 | 2011-01-10 02:58:51 +0000 | [diff] [blame] | 1343 | if (MO.isReg() && |
Dan Gohman | 7aa7bc7 | 2010-06-22 00:32:04 +0000 | [diff] [blame] | 1344 | TargetRegisterInfo::isVirtualRegister(MO.getReg())) { |
| 1345 | if (MO.isUse()) { |
Dan Gohman | cc1ca98 | 2010-06-22 02:07:21 +0000 | [diff] [blame] | 1346 | if (MO.isKill()) { |
| 1347 | if (NewMIs[0]->killsRegister(MO.getReg())) |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1348 | LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[0]); |
Dan Gohman | cc1ca98 | 2010-06-22 02:07:21 +0000 | [diff] [blame] | 1349 | else { |
| 1350 | assert(NewMIs[1]->killsRegister(MO.getReg()) && |
| 1351 | "Kill missing after load unfold!"); |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1352 | LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[1]); |
Dan Gohman | cc1ca98 | 2010-06-22 02:07:21 +0000 | [diff] [blame] | 1353 | } |
| 1354 | } |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1355 | } else if (LV->removeVirtualRegisterDead(MO.getReg(), &MI)) { |
Dan Gohman | cc1ca98 | 2010-06-22 02:07:21 +0000 | [diff] [blame] | 1356 | if (NewMIs[1]->registerDefIsDead(MO.getReg())) |
| 1357 | LV->addVirtualRegisterDead(MO.getReg(), NewMIs[1]); |
| 1358 | else { |
| 1359 | assert(NewMIs[0]->registerDefIsDead(MO.getReg()) && |
| 1360 | "Dead flag missing after load unfold!"); |
| 1361 | LV->addVirtualRegisterDead(MO.getReg(), NewMIs[0]); |
| 1362 | } |
| 1363 | } |
Dan Gohman | 7aa7bc7 | 2010-06-22 00:32:04 +0000 | [diff] [blame] | 1364 | } |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1365 | } |
| 1366 | LV->addVirtualRegisterKilled(Reg, NewMIs[1]); |
| 1367 | } |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1368 | MI.eraseFromParent(); |
Dan Gohman | 584fedf | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1369 | mi = NewMIs[1]; |
| 1370 | if (TransformSuccess) |
| 1371 | return true; |
| 1372 | } else { |
| 1373 | // Transforming didn't eliminate the tie and didn't lead to an |
| 1374 | // improvement. Clean up the unfolded instructions and keep the |
| 1375 | // original. |
| 1376 | DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); |
| 1377 | NewMIs[0]->eraseFromParent(); |
| 1378 | NewMIs[1]->eraseFromParent(); |
| 1379 | } |
| 1380 | } |
| 1381 | } |
| 1382 | } |
| 1383 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1384 | return false; |
| 1385 | } |
| 1386 | |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 1387 | /// runOnMachineFunction - Reduce two-address instructions to two operands. |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1388 | /// |
Chris Lattner | 163c1e7 | 2004-01-31 21:14:04 +0000 | [diff] [blame] | 1389 | bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { |
David Greene | eb00b18 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 1390 | DEBUG(dbgs() << "Machine Function\n"); |
Misha Brukman | 75fa4e4 | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 1391 | const TargetMachine &TM = MF.getTarget(); |
Evan Cheng | 875357d | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 1392 | MRI = &MF.getRegInfo(); |
| 1393 | TII = TM.getInstrInfo(); |
| 1394 | TRI = TM.getRegisterInfo(); |
Evan Cheng | 2a4410d | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1395 | InstrItins = TM.getInstrItineraryData(); |
Duncan Sands | 1465d61 | 2009-01-28 13:14:17 +0000 | [diff] [blame] | 1396 | LV = getAnalysisIfAvailable<LiveVariables>(); |
Dan Gohman | a70dca1 | 2009-10-09 23:27:56 +0000 | [diff] [blame] | 1397 | AA = &getAnalysis<AliasAnalysis>(); |
Evan Cheng | c3aa7c5 | 2011-11-16 18:44:48 +0000 | [diff] [blame] | 1398 | OptLevel = TM.getOptLevel(); |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1399 | |
Misha Brukman | 75fa4e4 | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 1400 | bool MadeChange = false; |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1401 | |
David Greene | eb00b18 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 1402 | DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n"); |
| 1403 | DEBUG(dbgs() << "********** Function: " |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 1404 | << MF.getFunction()->getName() << '\n'); |
Alkis Evlogimenos | 3a9986f | 2004-02-18 00:35:06 +0000 | [diff] [blame] | 1405 | |
Jakob Stoklund Olesen | 73e7dce | 2011-07-29 22:51:22 +0000 | [diff] [blame] | 1406 | // This pass takes the function out of SSA form. |
| 1407 | MRI->leaveSSA(); |
| 1408 | |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 1409 | // ReMatRegs - Keep track of the registers whose def's are remat'ed. |
Jakob Stoklund Olesen | 00f93fc | 2011-01-09 03:45:44 +0000 | [diff] [blame] | 1410 | BitVector ReMatRegs(MRI->getNumVirtRegs()); |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 1411 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1412 | typedef DenseMap<unsigned, SmallVector<std::pair<unsigned, unsigned>, 4> > |
| 1413 | TiedOperandMap; |
| 1414 | TiedOperandMap TiedOperands(4); |
| 1415 | |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 1416 | SmallPtrSet<MachineInstr*, 8> Processed; |
Misha Brukman | 75fa4e4 | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 1417 | for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end(); |
| 1418 | mbbi != mbbe; ++mbbi) { |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 1419 | unsigned Dist = 0; |
| 1420 | DistanceMap.clear(); |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 1421 | SrcRegMap.clear(); |
| 1422 | DstRegMap.clear(); |
| 1423 | Processed.clear(); |
Misha Brukman | 75fa4e4 | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 1424 | for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end(); |
Evan Cheng | 7a963fa | 2008-03-27 01:27:25 +0000 | [diff] [blame] | 1425 | mi != me; ) { |
Chris Lattner | 7896c9f | 2009-12-03 00:50:42 +0000 | [diff] [blame] | 1426 | MachineBasicBlock::iterator nmi = llvm::next(mi); |
Dale Johannesen | b8ff934 | 2010-02-10 21:47:48 +0000 | [diff] [blame] | 1427 | if (mi->isDebugValue()) { |
| 1428 | mi = nmi; |
| 1429 | continue; |
| 1430 | } |
Evan Cheng | f1250ee | 2010-03-23 20:36:12 +0000 | [diff] [blame] | 1431 | |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1432 | // Remember REG_SEQUENCE instructions, we'll deal with them later. |
| 1433 | if (mi->isRegSequence()) |
| 1434 | RegSequences.push_back(&*mi); |
| 1435 | |
Evan Cheng | e837dea | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 1436 | const MCInstrDesc &MCID = mi->getDesc(); |
Evan Cheng | 360c2dd | 2006-11-01 23:06:55 +0000 | [diff] [blame] | 1437 | bool FirstTied = true; |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 1438 | |
Evan Cheng | 7543e58 | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 1439 | DistanceMap.insert(std::make_pair(mi, ++Dist)); |
Evan Cheng | 870b807 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 1440 | |
| 1441 | ProcessCopy(&*mi, &*mbbi, Processed); |
| 1442 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1443 | // First scan through all the tied register uses in this instruction |
| 1444 | // and record a list of pairs of tied operands for each register. |
Chris Lattner | 518bb53 | 2010-02-09 19:54:29 +0000 | [diff] [blame] | 1445 | unsigned NumOps = mi->isInlineAsm() |
Evan Cheng | e837dea | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 1446 | ? mi->getNumOperands() : MCID.getNumOperands(); |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1447 | for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) { |
| 1448 | unsigned DstIdx = 0; |
| 1449 | if (!mi->isRegTiedToDefOperand(SrcIdx, &DstIdx)) |
Evan Cheng | 360c2dd | 2006-11-01 23:06:55 +0000 | [diff] [blame] | 1450 | continue; |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1451 | |
Evan Cheng | 360c2dd | 2006-11-01 23:06:55 +0000 | [diff] [blame] | 1452 | if (FirstTied) { |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1453 | FirstTied = false; |
Evan Cheng | 360c2dd | 2006-11-01 23:06:55 +0000 | [diff] [blame] | 1454 | ++NumTwoAddressInstrs; |
David Greene | eb00b18 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 1455 | DEBUG(dbgs() << '\t' << *mi); |
Evan Cheng | 360c2dd | 2006-11-01 23:06:55 +0000 | [diff] [blame] | 1456 | } |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 1457 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1458 | assert(mi->getOperand(SrcIdx).isReg() && |
| 1459 | mi->getOperand(SrcIdx).getReg() && |
| 1460 | mi->getOperand(SrcIdx).isUse() && |
| 1461 | "two address instruction invalid"); |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1462 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1463 | unsigned regB = mi->getOperand(SrcIdx).getReg(); |
Benjamin Kramer | 4e39f8f | 2011-06-18 13:53:47 +0000 | [diff] [blame] | 1464 | TiedOperands[regB].push_back(std::make_pair(SrcIdx, DstIdx)); |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1465 | } |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1466 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1467 | // Now iterate over the information collected above. |
| 1468 | for (TiedOperandMap::iterator OI = TiedOperands.begin(), |
| 1469 | OE = TiedOperands.end(); OI != OE; ++OI) { |
| 1470 | SmallVector<std::pair<unsigned, unsigned>, 4> &TiedPairs = OI->second; |
Evan Cheng | 360c2dd | 2006-11-01 23:06:55 +0000 | [diff] [blame] | 1471 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1472 | // If the instruction has a single pair of tied operands, try some |
| 1473 | // transformations that may either eliminate the tied operands or |
| 1474 | // improve the opportunities for coalescing away the register copy. |
| 1475 | if (TiedOperands.size() == 1 && TiedPairs.size() == 1) { |
| 1476 | unsigned SrcIdx = TiedPairs[0].first; |
| 1477 | unsigned DstIdx = TiedPairs[0].second; |
Bob Wilson | 4344979 | 2009-08-31 21:54:55 +0000 | [diff] [blame] | 1478 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1479 | // If the registers are already equal, nothing needs to be done. |
| 1480 | if (mi->getOperand(SrcIdx).getReg() == |
| 1481 | mi->getOperand(DstIdx).getReg()) |
| 1482 | break; // Done with this instruction. |
| 1483 | |
Evan Cheng | f06e6c2 | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 1484 | if (TryInstructionTransform(mi, nmi, mbbi, SrcIdx, DstIdx, Dist, |
| 1485 | Processed)) |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1486 | break; // The tied operands have been eliminated. |
| 1487 | } |
| 1488 | |
Cameron Zwarich | aaa5f14 | 2011-06-07 23:54:00 +0000 | [diff] [blame] | 1489 | bool IsEarlyClobber = false; |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1490 | bool RemovedKillFlag = false; |
| 1491 | bool AllUsesCopied = true; |
| 1492 | unsigned LastCopiedReg = 0; |
| 1493 | unsigned regB = OI->first; |
| 1494 | for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { |
| 1495 | unsigned SrcIdx = TiedPairs[tpi].first; |
| 1496 | unsigned DstIdx = TiedPairs[tpi].second; |
Cameron Zwarich | aaa5f14 | 2011-06-07 23:54:00 +0000 | [diff] [blame] | 1497 | |
| 1498 | const MachineOperand &DstMO = mi->getOperand(DstIdx); |
| 1499 | unsigned regA = DstMO.getReg(); |
| 1500 | IsEarlyClobber |= DstMO.isEarlyClobber(); |
| 1501 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1502 | // Grab regB from the instruction because it may have changed if the |
| 1503 | // instruction was commuted. |
| 1504 | regB = mi->getOperand(SrcIdx).getReg(); |
| 1505 | |
| 1506 | if (regA == regB) { |
| 1507 | // The register is tied to multiple destinations (or else we would |
| 1508 | // not have continued this far), but this use of the register |
| 1509 | // already matches the tied destination. Leave it. |
| 1510 | AllUsesCopied = false; |
| 1511 | continue; |
| 1512 | } |
| 1513 | LastCopiedReg = regA; |
| 1514 | |
| 1515 | assert(TargetRegisterInfo::isVirtualRegister(regB) && |
| 1516 | "cannot make instruction into two-address form"); |
Chris Lattner | 6b50767 | 2004-01-31 21:21:43 +0000 | [diff] [blame] | 1517 | |
Chris Lattner | 1e31363 | 2004-07-21 23:17:57 +0000 | [diff] [blame] | 1518 | #ifndef NDEBUG |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1519 | // First, verify that we don't have a use of "a" in the instruction |
| 1520 | // (a = b + a for example) because our transformation will not |
| 1521 | // work. This should never occur because we are in SSA form. |
| 1522 | for (unsigned i = 0; i != mi->getNumOperands(); ++i) |
| 1523 | assert(i == DstIdx || |
| 1524 | !mi->getOperand(i).isReg() || |
| 1525 | mi->getOperand(i).getReg() != regA); |
Chris Lattner | 1e31363 | 2004-07-21 23:17:57 +0000 | [diff] [blame] | 1526 | #endif |
Alkis Evlogimenos | 14be640 | 2004-02-04 22:17:40 +0000 | [diff] [blame] | 1527 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1528 | // Emit a copy or rematerialize the definition. |
| 1529 | const TargetRegisterClass *rc = MRI->getRegClass(regB); |
| 1530 | MachineInstr *DefMI = MRI->getVRegDef(regB); |
| 1531 | // If it's safe and profitable, remat the definition instead of |
| 1532 | // copying it. |
| 1533 | if (DefMI && |
| 1534 | DefMI->getDesc().isAsCheapAsAMove() && |
Evan Cheng | ac1abde | 2010-03-02 19:03:01 +0000 | [diff] [blame] | 1535 | DefMI->isSafeToReMat(TII, AA, regB) && |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1536 | isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist)){ |
David Greene | eb00b18 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 1537 | DEBUG(dbgs() << "2addr: REMATTING : " << *DefMI << "\n"); |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1538 | unsigned regASubIdx = mi->getOperand(DstIdx).getSubReg(); |
Jakob Stoklund Olesen | 9edf7de | 2010-06-02 22:47:25 +0000 | [diff] [blame] | 1539 | TII->reMaterialize(*mbbi, mi, regA, regASubIdx, DefMI, *TRI); |
Jakob Stoklund Olesen | 00f93fc | 2011-01-09 03:45:44 +0000 | [diff] [blame] | 1540 | ReMatRegs.set(TargetRegisterInfo::virtReg2Index(regB)); |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1541 | ++NumReMats; |
Bob Wilson | 71124f6 | 2009-09-01 04:18:40 +0000 | [diff] [blame] | 1542 | } else { |
Jakob Stoklund Olesen | 92c1f72 | 2010-07-10 19:08:25 +0000 | [diff] [blame] | 1543 | BuildMI(*mbbi, mi, mi->getDebugLoc(), TII->get(TargetOpcode::COPY), |
| 1544 | regA).addReg(regB); |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1545 | } |
| 1546 | |
| 1547 | MachineBasicBlock::iterator prevMI = prior(mi); |
| 1548 | // Update DistanceMap. |
| 1549 | DistanceMap.insert(std::make_pair(prevMI, Dist)); |
| 1550 | DistanceMap[mi] = ++Dist; |
| 1551 | |
David Greene | eb00b18 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 1552 | DEBUG(dbgs() << "\t\tprepend:\t" << *prevMI); |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1553 | |
| 1554 | MachineOperand &MO = mi->getOperand(SrcIdx); |
| 1555 | assert(MO.isReg() && MO.getReg() == regB && MO.isUse() && |
| 1556 | "inconsistent operand info for 2-reg pass"); |
| 1557 | if (MO.isKill()) { |
| 1558 | MO.setIsKill(false); |
| 1559 | RemovedKillFlag = true; |
| 1560 | } |
| 1561 | MO.setReg(regA); |
| 1562 | } |
| 1563 | |
| 1564 | if (AllUsesCopied) { |
Cameron Zwarich | aaa5f14 | 2011-06-07 23:54:00 +0000 | [diff] [blame] | 1565 | if (!IsEarlyClobber) { |
| 1566 | // Replace other (un-tied) uses of regB with LastCopiedReg. |
| 1567 | for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { |
| 1568 | MachineOperand &MO = mi->getOperand(i); |
| 1569 | if (MO.isReg() && MO.getReg() == regB && MO.isUse()) { |
| 1570 | if (MO.isKill()) { |
| 1571 | MO.setIsKill(false); |
| 1572 | RemovedKillFlag = true; |
| 1573 | } |
| 1574 | MO.setReg(LastCopiedReg); |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1575 | } |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1576 | } |
| 1577 | } |
| 1578 | |
| 1579 | // Update live variables for regB. |
| 1580 | if (RemovedKillFlag && LV && LV->getVarInfo(regB).removeKill(mi)) |
| 1581 | LV->addVirtualRegisterKilled(regB, prior(mi)); |
| 1582 | |
| 1583 | } else if (RemovedKillFlag) { |
| 1584 | // Some tied uses of regB matched their destination registers, so |
| 1585 | // regB is still used in this instruction, but a kill flag was |
| 1586 | // removed from a different tied use of regB, so now we need to add |
| 1587 | // a kill flag to one of the remaining uses of regB. |
| 1588 | for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { |
| 1589 | MachineOperand &MO = mi->getOperand(i); |
| 1590 | if (MO.isReg() && MO.getReg() == regB && MO.isUse()) { |
| 1591 | MO.setIsKill(true); |
| 1592 | break; |
Bob Wilson | 71124f6 | 2009-09-01 04:18:40 +0000 | [diff] [blame] | 1593 | } |
| 1594 | } |
Bob Wilson | 4344979 | 2009-08-31 21:54:55 +0000 | [diff] [blame] | 1595 | } |
Evan Cheng | 68fc2da | 2010-06-09 19:26:01 +0000 | [diff] [blame] | 1596 | |
| 1597 | // Schedule the source copy / remat inserted to form two-address |
| 1598 | // instruction. FIXME: Does it matter the distance map may not be |
| 1599 | // accurate after it's scheduled? |
| 1600 | TII->scheduleTwoAddrSource(prior(mi), mi, *TRI); |
| 1601 | |
Bob Wilson | 4344979 | 2009-08-31 21:54:55 +0000 | [diff] [blame] | 1602 | MadeChange = true; |
| 1603 | |
David Greene | eb00b18 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 1604 | DEBUG(dbgs() << "\t\trewrite to:\t" << *mi); |
Misha Brukman | 75fa4e4 | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 1605 | } |
Bill Wendling | 637980e | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 1606 | |
Jakob Stoklund Olesen | ed2185e | 2010-07-06 23:26:25 +0000 | [diff] [blame] | 1607 | // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form. |
| 1608 | if (mi->isInsertSubreg()) { |
| 1609 | // From %reg = INSERT_SUBREG %reg, %subreg, subidx |
| 1610 | // To %reg:subidx = COPY %subreg |
| 1611 | unsigned SubIdx = mi->getOperand(3).getImm(); |
| 1612 | mi->RemoveOperand(3); |
| 1613 | assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx"); |
| 1614 | mi->getOperand(0).setSubReg(SubIdx); |
| 1615 | mi->RemoveOperand(1); |
| 1616 | mi->setDesc(TII->get(TargetOpcode::COPY)); |
| 1617 | DEBUG(dbgs() << "\t\tconvert to:\t" << *mi); |
| 1618 | } |
| 1619 | |
Bob Wilson | cc80df9 | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1620 | // Clear TiedOperands here instead of at the top of the loop |
| 1621 | // since most instructions do not have tied operands. |
| 1622 | TiedOperands.clear(); |
Evan Cheng | 7a963fa | 2008-03-27 01:27:25 +0000 | [diff] [blame] | 1623 | mi = nmi; |
Misha Brukman | 75fa4e4 | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 1624 | } |
| 1625 | } |
| 1626 | |
Evan Cheng | 601ca4b | 2008-06-25 01:16:38 +0000 | [diff] [blame] | 1627 | // Some remat'ed instructions are dead. |
Jakob Stoklund Olesen | 00f93fc | 2011-01-09 03:45:44 +0000 | [diff] [blame] | 1628 | for (int i = ReMatRegs.find_first(); i != -1; i = ReMatRegs.find_next(i)) { |
| 1629 | unsigned VReg = TargetRegisterInfo::index2VirtReg(i); |
Evan Cheng | f1250ee | 2010-03-23 20:36:12 +0000 | [diff] [blame] | 1630 | if (MRI->use_nodbg_empty(VReg)) { |
Evan Cheng | 601ca4b | 2008-06-25 01:16:38 +0000 | [diff] [blame] | 1631 | MachineInstr *DefMI = MRI->getVRegDef(VReg); |
| 1632 | DefMI->eraseFromParent(); |
Bill Wendling | a16157a | 2008-05-26 05:49:49 +0000 | [diff] [blame] | 1633 | } |
Bill Wendling | 48f7f23 | 2008-05-26 05:18:34 +0000 | [diff] [blame] | 1634 | } |
| 1635 | |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1636 | // Eliminate REG_SEQUENCE instructions. Their whole purpose was to preseve |
| 1637 | // SSA form. It's now safe to de-SSA. |
| 1638 | MadeChange |= EliminateRegSequences(); |
| 1639 | |
Misha Brukman | 75fa4e4 | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 1640 | return MadeChange; |
Alkis Evlogimenos | 71499de | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1641 | } |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1642 | |
| 1643 | static void UpdateRegSequenceSrcs(unsigned SrcReg, |
Evan Cheng | 53c779b | 2010-05-17 20:57:12 +0000 | [diff] [blame] | 1644 | unsigned DstReg, unsigned SubIdx, |
Jakob Stoklund Olesen | 5a0d4fc | 2010-05-29 00:14:14 +0000 | [diff] [blame] | 1645 | MachineRegisterInfo *MRI, |
| 1646 | const TargetRegisterInfo &TRI) { |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1647 | for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg), |
Evan Cheng | 3ae56bc | 2010-05-12 01:27:49 +0000 | [diff] [blame] | 1648 | RE = MRI->reg_end(); RI != RE; ) { |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1649 | MachineOperand &MO = RI.getOperand(); |
| 1650 | ++RI; |
Jakob Stoklund Olesen | 5a0d4fc | 2010-05-29 00:14:14 +0000 | [diff] [blame] | 1651 | MO.substVirtReg(DstReg, SubIdx, TRI); |
Evan Cheng | 53c779b | 2010-05-17 20:57:12 +0000 | [diff] [blame] | 1652 | } |
| 1653 | } |
| 1654 | |
| 1655 | /// CoalesceExtSubRegs - If a number of sources of the REG_SEQUENCE are |
| 1656 | /// EXTRACT_SUBREG from the same register and to the same virtual register |
| 1657 | /// with different sub-register indices, attempt to combine the |
| 1658 | /// EXTRACT_SUBREGs and pre-coalesce them. e.g. |
| 1659 | /// %reg1026<def> = VLDMQ %reg1025<kill>, 260, pred:14, pred:%reg0 |
| 1660 | /// %reg1029:6<def> = EXTRACT_SUBREG %reg1026, 6 |
| 1661 | /// %reg1029:5<def> = EXTRACT_SUBREG %reg1026<kill>, 5 |
| 1662 | /// Since D subregs 5, 6 can combine to a Q register, we can coalesce |
| 1663 | /// reg1026 to reg1029. |
| 1664 | void |
| 1665 | TwoAddressInstructionPass::CoalesceExtSubRegs(SmallVector<unsigned,4> &Srcs, |
| 1666 | unsigned DstReg) { |
| 1667 | SmallSet<unsigned, 4> Seen; |
| 1668 | for (unsigned i = 0, e = Srcs.size(); i != e; ++i) { |
| 1669 | unsigned SrcReg = Srcs[i]; |
| 1670 | if (!Seen.insert(SrcReg)) |
| 1671 | continue; |
| 1672 | |
Bob Wilson | 26bf8f9 | 2010-06-03 23:53:58 +0000 | [diff] [blame] | 1673 | // Check that the instructions are all in the same basic block. |
| 1674 | MachineInstr *SrcDefMI = MRI->getVRegDef(SrcReg); |
| 1675 | MachineInstr *DstDefMI = MRI->getVRegDef(DstReg); |
| 1676 | if (SrcDefMI->getParent() != DstDefMI->getParent()) |
| 1677 | continue; |
| 1678 | |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 1679 | // If there are no other uses than copies which feed into |
Evan Cheng | 53c779b | 2010-05-17 20:57:12 +0000 | [diff] [blame] | 1680 | // the reg_sequence, then we might be able to coalesce them. |
| 1681 | bool CanCoalesce = true; |
Bob Wilson | 4ffd22d | 2010-06-15 17:27:54 +0000 | [diff] [blame] | 1682 | SmallVector<unsigned, 4> SrcSubIndices, DstSubIndices; |
Evan Cheng | 53c779b | 2010-05-17 20:57:12 +0000 | [diff] [blame] | 1683 | for (MachineRegisterInfo::use_nodbg_iterator |
| 1684 | UI = MRI->use_nodbg_begin(SrcReg), |
| 1685 | UE = MRI->use_nodbg_end(); UI != UE; ++UI) { |
| 1686 | MachineInstr *UseMI = &*UI; |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 1687 | if (!UseMI->isCopy() || UseMI->getOperand(0).getReg() != DstReg) { |
Evan Cheng | 53c779b | 2010-05-17 20:57:12 +0000 | [diff] [blame] | 1688 | CanCoalesce = false; |
| 1689 | break; |
| 1690 | } |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 1691 | SrcSubIndices.push_back(UseMI->getOperand(1).getSubReg()); |
Bob Wilson | 4ffd22d | 2010-06-15 17:27:54 +0000 | [diff] [blame] | 1692 | DstSubIndices.push_back(UseMI->getOperand(0).getSubReg()); |
Evan Cheng | 53c779b | 2010-05-17 20:57:12 +0000 | [diff] [blame] | 1693 | } |
| 1694 | |
Bob Wilson | 4ffd22d | 2010-06-15 17:27:54 +0000 | [diff] [blame] | 1695 | if (!CanCoalesce || SrcSubIndices.size() < 2) |
Evan Cheng | 53c779b | 2010-05-17 20:57:12 +0000 | [diff] [blame] | 1696 | continue; |
| 1697 | |
Bob Wilson | 4ffd22d | 2010-06-15 17:27:54 +0000 | [diff] [blame] | 1698 | // Check that the source subregisters can be combined. |
| 1699 | std::sort(SrcSubIndices.begin(), SrcSubIndices.end()); |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1700 | unsigned NewSrcSubIdx = 0; |
Bob Wilson | 4ffd22d | 2010-06-15 17:27:54 +0000 | [diff] [blame] | 1701 | if (!TRI->canCombineSubRegIndices(MRI->getRegClass(SrcReg), SrcSubIndices, |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1702 | NewSrcSubIdx)) |
Bob Wilson | 26bf8f9 | 2010-06-03 23:53:58 +0000 | [diff] [blame] | 1703 | continue; |
| 1704 | |
Bob Wilson | 4ffd22d | 2010-06-15 17:27:54 +0000 | [diff] [blame] | 1705 | // Check that the destination subregisters can also be combined. |
| 1706 | std::sort(DstSubIndices.begin(), DstSubIndices.end()); |
| 1707 | unsigned NewDstSubIdx = 0; |
| 1708 | if (!TRI->canCombineSubRegIndices(MRI->getRegClass(DstReg), DstSubIndices, |
| 1709 | NewDstSubIdx)) |
| 1710 | continue; |
| 1711 | |
| 1712 | // If neither source nor destination can be combined to the full register, |
| 1713 | // just give up. This could be improved if it ever matters. |
| 1714 | if (NewSrcSubIdx != 0 && NewDstSubIdx != 0) |
| 1715 | continue; |
| 1716 | |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1717 | // Now that we know that all the uses are extract_subregs and that those |
| 1718 | // subregs can somehow be combined, scan all the extract_subregs again to |
| 1719 | // make sure the subregs are in the right order and can be composed. |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1720 | MachineInstr *SomeMI = 0; |
| 1721 | CanCoalesce = true; |
| 1722 | for (MachineRegisterInfo::use_nodbg_iterator |
| 1723 | UI = MRI->use_nodbg_begin(SrcReg), |
| 1724 | UE = MRI->use_nodbg_end(); UI != UE; ++UI) { |
| 1725 | MachineInstr *UseMI = &*UI; |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 1726 | assert(UseMI->isCopy()); |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1727 | unsigned DstSubIdx = UseMI->getOperand(0).getSubReg(); |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 1728 | unsigned SrcSubIdx = UseMI->getOperand(1).getSubReg(); |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1729 | assert(DstSubIdx != 0 && "missing subreg from RegSequence elimination"); |
Bob Wilson | 4ffd22d | 2010-06-15 17:27:54 +0000 | [diff] [blame] | 1730 | if ((NewDstSubIdx == 0 && |
| 1731 | TRI->composeSubRegIndices(NewSrcSubIdx, DstSubIdx) != SrcSubIdx) || |
| 1732 | (NewSrcSubIdx == 0 && |
| 1733 | TRI->composeSubRegIndices(NewDstSubIdx, SrcSubIdx) != DstSubIdx)) { |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1734 | CanCoalesce = false; |
| 1735 | break; |
Evan Cheng | 53c779b | 2010-05-17 20:57:12 +0000 | [diff] [blame] | 1736 | } |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1737 | // Keep track of one of the uses. |
| 1738 | SomeMI = UseMI; |
| 1739 | } |
| 1740 | if (!CanCoalesce) |
| 1741 | continue; |
| 1742 | |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 1743 | // Insert a copy to replace the original. |
Jakob Stoklund Olesen | 5c00e07 | 2010-07-08 16:40:15 +0000 | [diff] [blame] | 1744 | MachineInstr *CopyMI = BuildMI(*SomeMI->getParent(), SomeMI, |
| 1745 | SomeMI->getDebugLoc(), |
| 1746 | TII->get(TargetOpcode::COPY)) |
| 1747 | .addReg(DstReg, RegState::Define, NewDstSubIdx) |
| 1748 | .addReg(SrcReg, 0, NewSrcSubIdx); |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1749 | |
| 1750 | // Remove all the old extract instructions. |
| 1751 | for (MachineRegisterInfo::use_nodbg_iterator |
| 1752 | UI = MRI->use_nodbg_begin(SrcReg), |
| 1753 | UE = MRI->use_nodbg_end(); UI != UE; ) { |
| 1754 | MachineInstr *UseMI = &*UI; |
| 1755 | ++UI; |
| 1756 | if (UseMI == CopyMI) |
| 1757 | continue; |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 1758 | assert(UseMI->isCopy()); |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1759 | // Move any kills to the new copy or extract instruction. |
| 1760 | if (UseMI->getOperand(1).isKill()) { |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 1761 | CopyMI->getOperand(1).setIsKill(); |
Bob Wilson | 852a7e3 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 1762 | if (LV) |
| 1763 | // Update live variables |
| 1764 | LV->replaceKillInstruction(SrcReg, UseMI, &*CopyMI); |
| 1765 | } |
| 1766 | UseMI->eraseFromParent(); |
| 1767 | } |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1768 | } |
| 1769 | } |
| 1770 | |
Evan Cheng | c6dcce3 | 2010-05-17 23:24:12 +0000 | [diff] [blame] | 1771 | static bool HasOtherRegSequenceUses(unsigned Reg, MachineInstr *RegSeq, |
| 1772 | MachineRegisterInfo *MRI) { |
| 1773 | for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), |
| 1774 | UE = MRI->use_end(); UI != UE; ++UI) { |
| 1775 | MachineInstr *UseMI = &*UI; |
| 1776 | if (UseMI != RegSeq && UseMI->isRegSequence()) |
| 1777 | return true; |
| 1778 | } |
| 1779 | return false; |
| 1780 | } |
| 1781 | |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1782 | /// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as part |
| 1783 | /// of the de-ssa process. This replaces sources of REG_SEQUENCE as |
| 1784 | /// sub-register references of the register defined by REG_SEQUENCE. e.g. |
| 1785 | /// |
| 1786 | /// %reg1029<def>, %reg1030<def> = VLD1q16 %reg1024<kill>, ... |
| 1787 | /// %reg1031<def> = REG_SEQUENCE %reg1029<kill>, 5, %reg1030<kill>, 6 |
| 1788 | /// => |
| 1789 | /// %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ... |
| 1790 | bool TwoAddressInstructionPass::EliminateRegSequences() { |
| 1791 | if (RegSequences.empty()) |
| 1792 | return false; |
| 1793 | |
| 1794 | for (unsigned i = 0, e = RegSequences.size(); i != e; ++i) { |
| 1795 | MachineInstr *MI = RegSequences[i]; |
| 1796 | unsigned DstReg = MI->getOperand(0).getReg(); |
| 1797 | if (MI->getOperand(0).getSubReg() || |
| 1798 | TargetRegisterInfo::isPhysicalRegister(DstReg) || |
| 1799 | !(MI->getNumOperands() & 1)) { |
| 1800 | DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI); |
| 1801 | llvm_unreachable(0); |
| 1802 | } |
Evan Cheng | 0bcccac | 2010-05-11 00:04:31 +0000 | [diff] [blame] | 1803 | |
Evan Cheng | 44bfdd3 | 2010-05-17 22:09:49 +0000 | [diff] [blame] | 1804 | bool IsImpDef = true; |
Evan Cheng | b990a2f | 2010-05-14 23:21:14 +0000 | [diff] [blame] | 1805 | SmallVector<unsigned, 4> RealSrcs; |
Evan Cheng | 0bcccac | 2010-05-11 00:04:31 +0000 | [diff] [blame] | 1806 | SmallSet<unsigned, 4> Seen; |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1807 | for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) { |
| 1808 | unsigned SrcReg = MI->getOperand(i).getReg(); |
Bob Wilson | 495de3b | 2010-12-17 01:21:12 +0000 | [diff] [blame] | 1809 | unsigned SubIdx = MI->getOperand(i+1).getImm(); |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1810 | if (MI->getOperand(i).getSubReg() || |
| 1811 | TargetRegisterInfo::isPhysicalRegister(SrcReg)) { |
| 1812 | DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI); |
| 1813 | llvm_unreachable(0); |
| 1814 | } |
Evan Cheng | 0bcccac | 2010-05-11 00:04:31 +0000 | [diff] [blame] | 1815 | |
Evan Cheng | 054dbb8 | 2010-05-13 00:00:35 +0000 | [diff] [blame] | 1816 | MachineInstr *DefMI = MRI->getVRegDef(SrcReg); |
Evan Cheng | b990a2f | 2010-05-14 23:21:14 +0000 | [diff] [blame] | 1817 | if (DefMI->isImplicitDef()) { |
| 1818 | DefMI->eraseFromParent(); |
| 1819 | continue; |
| 1820 | } |
Evan Cheng | 44bfdd3 | 2010-05-17 22:09:49 +0000 | [diff] [blame] | 1821 | IsImpDef = false; |
Evan Cheng | b990a2f | 2010-05-14 23:21:14 +0000 | [diff] [blame] | 1822 | |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 1823 | // Remember COPY sources. These might be candidate for coalescing. |
Jakob Stoklund Olesen | c0075cc | 2010-07-10 22:42:53 +0000 | [diff] [blame] | 1824 | if (DefMI->isCopy() && DefMI->getOperand(1).getSubReg()) |
Evan Cheng | b990a2f | 2010-05-14 23:21:14 +0000 | [diff] [blame] | 1825 | RealSrcs.push_back(DefMI->getOperand(1).getReg()); |
| 1826 | |
Jakob Stoklund Olesen | 1e1098c | 2010-07-10 22:42:59 +0000 | [diff] [blame] | 1827 | bool isKill = MI->getOperand(i).isKill(); |
| 1828 | if (!Seen.insert(SrcReg) || MI->getParent() != DefMI->getParent() || |
Bob Wilson | 495de3b | 2010-12-17 01:21:12 +0000 | [diff] [blame] | 1829 | !isKill || HasOtherRegSequenceUses(SrcReg, MI, MRI) || |
| 1830 | !TRI->getMatchingSuperRegClass(MRI->getRegClass(DstReg), |
| 1831 | MRI->getRegClass(SrcReg), SubIdx)) { |
Evan Cheng | 054dbb8 | 2010-05-13 00:00:35 +0000 | [diff] [blame] | 1832 | // REG_SEQUENCE cannot have duplicated operands, add a copy. |
Jakob Stoklund Olesen | 3437352 | 2010-05-19 20:08:00 +0000 | [diff] [blame] | 1833 | // Also add an copy if the source is live-in the block. We don't want |
Evan Cheng | 054dbb8 | 2010-05-13 00:00:35 +0000 | [diff] [blame] | 1834 | // to end up with a partial-redef of a livein, e.g. |
| 1835 | // BB0: |
| 1836 | // reg1051:10<def> = |
| 1837 | // ... |
| 1838 | // BB1: |
| 1839 | // ... = reg1051:10 |
| 1840 | // BB2: |
| 1841 | // reg1051:9<def> = |
| 1842 | // LiveIntervalAnalysis won't like it. |
Jakob Stoklund Olesen | 3437352 | 2010-05-19 20:08:00 +0000 | [diff] [blame] | 1843 | // |
| 1844 | // If the REG_SEQUENCE doesn't kill its source, keeping live variables |
| 1845 | // correctly up to date becomes very difficult. Insert a copy. |
Jakob Stoklund Olesen | e4b9c4f | 2010-08-09 20:19:16 +0000 | [diff] [blame] | 1846 | |
| 1847 | // Defer any kill flag to the last operand using SrcReg. Otherwise, we |
| 1848 | // might insert a COPY that uses SrcReg after is was killed. |
| 1849 | if (isKill) |
| 1850 | for (unsigned j = i + 2; j < e; j += 2) |
| 1851 | if (MI->getOperand(j).getReg() == SrcReg) { |
| 1852 | MI->getOperand(j).setIsKill(); |
| 1853 | isKill = false; |
| 1854 | break; |
| 1855 | } |
| 1856 | |
Evan Cheng | 054dbb8 | 2010-05-13 00:00:35 +0000 | [diff] [blame] | 1857 | MachineBasicBlock::iterator InsertLoc = MI; |
Jakob Stoklund Olesen | 1e1098c | 2010-07-10 22:42:59 +0000 | [diff] [blame] | 1858 | MachineInstr *CopyMI = BuildMI(*MI->getParent(), InsertLoc, |
| 1859 | MI->getDebugLoc(), TII->get(TargetOpcode::COPY)) |
Bob Wilson | 495de3b | 2010-12-17 01:21:12 +0000 | [diff] [blame] | 1860 | .addReg(DstReg, RegState::Define, SubIdx) |
Jakob Stoklund Olesen | 1e1098c | 2010-07-10 22:42:59 +0000 | [diff] [blame] | 1861 | .addReg(SrcReg, getKillRegState(isKill)); |
| 1862 | MI->getOperand(i).setReg(0); |
| 1863 | if (LV && isKill) |
| 1864 | LV->replaceKillInstruction(SrcReg, MI, CopyMI); |
| 1865 | DEBUG(dbgs() << "Inserted: " << *CopyMI); |
Evan Cheng | 0bcccac | 2010-05-11 00:04:31 +0000 | [diff] [blame] | 1866 | } |
| 1867 | } |
| 1868 | |
| 1869 | for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) { |
| 1870 | unsigned SrcReg = MI->getOperand(i).getReg(); |
Jakob Stoklund Olesen | 1e1098c | 2010-07-10 22:42:59 +0000 | [diff] [blame] | 1871 | if (!SrcReg) continue; |
Evan Cheng | 53c779b | 2010-05-17 20:57:12 +0000 | [diff] [blame] | 1872 | unsigned SubIdx = MI->getOperand(i+1).getImm(); |
Jakob Stoklund Olesen | 5a0d4fc | 2010-05-29 00:14:14 +0000 | [diff] [blame] | 1873 | UpdateRegSequenceSrcs(SrcReg, DstReg, SubIdx, MRI, *TRI); |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1874 | } |
| 1875 | |
Evan Cheng | 44bfdd3 | 2010-05-17 22:09:49 +0000 | [diff] [blame] | 1876 | if (IsImpDef) { |
| 1877 | DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF"); |
| 1878 | MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); |
| 1879 | for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) |
| 1880 | MI->RemoveOperand(j); |
| 1881 | } else { |
| 1882 | DEBUG(dbgs() << "Eliminated: " << *MI); |
| 1883 | MI->eraseFromParent(); |
| 1884 | } |
Evan Cheng | b990a2f | 2010-05-14 23:21:14 +0000 | [diff] [blame] | 1885 | |
Jakob Stoklund Olesen | fe181f4 | 2010-06-18 23:10:20 +0000 | [diff] [blame] | 1886 | // Try coalescing some EXTRACT_SUBREG instructions. This can create |
| 1887 | // INSERT_SUBREG instructions that must have <undef> flags added by |
| 1888 | // LiveIntervalAnalysis, so only run it when LiveVariables is available. |
| 1889 | if (LV) |
| 1890 | CoalesceExtSubRegs(RealSrcs, DstReg); |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1891 | } |
| 1892 | |
Evan Cheng | fc6e6a9 | 2010-05-10 21:24:55 +0000 | [diff] [blame] | 1893 | RegSequences.clear(); |
Evan Cheng | 3d720fb | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1894 | return true; |
| 1895 | } |