GenericUniformityImpl.h Source File (original) (raw)

44#ifndef LLVM_ADT_GENERICUNIFORMITYIMPL_H

45#define LLVM_ADT_GENERICUNIFORMITYIMPL_H

56#define DEBUG_TYPE "uniformity"

58namespace llvm {

61class MachineInstr;

90public:

91 using BlockT = typename ContextT::BlockT;

92 using FunctionT = typename ContextT::FunctionT;

96 using CycleT = typename CycleInfoT::CycleT;

97 using const_iterator = typename std::vector<BlockT *>::const_iterator;

100

101 bool empty() const { return m_order.empty(); }

102 size_t size() const { return m_order.size(); }

103

104 void clear() { m_order.clear(); }

106

107 unsigned count(BlockT *BB) const { return POIndex.count(BB); }

109

111 POIndex[&BB] = m_order.size();

112 m_order.push_back(&BB);

114 << "): " << Context.print(&BB) << "\n");

116 ReducibleCycleHeaders.insert(&BB);

117 }

118

120 assert(POIndex.count(BB));

121 return POIndex.lookup(BB);

122 }

123

125 return ReducibleCycleHeaders.contains(BB);

126 }

127

128private:

132 const ContextT &Context;

133

136

140};

141

142template <typename> class DivergencePropagator;

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

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

263public:

264 using BlockT = typename ContextT::BlockT;

266 using FunctionT = typename ContextT::FunctionT;

267 using ValueRefT = typename ContextT::ValueRefT;

269

271 using CycleT = typename CycleInfoT::CycleT;

272

275

276

277

278

279

280

281

282

284

285

286

295

297

300

301

302

303

304

305

306

307

308

309

311

312private:

314

316

319

321 CachedControlDivDescs;

322};

323

324

325

326

327

328

329

331public:

332 using BlockT = typename ContextT::BlockT;

333 using FunctionT = typename ContextT::FunctionT;

334 using ValueRefT = typename ContextT::ValueRefT;

336 using UseT = typename ContextT::UseT;

339

341 using CycleT = typename CycleInfoT::CycleT;

342

345 typename SyncDependenceAnalysisT::DivergenceDescriptor;

346 using BlockLabelMapT = typename SyncDependenceAnalysisT::BlockLabelMap;

347

349 std::tuple<ConstValueRefT, InstructionT *, const CycleT *>;

350

355

357

359

360

362

363

365

366

367

369

370

371

373

374

375

377

378

380

381

382

384

386

388 if (I.isTerminator()) {

390 }

392 };

393

394

396

398

402

404

406

409

410protected:

415

416

419

420

421 std::vector<const InstructionT *> Worklist;

422

423

424

426

427private:

429

430

432

433

434

435

436

438

439

441

442

444

445

446

447 void taintAndPushAllDefs(const BlockT &JoinBlock);

448

449

450

451 void taintAndPushPhiNodes(const BlockT &JoinBlock);

452

453

454

455

456 void propagateCycleExitDivergence(const BlockT &DivExit,

457 const CycleT &DivCycle);

458

459

460 void analyzeCycleExitDivergence(const CycleT &DefCycle);

461

462

463 void propagateTemporalDivergence(const InstructionT &I,

464 const CycleT &DefCycle);

465

466

469

470 bool usesValueFromCycle(const InstructionT &I, const CycleT &DefCycle) const;

471

472

473 bool isTemporalDivergent(const BlockT &ObservingBlock,

475};

476

477template

481

482

484public:

485 using BlockT = typename ContextT::BlockT;

487 using FunctionT = typename ContextT::FunctionT;

488 using ValueRefT = typename ContextT::ValueRefT;

489

491 using CycleT = typename CycleInfoT::CycleT;

492

496 typename SyncDependenceAnalysisT::DivergenceDescriptor;

497 using BlockLabelMapT = typename SyncDependenceAnalysisT::BlockLabelMap;

498

504

505

506

507

508

510

511

512 std::unique_ptr DivDesc;

514

520

522 Out << "Propagator::BlockLabels {\n";

523 for (int BlockIdx = (int)CyclePOT.size() - 1; BlockIdx >= 0; --BlockIdx) {

526 Out << Context.print(Block) << "(" << BlockIdx << ") : ";

527 if (!Label) {

528 Out << "\n";

529 } else {

530 Out << Context.print(Label) << "\n";

531 }

532 }

533 Out << "}\n";

534 }

535

536

537

539 const auto *OldLabel = BlockLabels[&SuccBlock];

540

542 << "\tpushed label: " << Context.print(&PushedLabel)

543 << "\n"

544 << "\told label: " << Context.print(OldLabel) << "\n");

