LCSSA.cpp Source File (original) (raw)

52using namespace llvm;

54#define DEBUG_TYPE "lcssa"

56 STATISTIC(NumLCSSA, "Number of live out of a loop variables");

58#ifdef EXPENSIVE_CHECKS

60#else

62#endif

66 cl::desc("Verify loop lcssa form (time consuming)"));

72}

82static bool

92 bool Changed = false;

94 while (!Worklist.empty()) {

95 UsesToRewrite.clear();

98 assert(->getType()->isTokenTy() && "Tokens shouldn't be in the worklist");

101 assert(L && "Instruction belongs to a BB that's not part of a loop");

102 if (!LoopExitBlocks.count(L))

103 L->getExitBlocks(LoopExitBlocks[L]);

106

107 if (ExitBlocks.empty())

108 continue;

109

113

114

117 continue;

118 }

119

120

121

122

123 if (auto *PN = dyn_cast(User))

124 UserBB = PN->getIncomingBlock(U);

125

126 if (InstBB != UserBB && !L->contains(UserBB))

128 }

129

130

131 if (UsesToRewrite.empty())

132 continue;

133

134 ++NumLCSSA;

135

136

137

138

139

141 if (auto *Inv = dyn_cast(I))

142 DomBB = Inv->getNormalDest();

143

145

148

150 SSAUpdater SSAUpdate(&LocalInsertedPHIs);

151 SSAUpdate.Initialize(I->getType(), I->getName());

152

153

154

155 bool HasSCEV = SE && SE->isSCEVable(I->getType()) &&

157 for (BasicBlock *ExitBB : ExitBlocks) {

159 continue;

160

161

163 continue;

165 I->getName() + ".lcssa");

167 if (InsertedPHIs)

169

171

172

173

174

175

176

179

180

181

182

183 if (!L->contains(Pred))

187 }

188

190

191

193

194

195

196

197

198

199

200

201

202 if (auto *OtherLoop = LI.getLoopFor(ExitBB))

203 if (!L->contains(OtherLoop))

205

206

207

208

209

210 if (HasSCEV)

212 }

213

214

215

216 for (Use *UseToRewrite : UsesToRewrite) {

217 Instruction *User = cast(UseToRewrite->getUser());

219

220

221

222

223 if (auto *PN = dyn_cast(User))

224 UserBB = PN->getIncomingBlock(*UseToRewrite);

225

226

227

228

229

230 if (isa(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {

231 UseToRewrite->set(&UserBB->front());

232 continue;

233 }

234

235

236

237 if (AddedPHIs.size() == 1) {

238 UseToRewrite->set(AddedPHIs[0]);

239 continue;

240 }

241

242

244 }

245

249

250

251 for (auto *DVI : DbgValues) {

253 if (InstBB == UserBB || L->contains(UserBB))

254 continue;

255

256

257

258 Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]

260 if (V)

261 DVI->replaceVariableLocationOp(I, V);

262 }

263

264

265

268 if (InstBB == UserBB || L->contains(UserBB))

269 continue;

270

271

272

273 Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]

275 if (V)

276 DVR->replaceVariableLocationOp(I, V);

277 }

278

279

280

281 for (PHINode *InsertedPN : LocalInsertedPHIs) {

282 if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))

283 if (!L->contains(OtherLoop))

284 PostProcessPHIs.push_back(InsertedPN);

285 if (InsertedPHIs)

286 InsertedPHIs->push_back(InsertedPN);

287 }

288

289

290

291 for (auto *PostProcessPN : PostProcessPHIs)

292 if (!PostProcessPN->use_empty())

293 Worklist.push_back(PostProcessPN);

294

295

296

297 for (PHINode *PN : AddedPHIs)

298 if (PN->use_empty())

299 LocalPHIsToRemove.insert(PN);

300

301 Changed = true;

302 }

303

304

305

306

307

308

309

310

311

312 if (PHIsToRemove) {

313 PHIsToRemove->append(LocalPHIsToRemove.begin(), LocalPHIsToRemove.end());

314 } else {

315 for (PHINode *PN : LocalPHIsToRemove)

316 if (PN->use_empty())

317 PN->eraseFromParent();

318 }

