MachineCopyPropagation.cpp Source File (original) (raw)

74#include

75#include

77using namespace llvm;

79#define DEBUG_TYPE "machine-cp"

81 STATISTIC(NumDeletes, "Number of dead copies deleted");

82 STATISTIC(NumCopyForwards, "Number of copy uses forwarded");

83 STATISTIC(NumCopyBackwardPropagated, "Number of copy defs backward propagated");

84 STATISTIC(SpillageChainsLength, "Length of spillage chains");

85 STATISTIC(NumSpillageChains, "Number of spillage chains");

87 "Controls which register COPYs are forwarded");

94namespace {

96static std::optional isCopyInstr(const MachineInstr &MI,

98 bool UseCopyInstr) {

99 if (UseCopyInstr)

100 return TII.isCopyInstr(MI);

101

102 if (MI.isCopy())

103 return std::optional(

105

106 return std::nullopt;

107}

108

109class CopyTracker {

110 struct CopyInfo {

115 bool Avail = false;

116 };

117

119

120

121

122

124

125public:

126

131 if (!Inserted) {

132 return It->second;

133 } else {

134 BitVector &PreservedRegUnits = It->second;

135

136 PreservedRegUnits.resize(TRI.getNumRegUnits());

137 for (unsigned SafeReg = 0, E = TRI.getNumRegs(); SafeReg < E; ++SafeReg)

139 for (auto SafeUnit : TRI.regunits(SafeReg))

140 PreservedRegUnits.set(SafeUnit);

141

142 return PreservedRegUnits;

143 }

144 }

145

146

147

151

153 auto CI = Copies.find(Unit);

154 if (CI != Copies.end())

155 CI->second.Avail = false;

156 }

157 }

158 }

159

160

163

164

165

166

169 std::optional CopyOperands =

170 isCopyInstr(*MI, TII, UseCopyInstr);

171 assert(CopyOperands && "Expect copy");

172

173 auto Dest = TRI.regunits(CopyOperands->Destination->getReg().asMCReg());

174 auto Src = TRI.regunits(CopyOperands->Source->getReg().asMCReg());

175 RegUnitsToInvalidate.insert(Dest.begin(), Dest.end());

176 RegUnitsToInvalidate.insert(Src.begin(), Src.end());

177 };

178

180 auto I = Copies.find(Unit);

183 InvalidateCopy(MI);

185 InvalidateCopy(MI);

186 }

187 }

188 for (MCRegUnit Unit : RegUnitsToInvalidate)

190 }

191

192

195 auto I = Copies.find(Unit);

197

198

199 markRegsUnavailable(I->second.DefRegs, TRI);

200

201

203 std::optional CopyOperands =

204 isCopyInstr(*MI, TII, UseCopyInstr);

205

206 MCRegister Def = CopyOperands->Destination->getReg().asMCReg();

207 MCRegister Src = CopyOperands->Source->getReg().asMCReg();

208

209 markRegsUnavailable(Def, TRI);

210

211

212

213

214

215

216

217

218

219

220

221

222

223 for (MCRegUnit SrcUnit : TRI.regunits(Src)) {

224 auto SrcCopy = Copies.find(SrcUnit);

225 if (SrcCopy != Copies.end() && SrcCopy->second.LastSeenUseInCopy) {

226

227

228 for (auto itr = SrcCopy->second.DefRegs.begin();

229 itr != SrcCopy->second.DefRegs.end(); itr++) {

230 if (*itr == Def) {

231 SrcCopy->second.DefRegs.erase(itr);

232

233

234

235

236

237 if (SrcCopy->second.DefRegs.empty() && !SrcCopy->second.MI) {

238 Copies.erase(SrcCopy);

239 }

240 break;

241 }

242 }

243 }

244 }

245 }

246

248 }

249 }

250

251

255 clobberRegUnit(Unit, TRI, TII, UseCopyInstr);

256 }

257 }

258

259

260

261

264 bool UseCopyInstr) {

267 if (!AvailCopy)

268 return false;

269

270 std::optional CopyOperands =

271 isCopyInstr(*AvailCopy, TII, UseCopyInstr);

272 Register Src = CopyOperands->Source->getReg();

273

274

275 if (Src != Reg)

276 return false;

277

278 auto I = Copies.find(RU);

280 return false;

281

282 I->second.SrcUsers.insert(&MI);

283 return true;

284 }

285

286

290 auto I = Copies.find(RU);

292 return {};

293 return I->second.SrcUsers;

294 }

295

296

299 std::optional CopyOperands =

300 isCopyInstr(*MI, TII, UseCopyInstr);

301 assert(CopyOperands && "Tracking non-copy?");

302

303 MCRegister Src = CopyOperands->Source->getReg().asMCReg();

304 MCRegister Def = CopyOperands->Destination->getReg().asMCReg();

305

306

308 Copies[Unit] = {MI, nullptr, {}, {}, true};

309

310

311

315 Copy.DefRegs.push_back(Def);

316 Copy.LastSeenUseInCopy = MI;

317 }

318 }

319

320 bool hasAnyCopies() {

321 return Copies .empty();

322 }

