LoopCacheAnalysis.h Source File (original) (raw)

14#ifndef LLVM_ANALYSIS_LOOPCACHEANALYSIS_H

15#define LLVM_ANALYSIS_LOOPCACHEANALYSIS_H

20#include

22namespace llvm {

52public:

57 bool isValid() const { return IsValid; }

62 return Subscripts[SubNum];

63 }

65 assert(!Subscripts.empty() && "Expecting non-empty container");

66 return Subscripts.front();

67 }

69 assert(!Subscripts.empty() && "Expecting non-empty container");

70 return Subscripts.back();

71 }

85 unsigned MaxDistance, const Loop &L,

99private:

100

102

103

104 bool tryDelinearizeFixedSize(const SCEV *AccessFn,

106 const SCEV *ElementSize);

107

108

109 bool isLoopInvariant(const Loop &L) const;

110

111

112

113

114

115

116 bool isConsecutive(const Loop &L, const SCEV *&Stride, unsigned CLS) const;

117

118

119

120

121

122

123 int getSubscriptIndex(const Loop &L) const;

124

125

126 const SCEV *getLastCoefficient() const;

127

128

129

130 bool isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,

131 const Loop &L) const;

132

133

134

135 bool isSimpleAddRecurrence(const SCEV &Subscript, const Loop &L) const;

136

137

138

140

141private:

142

143 bool IsValid = false;

144

145

147

148

149 const SCEV *BasePointer = nullptr;

150

151

153

154

156

158};

159

160

161

162

163

164

165

166

167

168

169

170

171

172

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

193 using LoopTripCountTy = std::pair<const Loop *, unsigned>;

194 using LoopCacheCostTy = std::pair<const Loop *, CacheCostTy>;

195

196public:

197

198

199

200

203 std::optional TRT = std::nullopt);

204

205

206

207

208

209 static std::unique_ptr

211 std::optional TRT = std::nullopt);

212

213

214

216 auto IT = llvm::find_if(LoopCosts, [&L](const LoopCacheCostTy &LCC) {

217 return LCC.first == &L;

218 });

219 return (IT != LoopCosts.end()) ? (*IT).second : -1;

220 }

221

222

224

225private:

226

227

228 void calculateCacheFootprint();

229

230

231

232

233 bool populateReferenceGroups(ReferenceGroupsTy &RefGroups) const;

234

235

236

239

240

241

242

243

244

245

246

247

248

249

251 const Loop &L) const;

252

253

254 void sortLoopCosts() {

256 [](const LoopCacheCostTy &A, const LoopCacheCostTy &B) {

257 return A.second > B.second;

258 });

259 }

260

261private:

262

264

265

266 SmallVector<LoopTripCountTy, 3> TripCounts;

267

268

269 SmallVector<LoopCacheCostTy, 3> LoopCosts;

270

271

272

273 std::optional TRT;

274

275 const LoopInfo &LI;

276 ScalarEvolution &SE;

277 TargetTransformInfo &TTI;

278 AAResults &AA;

279 DependenceInfo &DI;

280};

281

284

285

288

289public:

291

294

296};

297

298}

299

300#endif

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

static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))

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

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

This header defines various interfaces for pass management in LLVM.

This file defines an InstructionCost class that is used when calculating the cost of an instruction,...

This header provides classes for managing per-loop analyses.

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

CacheCost represents the estimated cost of a inner loop as the number of cache lines used by the memo...

Definition LoopCacheAnalysis.h:191

CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI, ScalarEvolution &SE, TargetTransformInfo &TTI, AAResults &AA, DependenceInfo &DI, std::optional< unsigned > TRT=std::nullopt)

Construct a CacheCost object for the loop nest described by Loops.

ArrayRef< LoopCacheCostTy > getLoopCosts() const

Return the estimated ordered loop costs.

Definition LoopCacheAnalysis.h:223

static std::unique_ptr< CacheCost > getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR, DependenceInfo &DI, std::optional< unsigned > TRT=std::nullopt)

Create a CacheCost for the loop nest rooted by Root.

friend raw_ostream & operator<<(raw_ostream &OS, const CacheCost &CC)

CacheCostTy getLoopCost(const Loop &L) const

Return the estimated cost of loop L if the given loop is part of the loop nest associated with this o...

Definition LoopCacheAnalysis.h:215

DependenceInfo - This class is the main dependence-analysis driver.

Represents a memory reference as a base pointer and a set of indexing operations.

Definition LoopCacheAnalysis.h:49

const SCEV * getBasePointer() const

Definition LoopCacheAnalysis.h:58

CacheCostTy computeRefCost(const Loop &L, unsigned CLS) const

Compute the cost of the reference w.r.t.

const SCEV * getSubscript(unsigned SubNum) const

Definition LoopCacheAnalysis.h:60

const SCEV * getFirstSubscript() const

Definition LoopCacheAnalysis.h:64

friend raw_ostream & operator<<(raw_ostream &OS, const IndexedReference &R)

std::optional< bool > hasSpacialReuse(const IndexedReference &Other, unsigned CLS, AAResults &AA) const

Return true/false if the current object and the indexed reference Other are/aren't in the same cache ...

std::optional< bool > hasTemporalReuse(const IndexedReference &Other, unsigned MaxDistance, const Loop &L, DependenceInfo &DI, AAResults &AA) const

Return true if the current object and the indexed reference Other have distance smaller than MaxDista...

IndexedReference(Instruction &StoreOrLoadInst, const LoopInfo &LI, ScalarEvolution &SE)

Construct an indexed reference given a StoreOrLoadInst instruction.

bool isValid() const

Definition LoopCacheAnalysis.h:57

const SCEV * getLastSubscript() const

Definition LoopCacheAnalysis.h:68

size_t getNumSubscripts() const

Definition LoopCacheAnalysis.h:59

This class provides an interface for updating the loop pass manager based on mutations to the loop ne...

static bool isRequired()

Definition LoopCacheAnalysis.h:295

LoopCachePrinterPass(raw_ostream &OS)

Definition LoopCacheAnalysis.h:290

PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)

Represents a single loop in the control flow graph.

A set of analyses that are preserved following a run of a transformation pass.

This class represents an analyzed expression in the program.

The main scalar evolution driver.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

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

Abstract Attribute helper functions.

This is an optimization pass for GlobalISel generic memory operations.

void stable_sort(R &&Range)

InstructionCost CacheCostTy

Definition LoopCacheAnalysis.h:35

SmallVector< std::unique_ptr< IndexedReference >, 8 > ReferenceGroupTy

A reference group represents a set of memory references that exhibit temporal or spacial reuse.

Definition LoopCacheAnalysis.h:173

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

SmallVector< Loop *, 8 > LoopVectorTy

Definition LoopCacheAnalysis.h:36

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

void delinearize(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)

Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an array...

auto find_if(R &&Range, UnaryPredicate P)

Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.

SmallVector< ReferenceGroupTy, 8 > ReferenceGroupsTy

Definition LoopCacheAnalysis.h:174

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

A CRTP mix-in to automatically provide informational APIs needed for passes.