SSAUpdaterImpl.h Source File (original) (raw)

32private:

33 UpdaterT *Updater;

36 using BlkT = typename Traits::BlkT;

37 using ValT = typename Traits::ValT;

38 using PhiT = typename Traits::PhiT;

43 class BBInfo {

44 public:

46 BlkT *BB;

49 ValT AvailableVal;

52 BBInfo *DefBB;

55 int BlkNum = 0;

58 BBInfo *IDom = nullptr;

61 unsigned NumPreds = 0;

64 BBInfo **Preds = nullptr;

67 PhiT *PHITag = nullptr;

69 BBInfo(BlkT *ThisBB, ValT V)

70 : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {}

71 };

75 AvailableValsTy *AvailableVals;

82 BBMapTy BBMap;

85public:

88 Updater(U), AvailableVals(A), InsertedPHIs(Ins) {}

99 if (BlockList.size() == 0) {

100 ValT V = Traits::GetPoisonVal(BB, Updater);

101 (*AvailableVals)[BB] = V;

102 return V;

103 }

104

108

109 return BBMap[BB]->DefBB->AvailableVal;

110 }

111

112

113

114

115

119

120 BBInfo *Info = new (Allocator) BBInfo(BB, 0);

121 BBMap[BB] = Info;

123

124

125

126

128 while (!WorkList.empty()) {

131 Traits::FindPredecessorBlocks(Info->BB, &Preds);

132 Info->NumPreds = Preds.size();

133 if (Info->NumPreds == 0)

134 Info->Preds = nullptr;

135 else

136 Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(

137 Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));

138

139 for (unsigned p = 0; p != Info->NumPreds; ++p) {

140 BlkT *Pred = Preds[p];

141

142 BBInfo *&BBMapBucket = BBMap[Pred];

143 if (BBMapBucket) {

144 Info->Preds[p] = BBMapBucket;

145 continue;

146 }

147

148

149 ValT PredVal = AvailableVals->lookup(Pred);

150 BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);

151 BBMapBucket = PredInfo;

152 Info->Preds[p] = PredInfo;

153

154 if (PredInfo->AvailableVal) {

156 continue;

157 }

159 }

160 }

161

162

163

164

165 BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0);

166 unsigned BlkNum = 1;

167

168

169 while (!RootList.empty()) {

171 Info->IDom = PseudoEntry;

172 Info->BlkNum = -1;

174 }

175

176 while (!WorkList.empty()) {

178

179 if (Info->BlkNum == -2) {

180

181 Info->BlkNum = BlkNum++;

182

183 if ( Info ->AvailableVal)

186 continue;

187 }

188

189

190

191

192

193 Info->BlkNum = -2;

194

195

196 for (typename Traits::BlkSucc_iterator SI =

197 Traits::BlkSucc_begin(Info->BB),

198 E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {

199 BBInfo *SuccInfo = BBMap[*SI];

200 if (!SuccInfo || SuccInfo->BlkNum)

201 continue;

202 SuccInfo->BlkNum = -1;

204 }

205 }

206 PseudoEntry->BlkNum = BlkNum;

207 return PseudoEntry;

208 }

209

210

211

212

213

215 while (Blk1 != Blk2) {

216 while (Blk1->BlkNum < Blk2->BlkNum) {

217 Blk1 = Blk1->IDom;

218 if (!Blk1)

219 return Blk2;

220 }

221 while (Blk2->BlkNum < Blk1->BlkNum) {

222 Blk2 = Blk2->IDom;

223 if (!Blk2)

224 return Blk1;

225 }

226 }

227 return Blk1;

228 }

229

230

231

232

233

234

235

236

237

238

239

240 void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {

242 do {

244

246 E = BlockList->rend(); I != E; ++I) {

247 BBInfo *Info = *I;

248 BBInfo *NewIDom = nullptr;

249

250

251 for (unsigned p = 0; p != Info->NumPreds; ++p) {

252 BBInfo *Pred = Info->Preds[p];

253

254

255 if (Pred->BlkNum == 0) {

256 Pred->AvailableVal = Traits::GetPoisonVal(Pred->BB, Updater);

257 (*AvailableVals)[Pred->BB] = Pred->AvailableVal;

258 Pred->DefBB = Pred;

259 Pred->BlkNum = PseudoEntry->BlkNum;

260 PseudoEntry->BlkNum++;

261 }

262

263 if (!NewIDom)

264 NewIDom = Pred;

265 else

267 }

268

269

270 if (NewIDom && NewIDom != Info->IDom) {

271 Info->IDom = NewIDom;

273 }

274 }

276 }