323

326 bool MustBeAvailable = false) {

327 auto CI = Copies.find(RegUnit);

328 if (CI == Copies.end())

329 return nullptr;

330 if (MustBeAvailable && !CI->second.Avail)

331 return nullptr;

332 return CI->second.MI;

333 }

334

337 auto CI = Copies.find(RegUnit);

338 if (CI == Copies.end())

339 return nullptr;

340 if (CI->second.DefRegs.size() != 1)

341 return nullptr;

342 MCRegUnit RU = *TRI.regunits(CI->second.DefRegs[0]).begin();

343 return findCopyForUnit(RU, TRI, true);

344 }

345

349 bool UseCopyInstr) {

352

353 if (!AvailCopy)

354 return nullptr;

355

356 std::optional CopyOperands =

357 isCopyInstr(*AvailCopy, TII, UseCopyInstr);

358 Register AvailSrc = CopyOperands->Source->getReg();

359 Register AvailDef = CopyOperands->Destination->getReg();

360 if ( TRI .isSubRegisterEq(AvailSrc, Reg))

361 return nullptr;

362

366 if (MO.isRegMask())

367

368 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))

369 return nullptr;

370

371 return AvailCopy;

372 }

373

377

378

381 findCopyForUnit(RU, TRI, true);

382

383 if (!AvailCopy)

384 return nullptr;

385

386 std::optional CopyOperands =

387 isCopyInstr(*AvailCopy, TII, UseCopyInstr);

388 Register AvailSrc = CopyOperands->Source->getReg();

389 Register AvailDef = CopyOperands->Destination->getReg();

390 if ( TRI .isSubRegisterEq(AvailDef, Reg))

391 return nullptr;

392

393

394

398 if (MO.isRegMask())

399 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))

400 return nullptr;

401

402 return AvailCopy;

403 }

404

405

410 bool UseCopyInstr) {

412 auto CI = Copies.find(RU);

413 if (CI == Copies.end() || !CI->second.Avail)

414 return nullptr;

415

417 std::optional CopyOperands =

418 isCopyInstr(*DefCopy, TII, UseCopyInstr);

419 Register Def = CopyOperands->Destination->getReg();

420 if ( TRI .isSubRegisterEq(Def, Reg))

421 return nullptr;

422

427 if (MO.isRegMask())

428 if (MO.clobbersPhysReg(Def)) {

431 return nullptr;

432 }

433

434 return DefCopy;

435 }

436

437

441 auto CI = Copies.find(RU);

442 if (CI == Copies.end())

443 return nullptr;

444 return CI->second.LastSeenUseInCopy;

445 }

446

447 void clear() {

449 }

450};

451

456

457

458 bool UseCopyInstr;

459

460public:

461 static char ID;

462

463 MachineCopyPropagation(bool CopyInstr = false)

466 }

467

471 }

472

474

477 MachineFunctionProperties::Property::NoVRegs);

478 }

479

480private:

481 typedef enum { DebugUse = false, RegularUse = true } DebugType;

482

491 bool isForwardableRegClassCopy(const MachineInstr &Copy,

493 bool isBackwardPropagatableRegClassCopy(const MachineInstr &Copy,

495 unsigned UseIdx);

497 bool hasOverlappingMultipleDef(const MachineInstr &MI,

499 bool canUpdateSrcUsers(const MachineInstr &Copy,

501

502

504

505

507

508 CopyTracker Tracker;

509

510 bool Changed = false;

511};

512

513}

514

515char MachineCopyPropagation::ID = 0;

516

518

520 "Machine Copy Propagation Pass", false, false)

521

523 DebugType DT) {

524

525

526

528 if (MachineInstr *Copy = Tracker.findCopyForUnit(Unit, *TRI)) {

529 if (DT == RegularUse) {

530 LLVM_DEBUG(dbgs() << "MCP: Copy is used - not dead: "; Copy->dump());

531 MaybeDeadCopies.remove(Copy);

532 } else {

533 CopyDbgUsers[Copy].insert(&Reader);

534 }

535 }

536 }

537}

538

539void MachineCopyPropagation::readSuccessorLiveIns(

541 if (MaybeDeadCopies.empty())

542 return;

543

544

546 for (const auto &LI : Succ->liveins()) {

547 for (MCRegUnit Unit : TRI->regunits(LI.PhysReg)) {

548 if (MachineInstr *Copy = Tracker.findCopyForUnit(Unit, *TRI))

549 MaybeDeadCopies.remove(Copy);

550 }

551 }

552 }

553}

554

555

556

557

558

559

560

564

565 std::optional CopyOperands =

566 isCopyInstr(PreviousCopy, *TII, UseCopyInstr);

567 MCRegister PreviousSrc = CopyOperands->Source->getReg().asMCReg();

568 MCRegister PreviousDef = CopyOperands->Destination->getReg().asMCReg();

569 if (Src == PreviousSrc && Def == PreviousDef)

570 return true;

571 if ( TRI ->isSubRegister(PreviousSrc, Src))

572 return false;

573 unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);

574 return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);

575}

576

577

