ScalarEvolutionDivision.cpp Source File (original) (raw)

21#include

22#include

24#define DEBUG_TYPE "scev-division"

26namespace llvm {

28}

30using namespace llvm;

33 struct FindSCEVSize {

36 FindSCEVSize() = default;

38 bool follow(const SCEV *S) {

41 return true;

42 }

44 bool isDone() const { return false; }

45 };

47 FindSCEVSize F;

49 ST.visitAll(S);

50 return F.Size;

51}

56 const SCEV *Denominator, const SCEV **Quotient,

57 const SCEV **Remainder) {

58 assert(Numerator && Denominator && "Uninitialized SCEV");

60 SCEVDivision D(SE, Numerator, Denominator);

64 if (Numerator == Denominator) {

65 *Quotient = D.One;

66 *Remainder = D.Zero;

67 return;

68 }

70 if (Numerator->isZero()) {

71 *Quotient = D.Zero;

72 *Remainder = D.Zero;

73 return;

74 }

77 if (Denominator->isOne()) {

78 *Quotient = Numerator;

79 *Remainder = D.Zero;

80 return;

81 }

85 const SCEV *Q, *R;

86 *Quotient = Numerator;

87 for (const SCEV *Op : T->operands()) {

88 divide(SE, *Quotient, Op, &Q, &R);

89 *Quotient = Q;

93 if (!R->isZero()) {

94 *Quotient = D.Zero;

95 *Remainder = Numerator;

96 return;

97 }

98 }

99 *Remainder = D.Zero;

100 return;

101 }

102

103 D.visit(Numerator);

104 *Quotient = D.Quotient;

105 *Remainder = D.Remainder;

106}

107

111 APInt DenominatorVal = D->getAPInt();

114

115 if (NumeratorBW > DenominatorBW)

116 DenominatorVal = DenominatorVal.sext(NumeratorBW);

117 else if (NumeratorBW < DenominatorBW)

118 NumeratorVal = NumeratorVal.sext(DenominatorBW);

119

122 APInt::sdivrem(NumeratorVal, DenominatorVal, QuotientVal, RemainderVal);

123 Quotient = SE.getConstant(QuotientVal);

124 Remainder = SE.getConstant(RemainderVal);

125 return;

126 }

127}

128

130 return cannotDivide(Numerator);

131}

132

134 const SCEV *StartQ, *StartR, *StepQ, *StepR;

136 return cannotDivide(Numerator);

137 divide(SE, Numerator->getStart(), Denominator, &StartQ, &StartR);

139

140 Type *Ty = Denominator->getType();

141 if (Ty != StartQ->getType() || Ty != StartR->getType() ||

143 return cannotDivide(Numerator);

144 Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(),

146 Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(),

148}

149

152 Type *Ty = Denominator->getType();

153

155 const SCEV *Q, *R;

156 divide(SE, Op, Denominator, &Q, &R);

157

158

159 if (Ty != Q->getType() || Ty != R->getType())

160 return cannotDivide(Numerator);

161

164 }

165

166 if (Qs.size() == 1) {

167 Quotient = Qs[0];

168 Remainder = Rs[0];

169 return;

170 }

171

172 Quotient = SE.getAddExpr(Qs);

173 Remainder = SE.getAddExpr(Rs);

174}

175

178 Type *Ty = Denominator->getType();

179

180 bool FoundDenominatorTerm = false;

182

183 if (Ty != Op->getType())

184 return cannotDivide(Numerator);

185

186 if (FoundDenominatorTerm) {

188 continue;

189 }

190

191

192 const SCEV *Q, *R;

193 divide(SE, Op, Denominator, &Q, &R);

194 if (!R->isZero()) {

196 continue;

197 }

198

199

201 return cannotDivide(Numerator);

202

203 FoundDenominatorTerm = true;

205 }

206

207 if (FoundDenominatorTerm) {

208 Remainder = Zero;

209 if (Qs.size() == 1)

210 Quotient = Qs[0];

211 else

212 Quotient = SE.getMulExpr(Qs);

213 return;

214 }

215

217 return cannotDivide(Numerator);

218

219

223

