Movatterモバイル変換

Go to the documentation of this file.

1//===- RDFGraph.cpp -------------------------------------------------------===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// Target-independent, SSA-based data flow graph for register data flow (RDF).

10//

11#include "llvm/CodeGen/RDFGraph.h"

12#include "llvm/ADT/BitVector.h"

13#include "llvm/ADT/STLExtras.h"

14#include "llvm/ADT/SetVector.h"

15#include "llvm/CodeGen/MachineBasicBlock.h"

16#include "llvm/CodeGen/MachineDominanceFrontier.h"

17#include "llvm/CodeGen/MachineDominators.h"

18#include "llvm/CodeGen/MachineFunction.h"

19#include "llvm/CodeGen/MachineInstr.h"

20#include "llvm/CodeGen/MachineOperand.h"

21#include "llvm/CodeGen/MachineRegisterInfo.h"

22#include "llvm/CodeGen/RDFRegisters.h"

23#include "llvm/CodeGen/TargetInstrInfo.h"

24#include "llvm/CodeGen/TargetLowering.h"

25#include "llvm/CodeGen/TargetRegisterInfo.h"

26#include "llvm/CodeGen/TargetSubtargetInfo.h"

27#include "llvm/IR/Function.h"

28#include "llvm/MC/LaneBitmask.h"

29#include "llvm/MC/MCInstrDesc.h"

30#include "llvm/Support/ErrorHandling.h"

31#include "llvm/Support/raw_ostream.h"

32#include <cassert>

33#include <cstdint>

34#include <cstring>

35#include <iterator>

36#include <set>

37#include <utility>

38#include <vector>

40// Printing functions. Have them here first, so that the rest of the code

41// can use them.

42namespacellvm::rdf {

44raw_ostream &operator<<(raw_ostream &OS,constPrint<RegisterRef> &P) {

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

46returnOS;

47}

49raw_ostream &operator<<(raw_ostream &OS,constPrint<NodeId> &P) {

50if (P.Obj == 0)

51returnOS <<"null";

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

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

54uint16_t Kind =NodeAttrs::kind(Attrs);

55uint16_t Flags =NodeAttrs::flags(Attrs);

56switch (NodeAttrs::type(Attrs)) {

57caseNodeAttrs::Code:

58switch (Kind) {

59caseNodeAttrs::Func:

60OS <<'f';

61break;

62caseNodeAttrs::Block:

63OS <<'b';

64break;

65caseNodeAttrs::Stmt:

66OS <<'s';

67break;

68caseNodeAttrs::Phi:

69OS <<'p';

70break;

71default:

72OS <<"c?";

73break;

74 }

75break;

76caseNodeAttrs::Ref:

77if (Flags &NodeAttrs::Undef)

78OS <<'/';

79if (Flags &NodeAttrs::Dead)

80OS <<'\\';

81if (Flags &NodeAttrs::Preserving)

82OS <<'+';

83if (Flags &NodeAttrs::Clobbering)

84OS <<'~';

85switch (Kind) {

86caseNodeAttrs::Use:

87OS <<'u';

88break;

89caseNodeAttrs::Def:

90OS <<'d';

91break;

92caseNodeAttrs::Block:

93OS <<'b';

94break;

95default:

96OS <<"r?";

97break;

98 }

99break;

100default:

101OS <<'?';

102break;

103 }

104OS <<P.Obj;

105if (Flags &NodeAttrs::Shadow)

106OS <<'"';

107returnOS;

108}

109

110staticvoidprintRefHeader(raw_ostream &OS,constRef RA,

111constDataFlowGraph &G) {

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

113if (RA.Addr->getFlags() &NodeAttrs::Fixed)

114OS <<'!';

115}

116

117raw_ostream &operator<<(raw_ostream &OS,constPrint<Def> &P) {

118printRefHeader(OS,P.Obj,P.G);

119OS <<'(';

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

121OS <<Print(N,P.G);

122OS <<',';

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

124OS <<Print(N,P.G);

125OS <<',';

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

127OS <<Print(N,P.G);

128OS <<"):";

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

130OS <<Print(N,P.G);

131returnOS;

132}

133

134raw_ostream &operator<<(raw_ostream &OS,constPrint<Use> &P) {

135printRefHeader(OS,P.Obj,P.G);

136OS <<'(';

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

138OS <<Print(N,P.G);

139OS <<"):";

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

141OS <<Print(N,P.G);

142returnOS;

143}

144

145raw_ostream &operator<<(raw_ostream &OS,constPrint<PhiUse> &P) {

146printRefHeader(OS,P.Obj,P.G);

147OS <<'(';

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

149OS <<Print(N,P.G);

150OS <<',';

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

152OS <<Print(N,P.G);

153OS <<"):";

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

155OS <<Print(N,P.G);

156returnOS;

157}

158

159raw_ostream &operator<<(raw_ostream &OS,constPrint<Ref> &P) {

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

161caseNodeAttrs::Def:

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

163break;

164caseNodeAttrs::Use:

165if (P.Obj.Addr->getFlags() &NodeAttrs::PhiRef)

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

167else

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

169break;

170 }

171returnOS;

172}

173

174raw_ostream &operator<<(raw_ostream &OS,constPrint<NodeList> &P) {

175unsignedN =P.Obj.size();

176for (autoI :P.Obj) {

177OS <<Print(I.Id,P.G);

178if (--N)

179OS <<' ';

180 }

181returnOS;

182}

183

184raw_ostream &operator<<(raw_ostream &OS,constPrint<NodeSet> &P) {

185unsignedN =P.Obj.size();

186for (autoI :P.Obj) {

187OS <<Print(I,P.G);

188if (--N)

189OS <<' ';

190 }

191returnOS;

192}

193

194namespace{

195

196template <typename T>structPrintListV {

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

198

199usingType =T;

200constNodeList &List;

201const DataFlowGraph &G;

202};

203

204template <typename T>

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

206unsignedN =P.List.size();

207for (NodeAddr<T>A :P.List) {

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

209if (--N)

210OS <<", ";

211 }

212returnOS;

213}

214

215}// end anonymous namespace

216

217raw_ostream &operator<<(raw_ostream &OS,constPrint<Phi> &P) {

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

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

220returnOS;

221}

222

223raw_ostream &operator<<(raw_ostream &OS,constPrint<Stmt> &P) {

224constMachineInstr &MI = *P.Obj.Addr->getCode();

225unsigned Opc =MI.getOpcode();

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

227// Print the target for calls and branches (for readability).

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

229MachineInstr::const_mop_iterator T =

230llvm::find_if(MI.operands(), [](constMachineOperand &Op) ->bool {

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

232 });

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

234OS <<' ';

235if (T->isMBB())

236OS <<printMBBReference(*T->getMBB());

237elseif (T->isGlobal())

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

239elseif (T->isSymbol())

240OS <<T->getSymbolName();

241 }

242 }

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

244returnOS;

245}

246

247raw_ostream &operator<<(raw_ostream &OS,constPrint<Instr> &P) {

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

249caseNodeAttrs::Phi:

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

251break;

252caseNodeAttrs::Stmt:

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

254break;

255default:

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

257break;

258 }

259returnOS;

260}

261

262raw_ostream &operator<<(raw_ostream &OS,constPrint<Block> &P) {

263MachineBasicBlock *BB =P.Obj.Addr->getCode();

264unsigned NP = BB->pred_size();

265 std::vector<int> Ns;

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

267unsignedN = Ns.size();

268for (intI : Ns) {

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

270if (--N)

271OS <<", ";

272 }

273 };

274

275OS <<Print(P.Obj.Id,P.G) <<": --- " <<printMBBReference(*BB)

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

277for (MachineBasicBlock *B : BB->predecessors())

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

279 PrintBBs(Ns);

280

281unsigned NS = BB->succ_size();

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

283 Ns.clear();

284for (MachineBasicBlock *B : BB->successors())

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

286 PrintBBs(Ns);

287OS <<'\n';

288

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

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

291returnOS;

292}

293

294raw_ostream &operator<<(raw_ostream &OS,constPrint<Func> &P) {

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

296 <<Print(P.Obj.Id,P.G)

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

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

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

300OS <<"]\n";

301returnOS;

302}

303

304raw_ostream &operator<<(raw_ostream &OS,constPrint<RegisterSet> &P) {

305OS <<'{';

306for (autoI :P.Obj)

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

308OS <<" }";

309returnOS;

310}

311

312raw_ostream &operator<<(raw_ostream &OS,constPrint<RegisterAggr> &P) {

313OS <<P.Obj;

314returnOS;

315}

316

317raw_ostream &operator<<(raw_ostream &OS,

318constPrint<DataFlowGraph::DefStack> &P) {

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

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

321 <<'>';

322I.down();

323if (I !=E)

324OS <<' ';

325 }

326returnOS;

327}

328

329// Node allocation functions.

330//

331// Node allocator is like a slab memory allocator: it allocates blocks of

