GenericUniformityImpl.h Source File (original) (raw)

44#ifndef LLVM_ADT_GENERICUNIFORMITYIMPL_H

45#define LLVM_ADT_GENERICUNIFORMITYIMPL_H

56#define DEBUG_TYPE "uniformity"

87public:

88 using BlockT = typename ContextT::BlockT;

89 using FunctionT = typename ContextT::FunctionT;

93 using CycleT = typename CycleInfoT::CycleT;

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

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

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

100

103

106

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

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

113 ReducibleCycleHeaders.insert(&BB);

114 }

115

118 return POIndex.lookup(BB);

119 }

120

122 return ReducibleCycleHeaders.contains(BB);

123 }

124

125private:

129 const ContextT &Context;

130

133

137};

138

139template <typename> class DivergencePropagator;

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

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

260public:

261 using BlockT = typename ContextT::BlockT;

263 using FunctionT = typename ContextT::FunctionT;

264 using ValueRefT = typename ContextT::ValueRefT;

266

268 using CycleT = typename CycleInfoT::CycleT;

269

272

273

274

275

276

277

278

279

281

282

283

285

287

289

291 };

292

294

297

298

299

300

301

302

303

304

305

306

308

309private:

311

313

316

318 CachedControlDivDescs;

319};

320

321

322

323

324

325

326

328public:

329 using BlockT = typename ContextT::BlockT;

330 using FunctionT = typename ContextT::FunctionT;

331 using ValueRefT = typename ContextT::ValueRefT;

333 using UseT = typename ContextT::UseT;

336

338 using CycleT = typename CycleInfoT::CycleT;

339

342 typename SyncDependenceAnalysisT::DivergenceDescriptor;

343 using BlockLabelMapT = typename SyncDependenceAnalysisT::BlockLabelMap;

344

349

351

353

354

356

357

359

360

361

363

364

365

367

368

369

371

372

374

375

376

378

380

382 if (I.isTerminator()) {

384 }

386 };

387

388

390

392

395 }

396

398

399protected:

400

404

407 };

408

413

414

417

418

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

420

421

422

424

425private:

427

428

430

431

432

433

434

436

437

439

440

442

443

444

445 void taintAndPushAllDefs(const BlockT &JoinBlock);

446

447

448

449 void taintAndPushPhiNodes(const BlockT &JoinBlock);

450

451

452

453

454 void propagateCycleExitDivergence(const BlockT &DivExit,

455 const CycleT &DivCycle);

456

457

458 void analyzeCycleExitDivergence(const CycleT &DefCycle);

459

460

461 void propagateTemporalDivergence(const InstructionT &I,

462 const CycleT &DefCycle);

463

464

467

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

469

470

471 bool isTemporalDivergent(const BlockT &ObservingBlock,

473};

474

475template

477 delete Impl;

478}

479

480

482public:

483 using BlockT = typename ContextT::BlockT;

485 using FunctionT = typename ContextT::FunctionT;

486 using ValueRefT = typename ContextT::ValueRefT;

487

489 using CycleT = typename CycleInfoT::CycleT;

490

494 typename SyncDependenceAnalysisT::DivergenceDescriptor;

495 using BlockLabelMapT = typename SyncDependenceAnalysisT::BlockLabelMap;

496

502

503

504

505

506

508

509

510 std::unique_ptr DivDesc;

512

518

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

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

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

525 if (!Label) {

526 Out << "\n";

527 } else {

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

529 }

530 }

531 Out << "}\n";

532 }

533

534

535

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

538

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

541 << "\n"

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

543

544

545 if (OldLabel == &PushedLabel)

546 return false;

547

548 if (OldLabel != &SuccBlock) {

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

550

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

553 }

554

555

556 if (!OldLabel) {

558 << "\n");

560 return false;

561 }

562

563

564

567

568 return true;

569 }

570

571

572

575 return false;

576

577

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

580 << "\n");

