blob: ceded879b0f7396020393fd5749c5902d20bf0a8 [file] [log] [blame]
Chris Lattner53e677a2004-04-02 20:23:17 +00001//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002//
Chris Lattner53e677a2004-04-02 20:23:17 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukman2b37d7c2005-04-21 21:13:18 +00007//
Chris Lattner53e677a2004-04-02 20:23:17 +00008//===----------------------------------------------------------------------===//
9//
10// This file contains the implementation of the scalar evolution analysis
11// engine, which is used primarily to analyze expressions involving induction
12// variables in loops.
13//
14// There are several aspects to this library. First is the representation of
15// scalar expressions, which are represented as subclasses of the SCEV class.
16// These classes are used to represent certain types of subexpressions that we
17// can handle. These classes are reference counted, managed by the SCEVHandle
18// class. We only create one SCEV of a particular shape, so pointer-comparisons
19// for equality are legal.
20//
21// One important aspect of the SCEV objects is that they are never cyclic, even
22// if there is a cycle in the dataflow for an expression (ie, a PHI node). If
23// the PHI node is one of the idioms that we can represent (e.g., a polynomial
24// recurrence) then we represent it directly as a recurrence node, otherwise we
25// represent it as a SCEVUnknown node.
26//
27// In addition to being able to represent expressions of various types, we also
28// have folders that are used to build the *canonical* representation for a
29// particular expression. These folders are capable of using a variety of
30// rewrite rules to simplify the expressions.
Misha Brukman2b37d7c2005-04-21 21:13:18 +000031//
Chris Lattner53e677a2004-04-02 20:23:17 +000032// Once the folders are defined, we can implement the more interesting
33// higher-level code, such as the code that recognizes PHI nodes of various
34// types, computes the execution count of a loop, etc.
35//
Chris Lattner53e677a2004-04-02 20:23:17 +000036// TODO: We should use these routines and value representations to implement
37// dependence analysis!
38//
39//===----------------------------------------------------------------------===//
40//
41// There are several good references for the techniques used in this analysis.
42//
43// Chains of recurrences -- a method to expedite the evaluation
44// of closed-form functions
45// Olaf Bachmann, Paul S. Wang, Eugene V. Zima
46//
47// On computational properties of chains of recurrences
48// Eugene V. Zima
49//
50// Symbolic Evaluation of Chains of Recurrences for Loop Optimization
51// Robert A. van Engelen
52//
53// Efficient Symbolic Analysis for Optimizing Compilers
54// Robert A. van Engelen
55//
56// Using the chains of recurrences algebra for data dependence testing and
57// induction variable substitution
58// MS Thesis, Johnie Birch
59//
60//===----------------------------------------------------------------------===//
61
Chris Lattner3b27d682006-12-19 22:30:33 +000062#define DEBUG_TYPE "scalar-evolution"
Chris Lattner0a7f98c2004-04-15 15:07:24 +000063#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Chris Lattner53e677a2004-04-02 20:23:17 +000064#include "llvm/Constants.h"
65#include "llvm/DerivedTypes.h"
Chris Lattner673e02b2004-10-12 01:49:27 +000066#include "llvm/GlobalVariable.h"
Chris Lattner53e677a2004-04-02 20:23:17 +000067#include "llvm/Instructions.h"
John Criswella1156432005-10-27 15:54:34 +000068#include "llvm/Analysis/ConstantFolding.h"
Chris Lattner53e677a2004-04-02 20:23:17 +000069#include "llvm/Analysis/LoopInfo.h"
70#include "llvm/Assembly/Writer.h"
71#include "llvm/Transforms/Scalar.h"
72#include "llvm/Support/CFG.h"
Chris Lattner95255282006-06-28 23:17:24 +000073#include "llvm/Support/CommandLine.h"
Chris Lattnerb3364092006-10-04 21:49:37 +000074#include "llvm/Support/Compiler.h"
Chris Lattner53e677a2004-04-02 20:23:17 +000075#include "llvm/Support/ConstantRange.h"
76#include "llvm/Support/InstIterator.h"
Chris Lattnerb3364092006-10-04 21:49:37 +000077#include "llvm/Support/ManagedStatic.h"
Chris Lattner75de5ab2006-12-19 01:16:02 +000078#include "llvm/Support/MathExtras.h"
Bill Wendling6f81b512006-11-28 22:46:12 +000079#include "llvm/Support/Streams.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000080#include "llvm/ADT/Statistic.h"
Bill Wendling6f81b512006-11-28 22:46:12 +000081#include <ostream>
Alkis Evlogimenos20aa4742004-09-03 18:19:51 +000082#include <algorithm>
Jeff Cohen97af7512006-12-02 02:22:01 +000083#include <cmath>
Chris Lattner53e677a2004-04-02 20:23:17 +000084using namespace llvm;
85
Chris Lattner3b27d682006-12-19 22:30:33 +000086STATISTIC(NumBruteForceEvaluations,
87 "Number of brute force evaluations needed to "
88 "calculate high-order polynomial exit values");
89STATISTIC(NumArrayLenItCounts,
90 "Number of trip counts computed with array length");
91STATISTIC(NumTripCountsComputed,
92 "Number of loops with predictable loop counts");
93STATISTIC(NumTripCountsNotComputed,
94 "Number of loops without predictable loop counts");
95STATISTIC(NumBruteForceTripCountsComputed,
96 "Number of loops with trip counts computed by force");
97
Dan Gohman844731a2008-05-13 00:00:25 +000098static cl::opt<unsigned>
Chris Lattner3b27d682006-12-19 22:30:33 +000099MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
100 cl::desc("Maximum number of iterations SCEV will "
101 "symbolically execute a constant derived loop"),
102 cl::init(100));
103
Dan Gohman844731a2008-05-13 00:00:25 +0000104static RegisterPass<ScalarEvolution>
105R("scalar-evolution", "Scalar Evolution Analysis", false, true);
Devang Patel19974732007-05-03 01:11:54 +0000106char ScalarEvolution::ID = 0;
Chris Lattner53e677a2004-04-02 20:23:17 +0000107
108//===----------------------------------------------------------------------===//
109// SCEV class definitions
110//===----------------------------------------------------------------------===//
111
112//===----------------------------------------------------------------------===//
113// Implementation of the SCEV class.
114//
Chris Lattner53e677a2004-04-02 20:23:17 +0000115SCEV::~SCEV() {}
116void SCEV::dump() const {
Bill Wendlinge8156192006-12-07 01:30:32 +0000117 print(cerr);
Chris Lattner53e677a2004-04-02 20:23:17 +0000118}
119
Reid Spencer581b0d42007-02-28 19:57:34 +0000120uint32_t SCEV::getBitWidth() const {
121 if (const IntegerType* ITy = dyn_cast<IntegerType>(getType()))
122 return ITy->getBitWidth();
123 return 0;
124}
125
Dan Gohmancfeb6a42008-06-18 16:23:07 +0000126bool SCEV::isZero() const {
127 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
128 return SC->getValue()->isZero();
129 return false;
130}
131
Chris Lattner53e677a2004-04-02 20:23:17 +0000132
133SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
134
135bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
136 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
Misha Brukmanbb2aff12004-04-05 19:00:46 +0000137 return false;
Chris Lattner53e677a2004-04-02 20:23:17 +0000138}
139
140const Type *SCEVCouldNotCompute::getType() const {
141 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
Misha Brukmanbb2aff12004-04-05 19:00:46 +0000142 return 0;
Chris Lattner53e677a2004-04-02 20:23:17 +0000143}
144
145bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const {
146 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
147 return false;
148}
149
Chris Lattner4dc534c2005-02-13 04:37:18 +0000150SCEVHandle SCEVCouldNotCompute::
151replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
Dan Gohman246b2562007-10-22 18:31:58 +0000152 const SCEVHandle &Conc,
153 ScalarEvolution &SE) const {
Chris Lattner4dc534c2005-02-13 04:37:18 +0000154 return this;
155}
156
Chris Lattner53e677a2004-04-02 20:23:17 +0000157void SCEVCouldNotCompute::print(std::ostream &OS) const {
158 OS << "***COULDNOTCOMPUTE***";
159}
160
161bool SCEVCouldNotCompute::classof(const SCEV *S) {
162 return S->getSCEVType() == scCouldNotCompute;
163}
164
165
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000166// SCEVConstants - Only allow the creation of one SCEVConstant for any
167// particular value. Don't use a SCEVHandle here, or else the object will
168// never be deleted!
Chris Lattnerb3364092006-10-04 21:49:37 +0000169static ManagedStatic<std::map<ConstantInt*, SCEVConstant*> > SCEVConstants;
Misha Brukman2b37d7c2005-04-21 21:13:18 +0000170
Chris Lattner53e677a2004-04-02 20:23:17 +0000171
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000172SCEVConstant::~SCEVConstant() {
Chris Lattnerb3364092006-10-04 21:49:37 +0000173 SCEVConstants->erase(V);
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000174}
Chris Lattner53e677a2004-04-02 20:23:17 +0000175
Dan Gohman246b2562007-10-22 18:31:58 +0000176SCEVHandle ScalarEvolution::getConstant(ConstantInt *V) {
Chris Lattnerb3364092006-10-04 21:49:37 +0000177 SCEVConstant *&R = (*SCEVConstants)[V];
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000178 if (R == 0) R = new SCEVConstant(V);
179 return R;
180}
Chris Lattner53e677a2004-04-02 20:23:17 +0000181
Dan Gohman246b2562007-10-22 18:31:58 +0000182SCEVHandle ScalarEvolution::getConstant(const APInt& Val) {
183 return getConstant(ConstantInt::get(Val));
Dan Gohman9a6ae962007-07-09 15:25:17 +0000184}
185
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000186const Type *SCEVConstant::getType() const { return V->getType(); }
Chris Lattner53e677a2004-04-02 20:23:17 +0000187
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000188void SCEVConstant::print(std::ostream &OS) const {
189 WriteAsOperand(OS, V, false);
190}
Chris Lattner53e677a2004-04-02 20:23:17 +0000191
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000192// SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
193// particular input. Don't use a SCEVHandle here, or else the object will
194// never be deleted!
Chris Lattnerb3364092006-10-04 21:49:37 +0000195static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
196 SCEVTruncateExpr*> > SCEVTruncates;
Chris Lattner53e677a2004-04-02 20:23:17 +0000197
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000198SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
199 : SCEV(scTruncate), Op(op), Ty(ty) {
Chris Lattner42a75512007-01-15 02:27:26 +0000200 assert(Op->getType()->isInteger() && Ty->isInteger() &&
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000201 "Cannot truncate non-integer value!");
Reid Spencere7ca0422007-01-08 01:26:33 +0000202 assert(Op->getType()->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()
203 && "This is not a truncating conversion!");
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000204}
Chris Lattner53e677a2004-04-02 20:23:17 +0000205
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000206SCEVTruncateExpr::~SCEVTruncateExpr() {
Chris Lattnerb3364092006-10-04 21:49:37 +0000207 SCEVTruncates->erase(std::make_pair(Op, Ty));
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000208}
Chris Lattner53e677a2004-04-02 20:23:17 +0000209
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000210void SCEVTruncateExpr::print(std::ostream &OS) const {
211 OS << "(truncate " << *Op << " to " << *Ty << ")";
212}
213
214// SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
215// particular input. Don't use a SCEVHandle here, or else the object will never
216// be deleted!
Chris Lattnerb3364092006-10-04 21:49:37 +0000217static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
218 SCEVZeroExtendExpr*> > SCEVZeroExtends;
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000219
220SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
Reid Spencer48d8a702006-11-01 21:53:12 +0000221 : SCEV(scZeroExtend), Op(op), Ty(ty) {
Chris Lattner42a75512007-01-15 02:27:26 +0000222 assert(Op->getType()->isInteger() && Ty->isInteger() &&
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000223 "Cannot zero extend non-integer value!");
Reid Spencere7ca0422007-01-08 01:26:33 +0000224 assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
225 && "This is not an extending conversion!");
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000226}
227
228SCEVZeroExtendExpr::~SCEVZeroExtendExpr() {
Chris Lattnerb3364092006-10-04 21:49:37 +0000229 SCEVZeroExtends->erase(std::make_pair(Op, Ty));
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000230}
231
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000232void SCEVZeroExtendExpr::print(std::ostream &OS) const {
233 OS << "(zeroextend " << *Op << " to " << *Ty << ")";
234}
235
Dan Gohmand19534a2007-06-15 14:38:12 +0000236// SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
237// particular input. Don't use a SCEVHandle here, or else the object will never
238// be deleted!
239static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
240 SCEVSignExtendExpr*> > SCEVSignExtends;
241
242SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
243 : SCEV(scSignExtend), Op(op), Ty(ty) {
244 assert(Op->getType()->isInteger() && Ty->isInteger() &&
245 "Cannot sign extend non-integer value!");
246 assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
247 && "This is not an extending conversion!");
248}
249
250SCEVSignExtendExpr::~SCEVSignExtendExpr() {
251 SCEVSignExtends->erase(std::make_pair(Op, Ty));
252}
253
Dan Gohmand19534a2007-06-15 14:38:12 +0000254void SCEVSignExtendExpr::print(std::ostream &OS) const {
255 OS << "(signextend " << *Op << " to " << *Ty << ")";
256}
257
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000258// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
259// particular input. Don't use a SCEVHandle here, or else the object will never
260// be deleted!
Chris Lattnerb3364092006-10-04 21:49:37 +0000261static ManagedStatic<std::map<std::pair<unsigned, std::vector<SCEV*> >,
262 SCEVCommutativeExpr*> > SCEVCommExprs;
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000263
264SCEVCommutativeExpr::~SCEVCommutativeExpr() {
Chris Lattnerb3364092006-10-04 21:49:37 +0000265 SCEVCommExprs->erase(std::make_pair(getSCEVType(),
266 std::vector<SCEV*>(Operands.begin(),
267 Operands.end())));
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000268}
269
270void SCEVCommutativeExpr::print(std::ostream &OS) const {
271 assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
272 const char *OpStr = getOperationStr();
273 OS << "(" << *Operands[0];
274 for (unsigned i = 1, e = Operands.size(); i != e; ++i)
275 OS << OpStr << *Operands[i];
276 OS << ")";
277}
278
Chris Lattner4dc534c2005-02-13 04:37:18 +0000279SCEVHandle SCEVCommutativeExpr::
280replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
Dan Gohman246b2562007-10-22 18:31:58 +0000281 const SCEVHandle &Conc,
282 ScalarEvolution &SE) const {
Chris Lattner4dc534c2005-02-13 04:37:18 +0000283 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
Dan Gohman246b2562007-10-22 18:31:58 +0000284 SCEVHandle H =
285 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
Chris Lattner4dc534c2005-02-13 04:37:18 +0000286 if (H != getOperand(i)) {
287 std::vector<SCEVHandle> NewOps;
288 NewOps.reserve(getNumOperands());
289 for (unsigned j = 0; j != i; ++j)
290 NewOps.push_back(getOperand(j));
291 NewOps.push_back(H);
292 for (++i; i != e; ++i)
293 NewOps.push_back(getOperand(i)->
Dan Gohman246b2562007-10-22 18:31:58 +0000294 replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
Chris Lattner4dc534c2005-02-13 04:37:18 +0000295
296 if (isa<SCEVAddExpr>(this))
Dan Gohman246b2562007-10-22 18:31:58 +0000297 return SE.getAddExpr(NewOps);
Chris Lattner4dc534c2005-02-13 04:37:18 +0000298 else if (isa<SCEVMulExpr>(this))
Dan Gohman246b2562007-10-22 18:31:58 +0000299 return SE.getMulExpr(NewOps);
Nick Lewyckyc54c5612007-11-25 22:41:31 +0000300 else if (isa<SCEVSMaxExpr>(this))
301 return SE.getSMaxExpr(NewOps);
Nick Lewycky3e630762008-02-20 06:48:22 +0000302 else if (isa<SCEVUMaxExpr>(this))
303 return SE.getUMaxExpr(NewOps);
Chris Lattner4dc534c2005-02-13 04:37:18 +0000304 else
305 assert(0 && "Unknown commutative expr!");
306 }
307 }
308 return this;
309}
310
311
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000312// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000313// input. Don't use a SCEVHandle here, or else the object will never be
314// deleted!
Chris Lattnerb3364092006-10-04 21:49:37 +0000315static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>,
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000316 SCEVUDivExpr*> > SCEVUDivs;
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000317
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000318SCEVUDivExpr::~SCEVUDivExpr() {
319 SCEVUDivs->erase(std::make_pair(LHS, RHS));
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000320}
321
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000322void SCEVUDivExpr::print(std::ostream &OS) const {
323 OS << "(" << *LHS << " /u " << *RHS << ")";
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000324}
325
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000326const Type *SCEVUDivExpr::getType() const {
Reid Spencerc5b206b2006-12-31 05:48:39 +0000327 return LHS->getType();
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000328}
329
330// SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
331// particular input. Don't use a SCEVHandle here, or else the object will never
332// be deleted!
Chris Lattnerb3364092006-10-04 21:49:37 +0000333static ManagedStatic<std::map<std::pair<const Loop *, std::vector<SCEV*> >,
334 SCEVAddRecExpr*> > SCEVAddRecExprs;
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000335
336SCEVAddRecExpr::~SCEVAddRecExpr() {
Chris Lattnerb3364092006-10-04 21:49:37 +0000337 SCEVAddRecExprs->erase(std::make_pair(L,
338 std::vector<SCEV*>(Operands.begin(),
339 Operands.end())));
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000340}
341
Chris Lattner4dc534c2005-02-13 04:37:18 +0000342SCEVHandle SCEVAddRecExpr::
343replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
Dan Gohman246b2562007-10-22 18:31:58 +0000344 const SCEVHandle &Conc,
345 ScalarEvolution &SE) const {
Chris Lattner4dc534c2005-02-13 04:37:18 +0000346 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
Dan Gohman246b2562007-10-22 18:31:58 +0000347 SCEVHandle H =
348 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
Chris Lattner4dc534c2005-02-13 04:37:18 +0000349 if (H != getOperand(i)) {
350 std::vector<SCEVHandle> NewOps;
351 NewOps.reserve(getNumOperands());
352 for (unsigned j = 0; j != i; ++j)
353 NewOps.push_back(getOperand(j));
354 NewOps.push_back(H);
355 for (++i; i != e; ++i)
356 NewOps.push_back(getOperand(i)->
Dan Gohman246b2562007-10-22 18:31:58 +0000357 replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
Misha Brukman2b37d7c2005-04-21 21:13:18 +0000358
Dan Gohman246b2562007-10-22 18:31:58 +0000359 return SE.getAddRecExpr(NewOps, L);
Chris Lattner4dc534c2005-02-13 04:37:18 +0000360 }
361 }
362 return this;
363}
364
365
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000366bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
367 // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
Chris Lattnerff2006a2005-08-16 00:37:01 +0000368 // contain L and if the start is invariant.
369 return !QueryLoop->contains(L->getHeader()) &&
370 getOperand(0)->isLoopInvariant(QueryLoop);
Chris Lattner53e677a2004-04-02 20:23:17 +0000371}
372
373
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000374void SCEVAddRecExpr::print(std::ostream &OS) const {
375 OS << "{" << *Operands[0];
376 for (unsigned i = 1, e = Operands.size(); i != e; ++i)
377 OS << ",+," << *Operands[i];
378 OS << "}<" << L->getHeader()->getName() + ">";
379}
Chris Lattner53e677a2004-04-02 20:23:17 +0000380
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000381// SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular
382// value. Don't use a SCEVHandle here, or else the object will never be
383// deleted!
Chris Lattnerb3364092006-10-04 21:49:37 +0000384static ManagedStatic<std::map<Value*, SCEVUnknown*> > SCEVUnknowns;
Chris Lattner53e677a2004-04-02 20:23:17 +0000385
Chris Lattnerb3364092006-10-04 21:49:37 +0000386SCEVUnknown::~SCEVUnknown() { SCEVUnknowns->erase(V); }
Chris Lattner53e677a2004-04-02 20:23:17 +0000387
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000388bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
389 // All non-instruction values are loop invariant. All instructions are loop
390 // invariant if they are not contained in the specified loop.
391 if (Instruction *I = dyn_cast<Instruction>(V))
392 return !L->contains(I->getParent());
393 return true;
394}
Chris Lattner53e677a2004-04-02 20:23:17 +0000395
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000396const Type *SCEVUnknown::getType() const {
397 return V->getType();
398}
Chris Lattner53e677a2004-04-02 20:23:17 +0000399
Chris Lattner0a7f98c2004-04-15 15:07:24 +0000400void SCEVUnknown::print(std::ostream &OS) const {
401 WriteAsOperand(OS, V, false);
Chris Lattner53e677a2004-04-02 20:23:17 +0000402}
403
Chris Lattner8d741b82004-06-20 06:23:15 +0000404//===----------------------------------------------------------------------===//
405// SCEV Utilities
406//===----------------------------------------------------------------------===//
407
408namespace {
409 /// SCEVComplexityCompare - Return true if the complexity of the LHS is less
410 /// than the complexity of the RHS. This comparator is used to canonicalize
411 /// expressions.
Chris Lattner95255282006-06-28 23:17:24 +0000412 struct VISIBILITY_HIDDEN SCEVComplexityCompare {
Dan Gohmanf7b37b22008-04-14 18:23:56 +0000413 bool operator()(const SCEV *LHS, const SCEV *RHS) const {
Chris Lattner8d741b82004-06-20 06:23:15 +0000414 return LHS->getSCEVType() < RHS->getSCEVType();
415 }
416 };
417}
418
419/// GroupByComplexity - Given a list of SCEV objects, order them by their
420/// complexity, and group objects of the same complexity together by value.
421/// When this routine is finished, we know that any duplicates in the vector are
422/// consecutive and that complexity is monotonically increasing.
423///
424/// Note that we go take special precautions to ensure that we get determinstic
425/// results from this routine. In other words, we don't want the results of
426/// this to depend on where the addresses of various SCEV objects happened to
427/// land in memory.
428///
429static void GroupByComplexity(std::vector<SCEVHandle> &Ops) {
430 if (Ops.size() < 2) return; // Noop
431 if (Ops.size() == 2) {
432 // This is the common case, which also happens to be trivially simple.
433 // Special case it.
Dan Gohmanf7b37b22008-04-14 18:23:56 +0000434 if (SCEVComplexityCompare()(Ops[1], Ops[0]))
Chris Lattner8d741b82004-06-20 06:23:15 +0000435 std::swap(Ops[0], Ops[1]);
436 return;
437 }
438
439 // Do the rough sort by complexity.
440 std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
441
442 // Now that we are sorted by complexity, group elements of the same
443 // complexity. Note that this is, at worst, N^2, but the vector is likely to
444 // be extremely short in practice. Note that we take this approach because we
445 // do not want to depend on the addresses of the objects we are grouping.
Chris Lattner2d584522004-06-20 17:01:44 +0000446 for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
Chris Lattner8d741b82004-06-20 06:23:15 +0000447 SCEV *S = Ops[i];
448 unsigned Complexity = S->getSCEVType();
449
450 // If there are any objects of the same complexity and same value as this
451 // one, group them.
452 for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) {
453 if (Ops[j] == S) { // Found a duplicate.
454 // Move it to immediately after i'th element.
455 std::swap(Ops[i+1], Ops[j]);
456 ++i; // no need to rescan it.
Chris Lattner541ad5e2004-06-20 20:32:16 +0000457 if (i == e-2) return; // Done!
Chris Lattner8d741b82004-06-20 06:23:15 +0000458 }
459 }
460 }
461}
462
Chris Lattner53e677a2004-04-02 20:23:17 +0000463
Chris Lattner53e677a2004-04-02 20:23:17 +0000464
465//===----------------------------------------------------------------------===//
466// Simple SCEV method implementations
467//===----------------------------------------------------------------------===//
468
469/// getIntegerSCEV - Given an integer or FP type, create a constant for the
470/// specified signed integer value and return a SCEV for the constant.
Dan Gohman246b2562007-10-22 18:31:58 +0000471SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
Chris Lattner53e677a2004-04-02 20:23:17 +0000472 Constant *C;
Misha Brukman2b37d7c2005-04-21 21:13:18 +0000473 if (Val == 0)
Chris Lattner53e677a2004-04-02 20:23:17 +0000474 C = Constant::getNullValue(Ty);
475 else if (Ty->isFloatingPoint())
Chris Lattner02a260a2008-04-20 00:41:09 +0000476 C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
477 APFloat::IEEEdouble, Val));
Reid Spencere4d87aa2006-12-23 06:05:41 +0000478 else
Reid Spencerb83eb642006-10-20 07:07:24 +0000479 C = ConstantInt::get(Ty, Val);
Dan Gohman246b2562007-10-22 18:31:58 +0000480 return getUnknown(C);
Chris Lattner53e677a2004-04-02 20:23:17 +0000481}
482
Chris Lattner53e677a2004-04-02 20:23:17 +0000483/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
484///
Dan Gohman246b2562007-10-22 18:31:58 +0000485SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
Chris Lattner53e677a2004-04-02 20:23:17 +0000486 if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
Dan Gohman246b2562007-10-22 18:31:58 +0000487 return getUnknown(ConstantExpr::getNeg(VC->getValue()));
Misha Brukman2b37d7c2005-04-21 21:13:18 +0000488
Nick Lewycky178f20a2008-02-20 06:58:55 +0000489 return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(V->getType())));
Nick Lewycky3e630762008-02-20 06:48:22 +0000490}
491
492/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
493SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
494 if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
495 return getUnknown(ConstantExpr::getNot(VC->getValue()));
496
Nick Lewycky178f20a2008-02-20 06:58:55 +0000497 SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(V->getType()));
Nick Lewycky3e630762008-02-20 06:48:22 +0000498 return getMinusSCEV(AllOnes, V);
Chris Lattner53e677a2004-04-02 20:23:17 +0000499}
500
501/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
502///
Dan Gohman246b2562007-10-22 18:31:58 +0000503SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS,
504 const SCEVHandle &RHS) {
Chris Lattner53e677a2004-04-02 20:23:17 +0000505 // X - Y --> X + -Y
Dan Gohman246b2562007-10-22 18:31:58 +0000506 return getAddExpr(LHS, getNegativeSCEV(RHS));
Chris Lattner53e677a2004-04-02 20:23:17 +0000507}
508
509
Eli Friedmanb42a6262008-08-04 23:49:06 +0000510/// BinomialCoefficient - Compute BC(It, K). The result has width W.
511// Assume, K > 0.
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000512static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
Eli Friedmanb42a6262008-08-04 23:49:06 +0000513 ScalarEvolution &SE,
514 const IntegerType* ResultTy) {
515 // Handle the simplest case efficiently.
516 if (K == 1)
517 return SE.getTruncateOrZeroExtend(It, ResultTy);
518
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000519 // We are using the following formula for BC(It, K):
520 //
521 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / K!
522 //
Eli Friedmanb42a6262008-08-04 23:49:06 +0000523 // Suppose, W is the bitwidth of the return value. We must be prepared for
524 // overflow. Hence, we must assure that the result of our computation is
525 // equal to the accurate one modulo 2^W. Unfortunately, division isn't
526 // safe in modular arithmetic.
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000527 //
Eli Friedmanb42a6262008-08-04 23:49:06 +0000528 // However, this code doesn't use exactly that formula; the formula it uses
529 // is something like the following, where T is the number of factors of 2 in
530 // K! (i.e. trailing zeros in the binary representation of K!), and ^ is
531 // exponentiation:
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000532 //
Eli Friedmanb42a6262008-08-04 23:49:06 +0000533 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / 2^T / (K! / 2^T)
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000534 //
Eli Friedmanb42a6262008-08-04 23:49:06 +0000535 // This formula is trivially equivalent to the previous formula. However,
536 // this formula can be implemented much more efficiently. The trick is that
537 // K! / 2^T is odd, and exact division by an odd number *is* safe in modular
538 // arithmetic. To do exact division in modular arithmetic, all we have
539 // to do is multiply by the inverse. Therefore, this step can be done at
540 // width W.
541 //
542 // The next issue is how to safely do the division by 2^T. The way this
543 // is done is by doing the multiplication step at a width of at least W + T
544 // bits. This way, the bottom W+T bits of the product are accurate. Then,
545 // when we perform the division by 2^T (which is equivalent to a right shift
546 // by T), the bottom W bits are accurate. Extra bits are okay; they'll get
547 // truncated out after the division by 2^T.
548 //
549 // In comparison to just directly using the first formula, this technique
550 // is much more efficient; using the first formula requires W * K bits,
551 // but this formula less than W + K bits. Also, the first formula requires
552 // a division step, whereas this formula only requires multiplies and shifts.
553 //
554 // It doesn't matter whether the subtraction step is done in the calculation
555 // width or the input iteration count's width; if the subtraction overflows,
556 // the result must be zero anyway. We prefer here to do it in the width of
557 // the induction variable because it helps a lot for certain cases; CodeGen
558 // isn't smart enough to ignore the overflow, which leads to much less
559 // efficient code if the width of the subtraction is wider than the native
560 // register width.
561 //
562 // (It's possible to not widen at all by pulling out factors of 2 before
563 // the multiplication; for example, K=2 can be calculated as
564 // It/2*(It+(It*INT_MIN/INT_MIN)+-1). However, it requires
565 // extra arithmetic, so it's not an obvious win, and it gets
566 // much more complicated for K > 3.)
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000567
Eli Friedmanb42a6262008-08-04 23:49:06 +0000568 // Protection from insane SCEVs; this bound is conservative,
569 // but it probably doesn't matter.
570 if (K > 1000)
571 return new SCEVCouldNotCompute();
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000572
Eli Friedmanb42a6262008-08-04 23:49:06 +0000573 unsigned W = ResultTy->getBitWidth();
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000574
Eli Friedmanb42a6262008-08-04 23:49:06 +0000575 // Calculate K! / 2^T and T; we divide out the factors of two before
576 // multiplying for calculating K! / 2^T to avoid overflow.
577 // Other overflow doesn't matter because we only care about the bottom
578 // W bits of the result.
579 APInt OddFactorial(W, 1);
580 unsigned T = 1;
581 for (unsigned i = 3; i <= K; ++i) {
582 APInt Mult(W, i);
583 unsigned TwoFactors = Mult.countTrailingZeros();
584 T += TwoFactors;
585 Mult = Mult.lshr(TwoFactors);
586 OddFactorial *= Mult;
Chris Lattner53e677a2004-04-02 20:23:17 +0000587 }
Nick Lewycky6f8abf92008-06-13 04:38:55 +0000588
Eli Friedmanb42a6262008-08-04 23:49:06 +0000589 // We need at least W + T bits for the multiplication step
590 // FIXME: A temporary hack; we round up the bitwidths
591 // to the nearest power of 2 to be nice to the code generator.
592 unsigned CalculationBits = 1U << Log2_32_Ceil(W + T);
593 // FIXME: Temporary hack to avoid generating integers that are too wide.
594 // Although, it's not completely clear how to determine how much
595 // widening is safe; for example, on X86, we can't really widen
596 // beyond 64 because we need to be able to do multiplication
597 // that's CalculationBits wide, but on X86-64, we can safely widen up to
598 // 128 bits.
599 if (CalculationBits > 64)
600 return new SCEVCouldNotCompute();
601
602 // Calcuate 2^T, at width T+W.
603 APInt DivFactor = APInt(CalculationBits, 1).shl(T);
604
605 // Calculate the multiplicative inverse of K! / 2^T;
606 // this multiplication factor will perform the exact division by
607 // K! / 2^T.
608 APInt Mod = APInt::getSignedMinValue(W+1);
609 APInt MultiplyFactor = OddFactorial.zext(W+1);
610 MultiplyFactor = MultiplyFactor.multiplicativeInverse(Mod);
611 MultiplyFactor = MultiplyFactor.trunc(W);
612
613 // Calculate the product, at width T+W
614 const IntegerType *CalculationTy = IntegerType::get(CalculationBits);
615 SCEVHandle Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
616 for (unsigned i = 1; i != K; ++i) {
617 SCEVHandle S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType()));
618 Dividend = SE.getMulExpr(Dividend,
619 SE.getTruncateOrZeroExtend(S, CalculationTy));
620 }
621
622 // Divide by 2^T
623 SCEVHandle DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
624
625 // Truncate the result, and divide by K! / 2^T.
626
627 return SE.getMulExpr(SE.getConstant(MultiplyFactor),
628 SE.getTruncateOrZeroExtend(DivResult, ResultTy));
Chris Lattner53e677a2004-04-02 20:23:17 +0000629}
630
Chris Lattner53e677a2004-04-02 20:23:17 +0000631/// evaluateAtIteration - Return the value of this chain of recurrences at
632/// the specified iteration number. We can evaluate this recurrence by
633/// multiplying each element in the chain by the binomial coefficient
634/// corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as:
635///
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000636/// A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3)
Chris Lattner53e677a2004-04-02 20:23:17 +0000637///
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000638/// where BC(It, k) stands for binomial coefficient.
Chris Lattner53e677a2004-04-02 20:23:17 +0000639///
Dan Gohman246b2562007-10-22 18:31:58 +0000640SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It,
641 ScalarEvolution &SE) const {
Chris Lattner53e677a2004-04-02 20:23:17 +0000642 SCEVHandle Result = getStart();
Chris Lattner53e677a2004-04-02 20:23:17 +0000643 for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +0000644 // The computation is correct in the face of overflow provided that the
645 // multiplication is performed _after_ the evaluation of the binomial
646 // coefficient.
Nick Lewyckycb8f1b52008-10-13 03:58:02 +0000647 SCEVHandle Coeff = BinomialCoefficient(It, i, SE,
648 cast<IntegerType>(getType()));
649 if (isa<SCEVCouldNotCompute>(Coeff))
650 return Coeff;
651
652 Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff));
Chris Lattner53e677a2004-04-02 20:23:17 +0000653 }
654 return Result;
655}
656
Chris Lattner53e677a2004-04-02 20:23:17 +0000657//===----------------------------------------------------------------------===//
658// SCEV Expression folder implementations
659//===----------------------------------------------------------------------===//
660
Dan Gohman246b2562007-10-22 18:31:58 +0000661SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op, const Type *Ty) {
Chris Lattner53e677a2004-04-02 20:23:17 +0000662 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
Dan Gohman246b2562007-10-22 18:31:58 +0000663 return getUnknown(
Reid Spencer315d0552006-12-05 22:39:58 +0000664 ConstantExpr::getTrunc(SC->getValue(), Ty));
Chris Lattner53e677a2004-04-02 20:23:17 +0000665
666 // If the input value is a chrec scev made out of constants, truncate
667 // all of the constants.
668 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
669 std::vector<SCEVHandle> Operands;
670 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
671 // FIXME: This should allow truncation of other expression types!
672 if (isa<SCEVConstant>(AddRec->getOperand(i)))
Dan Gohman246b2562007-10-22 18:31:58 +0000673 Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
Chris Lattner53e677a2004-04-02 20:23:17 +0000674 else
675 break;
676 if (Operands.size() == AddRec->getNumOperands())
Dan Gohman246b2562007-10-22 18:31:58 +0000677 return getAddRecExpr(Operands, AddRec->getLoop());
Chris Lattner53e677a2004-04-02 20:23:17 +0000678 }
679
Chris Lattnerb3364092006-10-04 21:49:37 +0000680 SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)];
Chris Lattner53e677a2004-04-02 20:23:17 +0000681 if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
682 return Result;
683}
684
Dan Gohman246b2562007-10-22 18:31:58 +0000685SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty) {
Chris Lattner53e677a2004-04-02 20:23:17 +0000686 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
Dan Gohman246b2562007-10-22 18:31:58 +0000687 return getUnknown(
Reid Spencerd977d862006-12-12 23:36:14 +0000688 ConstantExpr::getZExt(SC->getValue(), Ty));
Chris Lattner53e677a2004-04-02 20:23:17 +0000689
690 // FIXME: If the input value is a chrec scev, and we can prove that the value
691 // did not overflow the old, smaller, value, we can zero extend all of the
692 // operands (often constants). This would allow analysis of something like
693 // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
694
Chris Lattnerb3364092006-10-04 21:49:37 +0000695 SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)];
Chris Lattner53e677a2004-04-02 20:23:17 +0000696 if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
697 return Result;
698}
699
Dan Gohman246b2562007-10-22 18:31:58 +0000700SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, const Type *Ty) {
Dan Gohmand19534a2007-06-15 14:38:12 +0000701 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
Dan Gohman246b2562007-10-22 18:31:58 +0000702 return getUnknown(
Dan Gohmand19534a2007-06-15 14:38:12 +0000703 ConstantExpr::getSExt(SC->getValue(), Ty));
704
705 // FIXME: If the input value is a chrec scev, and we can prove that the value
706 // did not overflow the old, smaller, value, we can sign extend all of the
707 // operands (often constants). This would allow analysis of something like
708 // this: for (signed char X = 0; X < 100; ++X) { int Y = X; }
709
710 SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)];
711 if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
712 return Result;
713}
714
Nick Lewycky6f8abf92008-06-13 04:38:55 +0000715/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
716/// of the input value to the specified type. If the type must be
717/// extended, it is zero extended.
718SCEVHandle ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V,
719 const Type *Ty) {
720 const Type *SrcTy = V->getType();
721 assert(SrcTy->isInteger() && Ty->isInteger() &&
722 "Cannot truncate or zero extend with non-integer arguments!");
723 if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits())
724 return V; // No conversion
725 if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits())
726 return getTruncateExpr(V, Ty);
727 return getZeroExtendExpr(V, Ty);
728}
729
Chris Lattner53e677a2004-04-02 20:23:17 +0000730// get - Get a canonical add expression, or something simpler if possible.
Dan Gohman246b2562007-10-22 18:31:58 +0000731SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) {
Chris Lattner53e677a2004-04-02 20:23:17 +0000732 assert(!Ops.empty() && "Cannot get empty add!");
Chris Lattner627018b2004-04-07 16:16:11 +0000733 if (Ops.size() == 1) return Ops[0];
Chris Lattner53e677a2004-04-02 20:23:17 +0000734
735 // Sort by complexity, this groups all similar expression types together.
Chris Lattner8d741b82004-06-20 06:23:15 +0000736 GroupByComplexity(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +0000737
738 // If there are any constants, fold them together.
739 unsigned Idx = 0;
740 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
741 ++Idx;
Chris Lattner627018b2004-04-07 16:16:11 +0000742 assert(Idx < Ops.size());
Chris Lattner53e677a2004-04-02 20:23:17 +0000743 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
744 // We found two constants, fold them together!
Nick Lewycky3e630762008-02-20 06:48:22 +0000745 ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() +
746 RHSC->getValue()->getValue());
747 Ops[0] = getConstant(Fold);
748 Ops.erase(Ops.begin()+1); // Erase the folded element
749 if (Ops.size() == 1) return Ops[0];
750 LHSC = cast<SCEVConstant>(Ops[0]);
Chris Lattner53e677a2004-04-02 20:23:17 +0000751 }
752
753 // If we are left with a constant zero being added, strip it off.
Reid Spencercae57542007-03-02 00:28:52 +0000754 if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
Chris Lattner53e677a2004-04-02 20:23:17 +0000755 Ops.erase(Ops.begin());
756 --Idx;
757 }
758 }
759
Chris Lattner627018b2004-04-07 16:16:11 +0000760 if (Ops.size() == 1) return Ops[0];
Misha Brukman2b37d7c2005-04-21 21:13:18 +0000761
Chris Lattner53e677a2004-04-02 20:23:17 +0000762 // Okay, check to see if the same value occurs in the operand list twice. If
763 // so, merge them together into an multiply expression. Since we sorted the
764 // list, these values are required to be adjacent.
765 const Type *Ty = Ops[0]->getType();
766 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
767 if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2
768 // Found a match, merge the two values into a multiply, and add any
769 // remaining values to the result.
Dan Gohman246b2562007-10-22 18:31:58 +0000770 SCEVHandle Two = getIntegerSCEV(2, Ty);
771 SCEVHandle Mul = getMulExpr(Ops[i], Two);
Chris Lattner53e677a2004-04-02 20:23:17 +0000772 if (Ops.size() == 2)
773 return Mul;
774 Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
775 Ops.push_back(Mul);
Dan Gohman246b2562007-10-22 18:31:58 +0000776 return getAddExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +0000777 }
778
Dan Gohmanf50cd742007-06-18 19:30:09 +0000779 // Now we know the first non-constant operand. Skip past any cast SCEVs.
780 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
781 ++Idx;
782
783 // If there are add operands they would be next.
Chris Lattner53e677a2004-04-02 20:23:17 +0000784 if (Idx < Ops.size()) {
785 bool DeletedAdd = false;
786 while (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
787 // If we have an add, expand the add operands onto the end of the operands
788 // list.
789 Ops.insert(Ops.end(), Add->op_begin(), Add->op_end());
790 Ops.erase(Ops.begin()+Idx);
791 DeletedAdd = true;
792 }
793
794 // If we deleted at least one add, we added operands to the end of the list,
795 // and they are not necessarily sorted. Recurse to resort and resimplify
796 // any operands we just aquired.
797 if (DeletedAdd)
Dan Gohman246b2562007-10-22 18:31:58 +0000798 return getAddExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +0000799 }
800
801 // Skip over the add expression until we get to a multiply.
802 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
803 ++Idx;
804
805 // If we are adding something to a multiply expression, make sure the
806 // something is not already an operand of the multiply. If so, merge it into
807 // the multiply.
808 for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
809 SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
810 for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
811 SCEV *MulOpSCEV = Mul->getOperand(MulOp);
812 for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
Chris Lattner6a1a78a2004-12-04 20:54:32 +0000813 if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(MulOpSCEV)) {
Chris Lattner53e677a2004-04-02 20:23:17 +0000814 // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1))
815 SCEVHandle InnerMul = Mul->getOperand(MulOp == 0);
816 if (Mul->getNumOperands() != 2) {
817 // If the multiply has more than two operands, we must get the
818 // Y*Z term.
819 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
820 MulOps.erase(MulOps.begin()+MulOp);
Dan Gohman246b2562007-10-22 18:31:58 +0000821 InnerMul = getMulExpr(MulOps);
Chris Lattner53e677a2004-04-02 20:23:17 +0000822 }
Dan Gohman246b2562007-10-22 18:31:58 +0000823 SCEVHandle One = getIntegerSCEV(1, Ty);
824 SCEVHandle AddOne = getAddExpr(InnerMul, One);
825 SCEVHandle OuterMul = getMulExpr(AddOne, Ops[AddOp]);
Chris Lattner53e677a2004-04-02 20:23:17 +0000826 if (Ops.size() == 2) return OuterMul;
827 if (AddOp < Idx) {
828 Ops.erase(Ops.begin()+AddOp);
829 Ops.erase(Ops.begin()+Idx-1);
830 } else {
831 Ops.erase(Ops.begin()+Idx);
832 Ops.erase(Ops.begin()+AddOp-1);
833 }
834 Ops.push_back(OuterMul);
Dan Gohman246b2562007-10-22 18:31:58 +0000835 return getAddExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +0000836 }
Misha Brukman2b37d7c2005-04-21 21:13:18 +0000837
Chris Lattner53e677a2004-04-02 20:23:17 +0000838 // Check this multiply against other multiplies being added together.
839 for (unsigned OtherMulIdx = Idx+1;
840 OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
841 ++OtherMulIdx) {
842 SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
843 // If MulOp occurs in OtherMul, we can fold the two multiplies
844 // together.
845 for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
846 OMulOp != e; ++OMulOp)
847 if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
848 // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
849 SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0);
850 if (Mul->getNumOperands() != 2) {
851 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
852 MulOps.erase(MulOps.begin()+MulOp);
Dan Gohman246b2562007-10-22 18:31:58 +0000853 InnerMul1 = getMulExpr(MulOps);
Chris Lattner53e677a2004-04-02 20:23:17 +0000854 }
855 SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0);
856 if (OtherMul->getNumOperands() != 2) {
857 std::vector<SCEVHandle> MulOps(OtherMul->op_begin(),
858 OtherMul->op_end());
859 MulOps.erase(MulOps.begin()+OMulOp);
Dan Gohman246b2562007-10-22 18:31:58 +0000860 InnerMul2 = getMulExpr(MulOps);
Chris Lattner53e677a2004-04-02 20:23:17 +0000861 }
Dan Gohman246b2562007-10-22 18:31:58 +0000862 SCEVHandle InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
863 SCEVHandle OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
Chris Lattner53e677a2004-04-02 20:23:17 +0000864 if (Ops.size() == 2) return OuterMul;
865 Ops.erase(Ops.begin()+Idx);
866 Ops.erase(Ops.begin()+OtherMulIdx-1);
867 Ops.push_back(OuterMul);
Dan Gohman246b2562007-10-22 18:31:58 +0000868 return getAddExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +0000869 }
870 }
871 }
872 }
873
874 // If there are any add recurrences in the operands list, see if any other
875 // added values are loop invariant. If so, we can fold them into the
876 // recurrence.
877 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
878 ++Idx;
879
880 // Scan over all recurrences, trying to fold loop invariants into them.
881 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
882 // Scan all of the other operands to this add and add them to the vector if
883 // they are loop invariant w.r.t. the recurrence.
884 std::vector<SCEVHandle> LIOps;
885 SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
886 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
887 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
888 LIOps.push_back(Ops[i]);
889 Ops.erase(Ops.begin()+i);
890 --i; --e;
891 }
892
893 // If we found some loop invariants, fold them into the recurrence.
894 if (!LIOps.empty()) {
Dan Gohman8dae1382008-09-14 17:21:12 +0000895 // NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step}
Chris Lattner53e677a2004-04-02 20:23:17 +0000896 LIOps.push_back(AddRec->getStart());
897
898 std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end());
Dan Gohman246b2562007-10-22 18:31:58 +0000899 AddRecOps[0] = getAddExpr(LIOps);
Chris Lattner53e677a2004-04-02 20:23:17 +0000900
Dan Gohman246b2562007-10-22 18:31:58 +0000901 SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
Chris Lattner53e677a2004-04-02 20:23:17 +0000902 // If all of the other operands were loop invariant, we are done.
903 if (Ops.size() == 1) return NewRec;
904
905 // Otherwise, add the folded AddRec by the non-liv parts.
906 for (unsigned i = 0;; ++i)
907 if (Ops[i] == AddRec) {
908 Ops[i] = NewRec;
909 break;
910 }
Dan Gohman246b2562007-10-22 18:31:58 +0000911 return getAddExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +0000912 }
913
914 // Okay, if there weren't any loop invariants to be folded, check to see if
915 // there are multiple AddRec's with the same loop induction variable being
916 // added together. If so, we can fold them.
917 for (unsigned OtherIdx = Idx+1;
918 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
919 if (OtherIdx != Idx) {
920 SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
921 if (AddRec->getLoop() == OtherAddRec->getLoop()) {
922 // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D}
923 std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end());
924 for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) {
925 if (i >= NewOps.size()) {
926 NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i,
927 OtherAddRec->op_end());
928 break;
929 }
Dan Gohman246b2562007-10-22 18:31:58 +0000930 NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i));
Chris Lattner53e677a2004-04-02 20:23:17 +0000931 }
Dan Gohman246b2562007-10-22 18:31:58 +0000932 SCEVHandle NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop());
Chris Lattner53e677a2004-04-02 20:23:17 +0000933
934 if (Ops.size() == 2) return NewAddRec;
935
936 Ops.erase(Ops.begin()+Idx);
937 Ops.erase(Ops.begin()+OtherIdx-1);
938 Ops.push_back(NewAddRec);
Dan Gohman246b2562007-10-22 18:31:58 +0000939 return getAddExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +0000940 }
941 }
942
943 // Otherwise couldn't fold anything into this recurrence. Move onto the
944 // next one.
945 }
946
947 // Okay, it looks like we really DO need an add expr. Check to see if we
948 // already have one, otherwise create a new one.
949 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
Chris Lattnerb3364092006-10-04 21:49:37 +0000950 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr,
951 SCEVOps)];
Chris Lattner53e677a2004-04-02 20:23:17 +0000952 if (Result == 0) Result = new SCEVAddExpr(Ops);
953 return Result;
954}
955
956
Dan Gohman246b2562007-10-22 18:31:58 +0000957SCEVHandle ScalarEvolution::getMulExpr(std::vector<SCEVHandle> &Ops) {
Chris Lattner53e677a2004-04-02 20:23:17 +0000958 assert(!Ops.empty() && "Cannot get empty mul!");
959
960 // Sort by complexity, this groups all similar expression types together.
Chris Lattner8d741b82004-06-20 06:23:15 +0000961 GroupByComplexity(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +0000962
963 // If there are any constants, fold them together.
964 unsigned Idx = 0;
965 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
966
967 // C1*(C2+V) -> C1*C2 + C1*V
968 if (Ops.size() == 2)
969 if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
970 if (Add->getNumOperands() == 2 &&
971 isa<SCEVConstant>(Add->getOperand(0)))
Dan Gohman246b2562007-10-22 18:31:58 +0000972 return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
973 getMulExpr(LHSC, Add->getOperand(1)));
Chris Lattner53e677a2004-04-02 20:23:17 +0000974
975
976 ++Idx;
977 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
978 // We found two constants, fold them together!
Nick Lewycky3e630762008-02-20 06:48:22 +0000979 ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
980 RHSC->getValue()->getValue());
981 Ops[0] = getConstant(Fold);
982 Ops.erase(Ops.begin()+1); // Erase the folded element
983 if (Ops.size() == 1) return Ops[0];
984 LHSC = cast<SCEVConstant>(Ops[0]);
Chris Lattner53e677a2004-04-02 20:23:17 +0000985 }
986
987 // If we are left with a constant one being multiplied, strip it off.
988 if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) {
989 Ops.erase(Ops.begin());
990 --Idx;
Reid Spencercae57542007-03-02 00:28:52 +0000991 } else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
Chris Lattner53e677a2004-04-02 20:23:17 +0000992 // If we have a multiply of zero, it will always be zero.
993 return Ops[0];
994 }
995 }
996
997 // Skip over the add expression until we get to a multiply.
998 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
999 ++Idx;
1000
1001 if (Ops.size() == 1)
1002 return Ops[0];
Misha Brukman2b37d7c2005-04-21 21:13:18 +00001003
Chris Lattner53e677a2004-04-02 20:23:17 +00001004 // If there are mul operands inline them all into this expression.
1005 if (Idx < Ops.size()) {
1006 bool DeletedMul = false;
1007 while (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
1008 // If we have an mul, expand the mul operands onto the end of the operands
1009 // list.
1010 Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end());
1011 Ops.erase(Ops.begin()+Idx);
1012 DeletedMul = true;
1013 }
1014
1015 // If we deleted at least one mul, we added operands to the end of the list,
1016 // and they are not necessarily sorted. Recurse to resort and resimplify
1017 // any operands we just aquired.
1018 if (DeletedMul)
Dan Gohman246b2562007-10-22 18:31:58 +00001019 return getMulExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +00001020 }
1021
1022 // If there are any add recurrences in the operands list, see if any other
1023 // added values are loop invariant. If so, we can fold them into the
1024 // recurrence.
1025 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
1026 ++Idx;
1027
1028 // Scan over all recurrences, trying to fold loop invariants into them.
1029 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
1030 // Scan all of the other operands to this mul and add them to the vector if
1031 // they are loop invariant w.r.t. the recurrence.
1032 std::vector<SCEVHandle> LIOps;
1033 SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
1034 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1035 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
1036 LIOps.push_back(Ops[i]);
1037 Ops.erase(Ops.begin()+i);
1038 --i; --e;
1039 }
1040
1041 // If we found some loop invariants, fold them into the recurrence.
1042 if (!LIOps.empty()) {
Dan Gohman8dae1382008-09-14 17:21:12 +00001043 // NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step}
Chris Lattner53e677a2004-04-02 20:23:17 +00001044 std::vector<SCEVHandle> NewOps;
1045 NewOps.reserve(AddRec->getNumOperands());
1046 if (LIOps.size() == 1) {
1047 SCEV *Scale = LIOps[0];
1048 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
Dan Gohman246b2562007-10-22 18:31:58 +00001049 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
Chris Lattner53e677a2004-04-02 20:23:17 +00001050 } else {
1051 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
1052 std::vector<SCEVHandle> MulOps(LIOps);
1053 MulOps.push_back(AddRec->getOperand(i));
Dan Gohman246b2562007-10-22 18:31:58 +00001054 NewOps.push_back(getMulExpr(MulOps));
Chris Lattner53e677a2004-04-02 20:23:17 +00001055 }
1056 }
1057
Dan Gohman246b2562007-10-22 18:31:58 +00001058 SCEVHandle NewRec = getAddRecExpr(NewOps, AddRec->getLoop());
Chris Lattner53e677a2004-04-02 20:23:17 +00001059
1060 // If all of the other operands were loop invariant, we are done.
1061 if (Ops.size() == 1) return NewRec;
1062
1063 // Otherwise, multiply the folded AddRec by the non-liv parts.
1064 for (unsigned i = 0;; ++i)
1065 if (Ops[i] == AddRec) {
1066 Ops[i] = NewRec;
1067 break;
1068 }
Dan Gohman246b2562007-10-22 18:31:58 +00001069 return getMulExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +00001070 }
1071
1072 // Okay, if there weren't any loop invariants to be folded, check to see if
1073 // there are multiple AddRec's with the same loop induction variable being
1074 // multiplied together. If so, we can fold them.
1075 for (unsigned OtherIdx = Idx+1;
1076 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
1077 if (OtherIdx != Idx) {
1078 SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
1079 if (AddRec->getLoop() == OtherAddRec->getLoop()) {
1080 // F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D}
1081 SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
Dan Gohman246b2562007-10-22 18:31:58 +00001082 SCEVHandle NewStart = getMulExpr(F->getStart(),
Chris Lattner53e677a2004-04-02 20:23:17 +00001083 G->getStart());
Dan Gohman246b2562007-10-22 18:31:58 +00001084 SCEVHandle B = F->getStepRecurrence(*this);
1085 SCEVHandle D = G->getStepRecurrence(*this);
1086 SCEVHandle NewStep = getAddExpr(getMulExpr(F, D),
1087 getMulExpr(G, B),
1088 getMulExpr(B, D));
1089 SCEVHandle NewAddRec = getAddRecExpr(NewStart, NewStep,
1090 F->getLoop());
Chris Lattner53e677a2004-04-02 20:23:17 +00001091 if (Ops.size() == 2) return NewAddRec;
1092
1093 Ops.erase(Ops.begin()+Idx);
1094 Ops.erase(Ops.begin()+OtherIdx-1);
1095 Ops.push_back(NewAddRec);
Dan Gohman246b2562007-10-22 18:31:58 +00001096 return getMulExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +00001097 }
1098 }
1099
1100 // Otherwise couldn't fold anything into this recurrence. Move onto the
1101 // next one.
1102 }
1103
1104 // Okay, it looks like we really DO need an mul expr. Check to see if we
1105 // already have one, otherwise create a new one.
1106 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
Chris Lattnerb3364092006-10-04 21:49:37 +00001107 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr,
1108 SCEVOps)];
Chris Lattner6a1a78a2004-12-04 20:54:32 +00001109 if (Result == 0)
1110 Result = new SCEVMulExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +00001111 return Result;
1112}
1113
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +00001114SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
Chris Lattner53e677a2004-04-02 20:23:17 +00001115 if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
1116 if (RHSC->getValue()->equalsInt(1))
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +00001117 return LHS; // X udiv 1 --> x
Chris Lattner53e677a2004-04-02 20:23:17 +00001118
1119 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
1120 Constant *LHSCV = LHSC->getValue();
1121 Constant *RHSCV = RHSC->getValue();
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +00001122 return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV));
Chris Lattner53e677a2004-04-02 20:23:17 +00001123 }
1124 }
1125
1126 // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow.
1127
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +00001128 SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)];
1129 if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
Chris Lattner53e677a2004-04-02 20:23:17 +00001130 return Result;
1131}
1132
1133
1134/// SCEVAddRecExpr::get - Get a add recurrence expression for the
1135/// specified loop. Simplify the expression as much as possible.
Dan Gohman246b2562007-10-22 18:31:58 +00001136SCEVHandle ScalarEvolution::getAddRecExpr(const SCEVHandle &Start,
Chris Lattner53e677a2004-04-02 20:23:17 +00001137 const SCEVHandle &Step, const Loop *L) {
1138 std::vector<SCEVHandle> Operands;
1139 Operands.push_back(Start);
1140 if (SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
1141 if (StepChrec->getLoop() == L) {
1142 Operands.insert(Operands.end(), StepChrec->op_begin(),
1143 StepChrec->op_end());
Dan Gohman246b2562007-10-22 18:31:58 +00001144 return getAddRecExpr(Operands, L);
Chris Lattner53e677a2004-04-02 20:23:17 +00001145 }
1146
1147 Operands.push_back(Step);
Dan Gohman246b2562007-10-22 18:31:58 +00001148 return getAddRecExpr(Operands, L);
Chris Lattner53e677a2004-04-02 20:23:17 +00001149}
1150
1151/// SCEVAddRecExpr::get - Get a add recurrence expression for the
1152/// specified loop. Simplify the expression as much as possible.
Dan Gohman246b2562007-10-22 18:31:58 +00001153SCEVHandle ScalarEvolution::getAddRecExpr(std::vector<SCEVHandle> &Operands,
Chris Lattner53e677a2004-04-02 20:23:17 +00001154 const Loop *L) {
1155 if (Operands.size() == 1) return Operands[0];
1156
Dan Gohmancfeb6a42008-06-18 16:23:07 +00001157 if (Operands.back()->isZero()) {
1158 Operands.pop_back();
Dan Gohman8dae1382008-09-14 17:21:12 +00001159 return getAddRecExpr(Operands, L); // {X,+,0} --> X
Dan Gohmancfeb6a42008-06-18 16:23:07 +00001160 }
Chris Lattner53e677a2004-04-02 20:23:17 +00001161
Dan Gohmand9cc7492008-08-08 18:33:12 +00001162 // Canonicalize nested AddRecs in by nesting them in order of loop depth.
1163 if (SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
1164 const Loop* NestedLoop = NestedAR->getLoop();
1165 if (L->getLoopDepth() < NestedLoop->getLoopDepth()) {
1166 std::vector<SCEVHandle> NestedOperands(NestedAR->op_begin(),
1167 NestedAR->op_end());
1168 SCEVHandle NestedARHandle(NestedAR);
1169 Operands[0] = NestedAR->getStart();
1170 NestedOperands[0] = getAddRecExpr(Operands, L);
1171 return getAddRecExpr(NestedOperands, NestedLoop);
1172 }
1173 }
1174
Chris Lattner53e677a2004-04-02 20:23:17 +00001175 SCEVAddRecExpr *&Result =
Chris Lattnerb3364092006-10-04 21:49:37 +00001176 (*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
1177 Operands.end()))];
Chris Lattner53e677a2004-04-02 20:23:17 +00001178 if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
1179 return Result;
1180}
1181
Nick Lewyckyc54c5612007-11-25 22:41:31 +00001182SCEVHandle ScalarEvolution::getSMaxExpr(const SCEVHandle &LHS,
1183 const SCEVHandle &RHS) {
1184 std::vector<SCEVHandle> Ops;
1185 Ops.push_back(LHS);
1186 Ops.push_back(RHS);
1187 return getSMaxExpr(Ops);
1188}
1189
1190SCEVHandle ScalarEvolution::getSMaxExpr(std::vector<SCEVHandle> Ops) {
1191 assert(!Ops.empty() && "Cannot get empty smax!");
1192 if (Ops.size() == 1) return Ops[0];
1193
1194 // Sort by complexity, this groups all similar expression types together.
1195 GroupByComplexity(Ops);
1196
1197 // If there are any constants, fold them together.
1198 unsigned Idx = 0;
1199 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1200 ++Idx;
1201 assert(Idx < Ops.size());
1202 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1203 // We found two constants, fold them together!
Nick Lewycky3e630762008-02-20 06:48:22 +00001204 ConstantInt *Fold = ConstantInt::get(
Nick Lewyckyc54c5612007-11-25 22:41:31 +00001205 APIntOps::smax(LHSC->getValue()->getValue(),
1206 RHSC->getValue()->getValue()));
Nick Lewycky3e630762008-02-20 06:48:22 +00001207 Ops[0] = getConstant(Fold);
1208 Ops.erase(Ops.begin()+1); // Erase the folded element
1209 if (Ops.size() == 1) return Ops[0];
1210 LHSC = cast<SCEVConstant>(Ops[0]);
Nick Lewyckyc54c5612007-11-25 22:41:31 +00001211 }
1212
1213 // If we are left with a constant -inf, strip it off.
1214 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) {
1215 Ops.erase(Ops.begin());
1216 --Idx;
1217 }
1218 }
1219
1220 if (Ops.size() == 1) return Ops[0];
1221
1222 // Find the first SMax
1223 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr)
1224 ++Idx;
1225
1226 // Check to see if one of the operands is an SMax. If so, expand its operands
1227 // onto our operand list, and recurse to simplify.
1228 if (Idx < Ops.size()) {
1229 bool DeletedSMax = false;
1230 while (SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
1231 Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end());
1232 Ops.erase(Ops.begin()+Idx);
1233 DeletedSMax = true;
1234 }
1235
1236 if (DeletedSMax)
1237 return getSMaxExpr(Ops);
1238 }
1239
1240 // Okay, check to see if the same value occurs in the operand list twice. If
1241 // so, delete one. Since we sorted the list, these values are required to
1242 // be adjacent.
1243 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
1244 if (Ops[i] == Ops[i+1]) { // X smax Y smax Y --> X smax Y
1245 Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
1246 --i; --e;
1247 }
1248
1249 if (Ops.size() == 1) return Ops[0];
1250
1251 assert(!Ops.empty() && "Reduced smax down to nothing!");
1252
Nick Lewycky3e630762008-02-20 06:48:22 +00001253 // Okay, it looks like we really DO need an smax expr. Check to see if we
Nick Lewyckyc54c5612007-11-25 22:41:31 +00001254 // already have one, otherwise create a new one.
1255 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
1256 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr,
1257 SCEVOps)];
1258 if (Result == 0) Result = new SCEVSMaxExpr(Ops);
1259 return Result;
1260}
1261
Nick Lewycky3e630762008-02-20 06:48:22 +00001262SCEVHandle ScalarEvolution::getUMaxExpr(const SCEVHandle &LHS,
1263 const SCEVHandle &RHS) {
1264 std::vector<SCEVHandle> Ops;
1265 Ops.push_back(LHS);
1266 Ops.push_back(RHS);
1267 return getUMaxExpr(Ops);
1268}
1269
1270SCEVHandle ScalarEvolution::getUMaxExpr(std::vector<SCEVHandle> Ops) {
1271 assert(!Ops.empty() && "Cannot get empty umax!");
1272 if (Ops.size() == 1) return Ops[0];
1273
1274 // Sort by complexity, this groups all similar expression types together.
1275 GroupByComplexity(Ops);
1276
1277 // If there are any constants, fold them together.
1278 unsigned Idx = 0;
1279 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1280 ++Idx;
1281 assert(Idx < Ops.size());
1282 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1283 // We found two constants, fold them together!
1284 ConstantInt *Fold = ConstantInt::get(
1285 APIntOps::umax(LHSC->getValue()->getValue(),
1286 RHSC->getValue()->getValue()));
1287 Ops[0] = getConstant(Fold);
1288 Ops.erase(Ops.begin()+1); // Erase the folded element
1289 if (Ops.size() == 1) return Ops[0];
1290 LHSC = cast<SCEVConstant>(Ops[0]);
1291 }
1292
1293 // If we are left with a constant zero, strip it off.
1294 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) {
1295 Ops.erase(Ops.begin());
1296 --Idx;
1297 }
1298 }
1299
1300 if (Ops.size() == 1) return Ops[0];
1301
1302 // Find the first UMax
1303 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr)
1304 ++Idx;
1305
1306 // Check to see if one of the operands is a UMax. If so, expand its operands
1307 // onto our operand list, and recurse to simplify.
1308 if (Idx < Ops.size()) {
1309 bool DeletedUMax = false;
1310 while (SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
1311 Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end());
1312 Ops.erase(Ops.begin()+Idx);
1313 DeletedUMax = true;
1314 }
1315
1316 if (DeletedUMax)
1317 return getUMaxExpr(Ops);
1318 }
1319
1320 // Okay, check to see if the same value occurs in the operand list twice. If
1321 // so, delete one. Since we sorted the list, these values are required to
1322 // be adjacent.
1323 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
1324 if (Ops[i] == Ops[i+1]) { // X umax Y umax Y --> X umax Y
1325 Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
1326 --i; --e;
1327 }
1328
1329 if (Ops.size() == 1) return Ops[0];
1330
1331 assert(!Ops.empty() && "Reduced umax down to nothing!");
1332
1333 // Okay, it looks like we really DO need a umax expr. Check to see if we
1334 // already have one, otherwise create a new one.
1335 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
1336 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr,
1337 SCEVOps)];
1338 if (Result == 0) Result = new SCEVUMaxExpr(Ops);
1339 return Result;
1340}
1341
Dan Gohman246b2562007-10-22 18:31:58 +00001342SCEVHandle ScalarEvolution::getUnknown(Value *V) {
Chris Lattner0a7f98c2004-04-15 15:07:24 +00001343 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
Dan Gohman246b2562007-10-22 18:31:58 +00001344 return getConstant(CI);
Chris Lattnerb3364092006-10-04 21:49:37 +00001345 SCEVUnknown *&Result = (*SCEVUnknowns)[V];
Chris Lattner0a7f98c2004-04-15 15:07:24 +00001346 if (Result == 0) Result = new SCEVUnknown(V);
1347 return Result;
1348}
1349
Chris Lattner53e677a2004-04-02 20:23:17 +00001350
1351//===----------------------------------------------------------------------===//
Chris Lattner53e677a2004-04-02 20:23:17 +00001352// ScalarEvolutionsImpl Definition and Implementation
1353//===----------------------------------------------------------------------===//
1354//
1355/// ScalarEvolutionsImpl - This class implements the main driver for the scalar
1356/// evolution code.
1357///
1358namespace {
Chris Lattner95255282006-06-28 23:17:24 +00001359 struct VISIBILITY_HIDDEN ScalarEvolutionsImpl {
Dan Gohman246b2562007-10-22 18:31:58 +00001360 /// SE - A reference to the public ScalarEvolution object.
1361 ScalarEvolution &SE;
1362
Chris Lattner53e677a2004-04-02 20:23:17 +00001363 /// F - The function we are analyzing.
1364 ///
1365 Function &F;
1366
1367 /// LI - The loop information for the function we are currently analyzing.
1368 ///
1369 LoopInfo &LI;
1370
1371 /// UnknownValue - This SCEV is used to represent unknown trip counts and
1372 /// things.
1373 SCEVHandle UnknownValue;
1374
1375 /// Scalars - This is a cache of the scalars we have analyzed so far.
1376 ///
1377 std::map<Value*, SCEVHandle> Scalars;
1378
1379 /// IterationCounts - Cache the iteration count of the loops for this
1380 /// function as they are computed.
1381 std::map<const Loop*, SCEVHandle> IterationCounts;
1382
Chris Lattner3221ad02004-04-17 22:58:41 +00001383 /// ConstantEvolutionLoopExitValue - This map contains entries for all of
1384 /// the PHI instructions that we attempt to compute constant evolutions for.
1385 /// This allows us to avoid potentially expensive recomputation of these
1386 /// properties. An instruction maps to null if we are unable to compute its
1387 /// exit value.
1388 std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
Misha Brukman2b37d7c2005-04-21 21:13:18 +00001389
Chris Lattner53e677a2004-04-02 20:23:17 +00001390 public:
Dan Gohman246b2562007-10-22 18:31:58 +00001391 ScalarEvolutionsImpl(ScalarEvolution &se, Function &f, LoopInfo &li)
1392 : SE(se), F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {}
Chris Lattner53e677a2004-04-02 20:23:17 +00001393
1394 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1395 /// expression and create a new one.
1396 SCEVHandle getSCEV(Value *V);
1397
Chris Lattnera0740fb2005-08-09 23:36:33 +00001398 /// hasSCEV - Return true if the SCEV for this value has already been
1399 /// computed.
1400 bool hasSCEV(Value *V) const {
1401 return Scalars.count(V);
1402 }
1403
1404 /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
1405 /// the specified value.
1406 void setSCEV(Value *V, const SCEVHandle &H) {
1407 bool isNew = Scalars.insert(std::make_pair(V, H)).second;
1408 assert(isNew && "This entry already existed!");
1409 }
1410
1411
Chris Lattner53e677a2004-04-02 20:23:17 +00001412 /// getSCEVAtScope - Compute the value of the specified expression within
1413 /// the indicated loop (which may be null to indicate in no loop). If the
1414 /// expression cannot be evaluated, return UnknownValue itself.
1415 SCEVHandle getSCEVAtScope(SCEV *V, const Loop *L);
1416
1417
1418 /// hasLoopInvariantIterationCount - Return true if the specified loop has
1419 /// an analyzable loop-invariant iteration count.
1420 bool hasLoopInvariantIterationCount(const Loop *L);
1421
1422 /// getIterationCount - If the specified loop has a predictable iteration
1423 /// count, return it. Note that it is not valid to call this method on a
1424 /// loop without a loop-invariant iteration count.
1425 SCEVHandle getIterationCount(const Loop *L);
1426
Dan Gohman5cec4db2007-06-19 14:28:31 +00001427 /// deleteValueFromRecords - This method should be called by the
1428 /// client before it removes a value from the program, to make sure
Chris Lattner53e677a2004-04-02 20:23:17 +00001429 /// that no dangling references are left around.
Dan Gohman5cec4db2007-06-19 14:28:31 +00001430 void deleteValueFromRecords(Value *V);
Chris Lattner53e677a2004-04-02 20:23:17 +00001431
1432 private:
1433 /// createSCEV - We know that there is no SCEV for the specified value.
1434 /// Analyze the expression.
1435 SCEVHandle createSCEV(Value *V);
Chris Lattner53e677a2004-04-02 20:23:17 +00001436
1437 /// createNodeForPHI - Provide the special handling we need to analyze PHI
1438 /// SCEVs.
1439 SCEVHandle createNodeForPHI(PHINode *PN);
Chris Lattner4dc534c2005-02-13 04:37:18 +00001440
1441 /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value
1442 /// for the specified instruction and replaces any references to the
1443 /// symbolic value SymName with the specified value. This is used during
1444 /// PHI resolution.
1445 void ReplaceSymbolicValueWithConcrete(Instruction *I,
1446 const SCEVHandle &SymName,
1447 const SCEVHandle &NewVal);
Chris Lattner53e677a2004-04-02 20:23:17 +00001448
1449 /// ComputeIterationCount - Compute the number of times the specified loop
1450 /// will iterate.
1451 SCEVHandle ComputeIterationCount(const Loop *L);
1452
Chris Lattner673e02b2004-10-12 01:49:27 +00001453 /// ComputeLoadConstantCompareIterationCount - Given an exit condition of
Nick Lewycky6e801dc2007-11-20 08:44:50 +00001454 /// 'icmp op load X, cst', try to see if we can compute the trip count.
Chris Lattner673e02b2004-10-12 01:49:27 +00001455 SCEVHandle ComputeLoadConstantCompareIterationCount(LoadInst *LI,
1456 Constant *RHS,
1457 const Loop *L,
Reid Spencere4d87aa2006-12-23 06:05:41 +00001458 ICmpInst::Predicate p);
Chris Lattner673e02b2004-10-12 01:49:27 +00001459
Chris Lattner7980fb92004-04-17 18:36:24 +00001460 /// ComputeIterationCountExhaustively - If the trip is known to execute a
1461 /// constant number of times (the condition evolves only from constants),
1462 /// try to evaluate a few iterations of the loop until we get the exit
1463 /// condition gets a value of ExitWhen (true or false). If we cannot
1464 /// evaluate the trip count of the loop, return UnknownValue.
1465 SCEVHandle ComputeIterationCountExhaustively(const Loop *L, Value *Cond,
1466 bool ExitWhen);
1467
Chris Lattner53e677a2004-04-02 20:23:17 +00001468 /// HowFarToZero - Return the number of times a backedge comparing the
1469 /// specified value to zero will execute. If not computable, return
Chris Lattnerdb25de42005-08-15 23:33:51 +00001470 /// UnknownValue.
Chris Lattner53e677a2004-04-02 20:23:17 +00001471 SCEVHandle HowFarToZero(SCEV *V, const Loop *L);
1472
1473 /// HowFarToNonZero - Return the number of times a backedge checking the
1474 /// specified value for nonzero will execute. If not computable, return
Chris Lattnerdb25de42005-08-15 23:33:51 +00001475 /// UnknownValue.
Chris Lattner53e677a2004-04-02 20:23:17 +00001476 SCEVHandle HowFarToNonZero(SCEV *V, const Loop *L);
Chris Lattner3221ad02004-04-17 22:58:41 +00001477
Chris Lattnerdb25de42005-08-15 23:33:51 +00001478 /// HowManyLessThans - Return the number of times a backedge containing the
1479 /// specified less-than comparison will execute. If not computable, return
Nick Lewyckyd6dac0e2007-08-06 19:21:00 +00001480 /// UnknownValue. isSigned specifies whether the less-than is signed.
1481 SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L,
1482 bool isSigned);
Chris Lattnerdb25de42005-08-15 23:33:51 +00001483
Dan Gohmanfd6edef2008-09-15 22:18:04 +00001484 /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
1485 /// (which may not be an immediate predecessor) which has exactly one
1486 /// successor from which BB is reachable, or null if no such block is
1487 /// found.
1488 BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
1489
Nick Lewycky59cff122008-07-12 07:41:32 +00001490 /// executesAtLeastOnce - Test whether entry to the loop is protected by
1491 /// a conditional between LHS and RHS.
1492 bool executesAtLeastOnce(const Loop *L, bool isSigned, SCEV *LHS, SCEV *RHS);
1493
Chris Lattner3221ad02004-04-17 22:58:41 +00001494 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
1495 /// in the header of its containing loop, we know the loop executes a
1496 /// constant number of times, and the PHI node is just a recurrence
1497 /// involving constants, fold it.
Reid Spencere8019bb2007-03-01 07:25:48 +00001498 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its,
Chris Lattner3221ad02004-04-17 22:58:41 +00001499 const Loop *L);
Chris Lattner53e677a2004-04-02 20:23:17 +00001500 };
1501}
1502
1503//===----------------------------------------------------------------------===//
1504// Basic SCEV Analysis and PHI Idiom Recognition Code
1505//
1506
Dan Gohman5cec4db2007-06-19 14:28:31 +00001507/// deleteValueFromRecords - This method should be called by the
Chris Lattner53e677a2004-04-02 20:23:17 +00001508/// client before it removes an instruction from the program, to make sure
1509/// that no dangling references are left around.
Dan Gohman5cec4db2007-06-19 14:28:31 +00001510void ScalarEvolutionsImpl::deleteValueFromRecords(Value *V) {
1511 SmallVector<Value *, 16> Worklist;
Nick Lewycky9d0332f2007-06-06 04:12:20 +00001512
Dan Gohman5cec4db2007-06-19 14:28:31 +00001513 if (Scalars.erase(V)) {
1514 if (PHINode *PN = dyn_cast<PHINode>(V))
Nick Lewycky9d0332f2007-06-06 04:12:20 +00001515 ConstantEvolutionLoopExitValue.erase(PN);
Dan Gohman5cec4db2007-06-19 14:28:31 +00001516 Worklist.push_back(V);
Nick Lewycky9d0332f2007-06-06 04:12:20 +00001517 }
1518
1519 while (!Worklist.empty()) {
Dan Gohman5cec4db2007-06-19 14:28:31 +00001520 Value *VV = Worklist.back();
Nick Lewycky9d0332f2007-06-06 04:12:20 +00001521 Worklist.pop_back();
1522
Dan Gohman5cec4db2007-06-19 14:28:31 +00001523 for (Instruction::use_iterator UI = VV->use_begin(), UE = VV->use_end();
Nick Lewycky9d0332f2007-06-06 04:12:20 +00001524 UI != UE; ++UI) {
Nick Lewycky51e844b2007-06-06 11:26:20 +00001525 Instruction *Inst = cast<Instruction>(*UI);
1526 if (Scalars.erase(Inst)) {
Dan Gohman5cec4db2007-06-19 14:28:31 +00001527 if (PHINode *PN = dyn_cast<PHINode>(VV))
Nick Lewycky9d0332f2007-06-06 04:12:20 +00001528 ConstantEvolutionLoopExitValue.erase(PN);
1529 Worklist.push_back(Inst);
1530 }
1531 }
1532 }
Chris Lattner53e677a2004-04-02 20:23:17 +00001533}
1534
1535
1536/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1537/// expression and create a new one.
1538SCEVHandle ScalarEvolutionsImpl::getSCEV(Value *V) {
1539 assert(V->getType() != Type::VoidTy && "Can't analyze void expressions!");
1540
1541 std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V);
1542 if (I != Scalars.end()) return I->second;
1543 SCEVHandle S = createSCEV(V);
1544 Scalars.insert(std::make_pair(V, S));
1545 return S;
1546}
1547
Chris Lattner4dc534c2005-02-13 04:37:18 +00001548/// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for
1549/// the specified instruction and replaces any references to the symbolic value
1550/// SymName with the specified value. This is used during PHI resolution.
1551void ScalarEvolutionsImpl::
1552ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName,
1553 const SCEVHandle &NewVal) {
Chris Lattner53e677a2004-04-02 20:23:17 +00001554 std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I);
Chris Lattner4dc534c2005-02-13 04:37:18 +00001555 if (SI == Scalars.end()) return;
Chris Lattner53e677a2004-04-02 20:23:17 +00001556
Chris Lattner4dc534c2005-02-13 04:37:18 +00001557 SCEVHandle NV =
Dan Gohman246b2562007-10-22 18:31:58 +00001558 SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, SE);
Chris Lattner4dc534c2005-02-13 04:37:18 +00001559 if (NV == SI->second) return; // No change.
1560
1561 SI->second = NV; // Update the scalars map!
1562
1563 // Any instruction values that use this instruction might also need to be
1564 // updated!
1565 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
1566 UI != E; ++UI)
1567 ReplaceSymbolicValueWithConcrete(cast<Instruction>(*UI), SymName, NewVal);
1568}
Chris Lattner53e677a2004-04-02 20:23:17 +00001569
1570/// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in
1571/// a loop header, making it a potential recurrence, or it doesn't.
1572///
1573SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) {
1574 if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized.
1575 if (const Loop *L = LI.getLoopFor(PN->getParent()))
1576 if (L->getHeader() == PN->getParent()) {
1577 // If it lives in the loop header, it has two incoming values, one
1578 // from outside the loop, and one from inside.
1579 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
1580 unsigned BackEdge = IncomingEdge^1;
Misha Brukman2b37d7c2005-04-21 21:13:18 +00001581
Chris Lattner53e677a2004-04-02 20:23:17 +00001582 // While we are analyzing this PHI node, handle its value symbolically.
Dan Gohman246b2562007-10-22 18:31:58 +00001583 SCEVHandle SymbolicName = SE.getUnknown(PN);
Chris Lattner53e677a2004-04-02 20:23:17 +00001584 assert(Scalars.find(PN) == Scalars.end() &&
1585 "PHI node already processed?");
1586 Scalars.insert(std::make_pair(PN, SymbolicName));
1587
1588 // Using this symbolic name for the PHI, analyze the value coming around
1589 // the back-edge.
1590 SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge));
1591
1592 // NOTE: If BEValue is loop invariant, we know that the PHI node just
1593 // has a special value for the first iteration of the loop.
1594
1595 // If the value coming around the backedge is an add with the symbolic
1596 // value we just inserted, then we found a simple induction variable!
1597 if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
1598 // If there is a single occurrence of the symbolic value, replace it
1599 // with a recurrence.
1600 unsigned FoundIndex = Add->getNumOperands();
1601 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
1602 if (Add->getOperand(i) == SymbolicName)
1603 if (FoundIndex == e) {
1604 FoundIndex = i;
1605 break;
1606 }
1607
1608 if (FoundIndex != Add->getNumOperands()) {
1609 // Create an add with everything but the specified operand.
1610 std::vector<SCEVHandle> Ops;
1611 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
1612 if (i != FoundIndex)
1613 Ops.push_back(Add->getOperand(i));
Dan Gohman246b2562007-10-22 18:31:58 +00001614 SCEVHandle Accum = SE.getAddExpr(Ops);
Chris Lattner53e677a2004-04-02 20:23:17 +00001615
1616 // This is not a valid addrec if the step amount is varying each
1617 // loop iteration, but is not itself an addrec in this loop.
1618 if (Accum->isLoopInvariant(L) ||
1619 (isa<SCEVAddRecExpr>(Accum) &&
1620 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
1621 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
Dan Gohman246b2562007-10-22 18:31:58 +00001622 SCEVHandle PHISCEV = SE.getAddRecExpr(StartVal, Accum, L);
Chris Lattner53e677a2004-04-02 20:23:17 +00001623
1624 // Okay, for the entire analysis of this edge we assumed the PHI
1625 // to be symbolic. We now need to go back and update all of the
1626 // entries for the scalars that use the PHI (except for the PHI
1627 // itself) to use the new analyzed value instead of the "symbolic"
1628 // value.
Chris Lattner4dc534c2005-02-13 04:37:18 +00001629 ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
Chris Lattner53e677a2004-04-02 20:23:17 +00001630 return PHISCEV;
1631 }
1632 }
Chris Lattner97156e72006-04-26 18:34:07 +00001633 } else if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(BEValue)) {
1634 // Otherwise, this could be a loop like this:
1635 // i = 0; for (j = 1; ..; ++j) { .... i = j; }
1636 // In this case, j = {1,+,1} and BEValue is j.
1637 // Because the other in-value of i (0) fits the evolution of BEValue
1638 // i really is an addrec evolution.
1639 if (AddRec->getLoop() == L && AddRec->isAffine()) {
1640 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
1641
1642 // If StartVal = j.start - j.stride, we can use StartVal as the
1643 // initial step of the addrec evolution.
Dan Gohman246b2562007-10-22 18:31:58 +00001644 if (StartVal == SE.getMinusSCEV(AddRec->getOperand(0),
1645 AddRec->getOperand(1))) {
Chris Lattner97156e72006-04-26 18:34:07 +00001646 SCEVHandle PHISCEV =
Dan Gohman246b2562007-10-22 18:31:58 +00001647 SE.getAddRecExpr(StartVal, AddRec->getOperand(1), L);
Chris Lattner97156e72006-04-26 18:34:07 +00001648
1649 // Okay, for the entire analysis of this edge we assumed the PHI
1650 // to be symbolic. We now need to go back and update all of the
1651 // entries for the scalars that use the PHI (except for the PHI
1652 // itself) to use the new analyzed value instead of the "symbolic"
1653 // value.
1654 ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
1655 return PHISCEV;
1656 }
1657 }
Chris Lattner53e677a2004-04-02 20:23:17 +00001658 }
1659
1660 return SymbolicName;
1661 }
Misha Brukman2b37d7c2005-04-21 21:13:18 +00001662
Chris Lattner53e677a2004-04-02 20:23:17 +00001663 // If it's not a loop phi, we can't handle it yet.
Dan Gohman246b2562007-10-22 18:31:58 +00001664 return SE.getUnknown(PN);
Chris Lattner53e677a2004-04-02 20:23:17 +00001665}
1666
Nick Lewycky83bb0052007-11-22 07:59:40 +00001667/// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
1668/// guaranteed to end in (at every loop iteration). It is, at the same time,
1669/// the minimum number of times S is divisible by 2. For example, given {4,+,8}
1670/// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S.
1671static uint32_t GetMinTrailingZeros(SCEVHandle S) {
1672 if (SCEVConstant *C = dyn_cast<SCEVConstant>(S))
Chris Lattner8314a0c2007-11-23 22:36:49 +00001673 return C->getValue()->getValue().countTrailingZeros();
Chris Lattnera17f0392006-12-12 02:26:09 +00001674
Nick Lewycky6e801dc2007-11-20 08:44:50 +00001675 if (SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
Nick Lewycky83bb0052007-11-22 07:59:40 +00001676 return std::min(GetMinTrailingZeros(T->getOperand()), T->getBitWidth());
1677
1678 if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
1679 uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
1680 return OpRes == E->getOperand()->getBitWidth() ? E->getBitWidth() : OpRes;
1681 }
1682
1683 if (SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
1684 uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
1685 return OpRes == E->getOperand()->getBitWidth() ? E->getBitWidth() : OpRes;
1686 }
1687
Chris Lattnera17f0392006-12-12 02:26:09 +00001688 if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
Nick Lewycky83bb0052007-11-22 07:59:40 +00001689 // The result is the min of all operands results.
1690 uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
1691 for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
1692 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
1693 return MinOpRes;
Chris Lattnera17f0392006-12-12 02:26:09 +00001694 }
1695
1696 if (SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
Nick Lewycky83bb0052007-11-22 07:59:40 +00001697 // The result is the sum of all operands results.
1698 uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
1699 uint32_t BitWidth = M->getBitWidth();
1700 for (unsigned i = 1, e = M->getNumOperands();
1701 SumOpRes != BitWidth && i != e; ++i)
1702 SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)),
1703 BitWidth);
1704 return SumOpRes;
Chris Lattnera17f0392006-12-12 02:26:09 +00001705 }
Nick Lewycky83bb0052007-11-22 07:59:40 +00001706
Chris Lattnera17f0392006-12-12 02:26:09 +00001707 if (SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
Nick Lewycky83bb0052007-11-22 07:59:40 +00001708 // The result is the min of all operands results.
1709 uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
1710 for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
1711 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
1712 return MinOpRes;
Chris Lattnera17f0392006-12-12 02:26:09 +00001713 }
Nick Lewycky83bb0052007-11-22 07:59:40 +00001714
Nick Lewyckyc54c5612007-11-25 22:41:31 +00001715 if (SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
1716 // The result is the min of all operands results.
1717 uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
1718 for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
1719 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
1720 return MinOpRes;
1721 }
1722
Nick Lewycky3e630762008-02-20 06:48:22 +00001723 if (SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
1724 // The result is the min of all operands results.
1725 uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
1726 for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
1727 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
1728 return MinOpRes;
1729 }
1730
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +00001731 // SCEVUDivExpr, SCEVUnknown
Nick Lewycky83bb0052007-11-22 07:59:40 +00001732 return 0;
Chris Lattnera17f0392006-12-12 02:26:09 +00001733}
Chris Lattner53e677a2004-04-02 20:23:17 +00001734
1735/// createSCEV - We know that there is no SCEV for the specified value.
1736/// Analyze the expression.
1737///
1738SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
Chris Lattner42b5e082007-11-23 08:46:22 +00001739 if (!isa<IntegerType>(V->getType()))
1740 return SE.getUnknown(V);
1741
Dan Gohman6c459a22008-06-22 19:56:46 +00001742 unsigned Opcode = Instruction::UserOp1;
1743 if (Instruction *I = dyn_cast<Instruction>(V))
1744 Opcode = I->getOpcode();
1745 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
1746 Opcode = CE->getOpcode();
1747 else
1748 return SE.getUnknown(V);
Chris Lattner2811f2a2007-04-02 05:41:38 +00001749
Dan Gohman6c459a22008-06-22 19:56:46 +00001750 User *U = cast<User>(V);
1751 switch (Opcode) {
1752 case Instruction::Add:
1753 return SE.getAddExpr(getSCEV(U->getOperand(0)),
1754 getSCEV(U->getOperand(1)));
1755 case Instruction::Mul:
1756 return SE.getMulExpr(getSCEV(U->getOperand(0)),
1757 getSCEV(U->getOperand(1)));
1758 case Instruction::UDiv:
1759 return SE.getUDivExpr(getSCEV(U->getOperand(0)),
1760 getSCEV(U->getOperand(1)));
1761 case Instruction::Sub:
1762 return SE.getMinusSCEV(getSCEV(U->getOperand(0)),
1763 getSCEV(U->getOperand(1)));
1764 case Instruction::Or:
1765 // If the RHS of the Or is a constant, we may have something like:
1766 // X*4+1 which got turned into X*4|1. Handle this as an Add so loop
1767 // optimizations will transparently handle this case.
1768 //
1769 // In order for this transformation to be safe, the LHS must be of the
1770 // form X*(2^n) and the Or constant must be less than 2^n.
1771 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
1772 SCEVHandle LHS = getSCEV(U->getOperand(0));
1773 const APInt &CIVal = CI->getValue();
1774 if (GetMinTrailingZeros(LHS) >=
1775 (CIVal.getBitWidth() - CIVal.countLeadingZeros()))
1776 return SE.getAddExpr(LHS, getSCEV(U->getOperand(1)));
Chris Lattner53e677a2004-04-02 20:23:17 +00001777 }
Dan Gohman6c459a22008-06-22 19:56:46 +00001778 break;
1779 case Instruction::Xor:
Dan Gohman6c459a22008-06-22 19:56:46 +00001780 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
Nick Lewycky01eaf802008-07-07 06:15:49 +00001781 // If the RHS of the xor is a signbit, then this is just an add.
1782 // Instcombine turns add of signbit into xor as a strength reduction step.
Dan Gohman6c459a22008-06-22 19:56:46 +00001783 if (CI->getValue().isSignBit())
1784 return SE.getAddExpr(getSCEV(U->getOperand(0)),
1785 getSCEV(U->getOperand(1)));
Nick Lewycky01eaf802008-07-07 06:15:49 +00001786
1787 // If the RHS of xor is -1, then this is a not operation.
Dan Gohman6c459a22008-06-22 19:56:46 +00001788 else if (CI->isAllOnesValue())
1789 return SE.getNotSCEV(getSCEV(U->getOperand(0)));
1790 }
1791 break;
1792
1793 case Instruction::Shl:
1794 // Turn shift left of a constant amount into a multiply.
1795 if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
1796 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
1797 Constant *X = ConstantInt::get(
1798 APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
1799 return SE.getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X));
1800 }
1801 break;
1802
Nick Lewycky01eaf802008-07-07 06:15:49 +00001803 case Instruction::LShr:
1804 // Turn logical shift right of a constant into a unsigned divide.
1805 if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
1806 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
1807 Constant *X = ConstantInt::get(
1808 APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
1809 return SE.getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X));
1810 }
1811 break;
1812
Dan Gohman6c459a22008-06-22 19:56:46 +00001813 case Instruction::Trunc:
1814 return SE.getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
1815
1816 case Instruction::ZExt:
1817 return SE.getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
1818
1819 case Instruction::SExt:
1820 return SE.getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
1821
1822 case Instruction::BitCast:
1823 // BitCasts are no-op casts so we just eliminate the cast.
1824 if (U->getType()->isInteger() &&
1825 U->getOperand(0)->getType()->isInteger())
1826 return getSCEV(U->getOperand(0));
1827 break;
1828
1829 case Instruction::PHI:
1830 return createNodeForPHI(cast<PHINode>(U));
1831
1832 case Instruction::Select:
1833 // This could be a smax or umax that was lowered earlier.
1834 // Try to recover it.
1835 if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) {
1836 Value *LHS = ICI->getOperand(0);
1837 Value *RHS = ICI->getOperand(1);
1838 switch (ICI->getPredicate()) {
1839 case ICmpInst::ICMP_SLT:
1840 case ICmpInst::ICMP_SLE:
1841 std::swap(LHS, RHS);
1842 // fall through
1843 case ICmpInst::ICMP_SGT:
1844 case ICmpInst::ICMP_SGE:
1845 if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
1846 return SE.getSMaxExpr(getSCEV(LHS), getSCEV(RHS));
1847 else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
Eli Friedman1fbffe02008-07-30 04:36:32 +00001848 // ~smax(~x, ~y) == smin(x, y).
1849 return SE.getNotSCEV(SE.getSMaxExpr(
1850 SE.getNotSCEV(getSCEV(LHS)),
1851 SE.getNotSCEV(getSCEV(RHS))));
Dan Gohman6c459a22008-06-22 19:56:46 +00001852 break;
1853 case ICmpInst::ICMP_ULT:
1854 case ICmpInst::ICMP_ULE:
1855 std::swap(LHS, RHS);
1856 // fall through
1857 case ICmpInst::ICMP_UGT:
1858 case ICmpInst::ICMP_UGE:
1859 if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
1860 return SE.getUMaxExpr(getSCEV(LHS), getSCEV(RHS));
1861 else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
1862 // ~umax(~x, ~y) == umin(x, y)
1863 return SE.getNotSCEV(SE.getUMaxExpr(SE.getNotSCEV(getSCEV(LHS)),
1864 SE.getNotSCEV(getSCEV(RHS))));
1865 break;
1866 default:
1867 break;
1868 }
1869 }
1870
1871 default: // We cannot analyze this expression.
1872 break;
Chris Lattner53e677a2004-04-02 20:23:17 +00001873 }
1874
Dan Gohman246b2562007-10-22 18:31:58 +00001875 return SE.getUnknown(V);
Chris Lattner53e677a2004-04-02 20:23:17 +00001876}
1877
1878
1879
1880//===----------------------------------------------------------------------===//
1881// Iteration Count Computation Code
1882//
1883
1884/// getIterationCount - If the specified loop has a predictable iteration
1885/// count, return it. Note that it is not valid to call this method on a
1886/// loop without a loop-invariant iteration count.
1887SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) {
1888 std::map<const Loop*, SCEVHandle>::iterator I = IterationCounts.find(L);
1889 if (I == IterationCounts.end()) {
1890 SCEVHandle ItCount = ComputeIterationCount(L);
1891 I = IterationCounts.insert(std::make_pair(L, ItCount)).first;
1892 if (ItCount != UnknownValue) {
1893 assert(ItCount->isLoopInvariant(L) &&
1894 "Computed trip count isn't loop invariant for loop!");
1895 ++NumTripCountsComputed;
1896 } else if (isa<PHINode>(L->getHeader()->begin())) {
1897 // Only count loops that have phi nodes as not being computable.
1898 ++NumTripCountsNotComputed;
1899 }
1900 }
1901 return I->second;
1902}
1903
1904/// ComputeIterationCount - Compute the number of times the specified loop
1905/// will iterate.
1906SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
1907 // If the loop has a non-one exit block count, we can't analyze it.
Devang Patelb7211a22007-08-21 00:31:24 +00001908 SmallVector<BasicBlock*, 8> ExitBlocks;
Chris Lattnerf1ab4b42004-04-18 22:14:10 +00001909 L->getExitBlocks(ExitBlocks);
1910 if (ExitBlocks.size() != 1) return UnknownValue;
Chris Lattner53e677a2004-04-02 20:23:17 +00001911
1912 // Okay, there is one exit block. Try to find the condition that causes the
1913 // loop to be exited.
Chris Lattnerf1ab4b42004-04-18 22:14:10 +00001914 BasicBlock *ExitBlock = ExitBlocks[0];
Chris Lattner53e677a2004-04-02 20:23:17 +00001915
1916 BasicBlock *ExitingBlock = 0;
1917 for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock);
1918 PI != E; ++PI)
1919 if (L->contains(*PI)) {
1920 if (ExitingBlock == 0)
1921 ExitingBlock = *PI;
1922 else
1923 return UnknownValue; // More than one block exiting!
1924 }
1925 assert(ExitingBlock && "No exits from loop, something is broken!");
1926
1927 // Okay, we've computed the exiting block. See what condition causes us to
1928 // exit.
1929 //
1930 // FIXME: we should be able to handle switch instructions (with a single exit)
Chris Lattner53e677a2004-04-02 20:23:17 +00001931 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
1932 if (ExitBr == 0) return UnknownValue;
1933 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
Chris Lattner8b0e3602007-01-07 02:24:26 +00001934
1935 // At this point, we know we have a conditional branch that determines whether
1936 // the loop is exited. However, we don't know if the branch is executed each
1937 // time through the loop. If not, then the execution count of the branch will
1938 // not be equal to the trip count of the loop.
1939 //
1940 // Currently we check for this by checking to see if the Exit branch goes to
1941 // the loop header. If so, we know it will always execute the same number of
Chris Lattner192e4032007-01-14 01:24:47 +00001942 // times as the loop. We also handle the case where the exit block *is* the
1943 // loop header. This is common for un-rotated loops. More extensive analysis
1944 // could be done to handle more cases here.
Chris Lattner8b0e3602007-01-07 02:24:26 +00001945 if (ExitBr->getSuccessor(0) != L->getHeader() &&
Chris Lattner192e4032007-01-14 01:24:47 +00001946 ExitBr->getSuccessor(1) != L->getHeader() &&
1947 ExitBr->getParent() != L->getHeader())
Chris Lattner8b0e3602007-01-07 02:24:26 +00001948 return UnknownValue;
1949
Reid Spencere4d87aa2006-12-23 06:05:41 +00001950 ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
1951
Nick Lewycky3b711652008-02-21 08:34:02 +00001952 // If it's not an integer comparison then compute it the hard way.
Reid Spencere4d87aa2006-12-23 06:05:41 +00001953 // Note that ICmpInst deals with pointer comparisons too so we must check
1954 // the type of the operand.
Chris Lattner8b0e3602007-01-07 02:24:26 +00001955 if (ExitCond == 0 || isa<PointerType>(ExitCond->getOperand(0)->getType()))
Chris Lattner7980fb92004-04-17 18:36:24 +00001956 return ComputeIterationCountExhaustively(L, ExitBr->getCondition(),
1957 ExitBr->getSuccessor(0) == ExitBlock);
Chris Lattner53e677a2004-04-02 20:23:17 +00001958
Reid Spencere4d87aa2006-12-23 06:05:41 +00001959 // If the condition was exit on true, convert the condition to exit on false
1960 ICmpInst::Predicate Cond;
Chris Lattner673e02b2004-10-12 01:49:27 +00001961 if (ExitBr->getSuccessor(1) == ExitBlock)
Reid Spencere4d87aa2006-12-23 06:05:41 +00001962 Cond = ExitCond->getPredicate();
Chris Lattner673e02b2004-10-12 01:49:27 +00001963 else
Reid Spencere4d87aa2006-12-23 06:05:41 +00001964 Cond = ExitCond->getInversePredicate();
Chris Lattner673e02b2004-10-12 01:49:27 +00001965
1966 // Handle common loops like: for (X = "string"; *X; ++X)
1967 if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
1968 if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
1969 SCEVHandle ItCnt =
1970 ComputeLoadConstantCompareIterationCount(LI, RHS, L, Cond);
1971 if (!isa<SCEVCouldNotCompute>(ItCnt)) return ItCnt;
1972 }
1973
Chris Lattner53e677a2004-04-02 20:23:17 +00001974 SCEVHandle LHS = getSCEV(ExitCond->getOperand(0));
1975 SCEVHandle RHS = getSCEV(ExitCond->getOperand(1));
1976
1977 // Try to evaluate any dependencies out of the loop.
1978 SCEVHandle Tmp = getSCEVAtScope(LHS, L);
1979 if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp;
1980 Tmp = getSCEVAtScope(RHS, L);
1981 if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp;
1982
Reid Spencere4d87aa2006-12-23 06:05:41 +00001983 // At this point, we would like to compute how many iterations of the
1984 // loop the predicate will return true for these inputs.
Dan Gohman70ff4cf2008-09-16 18:52:57 +00001985 if (LHS->isLoopInvariant(L) && !RHS->isLoopInvariant(L)) {
1986 // If there is a loop-invariant, force it into the RHS.
Chris Lattner53e677a2004-04-02 20:23:17 +00001987 std::swap(LHS, RHS);
Reid Spencere4d87aa2006-12-23 06:05:41 +00001988 Cond = ICmpInst::getSwappedPredicate(Cond);
Chris Lattner53e677a2004-04-02 20:23:17 +00001989 }
1990
1991 // FIXME: think about handling pointer comparisons! i.e.:
1992 // while (P != P+100) ++P;
1993
1994 // If we have a comparison of a chrec against a constant, try to use value
1995 // ranges to answer this query.
1996 if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
1997 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
1998 if (AddRec->getLoop() == L) {
1999 // Form the comparison range using the constant of the correct type so
2000 // that the ConstantRange class knows to do a signed or unsigned
2001 // comparison.
2002 ConstantInt *CompVal = RHSC->getValue();
2003 const Type *RealTy = ExitCond->getOperand(0)->getType();
Reid Spencer4da49122006-12-12 05:05:00 +00002004 CompVal = dyn_cast<ConstantInt>(
Reid Spencerb6ba3e62006-12-12 09:17:50 +00002005 ConstantExpr::getBitCast(CompVal, RealTy));
Chris Lattner53e677a2004-04-02 20:23:17 +00002006 if (CompVal) {
2007 // Form the constant range.
Reid Spencerc6aedf72007-02-28 22:03:51 +00002008 ConstantRange CompRange(
2009 ICmpInst::makeConstantRange(Cond, CompVal->getValue()));
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002010
Dan Gohman246b2562007-10-22 18:31:58 +00002011 SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, SE);
Chris Lattner53e677a2004-04-02 20:23:17 +00002012 if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
2013 }
2014 }
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002015
Chris Lattner53e677a2004-04-02 20:23:17 +00002016 switch (Cond) {
Reid Spencere4d87aa2006-12-23 06:05:41 +00002017 case ICmpInst::ICMP_NE: { // while (X != Y)
Chris Lattner53e677a2004-04-02 20:23:17 +00002018 // Convert to: while (X-Y != 0)
Dan Gohman246b2562007-10-22 18:31:58 +00002019 SCEVHandle TC = HowFarToZero(SE.getMinusSCEV(LHS, RHS), L);
Reid Spencere4d87aa2006-12-23 06:05:41 +00002020 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
Chris Lattner53e677a2004-04-02 20:23:17 +00002021 break;
Reid Spencere4d87aa2006-12-23 06:05:41 +00002022 }
2023 case ICmpInst::ICMP_EQ: {
Chris Lattner53e677a2004-04-02 20:23:17 +00002024 // Convert to: while (X-Y == 0) // while (X == Y)
Dan Gohman246b2562007-10-22 18:31:58 +00002025 SCEVHandle TC = HowFarToNonZero(SE.getMinusSCEV(LHS, RHS), L);
Reid Spencere4d87aa2006-12-23 06:05:41 +00002026 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
Chris Lattner53e677a2004-04-02 20:23:17 +00002027 break;
Reid Spencere4d87aa2006-12-23 06:05:41 +00002028 }
2029 case ICmpInst::ICMP_SLT: {
Nick Lewyckyd6dac0e2007-08-06 19:21:00 +00002030 SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true);
Reid Spencere4d87aa2006-12-23 06:05:41 +00002031 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
Chris Lattnerdb25de42005-08-15 23:33:51 +00002032 break;
Reid Spencere4d87aa2006-12-23 06:05:41 +00002033 }
2034 case ICmpInst::ICMP_SGT: {
Eli Friedman068acc32008-07-30 00:04:08 +00002035 SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS),
2036 SE.getNotSCEV(RHS), L, true);
Nick Lewyckyd6dac0e2007-08-06 19:21:00 +00002037 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
2038 break;
2039 }
2040 case ICmpInst::ICMP_ULT: {
2041 SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false);
2042 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
2043 break;
2044 }
2045 case ICmpInst::ICMP_UGT: {
Dale Johannesena0c8fc62008-04-20 16:58:57 +00002046 SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS),
Nick Lewycky08de6132008-05-06 04:03:18 +00002047 SE.getNotSCEV(RHS), L, false);
Reid Spencere4d87aa2006-12-23 06:05:41 +00002048 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
Chris Lattnerdb25de42005-08-15 23:33:51 +00002049 break;
Reid Spencere4d87aa2006-12-23 06:05:41 +00002050 }
Chris Lattner53e677a2004-04-02 20:23:17 +00002051 default:
Chris Lattnerd18d9dc2004-04-02 20:26:46 +00002052#if 0
Bill Wendlinge8156192006-12-07 01:30:32 +00002053 cerr << "ComputeIterationCount ";
Chris Lattner53e677a2004-04-02 20:23:17 +00002054 if (ExitCond->getOperand(0)->getType()->isUnsigned())
Bill Wendlinge8156192006-12-07 01:30:32 +00002055 cerr << "[unsigned] ";
2056 cerr << *LHS << " "
Reid Spencere4d87aa2006-12-23 06:05:41 +00002057 << Instruction::getOpcodeName(Instruction::ICmp)
2058 << " " << *RHS << "\n";
Chris Lattnerd18d9dc2004-04-02 20:26:46 +00002059#endif
Chris Lattnere34c0b42004-04-03 00:43:03 +00002060 break;
Chris Lattner53e677a2004-04-02 20:23:17 +00002061 }
Chris Lattner7980fb92004-04-17 18:36:24 +00002062 return ComputeIterationCountExhaustively(L, ExitCond,
Reid Spencere4d87aa2006-12-23 06:05:41 +00002063 ExitBr->getSuccessor(0) == ExitBlock);
Chris Lattner7980fb92004-04-17 18:36:24 +00002064}
2065
Chris Lattner673e02b2004-10-12 01:49:27 +00002066static ConstantInt *
Dan Gohman246b2562007-10-22 18:31:58 +00002067EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
2068 ScalarEvolution &SE) {
2069 SCEVHandle InVal = SE.getConstant(C);
2070 SCEVHandle Val = AddRec->evaluateAtIteration(InVal, SE);
Chris Lattner673e02b2004-10-12 01:49:27 +00002071 assert(isa<SCEVConstant>(Val) &&
2072 "Evaluation of SCEV at constant didn't fold correctly?");
2073 return cast<SCEVConstant>(Val)->getValue();
2074}
2075
2076/// GetAddressedElementFromGlobal - Given a global variable with an initializer
2077/// and a GEP expression (missing the pointer index) indexing into it, return
2078/// the addressed element of the initializer or null if the index expression is
2079/// invalid.
2080static Constant *
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002081GetAddressedElementFromGlobal(GlobalVariable *GV,
Chris Lattner673e02b2004-10-12 01:49:27 +00002082 const std::vector<ConstantInt*> &Indices) {
2083 Constant *Init = GV->getInitializer();
2084 for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
Reid Spencerb83eb642006-10-20 07:07:24 +00002085 uint64_t Idx = Indices[i]->getZExtValue();
Chris Lattner673e02b2004-10-12 01:49:27 +00002086 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) {
2087 assert(Idx < CS->getNumOperands() && "Bad struct index!");
2088 Init = cast<Constant>(CS->getOperand(Idx));
2089 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) {
2090 if (Idx >= CA->getNumOperands()) return 0; // Bogus program
2091 Init = cast<Constant>(CA->getOperand(Idx));
2092 } else if (isa<ConstantAggregateZero>(Init)) {
2093 if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
2094 assert(Idx < STy->getNumElements() && "Bad struct index!");
2095 Init = Constant::getNullValue(STy->getElementType(Idx));
2096 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) {
2097 if (Idx >= ATy->getNumElements()) return 0; // Bogus program
2098 Init = Constant::getNullValue(ATy->getElementType());
2099 } else {
2100 assert(0 && "Unknown constant aggregate type!");
2101 }
2102 return 0;
2103 } else {
2104 return 0; // Unknown initializer type
2105 }
2106 }
2107 return Init;
2108}
2109
2110/// ComputeLoadConstantCompareIterationCount - Given an exit condition of
Nick Lewycky08de6132008-05-06 04:03:18 +00002111/// 'icmp op load X, cst', try to see if we can compute the trip count.
Chris Lattner673e02b2004-10-12 01:49:27 +00002112SCEVHandle ScalarEvolutionsImpl::
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002113ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS,
Reid Spencere4d87aa2006-12-23 06:05:41 +00002114 const Loop *L,
2115 ICmpInst::Predicate predicate) {
Chris Lattner673e02b2004-10-12 01:49:27 +00002116 if (LI->isVolatile()) return UnknownValue;
2117
2118 // Check to see if the loaded pointer is a getelementptr of a global.
2119 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
2120 if (!GEP) return UnknownValue;
2121
2122 // Make sure that it is really a constant global we are gepping, with an
2123 // initializer, and make sure the first IDX is really 0.
2124 GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
2125 if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
2126 GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
2127 !cast<Constant>(GEP->getOperand(1))->isNullValue())
2128 return UnknownValue;
2129
2130 // Okay, we allow one non-constant index into the GEP instruction.
2131 Value *VarIdx = 0;
2132 std::vector<ConstantInt*> Indexes;
2133 unsigned VarIdxNum = 0;
2134 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
2135 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
2136 Indexes.push_back(CI);
2137 } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
2138 if (VarIdx) return UnknownValue; // Multiple non-constant idx's.
2139 VarIdx = GEP->getOperand(i);
2140 VarIdxNum = i-2;
2141 Indexes.push_back(0);
2142 }
2143
2144 // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
2145 // Check to see if X is a loop variant variable value now.
2146 SCEVHandle Idx = getSCEV(VarIdx);
2147 SCEVHandle Tmp = getSCEVAtScope(Idx, L);
2148 if (!isa<SCEVCouldNotCompute>(Tmp)) Idx = Tmp;
2149
2150 // We can only recognize very limited forms of loop index expressions, in
2151 // particular, only affine AddRec's like {C1,+,C2}.
2152 SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
2153 if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
2154 !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
2155 !isa<SCEVConstant>(IdxExpr->getOperand(1)))
2156 return UnknownValue;
2157
2158 unsigned MaxSteps = MaxBruteForceIterations;
2159 for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
Reid Spencerb83eb642006-10-20 07:07:24 +00002160 ConstantInt *ItCst =
Reid Spencerc5b206b2006-12-31 05:48:39 +00002161 ConstantInt::get(IdxExpr->getType(), IterationNum);
Dan Gohman246b2562007-10-22 18:31:58 +00002162 ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, SE);
Chris Lattner673e02b2004-10-12 01:49:27 +00002163
2164 // Form the GEP offset.
2165 Indexes[VarIdxNum] = Val;
2166
2167 Constant *Result = GetAddressedElementFromGlobal(GV, Indexes);
2168 if (Result == 0) break; // Cannot compute!
2169
2170 // Evaluate the condition for this iteration.
Reid Spencere4d87aa2006-12-23 06:05:41 +00002171 Result = ConstantExpr::getICmp(predicate, Result, RHS);
Zhou Sheng6b6b6ef2007-01-11 12:24:14 +00002172 if (!isa<ConstantInt>(Result)) break; // Couldn't decide for sure
Reid Spencere8019bb2007-03-01 07:25:48 +00002173 if (cast<ConstantInt>(Result)->getValue().isMinValue()) {
Chris Lattner673e02b2004-10-12 01:49:27 +00002174#if 0
Bill Wendlinge8156192006-12-07 01:30:32 +00002175 cerr << "\n***\n*** Computed loop count " << *ItCst
2176 << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
2177 << "***\n";
Chris Lattner673e02b2004-10-12 01:49:27 +00002178#endif
2179 ++NumArrayLenItCounts;
Dan Gohman246b2562007-10-22 18:31:58 +00002180 return SE.getConstant(ItCst); // Found terminating iteration!
Chris Lattner673e02b2004-10-12 01:49:27 +00002181 }
2182 }
2183 return UnknownValue;
2184}
2185
2186
Chris Lattner3221ad02004-04-17 22:58:41 +00002187/// CanConstantFold - Return true if we can constant fold an instruction of the
2188/// specified type, assuming that all operands were constants.
2189static bool CanConstantFold(const Instruction *I) {
Reid Spencer832254e2007-02-02 02:16:23 +00002190 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
Chris Lattner3221ad02004-04-17 22:58:41 +00002191 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
2192 return true;
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002193
Chris Lattner3221ad02004-04-17 22:58:41 +00002194 if (const CallInst *CI = dyn_cast<CallInst>(I))
2195 if (const Function *F = CI->getCalledFunction())
Dan Gohmanfa9b80e2008-01-31 01:05:10 +00002196 return canConstantFoldCallTo(F);
Chris Lattner3221ad02004-04-17 22:58:41 +00002197 return false;
Chris Lattner7980fb92004-04-17 18:36:24 +00002198}
2199
Chris Lattner3221ad02004-04-17 22:58:41 +00002200/// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
2201/// in the loop that V is derived from. We allow arbitrary operations along the
2202/// way, but the operands of an operation must either be constants or a value
2203/// derived from a constant PHI. If this expression does not fit with these
2204/// constraints, return null.
2205static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
2206 // If this is not an instruction, or if this is an instruction outside of the
2207 // loop, it can't be derived from a loop PHI.
2208 Instruction *I = dyn_cast<Instruction>(V);
2209 if (I == 0 || !L->contains(I->getParent())) return 0;
2210
Anton Korobeynikovae9f3a32008-02-20 11:08:44 +00002211 if (PHINode *PN = dyn_cast<PHINode>(I)) {
Chris Lattner3221ad02004-04-17 22:58:41 +00002212 if (L->getHeader() == I->getParent())
2213 return PN;
2214 else
2215 // We don't currently keep track of the control flow needed to evaluate
2216 // PHIs, so we cannot handle PHIs inside of loops.
2217 return 0;
Anton Korobeynikovae9f3a32008-02-20 11:08:44 +00002218 }
Chris Lattner3221ad02004-04-17 22:58:41 +00002219
2220 // If we won't be able to constant fold this expression even if the operands
2221 // are constants, return early.
2222 if (!CanConstantFold(I)) return 0;
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002223
Chris Lattner3221ad02004-04-17 22:58:41 +00002224 // Otherwise, we can evaluate this instruction if all of its operands are
2225 // constant or derived from a PHI node themselves.
2226 PHINode *PHI = 0;
2227 for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op)
2228 if (!(isa<Constant>(I->getOperand(Op)) ||
2229 isa<GlobalValue>(I->getOperand(Op)))) {
2230 PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L);
2231 if (P == 0) return 0; // Not evolving from PHI
2232 if (PHI == 0)
2233 PHI = P;
2234 else if (PHI != P)
2235 return 0; // Evolving from multiple different PHIs.
2236 }
2237
2238 // This is a expression evolving from a constant PHI!
2239 return PHI;
2240}
2241
2242/// EvaluateExpression - Given an expression that passes the
2243/// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node
2244/// in the loop has the value PHIVal. If we can't fold this expression for some
2245/// reason, return null.
2246static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
2247 if (isa<PHINode>(V)) return PHIVal;
Reid Spencere8404342004-07-18 00:18:30 +00002248 if (Constant *C = dyn_cast<Constant>(V)) return C;
Chris Lattner3221ad02004-04-17 22:58:41 +00002249 Instruction *I = cast<Instruction>(V);
2250
2251 std::vector<Constant*> Operands;
2252 Operands.resize(I->getNumOperands());
2253
2254 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
2255 Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal);
2256 if (Operands[i] == 0) return 0;
2257 }
2258
Chris Lattnerf286f6f2007-12-10 22:53:04 +00002259 if (const CmpInst *CI = dyn_cast<CmpInst>(I))
2260 return ConstantFoldCompareInstOperands(CI->getPredicate(),
2261 &Operands[0], Operands.size());
2262 else
2263 return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
2264 &Operands[0], Operands.size());
Chris Lattner3221ad02004-04-17 22:58:41 +00002265}
2266
2267/// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
2268/// in the header of its containing loop, we know the loop executes a
2269/// constant number of times, and the PHI node is just a recurrence
2270/// involving constants, fold it.
2271Constant *ScalarEvolutionsImpl::
Reid Spencere8019bb2007-03-01 07:25:48 +00002272getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its, const Loop *L){
Chris Lattner3221ad02004-04-17 22:58:41 +00002273 std::map<PHINode*, Constant*>::iterator I =
2274 ConstantEvolutionLoopExitValue.find(PN);
2275 if (I != ConstantEvolutionLoopExitValue.end())
2276 return I->second;
2277
Reid Spencere8019bb2007-03-01 07:25:48 +00002278 if (Its.ugt(APInt(Its.getBitWidth(),MaxBruteForceIterations)))
Chris Lattner3221ad02004-04-17 22:58:41 +00002279 return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it.
2280
2281 Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
2282
2283 // Since the loop is canonicalized, the PHI node must have two entries. One
2284 // entry must be a constant (coming in from outside of the loop), and the
2285 // second must be derived from the same PHI.
2286 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
2287 Constant *StartCST =
2288 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
2289 if (StartCST == 0)
2290 return RetVal = 0; // Must be a constant.
2291
2292 Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
2293 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
2294 if (PN2 != PN)
2295 return RetVal = 0; // Not derived from same PHI.
2296
2297 // Execute the loop symbolically to determine the exit value.
Reid Spencere8019bb2007-03-01 07:25:48 +00002298 if (Its.getActiveBits() >= 32)
2299 return RetVal = 0; // More than 2^32-1 iterations?? Not doing it!
Chris Lattner3221ad02004-04-17 22:58:41 +00002300
Reid Spencere8019bb2007-03-01 07:25:48 +00002301 unsigned NumIterations = Its.getZExtValue(); // must be in range
2302 unsigned IterationNum = 0;
Chris Lattner3221ad02004-04-17 22:58:41 +00002303 for (Constant *PHIVal = StartCST; ; ++IterationNum) {
2304 if (IterationNum == NumIterations)
2305 return RetVal = PHIVal; // Got exit value!
2306
2307 // Compute the value of the PHI node for the next iteration.
2308 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
2309 if (NextPHI == PHIVal)
2310 return RetVal = NextPHI; // Stopped evolving!
2311 if (NextPHI == 0)
2312 return 0; // Couldn't evaluate!
2313 PHIVal = NextPHI;
2314 }
2315}
2316
Chris Lattner7980fb92004-04-17 18:36:24 +00002317/// ComputeIterationCountExhaustively - If the trip is known to execute a
2318/// constant number of times (the condition evolves only from constants),
2319/// try to evaluate a few iterations of the loop until we get the exit
2320/// condition gets a value of ExitWhen (true or false). If we cannot
2321/// evaluate the trip count of the loop, return UnknownValue.
2322SCEVHandle ScalarEvolutionsImpl::
2323ComputeIterationCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
2324 PHINode *PN = getConstantEvolvingPHI(Cond, L);
2325 if (PN == 0) return UnknownValue;
2326
2327 // Since the loop is canonicalized, the PHI node must have two entries. One
2328 // entry must be a constant (coming in from outside of the loop), and the
2329 // second must be derived from the same PHI.
2330 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
2331 Constant *StartCST =
2332 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
2333 if (StartCST == 0) return UnknownValue; // Must be a constant.
2334
2335 Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
2336 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
2337 if (PN2 != PN) return UnknownValue; // Not derived from same PHI.
2338
2339 // Okay, we find a PHI node that defines the trip count of this loop. Execute
2340 // the loop symbolically to determine when the condition gets a value of
2341 // "ExitWhen".
2342 unsigned IterationNum = 0;
2343 unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis.
2344 for (Constant *PHIVal = StartCST;
2345 IterationNum != MaxIterations; ++IterationNum) {
Zhou Sheng6b6b6ef2007-01-11 12:24:14 +00002346 ConstantInt *CondVal =
2347 dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
Chris Lattner3221ad02004-04-17 22:58:41 +00002348
Zhou Sheng6b6b6ef2007-01-11 12:24:14 +00002349 // Couldn't symbolically evaluate.
Chris Lattneref3baf02007-01-12 18:28:58 +00002350 if (!CondVal) return UnknownValue;
Zhou Sheng6b6b6ef2007-01-11 12:24:14 +00002351
Reid Spencere8019bb2007-03-01 07:25:48 +00002352 if (CondVal->getValue() == uint64_t(ExitWhen)) {
Chris Lattner3221ad02004-04-17 22:58:41 +00002353 ConstantEvolutionLoopExitValue[PN] = PHIVal;
Chris Lattner7980fb92004-04-17 18:36:24 +00002354 ++NumBruteForceTripCountsComputed;
Dan Gohman246b2562007-10-22 18:31:58 +00002355 return SE.getConstant(ConstantInt::get(Type::Int32Ty, IterationNum));
Chris Lattner7980fb92004-04-17 18:36:24 +00002356 }
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002357
Chris Lattner3221ad02004-04-17 22:58:41 +00002358 // Compute the value of the PHI node for the next iteration.
2359 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
2360 if (NextPHI == 0 || NextPHI == PHIVal)
Chris Lattner7980fb92004-04-17 18:36:24 +00002361 return UnknownValue; // Couldn't evaluate or not making progress...
Chris Lattner3221ad02004-04-17 22:58:41 +00002362 PHIVal = NextPHI;
Chris Lattner7980fb92004-04-17 18:36:24 +00002363 }
2364
2365 // Too many iterations were needed to evaluate.
Chris Lattner53e677a2004-04-02 20:23:17 +00002366 return UnknownValue;
2367}
2368
2369/// getSCEVAtScope - Compute the value of the specified expression within the
2370/// indicated loop (which may be null to indicate in no loop). If the
2371/// expression cannot be evaluated, return UnknownValue.
2372SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) {
2373 // FIXME: this should be turned into a virtual method on SCEV!
2374
Chris Lattner3221ad02004-04-17 22:58:41 +00002375 if (isa<SCEVConstant>(V)) return V;
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002376
Nick Lewycky3e630762008-02-20 06:48:22 +00002377 // If this instruction is evolved from a constant-evolving PHI, compute the
Chris Lattner3221ad02004-04-17 22:58:41 +00002378 // exit value from the loop without using SCEVs.
2379 if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
2380 if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
2381 const Loop *LI = this->LI[I->getParent()];
2382 if (LI && LI->getParentLoop() == L) // Looking for loop exit value.
2383 if (PHINode *PN = dyn_cast<PHINode>(I))
2384 if (PN->getParent() == LI->getHeader()) {
2385 // Okay, there is no closed form solution for the PHI node. Check
2386 // to see if the loop that contains it has a known iteration count.
2387 // If so, we may be able to force computation of the exit value.
2388 SCEVHandle IterationCount = getIterationCount(LI);
2389 if (SCEVConstant *ICC = dyn_cast<SCEVConstant>(IterationCount)) {
2390 // Okay, we know how many times the containing loop executes. If
2391 // this is a constant evolving PHI node, get the final value at
2392 // the specified iteration number.
2393 Constant *RV = getConstantEvolutionLoopExitValue(PN,
Reid Spencere8019bb2007-03-01 07:25:48 +00002394 ICC->getValue()->getValue(),
Chris Lattner3221ad02004-04-17 22:58:41 +00002395 LI);
Dan Gohman246b2562007-10-22 18:31:58 +00002396 if (RV) return SE.getUnknown(RV);
Chris Lattner3221ad02004-04-17 22:58:41 +00002397 }
2398 }
2399
Reid Spencer09906f32006-12-04 21:33:23 +00002400 // Okay, this is an expression that we cannot symbolically evaluate
Chris Lattner3221ad02004-04-17 22:58:41 +00002401 // into a SCEV. Check to see if it's possible to symbolically evaluate
Reid Spencer09906f32006-12-04 21:33:23 +00002402 // the arguments into constants, and if so, try to constant propagate the
Chris Lattner3221ad02004-04-17 22:58:41 +00002403 // result. This is particularly useful for computing loop exit values.
2404 if (CanConstantFold(I)) {
2405 std::vector<Constant*> Operands;
2406 Operands.reserve(I->getNumOperands());
2407 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
2408 Value *Op = I->getOperand(i);
2409 if (Constant *C = dyn_cast<Constant>(Op)) {
2410 Operands.push_back(C);
Chris Lattner3221ad02004-04-17 22:58:41 +00002411 } else {
Chris Lattner42b5e082007-11-23 08:46:22 +00002412 // If any of the operands is non-constant and if they are
2413 // non-integer, don't even try to analyze them with scev techniques.
2414 if (!isa<IntegerType>(Op->getType()))
2415 return V;
2416
Chris Lattner3221ad02004-04-17 22:58:41 +00002417 SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L);
2418 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV))
Reid Spencerd977d862006-12-12 23:36:14 +00002419 Operands.push_back(ConstantExpr::getIntegerCast(SC->getValue(),
2420 Op->getType(),
2421 false));
Chris Lattner3221ad02004-04-17 22:58:41 +00002422 else if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) {
2423 if (Constant *C = dyn_cast<Constant>(SU->getValue()))
Reid Spencerd977d862006-12-12 23:36:14 +00002424 Operands.push_back(ConstantExpr::getIntegerCast(C,
2425 Op->getType(),
2426 false));
Chris Lattner3221ad02004-04-17 22:58:41 +00002427 else
2428 return V;
2429 } else {
2430 return V;
2431 }
2432 }
2433 }
Chris Lattnerf286f6f2007-12-10 22:53:04 +00002434
2435 Constant *C;
2436 if (const CmpInst *CI = dyn_cast<CmpInst>(I))
2437 C = ConstantFoldCompareInstOperands(CI->getPredicate(),
2438 &Operands[0], Operands.size());
2439 else
2440 C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
2441 &Operands[0], Operands.size());
Dan Gohman246b2562007-10-22 18:31:58 +00002442 return SE.getUnknown(C);
Chris Lattner3221ad02004-04-17 22:58:41 +00002443 }
2444 }
2445
2446 // This is some other type of SCEVUnknown, just return it.
2447 return V;
2448 }
2449
Chris Lattner53e677a2004-04-02 20:23:17 +00002450 if (SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
2451 // Avoid performing the look-up in the common case where the specified
2452 // expression has no loop-variant portions.
2453 for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
2454 SCEVHandle OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
2455 if (OpAtScope != Comm->getOperand(i)) {
2456 if (OpAtScope == UnknownValue) return UnknownValue;
2457 // Okay, at least one of these operands is loop variant but might be
2458 // foldable. Build a new instance of the folded commutative expression.
Chris Lattner3221ad02004-04-17 22:58:41 +00002459 std::vector<SCEVHandle> NewOps(Comm->op_begin(), Comm->op_begin()+i);
Chris Lattner53e677a2004-04-02 20:23:17 +00002460 NewOps.push_back(OpAtScope);
2461
2462 for (++i; i != e; ++i) {
2463 OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
2464 if (OpAtScope == UnknownValue) return UnknownValue;
2465 NewOps.push_back(OpAtScope);
2466 }
2467 if (isa<SCEVAddExpr>(Comm))
Dan Gohman246b2562007-10-22 18:31:58 +00002468 return SE.getAddExpr(NewOps);
Nick Lewyckyc54c5612007-11-25 22:41:31 +00002469 if (isa<SCEVMulExpr>(Comm))
2470 return SE.getMulExpr(NewOps);
2471 if (isa<SCEVSMaxExpr>(Comm))
2472 return SE.getSMaxExpr(NewOps);
Nick Lewycky3e630762008-02-20 06:48:22 +00002473 if (isa<SCEVUMaxExpr>(Comm))
2474 return SE.getUMaxExpr(NewOps);
Nick Lewyckyc54c5612007-11-25 22:41:31 +00002475 assert(0 && "Unknown commutative SCEV type!");
Chris Lattner53e677a2004-04-02 20:23:17 +00002476 }
2477 }
2478 // If we got here, all operands are loop invariant.
2479 return Comm;
2480 }
2481
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +00002482 if (SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
Chris Lattner60a05cc2006-04-01 04:48:52 +00002483 SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L);
Chris Lattner53e677a2004-04-02 20:23:17 +00002484 if (LHS == UnknownValue) return LHS;
Chris Lattner60a05cc2006-04-01 04:48:52 +00002485 SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L);
Chris Lattner53e677a2004-04-02 20:23:17 +00002486 if (RHS == UnknownValue) return RHS;
Chris Lattner60a05cc2006-04-01 04:48:52 +00002487 if (LHS == Div->getLHS() && RHS == Div->getRHS())
2488 return Div; // must be loop invariant
Wojciech Matyjewicze3320a12008-02-11 11:03:14 +00002489 return SE.getUDivExpr(LHS, RHS);
Chris Lattner53e677a2004-04-02 20:23:17 +00002490 }
2491
2492 // If this is a loop recurrence for a loop that does not contain L, then we
2493 // are dealing with the final value computed by the loop.
2494 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
2495 if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
2496 // To evaluate this recurrence, we need to know how many times the AddRec
2497 // loop iterates. Compute this now.
2498 SCEVHandle IterationCount = getIterationCount(AddRec->getLoop());
2499 if (IterationCount == UnknownValue) return UnknownValue;
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002500
Eli Friedmanb42a6262008-08-04 23:49:06 +00002501 // Then, evaluate the AddRec.
Dan Gohman246b2562007-10-22 18:31:58 +00002502 return AddRec->evaluateAtIteration(IterationCount, SE);
Chris Lattner53e677a2004-04-02 20:23:17 +00002503 }
2504 return UnknownValue;
2505 }
2506
2507 //assert(0 && "Unknown SCEV type!");
2508 return UnknownValue;
2509}
2510
Wojciech Matyjewiczde0f2382008-07-20 15:55:14 +00002511/// SolveLinEquationWithOverflow - Finds the minimum unsigned root of the
2512/// following equation:
2513///
2514/// A * X = B (mod N)
2515///
2516/// where N = 2^BW and BW is the common bit width of A and B. The signedness of
2517/// A and B isn't important.
2518///
2519/// If the equation does not have a solution, SCEVCouldNotCompute is returned.
2520static SCEVHandle SolveLinEquationWithOverflow(const APInt &A, const APInt &B,
2521 ScalarEvolution &SE) {
2522 uint32_t BW = A.getBitWidth();
2523 assert(BW == B.getBitWidth() && "Bit widths must be the same.");
2524 assert(A != 0 && "A must be non-zero.");
2525
2526 // 1. D = gcd(A, N)
2527 //
2528 // The gcd of A and N may have only one prime factor: 2. The number of
2529 // trailing zeros in A is its multiplicity
2530 uint32_t Mult2 = A.countTrailingZeros();
2531 // D = 2^Mult2
2532
2533 // 2. Check if B is divisible by D.
2534 //
2535 // B is divisible by D if and only if the multiplicity of prime factor 2 for B
2536 // is not less than multiplicity of this prime factor for D.
2537 if (B.countTrailingZeros() < Mult2)
2538 return new SCEVCouldNotCompute();
2539
2540 // 3. Compute I: the multiplicative inverse of (A / D) in arithmetic
2541 // modulo (N / D).
2542 //
2543 // (N / D) may need BW+1 bits in its representation. Hence, we'll use this
2544 // bit width during computations.
2545 APInt AD = A.lshr(Mult2).zext(BW + 1); // AD = A / D
2546 APInt Mod(BW + 1, 0);
2547 Mod.set(BW - Mult2); // Mod = N / D
2548 APInt I = AD.multiplicativeInverse(Mod);
2549
2550 // 4. Compute the minimum unsigned root of the equation:
2551 // I * (B / D) mod (N / D)
2552 APInt Result = (I * B.lshr(Mult2).zext(BW + 1)).urem(Mod);
2553
2554 // The result is guaranteed to be less than 2^BW so we may truncate it to BW
2555 // bits.
2556 return SE.getConstant(Result.trunc(BW));
2557}
Chris Lattner53e677a2004-04-02 20:23:17 +00002558
2559/// SolveQuadraticEquation - Find the roots of the quadratic equation for the
2560/// given quadratic chrec {L,+,M,+,N}. This returns either the two roots (which
2561/// might be the same) or two SCEVCouldNotCompute objects.
2562///
2563static std::pair<SCEVHandle,SCEVHandle>
Dan Gohman246b2562007-10-22 18:31:58 +00002564SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
Chris Lattner53e677a2004-04-02 20:23:17 +00002565 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
Reid Spencere8019bb2007-03-01 07:25:48 +00002566 SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
2567 SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
2568 SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002569
Chris Lattner53e677a2004-04-02 20:23:17 +00002570 // We currently can only solve this if the coefficients are constants.
Reid Spencere8019bb2007-03-01 07:25:48 +00002571 if (!LC || !MC || !NC) {
Chris Lattner53e677a2004-04-02 20:23:17 +00002572 SCEV *CNC = new SCEVCouldNotCompute();
2573 return std::make_pair(CNC, CNC);
2574 }
2575
Reid Spencere8019bb2007-03-01 07:25:48 +00002576 uint32_t BitWidth = LC->getValue()->getValue().getBitWidth();
Chris Lattnerfe560b82007-04-15 19:52:49 +00002577 const APInt &L = LC->getValue()->getValue();
2578 const APInt &M = MC->getValue()->getValue();
2579 const APInt &N = NC->getValue()->getValue();
Reid Spencere8019bb2007-03-01 07:25:48 +00002580 APInt Two(BitWidth, 2);
2581 APInt Four(BitWidth, 4);
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002582
Reid Spencere8019bb2007-03-01 07:25:48 +00002583 {
2584 using namespace APIntOps;
Zhou Sheng414de4d2007-04-07 17:48:27 +00002585 const APInt& C = L;
Reid Spencere8019bb2007-03-01 07:25:48 +00002586 // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C
2587 // The B coefficient is M-N/2
2588 APInt B(M);
2589 B -= sdiv(N,Two);
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002590
Reid Spencere8019bb2007-03-01 07:25:48 +00002591 // The A coefficient is N/2
Zhou Sheng414de4d2007-04-07 17:48:27 +00002592 APInt A(N.sdiv(Two));
Chris Lattner53e677a2004-04-02 20:23:17 +00002593
Reid Spencere8019bb2007-03-01 07:25:48 +00002594 // Compute the B^2-4ac term.
2595 APInt SqrtTerm(B);
2596 SqrtTerm *= B;
2597 SqrtTerm -= Four * (A * C);
Chris Lattner53e677a2004-04-02 20:23:17 +00002598
Reid Spencere8019bb2007-03-01 07:25:48 +00002599 // Compute sqrt(B^2-4ac). This is guaranteed to be the nearest
2600 // integer value or else APInt::sqrt() will assert.
2601 APInt SqrtVal(SqrtTerm.sqrt());
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002602
Reid Spencere8019bb2007-03-01 07:25:48 +00002603 // Compute the two solutions for the quadratic formula.
2604 // The divisions must be performed as signed divisions.
2605 APInt NegB(-B);
Reid Spencer3e35c8d2007-04-16 02:24:41 +00002606 APInt TwoA( A << 1 );
Nick Lewycky8f4d5eb2008-11-03 02:43:49 +00002607 if (TwoA.isMinValue()) {
2608 SCEV *CNC = new SCEVCouldNotCompute();
2609 return std::make_pair(CNC, CNC);
2610 }
2611
Reid Spencere8019bb2007-03-01 07:25:48 +00002612 ConstantInt *Solution1 = ConstantInt::get((NegB + SqrtVal).sdiv(TwoA));
2613 ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA));
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002614
Dan Gohman246b2562007-10-22 18:31:58 +00002615 return std::make_pair(SE.getConstant(Solution1),
2616 SE.getConstant(Solution2));
Reid Spencere8019bb2007-03-01 07:25:48 +00002617 } // end APIntOps namespace
Chris Lattner53e677a2004-04-02 20:23:17 +00002618}
2619
2620/// HowFarToZero - Return the number of times a backedge comparing the specified
2621/// value to zero will execute. If not computable, return UnknownValue
2622SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) {
2623 // If the value is a constant
2624 if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
2625 // If the value is already zero, the branch will execute zero times.
Reid Spencercae57542007-03-02 00:28:52 +00002626 if (C->getValue()->isZero()) return C;
Chris Lattner53e677a2004-04-02 20:23:17 +00002627 return UnknownValue; // Otherwise it will loop infinitely.
2628 }
2629
2630 SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
2631 if (!AddRec || AddRec->getLoop() != L)
2632 return UnknownValue;
2633
2634 if (AddRec->isAffine()) {
Wojciech Matyjewiczde0f2382008-07-20 15:55:14 +00002635 // If this is an affine expression, the execution count of this branch is
2636 // the minimum unsigned root of the following equation:
Chris Lattner53e677a2004-04-02 20:23:17 +00002637 //
Wojciech Matyjewiczde0f2382008-07-20 15:55:14 +00002638 // Start + Step*N = 0 (mod 2^BW)
Chris Lattner53e677a2004-04-02 20:23:17 +00002639 //
Wojciech Matyjewiczde0f2382008-07-20 15:55:14 +00002640 // equivalent to:
2641 //
2642 // Step*N = -Start (mod 2^BW)
2643 //
2644 // where BW is the common bit width of Start and Step.
2645
Chris Lattner53e677a2004-04-02 20:23:17 +00002646 // Get the initial value for the loop.
2647 SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
Chris Lattner4a2b23e2004-10-11 04:07:27 +00002648 if (isa<SCEVCouldNotCompute>(Start)) return UnknownValue;
Chris Lattner53e677a2004-04-02 20:23:17 +00002649
Wojciech Matyjewiczde0f2382008-07-20 15:55:14 +00002650 SCEVHandle Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
Chris Lattner53e677a2004-04-02 20:23:17 +00002651
Chris Lattner53e677a2004-04-02 20:23:17 +00002652 if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
Wojciech Matyjewiczde0f2382008-07-20 15:55:14 +00002653 // For now we handle only constant steps.
Chris Lattner53e677a2004-04-02 20:23:17 +00002654
Wojciech Matyjewiczde0f2382008-07-20 15:55:14 +00002655 // First, handle unitary steps.
2656 if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so:
2657 return SE.getNegativeSCEV(Start); // N = -Start (as unsigned)
2658 if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so:
2659 return Start; // N = Start (as unsigned)
2660
2661 // Then, try to solve the above equation provided that Start is constant.
2662 if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
2663 return SolveLinEquationWithOverflow(StepC->getValue()->getValue(),
2664 -StartC->getValue()->getValue(),SE);
Chris Lattner53e677a2004-04-02 20:23:17 +00002665 }
Chris Lattner42a75512007-01-15 02:27:26 +00002666 } else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) {
Chris Lattner53e677a2004-04-02 20:23:17 +00002667 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
2668 // the quadratic equation to solve it.
Dan Gohman246b2562007-10-22 18:31:58 +00002669 std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec, SE);
Chris Lattner53e677a2004-04-02 20:23:17 +00002670 SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
2671 SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
2672 if (R1) {
Chris Lattnerd18d9dc2004-04-02 20:26:46 +00002673#if 0
Bill Wendlinge8156192006-12-07 01:30:32 +00002674 cerr << "HFTZ: " << *V << " - sol#1: " << *R1
2675 << " sol#2: " << *R2 << "\n";
Chris Lattnerd18d9dc2004-04-02 20:26:46 +00002676#endif
Chris Lattner53e677a2004-04-02 20:23:17 +00002677 // Pick the smallest positive root value.
Zhou Sheng6b6b6ef2007-01-11 12:24:14 +00002678 if (ConstantInt *CB =
2679 dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
Reid Spencere4d87aa2006-12-23 06:05:41 +00002680 R1->getValue(), R2->getValue()))) {
Reid Spencer579dca12007-01-12 04:24:46 +00002681 if (CB->getZExtValue() == false)
Chris Lattner53e677a2004-04-02 20:23:17 +00002682 std::swap(R1, R2); // R1 is the minimum root now.
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002683
Chris Lattner53e677a2004-04-02 20:23:17 +00002684 // We can only use this value if the chrec ends up with an exact zero
2685 // value at this index. When solving for "X*X != 5", for example, we
2686 // should not accept a root of 2.
Dan Gohman246b2562007-10-22 18:31:58 +00002687 SCEVHandle Val = AddRec->evaluateAtIteration(R1, SE);
Dan Gohmancfeb6a42008-06-18 16:23:07 +00002688 if (Val->isZero())
2689 return R1; // We found a quadratic root!
Chris Lattner53e677a2004-04-02 20:23:17 +00002690 }
2691 }
2692 }
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002693
Chris Lattner53e677a2004-04-02 20:23:17 +00002694 return UnknownValue;
2695}
2696
2697/// HowFarToNonZero - Return the number of times a backedge checking the
2698/// specified value for nonzero will execute. If not computable, return
2699/// UnknownValue
2700SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) {
2701 // Loops that look like: while (X == 0) are very strange indeed. We don't
2702 // handle them yet except for the trivial case. This could be expanded in the
2703 // future as needed.
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002704
Chris Lattner53e677a2004-04-02 20:23:17 +00002705 // If the value is a constant, check to see if it is known to be non-zero
2706 // already. If so, the backedge will execute zero times.
2707 if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
Nick Lewycky39442af2008-02-21 09:14:53 +00002708 if (!C->getValue()->isNullValue())
2709 return SE.getIntegerSCEV(0, C->getType());
Chris Lattner53e677a2004-04-02 20:23:17 +00002710 return UnknownValue; // Otherwise it will loop infinitely.
2711 }
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002712
Chris Lattner53e677a2004-04-02 20:23:17 +00002713 // We could implement others, but I really doubt anyone writes loops like
2714 // this, and if they did, they would already be constant folded.
2715 return UnknownValue;
2716}
2717
Dan Gohmanfd6edef2008-09-15 22:18:04 +00002718/// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
2719/// (which may not be an immediate predecessor) which has exactly one
2720/// successor from which BB is reachable, or null if no such block is
2721/// found.
2722///
2723BasicBlock *
2724ScalarEvolutionsImpl::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) {
2725 // If the block has a unique predecessor, the predecessor must have
2726 // no other successors from which BB is reachable.
2727 if (BasicBlock *Pred = BB->getSinglePredecessor())
2728 return Pred;
2729
2730 // A loop's header is defined to be a block that dominates the loop.
2731 // If the loop has a preheader, it must be a block that has exactly
2732 // one successor that can reach BB. This is slightly more strict
2733 // than necessary, but works if critical edges are split.
2734 if (Loop *L = LI.getLoopFor(BB))
2735 return L->getLoopPreheader();
2736
2737 return 0;
2738}
2739
Nick Lewycky59cff122008-07-12 07:41:32 +00002740/// executesAtLeastOnce - Test whether entry to the loop is protected by
2741/// a conditional between LHS and RHS.
2742bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned,
2743 SCEV *LHS, SCEV *RHS) {
2744 BasicBlock *Preheader = L->getLoopPreheader();
2745 BasicBlock *PreheaderDest = L->getHeader();
Nick Lewycky59cff122008-07-12 07:41:32 +00002746
Dan Gohman38372182008-08-12 20:17:31 +00002747 // Starting at the preheader, climb up the predecessor chain, as long as
Dan Gohmanfd6edef2008-09-15 22:18:04 +00002748 // there are predecessors that can be found that have unique successors
2749 // leading to the original header.
2750 for (; Preheader;
2751 PreheaderDest = Preheader,
2752 Preheader = getPredecessorWithUniqueSuccessorForBB(Preheader)) {
Dan Gohman38372182008-08-12 20:17:31 +00002753
2754 BranchInst *LoopEntryPredicate =
Nick Lewycky59cff122008-07-12 07:41:32 +00002755 dyn_cast<BranchInst>(Preheader->getTerminator());
Dan Gohman38372182008-08-12 20:17:31 +00002756 if (!LoopEntryPredicate ||
2757 LoopEntryPredicate->isUnconditional())
2758 continue;
2759
2760 ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition());
2761 if (!ICI) continue;
2762
2763 // Now that we found a conditional branch that dominates the loop, check to
2764 // see if it is the comparison we are looking for.
2765 Value *PreCondLHS = ICI->getOperand(0);
2766 Value *PreCondRHS = ICI->getOperand(1);
2767 ICmpInst::Predicate Cond;
2768 if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest)
2769 Cond = ICI->getPredicate();
2770 else
2771 Cond = ICI->getInversePredicate();
2772
2773 switch (Cond) {
2774 case ICmpInst::ICMP_UGT:
2775 if (isSigned) continue;
2776 std::swap(PreCondLHS, PreCondRHS);
2777 Cond = ICmpInst::ICMP_ULT;
2778 break;
2779 case ICmpInst::ICMP_SGT:
2780 if (!isSigned) continue;
2781 std::swap(PreCondLHS, PreCondRHS);
2782 Cond = ICmpInst::ICMP_SLT;
2783 break;
2784 case ICmpInst::ICMP_ULT:
2785 if (isSigned) continue;
2786 break;
2787 case ICmpInst::ICMP_SLT:
2788 if (!isSigned) continue;
2789 break;
2790 default:
2791 continue;
2792 }
2793
2794 if (!PreCondLHS->getType()->isInteger()) continue;
2795
2796 SCEVHandle PreCondLHSSCEV = getSCEV(PreCondLHS);
2797 SCEVHandle PreCondRHSSCEV = getSCEV(PreCondRHS);
2798 if ((LHS == PreCondLHSSCEV && RHS == PreCondRHSSCEV) ||
2799 (LHS == SE.getNotSCEV(PreCondRHSSCEV) &&
2800 RHS == SE.getNotSCEV(PreCondLHSSCEV)))
2801 return true;
Nick Lewycky59cff122008-07-12 07:41:32 +00002802 }
2803
Dan Gohman38372182008-08-12 20:17:31 +00002804 return false;
Nick Lewycky59cff122008-07-12 07:41:32 +00002805}
2806
Chris Lattnerdb25de42005-08-15 23:33:51 +00002807/// HowManyLessThans - Return the number of times a backedge containing the
2808/// specified less-than comparison will execute. If not computable, return
2809/// UnknownValue.
2810SCEVHandle ScalarEvolutionsImpl::
Nick Lewyckyd6dac0e2007-08-06 19:21:00 +00002811HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) {
Chris Lattnerdb25de42005-08-15 23:33:51 +00002812 // Only handle: "ADDREC < LoopInvariant".
2813 if (!RHS->isLoopInvariant(L)) return UnknownValue;
2814
2815 SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
2816 if (!AddRec || AddRec->getLoop() != L)
2817 return UnknownValue;
2818
2819 if (AddRec->isAffine()) {
2820 // FORNOW: We only support unit strides.
Dan Gohman246b2562007-10-22 18:31:58 +00002821 SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType());
Chris Lattnerdb25de42005-08-15 23:33:51 +00002822 if (AddRec->getOperand(1) != One)
2823 return UnknownValue;
2824
Wojciech Matyjewicz3a4cbe22008-02-13 11:51:34 +00002825 // We know the LHS is of the form {n,+,1} and the RHS is some loop-invariant
2826 // m. So, we count the number of iterations in which {n,+,1} < m is true.
2827 // Note that we cannot simply return max(m-n,0) because it's not safe to
Wojciech Matyjewicza65ee032008-02-13 12:21:32 +00002828 // treat m-n as signed nor unsigned due to overflow possibility.
Chris Lattnerdb25de42005-08-15 23:33:51 +00002829
Wojciech Matyjewicz3a4cbe22008-02-13 11:51:34 +00002830 // First, we get the value of the LHS in the first iteration: n
2831 SCEVHandle Start = AddRec->getOperand(0);
2832
Nick Lewycky59cff122008-07-12 07:41:32 +00002833 if (executesAtLeastOnce(L, isSigned,
Nick Lewycky86dae652008-07-15 03:40:27 +00002834 SE.getMinusSCEV(AddRec->getOperand(0), One), RHS)) {
2835 // Since we know that the condition is true in order to enter the loop,
2836 // we know that it will run exactly m-n times.
Nick Lewycky59cff122008-07-12 07:41:32 +00002837 return SE.getMinusSCEV(RHS, Start);
Nick Lewycky86dae652008-07-15 03:40:27 +00002838 } else {
2839 // Then, we get the value of the LHS in the first iteration in which the
2840 // above condition doesn't hold. This equals to max(m,n).
Nick Lewycky59cff122008-07-12 07:41:32 +00002841 SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start)
2842 : SE.getUMaxExpr(RHS, Start);
Wojciech Matyjewicz3a4cbe22008-02-13 11:51:34 +00002843
Nick Lewycky59cff122008-07-12 07:41:32 +00002844 // Finally, we subtract these two values to get the number of times the
2845 // backedge is executed: max(m,n)-n.
2846 return SE.getMinusSCEV(End, Start);
2847 }
Chris Lattnerdb25de42005-08-15 23:33:51 +00002848 }
2849
2850 return UnknownValue;
2851}
2852
Chris Lattner53e677a2004-04-02 20:23:17 +00002853/// getNumIterationsInRange - Return the number of iterations of this loop that
2854/// produce values in the specified constant range. Another way of looking at
2855/// this is that it returns the first iteration number where the value is not in
2856/// the condition, thus computing the exit count. If the iteration count can't
2857/// be computed, an instance of SCEVCouldNotCompute is returned.
Dan Gohman246b2562007-10-22 18:31:58 +00002858SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
2859 ScalarEvolution &SE) const {
Chris Lattner53e677a2004-04-02 20:23:17 +00002860 if (Range.isFullSet()) // Infinite loop.
2861 return new SCEVCouldNotCompute();
2862
2863 // If the start is a non-zero constant, shift the range to simplify things.
2864 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
Reid Spencercae57542007-03-02 00:28:52 +00002865 if (!SC->getValue()->isZero()) {
Chris Lattner53e677a2004-04-02 20:23:17 +00002866 std::vector<SCEVHandle> Operands(op_begin(), op_end());
Dan Gohman246b2562007-10-22 18:31:58 +00002867 Operands[0] = SE.getIntegerSCEV(0, SC->getType());
2868 SCEVHandle Shifted = SE.getAddRecExpr(Operands, getLoop());
Chris Lattner53e677a2004-04-02 20:23:17 +00002869 if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
2870 return ShiftedAddRec->getNumIterationsInRange(
Dan Gohman246b2562007-10-22 18:31:58 +00002871 Range.subtract(SC->getValue()->getValue()), SE);
Chris Lattner53e677a2004-04-02 20:23:17 +00002872 // This is strange and shouldn't happen.
2873 return new SCEVCouldNotCompute();
2874 }
2875
2876 // The only time we can solve this is when we have all constant indices.
2877 // Otherwise, we cannot determine the overflow conditions.
2878 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
2879 if (!isa<SCEVConstant>(getOperand(i)))
2880 return new SCEVCouldNotCompute();
2881
2882
2883 // Okay at this point we know that all elements of the chrec are constants and
2884 // that the start element is zero.
2885
2886 // First check to see if the range contains zero. If not, the first
2887 // iteration exits.
Reid Spencera6e8a952007-03-01 07:54:15 +00002888 if (!Range.contains(APInt(getBitWidth(),0)))
Dan Gohman246b2562007-10-22 18:31:58 +00002889 return SE.getConstant(ConstantInt::get(getType(),0));
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002890
Chris Lattner53e677a2004-04-02 20:23:17 +00002891 if (isAffine()) {
2892 // If this is an affine expression then we have this situation:
2893 // Solve {0,+,A} in Range === Ax in Range
2894
Nick Lewyckyeefdebe2007-07-16 02:08:00 +00002895 // We know that zero is in the range. If A is positive then we know that
2896 // the upper value of the range must be the first possible exit value.
2897 // If A is negative then the lower of the range is the last possible loop
2898 // value. Also note that we already checked for a full range.
Reid Spencer581b0d42007-02-28 19:57:34 +00002899 APInt One(getBitWidth(),1);
Nick Lewyckyeefdebe2007-07-16 02:08:00 +00002900 APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue();
2901 APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower();
Chris Lattner53e677a2004-04-02 20:23:17 +00002902
Nick Lewyckyeefdebe2007-07-16 02:08:00 +00002903 // The exit value should be (End+A)/A.
Nick Lewycky9a2f9312007-09-27 14:12:54 +00002904 APInt ExitVal = (End + A).udiv(A);
Reid Spencerc7cd7a02007-03-01 19:32:33 +00002905 ConstantInt *ExitValue = ConstantInt::get(ExitVal);
Chris Lattner53e677a2004-04-02 20:23:17 +00002906
2907 // Evaluate at the exit value. If we really did fall out of the valid
2908 // range, then we computed our trip count, otherwise wrap around or other
2909 // things must have happened.
Dan Gohman246b2562007-10-22 18:31:58 +00002910 ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE);
Reid Spencera6e8a952007-03-01 07:54:15 +00002911 if (Range.contains(Val->getValue()))
Chris Lattner53e677a2004-04-02 20:23:17 +00002912 return new SCEVCouldNotCompute(); // Something strange happened
2913
2914 // Ensure that the previous value is in the range. This is a sanity check.
Reid Spencer581b0d42007-02-28 19:57:34 +00002915 assert(Range.contains(
2916 EvaluateConstantChrecAtConstant(this,
Dan Gohman246b2562007-10-22 18:31:58 +00002917 ConstantInt::get(ExitVal - One), SE)->getValue()) &&
Chris Lattner53e677a2004-04-02 20:23:17 +00002918 "Linear scev computation is off in a bad way!");
Dan Gohman246b2562007-10-22 18:31:58 +00002919 return SE.getConstant(ExitValue);
Chris Lattner53e677a2004-04-02 20:23:17 +00002920 } else if (isQuadratic()) {
2921 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the
2922 // quadratic equation to solve it. To do this, we must frame our problem in
2923 // terms of figuring out when zero is crossed, instead of when
2924 // Range.getUpper() is crossed.
2925 std::vector<SCEVHandle> NewOps(op_begin(), op_end());
Dan Gohman246b2562007-10-22 18:31:58 +00002926 NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
2927 SCEVHandle NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
Chris Lattner53e677a2004-04-02 20:23:17 +00002928
2929 // Next, solve the constructed addrec
2930 std::pair<SCEVHandle,SCEVHandle> Roots =
Dan Gohman246b2562007-10-22 18:31:58 +00002931 SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
Chris Lattner53e677a2004-04-02 20:23:17 +00002932 SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
2933 SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
2934 if (R1) {
2935 // Pick the smallest positive root value.
Zhou Sheng6b6b6ef2007-01-11 12:24:14 +00002936 if (ConstantInt *CB =
2937 dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
Reid Spencere4d87aa2006-12-23 06:05:41 +00002938 R1->getValue(), R2->getValue()))) {
Reid Spencer579dca12007-01-12 04:24:46 +00002939 if (CB->getZExtValue() == false)
Chris Lattner53e677a2004-04-02 20:23:17 +00002940 std::swap(R1, R2); // R1 is the minimum root now.
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002941
Chris Lattner53e677a2004-04-02 20:23:17 +00002942 // Make sure the root is not off by one. The returned iteration should
2943 // not be in the range, but the previous one should be. When solving
2944 // for "X*X < 5", for example, we should not return a root of 2.
2945 ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this,
Dan Gohman246b2562007-10-22 18:31:58 +00002946 R1->getValue(),
2947 SE);
Reid Spencera6e8a952007-03-01 07:54:15 +00002948 if (Range.contains(R1Val->getValue())) {
Chris Lattner53e677a2004-04-02 20:23:17 +00002949 // The next iteration must be out of the range...
Dan Gohman9a6ae962007-07-09 15:25:17 +00002950 ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()+1);
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002951
Dan Gohman246b2562007-10-22 18:31:58 +00002952 R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
Reid Spencera6e8a952007-03-01 07:54:15 +00002953 if (!Range.contains(R1Val->getValue()))
Dan Gohman246b2562007-10-22 18:31:58 +00002954 return SE.getConstant(NextVal);
Chris Lattner53e677a2004-04-02 20:23:17 +00002955 return new SCEVCouldNotCompute(); // Something strange happened
2956 }
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002957
Chris Lattner53e677a2004-04-02 20:23:17 +00002958 // If R1 was not in the range, then it is a good return value. Make
2959 // sure that R1-1 WAS in the range though, just in case.
Dan Gohman9a6ae962007-07-09 15:25:17 +00002960 ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()-1);
Dan Gohman246b2562007-10-22 18:31:58 +00002961 R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
Reid Spencera6e8a952007-03-01 07:54:15 +00002962 if (Range.contains(R1Val->getValue()))
Chris Lattner53e677a2004-04-02 20:23:17 +00002963 return R1;
2964 return new SCEVCouldNotCompute(); // Something strange happened
2965 }
2966 }
2967 }
2968
2969 // Fallback, if this is a general polynomial, figure out the progression
2970 // through brute force: evaluate until we find an iteration that fails the
2971 // test. This is likely to be slow, but getting an accurate trip count is
2972 // incredibly important, we will be able to simplify the exit test a lot, and
2973 // we are almost guaranteed to get a trip count in this case.
2974 ConstantInt *TestVal = ConstantInt::get(getType(), 0);
Chris Lattner53e677a2004-04-02 20:23:17 +00002975 ConstantInt *EndVal = TestVal; // Stop when we wrap around.
2976 do {
2977 ++NumBruteForceEvaluations;
Dan Gohman246b2562007-10-22 18:31:58 +00002978 SCEVHandle Val = evaluateAtIteration(SE.getConstant(TestVal), SE);
Chris Lattner53e677a2004-04-02 20:23:17 +00002979 if (!isa<SCEVConstant>(Val)) // This shouldn't happen.
2980 return new SCEVCouldNotCompute();
2981
2982 // Check to see if we found the value!
Reid Spencera6e8a952007-03-01 07:54:15 +00002983 if (!Range.contains(cast<SCEVConstant>(Val)->getValue()->getValue()))
Dan Gohman246b2562007-10-22 18:31:58 +00002984 return SE.getConstant(TestVal);
Chris Lattner53e677a2004-04-02 20:23:17 +00002985
2986 // Increment to test the next index.
Zhou Shengfdc1e162007-04-07 17:40:57 +00002987 TestVal = ConstantInt::get(TestVal->getValue()+1);
Chris Lattner53e677a2004-04-02 20:23:17 +00002988 } while (TestVal != EndVal);
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002989
Chris Lattner53e677a2004-04-02 20:23:17 +00002990 return new SCEVCouldNotCompute();
2991}
2992
2993
2994
2995//===----------------------------------------------------------------------===//
2996// ScalarEvolution Class Implementation
2997//===----------------------------------------------------------------------===//
2998
2999bool ScalarEvolution::runOnFunction(Function &F) {
Dan Gohman246b2562007-10-22 18:31:58 +00003000 Impl = new ScalarEvolutionsImpl(*this, F, getAnalysis<LoopInfo>());
Chris Lattner53e677a2004-04-02 20:23:17 +00003001 return false;
3002}
3003
3004void ScalarEvolution::releaseMemory() {
3005 delete (ScalarEvolutionsImpl*)Impl;
3006 Impl = 0;
3007}
3008
3009void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
3010 AU.setPreservesAll();
Chris Lattner53e677a2004-04-02 20:23:17 +00003011 AU.addRequiredTransitive<LoopInfo>();
3012}
3013
3014SCEVHandle ScalarEvolution::getSCEV(Value *V) const {
3015 return ((ScalarEvolutionsImpl*)Impl)->getSCEV(V);
3016}
3017
Chris Lattnera0740fb2005-08-09 23:36:33 +00003018/// hasSCEV - Return true if the SCEV for this value has already been
3019/// computed.
3020bool ScalarEvolution::hasSCEV(Value *V) const {
Chris Lattner05bd3742005-08-10 00:59:40 +00003021 return ((ScalarEvolutionsImpl*)Impl)->hasSCEV(V);
Chris Lattnera0740fb2005-08-09 23:36:33 +00003022}
3023
3024
3025/// setSCEV - Insert the specified SCEV into the map of current SCEVs for
3026/// the specified value.
3027void ScalarEvolution::setSCEV(Value *V, const SCEVHandle &H) {
3028 ((ScalarEvolutionsImpl*)Impl)->setSCEV(V, H);
3029}
3030
3031
Chris Lattner53e677a2004-04-02 20:23:17 +00003032SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const {
3033 return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L);
3034}
3035
3036bool ScalarEvolution::hasLoopInvariantIterationCount(const Loop *L) const {
3037 return !isa<SCEVCouldNotCompute>(getIterationCount(L));
3038}
3039
3040SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) const {
3041 return ((ScalarEvolutionsImpl*)Impl)->getSCEVAtScope(getSCEV(V), L);
3042}
3043
Dan Gohman5cec4db2007-06-19 14:28:31 +00003044void ScalarEvolution::deleteValueFromRecords(Value *V) const {
3045 return ((ScalarEvolutionsImpl*)Impl)->deleteValueFromRecords(V);
Chris Lattner53e677a2004-04-02 20:23:17 +00003046}
3047
Misha Brukman2b37d7c2005-04-21 21:13:18 +00003048static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE,
Chris Lattner53e677a2004-04-02 20:23:17 +00003049 const Loop *L) {
3050 // Print all inner loops first
3051 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
3052 PrintLoopInfo(OS, SE, *I);
Misha Brukman2b37d7c2005-04-21 21:13:18 +00003053
Nick Lewyckyaeb5e5c2008-01-02 02:49:20 +00003054 OS << "Loop " << L->getHeader()->getName() << ": ";
Chris Lattnerf1ab4b42004-04-18 22:14:10 +00003055
Devang Patelb7211a22007-08-21 00:31:24 +00003056 SmallVector<BasicBlock*, 8> ExitBlocks;
Chris Lattnerf1ab4b42004-04-18 22:14:10 +00003057 L->getExitBlocks(ExitBlocks);
3058 if (ExitBlocks.size() != 1)
Nick Lewyckyaeb5e5c2008-01-02 02:49:20 +00003059 OS << "<multiple exits> ";
Chris Lattner53e677a2004-04-02 20:23:17 +00003060
3061 if (SE->hasLoopInvariantIterationCount(L)) {
Nick Lewyckyaeb5e5c2008-01-02 02:49:20 +00003062 OS << *SE->getIterationCount(L) << " iterations! ";
Chris Lattner53e677a2004-04-02 20:23:17 +00003063 } else {
Nick Lewyckyaeb5e5c2008-01-02 02:49:20 +00003064 OS << "Unpredictable iteration count. ";
Chris Lattner53e677a2004-04-02 20:23:17 +00003065 }
3066
Nick Lewyckyaeb5e5c2008-01-02 02:49:20 +00003067 OS << "\n";
Chris Lattner53e677a2004-04-02 20:23:17 +00003068}
3069
Reid Spencerce9653c2004-12-07 04:03:45 +00003070void ScalarEvolution::print(std::ostream &OS, const Module* ) const {
Chris Lattner53e677a2004-04-02 20:23:17 +00003071 Function &F = ((ScalarEvolutionsImpl*)Impl)->F;
3072 LoopInfo &LI = ((ScalarEvolutionsImpl*)Impl)->LI;
3073
3074 OS << "Classifying expressions for: " << F.getName() << "\n";
3075 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
Chris Lattner42a75512007-01-15 02:27:26 +00003076 if (I->getType()->isInteger()) {
Chris Lattner6ffe5512004-04-27 15:13:33 +00003077 OS << *I;
Dan Gohman8dae1382008-09-14 17:21:12 +00003078 OS << " --> ";
Chris Lattner6ffe5512004-04-27 15:13:33 +00003079 SCEVHandle SV = getSCEV(&*I);
Chris Lattner53e677a2004-04-02 20:23:17 +00003080 SV->print(OS);
3081 OS << "\t\t";
Misha Brukman2b37d7c2005-04-21 21:13:18 +00003082
Chris Lattner6ffe5512004-04-27 15:13:33 +00003083 if (const Loop *L = LI.getLoopFor((*I).getParent())) {
Chris Lattner53e677a2004-04-02 20:23:17 +00003084 OS << "Exits: ";
Chris Lattner6ffe5512004-04-27 15:13:33 +00003085 SCEVHandle ExitValue = getSCEVAtScope(&*I, L->getParentLoop());
Chris Lattner53e677a2004-04-02 20:23:17 +00003086 if (isa<SCEVCouldNotCompute>(ExitValue)) {
3087 OS << "<<Unknown>>";
3088 } else {
3089 OS << *ExitValue;
3090 }
3091 }
3092
3093
3094 OS << "\n";
3095 }
3096
3097 OS << "Determining loop execution counts for: " << F.getName() << "\n";
3098 for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
3099 PrintLoopInfo(OS, this, *I);
3100}