332// memory in sizes that are multiples of the size of a node. Each block has

333// the same size. Nodes are allocated from the currently active block, and

334// when it becomes full, a new one is created.

335// There is a mapping scheme between node id and its location in a block,

336// and within that block is described in the header file.

337//

338void NodeAllocator::startNewBlock() {

339void *T = MemPool.Allocate(NodesPerBlock *NodeMemSize,NodeMemSize);

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

341 Blocks.push_back(P);

342// Check if the block index is still within the allowed range, i.e. less

343// than 2^N, where N is the number of bits in NodeId for the block index.

344// BitsPerIndex is the number of bits per node index.

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

346"Out of bits for block index");

347 ActiveEnd =P;

348}

349

350bool NodeAllocator::needNewBlock() {

351if (Blocks.empty())

352returntrue;

353

354char *ActiveBegin = Blocks.back();

355uint32_t Index = (ActiveEnd - ActiveBegin) /NodeMemSize;

356returnIndex >= NodesPerBlock;

357}

358

359Node NodeAllocator::New() {

360if (needNewBlock())

361 startNewBlock();

362

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

364uint32_t Index = (ActiveEnd - Blocks[ActiveB]) /NodeMemSize;

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

366 ActiveEnd +=NodeMemSize;

367return NA;

368}

369

370NodeId NodeAllocator::id(constNodeBase *P) const{

371 uintptr_tA =reinterpret_cast<uintptr_t>(P);

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

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

374if (A < B || A >=B + NodesPerBlock *NodeMemSize)

375continue;

376uint32_t Idx = (A -B) /NodeMemSize;

377return makeId(i,Idx);

378 }

379llvm_unreachable("Invalid node address");

380}

381

382voidNodeAllocator::clear() {

383 MemPool.Reset();

384 Blocks.clear();

385 ActiveEnd =nullptr;

386}

387

388// Insert node NA after "this" in the circular chain.

389voidNodeBase::append(Node NA) {

390NodeId Nx =Next;

391// If NA is already "next", do nothing.

392if (Next != NA.Id) {

393Next = NA.Id;

394 NA.Addr->Next = Nx;

395 }

396}

397

398// Fundamental node manipulator functions.

399

400// Obtain the register reference from a reference node.

401RegisterRef RefNode::getRegRef(constDataFlowGraph &G) const{

402assert(NodeAttrs::type(Attrs) ==NodeAttrs::Ref);

403if (NodeAttrs::flags(Attrs) &NodeAttrs::PhiRef)

404returnG.unpack(RefData.PR);

405assert(RefData.Op !=nullptr);

406returnG.makeRegRef(*RefData.Op);

407}

408

409// Set the register reference in the reference node directly (for references

410// in phi nodes).

411voidRefNode::setRegRef(RegisterRef RR,DataFlowGraph &G) {

412assert(NodeAttrs::type(Attrs) ==NodeAttrs::Ref);

413assert(NodeAttrs::flags(Attrs) &NodeAttrs::PhiRef);

414RefData.PR =G.pack(RR);

415}

416

417// Set the register reference in the reference node based on a machine

418// operand (for references in statement nodes).

419voidRefNode::setRegRef(MachineOperand *Op,DataFlowGraph &G) {

420assert(NodeAttrs::type(Attrs) ==NodeAttrs::Ref);

421assert(!(NodeAttrs::flags(Attrs) &NodeAttrs::PhiRef));

422 (void)G;

423RefData.Op =Op;

424}

425

426// Get the owner of a given reference node.

427Node RefNode::getOwner(constDataFlowGraph &G) {

428Node NA =G.addr<NodeBase *>(getNext());

429

430while (NA.Addr !=this) {

431if (NA.Addr->getType() ==NodeAttrs::Code)

432return NA;

433 NA =G.addr<NodeBase *>(NA.Addr->getNext());

434 }

435llvm_unreachable("No owner in circular list");

436}

437

438// Connect the def node to the reaching def node.

439voidDefNode::linkToDef(NodeId Self,Def DA) {

440RefData.RD = DA.Id;

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

442 DA.Addr->setReachedDef(Self);

443}

444

445// Connect the use node to the reaching def node.

446voidUseNode::linkToDef(NodeId Self,Def DA) {

447RefData.RD = DA.Id;

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

449 DA.Addr->setReachedUse(Self);

450}

451

452// Get the first member of the code node.

453Node CodeNode::getFirstMember(constDataFlowGraph &G) const{

454if (CodeData.FirstM == 0)

455returnNode();

456returnG.addr<NodeBase *>(CodeData.FirstM);

457}

458

459// Get the last member of the code node.

460Node CodeNode::getLastMember(constDataFlowGraph &G) const{

461if (CodeData.LastM == 0)

462returnNode();

463returnG.addr<NodeBase *>(CodeData.LastM);

464}

465

466// Add node NA at the end of the member list of the given code node.

467voidCodeNode::addMember(Node NA,constDataFlowGraph &G) {

468Node ML =getLastMember(G);

469if (ML.Id != 0) {

470ML.Addr->append(NA);

471 }else {

472CodeData.FirstM = NA.Id;

473NodeId Self =G.id(this);

474 NA.Addr->setNext(Self);

475 }

476CodeData.LastM = NA.Id;

477}

478

479// Add node NA after member node MA in the given code node.

480voidCodeNode::addMemberAfter(Node MA,Node NA,constDataFlowGraph &G) {

481 MA.Addr->append(NA);

482if (CodeData.LastM == MA.Id)

483CodeData.LastM = NA.Id;

484}

485

486// Remove member node NA from the given code node.

487voidCodeNode::removeMember(Node NA,constDataFlowGraph &G) {

488Node MA =getFirstMember(G);

489assert(MA.Id != 0);

490

491// Special handling if the member to remove is the first member.

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

493if (CodeData.LastM == MA.Id) {

494// If it is the only member, set both first and last to 0.

495CodeData.FirstM =CodeData.LastM = 0;

496 }else {

497// Otherwise, advance the first member.

498CodeData.FirstM = MA.Addr->getNext();

499 }

500return;

501 }

502

503while (MA.Addr !=this) {

504NodeId MX = MA.Addr->getNext();

505if (MX == NA.Id) {

506 MA.Addr->setNext(NA.Addr->getNext());

507// If the member to remove happens to be the last one, update the

508// LastM indicator.

509if (CodeData.LastM == NA.Id)

510CodeData.LastM = MA.Id;

511return;

512 }

513 MA =G.addr<NodeBase *>(MX);

514 }

515llvm_unreachable("No such member");

516}

517

518// Return the list of all members of the code node.

519NodeList CodeNode::members(constDataFlowGraph &G) const{

520staticauto True = [](Node) ->bool {returntrue; };

521returnmembers_if(True,G);

522}

523

524// Return the owner of the given instr node.

525Node InstrNode::getOwner(constDataFlowGraph &G) {

526Node NA =G.addr<NodeBase *>(getNext());

527

528while (NA.Addr !=this) {

529assert(NA.Addr->getType() ==NodeAttrs::Code);

530if (NA.Addr->getKind() ==NodeAttrs::Block)

531return NA;

532 NA =G.addr<NodeBase *>(NA.Addr->getNext());

533 }

534llvm_unreachable("No owner in circular list");

535}

536

537// Add the phi node PA to the given block node.

538voidBlockNode::addPhi(Phi PA,constDataFlowGraph &G) {

539Node M =getFirstMember(G);

540if (M.Id == 0) {

541addMember(PA,G);

542return;

543 }

544

545assert(M.Addr->getType() ==NodeAttrs::Code);

546if (M.Addr->getKind() ==NodeAttrs::Stmt) {

547// If the first member of the block is a statement, insert the phi as

548// the first member.

549CodeData.FirstM = PA.Id;

550 PA.Addr->setNext(M.Id);

551 }else {

552// If the first member is a phi, find the last phi, and append PA to it.

553assert(M.Addr->getKind() ==NodeAttrs::Phi);

554Node MN = M;

555do {

556 M = MN;

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

558assert(MN.Addr->getType() ==NodeAttrs::Code);

559 }while (MN.Addr->getKind() ==NodeAttrs::Phi);

560

561// M is the last phi.

562addMemberAfter(M, PA,G);

563 }

564}

565

566// Find the block node corresponding to the machine basic block BB in the

567// given func node.

568Block FuncNode::findBlock(constMachineBasicBlock *BB,

569constDataFlowGraph &G) const{

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

571NodeList Ms =members_if(EqBB,G);

572if (!Ms.empty())

573return Ms[0];

574returnBlock();

575}

576

577// Get the block node for the entry block in the given function.

578Block FuncNode::getEntryBlock(constDataFlowGraph &G) {

579MachineBasicBlock *EntryB = &getCode()->front();

580returnfindBlock(EntryB,G);

581}

582

583// Target operand information.

584//

585

586// For a given instruction, check if there are any bits of RR that can remain

587// unchanged across this def.

