IVUsers.cpp Source File (original) (raw)

22#include "llvm/Config/llvm-config.h"

30using namespace llvm;

32#define DEBUG_TYPE "iv-users"

39}

43 "Induction Variable Users", false, true)

59 if (const SCEVAddRecExpr *AR = dyn_cast(S)) {

62 if (AR->getLoop() == L)

63 return AR->isAffine() ||

64 (!L->contains(I) &&

70 isInteresting (AR->getStepRecurrence(*SE), I, L, SE, LI);

71 }

74 if (const SCEVAddExpr *Add = dyn_cast(S)) {

75 bool AnyInterestingYet = false;

76 for (const SCEV *Op : Add->operands())

78 if (AnyInterestingYet)

79 return false;

80 AnyInterestingYet = true;

81 }

82 return AnyInterestingYet;

83 }

86 return false;

87}

100 if (L->contains(User))

101 return false;

102

103 BasicBlock *LatchBlock = L->getLoopLatch();

104 if (!LatchBlock)

105 return false;

106

107

108

109 if (DT->dominates(LatchBlock, User->getParent()))

110 return true;

111

112

113

114

115

117 if (!PN || !Operand)

118 return false;

119

120

121

122

126 return false;

127

128

129

130 return true;

131}

132

133

134

135

138

139

140

141 if (!Processed.insert(I).second)

142 return true;

143

145 return false;

146

147

148

149

151 return false;

152

153

154

155

157 if (Width > 64 || .isLegalInteger(Width))

158 return false;

159

160

161

162 if (EphValues.count(I))

163 return false;

164

165

167

168

169

171 return false;

172

174 for (Use &U : I->uses()) {

176 if (!UniqueUsers.insert(User).second)

177 continue;

178

179

180 if (isa(User) && Processed.count(User))

181 continue;

182

183

184

185

186

187

188

189 bool AddUserToIVUsers = false;

191 if (isa(User) || Processed.count(User) ||

194 << " OF SCEV: " << *ISE << '\n');

195 AddUserToIVUsers = true;

196 }

199 << " OF SCEV: " << *ISE << '\n');

200 AddUserToIVUsers = true;

201 }

202

203 if (AddUserToIVUsers) {

204

206

207

208

209 const SCEV *OriginalISE = ISE;

210

212 auto *L = AR->getLoop();

214 if (Result)

215 NewUse.PostIncLoops.insert(L);

216 return Result;

217 };

218

220

221

222

223

224

225 if (OriginalISE != ISE) {

226 const SCEV *DenormalizedISE =

228

229

230

231 if (OriginalISE != DenormalizedISE) {

233 << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): "

234 << *ISE << '\n');

235 IVUses.pop_back();

236 return false;

237 }

238 }

240 << " NORMALIZED TO: " << *ISE << '\n');

241 }

242 }

243 return true;

244}

245

248 return IVUses.back();

249}

250

253 : L(L), AC(AC), LI(LI), DT(DT), SE(SE) {

254

255 EphValues.clear();

257

258

259

260

263}

264

266 OS << "IV Users for loop ";

270 }

271 OS << ":\n";

272

273 for (const IVStrideUse &IVUse : IVUses) {

274 OS << " ";

275 IVUse.getOperandValToReplace()->printAsOperand(OS, false);

277 for (const auto *PostIncLoop : IVUse.PostIncLoops) {

278 OS << " (post-inc with loop ";

279 PostIncLoop->getHeader()->printAsOperand(OS, false);

280 OS << ")";

281 }

282 OS << " in ";

283 if (IVUse.getUser())

284 IVUse.getUser()->print(OS);

285 else

286 OS << "Printing User";

287 OS << '\n';

288 }

289}

290

291#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

293#endif

294

296 Processed.clear();

297 IVUses.clear();

298}

299

302}

303

310}

311

313 auto *AC = &getAnalysis().getAssumptionCache(

314 *L->getHeader()->getParent());

315 auto *LI = &getAnalysis().getLoopInfo();

316 auto *DT = &getAnalysis().getDomTree();

317 auto *SE = &getAnalysis().getSE();

318

319 IU.reset(new IVUsers(L, AC, LI, DT, SE));

320 return false;

321}

322

324 IU->print(OS, M);

325}

326

328

329

330

333}

334

335

339}

340

342 if (const SCEVAddRecExpr *AR = dyn_cast(S)) {

343 if (AR->getLoop() == L)

344 return AR;

346 }

347

