LoopTermFold.cpp Source File (original) (raw)

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

41#include

42#include

44using namespace llvm;

46#define DEBUG_TYPE "loop-term-fold"

49 "Number of terminating condition fold recognized and performed");

51static std::optional<std::tuple<PHINode *, PHINode *, const SCEV *, bool>>

54 if (!L->isInnermost()) {

55 LLVM_DEBUG(dbgs() << "Cannot fold on non-innermost loop\n");

56 return std::nullopt;

57 }

59 if (!L->isLoopSimplifyForm()) {

60 LLVM_DEBUG(dbgs() << "Cannot fold on non-simple loop\n");

61 return std::nullopt;

62 }

65 LLVM_DEBUG(dbgs() << "Cannot fold on backedge that is loop variant\n");

66 return std::nullopt;

67 }

69 BasicBlock *LoopLatch = L->getLoopLatch();

72 return std::nullopt;

74 if (!TermCond) {

76 dbgs() << "Cannot fold on branching condition that is not an ICmpInst");

77 return std::nullopt;

78 }

79 if (!TermCond->hasOneUse()) {

82 << "Cannot replace terminating condition with more than one use\n");

83 return std::nullopt;

84 }

87 Value *RHS = TermCond->getOperand(1);

88 if ( LHS || !L->isLoopInvariant(RHS))

91 return std::nullopt;

95 Value *ToFoldStart, *ToFoldStep;

97 return std::nullopt;

100 if (ToFold->getParent() != L->getHeader())

101 return std::nullopt;

102

103

104

106 return std::nullopt;

107

108

109

110 const unsigned ExpansionBudget = [&]() {

113 return std::min(Budget, SmallTC);

115 return std::min(Budget, *SmallTC);

116

117 return Budget;

118 }();

119

121 const DataLayout &DL = L->getHeader()->getDataLayout();

123

124 PHINode *ToHelpFold = nullptr;

125 const SCEV *TermValueS = nullptr;

126 bool MustDropPoison = false;

127 auto InsertPt = L->getLoopPreheader()->getTerminator();

128 for (PHINode &PN : L->getHeader()->phis()) {

129 if (ToFold == &PN)

130 continue;

131

134 << "' is not SCEV-able, not qualified for the "

135 "terminating condition folding.\n");

136 continue;

137 }

139

140 if (!AddRec || !AddRec->isAffine()) {

142 << "' is not an affine add recursion, not qualified "

143 "for the terminating condition folding.\n");

144 continue;

145 }

146

147

148

149

150

151

152

153

154

155

158 continue;

159

161 const SCEV *TermValueSLocal = PostInc->evaluateAtIteration(BECount, SE);

164 dbgs() << "Is not safe to expand terminating value for phi node" << PN

165 << "\n");

166 continue;

167 }

168

170 InsertPt)) {

172 dbgs() << "Is too expensive to expand terminating value for phi node"

173 << PN << "\n");

174 continue;

175 }

176

177

178

180 LLVM_DEBUG(dbgs() << "Can not prove poison safety for IV " << PN << "\n");

181 continue;

182 }

183

184

185

186

187

188 bool MustDropPoisonLocal = false;

192 &DT)) {

193 LLVM_DEBUG(dbgs() << "Can not prove poison safety to insert use" << PN

194 << "\n");

195

196

197

198

200 continue;

201

202

203

205 }

206

207

208

209 ToHelpFold = &PN;

210 TermValueS = TermValueSLocal;

211 MustDropPoison = MustDropPoisonLocal;

212 }

213

215 << "Cannot find other AddRec IV to help folding\n";);

216

218 << "\nFound loop that can fold terminating condition\n"

220 << " TermCond: " << *TermCond << "\n"

221 << " BrandInst: " << *BI << "\n"

222 << " ToFold: " << *ToFold << "\n"

223 << " ToHelpFold: " << *ToHelpFold << "\n");

224

225 if (!ToFold || !ToHelpFold)

226 return std::nullopt;

227 return std::make_tuple(ToFold, ToHelpFold, TermValueS, MustDropPoison);

228}

229

233 std::unique_ptr MSSAU;

234 if (MSSA)

235 MSSAU = std::make_unique(MSSA);

236

238 if (!Opt)

239 return false;

240

241 auto [ToFold, ToHelpFold, TermValueS, MustDrop] = *Opt;

242

243 NumTermFold++;

244

245 BasicBlock *LoopPreheader = L->getLoopPreheader();

246 BasicBlock *LoopLatch = L->getLoopLatch();

247

248 (void)ToFold;

250 << *ToFold << "\n"

251 << "New term-cond phi-node:\n"

252 << *ToHelpFold << "\n");

253

254 Value *StartValue = ToHelpFold->getIncomingValueForBlock(LoopPreheader);

255 (void)StartValue;

256 Value *LoopValue = ToHelpFold->getIncomingValueForBlock(LoopLatch);

257

258

259 if (MustDrop)

261

262

263 const DataLayout &DL = L->getHeader()->getDataLayout();

265

267 "Terminating value was checked safe in canFoldTerminatingCondition");

268

269

270 Value *TermValue = Expander.expandCodeFor(TermValueS, ToHelpFold->getType(),

272

273 LLVM_DEBUG(dbgs() << "Start value of new term-cond phi-node:\n"

274 << *StartValue << "\n"

275 << "Terminating value of new term-cond phi-node:\n"

276 << *TermValue << "\n");

277

278

282 Value *NewTermCond =

284 "lsr_fold_term_cond.replaced_term_cond");

