LLVM: lib/CodeGen/RDFGraph.cpp Source File (original) (raw)

1

2

3

4

5

6

7

8

9

10

32#include

33#include

34#include

35#include

36#include

37#include

38#include

39

40

41

43

45 P.G.getPRI().print(OS, P.Obj);

46 return OS;

47}

48

50 if (P.Obj == 0)

51 return OS << "null";

52 auto NA = P.G.addr<NodeBase *>(P.Obj);

53 uint16_t Attrs = NA.Addr->getAttrs();

58 switch (Kind) {

60 OS << 'f';

61 break;

63 OS << 'b';

64 break;

66 OS << 's';

67 break;

69 OS << 'p';

70 break;

71 default:

72 OS << "c?";

73 break;

74 }

75 break;

78 OS << '/';

80 OS << '\\';

82 OS << '+';

84 OS << '~';

85 switch (Kind) {

87 OS << 'u';

88 break;

90 OS << 'd';

91 break;

93 OS << 'b';

94 break;

95 default:

96 OS << "r?";

97 break;

98 }

99 break;

100 default:

101 OS << '?';

102 break;

103 }

104 OS << P.Obj;

106 OS << '"';

107 return OS;

108}

109

112 OS << Print(RA.Id, G) << '<' << Print(RA.Addr->getRegRef(G), G) << '>';

114 OS << '!';

115}

116

119 OS << '(';

120 if (NodeId N = P.Obj.Addr->getReachingDef())

122 OS << ',';

123 if (NodeId N = P.Obj.Addr->getReachedDef())

125 OS << ',';

126 if (NodeId N = P.Obj.Addr->getReachedUse())

128 OS << "):";

129 if (NodeId N = P.Obj.Addr->getSibling())

131 return OS;

132}

133

136 OS << '(';

137 if (NodeId N = P.Obj.Addr->getReachingDef())

139 OS << "):";

140 if (NodeId N = P.Obj.Addr->getSibling())

142 return OS;

143}

144

147 OS << '(';

148 if (NodeId N = P.Obj.Addr->getReachingDef())

150 OS << ',';

151 if (NodeId N = P.Obj.Addr->getPredecessor())

153 OS << "):";

154 if (NodeId N = P.Obj.Addr->getSibling())

156 return OS;

157}

158

160 switch (P.Obj.Addr->getKind()) {

162 OS << PrintNode<DefNode *>(P.Obj, P.G);

163 break;

166 OS << PrintNode<PhiUseNode *>(P.Obj, P.G);

167 else

168 OS << PrintNode<UseNode *>(P.Obj, P.G);

169 break;

170 }

171 return OS;

172}

173

175 unsigned N = P.Obj.size();

176 for (auto I : P.Obj) {

178 if (--N)

179 OS << ' ';

180 }

181 return OS;

182}

183

185 unsigned N = P.Obj.size();

186 for (auto I : P.Obj) {

188 if (--N)

189 OS << ' ';

190 }

191 return OS;

192}

193

194namespace {

195

196template struct PrintListV {

197 PrintListV(const NodeList &L, const DataFlowGraph &G) : List(L), G(G) {}

198

199 using Type = T;

201 const DataFlowGraph &G;

202};

203

204template

205raw_ostream &operator<<(raw_ostream &OS, const PrintListV &P) {

206 unsigned N = P.List.size();

208 OS << PrintNode(A, P.G);

209 if (--N)

210 OS << ", ";

211 }

212 return OS;

213}

214

215}

216

218 OS << Print(P.Obj.Id, P.G) << ": phi ["

219 << PrintListV<RefNode *>(P.Obj.Addr->members(P.G), P.G) << ']';

220 return OS;

221}

222

225 unsigned Opc = MI.getOpcode();

226 OS << Print(P.Obj.Id, P.G) << ": " << P.G.getTII().getName(Opc);

227

228 if (MI.isCall() || MI.isBranch()) {

231 return Op.isMBB() || Op.isGlobal() || Op.isSymbol();

232 });

233 if (T != MI.operands_end()) {

234 OS << ' ';

235 if (T->isMBB())

237 else if (T->isGlobal())

238 OS << T->getGlobal()->getName();

239 else if (T->isSymbol())

240 OS << T->getSymbolName();

241 }

242 }

243 OS << " [" << PrintListV<RefNode *>(P.Obj.Addr->members(P.G), P.G) << ']';

244 return OS;

245}

246

248 switch (P.Obj.Addr->getKind()) {

250 OS << PrintNode<PhiNode *>(P.Obj, P.G);

251 break;

253 OS << PrintNode<StmtNode *>(P.Obj, P.G);

254 break;

255 default:

256 OS << "instr? " << Print(P.Obj.Id, P.G);

257 break;

258 }

259 return OS;

260}

261

265 std::vector Ns;

266 auto PrintBBs = [&OS](const std::vector &Ns) -> void {

267 unsigned N = Ns.size();

268 for (int I : Ns) {

269 OS << "%bb." << I;

270 if (--N)

271 OS << ", ";

272 }

273 };

274

276 << " --- preds(" << NP << "): ";

278 Ns.push_back(B->getNumber());

279 PrintBBs(Ns);

280

282 OS << " succs(" << NS << "): ";

283 Ns.clear();

285 Ns.push_back(B->getNumber());

286 PrintBBs(Ns);

287 OS << '\n';

288

289 for (auto I : P.Obj.Addr->members(P.G))

290 OS << PrintNode<InstrNode *>(I, P.G) << '\n';

291 return OS;

292}

293