545

546

547 if (OldLabel == &PushedLabel)

548 return false;

549

550 if (OldLabel != &SuccBlock) {

551 auto SuccIdx = CyclePOT.getIndex(&SuccBlock);

552

553 LLVM_DEBUG(dbgs() << "\tfresh label: " << SuccIdx << "\n");

555 }

556

557

558 if (!OldLabel) {

560 << "\n");

562 return false;

563 }

564

565

566

569

570 return true;

571 }

572

573

574

577 return false;

578

579

580 DivDesc->CycleDivBlocks.insert(&ExitBlock);

582 << "\n");

583 return true;

584 }

585

586

589 return false;

590

591

592 DivDesc->JoinDivBlocks.insert(&SuccBlock);

594 << "\n");

595 return true;

596 }

597

600

603

605

606

607 auto const *DivTermCycle = CI.getCycle(&DivTermBlock);

608

609

610

611

612 const CycleT *IrreducibleAncestor = [](const CycleT *C) -> const CycleT * {

613 if ()

614 return nullptr;

615 if (C->isReducible())

616 return nullptr;

617 while (const CycleT *P = C->getParentCycle()) {

618 if (P->isReducible())

619 return C;

620 C = P;

621 }

622 assert(->getParentCycle());

623 assert(->isReducible());

624 return C;

625 }(DivTermCycle);

626

628 if (DivTermCycle && !DivTermCycle->contains(SuccBlock)) {

629

630

631

632 DivDesc->CycleDivBlocks.insert(SuccBlock);

633 LLVM_DEBUG(dbgs() << "\tImmediate divergent cycle exit: "

634 << Context.print(SuccBlock) << "\n");

635 }

636 visitEdge(*SuccBlock, *SuccBlock);

637 }

638

639

640

641

642

643

644 while (true) {

646 if (BlockIdx == -1)

647 break;

648

650

651

653 (!IrreducibleAncestor || !IrreducibleAncestor->contains(Block)))

654 break;

655

657

659 if (BlockIdx == DivTermIdx) {

661 continue;

662 }

663

665 << BlockIdx << "\n");

666

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685 auto getReducibleParent = [&](const BlockT *Block) -> const CycleT * {

687 return nullptr;

688 const auto *BlockCycle = CI.getCycle(Block);

690 return BlockCycle;

691 return nullptr;

692 };

693

694 if (const auto *BlockCycle = getReducibleParent(Block)) {

696 BlockCycle->getExitBlocks(BlockCycleExits);

697 for (auto *BlockCycleExit : BlockCycleExits)

699 } else {

702 }

703 }

704

706

707

708

709

712 if (Cycle->isReducible()) {

713

714

715 continue;

716 }

718 Cycle->getExitBlocks(Exits);

719 auto *Header = Cycle->getHeader();

721 for (const auto *Exit : Exits) {

723

724 DivDesc->CycleDivBlocks.insert(Exit);

726 << "\n");

727 }

728 }

729 }

730

731 return std::move(DivDesc);

732 }

733};

734

735template

738 : CyclePO(Context), DT(DT), CI(CI) {

739 CyclePO.compute(CI);

740}

741

742template

745

746 if (succ_size(DivTermBlock) <= 1) {

747 return EmptyDivergenceDesc;

748 }

749

750

751 auto ItCached = CachedControlDivDescs.find(DivTermBlock);

752 if (ItCached != CachedControlDivDescs.end())

753 return *ItCached->second;

754

755

758

759 auto printBlockSet = [&](ConstBlockSet &Blocks) {

761 Out << "[";

763 for (const auto *BB : Blocks) {

764 Out << LS << CI.getSSAContext().print(BB);

765 }

766 Out << "]\n";

767 });

768 };

769

771 dbgs() << "\nResult (" << CI.getSSAContext().print(DivTermBlock)

772 << "):\n JoinDivBlocks: " << printBlockSet(DivDesc->JoinDivBlocks)

773 << " CycleDivBlocks: " << printBlockSet(DivDesc->CycleDivBlocks)

774 << "\n");

775 (void)printBlockSet;

776

777 auto ItInserted =

778 CachedControlDivDescs.try_emplace(DivTermBlock, std::move(DivDesc));

779 assert(ItInserted.second);

780 return *ItInserted.first->second;

781}

782

783template

787 return;

788 bool Marked = false;

789 if (I.isTerminator()) {

791 if (Marked) {

793 << Context.print(I.getParent()) << "\n");

794 }

795 } else {

797 }

798

799 if (Marked)

801}

802

803template

808 return true;

809 }

810 return false;

811}

812

813template

816 UniformOverrides.insert(&Instr);

