DependenceGraphBuilder.cpp Source File (original) (raw)

110

111

114 if (SCC.size() > 1)

115 ListOfSCCs.emplace_back(SCC.begin(), SCC.end());

116 }

117

118 for (NodeListType &NL : ListOfSCCs) {

119 LLVM_DEBUG(dbgs() << "Creating pi-block node with " << NL.size()

120 << " nodes in it.\n");

121

122

123

124

125 llvm::sort(NL, [&](NodeType *LHS, NodeType *RHS) {

126 return getOrdinal(*LHS) < getOrdinal(*RHS);

127 });

128

129 NodeType &PiNode = createPiBlock(NL);

130 ++TotalPiBlockNodes;

131

132

133

135

136

137

138 for (NodeType *N : Graph) {

139

140

141 if (*N == PiNode || NodesInSCC.count(N))

142 continue;

143

145 Incoming,

146 Outgoing,

147 DirectionCount

148 };

149

150

151

152

153

154

155

156

157

158 using EdgeKind = typename EdgeType::EdgeKind;

160 false};

161

163 const EdgeKind K) {

164 switch (K) {

165 case EdgeKind::RegisterDefUse:

166 createDefUseEdge(Src, Dst);

167 break;

168 case EdgeKind::MemoryDependence:

169 createMemoryEdge(Src, Dst);

170 break;

171 case EdgeKind::Rooted:

172 createRootedEdge(Src, Dst);

173 break;

174 default:

176 }

177 };

178

181 if (!Src->hasEdgeTo(*Dst))

182 return;

184 dbgs() << "reconnecting("

185 << (Dir == Direction::Incoming ? "incoming)" : "outgoing)")

186 << ":\nSrc:" << *Src << "\nDst:" << *Dst << "\nNew:" << *New

187 << "\n");

188 assert((Dir == Direction::Incoming || Dir == Direction::Outgoing) &&

189 "Invalid direction.");

190

192 Src->findEdgesTo(*Dst, EL);

193 for (EdgeType *OldEdge : EL) {

194 EdgeKind Kind = OldEdge->getKind();

195 if (!EdgeAlreadyCreated[Dir][Kind]) {

196 if (Dir == Direction::Incoming) {

197 createEdgeOfKind(*Src, *New, Kind);

198 LLVM_DEBUG(dbgs() << "created edge from Src to New.\n");

199 } else if (Dir == Direction::Outgoing) {

200 createEdgeOfKind(*New, *Dst, Kind);

201 LLVM_DEBUG(dbgs() << "created edge from New to Dst.\n");

202 }

203 EdgeAlreadyCreated[Dir][Kind] = true;

204 }

205 Src->removeEdge(*OldEdge);

206 destroyEdge(*OldEdge);

207 LLVM_DEBUG(dbgs() << "removed old edge between Src and Dst.\n\n");

208 }

209 };

210

211 for (NodeType *SCCNode : NL) {

212

213 reconnectEdges(N, SCCNode, &PiNode, Direction::Incoming);

214

215

216 reconnectEdges(SCCNode, N, &PiNode, Direction::Outgoing);

217 }

218 }

219 }

220

221

222 InstOrdinalMap.clear();

223 NodeOrdinalMap.clear();

224

225 LLVM_DEBUG(dbgs() << "==== End of Creation of Pi-Blocks ===\n");

226}

227

229 for (NodeType *N : Graph) {

231 N->collectInstructions([](const Instruction *I) { return true; }, SrcIList);

232

233

234

235

237

239 for (User *U : II->users()) {

241 if (!UI)

242 continue;

243 NodeType *DstNode = IMap.lookup(UI);

244

245

246

247

248

249 if (!DstNode) {

252 << "skipped def-use edge since the sink" << *UI

253 << " is outside the range of instructions being considered.\n");

254 continue;

255 }

256

257

258

259 if (DstNode == N) {

261 << "skipped def-use edge since the sink and the source ("

262 << N << ") are the same.\n");

263 continue;

264 }

265

266 if (VisitedTargets.insert(DstNode).second) {

268 ++TotalDefUseEdges;

269 }

270 }

271 }

272 }

273}

274

275template

277 using DGIterator = typename G::iterator;

278 auto isMemoryAccess = [](const Instruction *I) {

279 return I->mayReadOrWriteMemory();

280 };