581 return true;

582 }

583

584

587 return false;

588

589

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

592 << "\n");

593 return true;

594 }

595

598

601

602

603 int FloorIdx = CyclePOT.size() - 1;

604 const BlockT *FloorLabel = nullptr;

606

607

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

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

611

612

613

614 DivDesc->CycleDivBlocks.insert(SuccBlock);

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

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

617 }

618 auto SuccIdx = CyclePOT.getIndex(SuccBlock);

619 visitEdge(*SuccBlock, *SuccBlock);

620 FloorIdx = std::min(FloorIdx, SuccIdx);

621 }

622

623 while (true) {

625 if (BlockIdx == -1 || BlockIdx < FloorIdx)

626 break;

627

629

631 if (BlockIdx == DivTermIdx) {

633 continue;

634 }

635

638 << BlockIdx << "\n");

639

642

643 bool CausedJoin = false;

644 int LoweredFloorIdx = FloorIdx;

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

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

663 return nullptr;

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

666 return BlockCycle;

667 return nullptr;

668 };

669

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

672 BlockCycle->getExitBlocks(BlockCycleExits);

673 for (auto *BlockCycleExit : BlockCycleExits) {

675 LoweredFloorIdx =

676 std::min(LoweredFloorIdx, CyclePOT.getIndex(BlockCycleExit));

677 }

678 } else {

680 CausedJoin |= visitEdge(*SuccBlock, *Label);

681 LoweredFloorIdx =

682 std::min(LoweredFloorIdx, CyclePOT.getIndex(SuccBlock));

683 }

684 }

685

686

687 if (CausedJoin) {

688

689 FloorIdx = LoweredFloorIdx;

690 } else if (FloorLabel != Label) {

691

692

693 FloorIdx = LoweredFloorIdx;

694 FloorLabel = Label;

695 }

696 }

697

699

700

701

702

706

707

708 continue;

709 }

714 for (const auto *Exit : Exits) {

716

717 DivDesc->CycleDivBlocks.insert(Exit);

719 << "\n");

720 }

721 }

722 }

723

724 return std::move(DivDesc);

725 }

726};

727

728template

731

732template

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

736 CyclePO.compute(CI);

737}

738

739template

742

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

744 return EmptyDivergenceDesc;

745 }

746

747

748 auto ItCached = CachedControlDivDescs.find(DivTermBlock);

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

750 return *ItCached->second;

751

752

755

758 Out << "[";

759 ListSeparator LS;

760 for (const auto *BB : Blocks) {

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

762 }

763 Out << "]\n";

764 });

765 };

766

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

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

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

771 << "\n");

772 (void)printBlockSet;

773

774 auto ItInserted =

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

776 assert(ItInserted.second);

777 return *ItInserted.first->second;

778}

779

780template

783 if (isAlwaysUniform(I))

784 return;

785 bool Marked = false;

786 if (I.isTerminator()) {

787 Marked = DivergentTermBlocks.insert(I.getParent()).second;

788 if (Marked) {

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

791 }

792 } else {

793 Marked = markDefsDivergent(I);

794 }

795

796 if (Marked)

797 Worklist.push_back(&I);

798}

799

800template

803 if (DivergentValues.insert(Val).second) {

804 LLVM_DEBUG(dbgs() << "marked divergent: " << Context.print(Val) << "\n");

805 return true;

806 }

807 return false;

808}

809

810template

813 UniformOverrides.insert(&Instr);

814}

815

816

817

818

819

820

821

822

823

824

825

826

827

828

829template

831 const CycleT &DefCycle) {

833 DefCycle.getExitBlocks(Exits);

834 for (auto *Exit : Exits) {

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

836 if (usesValueFromCycle(Phi, DefCycle)) {

837 markDivergent(Phi);

838 }

839 }

840 }

841

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

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

845 continue;

846 for (auto &II : *BB) {

847 propagateTemporalDivergence(II, DefCycle);

848 }