295 OS << "DFG dump:[\n"

297 << ": Function: " << P.Obj.Addr->getCode()->getName() << '\n';

298 for (auto I : P.Obj.Addr->members(P.G))

299 OS << PrintNode<BlockNode *>(I, P.G) << '\n';

300 OS << "]\n";

301 return OS;

302}

303

305 OS << '{';

306 for (auto I : P.Obj)

307 OS << ' ' << Print(I, P.G);

308 OS << " }";

309 return OS;

310}

311

313 OS << P.Obj;

314 return OS;

315}

316

319 for (auto I = P.Obj.top(), E = P.Obj.bottom(); I != E;) {

320 OS << Print(I->Id, P.G) << '<' << Print(I->Addr->getRegRef(P.G), P.G)

321 << '>';

322 I.down();

323 if (I != E)

324 OS << ' ';

325 }

326 return OS;

327}

328

329

330

331

332

333

334

335

336

337

338void NodeAllocator::startNewBlock() {

340 char *P = static_cast<char *>(T);

341 Blocks.push_back(P);

342

343

344

345 assert((Blocks.size() < ((size_t)1 << (8 * sizeof(NodeId) - BitsPerIndex))) &&

346 "Out of bits for block index");

347 ActiveEnd = P;

348}

349

350bool NodeAllocator::needNewBlock() {

351 if (Blocks.empty())

352 return true;

353

354 char *ActiveBegin = Blocks.back();

356 return Index >= NodesPerBlock;

357}

358

360 if (needNewBlock())

361 startNewBlock();

362

363 uint32_t ActiveB = Blocks.size() - 1;

365 Node NA = {reinterpret_cast<NodeBase *>(ActiveEnd), makeId(ActiveB, Index)};

367 return NA;

368}

369

371 uintptr_t A = reinterpret_cast<uintptr_t>(P);

372 for (unsigned i = 0, n = Blocks.size(); i != n; ++i) {

373 uintptr_t B = reinterpret_cast<uintptr_t>(Blocks[i]);

375 continue;

377 return makeId(i, Idx);

378 }

380}

381

383 MemPool.Reset();

384 Blocks.clear();

385 ActiveEnd = nullptr;

386}

387

388

397

398

399

400

406 return G.makeRegRef(*RefData.Op);

407}

408

409

410

416

417

418

425

426

429

430 while (NA.Addr != this) {

432 return NA;

434 }

436}

437

438

441 RefData.Sib = DA.Addr->getReachedDef();

442 DA.Addr->setReachedDef(Self);

443}

444

445

448 RefData.Sib = DA.Addr->getReachedUse();

449 DA.Addr->setReachedUse(Self);

450}

451

452

458

459

465

466

469 if (ML.Id != 0) {

470 ML.Addr->append(NA);

471 } else {

473 NodeId Self = G.id(this);

475 }

477}

478

479

485

486

490

491

492 if (MA.Id == NA.Id) {

494

496 } else {

497

499 }

500 return;

501 }

502

503 while (MA.Addr != this) {

505 if (MX == NA.Id) {

507

508

511 return;

512 }

514 }

516}

517

518

520 static auto True = [](Node) -> bool { return true; };

522}

523

524

527

528 while (NA.Addr != this) {

531 return NA;

533 }

535}

536

537

540 if (M.Id == 0) {

542 return;

543 }

544

547

548

551 } else {

552

555 do {

556 M = MN;

557 MN = G.addr<NodeBase *>(M.Addr->getNext());

560

561

563 }

564}

565

566

567

570 auto EqBB = [BB](Node NA) -> bool { return Block(NA).Addr->getCode() == BB; };

573 return Ms[0];

575}

576

577

582

583

584

585

586

587

589 unsigned OpNum) const {

590 return TII.isPredicated(In);

591}

592

593

595 unsigned OpNum) const {

597 if (Op.isRegMask())

598 return true;

600 if (In.isCall())

601 if (Op.isDef() && Op.isDead())

602 return true;

603 return false;

604}

605

606

608 unsigned OpNum) const {

609 if (In.isCall() || In.isReturn() || In.isInlineAsm())

610 return true;

611

612 if (In.isBranch())

614 if (O.isGlobal() || O.isSymbol())

615 return true;

616

618 if (D.implicit_defs().empty() && D.implicit_uses().empty())

619 return false;

621

622

623

624 if (Op.getSubReg() != 0)

625 return false;

628 Op.isDef() ? D.implicit_defs() : D.implicit_uses();

630}

631

632

633

634

635

641 TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(*DefaultTOI),

642 LiveIns(PRI) {}

643

649 : MF(mf), TII(tii), TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(toi),

650 LiveIns(PRI) {}

651

652

653

654

655

656

657

659 bool Top)

660 : DS(S) {

661 if (!Top) {

662

663 Pos = 0;

664 return;

665 }

666

667 Pos = DS.Stack.size();

668 while (Pos > 0 && DS.isDelimiter(DS.Stack[Pos - 1]))

669 Pos--;

670}

671

672

674 unsigned S = 0;

676 S++;

677 return S;

678}

679

680

681

682

685 unsigned P = nextDown(Stack.size());

686 Stack.resize(P);

687}

688

689

692 Stack.push_back(Def(nullptr, N));

693}

694

695

696

697

700 unsigned P = Stack.size();

701 while (P > 0) {

702 bool Found = isDelimiter(Stack[P - 1], N);

703 P--;

704 if (Found)

705 break;

706 }

707

708 Stack.resize(P);

709}

710

711

