LoopSink.cpp Source File (original) (raw)

49using namespace llvm;

51#define DEBUG_TYPE "loopsink"

53 STATISTIC(NumLoopSunk, "Number of instructions sunk into loop");

54 STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop");

58 cl::desc("Do not sink instructions that require cloning unless they "

59 "execute less than this percent of the time."));

63 cl::desc("Do not sink instructions that have too many uses."));

83 if (BBs.size() > 1)

85 return T;

86}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

120 if (UseBBs.size() == 0)

121 return BBsToSinkInto;

122

125

126

127

128

129

130

131

132

133

134 for (BasicBlock *ColdestBB : ColdLoopBBs) {

135 BBsDominatedByColdestBB.clear();

136 for (BasicBlock *SinkedBB : BBsToSinkInto)

137 if (DT.dominates(ColdestBB, SinkedBB))

138 BBsDominatedByColdestBB.insert(SinkedBB);

139 if (BBsDominatedByColdestBB.size() == 0)

140 continue;

143 for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) {

144 BBsToSinkInto.erase(DominatedBB);

145 }

146 BBsToSinkInto.insert(ColdestBB);

147 continue;

148 }

149

150

151

152

153

154

155

156

157

158

159

160

161

163 break;

164 }

165

166

167 for (BasicBlock *BB : BBsToSinkInto) {

168 if (BB->getFirstInsertionPt() == BB->end()) {

169 BBsToSinkInto.clear();

170 break;

171 }

172 }

173

174

175

178 BBsToSinkInto.clear();

179 return BBsToSinkInto;

180}

181

182

183

184

185

190

192 for (auto &U : I.uses()) {

194

195

197 return false;

198

201 continue;

202 }

203

204

205

208

209

210

211 if (L.getLoopPreheader() == PhiBB)

212 return false;

213

215 }

216

217

218

219

221 return false;

222

223

226 if (BBsToSinkInto.empty())

227 return false;

228

229

230 if (BBsToSinkInto.size() > 1 &&

232 return false;

233

234

235

236

239 if (SortedBBsToSinkInto.size() > 1) {

241 return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second;

242 });

243 }

244

246

247

250 LoopBlockNumber.find(MoveBB)->second &&

251 "BBs not sorted!");

252

256

258

261 if (NewMemAcc) {

263 MSSAU->insertDef(MemDef, true);

264 else {

266 MSSAU->insertUse(MemUse, true);

267 }

268 }

269 }

270

271

272

273 I.replaceUsesWithIf(IC, [N](Use &U) {

276 });

277

279 LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()

280 << '\n');

281 NumLoopSunkCloned++;

282 }

284 NumLoopSunk++;

286

287 if (MSSAU)

291

292 return true;

293}

294

295

296

302 BasicBlock *Preheader = L.getLoopPreheader();

303 assert(Preheader && "Expected loop to have preheader");

304

306 "Unexpected call when profile data unavailable.");

307

309

310

311

313 return BFI.getBlockFreq(BB) > PreheaderFreq;

314 }))

315 return false;

316

319

321

322

325 int i = 0;

329 LoopBlockNumber[B] = ++i;

330 }

333 });

334

335

336

337

340 continue;

341

342 assert(L.hasLoopInvariantOperands(&I) &&

343 "Insts in a loop's preheader should have loop invariant operands!");

345 continue;

346 if (sinkInstruction(L, I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI,

347 &MSSAU)) {

349 if (SE)

351 }

352 }

353

355}

356

358

359

360 if (.hasProfileData())

362

364

367

372

373

374

375

376

377

379

381 do {

383

384 BasicBlock *Preheader = L.getLoopPreheader();

385 if (!Preheader)

386 continue;

387

388

389

390

392 nullptr);

393 } while (!PreorderLoops.empty());

394

397

401

403 MSSA.verifyMemorySSA();

404

405 return PA;

406}

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

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

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

static cl::opt< unsigned > SinkFrequencyPercentThreshold("sink-freq-percent-threshold", cl::Hidden, cl::init(90), cl::desc("Do not sink instructions that require cloning unless they " "execute less than this percent of the time."))

