RDFGraph.h Source File (original) (raw)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224#ifndef LLVM_CODEGEN_RDFGRAPH_H

225#define LLVM_CODEGEN_RDFGRAPH_H

226

233#include

234#include

235#include

236#include

237#include

238#include

239#include <unordered_map>

240#include

241#include

242

243

244

245

246static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal");

247

248namespace llvm {

249

259

261

263

265

267

269 None = 0x0000,

270

271

273 Code = 0x0001,

274 Ref = 0x0002,

275

276

278 Def = 0x0001 << 2,

279 Use = 0x0002 << 2,

280 Phi = 0x0003 << 2,

281 Stmt = 0x0004 << 2,

283 Func = 0x0006 << 2,

284

285

287 Shadow = 0x0001 << 5,

288 Clobbering = 0x0002 << 5,

289 PhiRef = 0x0004 << 5,

290 Preserving = 0x0008 << 5,

291 Fixed = 0x0010 << 5,

292 Undef = 0x0020 << 5,

293 Dead = 0x0040 << 5,

294 };

295

296

309

313

317

318

321 return false;

323 switch (kind(A)) {

325 return KB == Block;

327 return KB == Phi || KB == Stmt;

328 case Phi:

331 }

332 return false;

333 }

334};

335

343

347

348

349

350 template

352

360

363};

364

366

371

378

379

380

382

387

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

412

414

416 : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)),

417 IndexMask((1 << BitsPerIndex) - 1) {

419 }

420

423 uint32_t BlockN = N1 >> BitsPerIndex;

425 return reinterpret_cast<NodeBase *>(Blocks[BlockN] + Offset);

426 }

427

431

432private:

433 void startNewBlock();

434 bool needNewBlock();

435

437

438 return ((Block << BitsPerIndex) | Index) + 1;

439 }

440

441 const uint32_t NodesPerBlock;

444 char *ActiveEnd = nullptr;

445 std::vector<char *> Blocks;

447 AllocatorTy MemPool;

448};

449

450using RegisterSet = std::set<RegisterRef, RegisterRefLess>;

451

462

463

468

471

475

480

483 return LM.all() ? 0 : find(LM);

484 }

485};

486

488public:

489

491

496

500

501

503

504

505 void init() { memset(this, 0, sizeof *this); }

506

508

509protected:

512 NodeId Next;

513

514

515

537

538

539 union {

542 };

543};

544

545

546

548 "NodeBase must be at most NodeAllocator::NodeMemSize bytes");

549

552

555

557

562

565

568

571

576

581

582 template

586};

587

596

600

604 return RefData.PhiU.PredB;

605 }

610};

611

617

623

625 template

627};

628

632

636

642

650

659

668

675 : TrackRegs(Track.begin(), Track.end()) {}

676

680 };

681

684 return static_cast<T>(ptr(N));

685 }

686

688

692

701

704

705 bool empty() const { return Stack.empty() || top() == bottom(); }

706

707 private:

708 using value_type = Def;

710 using value_type = DefStack::value_type;

711

713 Pos = DS.nextUp(Pos);

714 return *this;

715 }

717 Pos = DS.nextDown(Pos);

718 return *this;

719 }

720

723 return DS.Stack[Pos - 1];

724 }

725 const value_type *operator->() const {

727 return &DS.Stack[Pos - 1];

728 }

729 bool operator==(const Iterator &It) const { return Pos == It.Pos; }

730 bool operator!=(const Iterator &It) const { return Pos != It.Pos; }

731

732 private:

733 friend struct DefStack;

734

735 Iterator(const DefStack &S, bool Top);

736

737

738

739 const DefStack &DS;

740 unsigned Pos;

741 };

742

743 public:

745

748 unsigned size() const;

749

750 void push(Def DA) { Stack.push_back(DA); }

751 void pop();

754

755 private:

756 friend struct Iterator;

757

758 using StorageType = std::vector<value_type>;

759

760 bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {

761 return (P.Addr == nullptr) && (N == 0 || P.Id == N);

762 }

763

764 unsigned nextUp(unsigned P) const;

765 unsigned nextDown(unsigned P) const;

766

767 StorageType Stack;

768 };

769