712unsigned DataFlowGraph::DefStack::nextUp(unsigned P) const {

713

714

715 unsigned SS = Stack.size();

716 bool IsDelim;

718 do {

719 P++;

720 IsDelim = isDelimiter(Stack[P - 1]);

721 } while (P < SS && IsDelim);

723 return P;

724}

725

726

727unsigned DataFlowGraph::DefStack::nextDown(unsigned P) const {

728

729

730 assert(P > 0 && P <= Stack.size());

731 bool IsDelim = isDelimiter(Stack[P - 1]);

732 do {

733 if (--P == 0)

734 break;

735 IsDelim = isDelimiter(Stack[P - 1]);

736 } while (P > 0 && IsDelim);

738 return P;

739}

740

741

742

743RegisterAggr DataFlowGraph::getLandingPadLiveIns() const {

744 RegisterAggr LR(getPRI());

745 const Function &F = MF.getFunction();

746 const Constant *PF = F.hasPersonalityFn() ? F.getPersonalityFn() : nullptr;

747 const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();

748 if (RegisterId R = TLI.getExceptionPointerRegister(PF))

749 LR.insert(RegisterRef(R));

751 if (RegisterId R = TLI.getExceptionSelectorRegister(PF))

752 LR.insert(RegisterRef(R));

753 }

754 return LR;

755}

756

757

758

759

761 if (N == 0)

762 return nullptr;

763 return Memory.ptr(N);

764}

765

766

768 if (P == nullptr)

769 return 0;

770 return Memory.id(P);

771}

772

773

776 P.Addr->init();

777 P.Addr->setAttrs(Attrs);

778 return P;

779}

780

781

782

783Node DataFlowGraph::cloneNode(const Node B) {

784 Node NA = newNode(0);

785 memcpy(NA.Addr, B.Addr, sizeof(NodeBase));

786

789 RA.Addr->setReachingDef(0);

790 RA.Addr->setSibling(0);

792 Def DA = NA;

793 DA.Addr->setReachedDef(0);

794 DA.Addr->setReachedUse(0);

795 }

796 }

797 return NA;

798}

799

800

801

802Use DataFlowGraph::newUse(Instr Owner, MachineOperand &Op, uint16_t Flags) {

804 UA.Addr->setRegRef(&Op, *this);

805 return UA;

806}

807

809 uint16_t Flags) {

812 PUA.Addr->setRegRef(RR, *this);

813 PUA.Addr->setPredecessor(PredB.Id);

814 return PUA;

815}

816

817Def DataFlowGraph::newDef(Instr Owner, MachineOperand &Op, uint16_t Flags) {

819 DA.Addr->setRegRef(&Op, *this);

820 return DA;

821}

822

823Def DataFlowGraph::newDef(Instr Owner, RegisterRef RR, uint16_t Flags) {

826 DA.Addr->setRegRef(RR, *this);

827 return DA;

828}

829

832 Owner.Addr->addPhi(PA, *this);

833 return PA;

834}

835

838 SA.Addr->setCode(MI);

839 Owner.Addr->addMember(SA, *this);

840 return SA;

841}

842

843Block DataFlowGraph::newBlock(Func Owner, MachineBasicBlock *BB) {

845 BA.Addr->setCode(BB);

846 Owner.Addr->addMember(BA, *this);

847 return BA;

848}

849

850Func DataFlowGraph::newFunc(MachineFunction *MF) {

852 FA.Addr->setCode(MF);

853 return FA;

854}

855

856

858 reset();

859 BuildCfg = config;

861 ReservedRegs = MRI.getReservedRegs();

863

864 auto Insert = [](auto &Set, auto &&Range) {

865 Set.insert(Range.begin(), Range.end());

866 };

867

868 if (BuildCfg.TrackRegs.empty()) {

869 std::set BaseSet;

870 if (BuildCfg.Classes.empty()) {

871

872 for (unsigned R = 1, E = getPRI().getTRI().getNumRegs(); R != E; ++R)

873 BaseSet.insert(R);

874 } else {

877 BaseSet.insert(R);

878 }

879 }

881 if (SkipReserved && ReservedRegs[R])

882 continue;

884 }

885 } else {

886

887 for (unsigned R : BuildCfg.TrackRegs) {

888 if (SkipReserved && ReservedRegs[R])

889 continue;

891 }

892 }

893

894 TheFunc = newFunc(&MF);

895

896 if (MF.empty())

897 return;

898

900 Block BA = newBlock(TheFunc, &B);

901 BlockNodes.insert(std::make_pair(&B, BA));

903 if (I.isDebugInstr())

904 continue;

905 buildStmt(BA, I);

906 }

907 }

908

909 Block EA = TheFunc.Addr->getEntryBlock(*this);

910 NodeList Blocks = TheFunc.Addr->members(*this);

911

912

914 assert(EntryB.pred_empty() && "Function entry block has predecessors");

915 for (std::pair<MCRegister, Register> P : MRI.liveins())

917 if (MRI.tracksLiveness()) {

918 for (auto I : EntryB.liveins())

919 LiveIns.insert(RegisterRef(I.PhysReg, I.LaneMask));

920 }

921

922

924 if (RR.isReg() && isTracked(RR))

925 continue;

926 Phi PA = newPhi(EA);

928 Def DA = newDef(PA, RR, PhiFlags);

930 }

931

932

933

934

935

936

937 RegisterAggr EHRegs = getLandingPadLiveIns();