588boolTargetOperandInfo::isPreserving(constMachineInstr &In,

589unsigned OpNum) const{

590returnTII.isPredicated(In);

591}

592

593// Check if the definition of RR produces an unspecified value.

594boolTargetOperandInfo::isClobbering(constMachineInstr &In,

595unsigned OpNum) const{

596constMachineOperand &Op = In.getOperand(OpNum);

597if (Op.isRegMask())

598returntrue;

599assert(Op.isReg());

600if (In.isCall())

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

602returntrue;

603returnfalse;

604}

605

606// Check if the given instruction specifically requires

607boolTargetOperandInfo::isFixedReg(constMachineInstr &In,

608unsigned OpNum) const{

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

610returntrue;

611// Check for a tail call.

612if (In.isBranch())

613for (constMachineOperand &O : In.operands())

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

615returntrue;

616

617constMCInstrDesc &D = In.getDesc();

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

619returnfalse;

620constMachineOperand &Op = In.getOperand(OpNum);

621// If there is a sub-register, treat the operand as non-fixed. Currently,

622// fixed registers are those that are listed in the descriptor as implicit

623// uses or defs, and those lists do not allow sub-registers.

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

625returnfalse;

626Register Reg =Op.getReg();

627ArrayRef<MCPhysReg> ImpOps =

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

629returnis_contained(ImpOps,Reg);

630}

631

632//

633// The data flow graph construction.

634//

635

636DataFlowGraph::DataFlowGraph(MachineFunction &mf,constTargetInstrInfo &tii,

637constTargetRegisterInfo &tri,

638constMachineDominatorTree &mdt,

639constMachineDominanceFrontier &mdf)

640 : DefaultTOI(std::make_unique<TargetOperandInfo>(tii)), MF(mf),TII(tii),

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

642 LiveIns(PRI) {}

643

644DataFlowGraph::DataFlowGraph(MachineFunction &mf,constTargetInstrInfo &tii,

645constTargetRegisterInfo &tri,

646constMachineDominatorTree &mdt,

647constMachineDominanceFrontier &mdf,

648constTargetOperandInfo &toi)

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

650 LiveIns(PRI) {}

651

652// The implementation of the definition stack.

653// Each register reference has its own definition stack. In particular,

654// for a register references "Reg" and "Reg:subreg" will each have their

655// own definition stacks.

656

657// Construct a stack iterator.

658DataFlowGraph::DefStack::Iterator::Iterator(constDataFlowGraph::DefStack &S,

659bool Top)

660 : DS(S) {

661if (!Top) {

662// Initialize to bottom.

663 Pos = 0;

664return;

665 }

666// Initialize to the top, i.e. top-most non-delimiter (or 0, if empty).

667 Pos = DS.Stack.size();

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

669 Pos--;

670}

671

672// Return the size of the stack, including block delimiters.

673unsignedDataFlowGraph::DefStack::size() const{

674unsigned S = 0;

675for (autoI =top(),E =bottom();I !=E;I.down())

676 S++;

677return S;

678}

679

680// Remove the top entry from the stack. Remove all intervening delimiters

681// so that after this, the stack is either empty, or the top of the stack

682// is a non-delimiter.

683voidDataFlowGraph::DefStack::pop() {

684assert(!empty());

685unsignedP = nextDown(Stack.size());

686 Stack.resize(P);

687}

688

689// Push a delimiter for block node N on the stack.

690voidDataFlowGraph::DefStack::start_block(NodeId N) {

691assert(N != 0);

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

693}

694

695// Remove all nodes from the top of the stack, until the delimited for

696// block node N is encountered. Remove the delimiter as well. In effect,

697// this will remove from the stack all definitions from block N.

698voidDataFlowGraph::DefStack::clear_block(NodeId N) {

699assert(N != 0);

700unsignedP = Stack.size();

701while (P > 0) {

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

703P--;

704if (Found)

705break;

706 }

707// This will also remove the delimiter, if found.

708 Stack.resize(P);

709}

710

711// Move the stack iterator up by one.

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

713// Get the next valid position after P (skipping all delimiters).

714// The input position P does not have to point to a non-delimiter.

715unsigned SS = Stack.size();

716bool IsDelim;

717assert(P < SS);

718do {

719P++;

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

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

722assert(!IsDelim);

723returnP;

724}

725

726// Move the stack iterator down by one.

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

728// Get the preceding valid position before P (skipping all delimiters).

729// The input position P does not have to point to a non-delimiter.

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

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

732do {

733if (--P == 0)

734break;

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

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

737assert(!IsDelim);

738returnP;

739}

740

741// Register information.

742

743RegisterAggr DataFlowGraph::getLandingPadLiveIns() const{

744 RegisterAggr LR(getPRI());

745constFunction &F = MF.getFunction();

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

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

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

749 LR.insert(RegisterRef(R));

750if (!isFuncletEHPersonality(classifyEHPersonality(PF))) {

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

752 LR.insert(RegisterRef(R));

753 }

754return LR;

755}

756

757// Node management functions.

758

759// Get the pointer to the node with the id N.

760NodeBase *DataFlowGraph::ptr(NodeId N) const{

761if (N == 0)

762returnnullptr;

763returnMemory.ptr(N);

764}

765

766// Get the id of the node at the address P.

767NodeId DataFlowGraph::id(constNodeBase *P) const{

768if (P ==nullptr)

769return 0;

770returnMemory.id(P);

771}

772

773// Allocate a new node and set the attributes to Attrs.

774Node DataFlowGraph::newNode(uint16_t Attrs) {

775Node P =Memory.New();

776P.Addr->init();

777P.Addr->setAttrs(Attrs);

778returnP;

779}

780

781// Make a copy of the given node B, except for the data-flow links, which

782// are set to 0.

783Node DataFlowGraph::cloneNode(constNode B) {

784Node NA = newNode(0);

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

786// Ref nodes need to have the data-flow links reset.

787if (NA.Addr->getType() ==NodeAttrs::Ref) {

788Ref RA = NA;

789RA.Addr->setReachingDef(0);

790RA.Addr->setSibling(0);

791if (NA.Addr->getKind() ==NodeAttrs::Def) {

792Def DA = NA;

793 DA.Addr->setReachedDef(0);

794 DA.Addr->setReachedUse(0);

795 }

796 }

797return NA;

798}

799

800// Allocation routines for specific node types/kinds.

801

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

803Use UA = newNode(NodeAttrs::Ref |NodeAttrs::Use | Flags);

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

805return UA;

806}

807

808PhiUse DataFlowGraph::newPhiUse(Phi Owner, RegisterRef RR,Block PredB,

809uint16_t Flags) {

810PhiUse PUA = newNode(NodeAttrs::Ref |NodeAttrs::Use | Flags);

811assert(Flags &NodeAttrs::PhiRef);

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

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

814return PUA;

815}

816

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

818Def DA = newNode(NodeAttrs::Ref |NodeAttrs::Def | Flags);

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

820returnDA;

821}

822

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

824Def DA = newNode(NodeAttrs::Ref |NodeAttrs::Def | Flags);

825assert(Flags &NodeAttrs::PhiRef);

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

827returnDA;

828}

829

830Phi DataFlowGraph::newPhi(Block Owner) {

831Phi PA = newNode(NodeAttrs::Code |NodeAttrs::Phi);

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

833return PA;

834}

835

836Stmt DataFlowGraph::newStmt(Block Owner, MachineInstr *MI) {

837Stmt SA = newNode(NodeAttrs::Code |NodeAttrs::Stmt);

838 SA.Addr->setCode(MI);

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

840return SA;

841}

842

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

844Block BA = newNode(NodeAttrs::Code |NodeAttrs::Block);

845 BA.Addr->setCode(BB);

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

847return BA;

848}

849

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

851Func FA = newNode(NodeAttrs::Code |NodeAttrs::Func);

852 FA.Addr->setCode(MF);

853return FA;

854}

855

856// Build the data flow graph.

857voidDataFlowGraph::build(constConfig &config) {

858 reset();

859 BuildCfg = config;

860MachineRegisterInfo &MRI = MF.getRegInfo();

861 ReservedRegs =MRI.getReservedRegs();

862bool SkipReserved = BuildCfg.Options &BuildOptions::OmitReserved;

863

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

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

866 };

867

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

869 std::set<RegisterId> BaseSet;

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

871// Insert every register.

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

873 BaseSet.insert(R);

874 }else {

875for (constTargetRegisterClass *RC : BuildCfg.Classes) {

876for (MCPhysReg R : *RC)

877 BaseSet.insert(R);

878 }

879 }

880for (RegisterId R : BaseSet) {

881if (SkipReserved && ReservedRegs[R])

882continue;

883 Insert(TrackedUnits,getPRI().getUnits(RegisterRef(R)));

884 }

885 }else {

886// Track set in Config overrides everything.

887for (unsigned R : BuildCfg.TrackRegs) {

888if (SkipReserved && ReservedRegs[R])

889continue;

890 Insert(TrackedUnits,getPRI().getUnits(RegisterRef(R)));

891 }

892 }

