Alkis Evlogimenos | 725021c | 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 | f3ebc3f | 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 | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
Alkis Evlogimenos | 5e0e671 | 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 | 3274264 | 2004-02-04 22:17:40 +0000 | [diff] [blame] | 19 | // A op= C |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 20 | // |
Alkis Evlogimenos | 3274264 | 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 | d835aa6 | 2004-01-31 21:07:15 +0000 | [diff] [blame] | 27 | // |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 28 | //===----------------------------------------------------------------------===// |
| 29 | |
Chris Lattner | d835aa6 | 2004-01-31 21:07:15 +0000 | [diff] [blame] | 30 | #include "llvm/CodeGen/Passes.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 31 | #include "llvm/ADT/BitVector.h" |
| 32 | #include "llvm/ADT/DenseMap.h" |
| 33 | #include "llvm/ADT/STLExtras.h" |
| 34 | #include "llvm/ADT/SmallSet.h" |
| 35 | #include "llvm/ADT/Statistic.h" |
| 36 | #include "llvm/Analysis/AliasAnalysis.h" |
Jakob Stoklund Olesen | 24bc514 | 2012-08-03 22:58:34 +0000 | [diff] [blame] | 37 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 38 | #include "llvm/CodeGen/LiveVariables.h" |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 39 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 40 | #include "llvm/CodeGen/MachineInstr.h" |
Bob Wilson | a55b887 | 2010-06-15 05:56:31 +0000 | [diff] [blame] | 41 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
Chris Lattner | a10fff5 | 2007-12-31 04:13:23 +0000 | [diff] [blame] | 42 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 43 | #include "llvm/IR/Function.h" |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 44 | #include "llvm/MC/MCInstrItineraries.h" |
Andrew Trick | 608a698 | 2013-04-24 15:54:39 +0000 | [diff] [blame] | 45 | #include "llvm/Support/CommandLine.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 46 | #include "llvm/Support/Debug.h" |
| 47 | #include "llvm/Support/ErrorHandling.h" |
Benjamin Kramer | 799003b | 2015-03-23 19:32:43 +0000 | [diff] [blame] | 48 | #include "llvm/Support/raw_ostream.h" |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 49 | #include "llvm/Target/TargetInstrInfo.h" |
| 50 | #include "llvm/Target/TargetMachine.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 51 | #include "llvm/Target/TargetRegisterInfo.h" |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 52 | #include "llvm/Target/TargetSubtargetInfo.h" |
Eugene Zelenko | ecefe5a | 2016-02-02 18:20:45 +0000 | [diff] [blame^] | 53 | |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 54 | using namespace llvm; |
| 55 | |
Chandler Carruth | 1b9dde0 | 2014-04-22 02:02:50 +0000 | [diff] [blame] | 56 | #define DEBUG_TYPE "twoaddrinstr" |
| 57 | |
Chris Lattner | aee775a | 2006-12-19 22:41:21 +0000 | [diff] [blame] | 58 | STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); |
| 59 | STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 60 | STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted"); |
Chris Lattner | aee775a | 2006-12-19 22:41:21 +0000 | [diff] [blame] | 61 | STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 62 | STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 63 | STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up"); |
| 64 | STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down"); |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 65 | |
Andrew Trick | 608a698 | 2013-04-24 15:54:39 +0000 | [diff] [blame] | 66 | // Temporary flag to disable rescheduling. |
| 67 | static cl::opt<bool> |
| 68 | EnableRescheduling("twoaddr-reschedule", |
Evan Cheng | f85a76f | 2013-05-02 02:07:32 +0000 | [diff] [blame] | 69 | cl::desc("Coalesce copies by rescheduling (default=true)"), |
| 70 | cl::init(true), cl::Hidden); |
Andrew Trick | 608a698 | 2013-04-24 15:54:39 +0000 | [diff] [blame] | 71 | |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 72 | namespace { |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 73 | class TwoAddressInstructionPass : public MachineFunctionPass { |
| 74 | MachineFunction *MF; |
| 75 | const TargetInstrInfo *TII; |
| 76 | const TargetRegisterInfo *TRI; |
| 77 | const InstrItineraryData *InstrItins; |
| 78 | MachineRegisterInfo *MRI; |
| 79 | LiveVariables *LV; |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 80 | LiveIntervals *LIS; |
| 81 | AliasAnalysis *AA; |
| 82 | CodeGenOpt::Level OptLevel; |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 83 | |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 84 | // The current basic block being processed. |
| 85 | MachineBasicBlock *MBB; |
| 86 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 87 | // Keep track the distance of a MI from the start of the current basic block. |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 88 | DenseMap<MachineInstr*, unsigned> DistanceMap; |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 89 | |
Jakob Stoklund Olesen | d788e32 | 2012-10-26 22:06:00 +0000 | [diff] [blame] | 90 | // Set of already processed instructions in the current block. |
| 91 | SmallPtrSet<MachineInstr*, 8> Processed; |
| 92 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 93 | // A map from virtual registers to physical registers which are likely targets |
| 94 | // to be coalesced to due to copies from physical registers to virtual |
| 95 | // registers. e.g. v1024 = move r0. |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 96 | DenseMap<unsigned, unsigned> SrcRegMap; |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 97 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 98 | // A map from virtual registers to physical registers which are likely targets |
| 99 | // to be coalesced to due to copies to physical registers from virtual |
| 100 | // registers. e.g. r1 = move v1024. |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 101 | DenseMap<unsigned, unsigned> DstRegMap; |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 102 | |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 103 | bool sink3AddrInstruction(MachineInstr *MI, unsigned Reg, |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 104 | MachineBasicBlock::iterator OldPos); |
Evan Cheng | c5618eb | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 105 | |
Eric Christopher | 2891913 | 2015-03-03 22:03:03 +0000 | [diff] [blame] | 106 | bool isRevCopyChain(unsigned FromReg, unsigned ToReg, int Maxlen); |
| 107 | |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 108 | bool noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef); |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 109 | |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 110 | bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 111 | MachineInstr *MI, unsigned Dist); |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 112 | |
Andrew Kaylor | 16c4da0 | 2015-09-28 20:33:22 +0000 | [diff] [blame] | 113 | bool commuteInstruction(MachineInstr *MI, |
| 114 | unsigned RegBIdx, unsigned RegCIdx, unsigned Dist); |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 115 | |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 116 | bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB); |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 117 | |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 118 | bool convertInstTo3Addr(MachineBasicBlock::iterator &mi, |
| 119 | MachineBasicBlock::iterator &nmi, |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 120 | unsigned RegA, unsigned RegB, unsigned Dist); |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 121 | |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 122 | bool isDefTooClose(unsigned Reg, unsigned Dist, MachineInstr *MI); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 123 | |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 124 | bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 125 | MachineBasicBlock::iterator &nmi, |
| 126 | unsigned Reg); |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 127 | bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 128 | MachineBasicBlock::iterator &nmi, |
| 129 | unsigned Reg); |
| 130 | |
| 131 | bool tryInstructionTransform(MachineBasicBlock::iterator &mi, |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 132 | MachineBasicBlock::iterator &nmi, |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 133 | unsigned SrcIdx, unsigned DstIdx, |
Cameron Zwarich | f05c0cb | 2013-02-24 00:27:26 +0000 | [diff] [blame] | 134 | unsigned Dist, bool shouldOnlyCommute); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 135 | |
Andrew Kaylor | 16c4da0 | 2015-09-28 20:33:22 +0000 | [diff] [blame] | 136 | bool tryInstructionCommute(MachineInstr *MI, |
| 137 | unsigned DstOpIdx, |
| 138 | unsigned BaseOpIdx, |
| 139 | bool BaseOpKilled, |
| 140 | unsigned Dist); |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 141 | void scanUses(unsigned DstReg); |
Evan Cheng | 15fed7a | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 142 | |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 143 | void processCopy(MachineInstr *MI); |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 144 | |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 145 | typedef SmallVector<std::pair<unsigned, unsigned>, 4> TiedPairList; |
| 146 | typedef SmallDenseMap<unsigned, TiedPairList> TiedOperandMap; |
| 147 | bool collectTiedOperands(MachineInstr *MI, TiedOperandMap&); |
| 148 | void processTiedPairs(MachineInstr *MI, TiedPairList&, unsigned &Dist); |
Jakob Stoklund Olesen | da2b6b3 | 2012-12-01 01:06:44 +0000 | [diff] [blame] | 149 | void eliminateRegSequence(MachineBasicBlock::iterator&); |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 150 | |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 151 | public: |
| 152 | static char ID; // Pass identification, replacement for typeid |
| 153 | TwoAddressInstructionPass() : MachineFunctionPass(ID) { |
| 154 | initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry()); |
| 155 | } |
Evan Cheng | 1e4f552 | 2010-05-17 23:24:12 +0000 | [diff] [blame] | 156 | |
Craig Topper | 4584cd5 | 2014-03-07 09:26:03 +0000 | [diff] [blame] | 157 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 158 | AU.setPreservesCFG(); |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 159 | AU.addRequired<AAResultsWrapperPass>(); |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 160 | AU.addPreserved<LiveVariables>(); |
| 161 | AU.addPreserved<SlotIndexes>(); |
| 162 | AU.addPreserved<LiveIntervals>(); |
| 163 | AU.addPreservedID(MachineLoopInfoID); |
| 164 | AU.addPreservedID(MachineDominatorsID); |
| 165 | MachineFunctionPass::getAnalysisUsage(AU); |
| 166 | } |
Devang Patel | 09f162c | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 167 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 168 | /// Pass entry point. |
Craig Topper | 4584cd5 | 2014-03-07 09:26:03 +0000 | [diff] [blame] | 169 | bool runOnMachineFunction(MachineFunction&) override; |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 170 | }; |
| 171 | } // end anonymous namespace |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 172 | |
Dan Gohman | d78c400 | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 173 | char TwoAddressInstructionPass::ID = 0; |
Owen Anderson | 8ac477f | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 174 | INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, "twoaddressinstruction", |
| 175 | "Two-Address instruction pass", false, false) |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 176 | INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) |
Owen Anderson | 8ac477f | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 177 | INITIALIZE_PASS_END(TwoAddressInstructionPass, "twoaddressinstruction", |
Owen Anderson | df7a4f2 | 2010-10-07 22:25:06 +0000 | [diff] [blame] | 178 | "Two-Address instruction pass", false, false) |
Dan Gohman | d78c400 | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 179 | |
Owen Anderson | a7aed18 | 2010-08-06 18:33:48 +0000 | [diff] [blame] | 180 | char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID; |
Alkis Evlogimenos | 7139090 | 2003-12-18 22:40:24 +0000 | [diff] [blame] | 181 | |
Cameron Zwarich | 35c3050 | 2013-02-23 04:49:20 +0000 | [diff] [blame] | 182 | static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, LiveIntervals *LIS); |
| 183 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 184 | /// A two-address instruction has been converted to a three-address instruction |
| 185 | /// to avoid clobbering a register. Try to sink it past the instruction that |
| 186 | /// would kill the above mentioned register to reduce register pressure. |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 187 | bool TwoAddressInstructionPass:: |
| 188 | sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, |
| 189 | MachineBasicBlock::iterator OldPos) { |
Eli Friedman | 8a15a5a | 2011-09-23 22:41:57 +0000 | [diff] [blame] | 190 | // FIXME: Shouldn't we be trying to do this before we three-addressify the |
| 191 | // instruction? After this transformation is done, we no longer need |
| 192 | // the instruction to be in three-address form. |
| 193 | |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 194 | // Check if it's safe to move this instruction. |
| 195 | bool SeenStore = true; // Be conservative. |
Matthias Braun | 07066cc | 2015-05-19 21:22:20 +0000 | [diff] [blame] | 196 | if (!MI->isSafeToMove(AA, SeenStore)) |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 197 | return false; |
| 198 | |
| 199 | unsigned DefReg = 0; |
| 200 | SmallSet<unsigned, 4> UseRegs; |
Bill Wendling | 19e3c85 | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 201 | |
Craig Topper | da5168b | 2015-10-08 06:06:42 +0000 | [diff] [blame] | 202 | for (const MachineOperand &MO : MI->operands()) { |
Dan Gohman | 0d1e9a8 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 203 | if (!MO.isReg()) |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 204 | continue; |
| 205 | unsigned MOReg = MO.getReg(); |
| 206 | if (!MOReg) |
| 207 | continue; |
| 208 | if (MO.isUse() && MOReg != SavedReg) |
| 209 | UseRegs.insert(MO.getReg()); |
| 210 | if (!MO.isDef()) |
| 211 | continue; |
| 212 | if (MO.isImplicit()) |
| 213 | // Don't try to move it if it implicitly defines a register. |
| 214 | return false; |
| 215 | if (DefReg) |
| 216 | // For now, don't move any instructions that define multiple registers. |
| 217 | return false; |
| 218 | DefReg = MO.getReg(); |
| 219 | } |
| 220 | |
| 221 | // Find the instruction that kills SavedReg. |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 222 | MachineInstr *KillMI = nullptr; |
Cameron Zwarich | 35c3050 | 2013-02-23 04:49:20 +0000 | [diff] [blame] | 223 | if (LIS) { |
| 224 | LiveInterval &LI = LIS->getInterval(SavedReg); |
| 225 | assert(LI.end() != LI.begin() && |
| 226 | "Reg should not have empty live interval."); |
| 227 | |
| 228 | SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); |
| 229 | LiveInterval::const_iterator I = LI.find(MBBEndIdx); |
| 230 | if (I != LI.end() && I->start < MBBEndIdx) |
| 231 | return false; |
| 232 | |
| 233 | --I; |
| 234 | KillMI = LIS->getInstructionFromIndex(I->end); |
| 235 | } |
| 236 | if (!KillMI) { |
Craig Topper | da5168b | 2015-10-08 06:06:42 +0000 | [diff] [blame] | 237 | for (MachineOperand &UseMO : MRI->use_nodbg_operands(SavedReg)) { |
Cameron Zwarich | 35c3050 | 2013-02-23 04:49:20 +0000 | [diff] [blame] | 238 | if (!UseMO.isKill()) |
| 239 | continue; |
| 240 | KillMI = UseMO.getParent(); |
| 241 | break; |
| 242 | } |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 243 | } |
Bill Wendling | 19e3c85 | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 244 | |
Eli Friedman | 8a15a5a | 2011-09-23 22:41:57 +0000 | [diff] [blame] | 245 | // If we find the instruction that kills SavedReg, and it is in an |
| 246 | // appropriate location, we can try to sink the current instruction |
| 247 | // past it. |
| 248 | if (!KillMI || KillMI->getParent() != MBB || KillMI == MI || |
Jakob Stoklund Olesen | 420798c | 2012-08-09 22:08:26 +0000 | [diff] [blame] | 249 | KillMI == OldPos || KillMI->isTerminator()) |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 250 | return false; |
| 251 | |
Bill Wendling | 19e3c85 | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 252 | // If any of the definitions are used by another instruction between the |
| 253 | // position and the kill use, then it's not safe to sink it. |
Andrew Trick | 808a7a6 | 2012-02-03 05:12:30 +0000 | [diff] [blame] | 254 | // |
Bill Wendling | 19e3c85 | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 255 | // FIXME: This can be sped up if there is an easy way to query whether an |
Evan Cheng | c5618eb | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 256 | // instruction is before or after another instruction. Then we can use |
Bill Wendling | 19e3c85 | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 257 | // MachineRegisterInfo def / use instead. |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 258 | MachineOperand *KillMO = nullptr; |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 259 | MachineBasicBlock::iterator KillPos = KillMI; |
| 260 | ++KillPos; |
Bill Wendling | 19e3c85 | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 261 | |
Evan Cheng | c5618eb | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 262 | unsigned NumVisited = 0; |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 263 | for (MachineBasicBlock::iterator I = std::next(OldPos); I != KillPos; ++I) { |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 264 | MachineInstr *OtherMI = I; |
Dale Johannesen | 12565de | 2010-02-11 18:22:31 +0000 | [diff] [blame] | 265 | // DBG_VALUE cannot be counted against the limit. |
| 266 | if (OtherMI->isDebugValue()) |
| 267 | continue; |
Evan Cheng | c5618eb | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 268 | if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost. |
| 269 | return false; |
| 270 | ++NumVisited; |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 271 | for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { |
| 272 | MachineOperand &MO = OtherMI->getOperand(i); |
Dan Gohman | 0d1e9a8 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 273 | if (!MO.isReg()) |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 274 | continue; |
| 275 | unsigned MOReg = MO.getReg(); |
| 276 | if (!MOReg) |
| 277 | continue; |
| 278 | if (DefReg == MOReg) |
| 279 | return false; |
Bill Wendling | 19e3c85 | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 280 | |
Cameron Zwarich | 35c3050 | 2013-02-23 04:49:20 +0000 | [diff] [blame] | 281 | if (MO.isKill() || (LIS && isPlainlyKilled(OtherMI, MOReg, LIS))) { |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 282 | if (OtherMI == KillMI && MOReg == SavedReg) |
Evan Cheng | c5618eb | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 283 | // Save the operand that kills the register. We want to unset the kill |
| 284 | // marker if we can sink MI past it. |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 285 | KillMO = &MO; |
| 286 | else if (UseRegs.count(MOReg)) |
| 287 | // One of the uses is killed before the destination. |
| 288 | return false; |
| 289 | } |
| 290 | } |
| 291 | } |
Jakob Stoklund Olesen | 420798c | 2012-08-09 22:08:26 +0000 | [diff] [blame] | 292 | assert(KillMO && "Didn't find kill"); |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 293 | |
Cameron Zwarich | 35c3050 | 2013-02-23 04:49:20 +0000 | [diff] [blame] | 294 | if (!LIS) { |
| 295 | // Update kill and LV information. |
| 296 | KillMO->setIsKill(false); |
| 297 | KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); |
| 298 | KillMO->setIsKill(true); |
Andrew Trick | 808a7a6 | 2012-02-03 05:12:30 +0000 | [diff] [blame] | 299 | |
Cameron Zwarich | 35c3050 | 2013-02-23 04:49:20 +0000 | [diff] [blame] | 300 | if (LV) |
| 301 | LV->replaceKillInstruction(SavedReg, KillMI, MI); |
| 302 | } |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 303 | |
| 304 | // Move instruction to its destination. |
| 305 | MBB->remove(MI); |
| 306 | MBB->insert(KillPos, MI); |
| 307 | |
Jakob Stoklund Olesen | 24bc514 | 2012-08-03 22:58:34 +0000 | [diff] [blame] | 308 | if (LIS) |
| 309 | LIS->handleMove(MI); |
| 310 | |
Evan Cheng | 5c26bde | 2008-03-13 06:37:55 +0000 | [diff] [blame] | 311 | ++Num3AddrSunk; |
| 312 | return true; |
| 313 | } |
| 314 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 315 | /// Return the MachineInstr* if it is the single def of the Reg in current BB. |
Eric Christopher | 2891913 | 2015-03-03 22:03:03 +0000 | [diff] [blame] | 316 | static MachineInstr *getSingleDef(unsigned Reg, MachineBasicBlock *BB, |
| 317 | const MachineRegisterInfo *MRI) { |
| 318 | MachineInstr *Ret = nullptr; |
| 319 | for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { |
| 320 | if (DefMI.getParent() != BB || DefMI.isDebugValue()) |
| 321 | continue; |
| 322 | if (!Ret) |
| 323 | Ret = &DefMI; |
| 324 | else if (Ret != &DefMI) |
| 325 | return nullptr; |
| 326 | } |
| 327 | return Ret; |
| 328 | } |
| 329 | |
| 330 | /// Check if there is a reversed copy chain from FromReg to ToReg: |
| 331 | /// %Tmp1 = copy %Tmp2; |
| 332 | /// %FromReg = copy %Tmp1; |
| 333 | /// %ToReg = add %FromReg ... |
| 334 | /// %Tmp2 = copy %ToReg; |
| 335 | /// MaxLen specifies the maximum length of the copy chain the func |
| 336 | /// can walk through. |
| 337 | bool TwoAddressInstructionPass::isRevCopyChain(unsigned FromReg, unsigned ToReg, |
| 338 | int Maxlen) { |
| 339 | unsigned TmpReg = FromReg; |
| 340 | for (int i = 0; i < Maxlen; i++) { |
| 341 | MachineInstr *Def = getSingleDef(TmpReg, MBB, MRI); |
| 342 | if (!Def || !Def->isCopy()) |
| 343 | return false; |
| 344 | |
| 345 | TmpReg = Def->getOperand(1).getReg(); |
| 346 | |
| 347 | if (TmpReg == ToReg) |
| 348 | return true; |
| 349 | } |
| 350 | return false; |
| 351 | } |
| 352 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 353 | /// Return true if there are no intervening uses between the last instruction |
| 354 | /// in the MBB that defines the specified register and the two-address |
| 355 | /// instruction which is being processed. It also returns the last def location |
| 356 | /// by reference. |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 357 | bool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist, |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 358 | unsigned &LastDef) { |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 359 | LastDef = 0; |
| 360 | unsigned LastUse = Dist; |
Owen Anderson | b36376e | 2014-03-17 19:36:09 +0000 | [diff] [blame] | 361 | for (MachineOperand &MO : MRI->reg_operands(Reg)) { |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 362 | MachineInstr *MI = MO.getParent(); |
Chris Lattner | b06015a | 2010-02-09 19:54:29 +0000 | [diff] [blame] | 363 | if (MI->getParent() != MBB || MI->isDebugValue()) |
Dale Johannesen | c3adf44 | 2010-02-09 02:01:46 +0000 | [diff] [blame] | 364 | continue; |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 365 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); |
| 366 | if (DI == DistanceMap.end()) |
| 367 | continue; |
| 368 | if (MO.isUse() && DI->second < LastUse) |
| 369 | LastUse = DI->second; |
| 370 | if (MO.isDef() && DI->second > LastDef) |
| 371 | LastDef = DI->second; |
| 372 | } |
| 373 | |
| 374 | return !(LastUse > LastDef && LastUse < Dist); |
| 375 | } |
| 376 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 377 | /// Return true if the specified MI is a copy instruction or an extract_subreg |
| 378 | /// instruction. It also returns the source and destination registers and |
| 379 | /// whether they are physical registers by reference. |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 380 | static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, |
| 381 | unsigned &SrcReg, unsigned &DstReg, |
| 382 | bool &IsSrcPhys, bool &IsDstPhys) { |
| 383 | SrcReg = 0; |
| 384 | DstReg = 0; |
Jakob Stoklund Olesen | 37c42a3 | 2010-07-16 04:45:42 +0000 | [diff] [blame] | 385 | if (MI.isCopy()) { |
| 386 | DstReg = MI.getOperand(0).getReg(); |
| 387 | SrcReg = MI.getOperand(1).getReg(); |
| 388 | } else if (MI.isInsertSubreg() || MI.isSubregToReg()) { |
| 389 | DstReg = MI.getOperand(0).getReg(); |
| 390 | SrcReg = MI.getOperand(2).getReg(); |
| 391 | } else |
| 392 | return false; |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 393 | |
Jakob Stoklund Olesen | 37c42a3 | 2010-07-16 04:45:42 +0000 | [diff] [blame] | 394 | IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); |
| 395 | IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); |
| 396 | return true; |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 397 | } |
| 398 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 399 | /// Test if the given register value, which is used by the |
| 400 | /// given instruction, is killed by the given instruction. |
Cameron Zwarich | c896478 | 2013-02-21 07:02:28 +0000 | [diff] [blame] | 401 | static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, |
| 402 | LiveIntervals *LIS) { |
| 403 | if (LIS && TargetRegisterInfo::isVirtualRegister(Reg) && |
| 404 | !LIS->isNotInMIMap(MI)) { |
| 405 | // FIXME: Sometimes tryInstructionTransform() will add instructions and |
| 406 | // test whether they can be folded before keeping them. In this case it |
| 407 | // sets a kill before recursively calling tryInstructionTransform() again. |
| 408 | // If there is no interval available, we assume that this instruction is |
| 409 | // one of those. A kill flag is manually inserted on the operand so the |
| 410 | // check below will handle it. |
| 411 | LiveInterval &LI = LIS->getInterval(Reg); |
| 412 | // This is to match the kill flag version where undefs don't have kill |
| 413 | // flags. |
| 414 | if (!LI.hasAtLeastOneValue()) |
| 415 | return false; |
| 416 | |
| 417 | SlotIndex useIdx = LIS->getInstructionIndex(MI); |
| 418 | LiveInterval::const_iterator I = LI.find(useIdx); |
| 419 | assert(I != LI.end() && "Reg must be live-in to use."); |
Cameron Zwarich | 4e80d9e | 2013-02-23 04:49:22 +0000 | [diff] [blame] | 420 | return !I->end.isBlock() && SlotIndex::isSameInstr(I->end, useIdx); |
Cameron Zwarich | c896478 | 2013-02-21 07:02:28 +0000 | [diff] [blame] | 421 | } |
| 422 | |
| 423 | return MI->killsRegister(Reg); |
| 424 | } |
| 425 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 426 | /// Test if the given register value, which is used by the given |
Dan Gohman | ad3e549 | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 427 | /// instruction, is killed by the given instruction. This looks through |
| 428 | /// coalescable copies to see if the original value is potentially not killed. |
| 429 | /// |
| 430 | /// For example, in this code: |
| 431 | /// |
| 432 | /// %reg1034 = copy %reg1024 |
| 433 | /// %reg1035 = copy %reg1025<kill> |
| 434 | /// %reg1036 = add %reg1034<kill>, %reg1035<kill> |
| 435 | /// |
| 436 | /// %reg1034 is not considered to be killed, since it is copied from a |
| 437 | /// register which is not killed. Treating it as not killed lets the |
| 438 | /// normal heuristics commute the (two-address) add, which lets |
| 439 | /// coalescing eliminate the extra copy. |
| 440 | /// |
Cameron Zwarich | 384026b | 2013-02-21 22:58:42 +0000 | [diff] [blame] | 441 | /// If allowFalsePositives is true then likely kills are treated as kills even |
| 442 | /// if it can't be proven that they are kills. |
Dan Gohman | ad3e549 | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 443 | static bool isKilled(MachineInstr &MI, unsigned Reg, |
| 444 | const MachineRegisterInfo *MRI, |
Cameron Zwarich | 94b204b | 2013-02-21 04:33:02 +0000 | [diff] [blame] | 445 | const TargetInstrInfo *TII, |
Cameron Zwarich | 384026b | 2013-02-21 22:58:42 +0000 | [diff] [blame] | 446 | LiveIntervals *LIS, |
| 447 | bool allowFalsePositives) { |
Dan Gohman | ad3e549 | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 448 | MachineInstr *DefMI = &MI; |
| 449 | for (;;) { |
Cameron Zwarich | 384026b | 2013-02-21 22:58:42 +0000 | [diff] [blame] | 450 | // All uses of physical registers are likely to be kills. |
| 451 | if (TargetRegisterInfo::isPhysicalRegister(Reg) && |
| 452 | (allowFalsePositives || MRI->hasOneUse(Reg))) |
| 453 | return true; |
Cameron Zwarich | c896478 | 2013-02-21 07:02:28 +0000 | [diff] [blame] | 454 | if (!isPlainlyKilled(DefMI, Reg, LIS)) |
Dan Gohman | ad3e549 | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 455 | return false; |
| 456 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) |
| 457 | return true; |
| 458 | MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); |
| 459 | // If there are multiple defs, we can't do a simple analysis, so just |
| 460 | // go with what the kill flag says. |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 461 | if (std::next(Begin) != MRI->def_end()) |
Dan Gohman | ad3e549 | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 462 | return true; |
Owen Anderson | 16c6bf4 | 2014-03-13 23:12:04 +0000 | [diff] [blame] | 463 | DefMI = Begin->getParent(); |
Dan Gohman | ad3e549 | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 464 | bool IsSrcPhys, IsDstPhys; |
| 465 | unsigned SrcReg, DstReg; |
| 466 | // If the def is something other than a copy, then it isn't going to |
| 467 | // be coalesced, so follow the kill flag. |
| 468 | if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) |
| 469 | return true; |
| 470 | Reg = SrcReg; |
| 471 | } |
| 472 | } |
| 473 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 474 | /// Return true if the specified MI uses the specified register as a two-address |
| 475 | /// use. If so, return the destination register by reference. |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 476 | static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { |
Evan Cheng | f85a76f | 2013-05-02 02:07:32 +0000 | [diff] [blame] | 477 | for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) { |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 478 | const MachineOperand &MO = MI.getOperand(i); |
| 479 | if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) |
| 480 | continue; |
Evan Cheng | 1361cbb | 2009-03-19 20:30:06 +0000 | [diff] [blame] | 481 | unsigned ti; |
| 482 | if (MI.isRegTiedToDefOperand(i, &ti)) { |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 483 | DstReg = MI.getOperand(ti).getReg(); |
| 484 | return true; |
| 485 | } |
| 486 | } |
| 487 | return false; |
| 488 | } |
| 489 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 490 | /// Given a register, if has a single in-basic block use, return the use |
| 491 | /// instruction if it's a copy or a two-address use. |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 492 | static |
| 493 | MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, |
| 494 | MachineRegisterInfo *MRI, |
| 495 | const TargetInstrInfo *TII, |
Evan Cheng | 9787183 | 2009-04-14 00:32:25 +0000 | [diff] [blame] | 496 | bool &IsCopy, |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 497 | unsigned &DstReg, bool &IsDstPhys) { |
Evan Cheng | f94d683 | 2010-03-03 21:18:38 +0000 | [diff] [blame] | 498 | if (!MRI->hasOneNonDBGUse(Reg)) |
| 499 | // None or more than one use. |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 500 | return nullptr; |
Owen Anderson | 16c6bf4 | 2014-03-13 23:12:04 +0000 | [diff] [blame] | 501 | MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(Reg); |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 502 | if (UseMI.getParent() != MBB) |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 503 | return nullptr; |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 504 | unsigned SrcReg; |
| 505 | bool IsSrcPhys; |
Evan Cheng | 9787183 | 2009-04-14 00:32:25 +0000 | [diff] [blame] | 506 | if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) { |
| 507 | IsCopy = true; |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 508 | return &UseMI; |
Evan Cheng | 9787183 | 2009-04-14 00:32:25 +0000 | [diff] [blame] | 509 | } |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 510 | IsDstPhys = false; |
Evan Cheng | 9787183 | 2009-04-14 00:32:25 +0000 | [diff] [blame] | 511 | if (isTwoAddrUse(UseMI, Reg, DstReg)) { |
| 512 | IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 513 | return &UseMI; |
Evan Cheng | 9787183 | 2009-04-14 00:32:25 +0000 | [diff] [blame] | 514 | } |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 515 | return nullptr; |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 516 | } |
| 517 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 518 | /// Return the physical register the specified virtual register might be mapped |
| 519 | /// to. |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 520 | static unsigned |
| 521 | getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) { |
| 522 | while (TargetRegisterInfo::isVirtualRegister(Reg)) { |
| 523 | DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg); |
| 524 | if (SI == RegMap.end()) |
| 525 | return 0; |
| 526 | Reg = SI->second; |
| 527 | } |
| 528 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) |
| 529 | return Reg; |
| 530 | return 0; |
| 531 | } |
| 532 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 533 | /// Return true if the two registers are equal or aliased. |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 534 | static bool |
| 535 | regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { |
| 536 | if (RegA == RegB) |
| 537 | return true; |
| 538 | if (!RegA || !RegB) |
| 539 | return false; |
| 540 | return TRI->regsOverlap(RegA, RegB); |
| 541 | } |
| 542 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 543 | /// Return true if it's potentially profitable to commute the two-address |
| 544 | /// instruction that's being processed. |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 545 | bool |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 546 | TwoAddressInstructionPass:: |
| 547 | isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, |
| 548 | MachineInstr *MI, unsigned Dist) { |
Evan Cheng | 822ddde | 2011-11-16 18:44:48 +0000 | [diff] [blame] | 549 | if (OptLevel == CodeGenOpt::None) |
| 550 | return false; |
| 551 | |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 552 | // Determine if it's profitable to commute this two address instruction. In |
| 553 | // general, we want no uses between this instruction and the definition of |
| 554 | // the two-address register. |
| 555 | // e.g. |
| 556 | // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 |
| 557 | // %reg1029<def> = MOV8rr %reg1028 |
| 558 | // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> |
| 559 | // insert => %reg1030<def> = MOV8rr %reg1028 |
| 560 | // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> |
| 561 | // In this case, it might not be possible to coalesce the second MOV8rr |
| 562 | // instruction if the first one is coalesced. So it would be profitable to |
| 563 | // commute it: |
| 564 | // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 |
| 565 | // %reg1029<def> = MOV8rr %reg1028 |
| 566 | // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> |
| 567 | // insert => %reg1030<def> = MOV8rr %reg1029 |
Andrew Trick | 808a7a6 | 2012-02-03 05:12:30 +0000 | [diff] [blame] | 568 | // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead> |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 569 | |
Cameron Zwarich | 9e722ae | 2013-02-21 07:02:30 +0000 | [diff] [blame] | 570 | if (!isPlainlyKilled(MI, regC, LIS)) |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 571 | return false; |
| 572 | |
| 573 | // Ok, we have something like: |
| 574 | // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> |
| 575 | // let's see if it's worth commuting it. |
| 576 | |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 577 | // Look for situations like this: |
| 578 | // %reg1024<def> = MOV r1 |
| 579 | // %reg1025<def> = MOV r0 |
| 580 | // %reg1026<def> = ADD %reg1024, %reg1025 |
| 581 | // r0 = MOV %reg1026 |
| 582 | // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. |
Evan Cheng | b64e7b7 | 2012-05-03 01:45:13 +0000 | [diff] [blame] | 583 | unsigned ToRegA = getMappedReg(regA, DstRegMap); |
| 584 | if (ToRegA) { |
| 585 | unsigned FromRegB = getMappedReg(regB, SrcRegMap); |
| 586 | unsigned FromRegC = getMappedReg(regC, SrcRegMap); |
Craig Topper | 12f0d9e | 2014-11-05 06:43:02 +0000 | [diff] [blame] | 587 | bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA, TRI); |
| 588 | bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA, TRI); |
| 589 | |
| 590 | // Compute if any of the following are true: |
| 591 | // -RegB is not tied to a register and RegC is compatible with RegA. |
| 592 | // -RegB is tied to the wrong physical register, but RegC is. |
| 593 | // -RegB is tied to the wrong physical register, and RegC isn't tied. |
| 594 | if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC))) |
| 595 | return true; |
| 596 | // Don't compute if any of the following are true: |
| 597 | // -RegC is not tied to a register and RegB is compatible with RegA. |
| 598 | // -RegC is tied to the wrong physical register, but RegB is. |
| 599 | // -RegC is tied to the wrong physical register, and RegB isn't tied. |
| 600 | if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB))) |
| 601 | return false; |
Evan Cheng | b64e7b7 | 2012-05-03 01:45:13 +0000 | [diff] [blame] | 602 | } |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 603 | |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 604 | // If there is a use of regC between its last def (could be livein) and this |
| 605 | // instruction, then bail. |
| 606 | unsigned LastDefC = 0; |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 607 | if (!noUseAfterLastDef(regC, Dist, LastDefC)) |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 608 | return false; |
| 609 | |
| 610 | // If there is a use of regB between its last def (could be livein) and this |
| 611 | // instruction, then go ahead and make this transformation. |
| 612 | unsigned LastDefB = 0; |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 613 | if (!noUseAfterLastDef(regB, Dist, LastDefB)) |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 614 | return true; |
| 615 | |
Eric Christopher | 2891913 | 2015-03-03 22:03:03 +0000 | [diff] [blame] | 616 | // Look for situation like this: |
| 617 | // %reg101 = MOV %reg100 |
| 618 | // %reg102 = ... |
| 619 | // %reg103 = ADD %reg102, %reg101 |
| 620 | // ... = %reg103 ... |
| 621 | // %reg100 = MOV %reg103 |
| 622 | // If there is a reversed copy chain from reg101 to reg103, commute the ADD |
| 623 | // to eliminate an otherwise unavoidable copy. |
| 624 | // FIXME: |
| 625 | // We can extend the logic further: If an pair of operands in an insn has |
| 626 | // been merged, the insn could be regarded as a virtual copy, and the virtual |
| 627 | // copy could also be used to construct a copy chain. |
| 628 | // To more generally minimize register copies, ideally the logic of two addr |
| 629 | // instruction pass should be integrated with register allocation pass where |
| 630 | // interference graph is available. |
| 631 | if (isRevCopyChain(regC, regA, 3)) |
| 632 | return true; |
| 633 | |
| 634 | if (isRevCopyChain(regB, regA, 3)) |
| 635 | return false; |
| 636 | |
Evan Cheng | abda665 | 2009-01-25 03:53:59 +0000 | [diff] [blame] | 637 | // Since there are no intervening uses for both registers, then commute |
| 638 | // if the def of regC is closer. Its live interval is shorter. |
| 639 | return LastDefB && LastDefC && LastDefC > LastDefB; |
| 640 | } |
| 641 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 642 | /// Commute a two-address instruction and update the basic block, distance map, |
| 643 | /// and live variables if needed. Return true if it is successful. |
Andrew Kaylor | 16c4da0 | 2015-09-28 20:33:22 +0000 | [diff] [blame] | 644 | bool TwoAddressInstructionPass::commuteInstruction(MachineInstr *MI, |
| 645 | unsigned RegBIdx, |
| 646 | unsigned RegCIdx, |
| 647 | unsigned Dist) { |
| 648 | unsigned RegC = MI->getOperand(RegCIdx).getReg(); |
David Greene | ac9f819 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 649 | DEBUG(dbgs() << "2addr: COMMUTING : " << *MI); |
Andrew Kaylor | 16c4da0 | 2015-09-28 20:33:22 +0000 | [diff] [blame] | 650 | MachineInstr *NewMI = TII->commuteInstruction(MI, false, RegBIdx, RegCIdx); |
Evan Cheng | 6d89706 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 651 | |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 652 | if (NewMI == nullptr) { |
David Greene | ac9f819 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 653 | DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n"); |
Evan Cheng | 6d89706 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 654 | return false; |
| 655 | } |
| 656 | |
David Greene | ac9f819 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 657 | DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI); |
Cameron Zwarich | e6907bc | 2013-02-23 23:13:28 +0000 | [diff] [blame] | 658 | assert(NewMI == MI && |
| 659 | "TargetInstrInfo::commuteInstruction() should not return a new " |
| 660 | "instruction unless it was requested."); |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 661 | |
| 662 | // Update source register map. |
| 663 | unsigned FromRegC = getMappedReg(RegC, SrcRegMap); |
| 664 | if (FromRegC) { |
| 665 | unsigned RegA = MI->getOperand(0).getReg(); |
| 666 | SrcRegMap[RegA] = FromRegC; |
| 667 | } |
| 668 | |
Evan Cheng | 6d89706 | 2009-01-23 23:27:33 +0000 | [diff] [blame] | 669 | return true; |
| 670 | } |
| 671 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 672 | /// Return true if it is profitable to convert the given 2-address instruction |
| 673 | /// to a 3-address one. |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 674 | bool |
Evan Cheng | 15fed7a | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 675 | TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){ |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 676 | // Look for situations like this: |
| 677 | // %reg1024<def> = MOV r1 |
| 678 | // %reg1025<def> = MOV r0 |
| 679 | // %reg1026<def> = ADD %reg1024, %reg1025 |
| 680 | // r2 = MOV %reg1026 |
| 681 | // Turn ADD into a 3-address instruction to avoid a copy. |
Evan Cheng | 15fed7a | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 682 | unsigned FromRegB = getMappedReg(RegB, SrcRegMap); |
| 683 | if (!FromRegB) |
| 684 | return false; |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 685 | unsigned ToRegA = getMappedReg(RegA, DstRegMap); |
Evan Cheng | 15fed7a | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 686 | return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI)); |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 687 | } |
| 688 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 689 | /// Convert the specified two-address instruction into a three address one. |
| 690 | /// Return true if this transformation was successful. |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 691 | bool |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 692 | TwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi, |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 693 | MachineBasicBlock::iterator &nmi, |
Evan Cheng | d4fcc05 | 2011-02-10 02:20:55 +0000 | [diff] [blame] | 694 | unsigned RegA, unsigned RegB, |
| 695 | unsigned Dist) { |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 696 | // FIXME: Why does convertToThreeAddress() need an iterator reference? |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 697 | MachineFunction::iterator MFI = MBB->getIterator(); |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 698 | MachineInstr *NewMI = TII->convertToThreeAddress(MFI, mi, LV); |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 699 | assert(MBB->getIterator() == MFI && |
| 700 | "convertToThreeAddress changed iterator reference"); |
Jakob Stoklund Olesen | 1dfe4fc | 2012-10-26 23:05:13 +0000 | [diff] [blame] | 701 | if (!NewMI) |
| 702 | return false; |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 703 | |
Jakob Stoklund Olesen | 1dfe4fc | 2012-10-26 23:05:13 +0000 | [diff] [blame] | 704 | DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi); |
| 705 | DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI); |
| 706 | bool Sunk = false; |
Jakob Stoklund Olesen | 24bc514 | 2012-08-03 22:58:34 +0000 | [diff] [blame] | 707 | |
Cameron Zwarich | 2ad3ca3 | 2013-02-20 22:10:02 +0000 | [diff] [blame] | 708 | if (LIS) |
| 709 | LIS->ReplaceMachineInstrInMaps(mi, NewMI); |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 710 | |
Jakob Stoklund Olesen | 1dfe4fc | 2012-10-26 23:05:13 +0000 | [diff] [blame] | 711 | if (NewMI->findRegisterUseOperand(RegB, false, TRI)) |
| 712 | // FIXME: Temporary workaround. If the new instruction doesn't |
| 713 | // uses RegB, convertToThreeAddress must have created more |
| 714 | // then one instruction. |
| 715 | Sunk = sink3AddrInstruction(NewMI, RegB, mi); |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 716 | |
Jakob Stoklund Olesen | 1dfe4fc | 2012-10-26 23:05:13 +0000 | [diff] [blame] | 717 | MBB->erase(mi); // Nuke the old inst. |
Evan Cheng | d4fcc05 | 2011-02-10 02:20:55 +0000 | [diff] [blame] | 718 | |
Jakob Stoklund Olesen | 1dfe4fc | 2012-10-26 23:05:13 +0000 | [diff] [blame] | 719 | if (!Sunk) { |
| 720 | DistanceMap.insert(std::make_pair(NewMI, Dist)); |
| 721 | mi = NewMI; |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 722 | nmi = std::next(mi); |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 723 | } |
| 724 | |
Jakob Stoklund Olesen | 1dfe4fc | 2012-10-26 23:05:13 +0000 | [diff] [blame] | 725 | // Update source and destination register maps. |
| 726 | SrcRegMap.erase(RegA); |
| 727 | DstRegMap.erase(RegB); |
| 728 | return true; |
Evan Cheng | 09f5be8 | 2009-03-30 21:34:07 +0000 | [diff] [blame] | 729 | } |
| 730 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 731 | /// Scan forward recursively for only uses, update maps if the use is a copy or |
| 732 | /// a two-address instruction. |
Evan Cheng | 15fed7a | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 733 | void |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 734 | TwoAddressInstructionPass::scanUses(unsigned DstReg) { |
Evan Cheng | 15fed7a | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 735 | SmallVector<unsigned, 4> VirtRegPairs; |
| 736 | bool IsDstPhys; |
| 737 | bool IsCopy = false; |
| 738 | unsigned NewReg = 0; |
| 739 | unsigned Reg = DstReg; |
| 740 | while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy, |
| 741 | NewReg, IsDstPhys)) { |
David Blaikie | 70573dc | 2014-11-19 07:49:26 +0000 | [diff] [blame] | 742 | if (IsCopy && !Processed.insert(UseMI).second) |
Evan Cheng | 15fed7a | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 743 | break; |
| 744 | |
| 745 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); |
| 746 | if (DI != DistanceMap.end()) |
| 747 | // Earlier in the same MBB.Reached via a back edge. |
| 748 | break; |
| 749 | |
| 750 | if (IsDstPhys) { |
| 751 | VirtRegPairs.push_back(NewReg); |
| 752 | break; |
| 753 | } |
| 754 | bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second; |
| 755 | if (!isNew) |
| 756 | assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!"); |
| 757 | VirtRegPairs.push_back(NewReg); |
| 758 | Reg = NewReg; |
| 759 | } |
| 760 | |
| 761 | if (!VirtRegPairs.empty()) { |
| 762 | unsigned ToReg = VirtRegPairs.back(); |
| 763 | VirtRegPairs.pop_back(); |
| 764 | while (!VirtRegPairs.empty()) { |
| 765 | unsigned FromReg = VirtRegPairs.back(); |
| 766 | VirtRegPairs.pop_back(); |
| 767 | bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; |
| 768 | if (!isNew) |
| 769 | assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!"); |
| 770 | ToReg = FromReg; |
| 771 | } |
| 772 | bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second; |
| 773 | if (!isNew) |
| 774 | assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!"); |
| 775 | } |
| 776 | } |
| 777 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 778 | /// If the specified instruction is not yet processed, process it if it's a |
| 779 | /// copy. For a copy instruction, we find the physical registers the |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 780 | /// source and destination registers might be mapped to. These are kept in |
| 781 | /// point-to maps used to determine future optimizations. e.g. |
| 782 | /// v1024 = mov r0 |
| 783 | /// v1025 = mov r1 |
| 784 | /// v1026 = add v1024, v1025 |
| 785 | /// r1 = mov r1026 |
| 786 | /// If 'add' is a two-address instruction, v1024, v1026 are both potentially |
| 787 | /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is |
| 788 | /// potentially joined with r1 on the output side. It's worthwhile to commute |
| 789 | /// 'add' to eliminate a copy. |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 790 | void TwoAddressInstructionPass::processCopy(MachineInstr *MI) { |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 791 | if (Processed.count(MI)) |
| 792 | return; |
| 793 | |
| 794 | bool IsSrcPhys, IsDstPhys; |
| 795 | unsigned SrcReg, DstReg; |
| 796 | if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) |
| 797 | return; |
| 798 | |
| 799 | if (IsDstPhys && !IsSrcPhys) |
| 800 | DstRegMap.insert(std::make_pair(SrcReg, DstReg)); |
| 801 | else if (!IsDstPhys && IsSrcPhys) { |
Evan Cheng | f084380 | 2009-04-13 20:04:24 +0000 | [diff] [blame] | 802 | bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second; |
| 803 | if (!isNew) |
| 804 | assert(SrcRegMap[DstReg] == SrcReg && |
| 805 | "Can't map to two src physical registers!"); |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 806 | |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 807 | scanUses(DstReg); |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 808 | } |
| 809 | |
| 810 | Processed.insert(MI); |
| 811 | } |
| 812 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 813 | /// If there is one more local instruction that reads 'Reg' and it kills 'Reg, |
| 814 | /// consider moving the instruction below the kill instruction in order to |
| 815 | /// eliminate the need for the copy. |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 816 | bool TwoAddressInstructionPass:: |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 817 | rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 818 | MachineBasicBlock::iterator &nmi, |
| 819 | unsigned Reg) { |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 820 | // Bail immediately if we don't have LV or LIS available. We use them to find |
| 821 | // kills efficiently. |
| 822 | if (!LV && !LIS) |
Chandler Carruth | db5536f | 2012-07-15 03:29:46 +0000 | [diff] [blame] | 823 | return false; |
| 824 | |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 825 | MachineInstr *MI = &*mi; |
Andrew Trick | 808a7a6 | 2012-02-03 05:12:30 +0000 | [diff] [blame] | 826 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 827 | if (DI == DistanceMap.end()) |
| 828 | // Must be created from unfolded load. Don't waste time trying this. |
| 829 | return false; |
| 830 | |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 831 | MachineInstr *KillMI = nullptr; |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 832 | if (LIS) { |
| 833 | LiveInterval &LI = LIS->getInterval(Reg); |
| 834 | assert(LI.end() != LI.begin() && |
| 835 | "Reg should not have empty live interval."); |
| 836 | |
| 837 | SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); |
| 838 | LiveInterval::const_iterator I = LI.find(MBBEndIdx); |
| 839 | if (I != LI.end() && I->start < MBBEndIdx) |
| 840 | return false; |
| 841 | |
| 842 | --I; |
| 843 | KillMI = LIS->getInstructionFromIndex(I->end); |
| 844 | } else { |
| 845 | KillMI = LV->getVarInfo(Reg).findKill(MBB); |
| 846 | } |
Chandler Carruth | db5536f | 2012-07-15 03:29:46 +0000 | [diff] [blame] | 847 | if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike()) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 848 | // Don't mess with copies, they may be coalesced later. |
| 849 | return false; |
| 850 | |
Evan Cheng | 7f8e563 | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 851 | if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() || |
| 852 | KillMI->isBranch() || KillMI->isTerminator()) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 853 | // Don't move pass calls, etc. |
| 854 | return false; |
| 855 | |
| 856 | unsigned DstReg; |
| 857 | if (isTwoAddrUse(*KillMI, Reg, DstReg)) |
| 858 | return false; |
| 859 | |
Evan Cheng | 7098c4e | 2011-11-15 06:26:51 +0000 | [diff] [blame] | 860 | bool SeenStore = true; |
Matthias Braun | 07066cc | 2015-05-19 21:22:20 +0000 | [diff] [blame] | 861 | if (!MI->isSafeToMove(AA, SeenStore)) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 862 | return false; |
| 863 | |
| 864 | if (TII->getInstrLatency(InstrItins, MI) > 1) |
| 865 | // FIXME: Needs more sophisticated heuristics. |
| 866 | return false; |
| 867 | |
| 868 | SmallSet<unsigned, 2> Uses; |
Evan Cheng | b8c55a5 | 2011-11-16 03:47:42 +0000 | [diff] [blame] | 869 | SmallSet<unsigned, 2> Kills; |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 870 | SmallSet<unsigned, 2> Defs; |
Sanjay Patel | 0b2a949 | 2015-12-01 19:57:43 +0000 | [diff] [blame] | 871 | for (const MachineOperand &MO : MI->operands()) { |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 872 | if (!MO.isReg()) |
| 873 | continue; |
| 874 | unsigned MOReg = MO.getReg(); |
| 875 | if (!MOReg) |
| 876 | continue; |
| 877 | if (MO.isDef()) |
| 878 | Defs.insert(MOReg); |
Evan Cheng | b8c55a5 | 2011-11-16 03:47:42 +0000 | [diff] [blame] | 879 | else { |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 880 | Uses.insert(MOReg); |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 881 | if (MOReg != Reg && (MO.isKill() || |
| 882 | (LIS && isPlainlyKilled(MI, MOReg, LIS)))) |
Evan Cheng | b8c55a5 | 2011-11-16 03:47:42 +0000 | [diff] [blame] | 883 | Kills.insert(MOReg); |
| 884 | } |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 885 | } |
| 886 | |
| 887 | // Move the copies connected to MI down as well. |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 888 | MachineBasicBlock::iterator Begin = MI; |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 889 | MachineBasicBlock::iterator AfterMI = std::next(Begin); |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 890 | |
| 891 | MachineBasicBlock::iterator End = AfterMI; |
| 892 | while (End->isCopy() && Defs.count(End->getOperand(1).getReg())) { |
| 893 | Defs.insert(End->getOperand(0).getReg()); |
| 894 | ++End; |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 895 | } |
| 896 | |
| 897 | // Check if the reschedule will not break depedencies. |
| 898 | unsigned NumVisited = 0; |
| 899 | MachineBasicBlock::iterator KillPos = KillMI; |
| 900 | ++KillPos; |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 901 | for (MachineBasicBlock::iterator I = End; I != KillPos; ++I) { |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 902 | MachineInstr *OtherMI = I; |
| 903 | // DBG_VALUE cannot be counted against the limit. |
| 904 | if (OtherMI->isDebugValue()) |
| 905 | continue; |
| 906 | if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. |
| 907 | return false; |
| 908 | ++NumVisited; |
Evan Cheng | 7f8e563 | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 909 | if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() || |
| 910 | OtherMI->isBranch() || OtherMI->isTerminator()) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 911 | // Don't move pass calls, etc. |
| 912 | return false; |
Sanjay Patel | 0b2a949 | 2015-12-01 19:57:43 +0000 | [diff] [blame] | 913 | for (const MachineOperand &MO : OtherMI->operands()) { |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 914 | if (!MO.isReg()) |
| 915 | continue; |
| 916 | unsigned MOReg = MO.getReg(); |
| 917 | if (!MOReg) |
| 918 | continue; |
| 919 | if (MO.isDef()) { |
| 920 | if (Uses.count(MOReg)) |
| 921 | // Physical register use would be clobbered. |
| 922 | return false; |
| 923 | if (!MO.isDead() && Defs.count(MOReg)) |
| 924 | // May clobber a physical register def. |
| 925 | // FIXME: This may be too conservative. It's ok if the instruction |
| 926 | // is sunken completely below the use. |
| 927 | return false; |
| 928 | } else { |
| 929 | if (Defs.count(MOReg)) |
| 930 | return false; |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 931 | bool isKill = MO.isKill() || |
| 932 | (LIS && isPlainlyKilled(OtherMI, MOReg, LIS)); |
Evan Cheng | b8c55a5 | 2011-11-16 03:47:42 +0000 | [diff] [blame] | 933 | if (MOReg != Reg && |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 934 | ((isKill && Uses.count(MOReg)) || Kills.count(MOReg))) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 935 | // Don't want to extend other live ranges and update kills. |
| 936 | return false; |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 937 | if (MOReg == Reg && !isKill) |
Chandler Carruth | db5536f | 2012-07-15 03:29:46 +0000 | [diff] [blame] | 938 | // We can't schedule across a use of the register in question. |
| 939 | return false; |
| 940 | // Ensure that if this is register in question, its the kill we expect. |
| 941 | assert((MOReg != Reg || OtherMI == KillMI) && |
| 942 | "Found multiple kills of a register in a basic block"); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 943 | } |
| 944 | } |
| 945 | } |
| 946 | |
| 947 | // Move debug info as well. |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 948 | while (Begin != MBB->begin() && std::prev(Begin)->isDebugValue()) |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 949 | --Begin; |
| 950 | |
| 951 | nmi = End; |
| 952 | MachineBasicBlock::iterator InsertPos = KillPos; |
| 953 | if (LIS) { |
| 954 | // We have to move the copies first so that the MBB is still well-formed |
| 955 | // when calling handleMove(). |
| 956 | for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) { |
| 957 | MachineInstr *CopyMI = MBBI; |
| 958 | ++MBBI; |
| 959 | MBB->splice(InsertPos, MBB, CopyMI); |
| 960 | LIS->handleMove(CopyMI); |
| 961 | InsertPos = CopyMI; |
| 962 | } |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 963 | End = std::next(MachineBasicBlock::iterator(MI)); |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 964 | } |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 965 | |
| 966 | // Copies following MI may have been moved as well. |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 967 | MBB->splice(InsertPos, MBB, Begin, End); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 968 | DistanceMap.erase(DI); |
| 969 | |
Chandler Carruth | db5536f | 2012-07-15 03:29:46 +0000 | [diff] [blame] | 970 | // Update live variables |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 971 | if (LIS) { |
Jakob Stoklund Olesen | 24bc514 | 2012-08-03 22:58:34 +0000 | [diff] [blame] | 972 | LIS->handleMove(MI); |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 973 | } else { |
| 974 | LV->removeVirtualRegisterKilled(Reg, KillMI); |
| 975 | LV->addVirtualRegisterKilled(Reg, MI); |
| 976 | } |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 977 | |
Jakob Stoklund Olesen | 0ef0311 | 2012-07-17 17:57:23 +0000 | [diff] [blame] | 978 | DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 979 | return true; |
| 980 | } |
| 981 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 982 | /// Return true if the re-scheduling will put the given instruction too close |
| 983 | /// to the defs of its register dependencies. |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 984 | bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist, |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 985 | MachineInstr *MI) { |
Owen Anderson | b36376e | 2014-03-17 19:36:09 +0000 | [diff] [blame] | 986 | for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { |
| 987 | if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike()) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 988 | continue; |
Owen Anderson | b36376e | 2014-03-17 19:36:09 +0000 | [diff] [blame] | 989 | if (&DefMI == MI) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 990 | return true; // MI is defining something KillMI uses |
Owen Anderson | b36376e | 2014-03-17 19:36:09 +0000 | [diff] [blame] | 991 | DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(&DefMI); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 992 | if (DDI == DistanceMap.end()) |
| 993 | return true; // Below MI |
| 994 | unsigned DefDist = DDI->second; |
| 995 | assert(Dist > DefDist && "Visited def already?"); |
Owen Anderson | b36376e | 2014-03-17 19:36:09 +0000 | [diff] [blame] | 996 | if (TII->getInstrLatency(InstrItins, &DefMI) > (Dist - DefDist)) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 997 | return true; |
| 998 | } |
| 999 | return false; |
| 1000 | } |
| 1001 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 1002 | /// If there is one more local instruction that reads 'Reg' and it kills 'Reg, |
| 1003 | /// consider moving the kill instruction above the current two-address |
| 1004 | /// instruction in order to eliminate the need for the copy. |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 1005 | bool TwoAddressInstructionPass:: |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 1006 | rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 1007 | MachineBasicBlock::iterator &nmi, |
| 1008 | unsigned Reg) { |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 1009 | // Bail immediately if we don't have LV or LIS available. We use them to find |
| 1010 | // kills efficiently. |
| 1011 | if (!LV && !LIS) |
Chandler Carruth | db5536f | 2012-07-15 03:29:46 +0000 | [diff] [blame] | 1012 | return false; |
| 1013 | |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1014 | MachineInstr *MI = &*mi; |
| 1015 | DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); |
| 1016 | if (DI == DistanceMap.end()) |
| 1017 | // Must be created from unfolded load. Don't waste time trying this. |
| 1018 | return false; |
| 1019 | |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 1020 | MachineInstr *KillMI = nullptr; |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 1021 | if (LIS) { |
| 1022 | LiveInterval &LI = LIS->getInterval(Reg); |
| 1023 | assert(LI.end() != LI.begin() && |
| 1024 | "Reg should not have empty live interval."); |
| 1025 | |
| 1026 | SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); |
| 1027 | LiveInterval::const_iterator I = LI.find(MBBEndIdx); |
| 1028 | if (I != LI.end() && I->start < MBBEndIdx) |
| 1029 | return false; |
| 1030 | |
| 1031 | --I; |
| 1032 | KillMI = LIS->getInstructionFromIndex(I->end); |
| 1033 | } else { |
| 1034 | KillMI = LV->getVarInfo(Reg).findKill(MBB); |
| 1035 | } |
Chandler Carruth | db5536f | 2012-07-15 03:29:46 +0000 | [diff] [blame] | 1036 | if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike()) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1037 | // Don't mess with copies, they may be coalesced later. |
| 1038 | return false; |
| 1039 | |
| 1040 | unsigned DstReg; |
| 1041 | if (isTwoAddrUse(*KillMI, Reg, DstReg)) |
| 1042 | return false; |
| 1043 | |
Evan Cheng | 7098c4e | 2011-11-15 06:26:51 +0000 | [diff] [blame] | 1044 | bool SeenStore = true; |
Matthias Braun | 07066cc | 2015-05-19 21:22:20 +0000 | [diff] [blame] | 1045 | if (!KillMI->isSafeToMove(AA, SeenStore)) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1046 | return false; |
| 1047 | |
| 1048 | SmallSet<unsigned, 2> Uses; |
| 1049 | SmallSet<unsigned, 2> Kills; |
| 1050 | SmallSet<unsigned, 2> Defs; |
| 1051 | SmallSet<unsigned, 2> LiveDefs; |
Sanjay Patel | 0b2a949 | 2015-12-01 19:57:43 +0000 | [diff] [blame] | 1052 | for (const MachineOperand &MO : KillMI->operands()) { |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1053 | if (!MO.isReg()) |
| 1054 | continue; |
| 1055 | unsigned MOReg = MO.getReg(); |
| 1056 | if (MO.isUse()) { |
| 1057 | if (!MOReg) |
| 1058 | continue; |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 1059 | if (isDefTooClose(MOReg, DI->second, MI)) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1060 | return false; |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 1061 | bool isKill = MO.isKill() || (LIS && isPlainlyKilled(KillMI, MOReg, LIS)); |
| 1062 | if (MOReg == Reg && !isKill) |
Chandler Carruth | db5536f | 2012-07-15 03:29:46 +0000 | [diff] [blame] | 1063 | return false; |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1064 | Uses.insert(MOReg); |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 1065 | if (isKill && MOReg != Reg) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1066 | Kills.insert(MOReg); |
| 1067 | } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) { |
| 1068 | Defs.insert(MOReg); |
| 1069 | if (!MO.isDead()) |
| 1070 | LiveDefs.insert(MOReg); |
| 1071 | } |
| 1072 | } |
| 1073 | |
| 1074 | // Check if the reschedule will not break depedencies. |
| 1075 | unsigned NumVisited = 0; |
| 1076 | MachineBasicBlock::iterator KillPos = KillMI; |
| 1077 | for (MachineBasicBlock::iterator I = mi; I != KillPos; ++I) { |
| 1078 | MachineInstr *OtherMI = I; |
| 1079 | // DBG_VALUE cannot be counted against the limit. |
| 1080 | if (OtherMI->isDebugValue()) |
| 1081 | continue; |
| 1082 | if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. |
| 1083 | return false; |
| 1084 | ++NumVisited; |
Evan Cheng | 7f8e563 | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 1085 | if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() || |
| 1086 | OtherMI->isBranch() || OtherMI->isTerminator()) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1087 | // Don't move pass calls, etc. |
| 1088 | return false; |
Evan Cheng | 9ddd69a | 2011-11-16 03:05:12 +0000 | [diff] [blame] | 1089 | SmallVector<unsigned, 2> OtherDefs; |
Sanjay Patel | 0b2a949 | 2015-12-01 19:57:43 +0000 | [diff] [blame] | 1090 | for (const MachineOperand &MO : OtherMI->operands()) { |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1091 | if (!MO.isReg()) |
| 1092 | continue; |
| 1093 | unsigned MOReg = MO.getReg(); |
| 1094 | if (!MOReg) |
| 1095 | continue; |
| 1096 | if (MO.isUse()) { |
| 1097 | if (Defs.count(MOReg)) |
| 1098 | // Moving KillMI can clobber the physical register if the def has |
| 1099 | // not been seen. |
| 1100 | return false; |
| 1101 | if (Kills.count(MOReg)) |
| 1102 | // Don't want to extend other live ranges and update kills. |
| 1103 | return false; |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 1104 | if (OtherMI != MI && MOReg == Reg && |
| 1105 | !(MO.isKill() || (LIS && isPlainlyKilled(OtherMI, MOReg, LIS)))) |
Chandler Carruth | db5536f | 2012-07-15 03:29:46 +0000 | [diff] [blame] | 1106 | // We can't schedule across a use of the register in question. |
| 1107 | return false; |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1108 | } else { |
Evan Cheng | 9ddd69a | 2011-11-16 03:05:12 +0000 | [diff] [blame] | 1109 | OtherDefs.push_back(MOReg); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1110 | } |
| 1111 | } |
Evan Cheng | 9ddd69a | 2011-11-16 03:05:12 +0000 | [diff] [blame] | 1112 | |
| 1113 | for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) { |
| 1114 | unsigned MOReg = OtherDefs[i]; |
| 1115 | if (Uses.count(MOReg)) |
| 1116 | return false; |
| 1117 | if (TargetRegisterInfo::isPhysicalRegister(MOReg) && |
| 1118 | LiveDefs.count(MOReg)) |
| 1119 | return false; |
| 1120 | // Physical register def is seen. |
| 1121 | Defs.erase(MOReg); |
| 1122 | } |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1123 | } |
| 1124 | |
| 1125 | // Move the old kill above MI, don't forget to move debug info as well. |
| 1126 | MachineBasicBlock::iterator InsertPos = mi; |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 1127 | while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugValue()) |
Evan Cheng | f2fc508 | 2011-11-14 21:11:15 +0000 | [diff] [blame] | 1128 | --InsertPos; |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1129 | MachineBasicBlock::iterator From = KillMI; |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 1130 | MachineBasicBlock::iterator To = std::next(From); |
| 1131 | while (std::prev(From)->isDebugValue()) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1132 | --From; |
| 1133 | MBB->splice(InsertPos, MBB, From, To); |
| 1134 | |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 1135 | nmi = std::prev(InsertPos); // Backtrack so we process the moved instr. |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1136 | DistanceMap.erase(DI); |
| 1137 | |
Chandler Carruth | db5536f | 2012-07-15 03:29:46 +0000 | [diff] [blame] | 1138 | // Update live variables |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 1139 | if (LIS) { |
Jakob Stoklund Olesen | 24bc514 | 2012-08-03 22:58:34 +0000 | [diff] [blame] | 1140 | LIS->handleMove(KillMI); |
Cameron Zwarich | 7d13fb4 | 2013-02-23 04:49:13 +0000 | [diff] [blame] | 1141 | } else { |
| 1142 | LV->removeVirtualRegisterKilled(Reg, KillMI); |
| 1143 | LV->addVirtualRegisterKilled(Reg, MI); |
| 1144 | } |
Chandler Carruth | db5536f | 2012-07-15 03:29:46 +0000 | [diff] [blame] | 1145 | |
Jakob Stoklund Olesen | 0ef0311 | 2012-07-17 17:57:23 +0000 | [diff] [blame] | 1146 | DEBUG(dbgs() << "\trescheduled kill: " << *KillMI); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1147 | return true; |
| 1148 | } |
| 1149 | |
Andrew Kaylor | 16c4da0 | 2015-09-28 20:33:22 +0000 | [diff] [blame] | 1150 | /// Tries to commute the operand 'BaseOpIdx' and some other operand in the |
| 1151 | /// given machine instruction to improve opportunities for coalescing and |
| 1152 | /// elimination of a register to register copy. |
| 1153 | /// |
| 1154 | /// 'DstOpIdx' specifies the index of MI def operand. |
| 1155 | /// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx' |
| 1156 | /// operand is killed by the given instruction. |
| 1157 | /// The 'Dist' arguments provides the distance of MI from the start of the |
| 1158 | /// current basic block and it is used to determine if it is profitable |
| 1159 | /// to commute operands in the instruction. |
| 1160 | /// |
| 1161 | /// Returns true if the transformation happened. Otherwise, returns false. |
| 1162 | bool TwoAddressInstructionPass::tryInstructionCommute(MachineInstr *MI, |
| 1163 | unsigned DstOpIdx, |
| 1164 | unsigned BaseOpIdx, |
| 1165 | bool BaseOpKilled, |
| 1166 | unsigned Dist) { |
| 1167 | unsigned DstOpReg = MI->getOperand(DstOpIdx).getReg(); |
| 1168 | unsigned BaseOpReg = MI->getOperand(BaseOpIdx).getReg(); |
| 1169 | unsigned OpsNum = MI->getDesc().getNumOperands(); |
| 1170 | unsigned OtherOpIdx = MI->getDesc().getNumDefs(); |
| 1171 | for (; OtherOpIdx < OpsNum; OtherOpIdx++) { |
| 1172 | // The call of findCommutedOpIndices below only checks if BaseOpIdx |
Sanjay Patel | 96824de | 2015-12-01 19:19:18 +0000 | [diff] [blame] | 1173 | // and OtherOpIdx are commutable, it does not really search for |
Andrew Kaylor | 16c4da0 | 2015-09-28 20:33:22 +0000 | [diff] [blame] | 1174 | // other commutable operands and does not change the values of passed |
| 1175 | // variables. |
| 1176 | if (OtherOpIdx == BaseOpIdx || |
| 1177 | !TII->findCommutedOpIndices(MI, BaseOpIdx, OtherOpIdx)) |
| 1178 | continue; |
| 1179 | |
| 1180 | unsigned OtherOpReg = MI->getOperand(OtherOpIdx).getReg(); |
| 1181 | bool AggressiveCommute = false; |
| 1182 | |
| 1183 | // If OtherOp dies but BaseOp does not, swap the OtherOp and BaseOp |
| 1184 | // operands. This makes the live ranges of DstOp and OtherOp joinable. |
| 1185 | bool DoCommute = |
| 1186 | !BaseOpKilled && isKilled(*MI, OtherOpReg, MRI, TII, LIS, false); |
| 1187 | |
| 1188 | if (!DoCommute && |
| 1189 | isProfitableToCommute(DstOpReg, BaseOpReg, OtherOpReg, MI, Dist)) { |
| 1190 | DoCommute = true; |
| 1191 | AggressiveCommute = true; |
| 1192 | } |
| 1193 | |
| 1194 | // If it's profitable to commute, try to do so. |
| 1195 | if (DoCommute && commuteInstruction(MI, BaseOpIdx, OtherOpIdx, Dist)) { |
| 1196 | ++NumCommuted; |
| 1197 | if (AggressiveCommute) |
| 1198 | ++NumAggrCommuted; |
| 1199 | return true; |
| 1200 | } |
| 1201 | } |
| 1202 | return false; |
| 1203 | } |
| 1204 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 1205 | /// For the case where an instruction has a single pair of tied register |
| 1206 | /// operands, attempt some transformations that may either eliminate the tied |
| 1207 | /// operands or improve the opportunities for coalescing away the register copy. |
| 1208 | /// Returns true if no copy needs to be inserted to untie mi's operands |
| 1209 | /// (either because they were untied, or because mi was rescheduled, and will |
| 1210 | /// be visited again later). If the shouldOnlyCommute flag is true, only |
| 1211 | /// instruction commutation is attempted. |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1212 | bool TwoAddressInstructionPass:: |
Jakob Stoklund Olesen | 112a44d | 2012-10-26 21:12:49 +0000 | [diff] [blame] | 1213 | tryInstructionTransform(MachineBasicBlock::iterator &mi, |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1214 | MachineBasicBlock::iterator &nmi, |
Cameron Zwarich | f05c0cb | 2013-02-24 00:27:26 +0000 | [diff] [blame] | 1215 | unsigned SrcIdx, unsigned DstIdx, |
| 1216 | unsigned Dist, bool shouldOnlyCommute) { |
Evan Cheng | 822ddde | 2011-11-16 18:44:48 +0000 | [diff] [blame] | 1217 | if (OptLevel == CodeGenOpt::None) |
| 1218 | return false; |
| 1219 | |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1220 | MachineInstr &MI = *mi; |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1221 | unsigned regA = MI.getOperand(DstIdx).getReg(); |
| 1222 | unsigned regB = MI.getOperand(SrcIdx).getReg(); |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1223 | |
| 1224 | assert(TargetRegisterInfo::isVirtualRegister(regB) && |
| 1225 | "cannot make instruction into two-address form"); |
Cameron Zwarich | 384026b | 2013-02-21 22:58:42 +0000 | [diff] [blame] | 1226 | bool regBKilled = isKilled(MI, regB, MRI, TII, LIS, true); |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1227 | |
Evan Cheng | b64e7b7 | 2012-05-03 01:45:13 +0000 | [diff] [blame] | 1228 | if (TargetRegisterInfo::isVirtualRegister(regA)) |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 1229 | scanUses(regA); |
Evan Cheng | b64e7b7 | 2012-05-03 01:45:13 +0000 | [diff] [blame] | 1230 | |
Andrew Kaylor | 16c4da0 | 2015-09-28 20:33:22 +0000 | [diff] [blame] | 1231 | bool Commuted = tryInstructionCommute(&MI, DstIdx, SrcIdx, regBKilled, Dist); |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1232 | |
Quentin Colombet | 9729fb3 | 2015-07-01 23:12:13 +0000 | [diff] [blame] | 1233 | // If the instruction is convertible to 3 Addr, instead |
| 1234 | // of returning try 3 Addr transformation aggresively and |
| 1235 | // use this variable to check later. Because it might be better. |
| 1236 | // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret` |
| 1237 | // instead of the following code. |
NAKAMURA Takumi | 8496503 | 2015-09-22 11:14:12 +0000 | [diff] [blame] | 1238 | // addl %esi, %edi |
| 1239 | // movl %edi, %eax |
Quentin Colombet | 9729fb3 | 2015-07-01 23:12:13 +0000 | [diff] [blame] | 1240 | // ret |
Andrew Kaylor | 16c4da0 | 2015-09-28 20:33:22 +0000 | [diff] [blame] | 1241 | if (Commuted && !MI.isConvertibleTo3Addr()) |
| 1242 | return false; |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1243 | |
Cameron Zwarich | f05c0cb | 2013-02-24 00:27:26 +0000 | [diff] [blame] | 1244 | if (shouldOnlyCommute) |
| 1245 | return false; |
| 1246 | |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1247 | // If there is one more use of regB later in the same MBB, consider |
| 1248 | // re-schedule this MI below it. |
Quentin Colombet | 40dd510 | 2015-07-06 20:12:54 +0000 | [diff] [blame] | 1249 | if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) { |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1250 | ++NumReSchedDowns; |
Lang Hames | 3ad11ff | 2012-04-09 20:17:30 +0000 | [diff] [blame] | 1251 | return true; |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1252 | } |
| 1253 | |
Craig Topper | 2c4068f | 2015-10-06 05:39:59 +0000 | [diff] [blame] | 1254 | // If we commuted, regB may have changed so we should re-sample it to avoid |
| 1255 | // confusing the three address conversion below. |
| 1256 | if (Commuted) { |
| 1257 | regB = MI.getOperand(SrcIdx).getReg(); |
| 1258 | regBKilled = isKilled(MI, regB, MRI, TII, LIS, true); |
| 1259 | } |
| 1260 | |
Evan Cheng | 7f8e563 | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 1261 | if (MI.isConvertibleTo3Addr()) { |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1262 | // This instruction is potentially convertible to a true |
| 1263 | // three-address instruction. Check if it is profitable. |
Evan Cheng | 15fed7a | 2011-03-02 01:08:17 +0000 | [diff] [blame] | 1264 | if (!regBKilled || isProfitableToConv3Addr(regA, regB)) { |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1265 | // Try to convert it. |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 1266 | if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) { |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1267 | ++NumConvertedTo3Addr; |
| 1268 | return true; // Done with this instruction. |
| 1269 | } |
| 1270 | } |
| 1271 | } |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1272 | |
Quentin Colombet | 9729fb3 | 2015-07-01 23:12:13 +0000 | [diff] [blame] | 1273 | // Return if it is commuted but 3 addr conversion is failed. |
Quentin Colombet | 40dd510 | 2015-07-06 20:12:54 +0000 | [diff] [blame] | 1274 | if (Commuted) |
Quentin Colombet | 9729fb3 | 2015-07-01 23:12:13 +0000 | [diff] [blame] | 1275 | return false; |
| 1276 | |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1277 | // If there is one more use of regB later in the same MBB, consider |
| 1278 | // re-schedule it before this MI if it's legal. |
Andrew Trick | 608a698 | 2013-04-24 15:54:39 +0000 | [diff] [blame] | 1279 | if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) { |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1280 | ++NumReSchedUps; |
Lang Hames | 3ad11ff | 2012-04-09 20:17:30 +0000 | [diff] [blame] | 1281 | return true; |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1282 | } |
| 1283 | |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1284 | // If this is an instruction with a load folded into it, try unfolding |
| 1285 | // the load, e.g. avoid this: |
| 1286 | // movq %rdx, %rcx |
| 1287 | // addq (%rax), %rcx |
| 1288 | // in favor of this: |
| 1289 | // movq (%rax), %rcx |
| 1290 | // addq %rdx, %rcx |
| 1291 | // because it's preferable to schedule a load than a register copy. |
Evan Cheng | 7f8e563 | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 1292 | if (MI.mayLoad() && !regBKilled) { |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1293 | // Determine if a load can be unfolded. |
| 1294 | unsigned LoadRegIndex; |
| 1295 | unsigned NewOpc = |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1296 | TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1297 | /*UnfoldLoad=*/true, |
| 1298 | /*UnfoldStore=*/false, |
| 1299 | &LoadRegIndex); |
| 1300 | if (NewOpc != 0) { |
Evan Cheng | 6cc775f | 2011-06-28 19:10:37 +0000 | [diff] [blame] | 1301 | const MCInstrDesc &UnfoldMCID = TII->get(NewOpc); |
| 1302 | if (UnfoldMCID.getNumDefs() == 1) { |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1303 | // Unfold the load. |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1304 | DEBUG(dbgs() << "2addr: UNFOLDING: " << MI); |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1305 | const TargetRegisterClass *RC = |
Andrew Trick | 32aea35 | 2012-05-03 01:14:37 +0000 | [diff] [blame] | 1306 | TRI->getAllocatableClass( |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1307 | TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF)); |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1308 | unsigned Reg = MRI->createVirtualRegister(RC); |
| 1309 | SmallVector<MachineInstr *, 2> NewMIs; |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1310 | if (!TII->unfoldMemoryOperand(*MF, &MI, Reg, |
Evan Cheng | 0ce8448 | 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 | 3c1b3c6 | 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. |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 1323 | MBB->insert(mi, NewMIs[0]); |
| 1324 | MBB->insert(mi, NewMIs[1]); |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 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]; |
Cameron Zwarich | 6868f38 | 2013-02-24 00:27:29 +0000 | [diff] [blame] | 1333 | bool TransformResult = |
Cameron Zwarich | f05c0cb | 2013-02-24 00:27:26 +0000 | [diff] [blame] | 1334 | tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist, true); |
Cameron Zwarich | 1b4c64c | 2013-02-24 01:26:05 +0000 | [diff] [blame] | 1335 | (void)TransformResult; |
Cameron Zwarich | 6868f38 | 2013-02-24 00:27:29 +0000 | [diff] [blame] | 1336 | assert(!TransformResult && |
| 1337 | "tryInstructionTransform() should return false."); |
| 1338 | if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) { |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1339 | // Success, or at least we made an improvement. Keep the unfolded |
| 1340 | // instructions and discard the original. |
| 1341 | if (LV) { |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1342 | for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { |
| 1343 | MachineOperand &MO = MI.getOperand(i); |
Andrew Trick | 808a7a6 | 2012-02-03 05:12:30 +0000 | [diff] [blame] | 1344 | if (MO.isReg() && |
Dan Gohman | 851e478 | 2010-06-22 00:32:04 +0000 | [diff] [blame] | 1345 | TargetRegisterInfo::isVirtualRegister(MO.getReg())) { |
| 1346 | if (MO.isUse()) { |
Dan Gohman | 2370e2f | 2010-06-22 02:07:21 +0000 | [diff] [blame] | 1347 | if (MO.isKill()) { |
| 1348 | if (NewMIs[0]->killsRegister(MO.getReg())) |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1349 | LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[0]); |
Dan Gohman | 2370e2f | 2010-06-22 02:07:21 +0000 | [diff] [blame] | 1350 | else { |
| 1351 | assert(NewMIs[1]->killsRegister(MO.getReg()) && |
| 1352 | "Kill missing after load unfold!"); |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1353 | LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[1]); |
Dan Gohman | 2370e2f | 2010-06-22 02:07:21 +0000 | [diff] [blame] | 1354 | } |
| 1355 | } |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1356 | } else if (LV->removeVirtualRegisterDead(MO.getReg(), &MI)) { |
Dan Gohman | 2370e2f | 2010-06-22 02:07:21 +0000 | [diff] [blame] | 1357 | if (NewMIs[1]->registerDefIsDead(MO.getReg())) |
| 1358 | LV->addVirtualRegisterDead(MO.getReg(), NewMIs[1]); |
| 1359 | else { |
| 1360 | assert(NewMIs[0]->registerDefIsDead(MO.getReg()) && |
| 1361 | "Dead flag missing after load unfold!"); |
| 1362 | LV->addVirtualRegisterDead(MO.getReg(), NewMIs[0]); |
| 1363 | } |
| 1364 | } |
Dan Gohman | 851e478 | 2010-06-22 00:32:04 +0000 | [diff] [blame] | 1365 | } |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1366 | } |
| 1367 | LV->addVirtualRegisterKilled(Reg, NewMIs[1]); |
| 1368 | } |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1369 | |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1370 | SmallVector<unsigned, 4> OrigRegs; |
| 1371 | if (LIS) { |
Craig Topper | da5168b | 2015-10-08 06:06:42 +0000 | [diff] [blame] | 1372 | for (const MachineOperand &MO : MI.operands()) { |
| 1373 | if (MO.isReg()) |
| 1374 | OrigRegs.push_back(MO.getReg()); |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1375 | } |
| 1376 | } |
| 1377 | |
Evan Cheng | 30f44ad | 2011-11-14 19:48:55 +0000 | [diff] [blame] | 1378 | MI.eraseFromParent(); |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1379 | |
| 1380 | // Update LiveIntervals. |
Cameron Zwarich | caad7e1 | 2013-02-20 22:10:00 +0000 | [diff] [blame] | 1381 | if (LIS) { |
| 1382 | MachineBasicBlock::iterator Begin(NewMIs[0]); |
| 1383 | MachineBasicBlock::iterator End(NewMIs[1]); |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1384 | LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs); |
Cameron Zwarich | caad7e1 | 2013-02-20 22:10:00 +0000 | [diff] [blame] | 1385 | } |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1386 | |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1387 | mi = NewMIs[1]; |
Dan Gohman | 3c1b3c6 | 2010-06-21 22:17:20 +0000 | [diff] [blame] | 1388 | } else { |
| 1389 | // Transforming didn't eliminate the tie and didn't lead to an |
| 1390 | // improvement. Clean up the unfolded instructions and keep the |
| 1391 | // original. |
| 1392 | DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); |
| 1393 | NewMIs[0]->eraseFromParent(); |
| 1394 | NewMIs[1]->eraseFromParent(); |
| 1395 | } |
| 1396 | } |
| 1397 | } |
| 1398 | } |
| 1399 | |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1400 | return false; |
| 1401 | } |
| 1402 | |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1403 | // Collect tied operands of MI that need to be handled. |
| 1404 | // Rewrite trivial cases immediately. |
| 1405 | // Return true if any tied operands where found, including the trivial ones. |
| 1406 | bool TwoAddressInstructionPass:: |
| 1407 | collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) { |
| 1408 | const MCInstrDesc &MCID = MI->getDesc(); |
| 1409 | bool AnyOps = false; |
Jakob Stoklund Olesen | ade363e | 2012-09-04 22:59:30 +0000 | [diff] [blame] | 1410 | unsigned NumOps = MI->getNumOperands(); |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1411 | |
| 1412 | for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) { |
| 1413 | unsigned DstIdx = 0; |
| 1414 | if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx)) |
| 1415 | continue; |
| 1416 | AnyOps = true; |
Jakob Stoklund Olesen | fbf45dc | 2012-08-07 22:47:06 +0000 | [diff] [blame] | 1417 | MachineOperand &SrcMO = MI->getOperand(SrcIdx); |
| 1418 | MachineOperand &DstMO = MI->getOperand(DstIdx); |
| 1419 | unsigned SrcReg = SrcMO.getReg(); |
| 1420 | unsigned DstReg = DstMO.getReg(); |
| 1421 | // Tied constraint already satisfied? |
| 1422 | if (SrcReg == DstReg) |
| 1423 | continue; |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1424 | |
Jakob Stoklund Olesen | fbf45dc | 2012-08-07 22:47:06 +0000 | [diff] [blame] | 1425 | assert(SrcReg && SrcMO.isUse() && "two address instruction invalid"); |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1426 | |
| 1427 | // Deal with <undef> uses immediately - simply rewrite the src operand. |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1428 | if (SrcMO.isUndef() && !DstMO.getSubReg()) { |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1429 | // Constrain the DstReg register class if required. |
| 1430 | if (TargetRegisterInfo::isVirtualRegister(DstReg)) |
| 1431 | if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx, |
| 1432 | TRI, *MF)) |
| 1433 | MRI->constrainRegClass(DstReg, RC); |
Jakob Stoklund Olesen | fbf45dc | 2012-08-07 22:47:06 +0000 | [diff] [blame] | 1434 | SrcMO.setReg(DstReg); |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1435 | SrcMO.setSubReg(0); |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1436 | DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI); |
| 1437 | continue; |
| 1438 | } |
Jakob Stoklund Olesen | fbf45dc | 2012-08-07 22:47:06 +0000 | [diff] [blame] | 1439 | TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx)); |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1440 | } |
| 1441 | return AnyOps; |
| 1442 | } |
| 1443 | |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1444 | // Process a list of tied MI operands that all use the same source register. |
| 1445 | // The tied pairs are of the form (SrcIdx, DstIdx). |
| 1446 | void |
| 1447 | TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, |
| 1448 | TiedPairList &TiedPairs, |
| 1449 | unsigned &Dist) { |
| 1450 | bool IsEarlyClobber = false; |
Cameron Zwarich | 2991feb | 2013-02-20 06:46:46 +0000 | [diff] [blame] | 1451 | for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { |
| 1452 | const MachineOperand &DstMO = MI->getOperand(TiedPairs[tpi].second); |
| 1453 | IsEarlyClobber |= DstMO.isEarlyClobber(); |
| 1454 | } |
| 1455 | |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1456 | bool RemovedKillFlag = false; |
| 1457 | bool AllUsesCopied = true; |
| 1458 | unsigned LastCopiedReg = 0; |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1459 | SlotIndex LastCopyIdx; |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1460 | unsigned RegB = 0; |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1461 | unsigned SubRegB = 0; |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1462 | for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { |
| 1463 | unsigned SrcIdx = TiedPairs[tpi].first; |
| 1464 | unsigned DstIdx = TiedPairs[tpi].second; |
| 1465 | |
| 1466 | const MachineOperand &DstMO = MI->getOperand(DstIdx); |
| 1467 | unsigned RegA = DstMO.getReg(); |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1468 | |
| 1469 | // Grab RegB from the instruction because it may have changed if the |
| 1470 | // instruction was commuted. |
| 1471 | RegB = MI->getOperand(SrcIdx).getReg(); |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1472 | SubRegB = MI->getOperand(SrcIdx).getSubReg(); |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1473 | |
| 1474 | if (RegA == RegB) { |
| 1475 | // The register is tied to multiple destinations (or else we would |
| 1476 | // not have continued this far), but this use of the register |
| 1477 | // already matches the tied destination. Leave it. |
| 1478 | AllUsesCopied = false; |
| 1479 | continue; |
| 1480 | } |
| 1481 | LastCopiedReg = RegA; |
| 1482 | |
| 1483 | assert(TargetRegisterInfo::isVirtualRegister(RegB) && |
| 1484 | "cannot make instruction into two-address form"); |
| 1485 | |
| 1486 | #ifndef NDEBUG |
| 1487 | // First, verify that we don't have a use of "a" in the instruction |
| 1488 | // (a = b + a for example) because our transformation will not |
| 1489 | // work. This should never occur because we are in SSA form. |
| 1490 | for (unsigned i = 0; i != MI->getNumOperands(); ++i) |
| 1491 | assert(i == DstIdx || |
| 1492 | !MI->getOperand(i).isReg() || |
| 1493 | MI->getOperand(i).getReg() != RegA); |
| 1494 | #endif |
| 1495 | |
| 1496 | // Emit a copy. |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1497 | MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), |
| 1498 | TII->get(TargetOpcode::COPY), RegA); |
| 1499 | // If this operand is folding a truncation, the truncation now moves to the |
| 1500 | // copy so that the register classes remain valid for the operands. |
| 1501 | MIB.addReg(RegB, 0, SubRegB); |
| 1502 | const TargetRegisterClass *RC = MRI->getRegClass(RegB); |
| 1503 | if (SubRegB) { |
| 1504 | if (TargetRegisterInfo::isVirtualRegister(RegA)) { |
| 1505 | assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA), |
| 1506 | SubRegB) && |
| 1507 | "tied subregister must be a truncation"); |
| 1508 | // The superreg class will not be used to constrain the subreg class. |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 1509 | RC = nullptr; |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1510 | } |
| 1511 | else { |
| 1512 | assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB)) |
| 1513 | && "tied subregister must be a truncation"); |
| 1514 | } |
| 1515 | } |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1516 | |
| 1517 | // Update DistanceMap. |
| 1518 | MachineBasicBlock::iterator PrevMI = MI; |
| 1519 | --PrevMI; |
| 1520 | DistanceMap.insert(std::make_pair(PrevMI, Dist)); |
| 1521 | DistanceMap[MI] = ++Dist; |
| 1522 | |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1523 | if (LIS) { |
| 1524 | LastCopyIdx = LIS->InsertMachineInstrInMaps(PrevMI).getRegSlot(); |
| 1525 | |
| 1526 | if (TargetRegisterInfo::isVirtualRegister(RegA)) { |
| 1527 | LiveInterval &LI = LIS->getInterval(RegA); |
| 1528 | VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator()); |
| 1529 | SlotIndex endIdx = |
| 1530 | LIS->getInstructionIndex(MI).getRegSlot(IsEarlyClobber); |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 1531 | LI.addSegment(LiveInterval::Segment(LastCopyIdx, endIdx, VNI)); |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1532 | } |
| 1533 | } |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1534 | |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1535 | DEBUG(dbgs() << "\t\tprepend:\t" << *MIB); |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1536 | |
| 1537 | MachineOperand &MO = MI->getOperand(SrcIdx); |
| 1538 | assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() && |
| 1539 | "inconsistent operand info for 2-reg pass"); |
| 1540 | if (MO.isKill()) { |
| 1541 | MO.setIsKill(false); |
| 1542 | RemovedKillFlag = true; |
| 1543 | } |
| 1544 | |
| 1545 | // Make sure regA is a legal regclass for the SrcIdx operand. |
| 1546 | if (TargetRegisterInfo::isVirtualRegister(RegA) && |
| 1547 | TargetRegisterInfo::isVirtualRegister(RegB)) |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1548 | MRI->constrainRegClass(RegA, RC); |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1549 | MO.setReg(RegA); |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1550 | // The getMatchingSuper asserts guarantee that the register class projected |
| 1551 | // by SubRegB is compatible with RegA with no subregister. So regardless of |
| 1552 | // whether the dest oper writes a subreg, the source oper should not. |
| 1553 | MO.setSubReg(0); |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1554 | |
| 1555 | // Propagate SrcRegMap. |
| 1556 | SrcRegMap[RegA] = RegB; |
| 1557 | } |
| 1558 | |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1559 | if (AllUsesCopied) { |
| 1560 | if (!IsEarlyClobber) { |
| 1561 | // Replace other (un-tied) uses of regB with LastCopiedReg. |
Sanjay Patel | 0b2a949 | 2015-12-01 19:57:43 +0000 | [diff] [blame] | 1562 | for (MachineOperand &MO : MI->operands()) { |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1563 | if (MO.isReg() && MO.getReg() == RegB && MO.getSubReg() == SubRegB && |
| 1564 | MO.isUse()) { |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1565 | if (MO.isKill()) { |
| 1566 | MO.setIsKill(false); |
| 1567 | RemovedKillFlag = true; |
| 1568 | } |
| 1569 | MO.setReg(LastCopiedReg); |
Andrew Trick | e339828 | 2013-12-17 04:50:45 +0000 | [diff] [blame] | 1570 | MO.setSubReg(0); |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1571 | } |
| 1572 | } |
| 1573 | } |
| 1574 | |
| 1575 | // Update live variables for regB. |
| 1576 | if (RemovedKillFlag && LV && LV->getVarInfo(RegB).removeKill(MI)) { |
| 1577 | MachineBasicBlock::iterator PrevMI = MI; |
| 1578 | --PrevMI; |
| 1579 | LV->addVirtualRegisterKilled(RegB, PrevMI); |
| 1580 | } |
| 1581 | |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1582 | // Update LiveIntervals. |
| 1583 | if (LIS) { |
| 1584 | LiveInterval &LI = LIS->getInterval(RegB); |
| 1585 | SlotIndex MIIdx = LIS->getInstructionIndex(MI); |
| 1586 | LiveInterval::const_iterator I = LI.find(MIIdx); |
| 1587 | assert(I != LI.end() && "RegB must be live-in to use."); |
| 1588 | |
| 1589 | SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber); |
| 1590 | if (I->end == UseIdx) |
Matthias Braun | 13ddb7c | 2013-10-10 21:28:43 +0000 | [diff] [blame] | 1591 | LI.removeSegment(LastCopyIdx, UseIdx); |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1592 | } |
| 1593 | |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1594 | } else if (RemovedKillFlag) { |
| 1595 | // Some tied uses of regB matched their destination registers, so |
| 1596 | // regB is still used in this instruction, but a kill flag was |
| 1597 | // removed from a different tied use of regB, so now we need to add |
| 1598 | // a kill flag to one of the remaining uses of regB. |
Sanjay Patel | 0b2a949 | 2015-12-01 19:57:43 +0000 | [diff] [blame] | 1599 | for (MachineOperand &MO : MI->operands()) { |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1600 | if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) { |
| 1601 | MO.setIsKill(true); |
| 1602 | break; |
| 1603 | } |
| 1604 | } |
| 1605 | } |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1606 | } |
| 1607 | |
Sanjay Patel | b53791e | 2015-12-01 19:32:35 +0000 | [diff] [blame] | 1608 | /// Reduce two-address instructions to two operands. |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1609 | bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) { |
| 1610 | MF = &Func; |
| 1611 | const TargetMachine &TM = MF->getTarget(); |
| 1612 | MRI = &MF->getRegInfo(); |
Eric Christopher | 3372620 | 2015-01-27 08:48:42 +0000 | [diff] [blame] | 1613 | TII = MF->getSubtarget().getInstrInfo(); |
| 1614 | TRI = MF->getSubtarget().getRegisterInfo(); |
| 1615 | InstrItins = MF->getSubtarget().getInstrItineraryData(); |
Duncan Sands | 5a913d6 | 2009-01-28 13:14:17 +0000 | [diff] [blame] | 1616 | LV = getAnalysisIfAvailable<LiveVariables>(); |
Jakob Stoklund Olesen | 24bc514 | 2012-08-03 22:58:34 +0000 | [diff] [blame] | 1617 | LIS = getAnalysisIfAvailable<LiveIntervals>(); |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 1618 | AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); |
Evan Cheng | 822ddde | 2011-11-16 18:44:48 +0000 | [diff] [blame] | 1619 | OptLevel = TM.getOptLevel(); |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1620 | |
Misha Brukman | 6dd644e | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 1621 | bool MadeChange = false; |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1622 | |
David Greene | ac9f819 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 1623 | DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n"); |
Andrew Trick | 808a7a6 | 2012-02-03 05:12:30 +0000 | [diff] [blame] | 1624 | DEBUG(dbgs() << "********** Function: " |
Craig Topper | a538d83 | 2012-08-22 06:07:19 +0000 | [diff] [blame] | 1625 | << MF->getName() << '\n'); |
Alkis Evlogimenos | 26583db | 2004-02-18 00:35:06 +0000 | [diff] [blame] | 1626 | |
Jakob Stoklund Olesen | 9760f04 | 2011-07-29 22:51:22 +0000 | [diff] [blame] | 1627 | // This pass takes the function out of SSA form. |
| 1628 | MRI->leaveSSA(); |
| 1629 | |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1630 | TiedOperandMap TiedOperands; |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 1631 | for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); |
| 1632 | MBBI != MBBE; ++MBBI) { |
Duncan P. N. Exon Smith | f1ff53e | 2015-10-09 22:56:24 +0000 | [diff] [blame] | 1633 | MBB = &*MBBI; |
Evan Cheng | c5618eb | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 1634 | unsigned Dist = 0; |
| 1635 | DistanceMap.clear(); |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 1636 | SrcRegMap.clear(); |
| 1637 | DstRegMap.clear(); |
| 1638 | Processed.clear(); |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 1639 | for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end(); |
Evan Cheng | 5832410 | 2008-03-27 01:27:25 +0000 | [diff] [blame] | 1640 | mi != me; ) { |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 1641 | MachineBasicBlock::iterator nmi = std::next(mi); |
Dale Johannesen | 8bba160 | 2010-02-10 21:47:48 +0000 | [diff] [blame] | 1642 | if (mi->isDebugValue()) { |
| 1643 | mi = nmi; |
| 1644 | continue; |
| 1645 | } |
Evan Cheng | 77be42a | 2010-03-23 20:36:12 +0000 | [diff] [blame] | 1646 | |
Jakob Stoklund Olesen | da2b6b3 | 2012-12-01 01:06:44 +0000 | [diff] [blame] | 1647 | // Expand REG_SEQUENCE instructions. This will position mi at the first |
| 1648 | // expanded instruction. |
Evan Cheng | 4b6abd8 | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1649 | if (mi->isRegSequence()) |
Jakob Stoklund Olesen | da2b6b3 | 2012-12-01 01:06:44 +0000 | [diff] [blame] | 1650 | eliminateRegSequence(mi); |
Evan Cheng | 4b6abd8 | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1651 | |
Evan Cheng | c5618eb | 2008-06-18 07:49:14 +0000 | [diff] [blame] | 1652 | DistanceMap.insert(std::make_pair(mi, ++Dist)); |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 1653 | |
Jakob Stoklund Olesen | 7fa17d4 | 2012-10-26 23:05:10 +0000 | [diff] [blame] | 1654 | processCopy(&*mi); |
Evan Cheng | c2f95b5 | 2009-03-01 02:03:43 +0000 | [diff] [blame] | 1655 | |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1656 | // First scan through all the tied register uses in this instruction |
| 1657 | // and record a list of pairs of tied operands for each register. |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1658 | if (!collectTiedOperands(mi, TiedOperands)) { |
| 1659 | mi = nmi; |
| 1660 | continue; |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1661 | } |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1662 | |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1663 | ++NumTwoAddressInstrs; |
Jakob Stoklund Olesen | a0c72ec | 2012-08-03 23:57:58 +0000 | [diff] [blame] | 1664 | MadeChange = true; |
Jakob Stoklund Olesen | 1162a15 | 2012-08-03 23:25:45 +0000 | [diff] [blame] | 1665 | DEBUG(dbgs() << '\t' << *mi); |
| 1666 | |
Chandler Carruth | 985454e | 2012-07-18 18:58:22 +0000 | [diff] [blame] | 1667 | // If the instruction has a single pair of tied operands, try some |
| 1668 | // transformations that may either eliminate the tied operands or |
| 1669 | // improve the opportunities for coalescing away the register copy. |
| 1670 | if (TiedOperands.size() == 1) { |
Craig Topper | b94011f | 2013-07-14 04:42:23 +0000 | [diff] [blame] | 1671 | SmallVectorImpl<std::pair<unsigned, unsigned> > &TiedPairs |
Chandler Carruth | 985454e | 2012-07-18 18:58:22 +0000 | [diff] [blame] | 1672 | = TiedOperands.begin()->second; |
| 1673 | if (TiedPairs.size() == 1) { |
| 1674 | unsigned SrcIdx = TiedPairs[0].first; |
| 1675 | unsigned DstIdx = TiedPairs[0].second; |
| 1676 | unsigned SrcReg = mi->getOperand(SrcIdx).getReg(); |
| 1677 | unsigned DstReg = mi->getOperand(DstIdx).getReg(); |
| 1678 | if (SrcReg != DstReg && |
Cameron Zwarich | f05c0cb | 2013-02-24 00:27:26 +0000 | [diff] [blame] | 1679 | tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) { |
NAKAMURA Takumi | 8496503 | 2015-09-22 11:14:12 +0000 | [diff] [blame] | 1680 | // The tied operands have been eliminated or shifted further down |
| 1681 | // the block to ease elimination. Continue processing with 'nmi'. |
Chandler Carruth | 985454e | 2012-07-18 18:58:22 +0000 | [diff] [blame] | 1682 | TiedOperands.clear(); |
| 1683 | mi = nmi; |
| 1684 | continue; |
| 1685 | } |
| 1686 | } |
| 1687 | } |
| 1688 | |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1689 | // Now iterate over the information collected above. |
Craig Topper | da5168b | 2015-10-08 06:06:42 +0000 | [diff] [blame] | 1690 | for (auto &TO : TiedOperands) { |
| 1691 | processTiedPairs(mi, TO.second, Dist); |
David Greene | ac9f819 | 2010-01-05 01:24:21 +0000 | [diff] [blame] | 1692 | DEBUG(dbgs() << "\t\trewrite to:\t" << *mi); |
Jakob Stoklund Olesen | 6b556f8 | 2012-06-25 03:27:12 +0000 | [diff] [blame] | 1693 | } |
Bill Wendling | 19e3c85 | 2008-05-10 00:12:52 +0000 | [diff] [blame] | 1694 | |
Jakob Stoklund Olesen | 6b556f8 | 2012-06-25 03:27:12 +0000 | [diff] [blame] | 1695 | // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form. |
| 1696 | if (mi->isInsertSubreg()) { |
| 1697 | // From %reg = INSERT_SUBREG %reg, %subreg, subidx |
| 1698 | // To %reg:subidx = COPY %subreg |
| 1699 | unsigned SubIdx = mi->getOperand(3).getImm(); |
| 1700 | mi->RemoveOperand(3); |
| 1701 | assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx"); |
| 1702 | mi->getOperand(0).setSubReg(SubIdx); |
| 1703 | mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef()); |
| 1704 | mi->RemoveOperand(1); |
| 1705 | mi->setDesc(TII->get(TargetOpcode::COPY)); |
| 1706 | DEBUG(dbgs() << "\t\tconvert to:\t" << *mi); |
Jakob Stoklund Olesen | 70ee3ec | 2010-07-06 23:26:25 +0000 | [diff] [blame] | 1707 | } |
| 1708 | |
Bob Wilson | 5c7d9ca | 2009-09-03 20:58:42 +0000 | [diff] [blame] | 1709 | // Clear TiedOperands here instead of at the top of the loop |
| 1710 | // since most instructions do not have tied operands. |
| 1711 | TiedOperands.clear(); |
Evan Cheng | 5832410 | 2008-03-27 01:27:25 +0000 | [diff] [blame] | 1712 | mi = nmi; |
Misha Brukman | 6dd644e | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 1713 | } |
| 1714 | } |
| 1715 | |
Cameron Zwarich | 3673581 | 2013-02-20 06:46:34 +0000 | [diff] [blame] | 1716 | if (LIS) |
| 1717 | MF->verify(this, "After two-address instruction pass"); |
| 1718 | |
Misha Brukman | 6dd644e | 2004-07-22 15:26:23 +0000 | [diff] [blame] | 1719 | return MadeChange; |
Alkis Evlogimenos | 725021c | 2003-12-18 13:06:04 +0000 | [diff] [blame] | 1720 | } |
Evan Cheng | 4b6abd8 | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1721 | |
Jakob Stoklund Olesen | da2b6b3 | 2012-12-01 01:06:44 +0000 | [diff] [blame] | 1722 | /// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process. |
Evan Cheng | 4b6abd8 | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1723 | /// |
Jakob Stoklund Olesen | da2b6b3 | 2012-12-01 01:06:44 +0000 | [diff] [blame] | 1724 | /// The instruction is turned into a sequence of sub-register copies: |
| 1725 | /// |
| 1726 | /// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1 |
| 1727 | /// |
| 1728 | /// Becomes: |
| 1729 | /// |
| 1730 | /// %dst:ssub0<def,undef> = COPY %v1 |
| 1731 | /// %dst:ssub1<def> = COPY %v2 |
| 1732 | /// |
| 1733 | void TwoAddressInstructionPass:: |
| 1734 | eliminateRegSequence(MachineBasicBlock::iterator &MBBI) { |
| 1735 | MachineInstr *MI = MBBI; |
| 1736 | unsigned DstReg = MI->getOperand(0).getReg(); |
| 1737 | if (MI->getOperand(0).getSubReg() || |
| 1738 | TargetRegisterInfo::isPhysicalRegister(DstReg) || |
| 1739 | !(MI->getNumOperands() & 1)) { |
| 1740 | DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI); |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 1741 | llvm_unreachable(nullptr); |
Evan Cheng | 4b6abd8 | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1742 | } |
| 1743 | |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1744 | SmallVector<unsigned, 4> OrigRegs; |
| 1745 | if (LIS) { |
| 1746 | OrigRegs.push_back(MI->getOperand(0).getReg()); |
| 1747 | for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) |
| 1748 | OrigRegs.push_back(MI->getOperand(i).getReg()); |
| 1749 | } |
| 1750 | |
Jakob Stoklund Olesen | da2b6b3 | 2012-12-01 01:06:44 +0000 | [diff] [blame] | 1751 | bool DefEmitted = false; |
| 1752 | for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) { |
| 1753 | MachineOperand &UseMO = MI->getOperand(i); |
| 1754 | unsigned SrcReg = UseMO.getReg(); |
| 1755 | unsigned SubIdx = MI->getOperand(i+1).getImm(); |
| 1756 | // Nothing needs to be inserted for <undef> operands. |
| 1757 | if (UseMO.isUndef()) |
| 1758 | continue; |
| 1759 | |
| 1760 | // Defer any kill flag to the last operand using SrcReg. Otherwise, we |
| 1761 | // might insert a COPY that uses SrcReg after is was killed. |
| 1762 | bool isKill = UseMO.isKill(); |
| 1763 | if (isKill) |
| 1764 | for (unsigned j = i + 2; j < e; j += 2) |
| 1765 | if (MI->getOperand(j).getReg() == SrcReg) { |
| 1766 | MI->getOperand(j).setIsKill(); |
| 1767 | UseMO.setIsKill(false); |
| 1768 | isKill = false; |
| 1769 | break; |
| 1770 | } |
| 1771 | |
| 1772 | // Insert the sub-register copy. |
| 1773 | MachineInstr *CopyMI = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), |
| 1774 | TII->get(TargetOpcode::COPY)) |
| 1775 | .addReg(DstReg, RegState::Define, SubIdx) |
| 1776 | .addOperand(UseMO); |
| 1777 | |
| 1778 | // The first def needs an <undef> flag because there is no live register |
| 1779 | // before it. |
| 1780 | if (!DefEmitted) { |
| 1781 | CopyMI->getOperand(0).setIsUndef(true); |
| 1782 | // Return an iterator pointing to the first inserted instr. |
| 1783 | MBBI = CopyMI; |
| 1784 | } |
| 1785 | DefEmitted = true; |
| 1786 | |
| 1787 | // Update LiveVariables' kill info. |
| 1788 | if (LV && isKill && !TargetRegisterInfo::isPhysicalRegister(SrcReg)) |
| 1789 | LV->replaceKillInstruction(SrcReg, MI, CopyMI); |
| 1790 | |
| 1791 | DEBUG(dbgs() << "Inserted: " << *CopyMI); |
| 1792 | } |
| 1793 | |
David Blaikie | 9db062e | 2013-02-20 07:39:20 +0000 | [diff] [blame] | 1794 | MachineBasicBlock::iterator EndMBBI = |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 1795 | std::next(MachineBasicBlock::iterator(MI)); |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1796 | |
Jakob Stoklund Olesen | da2b6b3 | 2012-12-01 01:06:44 +0000 | [diff] [blame] | 1797 | if (!DefEmitted) { |
| 1798 | DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF"); |
| 1799 | MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); |
| 1800 | for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) |
| 1801 | MI->RemoveOperand(j); |
| 1802 | } else { |
| 1803 | DEBUG(dbgs() << "Eliminated: " << *MI); |
| 1804 | MI->eraseFromParent(); |
| 1805 | } |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1806 | |
| 1807 | // Udpate LiveIntervals. |
Cameron Zwarich | caad7e1 | 2013-02-20 22:10:00 +0000 | [diff] [blame] | 1808 | if (LIS) |
Cameron Zwarich | 8e60d4d | 2013-02-20 06:46:48 +0000 | [diff] [blame] | 1809 | LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs); |
Evan Cheng | 4b6abd8 | 2010-05-05 18:45:40 +0000 | [diff] [blame] | 1810 | } |