938 if (!EHRegs.empty()) {

939 for (Block BA : Blocks) {

941 if (B.isEHPad())

942 continue;

943

944

948

949

951 if (RR.isReg() && isTracked(RR))

952 continue;

953 Phi PA = newPhi(BA);

955

956 Def DA = newDef(PA, RR, PhiFlags);

958

959 for (Block PBA : Preds) {

960 PhiUse PUA = newPhiUse(PA, RR, PBA);

962 }

963 }

964 }

965 }

966

967

968

969

970 BlockRefsMap PhiM(getPRI());

971 BlockRefsMap PhiClobberM(getPRI());

972 for (Block BA : Blocks)

973 recordDefsForDF(PhiM, PhiClobberM, BA);

974 for (Block BA : Blocks)

975 buildPhis(PhiM, BA);

976

977

978

980 linkBlockRefs(DM, PhiClobberM, EA);

981

982

984 removeUnusedPhis();

985}

986

994

996 assert(Op.isReg() || Op.isRegMask());

997 if (Op.isReg())

1001}

1002

1003

1005

1006 for (auto &P : DefM)

1007 P.second.start_block(B);

1008}

1009

1010

1012

1013

1014

1015 for (auto &P : DefM)

1016 P.second.clear_block(B);

1017

1018

1019 for (auto I = DefM.begin(), E = DefM.end(), NextI = I; I != E; I = NextI) {

1020 NextI = std::next(I);

1021

1022 if (I->second.empty())

1023 DefM.erase(I);

1024 }

1025}

1026

1027

1028

1030 pushClobbers(IA, DefM);

1031 pushDefs(IA, DefM);

1032}

1033

1034

1035

1036void DataFlowGraph::pushClobbers(Instr IA, DefStackMap &DefM) {

1038 std::set Defined;

1039

1040

1041

1042

1043

1044

1045

1046

1047

1048

1049

1050

1051

1052 for (Def DA : IA.Addr->members_if(IsDef, *this)) {

1053 if (Visited.count(DA.Id))

1054 continue;

1056 continue;

1057

1061

1062

1063

1064 DefM[RR.Id].push(DA);

1065 Defined.insert(RR.Id);

1068 continue;

1069

1071 if (!Defined.count(A))

1072 DefM[A].push(DA);

1073 }

1074

1075 for (Node T : Rel)

1076 Visited.insert(T.Id);

1077 }

1078}

1079

1080

1081

1084#ifndef NDEBUG

1085 std::set Defined;

1086#endif

1087

1088

1089

1090

1091

1092

1093

1094

1095

1096

1097

1098

1099

1100 for (Def DA : IA.Addr->members_if(IsDef, *this)) {

1101 if (Visited.count(DA.Id))

1102 continue;

1104 continue;

1105

1107 Def PDA = Rel.front();

1108 RegisterRef RR = PDA.Addr->getRegRef(*this);

1109#ifndef NDEBUG

1110

1111

1112 if (!Defined.insert(RR.Id).second) {

1114 dbgs() << "Multiple definitions of register: " << Print(RR, *this)

1116 << '\n';

1118 }

1119#endif

1120

1121

1122 DefM[RR.Id].push(DA);

1125 continue;

1126

1128 DefM[A].push(DA);

1129 }

1130

1131 for (Node T : Rel)

1132 Visited.insert(T.Id);

1133 }

1134}

1135

1136

1137

1139 assert(IA.Id != 0 && RA.Id != 0);

1140

1143 do {

1146 } while (RA.Id != 0 && RA.Id != Start);

1147 return Refs;

1148}

1149

1150

1151void DataFlowGraph::reset() {

1153 BlockNodes.clear();

1154 TrackedUnits.clear();

1155 ReservedRegs.clear();

1156 TheFunc = Func();

1157}

1158

1159

1160

1161

1162

1163

1164

1166 assert(IA.Id != 0 && RA.Id != 0);

1167

1168 auto IsRelated = [this, RA](Ref TA) -> bool {

1169 if (TA.Addr->getKind() != RA.Addr->getKind())

1170 return false;

1171 if (getPRI().equal_to(TA.Addr->getRegRef(*this),

1172 RA.Addr->getRegRef(*this))) {

1173 return false;

1174 }

1175 return true;

1176 };

1177

1180 auto Cond = [&IsRelated, RA](Ref TA) -> bool {

1181 return IsRelated(TA) && &RA.Addr->getOp() == &TA.Addr->getOp();

1182 };

1183 return RA.Addr->getNextRef(RR, Cond, true, *this);

1184 }

1185

1187 auto Cond = [&IsRelated, RA](Ref TA) -> bool {

1188 if (!IsRelated(TA))

1189 return false;

1191 return true;

1192

1195 };

1196 return RA.Addr->getNextRef(RR, Cond, true, *this);

1197}

1198

1199

1200

1201

1202

1203

1204template

1205std::pair<Ref, Ref> DataFlowGraph::locateNextRef(Instr IA, Ref RA,

1207 assert(IA.Id != 0 && RA.Id != 0);

1208

1211 while (true) {

1213 if (NA.Id == 0 || NA.Id == Start)

1214 break;

1215 if (P(NA))

1216 break;

1217 RA = NA;

1218 }

1219

1220 if (NA.Id != 0 && NA.Id != Start)

1221 return std::make_pair(RA, NA);

1222 return std::make_pair(RA, Ref());

1223}

1224

1225

1226

1228 assert(IA.Id != 0 && RA.Id != 0);

1229

1231 auto IsShadow = [Flags](Ref TA) -> bool {

1232 return TA.Addr->getFlags() == Flags;

1233 };

1234 auto Loc = locateNextRef(IA, RA, IsShadow);