893

894 TheFunc = newFunc(&MF);

895

896if (MF.empty())

897return;

898

899for (MachineBasicBlock &B : MF) {

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

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

902for (MachineInstr &I :B) {

903if (I.isDebugInstr())

904continue;

905 buildStmt(BA,I);

906 }

907 }

908

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

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

911

912// Collect function live-ins and entry block live-ins.

913MachineBasicBlock &EntryB = *EA.Addr->getCode();

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

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

916 LiveIns.insert(RegisterRef(P.first));

917if (MRI.tracksLiveness()) {

918for (autoI : EntryB.liveins())

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

920 }

921

922// Add function-entry phi nodes for the live-in registers.

923for (RegisterRef RR : LiveIns.refs()) {

924if (RR.isReg() && !isTracked(RR))// isReg is likely guaranteed

925continue;

926Phi PA = newPhi(EA);

927uint16_t PhiFlags =NodeAttrs::PhiRef |NodeAttrs::Preserving;

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

929 PA.Addr->addMember(DA, *this);

930 }

931

932// Add phis for landing pads.

933// Landing pads, unlike usual backs blocks, are not entered through

934// branches in the program, or fall-throughs from other blocks. They

935// are entered from the exception handling runtime and target's ABI

936// may define certain registers as defined on entry to such a block.

937RegisterAggr EHRegs = getLandingPadLiveIns();

938if (!EHRegs.empty()) {

939for (Block BA :Blocks) {

940constMachineBasicBlock &B = *BA.Addr->getCode();

941if (!B.isEHPad())

942continue;

943

944// Prepare a list of NodeIds of the block's predecessors.

945NodeList Preds;

946for (MachineBasicBlock *PB :B.predecessors())

947 Preds.push_back(findBlock(PB));

948

949// Build phi nodes for each live-in.

950for (RegisterRef RR : EHRegs.refs()) {

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

952continue;

953Phi PA = newPhi(BA);

954uint16_t PhiFlags =NodeAttrs::PhiRef |NodeAttrs::Preserving;

955// Add def:

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

957 PA.Addr->addMember(DA, *this);

958// Add uses (no reaching defs for phi uses):

959for (Block PBA : Preds) {

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

961 PA.Addr->addMember(PUA, *this);

962 }

963 }

964 }

965 }

966

967// Build a map "PhiM" which will contain, for each block, the set

968// of references that will require phi definitions in that block.

969BlockRefsMap PhiM(getPRI());

970for (Block BA :Blocks)

971 recordDefsForDF(PhiM, BA);

972for (Block BA :Blocks)

973 buildPhis(PhiM, BA);

974

975// Link all the refs. This will recursively traverse the dominator tree.

976DefStackMap DM;

977 linkBlockRefs(DM, EA);

978

979// Finally, remove all unused phi nodes.

980if (!(BuildCfg.Options &BuildOptions::KeepDeadPhis))

981 removeUnusedPhis();

982}

983

984RegisterRef DataFlowGraph::makeRegRef(unsignedReg,unsigned Sub) const{

985assert(RegisterRef::isRegId(Reg) ||RegisterRef::isMaskId(Reg));

986assert(Reg != 0);

987if (Sub != 0)

988Reg = TRI.getSubReg(Reg, Sub);

989returnRegisterRef(Reg);

990}

991

992RegisterRef DataFlowGraph::makeRegRef(constMachineOperand &Op) const{

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

994if (Op.isReg())

995returnmakeRegRef(Op.getReg(),Op.getSubReg());

996returnRegisterRef(getPRI().getRegMaskId(Op.getRegMask()),

997LaneBitmask::getAll());

998}

999

1000// For each stack in the map DefM, push the delimiter for block B on it.

1001voidDataFlowGraph::markBlock(NodeId B,DefStackMap &DefM) {

1002// Push block delimiters.

1003for (auto &P : DefM)

1004P.second.start_block(B);

1005}

1006

1007// Remove all definitions coming from block B from each stack in DefM.

1008voidDataFlowGraph::releaseBlock(NodeId B,DefStackMap &DefM) {

1009// Pop all defs from this block from the definition stack. Defs that were

1010// added to the map during the traversal of instructions will not have a

1011// delimiter, but for those, the whole stack will be emptied.

1012for (auto &P : DefM)

1013P.second.clear_block(B);

1014

1015// Finally, remove empty stacks from the map.

1016for (autoI = DefM.begin(),E = DefM.end(), NextI =I;I !=E;I = NextI) {

1017 NextI = std::next(I);

1018// This preserves the validity of iterators other than I.

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

1020 DefM.erase(I);

1021 }

1022}

1023

1024// Push all definitions from the instruction node IA to an appropriate

1025// stack in DefM.

1026voidDataFlowGraph::pushAllDefs(Instr IA,DefStackMap &DefM) {

1027 pushClobbers(IA, DefM);

1028 pushDefs(IA, DefM);

1029}

1030

1031// Push all definitions from the instruction node IA to an appropriate

1032// stack in DefM.

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

1034NodeSet Visited;

1035 std::set<RegisterId> Defined;

1036

1037// The important objectives of this function are:

1038// - to be able to handle instructions both while the graph is being

1039// constructed, and after the graph has been constructed, and

1040// - maintain proper ordering of definitions on the stack for each

1041// register reference:

1042// - if there are two or more related defs in IA (i.e. coming from

1043// the same machine operand), then only push one def on the stack,

1044// - if there are multiple unrelated defs of non-overlapping

1045// subregisters of S, then the stack for S will have both (in an

1046// unspecified order), but the order does not matter from the data-

1047// -flow perspective.

1048

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

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

1051continue;

1052if (!(DA.Addr->getFlags() &NodeAttrs::Clobbering))

1053continue;

1054

1055NodeList Rel =getRelatedRefs(IA, DA);

1056Def PDA = Rel.front();

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

1058

1059// Push the definition on the stack for the register and all aliases.

1060// The def stack traversal in linkNodeUp will check the exact aliasing.

1061 DefM[RR.Reg].push(DA);

1062 Defined.insert(RR.Reg);

1063for (RegisterId A :getPRI().getAliasSet(RR.Reg)) {

1064if (RegisterRef::isRegId(A) && !isTracked(RegisterRef(A)))

1065continue;

1066// Check that we don't push the same def twice.

1067assert(A != RR.Reg);

1068if (!Defined.count(A))

1069 DefM[A].push(DA);

1070 }

1071// Mark all the related defs as visited.

1072for (Node T : Rel)

1073 Visited.insert(T.Id);

1074 }

1075}

1076

1077// Push all definitions from the instruction node IA to an appropriate

1078// stack in DefM.

1079void DataFlowGraph::pushDefs(Instr IA,DefStackMap &DefM) {

1080NodeSet Visited;

1081#ifndef NDEBUG

1082 std::set<RegisterId> Defined;

1083#endif

1084

1085// The important objectives of this function are:

1086// - to be able to handle instructions both while the graph is being

1087// constructed, and after the graph has been constructed, and

1088// - maintain proper ordering of definitions on the stack for each

1089// register reference:

1090// - if there are two or more related defs in IA (i.e. coming from

1091// the same machine operand), then only push one def on the stack,

1092// - if there are multiple unrelated defs of non-overlapping

1093// subregisters of S, then the stack for S will have both (in an

1094// unspecified order), but the order does not matter from the data-

1095// -flow perspective.

1096

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

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

1099continue;

1100if (DA.Addr->getFlags() &NodeAttrs::Clobbering)

1101continue;

1102

1103NodeList Rel =getRelatedRefs(IA, DA);

1104Def PDA = Rel.front();

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

1106#ifndef NDEBUG

1107// Assert if the register is defined in two or more unrelated defs.

1108// This could happen if there are two or more def operands defining it.

1109if (!Defined.insert(RR.Reg).second) {

1110 MachineInstr *MI =Stmt(IA).Addr->getCode();

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

1112 <<" in\n " << *MI <<"in " <<printMBBReference(*MI->getParent())

1113 <<'\n';

1114llvm_unreachable(nullptr);

1115 }

1116#endif

1117// Push the definition on the stack for the register and all aliases.

1118// The def stack traversal in linkNodeUp will check the exact aliasing.

1119 DefM[RR.Reg].push(DA);

1120for (RegisterId A :getPRI().getAliasSet(RR.Reg)) {

1121if (RegisterRef::isRegId(A) && !isTracked(RegisterRef(A)))

1122continue;

1123// Check that we don't push the same def twice.

1124assert(A != RR.Reg);

1125 DefM[A].push(DA);

1126 }

1127// Mark all the related defs as visited.

1128for (Node T : Rel)

1129 Visited.insert(T.Id);

1130 }

1131}

1132

1133// Return the list of all reference nodes related to RA, including RA itself.

1134// See "getNextRelated" for the meaning of a "related reference".

