Lines Matching full:copy
1 //===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===//
9 // This is an extremely simple MachineInstr-level copy propagation pass.
14 // %reg1 = COPY %reg0
21 // - the COPY def is the only value that reaches OP
24 // %reg1 = COPY %reg0
30 // %R1 = COPY %R0
32 // %R0 = COPY %R1 <<< Removed
36 // %R1 = COPY %R0
38 // %R1 = COPY %R0 <<< Removed
44 // $R1 = COPY $R0 // $R0 is killed
45 // Replace $R0 with $R1 and remove the COPY
82 STATISTIC(NumCopyForwards, "Number of copy uses forwarded");
83 STATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated");
89 static cl::opt<bool> MCPUseCopyInstr("mcp-use-is-copy-instr", cl::init(false),
92 EnableSpillageCopyElimination("enable-spill-copy-elim", cl::Hidden);
124 // Source of copy is no longer available for propagation. in markRegsUnavailable()
133 /// Remove register from copy maps.
137 // enough. We have to find the COPY defines Reg or registers defined by Reg in invalidateRegister()
139 // the subregisters used in the source of the COPY. in invalidateRegister()
144 assert(CopyOperands && "Expect copy"); in invalidateRegister()
165 /// Clobber a single register, removing it from the tracker's copy maps.
171 // When we clobber the source of a copy, we need to clobber everything in clobberRegister()
174 // When we clobber the destination of a copy, we need to clobber the in clobberRegister()
185 // Since we clobber the destination of a copy, the semantic of Src's in clobberRegister()
187 // to remove the record from the copy maps that indicates Src defined in clobberRegister()
189 // opportunities to further eliminate redundant copy instructions. in clobberRegister()
192 // L1: r0 = COPY r9 <- TrackMI in clobberRegister()
193 // L2: r0 = COPY r8 <- TrackMI (Remove r9 defined r0 from tracker) in clobberRegister()
196 // L5: r0 = COPY r8 <- Remove NopCopy in clobberRegister()
207 // SrcCopy from the tracker's copy maps. We only remove those in clobberRegister()
220 // Now we can erase the copy. in clobberRegister()
226 /// Add this copy's registers into the tracker's copy maps.
231 assert(CopyOperands && "Tracking non-copy?"); in trackCopy()
236 // Remember Def is defined by the copy. in trackCopy()
241 // it's no longer available for copy propagation. in trackCopy()
244 auto &Copy = I.first->second; in trackCopy() local
245 if (!is_contained(Copy.DefRegs, Def)) in trackCopy()
246 Copy.DefRegs.push_back(Def); in trackCopy()
247 Copy.LastSeenUseInCopy = MI; in trackCopy()
309 // copy if it copies the entire register anyway. in findAvailCopy()
324 // Check that the available copy isn't clobbered by any regmasks between in findAvailCopy()
336 // Find last COPY that defines Reg before Current MachineInstr.
368 // Find last COPY that uses Reg.
388 // Return true if this is a copy instruction and false otherwise.
419 bool eraseIfRedundant(MachineInstr &Copy, MCRegister Src, MCRegister Def);
422 bool isForwardableRegClassCopy(const MachineInstr &Copy,
424 bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy,
449 "Machine Copy Propagation Pass", false, false)
453 // If 'Reg' is defined by a copy, the copy is no longer a candidate in ReadRegister()
454 // for elimination. If a copy is "read" by a debug user, record the user in ReadRegister()
457 if (MachineInstr *Copy = Tracker.findCopyForUnit(Unit, *TRI)) { in ReadRegister() local
459 LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump()); in ReadRegister()
460 MaybeDeadCopies.remove(Copy); in ReadRegister()
462 CopyDbgUsers[Copy].insert(&Reader); in ReadRegister()
473 // If a copy result is livein to a successor, it is not dead. in readSuccessorLiveIns()
477 if (MachineInstr *Copy = Tracker.findCopyForUnit(Unit, *TRI)) in readSuccessorLiveIns() local
478 MaybeDeadCopies.remove(Copy); in readSuccessorLiveIns()
484 /// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
488 /// isNopCopy("ecx = COPY eax", AX, CX) == true
489 /// isNopCopy("ecx = COPY eax", AH, CL) == false
506 /// Remove instruction \p Copy if there exists a previous copy that copies the
509 bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, in eraseIfRedundant() argument
511 // Avoid eliminating a copy from/to a reserved registers as we cannot predict in eraseIfRedundant()
516 // Search for an existing copy. in eraseIfRedundant()
518 Tracker.findAvailCopy(Copy, Def, *TRI, *TII, UseCopyInstr); in eraseIfRedundant()
523 // Check that the existing copy uses the correct sub registers. in eraseIfRedundant()
529 LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump()); in eraseIfRedundant()
531 // Copy was redundantly redefining either Src or Def. Remove earlier kill in eraseIfRedundant()
532 // flags between Copy and PrevCopy because the value will be reused now. in eraseIfRedundant()
534 isCopyInstr(Copy, *TII, UseCopyInstr); in eraseIfRedundant()
540 make_range(PrevCopy->getIterator(), Copy.getIterator())) in eraseIfRedundant()
543 // Clear undef flag from remaining copy if needed. in eraseIfRedundant()
549 Copy.eraseFromParent(); in eraseIfRedundant()
556 const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) { in isBackwardPropagatableRegClassCopy() argument
558 isCopyInstr(Copy, *TII, UseCopyInstr); in isBackwardPropagatableRegClassCopy()
565 // We don't process further if UseI is a COPY, since forward copy propagation in isBackwardPropagatableRegClassCopy()
570 /// Decide whether we should forward the source of \param Copy to its use in
573 bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy, in isForwardableRegClassCopy() argument
577 isCopyInstr(Copy, *TII, UseCopyInstr); in isForwardableRegClassCopy()
591 /// is a COPY, we just try to avoid introducing additional cross-class in isForwardableRegClassCopy()
594 /// RegClassA = COPY RegClassB // Copy parameter in isForwardableRegClassCopy()
596 /// RegClassB = COPY RegClassA // UseI parameter in isForwardableRegClassCopy()
600 /// RegClassA = COPY RegClassB in isForwardableRegClassCopy()
602 /// RegClassB = COPY RegClassB in isForwardableRegClassCopy()
605 /// introduced a nop COPY that can be removed. in isForwardableRegClassCopy()
626 // The forwarded copy would be cross-class. Only do this if the original copy in isForwardableRegClassCopy()
671 /// replace the use in \p MI with the copy's source register.
676 // Look for non-tied explicit vreg uses that have an active COPY in forwardUses()
678 // Replace the vreg with the source of the active COPY. in forwardUses()
700 MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg().asMCReg(), in forwardUses() local
702 if (!Copy) in forwardUses()
706 isCopyInstr(*Copy, *TII, UseCopyInstr); in forwardUses()
712 // MI might use a sub-register of the Copy destination, in which case the in forwardUses()
713 // forwarded register is the matching sub-register of the Copy source. in forwardUses()
717 "MI source is not a sub-register of Copy destination"); in forwardUses()
720 LLVM_DEBUG(dbgs() << "MCP: Copy source does not have sub-register " in forwardUses()
730 if (!isForwardableRegClassCopy(*Copy, MI, OpIdx)) in forwardUses()
736 // Check that the instruction is not a copy that partially overwrites the in forwardUses()
737 // original copy source that we are about to use. The tracker mechanism in forwardUses()
742 LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI); in forwardUses()
754 << "\n in " << MI << " from " << *Copy); in forwardUses()
766 make_range(Copy->getIterator(), std::next(MI.getIterator()))) in forwardUses()
794 // The two copies cancel out and the source of the first copy in ForwardCopyPropagateBlock()
796 // %ecx = COPY %eax in ForwardCopyPropagateBlock()
798 // %eax = COPY %ecx in ForwardCopyPropagateBlock()
800 // %ecx = COPY %eax in ForwardCopyPropagateBlock()
804 // %ecx = COPY %eax in ForwardCopyPropagateBlock()
806 // %ecx = COPY %eax in ForwardCopyPropagateBlock()
808 // %ecx = COPY %eax in ForwardCopyPropagateBlock()
818 // If Src is defined by a previous copy, the previous copy cannot be in ForwardCopyPropagateBlock()
830 LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI.dump()); in ForwardCopyPropagateBlock()
832 // Copy is now a candidate for deletion. in ForwardCopyPropagateBlock()
836 // If 'Def' is previously source of another copy, then this earlier copy's in ForwardCopyPropagateBlock()
838 // %xmm9 = copy %xmm2 in ForwardCopyPropagateBlock()
840 // %xmm2 = copy %xmm0 in ForwardCopyPropagateBlock()
842 // %xmm2 = copy %xmm9 in ForwardCopyPropagateBlock()
873 // Not a copy. in ForwardCopyPropagateBlock()
914 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: "; in ForwardCopyPropagateBlock()
917 // Make sure we invalidate any entries in the copy maps before erasing in ForwardCopyPropagateBlock()
930 // Any previous copy definition or reading the Defs is no longer available. in ForwardCopyPropagateBlock()
947 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: "; in ForwardCopyPropagateBlock()
1011 MachineInstr *Copy = Tracker.findAvailBackwardCopy( in propagateDefs() local
1013 if (!Copy) in propagateDefs()
1017 isCopyInstr(*Copy, *TII, UseCopyInstr); in propagateDefs()
1024 if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx)) in propagateDefs()
1035 << MI << " from " << *Copy); in propagateDefs()
1041 MaybeDeadCopies.insert(Copy); in propagateDefs()
1062 // just let forward cp do COPY-to-COPY propagation. in BackwardCopyPropagateBlock()
1098 // in a copy instruction, so we can update the debug info if the in BackwardCopyPropagateBlock()
1101 if (auto *Copy = Tracker.findCopyDefViaUnit(Unit, *TRI)) { in BackwardCopyPropagateBlock() local
1102 CopyDbgUsers[Copy].insert(&MI); in BackwardCopyPropagateBlock()
1113 for (auto *Copy : MaybeDeadCopies) { in BackwardCopyPropagateBlock() local
1115 isCopyInstr(*Copy, *TII, UseCopyInstr); in BackwardCopyPropagateBlock()
1118 SmallVector<MachineInstr *> MaybeDeadDbgUsers(CopyDbgUsers[Copy].begin(), in BackwardCopyPropagateBlock()
1119 CopyDbgUsers[Copy].end()); in BackwardCopyPropagateBlock()
1122 Copy->eraseFromParent(); in BackwardCopyPropagateBlock()
1143 // Remove spill-reload like copy chains. For example
1144 // r0 = COPY r1
1145 // r1 = COPY r2
1146 // r2 = COPY r3
1147 // r3 = COPY r4
1149 // r4 = COPY r3
1150 // r3 = COPY r2
1151 // r2 = COPY r1
1152 // r1 = COPY r0
1154 // r0 = COPY r1
1155 // r1 = COPY r4
1157 // r4 = COPY r1
1158 // r1 = COPY r0
1163 // property#1: No Def of spill COPY in the chain is used or defined until the
1164 // paired reload COPY in the chain uses the Def.
1166 // property#2: NO Source of COPY in the chain is used or defined until the next
1167 // COPY in the chain defines the Source, except the innermost spill-reload
1170 // The algorithm is conducted by checking every COPY inside the MBB, assuming
1171 // the COPY is a reload COPY, then try to find paired spill COPY by searching
1172 // the COPY defines the Src of the reload COPY backward. If such pair is found,
1174 // last available COPY uses the Def of the reload COPY.
1176 // out last COPY that defines Reg; we use CopyTracker::findLastUseCopy(Reg, ...)
1177 // to find out last COPY that uses Reg. When we are encountered with a Non-COPY
1179 // Reg is defined by a COPY, we untrack this Reg via
1182 // ChainLeader maps MI inside a spill-reload chain to its innermost reload COPY. in EliminateSpillageCopies()
1185 // SpillChain maps innermost reload COPY of a spill-reload chain to a sequence in EliminateSpillageCopies()
1187 // ReloadChain maps innermost reload COPY of a spill-reload chain to a in EliminateSpillageCopies()
1190 // If a COPY's Source has use or def until next COPY defines the Source, in EliminateSpillageCopies()
1191 // we put the COPY in this set to keep property#2. in EliminateSpillageCopies()
1207 // more infomation about the outermost COPY. in EliminateSpillageCopies()
1309 // Update track information via non-copy instruction. in EliminateSpillageCopies()
1321 LLVM_DEBUG(dbgs() << "MCP: Copy source of\n"); in EliminateSpillageCopies()
1328 // Reg, i.e, COPY that defines Reg is removed from the mapping as well in EliminateSpillageCopies()
1331 // defined by a previous COPY, since we don't want to make COPYs uses in EliminateSpillageCopies()
1348 // Check if we can find a pair spill-reload copy. in EliminateSpillageCopies()
1358 // L2: r2 = COPY r3 in EliminateSpillageCopies()
1359 // L5: r3 = COPY r2 in EliminateSpillageCopies()
1360 // Looking for a valid COPY before L5 which uses r3. in EliminateSpillageCopies()
1363 // No COPY is found, which can be r3 is def-use between (L2, L5), we in EliminateSpillageCopies()
1366 // L2: r2 = COPY r3 in EliminateSpillageCopies()
1367 // L5: r3 = COPY r2 in EliminateSpillageCopies()
1368 // Such COPY is found and is L2, we create a new chain for L2 and L5. in EliminateSpillageCopies()
1370 // L2: r2 = COPY r3 in EliminateSpillageCopies()
1371 // L3: r1 = COPY r3 in EliminateSpillageCopies()
1372 // L5: r3 = COPY r2 in EliminateSpillageCopies()
1375 // L2: r2 = COPY r3 in EliminateSpillageCopies()
1376 // L3: r1 = COPY r3 in EliminateSpillageCopies()
1377 // L4: r3 = COPY r1 in EliminateSpillageCopies()
1378 // L5: r3 = COPY r2 in EliminateSpillageCopies()
1379 // Such COPY won't be found since L4 defines r3. we create a new chain in EliminateSpillageCopies()
1382 // L2: r2 = COPY r3 in EliminateSpillageCopies()
1383 // L3: r3 = COPY r1 in EliminateSpillageCopies()
1384 // L4: r1 = COPY r3 in EliminateSpillageCopies()
1385 // L5: r3 = COPY r2 in EliminateSpillageCopies()
1386 // COPY is found and is L4 which belongs to an existing chain, we add in EliminateSpillageCopies()
1418 // The COPY defines Src is no longer considered as a candidate of a in EliminateSpillageCopies()
1419 // valid chain. Since we expect the Def of a spill copy isn't used by in EliminateSpillageCopies()
1420 // any COPY instruction until a reload copy. For example: in EliminateSpillageCopies()
1421 // L1: r1 = COPY r2 in EliminateSpillageCopies()
1422 // L2: r3 = COPY r1 in EliminateSpillageCopies()
1424 // L1: r1 = COPY r2 in EliminateSpillageCopies()
1425 // L2: r3 = COPY r1 in EliminateSpillageCopies()
1426 // L3: r2 = COPY r1 in EliminateSpillageCopies()