1235 if (Loc.second.Id != 0 || !Create)

1236 return Loc.second;

1237

1238

1239 Ref NA = cloneNode(RA);

1241 IA.Addr->addMemberAfter(Loc.first, NA, *this);

1242 return NA;

1243}

1244

1245

1246

1248 Stmt SA = newStmt(BA, &In);

1249

1250 auto isCall = [](const MachineInstr &In) -> bool {

1251 if (In.isCall())

1252 return true;

1253

1254 if (In.isBranch()) {

1256 if (Op.isGlobal() || Op.isSymbol())

1257 return true;

1258

1259

1260

1261 if (In.isIndirectBranch())

1262 return true;

1263 }

1264 return false;

1265 };

1266

1267 auto isDefUndef = [this](const MachineInstr &In, RegisterRef DR) -> bool {

1268

1269

1270 for (const MachineOperand &Op : In.all_uses()) {

1271 if (Op.getReg() == 0 || Op.isUndef())

1272 continue;

1274 if (getPRI().alias(DR, UR))

1275 return false;

1276 }

1277 return true;

1278 };

1279

1280 bool IsCall = isCall(In);

1281 unsigned NumOps = In.getNumOperands();

1282

1283

1284

1285

1286

1287 BitVector DoneDefs(TRI.getNumRegs());

1288

1289 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {

1290 MachineOperand &Op = In.getOperand(OpN);

1291 if (Op.isReg() || Op.isDef() || Op.isImplicit())

1292 continue;

1294 if (!R || R.isPhysical() || isTracked(RegisterRef(R)))

1295 continue;

1297 if (TOI.isPreserving(In, OpN)) {

1299

1302 }

1303 if (TOI.isClobbering(In, OpN))

1305 if (TOI.isFixedReg(In, OpN))

1307 if (IsCall && Op.isDead())

1309 Def DA = newDef(SA, Op, Flags);

1311 assert(!DoneDefs.test(R));

1312 DoneDefs.set(R);

1313 }

1314

1315

1316 BitVector DoneClobbers(TRI.getNumRegs());

1317 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {

1318 MachineOperand &Op = In.getOperand(OpN);

1319 if (Op.isRegMask())

1320 continue;

1322 Def DA = newDef(SA, Op, Flags);

1324

1325 const uint32_t *RM = Op.getRegMask();

1326 for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {

1328 continue;

1329 if (!(RM[i / 32] & (1u << (i % 32))))

1330 DoneClobbers.set(i);

1331 }

1332 }

1333

1334

1335

1336 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {

1337 MachineOperand &Op = In.getOperand(OpN);

1338 if (Op.isReg() || Op.isDef() || Op.isImplicit())

1339 continue;

1341 if (!R || R.isPhysical() || isTracked(RegisterRef(R)) || DoneDefs.test(R))

1342 continue;

1345 if (TOI.isPreserving(In, OpN)) {

1347

1348 if (isDefUndef(In, RR))

1350 }

1351 if (TOI.isClobbering(In, OpN))

1353 if (TOI.isFixedReg(In, OpN))

1355 if (IsCall && Op.isDead()) {

1356 if (DoneClobbers.test(R))

1357 continue;

1359 }

1360 Def DA = newDef(SA, Op, Flags);

1362 DoneDefs.set(R);

1363 }

1364

1365 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {

1366 MachineOperand &Op = In.getOperand(OpN);

1367 if (Op.isReg() || Op.isUse())

1368 continue;

1370 if (!R || R.isPhysical() || isTracked(RegisterRef(R)))

1371 continue;

1373 if (Op.isUndef())

1375 if (TOI.isFixedReg(In, OpN))

1377 Use UA = newUse(SA, Op, Flags);

1379 }

1380}

1381

1382

1383

1384

1385void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM,

1386 BlockRefsMap &PhiClobberM, Block BA) {

1387

1388

1389

1390 MachineBasicBlock *BB = BA.Addr->getCode();

1392 auto DFLoc = MDF.find(BB);

1393 if (DFLoc == MDF.end() || DFLoc->second.empty())

1394 return;

1395

1396

1397

1398

1399

1400

1401 RegisterAggr Defs(getPRI());

1402 RegisterAggr ClobberDefs(getPRI());

1404 for (Ref RA : IA.Addr->members_if(IsDef, *this)) {

1405 RegisterRef RR = RA.Addr->getRegRef(*this);

1407 continue;

1408 if (RR.isReg())

1409 Defs.insert(RR);

1410

1411 else if (RR.isMask())

1412 ClobberDefs.insert(RR);

1413 }

1414 }

1415

1416

1419 for (unsigned i = 0; i < IDF.size(); ++i) {

1420 auto F = MDF.find(IDF[i]);

1421 if (F != MDF.end())

1422 IDF.insert_range(F->second);

1423 }

1424

1425

1426

1427 for (auto *DB : IDF) {

1429 PhiM[DBA.Id].insert(Defs);

1430 PhiClobberM[DBA.Id].insert(ClobberDefs);

1431 }

1432}

1433

1434

1435

1436void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, Block BA,

1438

1439

1440 auto HasDF = PhiM.find(BA.Id);

1441 if (HasDF == PhiM.end() || HasDF->second.empty())

1442 return;

1443

1444

1446 const MachineBasicBlock *MBB = BA.Addr->getCode();

1447 for (MachineBasicBlock *PB : MBB->predecessors())

1449

1450 RegisterAggr PhiDefs(getPRI());

1451

1452