578

579

580bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy,

582

583

584 if (MRI->isReserved(Src) || MRI->isReserved(Def))

585 return false;

586

587

589 Tracker.findAvailCopy(Copy, Def, *TRI, *TII, UseCopyInstr);

590 if (!PrevCopy)

591 return false;

592

593 auto PrevCopyOperands = isCopyInstr(*PrevCopy, *TII, UseCopyInstr);

594

595 if (PrevCopyOperands->Destination->isDead())

596 return false;

597 if ( isNopCopy (*PrevCopy, Src, Def, TRI, TII, UseCopyInstr))

598 return false;

599

601

602

603

604 std::optional CopyOperands =

605 isCopyInstr(Copy, *TII, UseCopyInstr);

606 assert(CopyOperands);

607

608 Register CopyDef = CopyOperands->Destination->getReg();

609 assert(CopyDef == Src || CopyDef == Def);

612 MI.clearRegisterKills(CopyDef, TRI);

613

614

615 if (!CopyOperands->Source->isUndef()) {

616 PrevCopy->getOperand(PrevCopyOperands->Source->getOperandNo())

618 }

619

620 Copy.eraseFromParent();

621 Changed = true;

622 ++NumDeletes;

623 return true;

624}

625

626bool MachineCopyPropagation::isBackwardPropagatableRegClassCopy(

628 std::optional CopyOperands =

629 isCopyInstr(Copy, *TII, UseCopyInstr);

630 Register Def = CopyOperands->Destination->getReg();

631

634 return URC->contains(Def);

635

636

637

638 return false;

639}

640

641

642

643

644bool MachineCopyPropagation::isForwardableRegClassCopy(const MachineInstr &Copy,

646 unsigned UseIdx) {

647 std::optional CopyOperands =

648 isCopyInstr(Copy, *TII, UseCopyInstr);

649 Register CopySrcReg = CopyOperands->Source->getReg();

650

651

652

655 return URC->contains(CopySrcReg);

656

657 auto UseICopyOperands = isCopyInstr(UseI, *TII, UseCopyInstr);

658 if (!UseICopyOperands)

659 return false;

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681 Register UseDstReg = UseICopyOperands->Destination->getReg();

682 bool Found = false;

683 bool IsCrossClass = false;

685 if (RC->contains(CopySrcReg) && RC->contains(UseDstReg)) {

686 Found = true;

687 if (TRI->getCrossCopyRegClass(RC) != RC) {

688 IsCrossClass = true;

689 break;

690 }

691 }

692 }

693 if (!Found)

694 return false;

695 if (!IsCrossClass)

696 return true;

697

698

699 Register CopyDstReg = CopyOperands->Destination->getReg();

701 if (RC->contains(CopySrcReg) && RC->contains(CopyDstReg) &&

702 TRI->getCrossCopyRegClass(RC) != RC)

703 return true;

704 }

705 return false;

706}

707

708

709

710

711

712

713

714

715

716bool MachineCopyPropagation::hasImplicitOverlap(const MachineInstr &MI,

719 if (&MIUse != &Use && MIUse.isReg() && MIUse.isImplicit() &&

720 MIUse.isUse() && TRI->regsOverlap(Use.getReg(), MIUse.getReg()))

721 return true;

722

723 return false;

724}

725

726

727

728

729

730bool MachineCopyPropagation::hasOverlappingMultipleDef(

733 if ((&MIDef != &MODef) && MIDef.isReg() &&

734 TRI->regsOverlap(Def, MIDef.getReg()))

735 return true;

736 }

737

738 return false;

739}

740

741

742

743bool MachineCopyPropagation::canUpdateSrcUsers(const MachineInstr &Copy,

745 assert(CopySrc.isReg() && "Expected a register operand");

746 for (auto *SrcUser : Tracker.getSrcUsers(CopySrc.getReg(), *TRI)) {

747 if (hasImplicitOverlap(*SrcUser, CopySrc))

748 return false;

749

751 if (!MO.isReg() || !MO.isUse() || MO.getReg() != CopySrc.getReg())

752 continue;

753 if (MO.isTied() || !MO.isRenamable() ||

754 !isBackwardPropagatableRegClassCopy(Copy, *SrcUser,

755 MO.getOperandNo()))

756 return false;

757 }

758 }

759 return true;

760}

761

762

763

764void MachineCopyPropagation::forwardUses(MachineInstr &MI) {

765 if (!Tracker.hasAnyCopies())

766 return;

767

768

769

770

771 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx < OpEnd;

772 ++OpIdx) {

774

775

776

777

778

781 continue;

782

784 continue;

785

786

787

788

790 continue;

791

793 *TRI, *TII, UseCopyInstr);

794 if (!Copy)

795 continue;

796

797 std::optional CopyOperands =

798 isCopyInstr(*Copy, *TII, UseCopyInstr);

799 Register CopyDstReg = CopyOperands->Destination->getReg();

800 const MachineOperand &CopySrc = *CopyOperands->Source;

802

803 Register ForwardedReg = CopySrcReg;

804

805