817}

818

819

820

821

822

823

824

825

826

827

828

829

830

831

832template

833void GenericUniformityAnalysisImpl::analyzeCycleExitDivergence(

834 const CycleT &DefCycle) {

836 DefCycle.getExitBlocks(Exits);

837 for (auto *Exit : Exits) {

838 for (auto &Phi : Exit->phis()) {

839 if (usesValueFromCycle(Phi, DefCycle)) {

840 markDivergent(Phi);

841 }

842 }

843 }

844

845 for (auto *BB : DefCycle.blocks()) {

847 [&](BlockT *Exit) { return DT.dominates(BB, Exit); }))

848 continue;

849 for (auto &II : *BB) {

850 propagateTemporalDivergence(II, DefCycle);

851 }

852 }

853}

854

855template

856void GenericUniformityAnalysisImpl::propagateCycleExitDivergence(

857 const BlockT &DivExit, const CycleT &InnerDivCycle) {

859 << "\n");

860 auto *DivCycle = &InnerDivCycle;

861 auto *OuterDivCycle = DivCycle;

862 auto *ExitLevelCycle = CI.getCycle(&DivExit);

863 const unsigned CycleExitDepth =

864 ExitLevelCycle ? ExitLevelCycle->getDepth() : 0;

865

866

867 while (DivCycle && DivCycle->getDepth() > CycleExitDepth) {

869 << Context.print(DivCycle->getHeader()) << "\n");

870 OuterDivCycle = DivCycle;

871 DivCycle = DivCycle->getParentCycle();

872 }

874 << Context.print(OuterDivCycle->getHeader()) << "\n");

875

876 if (!DivergentExitCycles.insert(OuterDivCycle).second)

877 return;

878

879

880

881 for (const auto *C : AssumedDivergent) {

882 if (C->contains(OuterDivCycle))

883 return;

884 }

885

886 analyzeCycleExitDivergence(*OuterDivCycle);

887}

888

889template

890void GenericUniformityAnalysisImpl::taintAndPushAllDefs(

891 const BlockT &BB) {

893 for (const auto &I : instrs(BB)) {

894

895

896

897 if (I.isTerminator())

898 break;

899

900 markDivergent(I);

901 }

902}

903

904

905template

906void GenericUniformityAnalysisImpl::taintAndPushPhiNodes(

907 const BlockT &JoinBlock) {

909 << "\n");

910 for (const auto &Phi : JoinBlock.phis()) {

911

912

913

914

915

916

917

918 if (ContextT::isConstantOrUndefValuePhi(Phi))

919 continue;

920 markDivergent(Phi);

921 }

922}

923

924

925

926

927template

929 CycleT *Candidate) {

931 [Candidate](CycleT *C) { return C->contains(Candidate); }))

932 return false;

933 Cycles.push_back(Candidate);

934 return true;

935}

936

937

938

939

940

941

942template <typename CycleT, typename BlockT>

944 const BlockT *DivTermBlock,

945 const BlockT *JoinBlock) {

948

949 if (Cycle->contains(DivTermBlock))

950 return nullptr;

951

952 const auto *OriginalCycle = Cycle;

953 const auto *Parent = Cycle->getParentCycle();

954 while (Parent && !Parent->contains(DivTermBlock)) {

956 Parent = Cycle->getParentCycle();

957 }

958

959

960

961

962 (void)OriginalCycle;

964

965 if (Cycle->isReducible()) {

967 return nullptr;

968 }

969

970 LLVM_DEBUG(dbgs() << "cycle made divergent by external branch\n");

972}

973

974

975

976

977

978template <typename ContextT, typename CycleT, typename BlockT,

979 typename DominatorTreeT>

980static const CycleT *

982 const BlockT *JoinBlock, const DominatorTreeT &DT,

983 ContextT &Context) {

984 LLVM_DEBUG(dbgs() << "examine join " << Context.print(JoinBlock)

985 << " for internal branch " << Context.print(DivTermBlock)

986 << "\n");

987 if (DT.properlyDominates(DivTermBlock, JoinBlock))

988 return nullptr;

989

990

992 while (Cycle && Cycle ->contains(DivTermBlock)) {

994 }

996 return nullptr;

997

998 if (DT.properlyDominates(Cycle->getHeader(), JoinBlock))

999 return nullptr;

1000

1002 << " does not dominate join\n");

1003

1004 const auto *Parent = Cycle->getParentCycle();

1005 while (Parent && !DT.properlyDominates(Parent->getHeader(), JoinBlock)) {

1006 LLVM_DEBUG(dbgs() << " header " << Context.print(Parent->getHeader())

1007 << " does not dominate join\n");

1009 Parent = Parent->getParentCycle();

1010 }