849 }

850}

851

852template

853void GenericUniformityAnalysisImpl::propagateCycleExitDivergence(

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

855 LLVM_DEBUG(dbgs() << "\tpropCycleExitDiv " << Context.print(&DivExit)

856 << "\n");

857 auto *DivCycle = &InnerDivCycle;

858 auto *OuterDivCycle = DivCycle;

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

860 const unsigned CycleExitDepth =

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

862

863

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

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

867 OuterDivCycle = DivCycle;

868 DivCycle = DivCycle->getParentCycle();

869 }

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

872

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

874 return;

875

876

877

878 for (const auto *C : AssumedDivergent) {

879 if (C->contains(OuterDivCycle))

880 return;

881 }

882

883 analyzeCycleExitDivergence(*OuterDivCycle);

884}

885

886template

887void GenericUniformityAnalysisImpl::taintAndPushAllDefs(

888 const BlockT &BB) {

889 LLVM_DEBUG(dbgs() << "taintAndPushAllDefs " << Context.print(&BB) << "\n");

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

891

892

893

894 if (I.isTerminator())

895 break;

896

897 markDivergent(I);

898 }

899}

900

901

902template

903void GenericUniformityAnalysisImpl::taintAndPushPhiNodes(

904 const BlockT &JoinBlock) {

905 LLVM_DEBUG(dbgs() << "taintAndPushPhiNodes in " << Context.print(&JoinBlock)

906 << "\n");

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

908

909

910

911

912

913

914

915 if (ContextT::isConstantOrUndefValuePhi(Phi))

916 continue;

917 markDivergent(Phi);

918 }

919}

920

921

922

923

924template

926 CycleT *Candidate) {

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

929 return false;

931 return true;

932}

933

934

935

936

937

938

939template <typename CycleT, typename BlockT>

941 const BlockT *DivTermBlock,

942 const BlockT *JoinBlock) {

945

947 return nullptr;

948

949 const auto *OriginalCycle = Cycle;

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

954 }

955

956

957

958

959 (void)OriginalCycle;

961

964 return nullptr;

965 }

966

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

969}

970

971

972

973

974

975template <typename ContextT, typename CycleT, typename BlockT,

976 typename DominatorTreeT>

977static const CycleT *

979 const BlockT *JoinBlock, const DominatorTreeT &DT,

980 ContextT &Context) {

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

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

983 << "\n");

985 return nullptr;

986

987

991 }

993 return nullptr;

994

996 return nullptr;

997

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

1000

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

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

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

1007 }

1008

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

1011}

1012

1013template <typename ContextT, typename CycleT, typename BlockT,

1014 typename DominatorTreeT>

1015static const CycleT *

1017 const BlockT *JoinBlock, const DominatorTreeT &DT,

1018 ContextT &Context) {

1020 return nullptr;

1021

1022

1023

1025

1026

1028

1029 if (Int)

1030 return Int;

1031 return Ext;

1032}

1033

1034template

1035bool GenericUniformityAnalysisImpl::isTemporalDivergent(

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

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

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

1041 if (DivergentExitCycles.contains(Cycle)) {

1042 return true;

1043 }

1044 }

1045 return false;

1046}

1047

1048template

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

1052 DivergentTermBlocks.insert(DivTermBlock);

1053 LLVM_DEBUG(dbgs() << "analyzeControlDiv " << Context.print(DivTermBlock)

1054 << "\n");

1055

1056

1058 return;

1059

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

1062

1063

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

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

1066 LLVM_DEBUG(dbgs() << "visiting join block " << Context.print(JoinBlock)

1067 << "\n");

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

1072 continue;

1073 }

1074 taintAndPushPhiNodes(*JoinBlock);

1075 }

1076

1077

1078

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

1081 });

1082

1083

1084

1085

1086

1087

1088 for (auto *C : DivCycles) {

1090 continue;

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

1093 taintAndPushAllDefs(*BB);

1094 }