770

771

772 using DefStackMap = std::unordered_map<RegisterId, DefStack>;

773

776

780

782 return {RR.Id, LMI.getIndexForLaneMask(RR.Mask)};

783 }

785 return {RR.Id, LMI.getIndexForLaneMask(RR.Mask)};

786 }

790

793

796

798

800

802 unlinkUseDF(UA);

803 if (RemoveFromOwner)

804 removeFromOwner(UA);

805 }

806

808 unlinkDefDF(DA);

809 if (RemoveFromOwner)

810 removeFromOwner(DA);

811 }

812

815

816

817 template <uint16_t Kind> static bool IsRef(const Node BA) {

819 }

820

821 template <uint16_t Kind> static bool IsCode(const Node BA) {

823 }

824

829

834

839

841 uint16_t Flags = DA.Addr->getFlags();

843 }

844

845private:

846 void reset();

847

849

861

862 template

864

866

868 void recordDefsForDF(BlockRefsMap &PhiM, BlockRefsMap &PhiClobberM, Block BA);

869 void buildPhis(BlockRefsMap &PhiM, Block BA,

871 void removeUnusedPhis();

872

875 template void linkRefUp(Instr IA, NodeAddr TA, DefStack &DS);

876 template

878 void linkBlockRefs(DefStackMap &DefM, BlockRefsMap &PhiClobberM, Block BA);

879

880 void unlinkUseDF(Use UA);

881 void unlinkDefDF(Def DA);

882

883 void removeFromOwner(Ref RA) {

884 Instr IA = RA.Addr->getOwner(*this);

885 IA.Addr->removeMember(RA, *this);

886 }

887

888

889 std::unique_ptr DefaultTOI;

890

894 const PhysicalRegisterInfo PRI;

897 const TargetOperandInfo &TOI;

898

899 RegisterAggr LiveIns;

900 Func TheFunc;

901 NodeAllocator Memory;

902

903 std::map<MachineBasicBlock *, Block> BlockNodes;

904

905 LaneMaskIndex LMI;

906

907 Config BuildCfg;

908 std::set TrackedUnits;

910};

911

912template

915

916

918

919 while (NA.Addr != this) {

922 if (G.getPRI().equal_to(RA.Addr->getRegRef(G), RR) && P(NA))

923 return NA;

924 if (NextOnly)

925 break;

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

927 } else {

928

930

931

932

933

934

935

936 if (NextOnly)

937 break;

938 Code CA = NA;

940 }

941 }

942

943 return Ref();

944}

945

946template

950 if (M.Id == 0)

951 return MM;

952

953 while (M.Addr != this) {

954 if (P(M))

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

957 }

958 return MM;

959}

960

961template struct Print {

963

966};

967

969

974

992

993}

994}

995

996#endif

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

This file defines the BumpPtrAllocator interface.

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< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static ManagedStatic< DebugCounterOwner > Owner

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

const HexagonInstrInfo * TII

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

SI optimize exec mask operations pre RA

This file defines the SmallVector class.

INLINE void g(uint32_t *state, size_t a, size_t b, size_t c, size_t d, uint32_t x, uint32_t y)

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

Allocate memory in an ever growing pool, as if by bump-pointer.

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

Representation of each machine instruction.

MachineOperand class - Representation of each machine instruction operand.

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.

@ C

The default llvm calling convention, compatible with C.

Definition RDFGraph.h:260

NodeAddr< DefNode * > Def

Definition RDFGraph.h:384

NodeAddr< InstrNode * > Instr

Definition RDFGraph.h:389

std::set< RegisterRef, RegisterRefLess > RegisterSet

Definition RDFGraph.h:450

NodeAddr< BlockNode * > Block

Definition RDFGraph.h:392

NodeAddr< PhiNode * > Phi

Definition RDFGraph.h:390

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

NodeAddr< PhiUseNode * > PhiUse

Definition RDFGraph.h:386

NodeAddr< StmtNode * > Stmt

Definition RDFGraph.h:391

uint32_t NodeId

Definition RDFGraph.h:262

NodeAddr< UseNode * > Use

Definition RDFGraph.h:385

NodeAddr< NodeBase * > Node