1011

1012 LLVM_DEBUG(dbgs() << " cycle made divergent by internal branch\n");

1014}

1015

1016template <typename ContextT, typename CycleT, typename BlockT,

1017 typename DominatorTreeT>

1018static const CycleT *

1020 const BlockT *JoinBlock, const DominatorTreeT &DT,

1021 ContextT &Context) {

1023 return nullptr;

1024

1025

1026

1028

1029

1031

1032 if (Int)

1033 return Int;

1034 return Ext;

1035}

1036

1037template

1038bool GenericUniformityAnalysisImpl::isTemporalDivergent(

1039 const BlockT &ObservingBlock, const InstructionT &Def) const {

1040 const BlockT *DefBlock = Def.getParent();

1041 for (const CycleT *Cycle = CI.getCycle(DefBlock);

1044 if (DivergentExitCycles.contains(Cycle)) {

1045 return true;

1046 }

1047 }

1048 return false;

1049}

1050

1051template

1054 const auto *DivTermBlock = Term.getParent();

1057 << "\n");

1058

1059

1060 if (!DT.isReachableFromEntry(DivTermBlock))

1061 return;

1062

1063 const auto &DivDesc = SDA.getJoinBlocks(DivTermBlock);

1065

1066

1067 for (const auto *JoinBlock : DivDesc.JoinDivBlocks) {

1068 const auto *Cycle = CI.getCycle(JoinBlock);

1070 << "\n");

1072 Cycle, DivTermBlock, JoinBlock, DT, Context)) {

1075 continue;

1076 }

1077 taintAndPushPhiNodes(*JoinBlock);

1078 }

1079

1080

1081

1083 return A->getDepth() > B->getDepth();

1084 });

1085

1086

1087

1088

1089

1090

1091 for (auto *C : DivCycles) {

1093 continue;

1095 for (const BlockT *BB : C->blocks()) {

1096 taintAndPushAllDefs(*BB);

1097 }

1098 }

1099

1100 const auto *BranchCycle = CI.getCycle(DivTermBlock);

1101 assert(DivDesc.CycleDivBlocks.empty() || BranchCycle);

1102 for (const auto *DivExitBlock : DivDesc.CycleDivBlocks) {

1103 propagateCycleExitDivergence(*DivExitBlock, *BranchCycle);

1104 }

1105}

1106

1107template

1109

1111 for (const auto DivVal : DivValuesCopy) {

1113 pushUsers(DivVal);

1114 }

1115

1116

1117

1121

1123

1124 if (I->isTerminator()) {

1126 continue;

1127 }

1128

1129

1131 pushUsers(*I);

1132 }

1133}

1134

1135template

1141

1142template

1145 return UniformOverrides.contains(&Instr);

1146}

1147

1148template

1152 DA.reset(new ImplT{DT, CI, TTI});

1153}

1154

1155template

1157 bool haveDivergentArgs = false;

1158

1159

1160

1161

1162 constexpr bool IsMIR = std::is_same<InstructionT, MachineInstr>::value;

1163 std::string NewLine = IsMIR ? "" : "\n";

1164

1165

1166

1167

1169 DivergentExitCycles.empty()) {

1170 OS << "ALL VALUES UNIFORM\n";

1171 return;

1172 }

1173

1175 const BlockT *parent = Context.getDefBlock(entry);

1176 if (!parent) {

1177 if (!haveDivergentArgs) {

1178 OS << "DIVERGENT ARGUMENTS:\n";

1179 haveDivergentArgs = true;

1180 }

1181 OS << " DIVERGENT: " << Context.print(entry) << '\n';

1182 }

1183 }

1184

1185 if (!AssumedDivergent.empty()) {

1186 OS << "CYCLES ASSUMED DIVERGENT:\n";

1187 for (const CycleT *cycle : AssumedDivergent) {

1188 OS << " " << cycle->print(Context) << '\n';

1189 }

1190 }

1191

1192 if (!DivergentExitCycles.empty()) {

1193 OS << "CYCLES WITH DIVERGENT EXIT:\n";

1194 for (const CycleT *cycle : DivergentExitCycles) {

1195 OS << " " << cycle->print(Context) << '\n';

1196 }

1197 }

1198

1200 OS << "\nTEMPORAL DIVERGENCE LIST:\n";

1201

1203 OS << "Value :" << Context.print(Val) << NewLine

1204 << "Used by :" << Context.print(UseInst) << NewLine

1205 << "Outside cycle :" << Cycle->print(Context) << "\n\n";

1206 }

1207 }

1208