1095 }

1096

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

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

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

1100 propagateCycleExitDivergence(*DivExitBlock, *BranchCycle);

1101 }

1102}

1103

1104template

1106

1107 auto DivValuesCopy = DivergentValues;

1108 for (const auto DivVal : DivValuesCopy) {

1109 assert(isDivergent(DivVal) && "Worklist invariant violated!");

1110 pushUsers(DivVal);

1111 }

1112

1113

1114

1115 while (!Worklist.empty()) {

1117 Worklist.pop_back();

1118

1119 LLVM_DEBUG(dbgs() << "worklist pop: " << Context.print(I) << "\n");

1120

1121 if (I->isTerminator()) {

1122 analyzeControlDivergence(*I);

1123 continue;

1124 }

1125

1126

1127 assert(isDivergent(*I) && "Worklist invariant violated!");

1128 pushUsers(*I);

1129 }

1130}

1131

1132template

1135 return UniformOverrides.contains(&Instr);

1136}

1137

1138template

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

1143}

1144

1145template

1147 bool haveDivergentArgs = false;

1148

1149

1150

1151

1152 if (DivergentValues.empty() && DivergentTermBlocks.empty() &&

1153 DivergentExitCycles.empty()) {

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

1155 return;

1156 }

1157

1158 for (const auto &entry : DivergentValues) {

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

1160 if (!parent) {

1161 if (!haveDivergentArgs) {

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

1163 haveDivergentArgs = true;

1164 }

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

1166 }

1167 }

1168

1169 if (!AssumedDivergent.empty()) {

1170 OS << "CYCLES ASSSUMED DIVERGENT:\n";

1171 for (const CycleT *cycle : AssumedDivergent) {

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

1173 }

1174 }

1175

1176 if (!DivergentExitCycles.empty()) {

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

1178 for (const CycleT *cycle : DivergentExitCycles) {

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

1180 }

1181 }

1182

1183 for (auto &block : F) {

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

1185

1186 OS << "DEFINITIONS\n";

1188 Context.appendBlockDefs(defs, block);

1189 for (auto value : defs) {

1190 if (isDivergent(value))

1191 OS << " DIVERGENT: ";

1192 else

1193 OS << " ";

1194 OS << Context.print(value) << '\n';

1195 }

1196

1197 OS << "TERMINATORS\n";

1199 Context.appendBlockTerms(terms, block);

1200 bool divergentTerminators = hasDivergentTerminator(block);

1201 for (auto *T : terms) {

1202 if (divergentTerminators)

1203 OS << " DIVERGENT: ";

1204 else

1205 OS << " ";

1206 OS << Context.print(T) << '\n';

1207 }

1208

1209 OS << "END BLOCK\n";

1210 }

1211}

1212

1213template

1215 return DA->hasDivergence();

1216}

1217

1218template

1219const typename ContextT::FunctionT &

1221 return DA->getFunction();

1222}

1223

1224

1225template

1227 return DA->isDivergent(V);

1228}

1229

1230template

1232 return DA->isDivergent(*I);

1233}

1234

1235template

1237 return DA->isDivergentUse(U);

1238}

1239

1240template

1242 return DA->hasDivergentTerminator(B);

1243}

1244

1245

1246template

1248 DA->print(out);

1249}

1250

1251template

1256 while (!Stack.empty()) {

1257 auto *NextBB = Stack.back();

1258 if (Finalized.count(NextBB)) {

1259 Stack.pop_back();

1260 continue;

1261 }

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

1263 << "\n");

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

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

1268 NestedCycle = NestedCycle->getParentCycle();

1269

1270 SmallVector<BlockT *, 3> NestedExits;

1271 NestedCycle->getExitBlocks(NestedExits);

1272 bool PushedNodes = false;