1135NodeList DataFlowGraph::getRelatedRefs(Instr IA,Ref RA) const{

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

1137

1138NodeList Refs;

1139NodeId Start =RA.Id;

1140do {

1141 Refs.push_back(RA);

1142RA =getNextRelated(IA,RA);

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

1144return Refs;

1145}

1146

1147// Clear all information in the graph.

1148void DataFlowGraph::reset() {

1149Memory.clear();

1150 BlockNodes.clear();

1151 TrackedUnits.clear();

1152 ReservedRegs.clear();

1153 TheFunc =Func();

1154}

1155

1156// Return the next reference node in the instruction node IA that is related

1157// to RA. Conceptually, two reference nodes are related if they refer to the

1158// same instance of a register access, but differ in flags or other minor

1159// characteristics. Specific examples of related nodes are shadow reference

1160// nodes.

1161// Return the equivalent of nullptr if there are no more related references.

1162Ref DataFlowGraph::getNextRelated(Instr IA,Ref RA) const{

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

1164

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

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

1167returnfalse;

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

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

1170returnfalse;

1171 }

1172returntrue;

1173 };

1174

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

1176if (IA.Addr->getKind() ==NodeAttrs::Stmt) {

1177autoCond = [&IsRelated,RA](Ref TA) ->bool {

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

1179 };

1180returnRA.Addr->getNextRef(RR,Cond,true, *this);

1181 }

1182

1183assert(IA.Addr->getKind() ==NodeAttrs::Phi);

1184autoCond = [&IsRelated,RA](Ref TA) ->bool {

1185if (!IsRelated(TA))

1186returnfalse;

1187if (TA.Addr->getKind() !=NodeAttrs::Use)

1188returntrue;

1189// For phi uses, compare predecessor blocks.

1190returnPhiUse(TA).Addr->getPredecessor() ==

1191PhiUse(RA).Addr->getPredecessor();

1192 };

1193returnRA.Addr->getNextRef(RR,Cond,true, *this);

1194}

1195

1196// Find the next node related to RA in IA that satisfies condition P.

1197// If such a node was found, return a pair where the second element is the

1198// located node. If such a node does not exist, return a pair where the

1199// first element is the element after which such a node should be inserted,

1200// and the second element is a null-address.

1201template <typename Predicate>

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

1203Predicate P) const{

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

1205

1206Ref NA;

1207NodeId Start =RA.Id;

1208while (true) {

1209 NA =getNextRelated(IA,RA);

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

1211break;

1212if (P(NA))

1213break;

1214RA = NA;

1215 }

1216

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

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

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

1220}

1221

1222// Get the next shadow node in IA corresponding to RA, and optionally create

1223// such a node if it does not exist.

1224Ref DataFlowGraph::getNextShadow(Instr IA,Ref RA,bool Create) {

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

1226

1227uint16_t Flags =RA.Addr->getFlags() |NodeAttrs::Shadow;

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

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

1230 };

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

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

1233return Loc.second;

1234

1235// Create a copy of RA and mark is as shadow.

1236Ref NA = cloneNode(RA);

1237 NA.Addr->setFlags(Flags |NodeAttrs::Shadow);

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

1239return NA;

1240}

1241

1242// Create a new statement node in the block node BA that corresponds to

1243// the machine instruction MI.

1244void DataFlowGraph::buildStmt(Block BA,MachineInstr &In) {

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

1246

1247auto isCall = [](constMachineInstr &In) ->bool {

1248if (In.isCall())

1249returntrue;

1250// Is tail call?

1251if (In.isBranch()) {

1252for (constMachineOperand &Op : In.operands())

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

1254returntrue;

1255// Assume indirect branches are calls. This is for the purpose of

1256// keeping implicit operands, and so it won't hurt on intra-function

1257// indirect branches.

1258if (In.isIndirectBranch())

1259returntrue;

1260 }

1261returnfalse;

1262 };

1263

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

1265// This instruction defines DR. Check if there is a use operand that

1266// would make DR live on entry to the instruction.

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

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

1269continue;

1270 RegisterRef UR =makeRegRef(Op);

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

1272returnfalse;

1273 }

1274returntrue;

1275 };

1276

1277bool IsCall = isCall(In);

1278unsigned NumOps =In.getNumOperands();

1279

1280// Avoid duplicate implicit defs. This will not detect cases of implicit

1281// defs that define registers that overlap, but it is not clear how to

1282// interpret that in the absence of explicit defs. Overlapping explicit

1283// defs are likely illegal already.

1284 BitVector DoneDefs(TRI.getNumRegs());

1285// Process explicit defs first.

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

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

1288if (!Op.isReg() || !Op.isDef() ||Op.isImplicit())

1289continue;

1290Register R =Op.getReg();

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

1292continue;

1293uint16_t Flags =NodeAttrs::None;

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

1295Flags |=NodeAttrs::Preserving;

1296// If the def is preserving, check if it is also undefined.

1297if (isDefUndef(In,makeRegRef(Op)))

1298Flags |=NodeAttrs::Undef;

1299 }

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

1301Flags |=NodeAttrs::Clobbering;

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

1303Flags |=NodeAttrs::Fixed;

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

1305Flags |=NodeAttrs::Dead;

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

1307 SA.Addr->addMember(DA, *this);

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

1309 DoneDefs.set(R);

1310 }

1311

1312// Process reg-masks (as clobbers).

1313 BitVector DoneClobbers(TRI.getNumRegs());

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

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

1316if (!Op.isRegMask())

1317continue;

1318uint16_t Flags =NodeAttrs::Clobbering |NodeAttrs::Fixed |NodeAttrs::Dead;

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

1320 SA.Addr->addMember(DA, *this);

1321// Record all clobbered registers in DoneDefs.

1322constuint32_t *RM =Op.getRegMask();

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

1324if (!isTracked(RegisterRef(i)))

1325continue;

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

1327 DoneClobbers.set(i);

1328 }

1329 }

1330

1331// Process implicit defs, skipping those that have already been added

1332// as explicit.

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

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

1335if (!Op.isReg() || !Op.isDef() || !Op.isImplicit())

1336continue;

1337Register R =Op.getReg();

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

1339continue;

1340 RegisterRef RR =makeRegRef(Op);

1341uint16_t Flags =NodeAttrs::None;

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

1343Flags |=NodeAttrs::Preserving;

1344// If the def is preserving, check if it is also undefined.

1345if (isDefUndef(In, RR))

1346Flags |=NodeAttrs::Undef;

1347 }

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

1349Flags |=NodeAttrs::Clobbering;

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

1351Flags |=NodeAttrs::Fixed;

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

1353if (DoneClobbers.test(R))

1354continue;

1355Flags |=NodeAttrs::Dead;

1356 }

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

1358 SA.Addr->addMember(DA, *this);

1359 DoneDefs.set(R);

1360 }

1361

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

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

1364if (!Op.isReg() || !Op.isUse())

1365continue;

1366Register R =Op.getReg();

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

1368continue;

1369uint16_t Flags =NodeAttrs::None;

1370if (Op.isUndef())

1371Flags |=NodeAttrs::Undef;

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

1373Flags |=NodeAttrs::Fixed;

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

1375 SA.Addr->addMember(UA, *this);

1376 }

1377}

1378

1379// Scan all defs in the block node BA and record in PhiM the locations of

1380// phi nodes corresponding to these defs.

1381void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM,Block BA) {

1382// Check all defs from block BA and record them in each block in BA's

1383// iterated dominance frontier. This information will later be used to

1384// create phi nodes.

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

1386assert(BB);

1387auto DFLoc = MDF.find(BB);

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

1389return;

1390

1391// Traverse all instructions in the block and collect the set of all

1392// defined references. For each reference there will be a phi created

1393// in the block's iterated dominance frontier.

1394// This is done to make sure that each defined reference gets only one

1395// phi node, even if it is defined multiple times.

1396 RegisterAggr Defs(getPRI());

1397for (Instr IA : BA.Addr->members(*this)) {

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

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

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

1401 Defs.insert(RR);

1402 }

1403 }

1404

1405// Calculate the iterated dominance frontier of BB.

1406constMachineDominanceFrontier::DomSetType &DF = DFLoc->second;

1407 SetVector<MachineBasicBlock *> IDF(DF.begin(),DF.end());

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

1409autoF = MDF.find(IDF[i]);

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

1411 IDF.insert(F->second.begin(),F->second.end());

1412 }

1413

1414// Finally, add the set of defs to each block in the iterated dominance

1415// frontier.

1416for (auto *DB : IDF) {

1417Block DBA =findBlock(DB);

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

1419 }

1420}

1421

1422// Given the locations of phi nodes in the map PhiM, create the phi nodes

1423// that are located in the block node BA.