1209 for (auto &block : F) {

1210 OS << "\nBLOCK " << Context.print(&block) << '\n';

1211

1212 OS << "DEFINITIONS\n";

1215 for (auto value : defs) {

1217 OS << " DIVERGENT: ";

1218 else

1219 OS << " ";

1220 OS << Context.print(value) << NewLine;

1221 }

1222

1223 OS << "TERMINATORS\n";

1227 for (auto *T : terms) {

1228 if (divergentTerminators)

1229 OS << " DIVERGENT: ";

1230 else

1231 OS << " ";

1232 OS << Context.print(T) << NewLine;

1233 }

1234

1235 OS << "END BLOCK\n";

1236 }

1237}

1238

1239template

1243 return make_range(DA->TemporalDivergenceList.begin(),

1244 DA->TemporalDivergenceList.end());

1245}

1246

1247template

1249 return DA->hasDivergence();

1250}

1251

1252template

1253const typename ContextT::FunctionT &

1255 return DA->getFunction();

1256}

1257

1258

1259template

1261 return DA->isDivergent(V);

1262}

1263

1264template

1266 return DA->isDivergent(*I);

1267}

1268

1269template

1271 return DA->isDivergentUse(U);

1272}

1273

1274template

1276 return DA->hasDivergentTerminator(B);

1277}

1278

1279

1280template

1282 DA->print(out);

1283}

1284

1285template

1286void llvm::ModifiedPostOrder::computeStackPO(

1290 while (!Stack.empty()) {

1291 auto *NextBB = Stack.back();

1292 if (Finalized.count(NextBB)) {

1293 Stack.pop_back();

1294 continue;

1295 }

1296 LLVM_DEBUG(dbgs() << " visiting " << CI.getSSAContext().print(NextBB)

1297 << "\n");

1298 auto *NestedCycle = CI.getCycle(NextBB);

1301 while (NestedCycle->getParentCycle() != Cycle)

1302 NestedCycle = NestedCycle->getParentCycle();

1303

1305 NestedCycle->getExitBlocks(NestedExits);

1306 bool PushedNodes = false;

1307 for (auto *NestedExitBB : NestedExits) {

1309 << CI.getSSAContext().print(NestedExitBB) << "\n");

1311 continue;

1312 if (Finalized.count(NestedExitBB))

1313 continue;

1314 PushedNodes = true;

1315 Stack.push_back(NestedExitBB);

1317 << CI.getSSAContext().print(NestedExitBB) << "\n");

1318 }

1319 if (!PushedNodes) {

1320

1321 Stack.pop_back();

1322 computeCyclePO(CI, NestedCycle, Finalized);

1323 }

1324 continue;

1325 }

1326

1327 LLVM_DEBUG(dbgs() << " no nested cycle, going into DAG\n");

1328

1329 bool PushedNodes = false;

1330 for (auto *SuccBB : successors(NextBB)) {

1332 << CI.getSSAContext().print(SuccBB) << "\n");

1333 if (Cycle && Cycle ->contains(SuccBB))

1334 continue;

1335 if (Finalized.count(SuccBB))

1336 continue;

1337 PushedNodes = true;

1338 Stack.push_back(SuccBB);

1339 LLVM_DEBUG(dbgs() << " pushed succ: " << CI.getSSAContext().print(SuccBB)

1340 << "\n");

1341 }

1342 if (!PushedNodes) {

1343

1345 << CI.getSSAContext().print(NextBB) << "\n");

1346 Stack.pop_back();

1347 Finalized.insert(NextBB);

1348 appendBlock(*NextBB);

1349 }

1350 }

1352}

1353

1354template

1355void ModifiedPostOrder::computeCyclePO(

1356 const CycleInfoT &CI, const CycleT *Cycle,

1360 auto *CycleHeader = Cycle->getHeader();

1361

1363 << CI.getSSAContext().print(CycleHeader) << "\n");

1364 assert(!Finalized.count(CycleHeader));

1365 Finalized.insert(CycleHeader);

1366

1367

1369 << CI.getSSAContext().print(CycleHeader) << "\n");

1370 appendBlock(*CycleHeader, Cycle->isReducible());

1371

1372

1373 for (auto *BB : successors(CycleHeader)) {

1374 LLVM_DEBUG(dbgs() << " examine succ: " << CI.getSSAContext().print(BB)

1375 << "\n");

1376 if ( Cycle ->contains(BB))

1377 continue;

1378 if (BB == CycleHeader)

1379 continue;

1380 if (!Finalized.count(BB)) {

1381 LLVM_DEBUG(dbgs() << " pushed succ: " << CI.getSSAContext().print(BB)

1382 << "\n");

1383 Stack.push_back(BB);

1384 }

1385 }