281 for (DGIterator SrcIt = Graph.begin(), E = Graph.end(); SrcIt != E; ++SrcIt) {

283 (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList);

284 if (SrcIList.empty())

285 continue;

286

287 for (DGIterator DstIt = SrcIt; DstIt != E; ++DstIt) {

288 if (**SrcIt == **DstIt)

289 continue;

291 (*DstIt)->collectInstructions(isMemoryAccess, DstIList);

292 if (DstIList.empty())

293 continue;

294 bool ForwardEdgeCreated = false;

295 bool BackwardEdgeCreated = false;

298 auto D = DI.depends(ISrc, IDst);

299 if ()

300 continue;

301

302

303

304

305

306

307

308 auto createConfusedEdges = [&](NodeType &Src, NodeType &Dst) {

309 if (!ForwardEdgeCreated) {

311 ++TotalMemoryEdges;

312 }

313 if (!BackwardEdgeCreated) {

315 ++TotalMemoryEdges;

316 }

317 ForwardEdgeCreated = BackwardEdgeCreated = true;

318 ++TotalConfusedEdges;

319 };

320

321 auto createForwardEdge = [&](NodeType &Src, NodeType &Dst) {

322 if (!ForwardEdgeCreated) {

324 ++TotalMemoryEdges;

325 }

326 ForwardEdgeCreated = true;

327 };

328

329 auto createBackwardEdge = [&](NodeType &Src, NodeType &Dst) {

330 if (!BackwardEdgeCreated) {

332 ++TotalMemoryEdges;

333 }

334 BackwardEdgeCreated = true;

335 };

336

337 if (D->isConfused())

338 createConfusedEdges(**SrcIt, **DstIt);

339 else if (D->isOrdered() && ->isLoopIndependent()) {

340 bool ReversedEdge = false;

341 for (unsigned Level = 1; Level <= D->getLevels(); ++Level) {

343 continue;

345 createBackwardEdge(**SrcIt, **DstIt);

346 ReversedEdge = true;

347 ++TotalEdgeReversals;

348 break;

350 break;

351 else {

352 createConfusedEdges(**SrcIt, **DstIt);

353 break;

354 }

355 }

356 if (!ReversedEdge)

357 createForwardEdge(**SrcIt, **DstIt);

358 } else

359 createForwardEdge(**SrcIt, **DstIt);

360

361

362 if (ForwardEdgeCreated && BackwardEdgeCreated)

363 break;

364 }

365

366

367

368

369 if (ForwardEdgeCreated && BackwardEdgeCreated)

370 break;

371 }

372 }

373 }

374}

375

378 return;

379 LLVM_DEBUG(dbgs() << "==== Start of Graph Simplification ===\n");

380

381

382

383

384

385

387

388

389

391

392 for (NodeType *N : Graph) {

393 if (N->getEdges().size() != 1)

394 continue;

395 EdgeType &Edge = N->back();

396 if (!Edge.isDefUse())

397 continue;

398 CandidateSourceNodes.insert(N);

399

400

401

402 TargetInDegreeMap.insert({&Edge.getTargetNode(), 0});

403 }

404

406 dbgs() << "Size of candidate src node list:" << CandidateSourceNodes.size()

407 << "\nNode with single outgoing def-use edge:\n";

408 for (NodeType *N : CandidateSourceNodes) {

409 dbgs() << N << "\n";

410 }

411 });

412

413 for (NodeType *N : Graph) {

414 for (EdgeType *E : *N) {

415 NodeType *Tgt = &E->getTargetNode();

416 auto TgtIT = TargetInDegreeMap.find(Tgt);

417 if (TgtIT != TargetInDegreeMap.end())

418 ++(TgtIT->second);

419 }

420 }

421

423 dbgs() << "Size of target in-degree map:" << TargetInDegreeMap.size()

424 << "\nContent of in-degree map:\n";

425 for (auto &I : TargetInDegreeMap) {

426 dbgs() << I.first << " --> " << I.second << "\n";

427 }

428 });

429

431 CandidateSourceNodes.end());

432 while (!Worklist.empty()) {

433 NodeType &Src = *Worklist.pop_back_val();

434

435

436 if (!CandidateSourceNodes.erase(&Src))

437 continue;

438

439 assert(Src.getEdges().size() == 1 &&

440 "Expected a single edge from the candidate src node.");

441 NodeType &Tgt = Src.back().getTargetNode();

442 assert(TargetInDegreeMap.find(&Tgt) != TargetInDegreeMap.end() &&

443 "Expected target to be in the in-degree map.");

444

445 if (TargetInDegreeMap[&Tgt] != 1)

446 continue;

447

449 continue;

450

451

452

453 if (Tgt.hasEdgeTo(Src))

454 continue;

455

456 LLVM_DEBUG(dbgs() << "Merging:" << Src << "\nWith:" << Tgt << "\n");

457

459

460

461

462

463

464

465

466

467

468

469

470 if (CandidateSourceNodes.erase(&Tgt)) {

471 Worklist.push_back(&Src);

472 CandidateSourceNodes.insert(&Src);

473 LLVM_DEBUG(dbgs() << "Putting " << &Src << " back in the worklist.\n");

474 }

475 }

476 LLVM_DEBUG(dbgs() << "=== End of Graph Simplification ===\n");

477}

478

479template

481

482

484 return;

485

487 using NodeKind = typename NodeType::NodeKind;

489 if (N->getKind() == NodeKind::PiBlock) {

490

491

494 }

496 }

497

498 size_t OldSize = Graph.Nodes.size();

499 Graph.Nodes.clear();

501 if (Graph.Nodes.size() != OldSize)

503 "Expected the number of nodes to stay the same after the sort");

504}