1424void DataFlowGraph::buildPhis(BlockRefsMap &PhiM,Block BA) {

1425// Check if this blocks has any DF defs, i.e. if there are any defs

1426// that this block is in the iterated dominance frontier of.

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

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

1429return;

1430

1431// Prepare a list of NodeIds of the block's predecessors.

1432NodeList Preds;

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

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

1435 Preds.push_back(findBlock(PB));

1436

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

1438uint16_t PhiFlags =NodeAttrs::PhiRef |NodeAttrs::Preserving;

1439

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

1441Phi PA = newPhi(BA);

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

1443

1444// Add phi uses.

1445for (Block PBA : Preds) {

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

1447 }

1448 }

1449}

1450

1451// Remove any unneeded phi nodes that were created during the build process.

1452void DataFlowGraph::removeUnusedPhis() {

1453// This will remove unused phis, i.e. phis where each def does not reach

1454// any uses or other defs. This will not detect or remove circular phi

1455// chains that are otherwise dead. Unused/dead phis are created during

1456// the build process and this function is intended to remove these cases

1457// that are easily determinable to be unnecessary.

1458

1459 SetVector<NodeId> PhiQ;

1460for (Block BA : TheFunc.Addr->members(*this)) {

1461for (autoP : BA.Addr->members_if(IsPhi, *this))

1462 PhiQ.insert(P.Id);

1463 }

1464

1465staticauto HasUsedDef = [](NodeList &Ms) ->bool {

1466for (Node M : Ms) {

1467if (M.Addr->getKind() !=NodeAttrs::Def)

1468continue;

1469Def DA =M;

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

1471returntrue;

1472 }

1473returnfalse;

1474 };

1475

1476// Any phi, if it is removed, may affect other phis (make them dead).

1477// For each removed phi, collect the potentially affected phis and add

1478// them back to the queue.

1479while (!PhiQ.empty()) {

1480auto PA = addr<PhiNode *>(PhiQ[0]);

1481 PhiQ.remove(PA.Id);

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

1483if (HasUsedDef(Refs))

1484continue;

1485for (Ref RA : Refs) {

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

1487autoRDA = addr<DefNode *>(RD);

1488Instr OA =RDA.Addr->getOwner(*this);

1489if (IsPhi(OA))

1490 PhiQ.insert(OA.Id);

1491 }

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

1493unlinkDef(RA,true);

1494else

1495unlinkUse(RA,true);

1496 }

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

1498 BA.Addr->removeMember(PA, *this);

1499 }

1500}

1501

1502// For a given reference node TA in an instruction node IA, connect the

1503// reaching def of TA to the appropriate def node. Create any shadow nodes

1504// as appropriate.

1505template <typename T>

1506void DataFlowGraph::linkRefUp(Instr IA, NodeAddr<T> TA, DefStack &DS) {

1507if (DS.empty())

1508return;

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

1510 NodeAddr<T> TAP;

1511

1512// References from the def stack that have been examined so far.

1513 RegisterAggr Defs(getPRI());

1514

1515for (autoI =DS.top(),E =DS.bottom();I !=E;I.down()) {

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

1517

1518// Skip all defs that we have already seen.

1519// If this completes a cover of RR, stop the stack traversal.

1520bool Seen = Defs.hasCoverOf(QR);

1521if (Seen)

1522continue;

1523

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

1525

1526// The reaching def.

1527Def RDA = *I;

1528

1529// Pick the reached node.

1530if (TAP.Id == 0) {

1531 TAP =TA;

1532 }else {

1533// Mark the existing ref as "shadow" and create a new shadow.

1534 TAP.Addr->setFlags(TAP.Addr->getFlags() |NodeAttrs::Shadow);

1535 TAP =getNextShadow(IA, TAP,true);

1536 }

1537

1538// Create the link.

1539 TAP.Addr->linkToDef(TAP.Id,RDA);

1540

1541if (Cover)

1542break;

1543 }

1544}

1545

1546// Create data-flow links for all reference nodes in the statement node SA.

1547template <typename Predicate>

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

1549#ifndef NDEBUG

1550RegisterSet Defs(getPRI());

1551#endif

1552

1553// Link all nodes (upwards in the data-flow) with their reaching defs.

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

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

1556assert(Kind ==NodeAttrs::Def || Kind ==NodeAttrs::Use);

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

1558#ifndef NDEBUG

1559// Do not expect multiple defs of the same reference.

1560assert(Kind !=NodeAttrs::Def || !Defs.count(RR));

1561 Defs.insert(RR);

1562#endif

1563

1564autoF = DefM.find(RR.Reg);

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

1566continue;

1567 DefStack &DS =F->second;

1568if (Kind ==NodeAttrs::Use)

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

1570elseif (Kind ==NodeAttrs::Def)

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

1572else

1573llvm_unreachable("Unexpected node in instruction");

1574 }

1575}

1576

1577// Create data-flow links for all instructions in the block node BA. This

1578// will include updating any phi nodes in BA.

1579void DataFlowGraph::linkBlockRefs(DefStackMap &DefM,Block BA) {

1580// Push block delimiters.

1581markBlock(BA.Id, DefM);

1582

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

1584returnIsDef(RA) && (RA.Addr->getFlags() &NodeAttrs::Clobbering);

1585 };

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

1587returnIsDef(RA) && !(RA.Addr->getFlags() &NodeAttrs::Clobbering);

1588 };

1589

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

1591// For each non-phi instruction in the block, link all the defs and uses

1592// to their reaching defs. For any member of the block (including phis),

1593// push the defs on the corresponding stacks.

1594for (Instr IA : BA.Addr->members(*this)) {

1595// Ignore phi nodes here. They will be linked part by part from the

1596// predecessors.

1597if (IA.Addr->getKind() ==NodeAttrs::Stmt) {

1598 linkStmtRefs(DefM, IA,IsUse);

1599 linkStmtRefs(DefM, IA, IsClobber);

1600 }

1601

1602// Push the definitions on the stack.

1603 pushClobbers(IA, DefM);

1604

1605if (IA.Addr->getKind() ==NodeAttrs::Stmt)

1606 linkStmtRefs(DefM, IA, IsNoClobber);

1607

1608 pushDefs(IA, DefM);

1609 }

1610

1611// Recursively process all children in the dominator tree.

1612MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode());

1613for (auto *I : *N) {

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

1615Block SBA =findBlock(SB);

1616 linkBlockRefs(DefM, SBA);

1617 }

1618

1619// Link the phi uses from the successor blocks.

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

1621if (NA.Addr->getKind() !=NodeAttrs::Use)

1622returnfalse;

1623assert(NA.Addr->getFlags() &NodeAttrs::PhiRef);

1624returnPhiUse(NA).Addr->getPredecessor() == BA.Id;

1625 };

1626

1627 RegisterAggr EHLiveIns = getLandingPadLiveIns();

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

1629

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

1631bool IsEHPad = SB->isEHPad();

1632Block SBA =findBlock(SB);

1633for (Instr IA : SBA.Addr->members_if(IsPhi, *this)) {

1634// Do not link phi uses for landing pad live-ins.

1635if (IsEHPad) {

1636// Find what register this phi is for.

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

1638assert(RA.Id != 0);

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

1640continue;

1641 }

1642// Go over each phi use associated with MBB, and link it.

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

1644PhiUse PUA =U;

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

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

1647 }

1648 }

1649 }

1650

1651// Pop all defs from this block from the definition stacks.

1652releaseBlock(BA.Id, DefM);

1653}

1654

1655// Remove the use node UA from any data-flow and structural links.

1656void DataFlowGraph::unlinkUseDF(Use UA) {

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

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

1659

1660if (RD == 0) {

1661assert(Sib == 0);

1662return;

1663 }

1664

1665autoRDA = addr<DefNode *>(RD);

1666autoTA = addr<UseNode *>(RDA.Addr->getReachedUse());

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

1668RDA.Addr->setReachedUse(Sib);

1669return;

1670 }

1671

1672while (TA.Id != 0) {

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

1674if (S == UA.Id) {

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

1676return;

1677 }

1678TA = addr<UseNode *>(S);

1679 }

1680}

1681

1682// Remove the def node DA from any data-flow and structural links.