1386

1387

1388 computeStackPO(Stack, CI, Cycle, Finalized);

1389

1391}

1392

1393

1394template

1398 auto *F = CI.getFunction();

1399 Stack.reserve(24);

1400 Stack.push_back(&F->front());

1401 computeStackPO(Stack, CI, nullptr, Finalized);

1402}

1403

1404}

1405

1406#undef DEBUG_TYPE

1407

1408#endif

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

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

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

This file defines the DenseSet and SmallDenseSet classes.

uint64_t IntrinsicInst * II

This file defines the SmallPtrSet class.

This file defines the SparseBitVector class.

unify loop Fixup each natural loop to have a single exit block

Implements a dense probed hash-table based set.

Compute divergence starting with a divergent branch.

Definition GenericUniformityImpl.h:483

typename SyncDependenceAnalysisT::BlockLabelMap BlockLabelMapT

Definition GenericUniformityImpl.h:497

const ModifiedPO & CyclePOT

Definition GenericUniformityImpl.h:499

GenericSyncDependenceAnalysis< ContextT > SyncDependenceAnalysisT

Definition GenericUniformityImpl.h:494

typename ContextT::DominatorTreeT DominatorTreeT

Definition GenericUniformityImpl.h:486

bool computeJoin(const BlockT &SuccBlock, const BlockT &PushedLabel)

Definition GenericUniformityImpl.h:538

const BlockT & DivTermBlock

Definition GenericUniformityImpl.h:502

std::unique_ptr< DivergenceDescriptorT > DivDesc

Definition GenericUniformityImpl.h:512

void printDefs(raw_ostream &Out)

Definition GenericUniformityImpl.h:521

typename ContextT::FunctionT FunctionT

Definition GenericUniformityImpl.h:487

GenericCycleInfo< ContextT > CycleInfoT

Definition GenericUniformityImpl.h:490

const CycleInfoT & CI

Definition GenericUniformityImpl.h:501

const DominatorTreeT & DT

Definition GenericUniformityImpl.h:500

ModifiedPostOrder< ContextT > ModifiedPO

Definition GenericUniformityImpl.h:493

std::unique_ptr< DivergenceDescriptorT > computeJoinPoints()

Definition GenericUniformityImpl.h:598

const ContextT & Context

Definition GenericUniformityImpl.h:503

BlockLabelMapT & BlockLabels

Definition GenericUniformityImpl.h:513

SparseBitVector FreshLabels

Definition GenericUniformityImpl.h:509

bool visitCycleExitEdge(const BlockT &ExitBlock, const BlockT &Label)

Definition GenericUniformityImpl.h:575

typename ContextT::ValueRefT ValueRefT

Definition GenericUniformityImpl.h:488

typename ContextT::BlockT BlockT

Definition GenericUniformityImpl.h:485

typename CycleInfoT::CycleT CycleT

Definition GenericUniformityImpl.h:491

DivergencePropagator(const ModifiedPO &CyclePOT, const DominatorTreeT &DT, const CycleInfoT &CI, const BlockT &DivTermBlock)

Definition GenericUniformityImpl.h:515

bool visitEdge(const BlockT &SuccBlock, const BlockT &Label)

Definition GenericUniformityImpl.h:587

typename SyncDependenceAnalysisT::DivergenceDescriptor DivergenceDescriptorT

Definition GenericUniformityImpl.h:495

Cycle information for a function.

bool contains(const BlockT *Block) const

Return whether Block is contained in the cycle.

const GenericCycle * getParentCycle() const

Locate join blocks for disjoint paths starting at a divergent branch.

Definition GenericUniformityImpl.h:262

GenericSyncDependenceAnalysis(const ContextT &Context, const DominatorTreeT &DT, const CycleInfoT &CI)

Definition GenericUniformityImpl.h:736

ModifiedPostOrder< ContextT > ModifiedPO

Definition GenericUniformityImpl.h:274

DivergencePropagator< ContextT > DivergencePropagatorT

Definition GenericUniformityImpl.h:296

DenseMap< const BlockT *, const BlockT * > BlockLabelMap

Definition GenericUniformityImpl.h:283

SmallPtrSet< const BlockT *, 4 > ConstBlockSet

Definition GenericUniformityImpl.h:273

typename ContextT::DominatorTreeT DominatorTreeT

Definition GenericUniformityImpl.h:265

GenericCycleInfo< ContextT > CycleInfoT

Definition GenericUniformityImpl.h:270

typename ContextT::FunctionT FunctionT

Definition GenericUniformityImpl.h:266

typename ContextT::InstructionT InstructionT

Definition GenericUniformityImpl.h:268

