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;

73 auto *TermCond = dyn_cast(BI->getCondition());

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 }

86 BinaryOperator *LHS = dyn_cast(TermCond->getOperand(0));

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;

190 cast(PN.getIncomingValueForBlock(LoopLatch));

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)

260 cast(LoopValue)->dropPoisonGeneratingFlags();

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:

313};

314

315}

316

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

319}

320

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

333}

334

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

358

362 return PA;

363}

364

365char LoopTermFold::ID = 0;

366

368 false, false)

376

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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)

loop term Loop Terminator Folding

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

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)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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.

A container for analyses that lazily runs them and caches their results.

Represent the analysis usage information of a pass.

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)

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

InstListType::iterator eraseFromParent()

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

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.

virtual bool runOnLoop(Loop *L, LPPassManager &LPM)=0

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

Represents a single loop in the control flow graph.

An analysis that produces MemorySSA for a function.

Legacy analysis pass which computes MemorySSA.

Encapsulates MemorySSA, including all data associated with memory accesses.

static PassRegistry * getPassRegistry()

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

Pass interface - Implemented by all 'passes'.

virtual void getAnalysisUsage(AnalysisUsage &) const

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

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.

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.

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

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.

bool isKnownNonZero(const SCEV *S)

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

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

const SCEV * getSCEV(Value *V)

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

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

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

bool isSCEVable(Type *Ty) const

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

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.

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

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

Returns a loop's estimated trip count based on branch weight metadata.

Pass * createLoopTermFoldPass()

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

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.

raw_ostream & dbgs()

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

cl::opt< unsigned > SCEVCheapExpansionBudget

PreservedAnalyses getLoopPassPreservedAnalyses()

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

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

void initializeLoopTermFoldPass(PassRegistry &)

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

TargetTransformInfo & TTI