1683void DataFlowGraph::unlinkDefDF(Def DA) {

1684//

1685// RD

1686// | reached

1687// | def

1688// :

1689// .

1690// +----+

1691// ... -- | DA | -- ... -- 0 : sibling chain of DA

1692// +----+

1693// | | reached

1694// | : def

1695// | .

1696// | ... : Siblings (defs)

1697// |

1698// : reached

1699// . use

1700// ... : sibling chain of reached uses

1701

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

1703

1704// Visit all siblings of the reached def and reset their reaching defs.

1705// Also, defs reached by DA are now "promoted" to being reached by RD,

1706// so all of them will need to be spliced into the sibling chain where

1707// DA belongs.

1708auto getAllNodes = [this](NodeId N) ->NodeList {

1709NodeList Res;

1710while (N) {

1711autoRA = addr<RefNode *>(N);

1712// Keep the nodes in the exact sibling order.

1713 Res.push_back(RA);

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

1715 }

1716return Res;

1717 };

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

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

1720

1721if (RD == 0) {

1722for (Ref I : ReachedDefs)

1723I.Addr->setSibling(0);

1724for (Ref I : ReachedUses)

1725I.Addr->setSibling(0);

1726 }

1727for (Def I : ReachedDefs)

1728I.Addr->setReachingDef(RD);

1729for (Use I : ReachedUses)

1730I.Addr->setReachingDef(RD);

1731

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

1733if (RD == 0) {

1734assert(Sib == 0);

1735return;

1736 }

1737

1738// Update the reaching def node and remove DA from the sibling list.

1739autoRDA = addr<DefNode *>(RD);

1740autoTA = addr<DefNode *>(RDA.Addr->getReachedDef());

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

1742// If DA is the first reached def, just update the RD's reached def

1743// to the DA's sibling.

1744RDA.Addr->setReachedDef(Sib);

1745 }else {

1746// Otherwise, traverse the sibling list of the reached defs and remove

1747// DA from it.

1748while (TA.Id != 0) {

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

1750if (S ==DA.Id) {

1751TA.Addr->setSibling(Sib);

1752break;

1753 }

1754TA = addr<DefNode *>(S);

1755 }

1756 }

1757

1758// Splice the DA's reached defs into the RDA's reached def chain.

1759if (!ReachedDefs.empty()) {

1760autoLast =Def(ReachedDefs.back());

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

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

1763 }

1764// Splice the DA's reached uses into the RDA's reached use chain.

1765if (!ReachedUses.empty()) {

1766autoLast =Use(ReachedUses.back());

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

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

1769 }

1770}

1771

1772boolDataFlowGraph::isTracked(RegisterRef RR) const{

1773return !disjoint(getPRI().getUnits(RR), TrackedUnits);

1774}

1775

1776boolDataFlowGraph::hasUntrackedRef(Stmt S,bool IgnoreReserved) const{

1777SmallVector<MachineOperand *> Ops;

1778

1779for (Ref R : S.Addr->members(*this)) {

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

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

1782if (IgnoreReserved && RR.isReg() && ReservedRegs[RR.idx()])

1783continue;

1784if (!isTracked(RR))

1785returntrue;

1786 }

1787for (constMachineOperand &Op : S.Addr->getCode()->operands()) {

1788if (!Op.isReg() && !Op.isRegMask())

1789continue;

1790if (!llvm::is_contained(Ops, &Op))

1791returntrue;

1792 }

1793returnfalse;

1794}

1795

1796}// end namespace llvm::rdf

MRI

unsigned const MachineRegisterInfo * MRI

Definition:AArch64AdvSIMDScalarPass.cpp:105

RDA

ReachingDefAnalysis & RDA

Definition:ARMLowOverheadLoops.cpp:530

MBB

MachineBasicBlock & MBB

Definition:ARMSLSHardening.cpp:71

BitVector.h

This file implements the BitVector class.

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

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")

Idx

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

Definition:DeadArgumentElimination.cpp:353

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

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

Index

uint32_t Index

Definition:ELFObjHandler.cpp:83

Blocks

DenseMap< Block *, BlockRelaxAux > Blocks

Definition:ELF_riscv.cpp:507

TII

const HexagonInstrInfo * TII

Definition:HexagonCopyToCombine.cpp:125

IRTranslator LLVM IR MI

Definition:IRTranslator.cpp:112

Function.h

InlinePriorityMode::ML

@ ML

LaneBitmask.h

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

MCInstrDesc.h

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

#define G(x, y, z)

Definition:MD5.cpp:56

MachineBasicBlock.h

MachineDominanceFrontier.h

MachineRegisterInfo.h

TRI

unsigned const TargetRegisterInfo * TRI

Definition:MachineSink.cpp:2029

Reg

unsigned Reg

Definition:MachineSink.cpp:2028

#define T

Definition:Mips16ISelLowering.cpp:341

Range

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

#define P(N)

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

List

const NodeList & List

Definition:RDFGraph.cpp:200

RDFGraph.h

RDFRegisters.h

Cond

const SmallVectorImpl< MachineOperand > & Cond

Definition:RISCVRedundantCopyElimination.cpp:75

assert

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

SI optimize exec mask operations pre RA

Definition:SIOptimizeExecMaskingPreRA.cpp:71

STLExtras.h

This file contains some templates that are useful if you are working with the STL at all.

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

SetVector.h

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

TargetInstrInfo.h

TargetLowering.h

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

TargetRegisterInfo.h

TargetSubtargetInfo.h

Node

Definition:ItaniumDemangle.h:163

Node::getKind

Kind getKind() const

Definition:ItaniumDemangle.h:255

Predicate

Definition:AMDGPURegBankLegalizeRules.cpp:332

llvm::ArrayRef

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

Definition:ArrayRef.h:41

llvm::BitVector::clear

void clear()

clear - Removes all bits from the bitvector.

Definition:BitVector.h:335

llvm::BumpPtrAllocatorImpl::Allocate

LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)

Allocate space at the specified alignment.

Definition:Allocator.h:148

llvm::BumpPtrAllocatorImpl::Reset

void Reset()

Deallocate all but the current slab and reset the current pointer to the beginning of it,...

Definition:Allocator.h:123

llvm::DWARFExpression::Operation

This class represents an Operation in the Expression.

Definition:DWARFExpression.h:32

llvm::DominatorTreeBase::getNode

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

Definition:GenericDomTree.h:401

llvm::MCInstrDesc

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

Definition:MCInstrDesc.h:198

llvm::MCRegisterInfo::getNumRegs

unsigned getNumRegs() const