806 if (MOUse.getReg() != CopyDstReg) {

807 unsigned SubRegIdx = TRI->getSubRegIndex(CopyDstReg, MOUse.getReg());

809 "MI source is not a sub-register of Copy destination");

810 ForwardedReg = TRI->getSubReg(CopySrcReg, SubRegIdx);

811 if (!ForwardedReg) {

812 LLVM_DEBUG(dbgs() << "MCP: Copy source does not have sub-register "

813 << TRI->getSubRegIndexName(SubRegIdx) << '\n');

814 continue;

815 }

816 }

817

818

819 if (MRI->isReserved(CopySrcReg) && MRI ->isConstantPhysReg(CopySrcReg))

820 continue;

821

822 if (!isForwardableRegClassCopy(*Copy, MI, OpIdx))

823 continue;

824

825 if (hasImplicitOverlap(MI, MOUse))

826 continue;

827

828

829

830

831 if (isCopyInstr(MI, *TII, UseCopyInstr) &&

832 MI.modifiesRegister(CopySrcReg, TRI) &&

833 .definesRegister(CopySrcReg, nullptr)) {

834 LLVM_DEBUG(dbgs() << "MCP: Copy source overlap with dest in " << MI);

835 continue;

836 }

837

839 LLVM_DEBUG(dbgs() << "MCP: Skipping forwarding due to debug counter:\n "

840 << MI);

841 continue;

842 }

843

845 << "\n with " << printReg(ForwardedReg, TRI)

846 << "\n in " << MI << " from " << *Copy);

847

848 MOUse.setReg(ForwardedReg);

849

853

854 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");

855

856

858 make_range(Copy->getIterator(), std::next(MI.getIterator())))

859 KMI.clearRegisterKills(CopySrcReg, TRI);

860

861 ++NumCopyForwards;

862 Changed = true;

863 }

864}

865

866void MachineCopyPropagation::ForwardCopyPropagateBlock(MachineBasicBlock &MBB) {

868 << "\n");

869

871

872 std::optional CopyOperands =

873 isCopyInstr(MI, *TII, UseCopyInstr);

874 if (CopyOperands) {

875

876 Register RegSrc = CopyOperands->Source->getReg();

877 Register RegDef = CopyOperands->Destination->getReg();

878

879 if ( TRI ->regsOverlap(RegDef, RegSrc)) {

881 "MachineCopyPropagation should be run after register allocation!");

882

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901 if (eraseIfRedundant(MI, Def, Src) || eraseIfRedundant(MI, Src, Def))

902 continue;

903

904 forwardUses(MI);

905

906

907 CopyOperands = isCopyInstr(MI, *TII, UseCopyInstr);

908 Src = CopyOperands->Source->getReg().asMCReg();

909

910

911

912 ReadRegister(Src, MI, RegularUse);

914 if (!MO.isReg() || !MO.readsReg())

915 continue;

917 if (!Reg)

918 continue;

919 ReadRegister(Reg, MI, RegularUse);

920 }

921

923

924

925 if ( MRI ->isReserved(Def))

926 MaybeDeadCopies.insert(&MI);

927

928

929

930

931

932

933

934

935 Tracker.clobberRegister(Def, *TRI, *TII, UseCopyInstr);

937 if (!MO.isReg() || !MO.isDef())

938 continue;

940 if (!Reg)

941 continue;

942 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);

943 }

944

945 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr);

946

947 continue;

948 }

949 }

950

951

953 if (MO.isReg() && MO.isEarlyClobber()) {

955

956

957

958 if (MO.isTied())

959 ReadRegister(Reg, MI, RegularUse);

960 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);

961 }

962

963 forwardUses(MI);

964

965

969 if (MO.isRegMask())

970 RegMask = &MO;

971 if (!MO.isReg())

972 continue;

974 if (!Reg)

975 continue;

976

978 "MachineCopyPropagation should be run after register allocation!");

979

980 if (MO.isDef() && !MO.isEarlyClobber()) {

981

982 if ( MRI ->isConstantPhysReg(Reg)) {

984 continue;

985 }

986 } else if (MO.readsReg())

987 ReadRegister(Reg.asMCReg(), MI, MO.isDebug() ? DebugUse : RegularUse);

988 }

989

990

991

992

993 if (RegMask) {

995 Tracker.getPreservedRegUnits(*RegMask, *TRI);

996

997

999 MaybeDeadCopies.begin();

1000 DI != MaybeDeadCopies.end();) {

1002 std::optional CopyOperands =

1003 isCopyInstr(*MaybeDead, *TII, UseCopyInstr);

1004 MCRegister Reg = CopyOperands->Destination->getReg().asMCReg();

1006

1008 ++DI;

1009 continue;

1010 }

1011

1012 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: ";

1013 MaybeDead->dump());

1014

1015

1016

1017 for (unsigned RegUnit : TRI->regunits(Reg))

1018 if (!PreservedRegUnits.test(RegUnit))

1019 Tracker.clobberRegUnit(RegUnit, *TRI, *TII, UseCopyInstr);

1020

1021

1022

1023 DI = MaybeDeadCopies.erase(DI);

