LCSSA.cpp Source File (original) (raw)

51using namespace llvm;

53#define DEBUG_TYPE "lcssa"

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

57#ifdef EXPENSIVE_CHECKS

59#else

61#endif

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

81static bool

93 while (!Worklist.empty()) {

94 UsesToRewrite.clear();

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

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

101 auto [It, Inserted] = LoopExitBlocks.try_emplace(L);

102 if (Inserted)

103 L->getExitBlocks(It->second);

105

106 if (ExitBlocks.empty())

107 continue;

108

112

113

116 continue;

117 }

118

119

120

121

123 UserBB = PN->getIncomingBlock(U);

124

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

127 }

128

129

130 if (UsesToRewrite.empty())

131 continue;

132

133 ++NumLCSSA;

134

135

136

137

138

141 DomBB = Inv->getNormalDest();

142

144

147

149 SSAUpdater SSAUpdate(&LocalInsertedPHIs);

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

151

152

153

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

156 for (BasicBlock *ExitBB : ExitBlocks) {

158 continue;

159

160

162 continue;

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

166 if (InsertedPHIs)

168

170

171

172

173

174

175

178

179

180

181

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

186 }

187

189

190

192

193

194

195

196

197

198

199

200

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

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

204

205

206

207

208

209 if (HasSCEV)

211 }

212

213

214

215 for (Use *UseToRewrite : UsesToRewrite) {

218

219

220

221

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

224

225

226

227

228

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

231 continue;

232 }

233

234

235

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

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

238 continue;

239 }

240

241

243 }

244

247

248

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

252 continue;

253

254

255

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

258 if (V)

259 DVR->replaceVariableLocationOp(I, V);

260 }

261

262

263

264 for (PHINode *InsertedPN : LocalInsertedPHIs) {

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

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

267 PostProcessPHIs.push_back(InsertedPN);

268 if (InsertedPHIs)

269 InsertedPHIs->push_back(InsertedPN);

270 }

271

272

273

274 for (auto *PostProcessPN : PostProcessPHIs)

275 if (!PostProcessPN->use_empty())

276 Worklist.push_back(PostProcessPN);

277

278

279

280 for (PHINode *PN : AddedPHIs)

281 if (PN->use_empty())

282 LocalPHIsToRemove.insert(PN);

283

285 }

286

287

288

289

290

291

292

293

294

295 if (PHIsToRemove) {

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

297 } else {

298 for (PHINode *PN : LocalPHIsToRemove)

299 if (PN->use_empty())

300 PN->eraseFromParent();

301 }

303}

304

305

306

307

314

316 InsertedPHIs, LoopExitBlocks);

317}

318

319

323

324

326

327 while (!BBWorklist.empty()) {

329

330

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

332 continue;

333

334

335

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354 if (!L.contains(IDomBB))

355 continue;

356

357 if (BlocksDominatingExits.insert(IDomBB))

359 }

360}

361

366

367#ifdef EXPENSIVE_CHECKS

368

369 for (Loop *SubLoop: L) {

370 (void)SubLoop;

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

372 }

373#endif

374

375 auto [It, Inserted] = LoopExitBlocks.try_emplace(&L);

376 if (Inserted)

377 L.getExitBlocks(It->second);

379 if (ExitBlocks.empty())

380 return false;

381

383

384

385

386

387

388

390

392

393

394

395 for (BasicBlock *BB : BlocksDominatingExits) {

396

397

399 continue;

401

402

403 if (I.use_empty() ||

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

406 continue;

407

408

409

410

411

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

413 continue;

414

416 }

417 }

418

420 nullptr, LoopExitBlocks);

421

422 assert(L.isLCSSAForm(DT));

423

425}

426

430

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

432}

433

434

439

440

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

443

446}

447

448

455

456

460 for (const auto &L : *LI)

463}

464

465namespace {

466struct LCSSAWrapperPass : public FunctionPass {

467 static char ID;

468 LCSSAWrapperPass() : FunctionPass(ID) {

470 }

471

472

473 DominatorTree *DT;

474 LoopInfo *LI;

475 ScalarEvolution *SE;

476

478 void verifyAnalysis() const override {

479

480

481

482

485 [&](Loop *L) {

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

487 }) &&

488 "LCSSA form is broken!");

489 }

490 };

491

492

493

494

495 void getAnalysisUsage(AnalysisUsage &AU) const override {

497

498 AU.addRequired();

504 AU.addPreserved();

506 AU.addPreserved();

508

509

512 }

513};

514}

515

516char LCSSAWrapperPass::ID = 0;

518 false, false)

524

527

528

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

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

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

532 auto *SEWP = getAnalysisIfAvailable();

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

534

536}

537

544

548

549

552 return PA;

553}

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

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

static bool runOnFunction(Function &F, bool PostInlining)

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...

Definition LCSSA.cpp:82

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

Return true if the specified block is in the list.

Definition LCSSA.cpp:68

static bool VerifyLoopLCSSA

Definition LCSSA.cpp:60

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

Definition LCSSA.cpp:362

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

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

Definition LCSSA.cpp:457

SmallDenseMap< Loop *, SmallVector< BasicBlock *, 1 > > LoopExitBlocksTy

Definition LCSSA.cpp:76

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

Definition LCSSA.cpp:320

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

Process a loop nest depth first.

Definition LCSSA.cpp:435

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)

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)

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.

AnalysisUsage & addPreservedID(const void *ID)

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

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

LLVM_ABI 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),...

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const Instruction & front() const

LLVM_ABI 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.

Represents analyses that only rely on functions' control flow.

LLVM_ABI const BasicBlock * getParent() const

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

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.

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

LLVM_ABI 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.

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

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

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition LCSSA.cpp:538

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.

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 LLVM_ABI PassRegistry * getPassRegistry()

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

Pass interface - Implemented by all 'passes'.

static LLVM_ABI 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.

PreservedAnalyses & preserveSet()

Mark an analysis set as preserved.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

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.

LLVM_ABI const SCEV * getSCEV(Value *V)

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

LLVM_ABI bool isSCEVable(Type *Ty) const

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

LLVM_ABI 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.

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.

LLVM_ABI Pass * createLCSSAPass()

Definition LCSSA.cpp:525

LLVM_ABI void findDbgValues(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)

Finds the dbg.values describing a value.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

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

Put a loop nest into LCSSA form.

Definition LCSSA.cpp:449

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...

LLVM_ABI char & LCSSAID

Definition LCSSA.cpp:526

LLVM_ABI char & LoopSimplifyID

DomTreeNodeBase< BasicBlock > DomTreeNode

LLVM_ABI void initializeLCSSAWrapperPassPass(PassRegistry &)

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

LLVM_ABI 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.

Definition LCSSA.cpp:308

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

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

Returns true if Element is found in Range.

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

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

Put loop into LCSSA form.

Definition LCSSA.cpp:427