Definition RDFGraph.h:381

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

std::set< NodeId > NodeSet

Definition RDFGraph.h:551

SmallVector< Node, 4 > NodeList

Definition RDFGraph.h:550

NodeAddr< CodeNode * > Code

Definition RDFGraph.h:388

NodeAddr< FuncNode * > Func

Definition RDFGraph.h:393

NodeAddr< RefNode * > Ref

Definition RDFGraph.h:383

This is an optimization pass for GlobalISel generic memory operations.

APInt operator*(APInt a, uint64_t RHS)

unsigned Log2_32(uint32_t Value)

Return the floor log base 2 of the specified value, -1 if the value is zero.

constexpr bool isPowerOf2_32(uint32_t Value)

Return true if the argument is a power of two > 0.

@ Sub

Subtraction of integers.

DWARFExpression::Operation Op

static constexpr LaneBitmask getAll()

constexpr bool any() const

constexpr bool all() const

Definition RDFGraph.h:643

MachineBasicBlock * getCode() const

Definition RDFGraph.h:644

void addPhi(Phi PA, const DataFlowGraph &G)

Definition RDFGraph.h:336

@ None

Definition RDFGraph.h:338

@ OmitReserved

Definition RDFGraph.h:340

@ KeepDeadPhis

Definition RDFGraph.h:339

Definition RDFGraph.h:612

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

Definition RDFGraph.h:947

void removeMember(Node NA, const DataFlowGraph &G)

NodeList members(const DataFlowGraph &G) const

void addMember(Node NA, const DataFlowGraph &G)

Node getFirstMember(const DataFlowGraph &G) const

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

void setCode(void *C)

Definition RDFGraph.h:616

T getCode() const

Definition RDFGraph.h:613

Node getLastMember(const DataFlowGraph &G) const

Definition RDFGraph.h:669

Config(ArrayRef< const TargetRegisterClass * > RCs)

Definition RDFGraph.h:672

Config(unsigned Opts)

Definition RDFGraph.h:671

SmallVector< const TargetRegisterClass * > Classes

Definition RDFGraph.h:678

unsigned Options

Definition RDFGraph.h:677

std::set< RegisterId > TrackRegs

Definition RDFGraph.h:679

Config(ArrayRef< RegisterId > Track)

Definition RDFGraph.h:674

Config(ArrayRef< MCPhysReg > Track)

Definition RDFGraph.h:673

void clear_block(NodeId N)

bool empty() const

Definition RDFGraph.h:705

void start_block(NodeId N)

iterator bottom() const

Definition RDFGraph.h:747

friend struct Iterator

Definition RDFGraph.h:756

void push(Def DA)

Definition RDFGraph.h:750

Iterator iterator

Definition RDFGraph.h:744

iterator top() const

Definition RDFGraph.h:746

Definition RDFGraph.h:660

NodeId id(const NodeBase *P) const

void unlinkUse(Use UA, bool RemoveFromOwner)

Definition RDFGraph.h:801

const RegisterAggr & getLiveIns() const

Definition RDFGraph.h:700

void releaseBlock(NodeId B, DefStackMap &DefM)

PackedRegisterRef pack(RegisterRef RR)

Definition RDFGraph.h:781

Ref getNextRelated(Instr IA, Ref RA) const

bool isTracked(RegisterRef RR) const

RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const

RegisterRef unpack(PackedRegisterRef PR) const

Definition RDFGraph.h:787

static bool IsDef(const Node BA)

Definition RDFGraph.h:825

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

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

static bool IsPhi(const Node BA)

Definition RDFGraph.h:835

Func getFunc() const

Definition RDFGraph.h:693

const MachineDominanceFrontier & getDF() const

Definition RDFGraph.h:699

static bool IsPreservingDef(const Def DA)

Definition RDFGraph.h:840

const MachineDominatorTree & getDT() const

Definition RDFGraph.h:698

NodeList getRelatedRefs(Instr IA, Ref RA) const

void unlinkDef(Def DA, bool RemoveFromOwner)

Definition RDFGraph.h:807

MachineFunction & getMF() const

Definition RDFGraph.h:694

const TargetInstrInfo & getTII() const

Definition RDFGraph.h:695

