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 SCEVExpander Expander(SE, "lsr_fold_term_cond");

122

123 PHINode *ToHelpFold = nullptr;

124 const SCEV *TermValueS = nullptr;

125 bool MustDropPoison = false;

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

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

128 if (ToFold == &PN)

129 continue;

130

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

134 "terminating condition folding.\n");

135 continue;

136 }

138

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

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

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

143 continue;

144 }

145

146

147

148

149

150

151

152

153

154

157 continue;

158

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

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

164 << "\n");

165 continue;

166 }

167

169 InsertPt)) {

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

172 << PN << "\n");

173 continue;

174 }

175

176

177

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

180 continue;

181 }

182

183

184

185

186

187 bool MustDropPoisonLocal = false;

191 &DT)) {

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

193 << "\n");

194

195

196

197

199 continue;

200

201

202

204 }

205

206

207

208 ToHelpFold = &PN;

209 TermValueS = TermValueSLocal;

210 MustDropPoison = MustDropPoisonLocal;

211 }

212

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

215

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

219 << " TermCond: " << *TermCond << "\n"

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

221 << " ToFold: " << *ToFold << "\n"

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

223

224 if (!ToFold || !ToHelpFold)

225 return std::nullopt;

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

227}

228

232 std::unique_ptr MSSAU;

233 if (MSSA)

234 MSSAU = std::make_unique(MSSA);

235

237 if (!Opt)

238 return false;

239

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

241

242 NumTermFold++;

243

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

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

246

247 (void)ToFold;

249 << *ToFold << "\n"

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

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

252

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

254 (void)StartValue;

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

256

257

258 if (MustDrop)

260

261

262 SCEVExpander Expander(SE, "lsr_fold_term_cond");

263

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

266

267

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

270

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

272 << *StartValue << "\n"

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

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

275

276

280 Value *NewTermCond =

282 "lsr_fold_term_cond.replaced_term_cond");

283

286

288 << *OldTermCond << "\n"

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

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

291

293

294 Expander.clear();

297 return true;

298}

299

300namespace {

301

302class LoopTermFold : public LoopPass {

303public:

304 static char ID;

305

306 LoopTermFold();

307

308private:

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

310 void getAnalysisUsage(AnalysisUsage &AU) const override;

311};

312

313}

314

315LoopTermFold::LoopTermFold() : LoopPass(ID) {

317}

318

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

324 AU.addRequired();

326 AU.addRequired();

327 AU.addPreserved();

328 AU.addRequired();

329 AU.addRequired();

331}

332

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

334 if (skipLoop(L))

335 return false;

336

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

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

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

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

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

342 auto &TLI = getAnalysis().getTLI(

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

344 auto *MSSAAnalysis = getAnalysisIfAvailable();

346 if (MSSAAnalysis)

347 MSSA = &MSSAAnalysis->getMSSA();

349}

350

362

363char LoopTermFold::ID = 0;

364

366 false, false)

374

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

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:229

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

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:351

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:375

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