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."));

82 T += BFI.getBlockFreq(B);

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;

142 BFI.getBlockFreq(ColdestBB)) {

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

162 if (adjustedSumFreq(BBsToSinkInto, BFI) <= BFI.getBlockFreq(ColdestBB))

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

177 BFI.getBlockFreq(L.getLoopPreheader()))

178 BBsToSinkInto.clear();

179 return BBsToSinkInto;

180}

181

182

183

184

185

190

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

193 Instruction *UI = cast(U.getUser());

194

195

197 return false;

198

199 if (!isa(UI)) {

201 continue;

202 }

203

204

205

206 PHINode *PN = dyn_cast(UI);

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) {

262 if (auto *MemDef = dyn_cast(NewMemAcc))

263 MSSAU->insertDef(MemDef, true);

264 else {

265 auto *MemUse = cast(NewMemAcc);

266 MSSAU->insertUse(MemUse, true);

267 }

268 }

269 }

270

271

272

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

274 Instruction *UIToReplace = cast(U.getUser());

275 return UIToReplace->getParent() == N && !isa(UIToReplace);

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)

288 if (MemoryUseOrDef *OldMemAcc = cast_or_null(

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

308 const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);

309

310

311

313 return BFI.getBlockFreq(BB) > PreheaderFreq;

314 }))

315 return false;

316

319

320 bool Changed = false;

321

322

325 int i = 0;

327 if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {

329 LoopBlockNumber[B] = ++i;

330 }

332 return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);

333 });

334

335

336

337

339 if (isa(&I))

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)) {

348 Changed = true;

349 if (SE)

351 }

352 }

353

354 return Changed;

355}

356

358

359

360 if (.hasProfileData())

362

364

367

372

373

374

375

376

377

379

380 bool Changed = false;

381 do {

383

384 BasicBlock *Preheader = L.getLoopPreheader();

385 if (!Preheader)

386 continue;

387

388

389

390

392 nullptr);

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

394

395 if (!Changed)

397

401

403 MSSA.verifyMemorySSA();

404

405 return PA;

406}

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

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

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)

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.

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

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

Return adjusted total frequency of BBs.

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

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

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.

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

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

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

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

LLVM Basic Block Representation.

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

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.

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.

void insertBefore(Instruction *InsertPos)

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

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)

Represents a single loop in the control flow graph.

An analysis that produces MemorySSA for a function.

MemorySSA * getMemorySSA() const

Get handle on MemorySSA.

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

Insert a definition into the MemorySSA IR.

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

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.

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.

void preserveSet()

Mark an analysis set as preserved.

void preserve()

Mark an analysis as preserved.

The main scalar evolution driver.

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

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.

void setName(const Twine &Name)

Change the name of the value.

StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

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.

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

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 reverse(ContainerTy &&C)

void sort(IteratorTy Start, IteratorTy End)

raw_ostream & dbgs()

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

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 VerifyMemorySSA

Enables verification of MemorySSA.