1453 if (!DefM.empty()) {

1455 for (Def DA : IA.Addr->members_if(IsDef, *this)) {

1456 auto DR = DA.Addr->getRegRef(*this);

1457 PhiDefs.insert(DR);

1458 }

1459 }

1460 }

1461

1462 MachineRegisterInfo &MRI = MF.getRegInfo();

1463 const RegisterAggr &Defs = PhiM[BA.Id];

1465

1466 for (RegisterRef RR : Defs.refs()) {

1467 if (!DefM.empty()) {

1468 auto F = DefM.find(RR.Id);

1469

1470

1471

1472 if (MRI.isAllocatable(RR.asMCReg()) || PhiDefs.hasCoverOf(RR) ||

1473 F == DefM.end() || F->second.empty())

1474 continue;

1475

1476 auto RDef = F->second.top();

1478 continue;

1479 PhiDefs.insert(RR);

1480 }

1481 Phi PA = newPhi(BA);

1482 PA.Addr->addMember(newDef(PA, RR, PhiFlags), *this);

1483

1484

1485 for (Block PBA : Preds) {

1486 PA.Addr->addMember(newPhiUse(PA, RR, PBA), *this);

1487 }

1488 }

1489}

1490

1491

1492void DataFlowGraph::removeUnusedPhis() {

1493

1494

1495

1496

1497

1498

1499 SetVector PhiQ;

1501 for (auto P : BA.Addr->members_if(IsPhi, *this))

1502 PhiQ.insert(P.Id);

1503 }

1504

1505 static auto HasUsedDef = [](NodeList &Ms) -> bool {

1506 for (Node M : Ms) {

1508 continue;

1510 if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0)

1511 return true;

1512 }

1513 return false;

1514 };

1515

1516

1517

1518

1519 while (!PhiQ.empty()) {

1521 PhiQ.remove(PA.Id);

1522 NodeList Refs = PA.Addr->members(*this);

1523 if (HasUsedDef(Refs))

1524 continue;

1525 for (Ref RA : Refs) {

1526 if (NodeId RD = RA.Addr->getReachingDef()) {

1530 PhiQ.insert(OA.Id);

1531 }

1532 if (RA.Addr->isDef())

1534 else

1536 }

1537 Block BA = PA.Addr->getOwner(*this);

1539 }

1540}

1541

1542

1543

1544

1545template

1546void DataFlowGraph::linkRefUp(Instr IA, NodeAddr TA, DefStack &DS) {

1547 if (DS.empty())

1548 return;

1549 RegisterRef RR = TA.Addr->getRegRef(*this);

1550 NodeAddr TAP;

1551

1552

1553 RegisterAggr Defs(getPRI());

1554

1555 for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) {

1556 RegisterRef QR = I->Addr->getRegRef(*this);

1557

1558

1559

1560 bool Seen = Defs.hasCoverOf(QR);

1561 if (Seen)

1562 continue;

1563

1564 bool Cover = Defs.insert(QR).hasCoverOf(RR);

1565

1566

1567 Def RDA = *I;

1568

1569

1570 if (TAP.Id == 0) {

1571 TAP = TA;

1572 } else {

1573

1576 }

1577

1578

1580

1581 if (Cover)

1582 break;

1583 }

1584}

1585

1586

1587template

1588void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, Stmt SA, Predicate P) {

1589#ifndef NDEBUG

1591#endif

1592

1593

1594 for (Ref RA : SA.Addr->members_if(P, *this)) {

1595 uint16_t Kind = RA.Addr->getKind();

1597 RegisterRef RR = RA.Addr->getRegRef(*this);

1598#ifndef NDEBUG

1599

1601 Defs.insert(RR);

1602#endif

1603

1604 auto F = DefM.find(RR.Id);

1605 if (F == DefM.end())

1606 continue;

1609 linkRefUp<UseNode *>(SA, RA, DS);

1611 linkRefUp<DefNode *>(SA, RA, DS);

1612 else

1614 }

1615}

1616

1617

1618

1619void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, BlockRefsMap &PhiClobberM,

1621

1622

1623

1624

1625

1626 buildPhis(PhiClobberM, BA, DefM);

1627

1628

1630

1631 auto IsClobber = [](Ref RA) -> bool {

1633 };

1634 auto IsNoClobber = [](Ref RA) -> bool {

1636 };

1637

1638 assert(BA.Addr && "block node address is needed to create a data-flow link");

1639

1640

1641

1643

1644

1646 linkStmtRefs(DefM, IA, IsUse);

1647 linkStmtRefs(DefM, IA, IsClobber);

1648 }

1649

1650

1651 pushClobbers(IA, DefM);

1652

1654 linkStmtRefs(DefM, IA, IsNoClobber);

1655

1656 pushDefs(IA, DefM);

1657 }

1658

1659

1661 for (auto *I : *N) {

1662 MachineBasicBlock *SB = I->getBlock();

1664 linkBlockRefs(DefM, PhiClobberM, SBA);

1665 }

1666

1667

1668 auto IsUseForBA = [BA](Node NA) -> bool {

1670 return false;

1673 };

1674

1675 RegisterAggr EHLiveIns = getLandingPadLiveIns();

1676 MachineBasicBlock *MBB = BA.Addr->getCode();

1677

1678 for (MachineBasicBlock *SB : MBB->successors()) {

1679 bool IsEHPad = SB->isEHPad();

1682

1683 if (IsEHPad) {

1684

1685 Ref RA = IA.Addr->getFirstMember(*this);

1687 if (EHLiveIns.hasCoverOf(RA.Addr->getRegRef(*this)))

1688 continue;

1689 }

1690

1691 for (auto U : IA.Addr->members_if(IsUseForBA, *this)) {

1693 RegisterRef RR = PUA.Addr->getRegRef(*this);

1694 linkRefUp<UseNode *>(IA, PUA, DefM[RR.Id]);

1695 }

1696 }