285

288

290 << *OldTermCond << "\n"

291 << "New term-cond:\n"

292 << *NewTermCond << "\n");

293

295

296 Expander.clear();

299 return true;

300}

301

302namespace {

303

304class LoopTermFold : public LoopPass {

305public:

306 static char ID;

307

308 LoopTermFold();

309

310private:

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

312 void getAnalysisUsage(AnalysisUsage &AU) const override;

313};

314

315}

316

317LoopTermFold::LoopTermFold() : LoopPass(ID) {

319}

320

321void LoopTermFold::getAnalysisUsage(AnalysisUsage &AU) const {

326 AU.addRequired();

328 AU.addRequired();

329 AU.addPreserved();

330 AU.addRequired();

331 AU.addRequired();

333}

334

335bool LoopTermFold::runOnLoop(Loop *L, LPPassManager & ) {

336 if (skipLoop(L))

337 return false;

338

339 auto &SE = getAnalysis().getSE();

340 auto &DT = getAnalysis().getDomTree();

341 auto &LI = getAnalysis().getLoopInfo();

342 const auto &TTI = getAnalysis().getTTI(

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

344 auto &TLI = getAnalysis().getTLI(

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

346 auto *MSSAAnalysis = getAnalysisIfAvailable();

348 if (MSSAAnalysis)

349 MSSA = &MSSAAnalysis->getMSSA();

351}

352

364

365char LoopTermFold::ID = 0;

366

368 false, false)

376

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

early cse Early CSE w MemorySSA

This header provides classes for managing per-loop analyses.

static std::optional< std::tuple< PHINode *, PHINode *, const SCEV *, bool > > canFoldTermCondOfLoop(Loop *L, ScalarEvolution &SE, DominatorTree &DT, const LoopInfo &LI, const TargetTransformInfo &TTI)

Definition LoopTermFold.cpp:52

static bool RunTermFold(Loop *L, ScalarEvolution &SE, DominatorTree &DT, LoopInfo &LI, const TargetTransformInfo &TTI, TargetLibraryInfo &TLI, MemorySSA *MSSA)

Definition LoopTermFold.cpp:230

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

This pass exposes codegen information to IR-level passes.

Represent the analysis usage information of a pass.

LLVM_ABI AnalysisUsage & addRequiredID(const void *ID)

AnalysisUsage & addPreservedID(const void *ID)

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

LLVM Basic Block Representation.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Conditional or Unconditional Branch instruction.

void setCondition(Value *V)

LLVM_ABI void swapSuccessors()

Swap the successors of this branch instruction.

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

Value * getCondition() const

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.

This instruction compares its operands according to the predicate given to the constructor.

Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

LLVM_ABI bool hasPoisonGeneratingFlags() const LLVM_READONLY

Return true if this operator has flags which may cause this instruction to evaluate to poison despite...

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

The legacy pass manager's analysis pass to compute loop information.

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

Definition LoopTermFold.cpp:353

Represents a single loop in the control flow graph.

An analysis that produces MemorySSA for a function.

Encapsulates MemorySSA, including all data associated with memory accesses.

static LLVM_ABI PassRegistry * getPassRegistry()

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

Pass interface - Implemented by all 'passes'.

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.

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

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

Constructs and returns the recurrence indicating how much this expression steps by.

bool isAffine() const

Return true if this represents an expression A + B*x where A and B are loop invariant values.

LLVM_ABI const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const

Return an expression representing the value of this expression one iteration of the loop ahead.

This class uses information about analyze scalars to rewrite expressions in canonical form.

LLVM_ABI bool isSafeToExpand(const SCEV *S) const

Return true if the given expression is safe to expand in the sense that all materialized values are s...

bool isHighCostExpansion(ArrayRef< const SCEV * > Exprs, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At)

Return true for expressions that can't be evaluated at runtime within given Budget.

void clear()

Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...

LLVM_ABI Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)

Insert code to directly compute the specified SCEV expression into the program.

bool hasNoSelfWrap() const

This class represents an analyzed expression in the program.

The main scalar evolution driver.

LLVM_ABI bool isKnownNonZero(const SCEV *S)

Test if the given expression is known to be non-zero.

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

LLVM_ABI const SCEV * getSCEV(Value *V)

Return a SCEV expression for the full generality of the specified expression.

LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)

Returns the upper bound of the loop trip count as a normal unsigned value.

LLVM_ABI bool isSCEVable(Type *Ty) const

Test if values of the given type are analyzable within the SCEV framework.

LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)

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

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

Wrapper pass for TargetTransformInfo.

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

Value * getOperand(unsigned i) const

LLVM Value Representation.

const ParentTy * getParent() const

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root, Instruction *OnPathTo, DominatorTree *DT)

Return true if undefined behavior would provable be executed on the path to OnPathTo if Root produced...

LLVM_ABI std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)

Return either:

LLVM_ABI void initializeLoopTermFoldPass(PassRegistry &)

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI char & LoopSimplifyID

LLVM_ABI Pass * createLoopTermFoldPass()

Definition LoopTermFold.cpp:377

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)

Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...

LLVM_ABI bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)

Examine each PHI in the given block and delete it if it is dead.

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget

decltype(auto) cast(const From &Val)

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

LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()

Returns the minimum set of Analyses that all loop passes must preserve.

LLVM_ABI bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond)

Return true if the induction variable IV in a Loop whose latch is LatchBlock would become dead if the...

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

TargetTransformInfo & TTI