224 if (Remainder->isZero()) {

225

228 return;

229 }

230

231

232 const SCEV *Q, *R;

233 const SCEV *Diff = SE.getMinusSCEV(Numerator, Remainder);

234

236 return cannotDivide(Numerator);

237 divide(SE, Diff, Denominator, &Q, &R);

238 if (R != Zero)

239 return cannotDivide(Numerator);

240 Quotient = Q;

241}

242

244 const SCEV *Denominator)

245 : SE(S), Denominator(Denominator) {

248

249

250

251 cannotDivide(Numerator);

252}

253

254

255

256void SCEVDivision::cannotDivide(const SCEV *Numerator) {

257 Quotient = Zero;

258 Remainder = Numerator;

259}

260

262 OS << "Printing analysis 'Scalar Evolution Division' for function '"

263 << F.getName() << "':\n";

266 if (!Div || Div->getOpcode() != Instruction::SDiv)

267 continue;

268

271 const SCEV *Quotient, *Remainder;

273

274 OS << "Instruction: " << *Div << "\n";

275 OS.indent(2) << "Numerator: " << *Numerator << "\n";

276 OS.indent(2) << "Denominator: " << *Denominator << "\n";

277 OS.indent(2) << "Quotient: " << *Quotient << "\n";

278 OS.indent(2) << "Remainder: " << *Remainder << "\n";

279 }

280}

281

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

This file implements a class to represent arbitrary precision integral constant values and operations...

Expand Atomic instructions

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

This file defines the DenseMap class.

static int sizeOfSCEV(const SCEV *S)

Definition ScalarEvolutionDivision.cpp:32

This file defines the SmallVector class.

Class for arbitrary precision integers.

static LLVM_ABI void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)

unsigned getBitWidth() const

Return the number of bits in the APInt.

LLVM_ABI APInt sext(unsigned width) const

Sign extend to a new width.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

BinaryOps getOpcode() const

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 an addition of some number of SCEVs.

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

const SCEV * getStart() const

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 Loop * getLoop() const

This class represents a constant integer value.

const APInt & getAPInt() const

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition ScalarEvolutionDivision.cpp:282

This node represents multiplication of some number of SCEVs.

NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const

ArrayRef< const SCEV * > operands() const

static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToSCEVMapTy &Map)

Visit all nodes in the expression tree using worklist traversal.

This class represents the value of vscale, as used when defining the length of a scalable vector or r...

This class represents an analyzed expression in the program.

LLVM_ABI bool isZero() const

Return true if the expression is a constant zero.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

Analysis pass that exposes the ScalarEvolution for a function.

The main scalar evolution driver.

const SCEV * getZero(Type *Ty)

Return a SCEV for the constant 0 of a specific type.

LLVM_ABI const SCEV * getSCEV(Value *V)

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

const SCEV * getOne(Type *Ty)

Return a SCEV for the constant 1 of a specific type.

void push_back(const T &Elt)

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

The instances of the Type class are immutable: once they are created, they are never changed.

Value * getOperand(unsigned i) const

This is an optimization pass for GlobalISel generic memory operations.

DenseMap< const Value *, const SCEV * > ValueToSCEVMapTy

decltype(auto) dyn_cast(const From &Val)

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

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

static void divide(ScalarEvolution &SE, const SCEV *Numerator, const SCEV *Denominator, const SCEV **Quotient, const SCEV **Remainder)

Computes the Quotient and Remainder of the division of Numerator by Denominator.

Definition ScalarEvolutionDivision.cpp:55

void visitVScale(const SCEVVScale *Numerator)

Definition ScalarEvolutionDivision.cpp:129

void visitAddRecExpr(const SCEVAddRecExpr *Numerator)

Definition ScalarEvolutionDivision.cpp:133

void visitConstant(const SCEVConstant *Numerator)

Definition ScalarEvolutionDivision.cpp:108

void visitAddExpr(const SCEVAddExpr *Numerator)

Definition ScalarEvolutionDivision.cpp:150

void visitMulExpr(const SCEVMulExpr *Numerator)

Definition ScalarEvolutionDivision.cpp:176