1697 }

1698

1699

1701}

1702

1703

1704void DataFlowGraph::unlinkUseDF(Use UA) {

1705 NodeId RD = UA.Addr->getReachingDef();

1706 NodeId Sib = UA.Addr->getSibling();

1707

1708 if (RD == 0) {

1710 return;

1711 }

1712

1715 if (TA.Id == UA.Id) {

1716 RDA.Addr->setReachedUse(Sib);

1717 return;

1718 }

1719

1720 while (TA.Id != 0) {

1721 NodeId S = TA.Addr->getSibling();

1722 if (S == UA.Id) {

1723 TA.Addr->setSibling(UA.Addr->getSibling());

1724 return;

1725 }

1727 }

1728}

1729

1730

1731void DataFlowGraph::unlinkDefDF(Def DA) {

1732

1733

1734

1735

1736

1737

1738

1739

1740

1741

1742

1743

1744

1745

1746

1747

1748

1749

1750 NodeId RD = DA.Addr->getReachingDef();

1751

1752

1753

1754

1755

1758 while (N) {

1760

1761 Res.push_back(RA);

1762 N = RA.Addr->getSibling();

1763 }

1764 return Res;

1765 };

1766 NodeList ReachedDefs = getAllNodes(DA.Addr->getReachedDef());

1767 NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse());

1768

1769 if (RD == 0) {

1770 for (Ref I : ReachedDefs)

1771 I.Addr->setSibling(0);

1772 for (Ref I : ReachedUses)

1773 I.Addr->setSibling(0);

1774 }

1775 for (Def I : ReachedDefs)

1776 I.Addr->setReachingDef(RD);

1777 for (Use I : ReachedUses)

1778 I.Addr->setReachingDef(RD);

1779

1780 NodeId Sib = DA.Addr->getSibling();

1781 if (RD == 0) {

1783 return;

1784 }

1785

1786

1789 if (TA.Id == DA.Id) {

1790

1791

1792 RDA.Addr->setReachedDef(Sib);

1793 } else {

1794

1795

1796 while (TA.Id != 0) {

1797 NodeId S = TA.Addr->getSibling();

1798 if (S == DA.Id) {

1799 TA.Addr->setSibling(Sib);

1800 break;

1801 }

1803 }

1804 }

1805

1806

1807 if (!ReachedDefs.empty()) {

1808 auto Last = Def(ReachedDefs.back());

1809 Last.Addr->setSibling(RDA.Addr->getReachedDef());

1810 RDA.Addr->setReachedDef(ReachedDefs.front().Id);

1811 }

1812

1813 if (!ReachedUses.empty()) {

1814 auto Last = Use(ReachedUses.back());

1815 Last.Addr->setSibling(RDA.Addr->getReachedUse());

1816 RDA.Addr->setReachedUse(ReachedUses.front().Id);

1817 }

1818}

1819

1823

1826

1828 Ops.push_back(&R.Addr->getOp());

1829 RegisterRef RR = R.Addr->getRegRef(*this);

1830 if (IgnoreReserved && RR.isReg() && ReservedRegs[RR.asMCReg().id()])

1831 continue;

1833 return true;

1834 }

1836 if (Op.isReg() && Op.isRegMask())

1837 continue;

1839 return true;

1840 }

1841 return false;

1842}

1843

1844}

unsigned const MachineRegisterInfo * MRI

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file implements the BitVector class.

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static ManagedStatic< DebugCounterOwner > Owner

static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")

static RegisterPass< DebugifyModulePass > DM("debugify", "Attach debug info to everything")

const size_t AbstractManglingParser< Derived, Alloc >::NumOps

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

A common definition of LaneBitmask for use in TableGen and CodeGen.

Promote Memory to Register

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)

const SmallVectorImpl< MachineOperand > & Cond

SI optimize exec mask operations pre RA

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

This file describes how to lower LLVM code to machine code.

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

void clear()

clear - Removes all bits from the bitvector.

LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)

Allocate space at the specified alignment.

Describe properties that are true of each instruction in the target description file.

constexpr unsigned id() const

unsigned pred_size() const

iterator_range< livein_iterator > liveins() const

unsigned succ_size() const

iterator_range< succ_iterator > successors()

iterator_range< pred_iterator > predecessors()

DominanceFrontierBase< MachineBasicBlock, false >::DomSetType DomSetType

DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...

const MachineBasicBlock & front() const

Representation of each machine instruction.

const MachineOperand * const_mop_iterator

MachineOperand class - Representation of each machine instruction operand.

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

Wrapper class representing virtual and physical registers.

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...

This class implements an extremely fast bulk output stream that can only output to a stream.

This class provides various memory handling functions that manipulate MemoryBlock instances.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

NodeAddr< DefNode * > Def

NodeAddr< InstrNode * > Instr

std::set< RegisterRef, RegisterRefLess > RegisterSet

NodeAddr< BlockNode * > Block

NodeAddr< PhiNode * > Phi

Print(const T &, const DataFlowGraph &) -> Print< T >

NodeAddr< PhiUseNode * > PhiUse

NodeAddr< StmtNode * > Stmt

NodeAddr< UseNode * > Use

static void printRefHeader(raw_ostream &OS, const Ref RA, const DataFlowGraph &G)