1025 Changed = true;

1026 ++NumDeletes;

1027 }

1028 }

1029

1030

1032 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);

1033 }

1034

1035 bool TracksLiveness = MRI->tracksLiveness();

1036

1037

1038

1039 if (TracksLiveness)

1040 readSuccessorLiveIns(MBB);

1041

1042

1043

1044

1046 for (MachineInstr *MaybeDead : MaybeDeadCopies) {

1047 LLVM_DEBUG(dbgs() << "MCP: Removing copy due to no live-out succ: ";

1048 MaybeDead->dump());

1049

1050 std::optional CopyOperands =

1051 isCopyInstr(*MaybeDead, *TII, UseCopyInstr);

1052 assert(CopyOperands);

1053

1054 Register SrcReg = CopyOperands->Source->getReg();

1055 Register DestReg = CopyOperands->Destination->getReg();

1056 assert( MRI ->isReserved(DestReg));

1057

1058

1060 CopyDbgUsers[MaybeDead].begin(), CopyDbgUsers[MaybeDead].end());

1062 MaybeDeadDbgUsers);

1063

1065 Changed = true;

1066 ++NumDeletes;

1067 }

1068 }

1069

1070 MaybeDeadCopies.clear();

1071 CopyDbgUsers.clear();

1072 Tracker.clear();

1073}

1074

1079

1080 if (!Def || !Src)

1081 return false;

1082

1083 if (MRI.isReserved(Def) || MRI.isReserved(Src))

1084 return false;

1085

1087}

1088

1089void MachineCopyPropagation::propagateDefs(MachineInstr &MI) {

1090 if (!Tracker.hasAnyCopies())

1091 return;

1092

1093 for (unsigned OpIdx = 0, OpEnd = MI.getNumOperands(); OpIdx != OpEnd;

1094 ++OpIdx) {

1096

1097 if (!MODef.isReg() || MODef.isUse())

1098 continue;

1099

1100

1102 continue;

1103

1104 if (!MODef.getReg())

1105 continue;

1106

1107

1109 continue;

1110

1113 if (!Copy)

1114 continue;

1115

1116 std::optional CopyOperands =

1117 isCopyInstr(*Copy, *TII, UseCopyInstr);

1118 Register Def = CopyOperands->Destination->getReg();

1119 Register Src = CopyOperands->Source->getReg();

1120

1121 if (MODef.getReg() != Src)

1122 continue;

1123

1124 if (!isBackwardPropagatableRegClassCopy(*Copy, MI, OpIdx))

1125 continue;

1126

1127 if (hasImplicitOverlap(MI, MODef))

1128 continue;

1129

1130 if (hasOverlappingMultipleDef(MI, MODef, Def))

1131 continue;

1132

1133 if (!canUpdateSrcUsers(*Copy, *CopyOperands->Source))

1134 continue;

1135

1137 << "\n with " << printReg(Def, TRI) << "\n in "

1138 << MI << " from " << *Copy);

1139

1141 MODef.setIsRenamable(CopyOperands->Destination->isRenamable());

1142

1143 for (auto *SrcUser : Tracker.getSrcUsers(Src, *TRI)) {

1145 if (!MO.isReg() || !MO.isUse() || MO.getReg() != Src)

1146 continue;

1147 MO.setReg(Def);

1148 MO.setIsRenamable(CopyOperands->Destination->isRenamable());

1149 }

1150 }

1151

1152 LLVM_DEBUG(dbgs() << "MCP: After replacement: " << MI << "\n");

1153 MaybeDeadCopies.insert(Copy);

1154 Changed = true;

1155 ++NumCopyBackwardPropagated;

1156 }

1157}

1158

1159void MachineCopyPropagation::BackwardCopyPropagateBlock(

1162 << "\n");

1163

1165

1166 std::optional CopyOperands =

1167 isCopyInstr(MI, *TII, UseCopyInstr);

1168 if (CopyOperands) {

1169 Register DefReg = CopyOperands->Destination->getReg();

1170 Register SrcReg = CopyOperands->Source->getReg();

1171

1172 if ( TRI ->regsOverlap(DefReg, SrcReg)) {

1173

1174

1176 Tracker.invalidateRegister(SrcReg.asMCReg(), *TRI, *TII,

1177 UseCopyInstr);

1178 Tracker.invalidateRegister(DefReg.asMCReg(), *TRI, *TII,

1179 UseCopyInstr);

1180 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr);

1181 continue;

1182 }

1183 }

1184 }

1185

1186

1188 if (MO.isReg() && MO.isEarlyClobber()) {

1190 if (!Reg)

1191 continue;

1192 Tracker.invalidateRegister(Reg, *TRI, *TII, UseCopyInstr);

1193 }

1194

1195 propagateDefs(MI);

1197 if (!MO.isReg())

1198 continue;

1199

1200 if (!MO.getReg())

1201 continue;

1202

1203 if (MO.isDef())

1204 Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI, *TII,

1205 UseCopyInstr);

1206

