IVUsers.cpp Source File (original) (raw)

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

30using namespace llvm;

32#define DEBUG_TYPE "iv-users"

43 "Induction Variable Users", false, true)

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

63 return AR->isAffine() ||

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

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

71 }

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

144 if (!SE->isSCEVable(I->getType()))

145 return false;

146

147

148

149

151 return false;

152

153

154

155

156 uint64_t Width = SE->getTypeSizeInBits(I->getType());

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

158 return false;

159

160

161

162 if (EphValues.count(I))

163 return false;

164

165

166 const SCEV *ISE = SE->getSCEV(I);

167

168

169

171 return false;

172

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

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

177 continue;

178

179

181 continue;

182

183

184

185

186

187

188

189 bool AddUserToIVUsers = false;

190 if (LI->getLoopFor(User->getParent()) != L) {

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

267 L->getHeader()->printAsOperand(OS, false);

268 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {

269 OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L);

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

301

309

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

316

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

318 return false;

319}

320

322 IU->print(OS, M);

323}

324

326

327

328

332

333

338

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

342 return AR;

344 }

345

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

349 return AR;

350 return nullptr;

351 }

352

353 return nullptr;

354}

355

358 if (!Expr)

359 return nullptr;

361 return AR->getStepRecurrence(*SE);

362 return nullptr;

363}

364

366 PostIncLoops.insert(L);

367}

368

370

372 Parent->IVUses.erase(this);

373

374}

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)

Definition IVUsers.cpp:339

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

Definition IVUsers.cpp:56

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

Definition IVUsers.cpp:97

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)

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

virtual void deleted()

Callback for Value destruction.

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.

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.

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.

Definition IVUsers.cpp:365

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)

Definition IVUsers.cpp:36

void getAnalysisUsage(AnalysisUsage &AU) const override

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

Definition IVUsers.cpp:302

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

Definition IVUsers.cpp:310

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

print - Print out the internal state of the pass.

Definition IVUsers.cpp:321

void releaseMemory() override

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

Definition IVUsers.cpp:325

IVUsersWrapperPass()

Definition IVUsers.cpp:300

void dump() const

dump - This method is used for debugging.

Definition IVUsers.cpp:292

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

Definition IVUsers.cpp:246

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

Definition IVUsers.cpp:251

void releaseMemory()

Definition IVUsers.cpp:295

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

Definition IVUsers.cpp:356

const SCEV * getReplacementExpr(const IVStrideUse &IU) const

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

Definition IVUsers.cpp:329

bool AddUsersIfInteresting(Instruction *I)

AddUsersIfInteresting - Inspect the specified Instruction.

Definition IVUsers.cpp:136

const SCEV * getExpr(const IVStrideUse &IU) const

getExpr - Return the expression for the use.

Definition IVUsers.cpp:334

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

Definition IVUsers.cpp:265

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.

Pass interface - Implemented by all 'passes'.

AnalysisType & getAnalysis() const

getAnalysis() - This function is used by subclasses to get to the analysis information ...

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.

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

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

bool erase(PtrType Ptr)

Remove pointer from the set.

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.

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.

decltype(auto) dyn_cast(const From &Val)

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

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

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

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

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

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

LLVM_ABI raw_ostream & dbgs()

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

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

DWARFExpression::Operation Op

Pass * createIVUsersPass()

Definition IVUsers.cpp:51

decltype(auto) cast(const From &Val)

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

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