Definition RDFGraph.cpp:110

NodeAddr< NodeBase * > Node

raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)

Definition RDFGraph.cpp:44

std::set< NodeId > NodeSet

SmallVector< Node, 4 > NodeList

NodeAddr< FuncNode * > Func

NodeAddr< RefNode * > Ref

bool disjoint(const std::set< T > &A, const std::set< T > &B)

constexpr from_range_t from_range

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI EHPersonality classifyEHPersonality(const Value *Pers)

See if the given exception handling personality function is one that we understand.

DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode

@ Ref

The access may reference the value stored in memory.

bool isFuncletEHPersonality(EHPersonality Pers)

Returns true if this is a personality function that invokes handler funclets (which must return to it...

@ Sub

Subtraction of integers.

uint16_t MCPhysReg

An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...

DWARFExpression::Operation Op

auto find_if(R &&Range, UnaryPredicate P)

Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.

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

Returns true if Element is found in Range.

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

Implement std::hash so that hash_code can be used in STL containers.

static constexpr LaneBitmask getAll()

MachineBasicBlock * getCode() const

void addPhi(Phi PA, const DataFlowGraph &G)

Definition RDFGraph.cpp:538

NodeList members_if(Predicate P, const DataFlowGraph &G) const

void removeMember(Node NA, const DataFlowGraph &G)

Definition RDFGraph.cpp:487

NodeList members(const DataFlowGraph &G) const

Definition RDFGraph.cpp:519

void addMember(Node NA, const DataFlowGraph &G)

Definition RDFGraph.cpp:467

Node getFirstMember(const DataFlowGraph &G) const

Definition RDFGraph.cpp:453

void addMemberAfter(Node MA, Node NA, const DataFlowGraph &G)

Definition RDFGraph.cpp:480

Node getLastMember(const DataFlowGraph &G) const

Definition RDFGraph.cpp:460

void clear_block(NodeId N)

Definition RDFGraph.cpp:698

void start_block(NodeId N)

Definition RDFGraph.cpp:690

unsigned size() const

Definition RDFGraph.cpp:673

void pop()

Definition RDFGraph.cpp:683

NodeId id(const NodeBase *P) const

Definition RDFGraph.cpp:767

void unlinkUse(Use UA, bool RemoveFromOwner)

void releaseBlock(NodeId B, DefStackMap &DefM)

Definition RDFGraph.cpp:1011

Ref getNextRelated(Instr IA, Ref RA) const

Definition RDFGraph.cpp:1165

bool isTracked(RegisterRef RR) const

Definition RDFGraph.cpp:1820

RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const

Definition RDFGraph.cpp:987

static bool IsDef(const Node BA)

DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, const MachineDominanceFrontier &mdf)

Definition RDFGraph.cpp:636

Ref getNextShadow(Instr IA, Ref RA, bool Create)

Definition RDFGraph.cpp:1227

static bool IsPhi(const Node BA)

NodeList getRelatedRefs(Instr IA, Ref RA) const

Definition RDFGraph.cpp:1138

void unlinkDef(Def DA, bool RemoveFromOwner)

static bool IsUse(const Node BA)

const PhysicalRegisterInfo & getPRI() const

void markBlock(NodeId B, DefStackMap &DefM)

Definition RDFGraph.cpp:1004

NodeBase * ptr(NodeId N) const

Definition RDFGraph.cpp:760

Block findBlock(MachineBasicBlock *BB) const

bool hasUntrackedRef(Stmt S, bool IgnoreReserved=true) const

Definition RDFGraph.cpp:1824

std::unordered_map< RegisterId, DefStack > DefStackMap

const TargetRegisterInfo & getTRI() const

void pushAllDefs(Instr IA, DefStackMap &DM)

Definition RDFGraph.cpp:1029

NodeAddr< T > addr(NodeId N) const

void linkToDef(NodeId Self, Def DA)

Definition RDFGraph.cpp:439

MachineFunction * getCode() const

Block findBlock(const MachineBasicBlock *BB, const DataFlowGraph &G) const

Definition RDFGraph.cpp:568

Block getEntryBlock(const DataFlowGraph &G)

Definition RDFGraph.cpp:578

Node getOwner(const DataFlowGraph &G)

Definition RDFGraph.cpp:525

NodeId id(const NodeBase *P) const

Definition RDFGraph.cpp:370

void clear()

Definition RDFGraph.cpp:382

Node New()

Definition RDFGraph.cpp:359

static uint16_t flags(uint16_t T)

static uint16_t kind(uint16_t T)

static uint16_t type(uint16_t T)

void setFlags(uint16_t F)

void append(Node NA)

Definition RDFGraph.cpp:389

uint16_t getFlags() const

NodeId getPredecessor() const

void setRegRef(RegisterRef RR, DataFlowGraph &G)

Definition RDFGraph.cpp:411

RegisterRef getRegRef(const DataFlowGraph &G) const

Definition RDFGraph.cpp:401

Node getOwner(const DataFlowGraph &G)

Definition RDFGraph.cpp:427

iterator_range< ref_iterator > refs() const

constexpr bool isReg() const

static constexpr bool isMaskId(RegisterId Id)

static constexpr bool isRegId(RegisterId Id)

constexpr MCRegister asMCReg() const

MachineInstr * getCode() const

virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const

Definition RDFGraph.cpp:607

const TargetInstrInfo & TII

virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const

Definition RDFGraph.cpp:588

virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const

Definition RDFGraph.cpp:594

void linkToDef(NodeId Self, Def DA)

Definition RDFGraph.cpp:446