348 if (const SCEVAddExpr *Add = dyn_cast(S)) {

349 for (const SCEV *Op : Add->operands())

351 return AR;

352 return nullptr;

353 }

354

355 return nullptr;

356}

357

360 if (!Expr)

361 return nullptr;

363 return AR->getStepRecurrence(*SE);

364 return nullptr;

365}

366

368 PostIncLoops.insert(L);

369}

370

371void IVStrideUse::deleted() {

372

373 Parent->Processed.erase(this->getUser());

374 Parent->IVUses.erase(this);

375

376}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

Module.h This file contains the declarations for the Module class.

static const SCEVAddRecExpr * findAddRecForLoop(const SCEV *S, const Loop *L)

iv Induction Variable Users

static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, ScalarEvolution *SE, LoopInfo *LI)

isInteresting - Test whether the given expression is "interesting" when used by the given expression,...

static bool IVUseShouldUsePostIncValue(Instruction *User, Value *Operand, const Loop *L, DominatorTree *DT)

IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression and now we need to decid...

This header provides classes for managing per-loop analyses.

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

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

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

void setPreservesAll()

Set by analyses that do not transform their input at all.

An immutable pass that tracks lazily created AssumptionCache objects.

A cache of @llvm.assume calls within a function.

LLVM Basic Block Representation.

InstListType::iterator iterator

Instruction iterators...

This class represents an Operation in the Expression.

A parsed version of the target data layout string in and methods for querying it.

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

IVStrideUse - Keep track of one use of a strided induction variable.

Instruction * getUser() const

getUser - Return the user instruction for this use.

const PostIncLoopSet & getPostIncLoops() const

getPostIncLoops - Return the set of loops for which the expression has been adjusted to use post-inc ...

void transformToPostInc(const Loop *L)

transformToPostInc - Transform the expression to post-inc form for the given loop.

Value * getOperandValToReplace() const

getOperandValToReplace - Return the Value of the operand in the user instruction that this IVStrideUs...

IVUsers run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)

void getAnalysisUsage(AnalysisUsage &AU) const override

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

bool runOnLoop(Loop *L, LPPassManager &LPM) override

void print(raw_ostream &OS, const Module *=nullptr) const override

print - Print out the internal state of the pass.

void releaseMemory() override

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...

void dump() const

dump - This method is used for debugging.

IVStrideUse & AddUser(Instruction *User, Value *Operand)

IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)

const SCEV * getStride(const IVStrideUse &IU, const Loop *L) const

const SCEV * getReplacementExpr(const IVStrideUse &IU) const

getReplacementExpr - Return a SCEV expression which computes the value of the OperandValToReplace of ...

bool AddUsersIfInteresting(Instruction *I)

AddUsersIfInteresting - Inspect the specified Instruction.

const SCEV * getExpr(const IVStrideUse &IU) const

getExpr - Return the expression for the use.

void print(raw_ostream &OS, const Module *=nullptr) const

BlockT * getHeader() const

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.

A Module instance is used to store all the information related to an LLVM module.

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

unsigned getNumIncomingValues() const

Return the number of incoming edges.

static PassRegistry * getPassRegistry()

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

Pass interface - Implemented by all 'passes'.

This node represents an addition of some number of SCEVs.

This node represents a polynomial recurrence on the trip count of the specified loop.

This class represents an analyzed expression in the program.

The main scalar evolution driver.

const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)

Return a SCEV expression for the specified value at the specified scope in the program.

const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)

If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...

uint64_t getTypeSizeInBits(Type *Ty) const

Return the size in bits of the specified type, for which isSCEVable must return true.

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.

bool hasLoopInvariantBackedgeTakenCount(const Loop *L)

Return true if the specified loop has an analyzable loop-invariant backedge-taken count.

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.

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

LLVM Value Representation.

void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const

Print the name of this Value out to the specified raw_ostream.

This class implements an extremely fast bulk output stream that can only output to a stream.

This is an optimization pass for GlobalISel generic memory operations.

const SCEV * denormalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)

Denormalize S to be post-increment for all loops present in Loops.

raw_ostream & dbgs()

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

void initializeIVUsersWrapperPassPass(PassRegistry &)

bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)

Return true if the instruction does not have any effects besides calculating the result and does not ...

const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE, bool CheckInvertible=true)

Normalize S to be post-increment for all loops present in Loops.

Pass * createIVUsersPass()

const SCEV * normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred, ScalarEvolution &SE)

Normalize S for all add recurrence sub-expressions for which Pred returns true.

A special type used by analysis passes to provide an address that identifies that particular analysis...

static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)

Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).

The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...