typename ContextT::BlockT BlockT

Definition GenericUniformityImpl.h:264

typename ContextT::ValueRefT ValueRefT

Definition GenericUniformityImpl.h:267

typename CycleInfoT::CycleT CycleT

Definition GenericUniformityImpl.h:271

const DivergenceDescriptor & getJoinBlocks(const BlockT *DivTermBlock)

Computes divergent join points and cycle exits caused by branch divergence in Term.

Definition GenericUniformityImpl.h:743

SmallVector< TemporalDivergenceTuple, 8 > TemporalDivergenceList

Definition GenericUniformityImpl.h:405

bool isAlwaysUniform(const InstructionT &Instr) const

Whether Val will always return a uniform value regardless of its operands.

Definition GenericUniformityImpl.h:1143

typename ContextT::BlockT BlockT

Definition GenericUniformityImpl.h:332

typename ContextT::ValueRefT ValueRefT

Definition GenericUniformityImpl.h:334

void analyzeControlDivergence(const InstructionT &Term)

Mark Term as divergent and push all Instructions that become divergent as a result on the worklist.

Definition GenericUniformityImpl.h:1052

const ContextT & Context

Definition GenericUniformityImpl.h:411

const CycleInfoT & CI

Definition GenericUniformityImpl.h:413

const FunctionT & getFunction() const

Definition GenericUniformityImpl.h:358

bool isDivergent(ConstValueRefT V) const

Whether Val is divergent at its definition.

Definition GenericUniformityImpl.h:395

bool isDivergentUse(const UseT &U) const

bool hasDivergentDefs(const InstructionT &I) const

typename ContextT::InstructionT InstructionT

Definition GenericUniformityImpl.h:337

DenseSet< ConstValueRefT > DivergentValues

Definition GenericUniformityImpl.h:417

typename ContextT::UseT UseT

Definition GenericUniformityImpl.h:336

typename ContextT::ConstValueRefT ConstValueRefT

Definition GenericUniformityImpl.h:335

typename SyncDependenceAnalysisT::BlockLabelMap BlockLabelMapT

Definition GenericUniformityImpl.h:346

bool hasDivergence() const

Whether any value was marked or analyzed to be divergent.

Definition GenericUniformityImpl.h:379

typename ContextT::DominatorTreeT DominatorTreeT

Definition GenericUniformityImpl.h:338

void compute()

Propagate divergence to all instructions in the region.

Definition GenericUniformityImpl.h:1108

bool hasDivergentTerminator(const BlockT &B) const

Definition GenericUniformityImpl.h:399

GenericUniformityAnalysisImpl(const DominatorTreeT &DT, const CycleInfoT &CI, const TargetTransformInfo *TTI)

Definition GenericUniformityImpl.h:351

bool markDefsDivergent(const InstructionT &Instr)

Mark outputs of Instr as divergent.

typename ContextT::FunctionT FunctionT

Definition GenericUniformityImpl.h:333

bool isDivergent(const InstructionT &I) const

Definition GenericUniformityImpl.h:387

std::tuple< ConstValueRefT, InstructionT *, const CycleT * > TemporalDivergenceTuple

Definition GenericUniformityImpl.h:348

const TargetTransformInfo * TTI

Definition GenericUniformityImpl.h:414

std::vector< const InstructionT * > Worklist

Definition GenericUniformityImpl.h:421

void markDivergent(const InstructionT &I)

Examine I for divergent outputs and add to the worklist.

Definition GenericUniformityImpl.h:784

void print(raw_ostream &out) const

Definition GenericUniformityImpl.h:1156

SmallPtrSet< const BlockT *, 32 > DivergentTermBlocks

Definition GenericUniformityImpl.h:418

GenericCycleInfo< ContextT > CycleInfoT

Definition GenericUniformityImpl.h:340

void addUniformOverride(const InstructionT &Instr)

Mark UniVal as a value that is always uniform.

Definition GenericUniformityImpl.h:814

void recordTemporalDivergence(ConstValueRefT, const InstructionT *, const CycleT *)

Definition GenericUniformityImpl.h:1136

typename CycleInfoT::CycleT CycleT

Definition GenericUniformityImpl.h:341

typename SyncDependenceAnalysisT::DivergenceDescriptor DivergenceDescriptorT

Definition GenericUniformityImpl.h:344

GenericSyncDependenceAnalysis< ContextT > SyncDependenceAnalysisT

Definition GenericUniformityImpl.h:343

const FunctionT & F

Definition GenericUniformityImpl.h:412

bool hasDivergentTerminator(const BlockT &B)

Definition GenericUniformityImpl.h:1275

bool isDivergentUse(const UseT &U) const