277

278

279

280

281

283 for (; Pred != IDom; Pred = Pred->IDom) {

284 if (Pred->DefBB == Pred)

285 return true;

286 }

287 return false;

288 }

289

290

291

292

293

296 do {

298

300 E = BlockList->rend(); I != E; ++I) {

301 BBInfo *Info = *I;

302

303

305 continue;

306

307

308 BBInfo *NewDefBB = Info->IDom->DefBB;

309 for (unsigned p = 0; p != Info->NumPreds; ++p) {

311

312 NewDefBB = Info;

313 break;

314 }

315 }

316

317

318 if (NewDefBB != Info->DefBB) {

319 Info->DefBB = NewDefBB;

321 }

322 }

324 }

325

326

327

328

330 if ( Info ->NumPreds)

331 return false;

332 ValT Singular = Info->Preds[0]->DefBB->AvailableVal;

333 if (!Singular)

334 return false;

335 for (unsigned Idx = 1; Idx < Info->NumPreds; ++Idx) {

336 ValT PredVal = Info->Preds[Idx]->DefBB->AvailableVal;

337 if (!PredVal || Singular != PredVal)

338 return false;

339 }

340

341 (*AvailableVals)[Info->BB] = Singular;

342 assert(BBMap[Info->BB] == Info && "Info missed in BBMap?");

343 Info->AvailableVal = Singular;

344 Info->DefBB = Info->Preds[0]->DefBB;

345 return true;

346 }

347

348

349

350

351

352

354

355

356

358 E = BlockList->end(); I != E; ++I) {

359 BBInfo *Info = *I;

360

362 continue;

363

364

366 continue;

367

368

370 if (Info->AvailableVal)

371 continue;

372

373 ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);

374 Info->AvailableVal = PHI;

375 (*AvailableVals)[Info->BB] = PHI;

376 }

377

378

379

381 E = BlockList->rend(); I != E; ++I) {

382 BBInfo *Info = *I;

383

385

386

387 (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;

388 continue;

389 }

390

391

392 PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);

393 if ( PHI )

394 continue;

395

396

397 for (unsigned p = 0; p != Info->NumPreds; ++p) {

398 BBInfo *PredInfo = Info->Preds[p];

399 BlkT *Pred = PredInfo->BB;

400

401 if (PredInfo->DefBB != PredInfo)

402 PredInfo = PredInfo->DefBB;

403 Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);

404 }

405

407

408

409 if (InsertedPHIs) InsertedPHIs->push_back(PHI);

410 }

411 }

412

413

414

417 for (auto &SomePHI : BB->phis()) {

420 break;

421 }

422 }

423 }

424

425

426

428

429

431 for (BBInfo *TaggedBlock : TaggedBlocks)

432 TaggedBlock->PHITag = nullptr;

433 TaggedBlocks.clear();

434 });

435

438

439

440 BBInfo *PHIBlock = BBMap[PHI->getParent()];

441 PHIBlock->PHITag = PHI;

442 TaggedBlocks.push_back(PHIBlock);

443

444 while (!WorkList.empty()) {

445 PHI = WorkList.pop_back_val();

446

447

448 for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),

449 E = Traits::PHI_end(PHI); I != E; ++I) {

450 ValT IncomingVal = I.getIncomingValue();

451 BBInfo *PredInfo = BBMap[I.getIncomingBlock()];

452

453 if (PredInfo->DefBB != PredInfo)

454 PredInfo = PredInfo->DefBB;

455

456

457 if (PredInfo->AvailableVal) {

458 if (IncomingVal == PredInfo->AvailableVal)

459 continue;

460 return false;

461 }

462

463

464 PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);

465 if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)

466 return false;

467

468

469 if (PredInfo->PHITag) {

470 if (IncomingPHIVal == PredInfo->PHITag)

471 continue;

472 return false;

473 }

474 PredInfo->PHITag = IncomingPHIVal;

475 TaggedBlocks.push_back(PredInfo);

476

477 WorkList.push_back(IncomingPHIVal);

478 }

479 }

480

482 return true;

483 }

484

485

486

488 for (BBInfo *Block : TaggedBlocks) {

490 assert(PHI && "PHITag didn't set?");

491 BlkT *BB = PHI->getParent();

492 ValT PHIVal = Traits::GetPHIValue(PHI);

493 (*AvailableVals)[BB] = PHIVal;

494 BBMap[BB]->AvailableVal = PHIVal;

495 }

496 }

497};