static bool IsRef(const Node BA)

Definition RDFGraph.h:817

PackedRegisterRef pack(RegisterRef RR) const

Definition RDFGraph.h:784

static bool IsUse(const Node BA)

Definition RDFGraph.h:830

T ptr(NodeId N) const

Definition RDFGraph.h:683

const PhysicalRegisterInfo & getPRI() const

Definition RDFGraph.h:697

static bool IsCode(const Node BA)

Definition RDFGraph.h:821

void markBlock(NodeId B, DefStackMap &DefM)

NodeBase * ptr(NodeId N) const

Block findBlock(MachineBasicBlock *BB) const

Definition RDFGraph.h:799

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

std::unordered_map< RegisterId, DefStack > DefStackMap

Definition RDFGraph.h:772

void build()

Definition RDFGraph.h:775

const TargetRegisterInfo & getTRI() const

Definition RDFGraph.h:696

void pushAllDefs(Instr IA, DefStackMap &DM)

NodeAddr< T > addr(NodeId N) const

Definition RDFGraph.h:689

Definition RDFGraph.h:588

NodeId getReachedUse() const

Definition RDFGraph.h:591

void setReachedUse(NodeId U)

Definition RDFGraph.h:592

void setReachedDef(NodeId D)

Definition RDFGraph.h:590

NodeId getReachedDef() const

Definition RDFGraph.h:589

void linkToDef(NodeId Self, Def DA)

Definition RDFGraph.h:651

MachineFunction * getCode() const

Definition RDFGraph.h:652

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

Block getEntryBlock(const DataFlowGraph &G)

LaneBitmask get(uint32_t Idx) const

uint32_t insert(LaneBitmask Val)

uint32_t find(LaneBitmask Val) const

Definition RDFGraph.h:629

Node getOwner(const DataFlowGraph &G)

uint32_t getIndexForLaneMask(LaneBitmask LM) const

Definition RDFGraph.h:481

LaneBitmask getLaneMaskForIndex(uint32_t K) const

Definition RDFGraph.h:472

uint32_t getIndexForLaneMask(LaneBitmask LM)

Definition RDFGraph.h:476

Definition RDFGraph.h:344

NodeBase * Addr

Definition RDFGraph.h:361

NodeAddr(const NodeAddr< S > &NA)

Definition RDFGraph.h:351

bool operator==(const NodeAddr< T > &NA) const

Definition RDFGraph.h:353

NodeAddr(T A, NodeId I)

Definition RDFGraph.h:346

NodeId Id

Definition RDFGraph.h:362

bool operator!=(const NodeAddr< T > &NA) const

Definition RDFGraph.h:357

NodeBase * ptr(NodeId N) const

Definition RDFGraph.h:421

NodeId id(const NodeBase *P) const

@ NodeMemSize

Definition RDFGraph.h:413

NodeAllocator(uint32_t NPB=4096)

Definition RDFGraph.h:415

Definition RDFGraph.h:266

static uint16_t set_kind(uint16_t A, uint16_t K)

Definition RDFGraph.h:310

static uint16_t flags(uint16_t T)

Definition RDFGraph.h:303

@ FlagMask

Definition RDFGraph.h:286

@ Phi

Definition RDFGraph.h:280

@ Undef

Definition RDFGraph.h:292

@ PhiRef

Definition RDFGraph.h:289

@ Ref

Definition RDFGraph.h:274

@ Code

Definition RDFGraph.h:273

@ Block

Definition RDFGraph.h:282

@ Preserving

Definition RDFGraph.h:290

@ Shadow

Definition RDFGraph.h:287

@ Dead

Definition RDFGraph.h:293

@ TypeMask

Definition RDFGraph.h:272

@ Stmt

Definition RDFGraph.h:281

@ Fixed

Definition RDFGraph.h:291

@ KindMask

Definition RDFGraph.h:277

@ Clobbering

Definition RDFGraph.h:288

@ Def

Definition RDFGraph.h:278

@ Func

Definition RDFGraph.h:283

@ Use

Definition RDFGraph.h:279

@ None

Definition RDFGraph.h:269

static uint16_t kind(uint16_t T)

