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.
133 /// Remove register from copy maps.
137 // enough. We have to find the COPY defines Reg or registers defined by Reg
139 // the subregisters used in the source of the COPY.
144 assert(CopyOperands && "Expect copy");
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
174 // When we clobber the destination of a copy, we need to clobber the
185 // Since we clobber the destination of a copy, the semantic of Src's
187 // to remove the record from the copy maps that indicates Src defined
189 // opportunities to further eliminate redundant copy instructions.
192 // L1: r0 = COPY r9 <- TrackMI
193 // L2: r0 = COPY r8 <- TrackMI (Remove r9 defined r0 from tracker)
196 // L5: r0 = COPY r8 <- Remove NopCopy
207 // SrcCopy from the tracker's copy maps. We only remove those
220 // Now we can erase the copy.
226 /// Add this copy's registers into the tracker's copy maps.
231 assert(CopyOperands && "Tracking non-copy?");
236 // Remember Def is defined by the copy.
241 // it's no longer available for copy propagation.
244 auto &Copy = I.first->second;
245 if (!is_contained(Copy.DefRegs, Def))
246 Copy.DefRegs.push_back(Def);
247 Copy.LastSeenUseInCopy = MI;
309 // copy if it copies the entire register anyway.
324 // Check that the available copy isn't clobbered by any regmasks between
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
454 // for elimination. If a copy is "read" by a debug user, record the user
457 if (MachineInstr *Copy = Tracker.findCopyForUnit(Unit, *TRI)) {
459 LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());
460 MaybeDeadCopies.remove(Copy);
462 CopyDbgUsers[Copy].insert(&Reader);
473 // If a copy result is livein to a successor, it is not dead.
477 if (MachineInstr *Copy = Tracker.findCopyForUnit(Unit, *TRI))
478 MaybeDeadCopies.remove(Copy);
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,
511 // Avoid eliminating a copy from/to a reserved registers as we cannot predict
516 // Search for an existing copy.
518 Tracker.findAvailCopy(Copy, Def, *TRI, *TII, UseCopyInstr);
523 // Check that the existing copy uses the correct sub registers.
529 LLVM_DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
531 // Copy was redundantly redefining either Src or Def. Remove earlier kill
532 // flags between Copy and PrevCopy because the value will be reused now.
534 isCopyInstr(Copy, *TII, UseCopyInstr);
540 make_range(PrevCopy->getIterator(), Copy.getIterator()))
543 // Clear undef flag from remaining copy if needed.
549 Copy.eraseFromParent();
556 const MachineInstr &Copy, const MachineInstr &UseI, unsigned UseIdx) {
558 isCopyInstr(Copy, *TII, UseCopyInstr);
565 // We don't process further if UseI is a COPY, since forward copy propagation
570 /// Decide whether we should forward the source of \param Copy to its use in
573 bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,
577 isCopyInstr(Copy, *TII, UseCopyInstr);
591 /// is a COPY, we just try to avoid introducing additional cross-class
594 /// RegClassA = COPY RegClassB // Copy parameter
596 /// RegClassB = COPY RegClassA // UseI parameter
600 /// RegClassA = COPY RegClassB
602 /// RegClassB = COPY RegClassB
605 /// introduced a nop COPY that can be removed.
626 // The forwarded copy would be cross-class. Only do this if the original copy
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
678 // Replace the vreg with the source of the active COPY.
700 MachineInstr *Copy = Tracker.findAvailCopy(MI, MOUse.getReg().asMCReg(),
702 if (!Copy)
706 isCopyInstr(*Copy, *TII, UseCopyInstr);
712 // MI might use a sub-register of the Copy destination, in which case the
713 // forwarded register is the matching sub-register of the Copy source.
717 "MI source is not a sub-register of Copy destination");
720 LLVM_DEBUG(dbgs() << "MCP: Copy source does not have sub-register "
730 if (!isForwardableRegClassCopy(*Copy, MI, OpIdx))
736 // Check that the instruction is not a copy that partially overwrites the
737 // original copy source that we are about to use. The tracker mechanism
742 LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI);
754 << "\n in " << MI << " from " << *Copy);
766 make_range(Copy->getIterator(), std::next(MI.getIterator())))
794 // The two copies cancel out and the source of the first copy
796 // %ecx = COPY %eax
798 // %eax = COPY %ecx
800 // %ecx = COPY %eax
804 // %ecx = COPY %eax
806 // %ecx = COPY %eax
808 // %ecx = COPY %eax
818 // If Src is defined by a previous copy, the previous copy cannot be
830 LLVM_DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI.dump());
832 // Copy is now a candidate for deletion.
836 // If 'Def' is previously source of another copy, then this earlier copy's
838 // %xmm9 = copy %xmm2
840 // %xmm2 = copy %xmm0
842 // %xmm2 = copy %xmm9
873 // Not a copy.
914 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
917 // Make sure we invalidate any entries in the copy maps before erasing
930 // Any previous copy definition or reading the Defs is no longer available.
947 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";
1011 MachineInstr *Copy = Tracker.findAvailBackwardCopy(
1013 if (!Copy)
1017 isCopyInstr(*Copy, *TII, UseCopyInstr);
1024 if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx))
1035 << MI << " from " << *Copy);
1041 MaybeDeadCopies.insert(Copy);
1062 // just let forward cp do COPY-to-COPY propagation.
1098 // in a copy instruction, so we can update the debug info if the
1101 if (auto *Copy = Tracker.findCopyDefViaUnit(Unit, *TRI)) {
1102 CopyDbgUsers[Copy].insert(&MI);
1113 for (auto *Copy : MaybeDeadCopies) {
1115 isCopyInstr(*Copy, *TII, UseCopyInstr);
1118 SmallVector<MachineInstr *> MaybeDeadDbgUsers(CopyDbgUsers[Copy].begin(),
1119 CopyDbgUsers[Copy].end());
1122 Copy->eraseFromParent();
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.
1185 // SpillChain maps innermost reload COPY of a spill-reload chain to a sequence
1187 // ReloadChain maps innermost reload COPY of a spill-reload chain to a
1190 // If a COPY's Source has use or def until next COPY defines the Source,
1191 // we put the COPY in this set to keep property#2.
1207 // more infomation about the outermost COPY.
1309 // Update track information via non-copy instruction.
1321 LLVM_DEBUG(dbgs() << "MCP: Copy source of\n");
1328 // Reg, i.e, COPY that defines Reg is removed from the mapping as well
1331 // defined by a previous COPY, since we don't want to make COPYs uses
1348 // Check if we can find a pair spill-reload copy.
1358 // L2: r2 = COPY r3
1359 // L5: r3 = COPY r2
1360 // Looking for a valid COPY before L5 which uses r3.
1363 // No COPY is found, which can be r3 is def-use between (L2, L5), we
1366 // L2: r2 = COPY r3
1367 // L5: r3 = COPY r2
1368 // Such COPY is found and is L2, we create a new chain for L2 and L5.
1370 // L2: r2 = COPY r3
1371 // L3: r1 = COPY r3
1372 // L5: r3 = COPY r2
1375 // L2: r2 = COPY r3
1376 // L3: r1 = COPY r3
1377 // L4: r3 = COPY r1
1378 // L5: r3 = COPY r2
1379 // Such COPY won't be found since L4 defines r3. we create a new chain
1382 // L2: r2 = COPY r3
1383 // L3: r3 = COPY r1
1384 // L4: r1 = COPY r3
1385 // L5: r3 = COPY r2
1386 // COPY is found and is L4 which belongs to an existing chain, we add
1418 // The COPY defines Src is no longer considered as a candidate of a
1419 // valid chain. Since we expect the Def of a spill copy isn't used by
1420 // any COPY instruction until a reload copy. For example:
1421 // L1: r1 = COPY r2
1422 // L2: r3 = COPY r1
1424 // L1: r1 = COPY r2
1425 // L2: r3 = COPY r1
1426 // L3: r2 = COPY r1