1273 for (auto *NestedExitBB : NestedExits) {

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

1277 continue;

1278 if (Finalized.count(NestedExitBB))

1279 continue;

1280 PushedNodes = true;

1281 Stack.push_back(NestedExitBB);

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

1284 }

1285 if (!PushedNodes) {

1286

1287 Stack.pop_back();

1288 computeCyclePO(CI, NestedCycle, Finalized);

1289 }

1290 continue;

1291 }

1292

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

1294

1295 bool PushedNodes = false;

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

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

1300 continue;

1301 if (Finalized.count(SuccBB))

1302 continue;

1303 PushedNodes = true;

1304 Stack.push_back(SuccBB);

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

1306 << "\n");

1307 }

1308 if (!PushedNodes) {

1309

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

1312 Stack.pop_back();

1313 Finalized.insert(NextBB);

1314 appendBlock(*NextBB);

1315 }

1316 }

1318}

1319

1320template

1321void ModifiedPostOrder::computeCyclePO(

1322 const CycleInfoT &CI, const CycleT *Cycle,

1323 SmallPtrSetImpl<const BlockT *> &Finalized) {

1325 SmallVector<const BlockT *> Stack;

1327

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

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

1331 Finalized.insert(CycleHeader);

1332

1333

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

1337

1338

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

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

1341 << "\n");

1343 continue;

1344 if (BB == CycleHeader)

1345 continue;

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

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

1348 << "\n");

1349 Stack.push_back(BB);

1350 }

1351 }

1352

1353

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

1355

1357}

1358

1359

1360template

1364 auto *F = CI.getFunction();

1365 Stack.reserve(24);

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

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

1368}

1369

1370}

1371

1372#undef DEBUG_TYPE

1373

1374#endif

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

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

Given that RA is a live value

This file defines the DenseSet and SmallDenseSet classes.

DenseMap< Block *, BlockRelaxAux > Blocks

uint64_t IntrinsicInst * II

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

This file defines the SmallPtrSet class.

This file defines the SparseBitVector class.

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

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

size_type count(const_arg_type_t< KeyT > Val) const

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

Implements a dense probed hash-table based set.

Compute divergence starting with a divergent branch.

typename SyncDependenceAnalysisT::BlockLabelMap BlockLabelMapT

const ModifiedPO & CyclePOT

GenericSyncDependenceAnalysis< ContextT > SyncDependenceAnalysisT

typename ContextT::DominatorTreeT DominatorTreeT

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

const BlockT & DivTermBlock

std::unique_ptr< DivergenceDescriptorT > DivDesc

void printDefs(raw_ostream &Out)

typename ContextT::FunctionT FunctionT

GenericCycleInfo< ContextT > CycleInfoT

const DominatorTreeT & DT

ModifiedPostOrder< ContextT > ModifiedPO

std::unique_ptr< DivergenceDescriptorT > computeJoinPoints()

BlockLabelMapT & BlockLabels

SparseBitVector FreshLabels

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

typename ContextT::ValueRefT ValueRefT

typename ContextT::BlockT BlockT

typename SyncDependenceAnalysisT::DivergenceDescriptor DivergenceDescriptorT

typename CycleInfoT::CycleT CycleT

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

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

bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const

properlyDominates - Returns true iff A dominates B and A != B.

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

Cycle information for a function.

A possibly irreducible generalization of a Loop.

BlockT * getHeader() const

bool isReducible() const

Whether the cycle is a natural loop.

void getExitBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const

Return all of the successor blocks of this cycle.

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.

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

ModifiedPostOrder< ContextT > ModifiedPO

typename ContextT::DominatorTreeT DominatorTreeT

GenericCycleInfo< ContextT > CycleInfoT

typename ContextT::FunctionT FunctionT

typename ContextT::InstructionT InstructionT

typename ContextT::BlockT BlockT

typename ContextT::ValueRefT ValueRefT

typename CycleInfoT::CycleT CycleT

const DivergenceDescriptor & getJoinBlocks(const BlockT *DivTermBlock)

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