Definition RDFGraph.h:300

static uint16_t set_type(uint16_t A, uint16_t T)

Definition RDFGraph.h:306

static bool contains(uint16_t A, uint16_t B)

Definition RDFGraph.h:319

static uint16_t set_flags(uint16_t A, uint16_t F)

Definition RDFGraph.h:314

static uint16_t type(uint16_t T)

Definition RDFGraph.h:297

Definition RDFGraph.h:522

NodeId LastM

Definition RDFGraph.h:524

NodeId FirstM

Definition RDFGraph.h:524

void * CP

Definition RDFGraph.h:523

Definition RDFGraph.h:516

NodeId DU

Definition RDFGraph.h:517

NodeId DD

Definition RDFGraph.h:517

Definition RDFGraph.h:519

NodeId PredB

Definition RDFGraph.h:520

Definition RDFGraph.h:526

NodeId RD

Definition RDFGraph.h:527

MachineOperand * Op

Definition RDFGraph.h:533

NodeId Sib

Definition RDFGraph.h:527

PackedRegisterRef PR

Definition RDFGraph.h:534

PhiU_struct PhiU

Definition RDFGraph.h:530

Def_struct Def

Definition RDFGraph.h:529

Definition RDFGraph.h:487

NodeId getNext() const

Definition RDFGraph.h:495

void setFlags(uint16_t F)

Definition RDFGraph.h:499

uint16_t Attrs

Definition RDFGraph.h:510

uint16_t Reserved

Definition RDFGraph.h:511

Ref_struct RefData

Definition RDFGraph.h:540

uint16_t getAttrs() const

Definition RDFGraph.h:497

uint16_t getType() const

Definition RDFGraph.h:492

void setAttrs(uint16_t A)

Definition RDFGraph.h:498

uint16_t getFlags() const

Definition RDFGraph.h:494

NodeId Next

Definition RDFGraph.h:512

void setNext(NodeId N)

Definition RDFGraph.h:507

Code_struct CodeData

Definition RDFGraph.h:541

uint16_t getKind() const

Definition RDFGraph.h:493

void init()

Definition RDFGraph.h:505

Definition RDFGraph.h:464

uint32_t MaskId

Definition RDFGraph.h:466

RegisterId Id

Definition RDFGraph.h:465

Definition RDFGraph.h:633

MachineInstr * getCode() const

Definition RDFGraph.h:634

Definition RDFGraph.h:601

NodeId getPredecessor() const

Definition RDFGraph.h:602

void setPredecessor(NodeId B)

Definition RDFGraph.h:606

PrintNode(const NodeAddr< T > &x, const DataFlowGraph &g)

Definition RDFGraph.h:971

Definition RDFGraph.h:961

Print(const T &x, const DataFlowGraph &g)

Definition RDFGraph.h:962

const DataFlowGraph & G

Definition RDFGraph.h:965

const T & Obj

Definition RDFGraph.h:964

Definition RDFGraph.h:553

bool isDef() const

Definition RDFGraph.h:577

NodeId getReachingDef() const

Definition RDFGraph.h:566

NodeId getSibling() const

Definition RDFGraph.h:569

Ref getNextRef(RegisterRef RR, Predicate P, bool NextOnly, const DataFlowGraph &G)

Definition RDFGraph.h:913

void setRegRef(RegisterRef RR, DataFlowGraph &G)

MachineOperand & getOp()

Definition RDFGraph.h:558

RegisterRef getRegRef(const DataFlowGraph &G) const

bool isUse() const

Definition RDFGraph.h:572

void setSibling(NodeId Sib)

Definition RDFGraph.h:570

void setReachingDef(NodeId RD)

Definition RDFGraph.h:567

Node getOwner(const DataFlowGraph &G)

Definition RDFGraph.h:637

MachineInstr * getCode() const

Definition RDFGraph.h:638

Definition RDFGraph.h:452

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

const TargetInstrInfo & TII

Definition RDFGraph.h:460

virtual ~TargetOperandInfo()=default

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

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

TargetOperandInfo(const TargetInstrInfo &tii)

Definition RDFGraph.h:453

Definition RDFGraph.h:597

void linkToDef(NodeId Self, Def DA)