1207 if (MO.readsReg()) {

1208 if (MO.isDebug()) {

1209

1210

1211

1212 for (MCRegUnit Unit : TRI->regunits(MO.getReg().asMCReg())) {

1213 if (auto *Copy = Tracker.findCopyDefViaUnit(Unit, *TRI)) {

1214 CopyDbgUsers[Copy].insert(&MI);

1215 }

1216 }

1217 } else if (!Tracker.trackSrcUsers(MO.getReg().asMCReg(), MI, *TRI, *TII,

1218 UseCopyInstr)) {

1219

1220 Tracker.invalidateRegister(MO.getReg().asMCReg(), *TRI, *TII,

1221 UseCopyInstr);

1222 }

1223 }

1224 }

1225 }

1226

1227 for (auto *Copy : MaybeDeadCopies) {

1228 std::optional CopyOperands =

1229 isCopyInstr(*Copy, *TII, UseCopyInstr);

1230 Register Src = CopyOperands->Source->getReg();

1231 Register Def = CopyOperands->Destination->getReg();

1233 CopyDbgUsers[Copy].end());

1234

1235 MRI->updateDbgUsersToReg(Src.asMCReg(), Def.asMCReg(), MaybeDeadDbgUsers);

1236 Copy->eraseFromParent();

1237 ++NumDeletes;

1238 }

1239

1240 MaybeDeadCopies.clear();

1241 CopyDbgUsers.clear();

1242 Tracker.clear();

1243}

1244

1249 auto &SC = SpillChain[Leader];

1250 auto &RC = ReloadChain[Leader];

1251 for (auto I = SC.rbegin(), E = SC.rend(); I != E; ++I)

1252 (*I)->dump();

1255}

1256

1257

1258

1259

1260

1261

1262

1263

1264

1265

1266

1267

1268

1269

1270

1271

1272

1273

1274

1275

1276

1277

1278

1279

1280

1281

1282

1283

1284

1285

1286

1287

1288

1289

1290

1291

1292

1293

1294

1295void MachineCopyPropagation::EliminateSpillageCopies(MachineBasicBlock &MBB) {

1296

1297

1299

1300

1301

1302

1304

1305

1307

1308 auto TryFoldSpillageCopies =

1311 assert(SC.size() == RC.size() && "Spill-reload should be paired");

1312

1313

1314

1315

1316

1317

1318

1319

1320

1321

1322 if (SC.size() <= 2)

1323 return;

1324

1325

1327 if (CopySourceInvalid.count(Spill))

1328 return;

1329

1331 if (CopySourceInvalid.count(Reload))

1332 return;

1333

1336 if (RC->contains(Def) && RC->contains(Src))

1337 return true;

1338 }

1339 return false;

1340 };

1341

1345 if (&MO == Old)

1346 MO.setReg(New->getReg());

1347 }

1348 };

1349

1350 std::optional InnerMostSpillCopy =

1351 isCopyInstr(*SC[0], *TII, UseCopyInstr);

1352 std::optional OuterMostSpillCopy =

1353 isCopyInstr(*SC.back(), *TII, UseCopyInstr);

1354 std::optional InnerMostReloadCopy =

1355 isCopyInstr(*RC[0], *TII, UseCopyInstr);

1356 std::optional OuterMostReloadCopy =

1357 isCopyInstr(*RC.back(), *TII, UseCopyInstr);

1358 if (!CheckCopyConstraint(OuterMostSpillCopy->Source->getReg(),

1359 InnerMostSpillCopy->Source->getReg()) ||

1360 !CheckCopyConstraint(InnerMostReloadCopy->Destination->getReg(),

1361 OuterMostReloadCopy->Destination->getReg()))

1362 return;

1363

1364 SpillageChainsLength += SC.size() + RC.size();

1365 NumSpillageChains += 1;

1366 UpdateReg(SC[0], InnerMostSpillCopy->Destination,

1367 OuterMostSpillCopy->Source);

1368 UpdateReg(RC[0], InnerMostReloadCopy->Source,

1369 OuterMostReloadCopy->Destination);

1370

1371 for (size_t I = 1; I < SC.size() - 1; ++I) {

1372 SC[I]->eraseFromParent();

1373 RC[I]->eraseFromParent();

1374 NumDeletes += 2;

1375 }

1376 };

1377

1378 auto IsFoldableCopy = [this](const MachineInstr &MaybeCopy) {

1379 if (MaybeCopy.getNumImplicitOperands() > 0)

1380 return false;

1381 std::optional CopyOperands =

1382 isCopyInstr(MaybeCopy, *TII, UseCopyInstr);

1383 if (!CopyOperands)

1384 return false;

1385 Register Src = CopyOperands->Source->getReg();

1386 Register Def = CopyOperands->Destination->getReg();

1387 return Src && Def && TRI ->regsOverlap(Src, Def) &&

1388 CopyOperands->Source->isRenamable() &&

1389 CopyOperands->Destination->isRenamable();

1390 };

1391

1394 if (!IsFoldableCopy(Spill) || !IsFoldableCopy(Reload))

1395 return false;

1396 std::optional SpillCopy =

1397 isCopyInstr(Spill, *TII, UseCopyInstr);

1398 std::optional ReloadCopy =