Whether U is divergent.

Definition GenericUniformityImpl.h:1270

bool isDivergent(ConstValueRefT V) const

Whether V is divergent at its definition.

Definition GenericUniformityImpl.h:1260

void print(raw_ostream &Out) const

T helper function for printing.

Definition GenericUniformityImpl.h:1281

std::tuple< ConstValueRefT, InstructionT *, const CycleT * > TemporalDivergenceTuple

typename ContextT::ConstValueRefT ConstValueRefT

typename ContextT::BlockT BlockT

typename ContextT::InstructionT InstructionT

typename ContextT::UseT UseT

bool hasDivergence() const

Whether any divergence was detected.

Definition GenericUniformityImpl.h:1248

const FunctionT & getFunction() const

The GPU kernel this analysis result is for.

Definition GenericUniformityImpl.h:1254

GenericUniformityInfo()=default

GenericCycleInfo< ContextT > CycleInfoT

typename ContextT::DominatorTreeT DominatorTreeT

iterator_range< TemporalDivergenceTuple * > getTemporalDivergenceList() const

Definition GenericUniformityImpl.h:1242

A helper class to return the specified delimiter string after the first invocation of operator String...

Construct a specially modified post-order traversal of cycles.

Definition GenericUniformityImpl.h:89

void clear()

Definition GenericUniformityImpl.h:104

typename ContextT::FunctionT FunctionT

Definition GenericUniformityImpl.h:92

const BlockT * operator[](size_t idx) const

Definition GenericUniformityImpl.h:108

typename CycleInfoT::CycleT CycleT

Definition GenericUniformityImpl.h:96

bool isReducibleCycleHeader(const BlockT *BB) const

Definition GenericUniformityImpl.h:124

bool empty() const

Definition GenericUniformityImpl.h:101

ModifiedPostOrder(const ContextT &C)

Definition GenericUniformityImpl.h:99

unsigned count(BlockT *BB) const

Definition GenericUniformityImpl.h:107

void compute(const CycleInfoT &CI)

Generically compute the modified post order.

Definition GenericUniformityImpl.h:1395

GenericCycleInfo< ContextT > CycleInfoT

Definition GenericUniformityImpl.h:95

void appendBlock(const BlockT &BB, bool isReducibleCycleHeader=false)

Definition GenericUniformityImpl.h:110

unsigned getIndex(const BlockT *BB) const

Definition GenericUniformityImpl.h:119

typename std::vector< BlockT * >::const_iterator const_iterator

Definition GenericUniformityImpl.h:97

typename ContextT::DominatorTreeT DominatorTreeT

Definition GenericUniformityImpl.h:93

size_t size() const

Definition GenericUniformityImpl.h:102

typename ContextT::BlockT BlockT

Definition GenericUniformityImpl.h:91

Simple wrapper around std::function<void(raw_ostream&)>.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

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

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

void push_back(const T &Elt)

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

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

A range adaptor for a pair of iterators.

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

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

static const CycleT * getIntDivCycle(const CycleT *Cycle, const BlockT *DivTermBlock, const BlockT *JoinBlock, const DominatorTreeT &DT, ContextT &Context)

Return the outermost cycle made divergent by branch inside it.

Definition GenericUniformityImpl.h:981

static const CycleT * getExtDivCycle(const CycleT *Cycle, const BlockT *DivTermBlock, const BlockT *JoinBlock)

Return the outermost cycle made divergent by branch outside it.

Definition GenericUniformityImpl.h:943

auto successors(const MachineBasicBlock *BB)

static bool insertIfNotContained(SmallVector< CycleT * > &Cycles, CycleT *Candidate)

Add Candidate to Cycles if it is not already contained in Cycles.

Definition GenericUniformityImpl.h:928

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

Convenience function for iterating over sub-ranges.

bool any_of(R &&range, UnaryPredicate P)

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

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

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

auto succ_size(const MachineBasicBlock *BB)

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

auto instrs(const MachineBasicBlock &BB)

static const CycleT * getOutermostDivergentCycle(const CycleT *Cycle, const BlockT *DivTermBlock, const BlockT *JoinBlock, const DominatorTreeT &DT, ContextT &Context)

Definition GenericUniformityImpl.h:1019

Information discovered by the sync dependence analysis for each divergent branch.

Definition GenericUniformityImpl.h:287

ConstBlockSet CycleDivBlocks

Definition GenericUniformityImpl.h:291

ConstBlockSet JoinDivBlocks

Definition GenericUniformityImpl.h:289

BlockLabelMap BlockLabels

Definition GenericUniformityImpl.h:293

void operator()(ImplT *Impl)

Definition GenericUniformityImpl.h:478