Analysis that identifies uniform values in a data-parallel execution.

bool isAlwaysUniform(const InstructionT &Instr) const

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

typename ContextT::BlockT BlockT

typename ContextT::ValueRefT ValueRefT

void analyzeControlDivergence(const InstructionT &Term)

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

const FunctionT & getFunction() const

bool isDivergent(ConstValueRefT V) const

Whether Val is divergent at its definition.

bool isDivergentUse(const UseT &U) const

bool hasDivergentDefs(const InstructionT &I) const

typename ContextT::InstructionT InstructionT

DenseSet< ConstValueRefT > DivergentValues

typename ContextT::UseT UseT

typename ContextT::ConstValueRefT ConstValueRefT

typename SyncDependenceAnalysisT::BlockLabelMap BlockLabelMapT

bool hasDivergence() const

Whether any value was marked or analyzed to be divergent.

typename ContextT::DominatorTreeT DominatorTreeT

void compute()

Propagate divergence to all instructions in the region.

bool hasDivergentTerminator(const BlockT &B) const

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

bool markDefsDivergent(const InstructionT &Instr)

Mark outputs of Instr as divergent.

typename ContextT::FunctionT FunctionT

bool isDivergent(const InstructionT &I) const

std::vector< const InstructionT * > Worklist

void markDivergent(const InstructionT &I)

Examine I for divergent outputs and add to the worklist.

void print(raw_ostream &out) const

SmallPtrSet< const BlockT *, 32 > DivergentTermBlocks

GenericCycleInfo< ContextT > CycleInfoT

void addUniformOverride(const InstructionT &Instr)

Mark UniVal as a value that is always uniform.

typename SyncDependenceAnalysisT::DivergenceDescriptor DivergenceDescriptorT

typename CycleInfoT::CycleT CycleT

GenericSyncDependenceAnalysis< ContextT > SyncDependenceAnalysisT

bool hasDivergentTerminator(const BlockT &B)

bool isDivergentUse(const UseT &U) const

Whether U is divergent.

bool isDivergent(ConstValueRefT V) const

Whether V is divergent at its definition.

void print(raw_ostream &Out) const

T helper function for printing.

typename ContextT::ConstValueRefT ConstValueRefT

typename ContextT::BlockT BlockT

typename ContextT::InstructionT InstructionT

typename ContextT::UseT UseT

bool hasDivergence() const

Whether any divergence was detected.

const FunctionT & getFunction() const

The GPU kernel this analysis result is for.

GenericUniformityInfo()=default

GenericCycleInfo< ContextT > CycleInfoT

typename ContextT::DominatorTreeT DominatorTreeT

Construct a specially modified post-order traversal of cycles.

typename ContextT::FunctionT FunctionT

const BlockT * operator[](size_t idx) const

typename CycleInfoT::CycleT CycleT

bool isReducibleCycleHeader(const BlockT *BB) const

ModifiedPostOrder(const ContextT &C)

unsigned count(BlockT *BB) const

void compute(const CycleInfoT &CI)

Generically compute the modified post order.

GenericCycleInfo< ContextT > CycleInfoT

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

unsigned getIndex(const BlockT *BB) const

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

typename ContextT::DominatorTreeT DominatorTreeT

typename ContextT::BlockT BlockT

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.

bool contains(ConstPtrType Ptr) const

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.

size_type count(const_arg_type_t< ValueT > V) const

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

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.

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

Return the outermost cycle made divergent by branch outside it.

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.

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)

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)

raw_ostream & dbgs()

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

auto succ_size(const MachineBasicBlock *BB)

auto instrs(const MachineBasicBlock &BB)

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

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

ConstBlockSet CycleDivBlocks

ConstBlockSet JoinDivBlocks

BlockLabelMap BlockLabels

void operator()(ImplT *Impl)

Value/block pair representing a single phi input.

PhiInput(ConstValueRefT value, BlockT *predBlock)