static bool sinkInstruction(Loop &L, Instruction &I, const SmallVectorImpl< BasicBlock * > &ColdLoopBBs, const SmallDenseMap< BasicBlock *, int, 16 > &LoopBlockNumber, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSAUpdater *MSSAU)

Definition LoopSink.cpp:186

static SmallPtrSet< BasicBlock *, 2 > findBBsToSinkInto(const Loop &L, const SmallPtrSetImpl< BasicBlock * > &UseBBs, const SmallVectorImpl< BasicBlock * > &ColdLoopBBs, DominatorTree &DT, BlockFrequencyInfo &BFI)

Return a set of basic blocks to insert sinked instructions.

Definition LoopSink.cpp:116

static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSA &MSSA, ScalarEvolution *SE)

Sinks instructions from loop's preheader to the loop body if the sum frequency of inserted copy is sm...

Definition LoopSink.cpp:297

static BlockFrequency adjustedSumFreq(SmallPtrSetImpl< BasicBlock * > &BBs, BlockFrequencyInfo &BFI)

Return adjusted total frequency of BBs.

Definition LoopSink.cpp:78

static cl::opt< unsigned > MaxNumberOfUseBBsForSinking("max-uses-for-sinking", cl::Hidden, cl::init(30), cl::desc("Do not sink instructions that have too many uses."))

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

FunctionAnalysisManager FAM

This file defines generic set operations that may be used on set's of different types,...

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

#define STATISTIC(VARNAME, DESC)

A manager for alias analyses.

LLVM Basic Block Representation.

LLVM_ABI const_iterator getFirstInsertionPt() const

Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...

const Function * getParent() const

Return the enclosing method, or null if none.

Analysis pass which computes BlockFrequencyInfo.

BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...

LLVM_ABI BlockFrequency getBlockFreq(const BasicBlock *BB) const

getblockFreq - Return block frequency.

Represents analyses that only rely on functions' control flow.

iterator find(const_arg_type_t< KeyT > Val)

Analysis pass which computes a DominatorTree.

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

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.

bool hasProfileData(bool IncludeSynthetic=false) const

Return true if the function is annotated with profile data.

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

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

Analysis pass that exposes the LoopInfo for a function.

SmallVector< LoopT *, 4 > getLoopsInPreorder() const

Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)

Definition LoopSink.cpp:357

Represents a single loop in the control flow graph.

An analysis that produces MemorySSA for a function.

MemorySSA * getMemorySSA() const

Get handle on MemorySSA.

LLVM_ABI void insertDef(MemoryDef *Def, bool RenameUses=false)

Insert a definition into the MemorySSA IR.

LLVM_ABI void insertUse(MemoryUse *Use, bool RenameUses=false)

LLVM_ABI MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point, bool CreationMustSucceed=true)

Create a MemoryAccess in MemorySSA at a specified point in a block.

LLVM_ABI void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)

Encapsulates MemorySSA, including all data associated with memory accesses.

MemoryUseOrDef * getMemoryAccess(const Instruction *I) const

Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.

Class that has the common methods + fields of memory uses/defs.

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

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.

The main scalar evolution driver.

LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)

Called when the client has changed the disposition of values in a loop or block.

Flags controlling how much is checked when sinking or hoisting instructions.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

void insert_range(Range &&R)

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

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.

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

LLVM_ABI void setName(const Twine &Name)

Change the name of the value.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

Abstract Attribute helper functions.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

void stable_sort(R &&Range)

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 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, MemorySSAUpdater &MSSAU, bool TargetExecutesOncePerLoop, SinkAndHoistLICMFlags &LICMFlags, OptimizationRemarkEmitter *ORE=nullptr)

Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...

decltype(auto) dyn_cast(const From &Val)

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

bool set_is_subset(const S1Ty &S1, const S2Ty &S2)

set_is_subset(A, B) - Return true iff A in B

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

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

auto cast_or_null(const Y &Val)

auto reverse(ContainerTy &&C)

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)

Replace each use of 'From' with 'To' if that use is dominated by the given edge.

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 VerifyMemorySSA

Enables verification of MemorySSA.

ArrayRef(const T &OneElt) -> ArrayRef< T >

decltype(auto) cast(const From &Val)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.