319 return Changed;

320}

321

322

323

324

331

333 InsertedPHIs, LoopExitBlocks);

334}

335

336

340

341

343

344 while (!BBWorklist.empty()) {

346

347

348 if (L.getHeader() == BB)

349 continue;

350

351

352

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371 if (!L.contains(IDomBB))

372 continue;

373

374 if (BlocksDominatingExits.insert(IDomBB))

376 }

377}

378

382 bool Changed = false;

383

384#ifdef EXPENSIVE_CHECKS

385

386 for (Loop *SubLoop: L) {

387 (void)SubLoop;

388 assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!");

389 }

390#endif

391

392 if (!LoopExitBlocks.count(&L))

393 L.getExitBlocks(LoopExitBlocks[&L]);

395 if (ExitBlocks.empty())

396 return false;

397

399

400

401

402

403

404

406

408

409

410

411 for (BasicBlock *BB : BlocksDominatingExits) {

412

413

415 continue;

417

418

419 if (I.use_empty() ||

420 (I.hasOneUse() && I.user_back()->getParent() == BB &&

421 !isa(I.user_back())))

422 continue;

423

424

425

426

427

428 if (I.getType()->isTokenTy())

429 continue;

430

432 }

433 }

434

436 nullptr, LoopExitBlocks);

437

438 assert(L.isLCSSAForm(DT));

439

440 return Changed;

441}

442

446

447 return formLCSSAImpl(L, DT, LI, SE, LoopExitBlocks);

448}

449

450

454 bool Changed = false;

455

456

457 for (Loop *SubLoop : L.getSubLoops())

459

460 Changed |= formLCSSAImpl(L, DT, LI, SE, LoopExitBlocks);

461 return Changed;

462}

463

464

468

470}

471

472

475 bool Changed = false;

476 for (const auto &L : *LI)

478 return Changed;

479}

480

481namespace {

482struct LCSSAWrapperPass : public FunctionPass {

483 static char ID;

486 }

487

488

492

495

496

497

498

501 [&](Loop *L) {

502 return L->isRecursivelyLCSSAForm(*DT, *LI);

503 }) &&

504 "LCSSA form is broken!");

505 }

506 };

507

508

509

510

513

524

525

528 }

529};

530}

531

532char LCSSAWrapperPass::ID = 0;

534 false, false)

540

543

544

545bool LCSSAWrapperPass::runOnFunction(Function &F) {

546 LI = &getAnalysis().getLoopInfo();

547 DT = &getAnalysis().getDomTree();

548 auto *SEWP = getAnalysisIfAvailable();

549 SE = SEWP ? &SEWP->getSE() : nullptr;

550

552}

553

560

564

565

568 return PA;

569}

This is the interface for LLVM's primary stateless and local alias analysis.

This is the interface for a simple mod/ref and alias analysis over globals.

static bool formLCSSAForInstructionsImpl(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove, SmallVectorImpl< PHINode * > *InsertedPHIs, LoopExitBlocksTy &LoopExitBlocks)

For every instruction from the worklist, check to see if it has any uses that are outside the current...

static bool isExitBlock(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &ExitBlocks)

Return true if the specified block is in the list.

static bool VerifyLoopLCSSA

static bool formLCSSAImpl(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE, LoopExitBlocksTy &LoopExitBlocks)

static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT, ScalarEvolution *SE)

Process all loops in the function, inner-most out.

static void computeBlocksDominatingExits(Loop &L, const DominatorTree &DT, ArrayRef< BasicBlock * > ExitBlocks, SmallSetVector< BasicBlock *, 8 > &BlocksDominatingExits)

static bool formLCSSARecursivelyImpl(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE, LoopExitBlocksTy &LoopExitBlocks)

Process a loop nest depth first.

static cl::opt< bool, true > VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA), cl::Hidden, cl::desc("Verify loop lcssa form (time consuming)"))

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

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