1399 isCopyInstr(Reload, *TII, UseCopyInstr);

1400 if (!SpillCopy || !ReloadCopy)

1401 return false;

1402 return SpillCopy->Source->getReg() == ReloadCopy->Destination->getReg() &&

1403 SpillCopy->Destination->getReg() == ReloadCopy->Source->getReg();

1404 };

1405

1406 auto IsChainedCopy = [&, this](const MachineInstr &Prev,

1408 if (!IsFoldableCopy(Prev) || !IsFoldableCopy(Current))

1409 return false;

1410 std::optional PrevCopy =

1411 isCopyInstr(Prev, *TII, UseCopyInstr);

1412 std::optional CurrentCopy =

1413 isCopyInstr(Current, *TII, UseCopyInstr);

1414 if (!PrevCopy || !CurrentCopy)

1415 return false;

1416 return PrevCopy->Source->getReg() == CurrentCopy->Destination->getReg();

1417 };

1418

1420 std::optional CopyOperands =

1421 isCopyInstr(MI, *TII, UseCopyInstr);

1422

1423

1425 if (!CopyOperands) {

1427 if (!MO.isReg())

1428 continue;

1430 if (!Reg)

1431 continue;

1433 Tracker.findLastSeenUseInCopy(Reg.asMCReg(), *TRI);

1434 if (LastUseCopy) {

1439 CopySourceInvalid.insert(LastUseCopy);

1440 }

1441

1442

1443

1444

1445

1446

1447 if (Tracker.findLastSeenDefInCopy(MI, Reg.asMCReg(), *TRI, *TII,

1448 UseCopyInstr))

1449

1450 RegsToClobber.insert(Reg);

1451 }

1452 for (Register Reg : RegsToClobber) {

1453 Tracker.clobberRegister(Reg, *TRI, *TII, UseCopyInstr);

1455 << "\n");

1456 }

1457 continue;

1458 }

1459

1460 Register Src = CopyOperands->Source->getReg();

1461 Register Def = CopyOperands->Destination->getReg();

1462

1463 LLVM_DEBUG(dbgs() << "MCP: Searching paired spill for reload: ");

1466 Tracker.findLastSeenDefInCopy(MI, Src.asMCReg(), *TRI, *TII, UseCopyInstr);

1467 bool MaybeSpillIsChained = ChainLeader.count(MaybeSpill);

1468 if (!MaybeSpillIsChained && MaybeSpill &&

1469 IsSpillReloadPair(*MaybeSpill, MI)) {

1470

1471

1472

1473

1474

1475

1476

1477

1478

1479

1480

1481

1482

1483

1484

1485

1486

1487

1488

1489

1490

1491

1492

1493

1494

1495

1496

1497

1498

1499

1500

1501

1505 Tracker.findLastSeenUseInCopy(Def.asMCReg(), *TRI);

1506 auto Leader = ChainLeader.find(MaybePrevReload);

1508 if (Leader == ChainLeader.end() ||

1509 (MaybePrevReload && !IsChainedCopy(*MaybePrevReload, MI))) {

1510 L = &MI;

1512 "SpillChain should not have contained newly found chain");

1513 } else {

1514 assert(MaybePrevReload &&

1515 "Found a valid leader through nullptr should not happend");

1516 L = Leader->second;

1518 "Existing chain's length should be larger than zero");

1519 }

1521 "Newly found paired spill-reload should not belong to any chain "

1522 "at this point");

1523 ChainLeader.insert({MaybeSpill, L});

1525 SpillChain[L].push_back(MaybeSpill);

1526 ReloadChain[L].push_back(&MI);

1527 LLVM_DEBUG(dbgs() << "MCP: Chain " << L << " now is:\n");

1529 } else if (MaybeSpill && !MaybeSpillIsChained) {

1530

1531

1532

1533

1534

1535

1536

1537

1538

1539

1540

1541

1542

1543 LLVM_DEBUG(dbgs() << "MCP: Not paired spill-reload:\n");

1546 Tracker.clobberRegister(Src.asMCReg(), *TRI, *TII, UseCopyInstr);

1548 << "\n");

1549 }

1550 Tracker.trackCopy(&MI, *TRI, *TII, UseCopyInstr);

1551 }

1552

1553 for (auto I = SpillChain.begin(), E = SpillChain.end(); I != E; ++I) {

1554 auto &SC = I->second;

1556 "Reload chain of the same leader should exist");

1557 auto &RC = ReloadChain[I->first];

1558 TryFoldSpillageCopies(SC, RC);

1559 }

1560

1561 MaybeDeadCopies.clear();

1562 CopyDbgUsers.clear();

1563 Tracker.clear();

1564}

1565

1566bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {

1568 return false;

1569

1570 bool isSpillageCopyElimEnabled = false;

1573 isSpillageCopyElimEnabled =

1575 break;

1577 isSpillageCopyElimEnabled = true;

1578 break;

1580 isSpillageCopyElimEnabled = false;

1581 break;

1582 }

1583

1584 Changed = false;

1585

1589

1591 if (isSpillageCopyElimEnabled)