Return the number of registers this target has (useful for sizing arrays holding per register informa...

Definition:MCRegisterInfo.h:414

llvm::MachineBasicBlock

Definition:MachineBasicBlock.h:125

llvm::MachineBasicBlock::pred_size

unsigned pred_size() const

Definition:MachineBasicBlock.h:417

llvm::MachineBasicBlock::liveins

iterator_range< livein_iterator > liveins() const

Definition:MachineBasicBlock.h:505

llvm::MachineBasicBlock::succ_size

unsigned succ_size() const

Definition:MachineBasicBlock.h:433

llvm::MachineBasicBlock::pred_empty

bool pred_empty() const

Definition:MachineBasicBlock.h:420

llvm::MachineBasicBlock::successors

iterator_range< succ_iterator > successors()

Definition:MachineBasicBlock.h:444

llvm::MachineBasicBlock::predecessors

iterator_range< pred_iterator > predecessors()

Definition:MachineBasicBlock.h:438

llvm::MachineDominanceFrontier

Definition:MachineDominanceFrontier.h:20

llvm::MachineDominanceFrontier::find

iterator find(MachineBasicBlock *B)

Definition:MachineDominanceFrontier.h:68

llvm::MachineDominanceFrontier::DomSetType

DominanceFrontierBase< MachineBasicBlock, false >::DomSetType DomSetType

Definition:MachineDominanceFrontier.h:26

llvm::MachineDominanceFrontier::end

iterator end()

Definition:MachineDominanceFrontier.h:60

llvm::MachineDominatorTree

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

Definition:MachineDominators.h:75

llvm::MachineFunction

Definition:MachineFunction.h:267

llvm::MachineFunction::getSubtarget

const TargetSubtargetInfo & getSubtarget() const

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

Definition:MachineFunction.h:733

llvm::MachineFunction::getFunction

Function & getFunction()

Return the LLVM function that this machine code represents.

Definition:MachineFunction.h:704

llvm::MachineFunction::front

const MachineBasicBlock & front() const

Definition:MachineFunction.h:959

llvm::MachineInstr

Representation of each machine instruction.

Definition:MachineInstr.h:71

llvm::MachineOperand

MachineOperand class - Representation of each machine instruction operand.

Definition:MachineOperand.h:48

llvm::MachineRegisterInfo

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

Definition:MachineRegisterInfo.h:51

llvm::Register

Wrapper class representing virtual and physical registers.

Definition:Register.h:19

llvm::SmallVectorBase::empty

bool empty() const

Definition:SmallVector.h:81

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVectorTemplateCommon::front

reference front()

Definition:SmallVector.h:299

llvm::SmallVector

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

Definition:SmallVector.h:1196

llvm::TargetInstrInfo

TargetInstrInfo - Interface to description of machine instruction set.

Definition:TargetInstrInfo.h:112

llvm::TargetInstrInfo::isPredicated

virtual bool isPredicated(const MachineInstr &MI) const

Returns true if the instruction is already predicated.

Definition:TargetInstrInfo.h:1612

llvm::TargetRegisterClass

Definition:TargetRegisterInfo.h:44

llvm::TargetRegisterInfo

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

Definition:TargetRegisterInfo.h:235

llvm::TargetRegisterInfo::getSubReg

MCRegister getSubReg(MCRegister Reg, unsigned Idx) const

Returns the physical register number of sub-register "Index" for physical register RegNo.

Definition:TargetRegisterInfo.h:1217

llvm::TargetSubtargetInfo::getTargetLowering

virtual const TargetLowering * getTargetLowering() const

Definition:TargetSubtargetInfo.h:101

llvm::raw_ostream

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

Definition:raw_ostream.h:52

llvm::sys::Memory

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

Definition:Memory.h:53

#define llvm_unreachable(msg)

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

Definition:ErrorHandling.h:143

llvm::AArch64PACKey::DA

@ DA

Definition:AArch64BaseInfo.h:877

llvm::AArch64PACKey::IA

@ IA

Definition:AArch64BaseInfo.h:875

llvm::AArch64::RM

@ RM

Definition:AArch64ISelLowering.h:542

llvm::ARM::ProfileKind::M

@ M

llvm::ISD::Register

@ Register

Definition:ISDOpcodes.h:74

llvm::ISD::Constant

@ Constant

Definition:ISDOpcodes.h:76

llvm::M68k::MemAddrModeKind::U

@ U

llvm::RISCVFenceField::R

@ R

Definition:RISCVBaseInfo.h:373

llvm::SIInstrFlags::DS

@ DS

Definition:SIDefines.h:88

llvm::X86II::TA

@ TA

Definition:X86BaseInfo.h:738

llvm::codeview::PublicSymFlags::Function

@ Function

llvm::lltok::Kind

Kind

Definition:LLToken.h:18

llvm::omp::RTLDependInfoFields::Flags

@ Flags

llvm::rdf

Definition:RDFGraph.h:260

llvm::rdf::Instr

NodeAddr< InstrNode * > Instr

Definition:RDFGraph.h:389

llvm::rdf::Stmt

NodeAddr< StmtNode * > Stmt

Definition:RDFGraph.h:391

llvm::rdf::Ref

NodeAddr< RefNode * > Ref

Definition:RDFGraph.h:383

llvm::rdf::Phi

NodeAddr< PhiNode * > Phi

Definition:RDFGraph.h:390

llvm::rdf::RegisterSet

std::set< RegisterRef > RegisterSet

Definition:RDFGraph.h:450

llvm::rdf::Print

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

llvm::rdf::PhiUse

NodeAddr< PhiUseNode * > PhiUse

Definition:RDFGraph.h:386

llvm::rdf::Def

NodeAddr< DefNode * > Def

Definition:RDFGraph.h:384

llvm::rdf::NodeId

uint32_t NodeId

Definition:RDFGraph.h:262

llvm::rdf::Func

NodeAddr< FuncNode * > Func

Definition:RDFGraph.h:393

llvm::rdf::Block

NodeAddr< BlockNode * > Block

Definition:RDFGraph.h:392

llvm::rdf::Node

NodeAddr< NodeBase * > Node

Definition:RDFGraph.h:381

llvm::rdf::printRefHeader

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

Definition:RDFGraph.cpp:110

llvm::rdf::operator<<

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

Definition:RDFGraph.cpp:44

llvm::rdf::RegisterId

uint32_t RegisterId

Definition:RDFRegisters.h:32

llvm::rdf::Use

NodeAddr< UseNode * > Use

Definition:RDFGraph.h:385

llvm::rdf::disjoint

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

Definition:RDFRegisters.h:35

llvm::rdf::NodeSet

std::set< NodeId > NodeSet

Definition:RDFGraph.h:551

llvm::tgtok::In

@ In

Definition:TGLexer.h:84

llvm::dbgs

raw_ostream & dbgs()

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

Definition:Debug.cpp:163

llvm::classifyEHPersonality

EHPersonality classifyEHPersonality(const Value *Pers)

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

Definition:EHPersonalities.cpp:23

llvm::isFuncletEHPersonality

bool isFuncletEHPersonality(EHPersonality Pers)

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

Definition:EHPersonalities.h:65

llvm::Op

DWARFExpression::Operation Op

Definition:DWARFExpression.cpp:22

llvm::PseudoProbeReservedId::Last

@ Last

llvm::find_if

auto find_if(R &&Range, UnaryPredicate P)

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

Definition:STLExtras.h:1766

llvm::is_contained

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

Returns true if Element is found in Range.

Definition:STLExtras.h:1903

llvm::MachineDomTreeNode

DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode

Definition:LiveIntervalCalc.h:26

llvm::printMBBReference

Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

Definition:MachineBasicBlock.cpp:122

std

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

Definition:BitVector.h:858

raw_ostream.h

#define N

NodeList

Definition:MicrosoftDemangle.cpp:38

llvm::LaneBitmask::getAll

static constexpr LaneBitmask getAll()

Definition:LaneBitmask.h:82

llvm::rdf::BlockNode::addPhi

void addPhi(Phi PA, const DataFlowGraph &G)

Definition:RDFGraph.cpp:538

llvm::rdf::BuildOptions::OmitReserved

@ OmitReserved

Definition:RDFGraph.h:340

llvm::rdf::BuildOptions::KeepDeadPhis

@ KeepDeadPhis

Definition:RDFGraph.h:339

llvm::rdf::CodeNode::members_if

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

Definition:RDFGraph.h:946

llvm::rdf::CodeNode::removeMember

void removeMember(Node NA, const DataFlowGraph &G)

Definition:RDFGraph.cpp:487

llvm::rdf::CodeNode::members

NodeList members(const DataFlowGraph &G) const

Definition:RDFGraph.cpp:519

llvm::rdf::CodeNode::addMember

void addMember(Node NA, const DataFlowGraph &G)

Definition:RDFGraph.cpp:467

llvm::rdf::CodeNode::getFirstMember

Node getFirstMember(const DataFlowGraph &G) const

Definition:RDFGraph.cpp:453

llvm::rdf::CodeNode::addMemberAfter

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

Definition:RDFGraph.cpp:480

llvm::rdf::CodeNode::getLastMember

Node getLastMember(const DataFlowGraph &G) const

Definition:RDFGraph.cpp:460

llvm::rdf::DataFlowGraph::Config

Definition:RDFGraph.h:669

llvm::rdf::DataFlowGraph::Config::Classes

SmallVector< const TargetRegisterClass * > Classes

Definition:RDFGraph.h:678

llvm::rdf::DataFlowGraph::Config::Options

unsigned Options

Definition:RDFGraph.h:677

llvm::rdf::DataFlowGraph::Config::TrackRegs

std::set< RegisterId > TrackRegs

Definition:RDFGraph.h:679

llvm::rdf::DataFlowGraph::DefStack

Definition:RDFGraph.h:702

llvm::rdf::DataFlowGraph::DefStack::clear_block

void clear_block(NodeId N)

Definition:RDFGraph.cpp:698

llvm::rdf::DataFlowGraph::DefStack::start_block

void start_block(NodeId N)

Definition:RDFGraph.cpp:690

llvm::rdf::DataFlowGraph::DefStack::bottom

iterator bottom() const

Definition:RDFGraph.h:747

llvm::rdf::DataFlowGraph::DefStack::size

unsigned size() const

Definition:RDFGraph.cpp:673

llvm::rdf::DataFlowGraph::DefStack::pop

void pop()

Definition:RDFGraph.cpp:683

llvm::rdf::DataFlowGraph::DefStack::top

iterator top() const

Definition:RDFGraph.h:746

llvm::rdf::DataFlowGraph

Definition:RDFGraph.h:660

llvm::rdf::DataFlowGraph::id

NodeId id(const NodeBase *P) const

Definition:RDFGraph.cpp:767

llvm::rdf::DataFlowGraph::unlinkUse

void unlinkUse(Use UA, bool RemoveFromOwner)

Definition:RDFGraph.h:801

llvm::rdf::DataFlowGraph::releaseBlock

void releaseBlock(NodeId B, DefStackMap &DefM)

Definition:RDFGraph.cpp:1008

llvm::rdf::DataFlowGraph::getNextRelated

Ref getNextRelated(Instr IA, Ref RA) const

Definition:RDFGraph.cpp:1162

llvm::rdf::DataFlowGraph::isTracked

bool isTracked(RegisterRef RR) const

Definition:RDFGraph.cpp:1772

llvm::rdf::DataFlowGraph::makeRegRef

RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const

Definition:RDFGraph.cpp:984

llvm::rdf::DataFlowGraph::IsDef

static bool IsDef(const Node BA)

Definition:RDFGraph.h:825

llvm::rdf::DataFlowGraph::DataFlowGraph

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

Definition:RDFGraph.cpp:636

llvm::rdf::DataFlowGraph::getNextShadow

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

Definition:RDFGraph.cpp:1224

llvm::rdf::DataFlowGraph::IsPhi

static bool IsPhi(const Node BA)

Definition:RDFGraph.h:835

llvm::rdf::DataFlowGraph::getRelatedRefs

NodeList getRelatedRefs(Instr IA, Ref RA) const

Definition:RDFGraph.cpp:1135

llvm::rdf::DataFlowGraph::unlinkDef

void unlinkDef(Def DA, bool RemoveFromOwner)