This is the interface for a SCEV-based alias analysis.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.

A container for analyses that lazily runs them and caches their results.

PassT::Result * getCachedResult(IRUnitT &IR) const

Get the cached result of an analysis pass for a given IR unit.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

Represent the analysis usage information of a pass.

AnalysisUsage & addPreservedID(const void *ID)

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

void setPreservesCFG()

This function should be called by the pass, iff they do not:

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

Legacy wrapper pass to provide the BasicAAResult object.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const Instruction & front() const

const Function * getParent() const

Return the enclosing method, or null if none.

DbgMarker * getMarker(InstListType::iterator It)

Return the DbgMarker for the position given by It, so that DbgRecords can be inserted there.

Analysis pass which computes BranchProbabilityInfo.

Legacy analysis pass which computes BranchProbabilityInfo.

Represents analyses that only rely on functions' control flow.

const BasicBlock * getParent() const

Record of a variable value-assignment, aka a non instruction representation of the dbg....

size_type count(const_arg_type_t< KeyT > Val) const

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

DomTreeNodeBase * getIDom() const

Analysis pass which computes a DominatorTree.

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

Legacy analysis pass which computes a DominatorTree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

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.

FunctionPass class - This class is used to implement most global optimizations.

virtual bool runOnFunction(Function &F)=0

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

Legacy wrapper pass to provide the GlobalsAAResult object.

void insertBefore(Instruction *InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified instruction.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Analysis pass that exposes the LoopInfo for a function.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

The legacy pass manager's analysis pass to compute loop information.

Represents a single loop in the control flow graph.

An analysis that produces MemorySSA for a function.

Legacy analysis pass which computes MemorySSA.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

static unsigned getOperandNumForIncomingValue(unsigned i)

unsigned getNumIncomingValues() const

Return the number of incoming edges.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

Pass interface - Implemented by all 'passes'.

virtual void getAnalysisUsage(AnalysisUsage &) const

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

virtual void verifyAnalysis() const

verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...

static PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.

size_t size(BasicBlock *BB)

ArrayRef< BasicBlock * > get(BasicBlock *BB)

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

void preserveSet()

Mark an analysis set as preserved.

void preserve()

Mark an analysis as preserved.

Legacy wrapper pass to provide the SCEVAAResult object.

Helper class for SSA formation on a set of values defined in multiple blocks.

void RewriteUse(Use &U)

Rewrite a use of the symbolic value.

Value * FindValueForBlock(BasicBlock *BB) const

Return the value for the specified block if the SSAUpdater has one, otherwise return nullptr.

void Initialize(Type *Ty, StringRef Name)

Reset this object to get ready for a new set of SSA updates with type 'Ty'.

bool HasValueForBlock(BasicBlock *BB) const

Return true if the SSAUpdater already has a value for the specified block.

void AddAvailableValue(BasicBlock *BB, Value *V)

Indicate that a rewritten value is available in the specified block with the specified value.

Analysis pass that exposes the ScalarEvolution for a function.

The main scalar evolution driver.

const SCEV * getSCEV(Value *V)

Return a SCEV expression for the full generality of the specified expression.

bool isSCEVable(Type *Ty) const

Test if values of the given type are analyzable within the SCEV framework.

const SCEV * getExistingSCEV(Value *V)

Return an existing SCEV for V if there is one, otherwise return nullptr.

iterator end()

Get an iterator to the end of the SetVector.

iterator begin()

Get an iterator to the beginning of the SetVector.

bool insert(const value_type &X)

Insert a new element into the SetVector.

A SetVector that performs no allocations if smaller than a certain size.

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

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

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

A Use represents the edge between a Value definition and its users.

const Use & getOperandUse(unsigned i) const

LLVM Value Representation.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

LocationClass< Ty > location(Ty &L)

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

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

void initializeLCSSAWrapperPassPass(PassRegistry &)

bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)

Put a loop nest into LCSSA form.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)

Finds the llvm.dbg.value intrinsics describing a value.

bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)

Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)

Put loop into LCSSA form.