GVN.h Source File (original) (raw)

15#ifndef LLVM_TRANSFORMS_SCALAR_GVN_H

16#define LLVM_TRANSFORMS_SCALAR_GVN_H

28#include

29#include

30#include

31#include

32#include

34namespace llvm {

104

105

110

111

116

117

122};

123

124

125

126

127

130

131public:

133

135

136

138

141 function_ref<StringRef(StringRef)> MapClassName2PassName);

142

143

144

146

150

157

158

159

160

164

165

166

167

168

170

171 std::vector Expressions;

172 std::vector<uint32_t> ExprIdx;

173

174

176

177

178

180

181

182 using PhiTranslateMap =

184 PhiTranslateMap PhiTranslateTable;

185

188 bool IsMDEnabled = false;

190 bool IsMSSAEnabled = false;

192

193 uint32_t NextValueNumber = 1;

194

206 std::pair<uint32_t, bool> assignExpNewValueNum(Expression &Exp);

209

210 public:

216

234 MD = M;

235 IsMDEnabled = MDEnabled;

236 }

238 MSSA = M;

239 IsMSSAEnabled = MSSAEnabled;

240 }

244 };

245

246private:

249

259

261

262

263

264 class LeaderMap {

265 public:

270

271 private:

272 struct LeaderListNode {

274 LeaderListNode *Next;

275 };

278

279 public:

281 const LeaderListNode *Current;

282

283 public:

289

292 assert(Current && "Dereferenced end of leader list!");

293 Current = Current->Next;

294 return *this;

295 }

297 return Current == Other.Current;

298 }

300 return Current != Other.Current;

301 }

303 };

304

306 auto I = NumToLeaders.find(N);

307 if (I == NumToLeaders.end()) {

309 leader_iterator(nullptr));

310 }

311

313 leader_iterator(nullptr));

314 }

315

316 LLVM_ABI void insert(uint32_t N, Value *V, const BasicBlock *BB);

317 LLVM_ABI void erase(uint32_t N, Instruction *I, const BasicBlock *BB);

318 LLVM_ABI void verifyRemoved(const Value *Inst) const;

319 void clear() {

320 NumToLeaders.clear();

321 TableAllocator.Reset();

322 }

323 };

324 LeaderMap LeaderTable;

325

326

327

328 DenseMap<AssertingVH, uint32_t> BlockRPONumber;

329

330

331

332

333 bool InvalidBlockRPONumbers = true;

334

335 using LoadDepVect = SmallVector<NonLocalDepResult, 64>;

336 using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;

337 using UnavailBlkVect = SmallVector<BasicBlock *, 64>;

338

339 bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,

340 const TargetLibraryInfo &RunTLI, AAResults &RunAA,

341 MemoryDependenceResults *RunMD, LoopInfo &LI,

342 OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);

343

344

346

347

348 bool processLoad(LoadInst *L);

349 bool processMaskedLoad(IntrinsicInst *I);

350 bool processNonLocalLoad(LoadInst *L);

351 bool processAssumeIntrinsic(AssumeInst *II);

352

353

354

355 std::optionalgvn::AvailableValue

356 AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, Value *Address);

357

358

359

360

361 void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,

362 AvailValInBlkVect &ValuesPerBlock,

363 UnavailBlkVect &UnavailableBlocks);

364

365

366

367 LoadInst *findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,

368 LoadInst *Load);

369

370 bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,

371 UnavailBlkVect &UnavailableBlocks);

372

373

374

375

376 bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,

377 UnavailBlkVect &UnavailableBlocks);

378

379

380

381 void eliminatePartiallyRedundantLoad(

382 LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,

383 MapVector<BasicBlock *, Value *> &AvailableLoads,

384 MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad);

385

386

387 bool processInstruction(Instruction *I);

388 bool processBlock(BasicBlock *BB);

389 void dump(DenseMap<uint32_t, Value *> &Map) const;

390 bool iterateOnFunction(Function &F);

391 bool performPRE(Function &F);

392 bool performScalarPRE(Instruction *I);

393 bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,

394 BasicBlock *Curr, unsigned int ValNo);

395 Value *findLeader(const BasicBlock *BB, uint32_t Num);

396 void cleanupGlobalSets();

397 void removeInstruction(Instruction *I);

398 void verifyRemoved(const Instruction *I) const;

399 bool splitCriticalEdges();

400 BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);

401 bool

403 const std::variant<BasicBlockEdge, Instruction *> &Root);

404 bool processFoldableCondBr(BranchInst *BI);

405 void addDeadBlock(BasicBlock *BB);

406 void assignValNumForDeadCode();

407 void assignBlockRPONumber(Function &F);

408};

409

410

412

413

414

419

420

421

426

427}

428

429#endif

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

This file defines the BumpPtrAllocator interface.

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

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

#define LLVM_LIBRARY_VISIBILITY_NAMESPACE

This file defines the DenseMap class.

early cse Early CSE w MemorySSA

This header defines various interfaces for pass management in LLVM.

This file implements a map that provides insertion order iteration.

uint64_t IntrinsicInst * II

ppc ctr loops PowerPC CTR Loops Verify

This file implements a set that has insertion order iteration characteristics.

This file defines the SmallVector class.

This represents the llvm.assume intrinsic.

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

LLVM Basic Block Representation.

Conditional or Unconditional Branch instruction.

This class represents a function call, abstracting a target machine's calling convention.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

iterator find(const_arg_type_t< KeyT > Val)

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

FunctionPass class - This class is used to implement most global optimizations.

const LeaderTableEntry value_type

Definition GVN.h:285

std::forward_iterator_tag iterator_category

Definition GVN.h:284

bool operator==(const leader_iterator &Other) const

Definition GVN.h:296

value_type * pointer

Definition GVN.h:287