1592 EliminateSpillageCopies(MBB);

1593 BackwardCopyPropagateBlock(MBB);

1594 ForwardCopyPropagateBlock(MBB);

1595 }

1596

1597 return Changed;

1598}

1599

1602 return new MachineCopyPropagation(UseCopyInstr);

1603}

unsigned const MachineRegisterInfo * MRI

#define LLVM_ATTRIBUTE_UNUSED

This file provides an implementation of debug counters.

#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)

This file defines the DenseMap class.

const HexagonInstrInfo * TII

static cl::opt< cl::boolOrDefault > EnableSpillageCopyElimination("enable-spill-copy-elim", cl::Hidden)

static void LLVM_ATTRIBUTE_UNUSED printSpillReloadChain(DenseMap< MachineInstr *, SmallVector< MachineInstr * > > &SpillChain, DenseMap< MachineInstr *, SmallVector< MachineInstr * > > &ReloadChain, MachineInstr *Leader)

static bool isBackwardPropagatableCopy(const DestSourcePair &CopyOperands, const MachineRegisterInfo &MRI)

static bool isNopCopy(const MachineInstr &PreviousCopy, MCRegister Src, MCRegister Def, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, bool UseCopyInstr)

Return true if PreviousCopy did copy register Src to register Def.

static cl::opt< bool > MCPUseCopyInstr("mcp-use-is-copy-instr", cl::init(false), cl::Hidden)

unsigned const TargetRegisterInfo * TRI

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file implements a set that has insertion order iteration characteristics.

This file defines the SmallSet class.

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

Represent the analysis usage information of a pass.

void setPreservesCFG()

This function should be called by the pass, iff they do not:

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

bool test(unsigned Idx) const

void resize(unsigned N, bool t=false)

resize - Grow or shrink the bitvector.

static bool shouldExecute(unsigned CounterName)

iterator find(const_arg_type_t< KeyT > Val)

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Implements a dense probed hash-table based set.

Wrapper class representing physical registers. Should be passed by value.

iterator_range< succ_iterator > successors()

StringRef getName() const

Return the name of the corresponding LLVM basic block, or an empty string.

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

virtual bool runOnMachineFunction(MachineFunction &MF)=0

runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...

virtual MachineFunctionProperties getRequiredProperties() const

Properties which a MachineFunction may have at a given point in time.

MachineFunctionProperties & set(Property P)

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Function & getFunction()

Return the LLVM function that this machine code represents.

Representation of each machine instruction.

void eraseFromParent()

Unlink 'this' from the containing basic block and delete it.

const MachineOperand & getOperand(unsigned i) const

const TargetRegisterClass * getRegClassConstraint(unsigned OpIdx, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) const

Compute the static register class constraint for operand OpIdx.

MachineOperand class - Representation of each machine instruction operand.

void setIsRenamable(bool Val=true)

bool isReg() const

isReg - Tests if this is a MO_Register operand.

void setReg(Register Reg)

Change the register this operand corresponds to.

bool isRenamable() const

isRenamable - Returns true if this register may be renamed, i.e.

void setIsUndef(bool Val=true)

getReg - Returns the register number.

static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)

clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.

const uint32_t * getRegMask() const

getRegMask - Returns a bit mask of registers preserved by this RegMask operand.

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

Wrapper class representing virtual and physical registers.

MCRegister asMCReg() const

Utility to check-convert this value to a MCRegister.

constexpr bool isPhysical() const

Return true if the specified register number is in the physical register namespace.

iterator begin()

Get an iterator to the beginning of the SetVector.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

A SetVector that performs no allocations if smaller than a certain size.

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

TargetInstrInfo - Interface to description of machine instruction set.

TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...

virtual const TargetRegisterInfo * getRegisterInfo() const

getRegisterInfo - If register information is available, return it.

virtual bool enableSpillageCopyElimination() const

Enable spillage copy elimination in MachineCopyPropagation pass.

virtual const TargetInstrInfo * getInstrInfo() const

A Use represents the edge between a Value definition and its users.

std::pair< iterator, bool > insert(const ValueT &V)

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

reverse_self_iterator getReverseIterator()

self_iterator getIterator()

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ SC

CHAIN = SC CHAIN, Imm128 - System call.

Reg

All possible values of the reg field in the ModR/M byte.

initializer< Ty > init(const Ty &Val)

NodeAddr< DefNode * > Def

const_iterator begin(StringRef path LLVM_LIFETIME_BOUND, Style style=Style::native)

Get begin iterator over path.

const_iterator end(StringRef path LLVM_LIFETIME_BOUND)

Get end iterator over path.

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

auto reverse(ContainerTy &&C)

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

auto drop_end(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the last N elements excluded.

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

MachineFunctionPass * createMachineCopyPropagationPass(bool UseCopyInstr)

void initializeMachineCopyPropagationPass(PassRegistry &)

Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)

Prints virtual and physical registers with or without a TRI instance.

char & MachineCopyPropagationID

MachineCopyPropagation - This pass performs copy propagation on machine instructions.

const MachineOperand * Source

const MachineOperand * Destination