bool operator!=(const leader_iterator &Other) const

Definition GVN.h:299

leader_iterator(const LeaderListNode *C)

Definition GVN.h:290

leader_iterator & operator++()

Definition GVN.h:291

value_type & reference

Definition GVN.h:288

std::ptrdiff_t difference_type

Definition GVN.h:286

reference operator*() const

Definition GVN.h:302

This class holds the mapping between values and value numbers.

Definition GVN.h:161

void setMemDep(MemoryDependenceResults *M, bool MDEnabled=true)

Definition GVN.h:233

LLVM_ABI ValueTable(ValueTable &&Arg)

void setMemorySSA(MemorySSA *M, bool MSSAEnabled=false)

Definition GVN.h:237

LLVM_ABI uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS)

Returns the value number of the given comparison, assigning it a new number if it did not have one be...

uint32_t getNextUnusedValueNumber()

Definition GVN.h:242

LLVM_ABI uint32_t lookup(Value *V, bool Verify=true) const

Returns the value number of the specified value.

LLVM_ABI ValueTable & operator=(const ValueTable &Arg)

void setAliasAnalysis(AAResults *A)

Definition GVN.h:231

LLVM_ABI void add(Value *V, uint32_t Num)

add - Insert a value into the table with a specified value number.

LLVM_ABI void clear()

Remove all entries from the ValueTable.

LLVM_ABI bool exists(Value *V) const

Returns true if a value number exists for the specified value.

LLVM_ABI ValueTable(const ValueTable &Arg)

LLVM_ABI uint32_t lookupOrAdd(MemoryAccess *MA)

AAResults * getAliasAnalysis() const

Definition GVN.h:232

LLVM_ABI uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVNPass &GVN)

Wrap phiTranslateImpl to provide caching functionality.

void setDomTree(DominatorTree *D)

Definition GVN.h:241

LLVM_ABI void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock)

Erase stale entry from phiTranslate cache so phiTranslate can be computed again.

LLVM_ABI void erase(Value *V)

Remove a value from the value numbering.

LLVM_ABI void verifyRemoved(const Value *) const

verifyRemoved - Verify that the value is removed from all internal data structures.

LLVM_ABI bool isPREEnabled() const

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Run the pass over the function.

LLVM_ABI void salvageAndRemoveInstruction(Instruction *I)

This removes the specified instruction from our various maps and marks it for deletion.

AAResults * getAliasAnalysis() const

Definition GVN.h:148

LLVM_ABI bool isLoadPREEnabled() const

GVNPass(GVNOptions Options={})

Definition GVN.h:134

LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)

LLVM_ABI bool isMemorySSAEnabled() const

DominatorTree & getDominatorTree() const

Definition GVN.h:147

LLVM_ABI bool isLoadInLoopPREEnabled() const

LLVM_ABI bool isLoadPRESplitBackedgeEnabled() const

LLVM_ABI bool isMemDepEnabled() const

MemoryDependenceResults & getMemDep() const

Definition GVN.h:149

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

This class allows to keep track on instructions with implicit control flow.

A wrapper class for inspecting calls to intrinsic functions.

An instruction for reading from memory.

A memory dependence query can return one of three different answers.

Provides a lazy, caching interface for making common memory aliasing information queries,...

Representation for a specific memory location.

Encapsulates MemorySSA, including all data associated with memory accesses.

This is a result from a NonLocal dependence query.

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

A vector that has set insertion semantics.

Provides information about what library functions are available for the current target.

LLVM Value Representation.

A range adaptor for a pair of iterators.

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

A private "module" namespace for types and utilities used by GVN.

Definition GVN.h:63

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >

LLVM_ABI FunctionPass * createGVNPass()

Create a legacy GVN pass.

FunctionAddr VTableAddr Next

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

BumpPtrAllocatorImpl<> BumpPtrAllocator

The standard BumpPtrAllocator which just uses the default template parameters.

An information struct used to provide DenseMap with the various necessary components for a given valu...

A simple and fast domtree-based GVN pass to hoist common expressions from sibling branches.

Definition GVN.h:415

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Run the pass over the function.

A set of parameters to control various transforms performed by GVN pass.

Definition GVN.h:78

GVNOptions & setLoadPRE(bool LoadPRE)

Enables or disables PRE of loads in GVN.

Definition GVN.h:95

std::optional< bool > AllowLoadPRESplitBackedge

Definition GVN.h:82

GVNOptions & setPRE(bool PRE)

Enables or disables PRE in GVN.

Definition GVN.h:89

GVNOptions & setLoadInLoopPRE(bool LoadInLoopPRE)

Definition GVN.h:100

std::optional< bool > AllowPRE

Definition GVN.h:79

std::optional< bool > AllowLoadInLoopPRE

Definition GVN.h:81

std::optional< bool > AllowMemDep

Definition GVN.h:83

GVNOptions & setMemDep(bool MemDep)

Enables or disables use of MemDepAnalysis.

Definition GVN.h:112

std::optional< bool > AllowLoadPRE

Definition GVN.h:80

GVNOptions & setLoadPRESplitBackedge(bool LoadPRESplitBackedge)

Enables or disables PRE of loads in GVN.

Definition GVN.h:106

std::optional< bool > AllowMemorySSA

Definition GVN.h:84

GVNOptions & setMemorySSA(bool MemSSA)

Enables or disables use of MemorySSA.

Definition GVN.h:118

Value * Val

Definition GVN.h:267

const BasicBlock * BB

Definition GVN.h:268

Uses an "inverted" value numbering to decide the similarity of expressions and sinks similar expressi...

Definition GVN.h:422

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Run the pass over the function.

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

Represents an AvailableValue which can be rematerialized at the end of the associated BasicBlock.

Represents a particular available value that we know how to materialize.