ScalarEvolution.cpp revision 414de4df41bba7f9e2b06723ae2ddae51dac3e0f
1//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 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. 31// 32// 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// 36// 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 62#define DEBUG_TYPE "scalar-evolution" 63#include "llvm/Analysis/ScalarEvolutionExpressions.h" 64#include "llvm/Constants.h" 65#include "llvm/DerivedTypes.h" 66#include "llvm/GlobalVariable.h" 67#include "llvm/Instructions.h" 68#include "llvm/Analysis/ConstantFolding.h" 69#include "llvm/Analysis/LoopInfo.h" 70#include "llvm/Assembly/Writer.h" 71#include "llvm/Transforms/Scalar.h" 72#include "llvm/Support/CFG.h" 73#include "llvm/Support/CommandLine.h" 74#include "llvm/Support/Compiler.h" 75#include "llvm/Support/ConstantRange.h" 76#include "llvm/Support/InstIterator.h" 77#include "llvm/Support/ManagedStatic.h" 78#include "llvm/Support/MathExtras.h" 79#include "llvm/Support/Streams.h" 80#include "llvm/ADT/Statistic.h" 81#include <ostream> 82#include <algorithm> 83#include <cmath> 84using namespace llvm; 85 86STATISTIC(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 98cl::opt<unsigned> 99MaxBruteForceIterations("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 104namespace { 105 RegisterPass<ScalarEvolution> 106 R("scalar-evolution", "Scalar Evolution Analysis"); 107} 108 109//===----------------------------------------------------------------------===// 110// SCEV class definitions 111//===----------------------------------------------------------------------===// 112 113//===----------------------------------------------------------------------===// 114// Implementation of the SCEV class. 115// 116SCEV::~SCEV() {} 117void SCEV::dump() const { 118 print(cerr); 119} 120 121/// getValueRange - Return the tightest constant bounds that this value is 122/// known to have. This method is only valid on integer SCEV objects. 123ConstantRange SCEV::getValueRange() const { 124 const Type *Ty = getType(); 125 assert(Ty->isInteger() && "Can't get range for a non-integer SCEV!"); 126 // Default to a full range if no better information is available. 127 return ConstantRange(getBitWidth()); 128} 129 130uint32_t SCEV::getBitWidth() const { 131 if (const IntegerType* ITy = dyn_cast<IntegerType>(getType())) 132 return ITy->getBitWidth(); 133 return 0; 134} 135 136 137SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {} 138 139bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const { 140 assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); 141 return false; 142} 143 144const Type *SCEVCouldNotCompute::getType() const { 145 assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); 146 return 0; 147} 148 149bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const { 150 assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); 151 return false; 152} 153 154SCEVHandle SCEVCouldNotCompute:: 155replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 156 const SCEVHandle &Conc) const { 157 return this; 158} 159 160void SCEVCouldNotCompute::print(std::ostream &OS) const { 161 OS << "***COULDNOTCOMPUTE***"; 162} 163 164bool SCEVCouldNotCompute::classof(const SCEV *S) { 165 return S->getSCEVType() == scCouldNotCompute; 166} 167 168 169// SCEVConstants - Only allow the creation of one SCEVConstant for any 170// particular value. Don't use a SCEVHandle here, or else the object will 171// never be deleted! 172static ManagedStatic<std::map<ConstantInt*, SCEVConstant*> > SCEVConstants; 173 174 175SCEVConstant::~SCEVConstant() { 176 SCEVConstants->erase(V); 177} 178 179SCEVHandle SCEVConstant::get(ConstantInt *V) { 180 SCEVConstant *&R = (*SCEVConstants)[V]; 181 if (R == 0) R = new SCEVConstant(V); 182 return R; 183} 184 185ConstantRange SCEVConstant::getValueRange() const { 186 return ConstantRange(V->getValue()); 187} 188 189const Type *SCEVConstant::getType() const { return V->getType(); } 190 191void SCEVConstant::print(std::ostream &OS) const { 192 WriteAsOperand(OS, V, false); 193} 194 195// SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any 196// particular input. Don't use a SCEVHandle here, or else the object will 197// never be deleted! 198static ManagedStatic<std::map<std::pair<SCEV*, const Type*>, 199 SCEVTruncateExpr*> > SCEVTruncates; 200 201SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty) 202 : SCEV(scTruncate), Op(op), Ty(ty) { 203 assert(Op->getType()->isInteger() && Ty->isInteger() && 204 "Cannot truncate non-integer value!"); 205 assert(Op->getType()->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits() 206 && "This is not a truncating conversion!"); 207} 208 209SCEVTruncateExpr::~SCEVTruncateExpr() { 210 SCEVTruncates->erase(std::make_pair(Op, Ty)); 211} 212 213ConstantRange SCEVTruncateExpr::getValueRange() const { 214 return getOperand()->getValueRange().truncate(getBitWidth()); 215} 216 217void SCEVTruncateExpr::print(std::ostream &OS) const { 218 OS << "(truncate " << *Op << " to " << *Ty << ")"; 219} 220 221// SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any 222// particular input. Don't use a SCEVHandle here, or else the object will never 223// be deleted! 224static ManagedStatic<std::map<std::pair<SCEV*, const Type*>, 225 SCEVZeroExtendExpr*> > SCEVZeroExtends; 226 227SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty) 228 : SCEV(scZeroExtend), Op(op), Ty(ty) { 229 assert(Op->getType()->isInteger() && Ty->isInteger() && 230 "Cannot zero extend non-integer value!"); 231 assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits() 232 && "This is not an extending conversion!"); 233} 234 235SCEVZeroExtendExpr::~SCEVZeroExtendExpr() { 236 SCEVZeroExtends->erase(std::make_pair(Op, Ty)); 237} 238 239ConstantRange SCEVZeroExtendExpr::getValueRange() const { 240 return getOperand()->getValueRange().zeroExtend(getBitWidth()); 241} 242 243void SCEVZeroExtendExpr::print(std::ostream &OS) const { 244 OS << "(zeroextend " << *Op << " to " << *Ty << ")"; 245} 246 247// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any 248// particular input. Don't use a SCEVHandle here, or else the object will never 249// be deleted! 250static ManagedStatic<std::map<std::pair<unsigned, std::vector<SCEV*> >, 251 SCEVCommutativeExpr*> > SCEVCommExprs; 252 253SCEVCommutativeExpr::~SCEVCommutativeExpr() { 254 SCEVCommExprs->erase(std::make_pair(getSCEVType(), 255 std::vector<SCEV*>(Operands.begin(), 256 Operands.end()))); 257} 258 259void SCEVCommutativeExpr::print(std::ostream &OS) const { 260 assert(Operands.size() > 1 && "This plus expr shouldn't exist!"); 261 const char *OpStr = getOperationStr(); 262 OS << "(" << *Operands[0]; 263 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 264 OS << OpStr << *Operands[i]; 265 OS << ")"; 266} 267 268SCEVHandle SCEVCommutativeExpr:: 269replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 270 const SCEVHandle &Conc) const { 271 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 272 SCEVHandle H = getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc); 273 if (H != getOperand(i)) { 274 std::vector<SCEVHandle> NewOps; 275 NewOps.reserve(getNumOperands()); 276 for (unsigned j = 0; j != i; ++j) 277 NewOps.push_back(getOperand(j)); 278 NewOps.push_back(H); 279 for (++i; i != e; ++i) 280 NewOps.push_back(getOperand(i)-> 281 replaceSymbolicValuesWithConcrete(Sym, Conc)); 282 283 if (isa<SCEVAddExpr>(this)) 284 return SCEVAddExpr::get(NewOps); 285 else if (isa<SCEVMulExpr>(this)) 286 return SCEVMulExpr::get(NewOps); 287 else 288 assert(0 && "Unknown commutative expr!"); 289 } 290 } 291 return this; 292} 293 294 295// SCEVSDivs - Only allow the creation of one SCEVSDivExpr for any particular 296// input. Don't use a SCEVHandle here, or else the object will never be 297// deleted! 298static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>, 299 SCEVSDivExpr*> > SCEVSDivs; 300 301SCEVSDivExpr::~SCEVSDivExpr() { 302 SCEVSDivs->erase(std::make_pair(LHS, RHS)); 303} 304 305void SCEVSDivExpr::print(std::ostream &OS) const { 306 OS << "(" << *LHS << " /s " << *RHS << ")"; 307} 308 309const Type *SCEVSDivExpr::getType() const { 310 return LHS->getType(); 311} 312 313// SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any 314// particular input. Don't use a SCEVHandle here, or else the object will never 315// be deleted! 316static ManagedStatic<std::map<std::pair<const Loop *, std::vector<SCEV*> >, 317 SCEVAddRecExpr*> > SCEVAddRecExprs; 318 319SCEVAddRecExpr::~SCEVAddRecExpr() { 320 SCEVAddRecExprs->erase(std::make_pair(L, 321 std::vector<SCEV*>(Operands.begin(), 322 Operands.end()))); 323} 324 325SCEVHandle SCEVAddRecExpr:: 326replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 327 const SCEVHandle &Conc) const { 328 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 329 SCEVHandle H = getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc); 330 if (H != getOperand(i)) { 331 std::vector<SCEVHandle> NewOps; 332 NewOps.reserve(getNumOperands()); 333 for (unsigned j = 0; j != i; ++j) 334 NewOps.push_back(getOperand(j)); 335 NewOps.push_back(H); 336 for (++i; i != e; ++i) 337 NewOps.push_back(getOperand(i)-> 338 replaceSymbolicValuesWithConcrete(Sym, Conc)); 339 340 return get(NewOps, L); 341 } 342 } 343 return this; 344} 345 346 347bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const { 348 // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't 349 // contain L and if the start is invariant. 350 return !QueryLoop->contains(L->getHeader()) && 351 getOperand(0)->isLoopInvariant(QueryLoop); 352} 353 354 355void SCEVAddRecExpr::print(std::ostream &OS) const { 356 OS << "{" << *Operands[0]; 357 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 358 OS << ",+," << *Operands[i]; 359 OS << "}<" << L->getHeader()->getName() + ">"; 360} 361 362// SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular 363// value. Don't use a SCEVHandle here, or else the object will never be 364// deleted! 365static ManagedStatic<std::map<Value*, SCEVUnknown*> > SCEVUnknowns; 366 367SCEVUnknown::~SCEVUnknown() { SCEVUnknowns->erase(V); } 368 369bool SCEVUnknown::isLoopInvariant(const Loop *L) const { 370 // All non-instruction values are loop invariant. All instructions are loop 371 // invariant if they are not contained in the specified loop. 372 if (Instruction *I = dyn_cast<Instruction>(V)) 373 return !L->contains(I->getParent()); 374 return true; 375} 376 377const Type *SCEVUnknown::getType() const { 378 return V->getType(); 379} 380 381void SCEVUnknown::print(std::ostream &OS) const { 382 WriteAsOperand(OS, V, false); 383} 384 385//===----------------------------------------------------------------------===// 386// SCEV Utilities 387//===----------------------------------------------------------------------===// 388 389namespace { 390 /// SCEVComplexityCompare - Return true if the complexity of the LHS is less 391 /// than the complexity of the RHS. This comparator is used to canonicalize 392 /// expressions. 393 struct VISIBILITY_HIDDEN SCEVComplexityCompare { 394 bool operator()(SCEV *LHS, SCEV *RHS) { 395 return LHS->getSCEVType() < RHS->getSCEVType(); 396 } 397 }; 398} 399 400/// GroupByComplexity - Given a list of SCEV objects, order them by their 401/// complexity, and group objects of the same complexity together by value. 402/// When this routine is finished, we know that any duplicates in the vector are 403/// consecutive and that complexity is monotonically increasing. 404/// 405/// Note that we go take special precautions to ensure that we get determinstic 406/// results from this routine. In other words, we don't want the results of 407/// this to depend on where the addresses of various SCEV objects happened to 408/// land in memory. 409/// 410static void GroupByComplexity(std::vector<SCEVHandle> &Ops) { 411 if (Ops.size() < 2) return; // Noop 412 if (Ops.size() == 2) { 413 // This is the common case, which also happens to be trivially simple. 414 // Special case it. 415 if (Ops[0]->getSCEVType() > Ops[1]->getSCEVType()) 416 std::swap(Ops[0], Ops[1]); 417 return; 418 } 419 420 // Do the rough sort by complexity. 421 std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare()); 422 423 // Now that we are sorted by complexity, group elements of the same 424 // complexity. Note that this is, at worst, N^2, but the vector is likely to 425 // be extremely short in practice. Note that we take this approach because we 426 // do not want to depend on the addresses of the objects we are grouping. 427 for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) { 428 SCEV *S = Ops[i]; 429 unsigned Complexity = S->getSCEVType(); 430 431 // If there are any objects of the same complexity and same value as this 432 // one, group them. 433 for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) { 434 if (Ops[j] == S) { // Found a duplicate. 435 // Move it to immediately after i'th element. 436 std::swap(Ops[i+1], Ops[j]); 437 ++i; // no need to rescan it. 438 if (i == e-2) return; // Done! 439 } 440 } 441 } 442} 443 444 445 446//===----------------------------------------------------------------------===// 447// Simple SCEV method implementations 448//===----------------------------------------------------------------------===// 449 450/// getIntegerSCEV - Given an integer or FP type, create a constant for the 451/// specified signed integer value and return a SCEV for the constant. 452SCEVHandle SCEVUnknown::getIntegerSCEV(int Val, const Type *Ty) { 453 Constant *C; 454 if (Val == 0) 455 C = Constant::getNullValue(Ty); 456 else if (Ty->isFloatingPoint()) 457 C = ConstantFP::get(Ty, Val); 458 else 459 C = ConstantInt::get(Ty, Val); 460 return SCEVUnknown::get(C); 461} 462 463SCEVHandle SCEVUnknown::getIntegerSCEV(const APInt& Val) { 464 return SCEVUnknown::get(ConstantInt::get(Val)); 465} 466 467/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the 468/// input value to the specified type. If the type must be extended, it is zero 469/// extended. 470static SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty) { 471 const Type *SrcTy = V->getType(); 472 assert(SrcTy->isInteger() && Ty->isInteger() && 473 "Cannot truncate or zero extend with non-integer arguments!"); 474 if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits()) 475 return V; // No conversion 476 if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()) 477 return SCEVTruncateExpr::get(V, Ty); 478 return SCEVZeroExtendExpr::get(V, Ty); 479} 480 481/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V 482/// 483SCEVHandle SCEV::getNegativeSCEV(const SCEVHandle &V) { 484 if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) 485 return SCEVUnknown::get(ConstantExpr::getNeg(VC->getValue())); 486 487 return SCEVMulExpr::get(V, SCEVUnknown::getIntegerSCEV(-1, V->getType())); 488} 489 490/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS. 491/// 492SCEVHandle SCEV::getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS) { 493 // X - Y --> X + -Y 494 return SCEVAddExpr::get(LHS, SCEV::getNegativeSCEV(RHS)); 495} 496 497 498/// PartialFact - Compute V!/(V-NumSteps)! 499static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) { 500 // Handle this case efficiently, it is common to have constant iteration 501 // counts while computing loop exit values. 502 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) { 503 const APInt& Val = SC->getValue()->getValue(); 504 APInt Result(Val.getBitWidth(), 1); 505 for (; NumSteps; --NumSteps) 506 Result *= Val-(NumSteps-1); 507 return SCEVUnknown::get(ConstantInt::get(Result)); 508 } 509 510 const Type *Ty = V->getType(); 511 if (NumSteps == 0) 512 return SCEVUnknown::getIntegerSCEV(1, Ty); 513 514 SCEVHandle Result = V; 515 for (unsigned i = 1; i != NumSteps; ++i) 516 Result = SCEVMulExpr::get(Result, SCEV::getMinusSCEV(V, 517 SCEVUnknown::getIntegerSCEV(i, Ty))); 518 return Result; 519} 520 521 522/// evaluateAtIteration - Return the value of this chain of recurrences at 523/// the specified iteration number. We can evaluate this recurrence by 524/// multiplying each element in the chain by the binomial coefficient 525/// corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as: 526/// 527/// A*choose(It, 0) + B*choose(It, 1) + C*choose(It, 2) + D*choose(It, 3) 528/// 529/// FIXME/VERIFY: I don't trust that this is correct in the face of overflow. 530/// Is the binomial equation safe using modular arithmetic?? 531/// 532SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const { 533 SCEVHandle Result = getStart(); 534 int Divisor = 1; 535 const Type *Ty = It->getType(); 536 for (unsigned i = 1, e = getNumOperands(); i != e; ++i) { 537 SCEVHandle BC = PartialFact(It, i); 538 Divisor *= i; 539 SCEVHandle Val = SCEVSDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)), 540 SCEVUnknown::getIntegerSCEV(Divisor,Ty)); 541 Result = SCEVAddExpr::get(Result, Val); 542 } 543 return Result; 544} 545 546 547//===----------------------------------------------------------------------===// 548// SCEV Expression folder implementations 549//===----------------------------------------------------------------------===// 550 551SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) { 552 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) 553 return SCEVUnknown::get( 554 ConstantExpr::getTrunc(SC->getValue(), Ty)); 555 556 // If the input value is a chrec scev made out of constants, truncate 557 // all of the constants. 558 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) { 559 std::vector<SCEVHandle> Operands; 560 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) 561 // FIXME: This should allow truncation of other expression types! 562 if (isa<SCEVConstant>(AddRec->getOperand(i))) 563 Operands.push_back(get(AddRec->getOperand(i), Ty)); 564 else 565 break; 566 if (Operands.size() == AddRec->getNumOperands()) 567 return SCEVAddRecExpr::get(Operands, AddRec->getLoop()); 568 } 569 570 SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)]; 571 if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty); 572 return Result; 573} 574 575SCEVHandle SCEVZeroExtendExpr::get(const SCEVHandle &Op, const Type *Ty) { 576 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) 577 return SCEVUnknown::get( 578 ConstantExpr::getZExt(SC->getValue(), Ty)); 579 580 // FIXME: If the input value is a chrec scev, and we can prove that the value 581 // did not overflow the old, smaller, value, we can zero extend all of the 582 // operands (often constants). This would allow analysis of something like 583 // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; } 584 585 SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)]; 586 if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty); 587 return Result; 588} 589 590// get - Get a canonical add expression, or something simpler if possible. 591SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { 592 assert(!Ops.empty() && "Cannot get empty add!"); 593 if (Ops.size() == 1) return Ops[0]; 594 595 // Sort by complexity, this groups all similar expression types together. 596 GroupByComplexity(Ops); 597 598 // If there are any constants, fold them together. 599 unsigned Idx = 0; 600 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 601 ++Idx; 602 assert(Idx < Ops.size()); 603 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 604 // We found two constants, fold them together! 605 Constant *Fold = ConstantInt::get(LHSC->getValue()->getValue() + 606 RHSC->getValue()->getValue()); 607 if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) { 608 Ops[0] = SCEVConstant::get(CI); 609 Ops.erase(Ops.begin()+1); // Erase the folded element 610 if (Ops.size() == 1) return Ops[0]; 611 LHSC = cast<SCEVConstant>(Ops[0]); 612 } else { 613 // If we couldn't fold the expression, move to the next constant. Note 614 // that this is impossible to happen in practice because we always 615 // constant fold constant ints to constant ints. 616 ++Idx; 617 } 618 } 619 620 // If we are left with a constant zero being added, strip it off. 621 if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) { 622 Ops.erase(Ops.begin()); 623 --Idx; 624 } 625 } 626 627 if (Ops.size() == 1) return Ops[0]; 628 629 // Okay, check to see if the same value occurs in the operand list twice. If 630 // so, merge them together into an multiply expression. Since we sorted the 631 // list, these values are required to be adjacent. 632 const Type *Ty = Ops[0]->getType(); 633 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 634 if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2 635 // Found a match, merge the two values into a multiply, and add any 636 // remaining values to the result. 637 SCEVHandle Two = SCEVUnknown::getIntegerSCEV(2, Ty); 638 SCEVHandle Mul = SCEVMulExpr::get(Ops[i], Two); 639 if (Ops.size() == 2) 640 return Mul; 641 Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 642 Ops.push_back(Mul); 643 return SCEVAddExpr::get(Ops); 644 } 645 646 // Okay, now we know the first non-constant operand. If there are add 647 // operands they would be next. 648 if (Idx < Ops.size()) { 649 bool DeletedAdd = false; 650 while (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) { 651 // If we have an add, expand the add operands onto the end of the operands 652 // list. 653 Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); 654 Ops.erase(Ops.begin()+Idx); 655 DeletedAdd = true; 656 } 657 658 // If we deleted at least one add, we added operands to the end of the list, 659 // and they are not necessarily sorted. Recurse to resort and resimplify 660 // any operands we just aquired. 661 if (DeletedAdd) 662 return get(Ops); 663 } 664 665 // Skip over the add expression until we get to a multiply. 666 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) 667 ++Idx; 668 669 // If we are adding something to a multiply expression, make sure the 670 // something is not already an operand of the multiply. If so, merge it into 671 // the multiply. 672 for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) { 673 SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]); 674 for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) { 675 SCEV *MulOpSCEV = Mul->getOperand(MulOp); 676 for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp) 677 if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(MulOpSCEV)) { 678 // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1)) 679 SCEVHandle InnerMul = Mul->getOperand(MulOp == 0); 680 if (Mul->getNumOperands() != 2) { 681 // If the multiply has more than two operands, we must get the 682 // Y*Z term. 683 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end()); 684 MulOps.erase(MulOps.begin()+MulOp); 685 InnerMul = SCEVMulExpr::get(MulOps); 686 } 687 SCEVHandle One = SCEVUnknown::getIntegerSCEV(1, Ty); 688 SCEVHandle AddOne = SCEVAddExpr::get(InnerMul, One); 689 SCEVHandle OuterMul = SCEVMulExpr::get(AddOne, Ops[AddOp]); 690 if (Ops.size() == 2) return OuterMul; 691 if (AddOp < Idx) { 692 Ops.erase(Ops.begin()+AddOp); 693 Ops.erase(Ops.begin()+Idx-1); 694 } else { 695 Ops.erase(Ops.begin()+Idx); 696 Ops.erase(Ops.begin()+AddOp-1); 697 } 698 Ops.push_back(OuterMul); 699 return SCEVAddExpr::get(Ops); 700 } 701 702 // Check this multiply against other multiplies being added together. 703 for (unsigned OtherMulIdx = Idx+1; 704 OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]); 705 ++OtherMulIdx) { 706 SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]); 707 // If MulOp occurs in OtherMul, we can fold the two multiplies 708 // together. 709 for (unsigned OMulOp = 0, e = OtherMul->getNumOperands(); 710 OMulOp != e; ++OMulOp) 711 if (OtherMul->getOperand(OMulOp) == MulOpSCEV) { 712 // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E)) 713 SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0); 714 if (Mul->getNumOperands() != 2) { 715 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end()); 716 MulOps.erase(MulOps.begin()+MulOp); 717 InnerMul1 = SCEVMulExpr::get(MulOps); 718 } 719 SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0); 720 if (OtherMul->getNumOperands() != 2) { 721 std::vector<SCEVHandle> MulOps(OtherMul->op_begin(), 722 OtherMul->op_end()); 723 MulOps.erase(MulOps.begin()+OMulOp); 724 InnerMul2 = SCEVMulExpr::get(MulOps); 725 } 726 SCEVHandle InnerMulSum = SCEVAddExpr::get(InnerMul1,InnerMul2); 727 SCEVHandle OuterMul = SCEVMulExpr::get(MulOpSCEV, InnerMulSum); 728 if (Ops.size() == 2) return OuterMul; 729 Ops.erase(Ops.begin()+Idx); 730 Ops.erase(Ops.begin()+OtherMulIdx-1); 731 Ops.push_back(OuterMul); 732 return SCEVAddExpr::get(Ops); 733 } 734 } 735 } 736 } 737 738 // If there are any add recurrences in the operands list, see if any other 739 // added values are loop invariant. If so, we can fold them into the 740 // recurrence. 741 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) 742 ++Idx; 743 744 // Scan over all recurrences, trying to fold loop invariants into them. 745 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) { 746 // Scan all of the other operands to this add and add them to the vector if 747 // they are loop invariant w.r.t. the recurrence. 748 std::vector<SCEVHandle> LIOps; 749 SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]); 750 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 751 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { 752 LIOps.push_back(Ops[i]); 753 Ops.erase(Ops.begin()+i); 754 --i; --e; 755 } 756 757 // If we found some loop invariants, fold them into the recurrence. 758 if (!LIOps.empty()) { 759 // NLI + LI + { Start,+,Step} --> NLI + { LI+Start,+,Step } 760 LIOps.push_back(AddRec->getStart()); 761 762 std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end()); 763 AddRecOps[0] = SCEVAddExpr::get(LIOps); 764 765 SCEVHandle NewRec = SCEVAddRecExpr::get(AddRecOps, AddRec->getLoop()); 766 // If all of the other operands were loop invariant, we are done. 767 if (Ops.size() == 1) return NewRec; 768 769 // Otherwise, add the folded AddRec by the non-liv parts. 770 for (unsigned i = 0;; ++i) 771 if (Ops[i] == AddRec) { 772 Ops[i] = NewRec; 773 break; 774 } 775 return SCEVAddExpr::get(Ops); 776 } 777 778 // Okay, if there weren't any loop invariants to be folded, check to see if 779 // there are multiple AddRec's with the same loop induction variable being 780 // added together. If so, we can fold them. 781 for (unsigned OtherIdx = Idx+1; 782 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx) 783 if (OtherIdx != Idx) { 784 SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]); 785 if (AddRec->getLoop() == OtherAddRec->getLoop()) { 786 // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D} 787 std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end()); 788 for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) { 789 if (i >= NewOps.size()) { 790 NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i, 791 OtherAddRec->op_end()); 792 break; 793 } 794 NewOps[i] = SCEVAddExpr::get(NewOps[i], OtherAddRec->getOperand(i)); 795 } 796 SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, AddRec->getLoop()); 797 798 if (Ops.size() == 2) return NewAddRec; 799 800 Ops.erase(Ops.begin()+Idx); 801 Ops.erase(Ops.begin()+OtherIdx-1); 802 Ops.push_back(NewAddRec); 803 return SCEVAddExpr::get(Ops); 804 } 805 } 806 807 // Otherwise couldn't fold anything into this recurrence. Move onto the 808 // next one. 809 } 810 811 // Okay, it looks like we really DO need an add expr. Check to see if we 812 // already have one, otherwise create a new one. 813 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end()); 814 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr, 815 SCEVOps)]; 816 if (Result == 0) Result = new SCEVAddExpr(Ops); 817 return Result; 818} 819 820 821SCEVHandle SCEVMulExpr::get(std::vector<SCEVHandle> &Ops) { 822 assert(!Ops.empty() && "Cannot get empty mul!"); 823 824 // Sort by complexity, this groups all similar expression types together. 825 GroupByComplexity(Ops); 826 827 // If there are any constants, fold them together. 828 unsigned Idx = 0; 829 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 830 831 // C1*(C2+V) -> C1*C2 + C1*V 832 if (Ops.size() == 2) 833 if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) 834 if (Add->getNumOperands() == 2 && 835 isa<SCEVConstant>(Add->getOperand(0))) 836 return SCEVAddExpr::get(SCEVMulExpr::get(LHSC, Add->getOperand(0)), 837 SCEVMulExpr::get(LHSC, Add->getOperand(1))); 838 839 840 ++Idx; 841 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 842 // We found two constants, fold them together! 843 Constant *Fold = ConstantInt::get(LHSC->getValue()->getValue() * 844 RHSC->getValue()->getValue()); 845 if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) { 846 Ops[0] = SCEVConstant::get(CI); 847 Ops.erase(Ops.begin()+1); // Erase the folded element 848 if (Ops.size() == 1) return Ops[0]; 849 LHSC = cast<SCEVConstant>(Ops[0]); 850 } else { 851 // If we couldn't fold the expression, move to the next constant. Note 852 // that this is impossible to happen in practice because we always 853 // constant fold constant ints to constant ints. 854 ++Idx; 855 } 856 } 857 858 // If we are left with a constant one being multiplied, strip it off. 859 if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) { 860 Ops.erase(Ops.begin()); 861 --Idx; 862 } else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) { 863 // If we have a multiply of zero, it will always be zero. 864 return Ops[0]; 865 } 866 } 867 868 // Skip over the add expression until we get to a multiply. 869 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) 870 ++Idx; 871 872 if (Ops.size() == 1) 873 return Ops[0]; 874 875 // If there are mul operands inline them all into this expression. 876 if (Idx < Ops.size()) { 877 bool DeletedMul = false; 878 while (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) { 879 // If we have an mul, expand the mul operands onto the end of the operands 880 // list. 881 Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end()); 882 Ops.erase(Ops.begin()+Idx); 883 DeletedMul = true; 884 } 885 886 // If we deleted at least one mul, we added operands to the end of the list, 887 // and they are not necessarily sorted. Recurse to resort and resimplify 888 // any operands we just aquired. 889 if (DeletedMul) 890 return get(Ops); 891 } 892 893 // If there are any add recurrences in the operands list, see if any other 894 // added values are loop invariant. If so, we can fold them into the 895 // recurrence. 896 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) 897 ++Idx; 898 899 // Scan over all recurrences, trying to fold loop invariants into them. 900 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) { 901 // Scan all of the other operands to this mul and add them to the vector if 902 // they are loop invariant w.r.t. the recurrence. 903 std::vector<SCEVHandle> LIOps; 904 SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]); 905 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 906 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { 907 LIOps.push_back(Ops[i]); 908 Ops.erase(Ops.begin()+i); 909 --i; --e; 910 } 911 912 // If we found some loop invariants, fold them into the recurrence. 913 if (!LIOps.empty()) { 914 // NLI * LI * { Start,+,Step} --> NLI * { LI*Start,+,LI*Step } 915 std::vector<SCEVHandle> NewOps; 916 NewOps.reserve(AddRec->getNumOperands()); 917 if (LIOps.size() == 1) { 918 SCEV *Scale = LIOps[0]; 919 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) 920 NewOps.push_back(SCEVMulExpr::get(Scale, AddRec->getOperand(i))); 921 } else { 922 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { 923 std::vector<SCEVHandle> MulOps(LIOps); 924 MulOps.push_back(AddRec->getOperand(i)); 925 NewOps.push_back(SCEVMulExpr::get(MulOps)); 926 } 927 } 928 929 SCEVHandle NewRec = SCEVAddRecExpr::get(NewOps, AddRec->getLoop()); 930 931 // If all of the other operands were loop invariant, we are done. 932 if (Ops.size() == 1) return NewRec; 933 934 // Otherwise, multiply the folded AddRec by the non-liv parts. 935 for (unsigned i = 0;; ++i) 936 if (Ops[i] == AddRec) { 937 Ops[i] = NewRec; 938 break; 939 } 940 return SCEVMulExpr::get(Ops); 941 } 942 943 // Okay, if there weren't any loop invariants to be folded, check to see if 944 // there are multiple AddRec's with the same loop induction variable being 945 // multiplied together. If so, we can fold them. 946 for (unsigned OtherIdx = Idx+1; 947 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx) 948 if (OtherIdx != Idx) { 949 SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]); 950 if (AddRec->getLoop() == OtherAddRec->getLoop()) { 951 // F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D} 952 SCEVAddRecExpr *F = AddRec, *G = OtherAddRec; 953 SCEVHandle NewStart = SCEVMulExpr::get(F->getStart(), 954 G->getStart()); 955 SCEVHandle B = F->getStepRecurrence(); 956 SCEVHandle D = G->getStepRecurrence(); 957 SCEVHandle NewStep = SCEVAddExpr::get(SCEVMulExpr::get(F, D), 958 SCEVMulExpr::get(G, B), 959 SCEVMulExpr::get(B, D)); 960 SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewStart, NewStep, 961 F->getLoop()); 962 if (Ops.size() == 2) return NewAddRec; 963 964 Ops.erase(Ops.begin()+Idx); 965 Ops.erase(Ops.begin()+OtherIdx-1); 966 Ops.push_back(NewAddRec); 967 return SCEVMulExpr::get(Ops); 968 } 969 } 970 971 // Otherwise couldn't fold anything into this recurrence. Move onto the 972 // next one. 973 } 974 975 // Okay, it looks like we really DO need an mul expr. Check to see if we 976 // already have one, otherwise create a new one. 977 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end()); 978 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr, 979 SCEVOps)]; 980 if (Result == 0) 981 Result = new SCEVMulExpr(Ops); 982 return Result; 983} 984 985SCEVHandle SCEVSDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 986 if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) { 987 if (RHSC->getValue()->equalsInt(1)) 988 return LHS; // X sdiv 1 --> x 989 if (RHSC->getValue()->isAllOnesValue()) 990 return SCEV::getNegativeSCEV(LHS); // X sdiv -1 --> -x 991 992 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) { 993 Constant *LHSCV = LHSC->getValue(); 994 Constant *RHSCV = RHSC->getValue(); 995 return SCEVUnknown::get(ConstantExpr::getSDiv(LHSCV, RHSCV)); 996 } 997 } 998 999 // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow. 1000 1001 SCEVSDivExpr *&Result = (*SCEVSDivs)[std::make_pair(LHS, RHS)]; 1002 if (Result == 0) Result = new SCEVSDivExpr(LHS, RHS); 1003 return Result; 1004} 1005 1006 1007/// SCEVAddRecExpr::get - Get a add recurrence expression for the 1008/// specified loop. Simplify the expression as much as possible. 1009SCEVHandle SCEVAddRecExpr::get(const SCEVHandle &Start, 1010 const SCEVHandle &Step, const Loop *L) { 1011 std::vector<SCEVHandle> Operands; 1012 Operands.push_back(Start); 1013 if (SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step)) 1014 if (StepChrec->getLoop() == L) { 1015 Operands.insert(Operands.end(), StepChrec->op_begin(), 1016 StepChrec->op_end()); 1017 return get(Operands, L); 1018 } 1019 1020 Operands.push_back(Step); 1021 return get(Operands, L); 1022} 1023 1024/// SCEVAddRecExpr::get - Get a add recurrence expression for the 1025/// specified loop. Simplify the expression as much as possible. 1026SCEVHandle SCEVAddRecExpr::get(std::vector<SCEVHandle> &Operands, 1027 const Loop *L) { 1028 if (Operands.size() == 1) return Operands[0]; 1029 1030 if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Operands.back())) 1031 if (StepC->getValue()->isZero()) { 1032 Operands.pop_back(); 1033 return get(Operands, L); // { X,+,0 } --> X 1034 } 1035 1036 SCEVAddRecExpr *&Result = 1037 (*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(), 1038 Operands.end()))]; 1039 if (Result == 0) Result = new SCEVAddRecExpr(Operands, L); 1040 return Result; 1041} 1042 1043SCEVHandle SCEVUnknown::get(Value *V) { 1044 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 1045 return SCEVConstant::get(CI); 1046 SCEVUnknown *&Result = (*SCEVUnknowns)[V]; 1047 if (Result == 0) Result = new SCEVUnknown(V); 1048 return Result; 1049} 1050 1051 1052//===----------------------------------------------------------------------===// 1053// ScalarEvolutionsImpl Definition and Implementation 1054//===----------------------------------------------------------------------===// 1055// 1056/// ScalarEvolutionsImpl - This class implements the main driver for the scalar 1057/// evolution code. 1058/// 1059namespace { 1060 struct VISIBILITY_HIDDEN ScalarEvolutionsImpl { 1061 /// F - The function we are analyzing. 1062 /// 1063 Function &F; 1064 1065 /// LI - The loop information for the function we are currently analyzing. 1066 /// 1067 LoopInfo &LI; 1068 1069 /// UnknownValue - This SCEV is used to represent unknown trip counts and 1070 /// things. 1071 SCEVHandle UnknownValue; 1072 1073 /// Scalars - This is a cache of the scalars we have analyzed so far. 1074 /// 1075 std::map<Value*, SCEVHandle> Scalars; 1076 1077 /// IterationCounts - Cache the iteration count of the loops for this 1078 /// function as they are computed. 1079 std::map<const Loop*, SCEVHandle> IterationCounts; 1080 1081 /// ConstantEvolutionLoopExitValue - This map contains entries for all of 1082 /// the PHI instructions that we attempt to compute constant evolutions for. 1083 /// This allows us to avoid potentially expensive recomputation of these 1084 /// properties. An instruction maps to null if we are unable to compute its 1085 /// exit value. 1086 std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 1087 1088 public: 1089 ScalarEvolutionsImpl(Function &f, LoopInfo &li) 1090 : F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {} 1091 1092 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the 1093 /// expression and create a new one. 1094 SCEVHandle getSCEV(Value *V); 1095 1096 /// hasSCEV - Return true if the SCEV for this value has already been 1097 /// computed. 1098 bool hasSCEV(Value *V) const { 1099 return Scalars.count(V); 1100 } 1101 1102 /// setSCEV - Insert the specified SCEV into the map of current SCEVs for 1103 /// the specified value. 1104 void setSCEV(Value *V, const SCEVHandle &H) { 1105 bool isNew = Scalars.insert(std::make_pair(V, H)).second; 1106 assert(isNew && "This entry already existed!"); 1107 } 1108 1109 1110 /// getSCEVAtScope - Compute the value of the specified expression within 1111 /// the indicated loop (which may be null to indicate in no loop). If the 1112 /// expression cannot be evaluated, return UnknownValue itself. 1113 SCEVHandle getSCEVAtScope(SCEV *V, const Loop *L); 1114 1115 1116 /// hasLoopInvariantIterationCount - Return true if the specified loop has 1117 /// an analyzable loop-invariant iteration count. 1118 bool hasLoopInvariantIterationCount(const Loop *L); 1119 1120 /// getIterationCount - If the specified loop has a predictable iteration 1121 /// count, return it. Note that it is not valid to call this method on a 1122 /// loop without a loop-invariant iteration count. 1123 SCEVHandle getIterationCount(const Loop *L); 1124 1125 /// deleteInstructionFromRecords - This method should be called by the 1126 /// client before it removes an instruction from the program, to make sure 1127 /// that no dangling references are left around. 1128 void deleteInstructionFromRecords(Instruction *I); 1129 1130 private: 1131 /// createSCEV - We know that there is no SCEV for the specified value. 1132 /// Analyze the expression. 1133 SCEVHandle createSCEV(Value *V); 1134 1135 /// createNodeForPHI - Provide the special handling we need to analyze PHI 1136 /// SCEVs. 1137 SCEVHandle createNodeForPHI(PHINode *PN); 1138 1139 /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value 1140 /// for the specified instruction and replaces any references to the 1141 /// symbolic value SymName with the specified value. This is used during 1142 /// PHI resolution. 1143 void ReplaceSymbolicValueWithConcrete(Instruction *I, 1144 const SCEVHandle &SymName, 1145 const SCEVHandle &NewVal); 1146 1147 /// ComputeIterationCount - Compute the number of times the specified loop 1148 /// will iterate. 1149 SCEVHandle ComputeIterationCount(const Loop *L); 1150 1151 /// ComputeLoadConstantCompareIterationCount - Given an exit condition of 1152 /// 'setcc load X, cst', try to see if we can compute the trip count. 1153 SCEVHandle ComputeLoadConstantCompareIterationCount(LoadInst *LI, 1154 Constant *RHS, 1155 const Loop *L, 1156 ICmpInst::Predicate p); 1157 1158 /// ComputeIterationCountExhaustively - If the trip is known to execute a 1159 /// constant number of times (the condition evolves only from constants), 1160 /// try to evaluate a few iterations of the loop until we get the exit 1161 /// condition gets a value of ExitWhen (true or false). If we cannot 1162 /// evaluate the trip count of the loop, return UnknownValue. 1163 SCEVHandle ComputeIterationCountExhaustively(const Loop *L, Value *Cond, 1164 bool ExitWhen); 1165 1166 /// HowFarToZero - Return the number of times a backedge comparing the 1167 /// specified value to zero will execute. If not computable, return 1168 /// UnknownValue. 1169 SCEVHandle HowFarToZero(SCEV *V, const Loop *L); 1170 1171 /// HowFarToNonZero - Return the number of times a backedge checking the 1172 /// specified value for nonzero will execute. If not computable, return 1173 /// UnknownValue. 1174 SCEVHandle HowFarToNonZero(SCEV *V, const Loop *L); 1175 1176 /// HowManyLessThans - Return the number of times a backedge containing the 1177 /// specified less-than comparison will execute. If not computable, return 1178 /// UnknownValue. 1179 SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L); 1180 1181 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 1182 /// in the header of its containing loop, we know the loop executes a 1183 /// constant number of times, and the PHI node is just a recurrence 1184 /// involving constants, fold it. 1185 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its, 1186 const Loop *L); 1187 }; 1188} 1189 1190//===----------------------------------------------------------------------===// 1191// Basic SCEV Analysis and PHI Idiom Recognition Code 1192// 1193 1194/// deleteInstructionFromRecords - This method should be called by the 1195/// client before it removes an instruction from the program, to make sure 1196/// that no dangling references are left around. 1197void ScalarEvolutionsImpl::deleteInstructionFromRecords(Instruction *I) { 1198 Scalars.erase(I); 1199 if (PHINode *PN = dyn_cast<PHINode>(I)) 1200 ConstantEvolutionLoopExitValue.erase(PN); 1201} 1202 1203 1204/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the 1205/// expression and create a new one. 1206SCEVHandle ScalarEvolutionsImpl::getSCEV(Value *V) { 1207 assert(V->getType() != Type::VoidTy && "Can't analyze void expressions!"); 1208 1209 std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V); 1210 if (I != Scalars.end()) return I->second; 1211 SCEVHandle S = createSCEV(V); 1212 Scalars.insert(std::make_pair(V, S)); 1213 return S; 1214} 1215 1216/// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for 1217/// the specified instruction and replaces any references to the symbolic value 1218/// SymName with the specified value. This is used during PHI resolution. 1219void ScalarEvolutionsImpl:: 1220ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName, 1221 const SCEVHandle &NewVal) { 1222 std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I); 1223 if (SI == Scalars.end()) return; 1224 1225 SCEVHandle NV = 1226 SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal); 1227 if (NV == SI->second) return; // No change. 1228 1229 SI->second = NV; // Update the scalars map! 1230 1231 // Any instruction values that use this instruction might also need to be 1232 // updated! 1233 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1234 UI != E; ++UI) 1235 ReplaceSymbolicValueWithConcrete(cast<Instruction>(*UI), SymName, NewVal); 1236} 1237 1238/// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in 1239/// a loop header, making it a potential recurrence, or it doesn't. 1240/// 1241SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) { 1242 if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized. 1243 if (const Loop *L = LI.getLoopFor(PN->getParent())) 1244 if (L->getHeader() == PN->getParent()) { 1245 // If it lives in the loop header, it has two incoming values, one 1246 // from outside the loop, and one from inside. 1247 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 1248 unsigned BackEdge = IncomingEdge^1; 1249 1250 // While we are analyzing this PHI node, handle its value symbolically. 1251 SCEVHandle SymbolicName = SCEVUnknown::get(PN); 1252 assert(Scalars.find(PN) == Scalars.end() && 1253 "PHI node already processed?"); 1254 Scalars.insert(std::make_pair(PN, SymbolicName)); 1255 1256 // Using this symbolic name for the PHI, analyze the value coming around 1257 // the back-edge. 1258 SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge)); 1259 1260 // NOTE: If BEValue is loop invariant, we know that the PHI node just 1261 // has a special value for the first iteration of the loop. 1262 1263 // If the value coming around the backedge is an add with the symbolic 1264 // value we just inserted, then we found a simple induction variable! 1265 if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) { 1266 // If there is a single occurrence of the symbolic value, replace it 1267 // with a recurrence. 1268 unsigned FoundIndex = Add->getNumOperands(); 1269 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) 1270 if (Add->getOperand(i) == SymbolicName) 1271 if (FoundIndex == e) { 1272 FoundIndex = i; 1273 break; 1274 } 1275 1276 if (FoundIndex != Add->getNumOperands()) { 1277 // Create an add with everything but the specified operand. 1278 std::vector<SCEVHandle> Ops; 1279 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) 1280 if (i != FoundIndex) 1281 Ops.push_back(Add->getOperand(i)); 1282 SCEVHandle Accum = SCEVAddExpr::get(Ops); 1283 1284 // This is not a valid addrec if the step amount is varying each 1285 // loop iteration, but is not itself an addrec in this loop. 1286 if (Accum->isLoopInvariant(L) || 1287 (isa<SCEVAddRecExpr>(Accum) && 1288 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) { 1289 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); 1290 SCEVHandle PHISCEV = SCEVAddRecExpr::get(StartVal, Accum, L); 1291 1292 // Okay, for the entire analysis of this edge we assumed the PHI 1293 // to be symbolic. We now need to go back and update all of the 1294 // entries for the scalars that use the PHI (except for the PHI 1295 // itself) to use the new analyzed value instead of the "symbolic" 1296 // value. 1297 ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV); 1298 return PHISCEV; 1299 } 1300 } 1301 } else if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(BEValue)) { 1302 // Otherwise, this could be a loop like this: 1303 // i = 0; for (j = 1; ..; ++j) { .... i = j; } 1304 // In this case, j = {1,+,1} and BEValue is j. 1305 // Because the other in-value of i (0) fits the evolution of BEValue 1306 // i really is an addrec evolution. 1307 if (AddRec->getLoop() == L && AddRec->isAffine()) { 1308 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); 1309 1310 // If StartVal = j.start - j.stride, we can use StartVal as the 1311 // initial step of the addrec evolution. 1312 if (StartVal == SCEV::getMinusSCEV(AddRec->getOperand(0), 1313 AddRec->getOperand(1))) { 1314 SCEVHandle PHISCEV = 1315 SCEVAddRecExpr::get(StartVal, AddRec->getOperand(1), L); 1316 1317 // Okay, for the entire analysis of this edge we assumed the PHI 1318 // to be symbolic. We now need to go back and update all of the 1319 // entries for the scalars that use the PHI (except for the PHI 1320 // itself) to use the new analyzed value instead of the "symbolic" 1321 // value. 1322 ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV); 1323 return PHISCEV; 1324 } 1325 } 1326 } 1327 1328 return SymbolicName; 1329 } 1330 1331 // If it's not a loop phi, we can't handle it yet. 1332 return SCEVUnknown::get(PN); 1333} 1334 1335/// GetConstantFactor - Determine the largest constant factor that S has. For 1336/// example, turn {4,+,8} -> 4. (S umod result) should always equal zero. 1337static APInt GetConstantFactor(SCEVHandle S) { 1338 if (SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 1339 const APInt& V = C->getValue()->getValue(); 1340 if (!V.isMinValue()) 1341 return V; 1342 else // Zero is a multiple of everything. 1343 return APInt(C->getBitWidth(), 1).shl(C->getBitWidth()-1); 1344 } 1345 1346 if (SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S)) { 1347 return GetConstantFactor(T->getOperand()).trunc( 1348 cast<IntegerType>(T->getType())->getBitWidth()); 1349 } 1350 if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) 1351 return GetConstantFactor(E->getOperand()).zext( 1352 cast<IntegerType>(E->getType())->getBitWidth()); 1353 1354 if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 1355 // The result is the min of all operands. 1356 APInt Res(GetConstantFactor(A->getOperand(0))); 1357 for (unsigned i = 1, e = A->getNumOperands(); 1358 i != e && Res.ugt(APInt(Res.getBitWidth(),1)); ++i) { 1359 APInt Tmp(GetConstantFactor(A->getOperand(i))); 1360 Res = APIntOps::umin(Res, Tmp); 1361 } 1362 return Res; 1363 } 1364 1365 if (SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) { 1366 // The result is the product of all the operands. 1367 APInt Res(GetConstantFactor(M->getOperand(0))); 1368 for (unsigned i = 1, e = M->getNumOperands(); i != e; ++i) { 1369 APInt Tmp(GetConstantFactor(M->getOperand(i))); 1370 Res *= Tmp; 1371 } 1372 return Res; 1373 } 1374 1375 if (SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 1376 // For now, we just handle linear expressions. 1377 if (A->getNumOperands() == 2) { 1378 // We want the GCD between the start and the stride value. 1379 APInt Start(GetConstantFactor(A->getOperand(0))); 1380 if (Start == 1) 1381 return Start; 1382 APInt Stride(GetConstantFactor(A->getOperand(1))); 1383 return APIntOps::GreatestCommonDivisor(Start, Stride); 1384 } 1385 } 1386 1387 // SCEVSDivExpr, SCEVUnknown. 1388 return APInt(S->getBitWidth(), 1); 1389} 1390 1391/// createSCEV - We know that there is no SCEV for the specified value. 1392/// Analyze the expression. 1393/// 1394SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) { 1395 if (Instruction *I = dyn_cast<Instruction>(V)) { 1396 switch (I->getOpcode()) { 1397 case Instruction::Add: 1398 return SCEVAddExpr::get(getSCEV(I->getOperand(0)), 1399 getSCEV(I->getOperand(1))); 1400 case Instruction::Mul: 1401 return SCEVMulExpr::get(getSCEV(I->getOperand(0)), 1402 getSCEV(I->getOperand(1))); 1403 case Instruction::SDiv: 1404 return SCEVSDivExpr::get(getSCEV(I->getOperand(0)), 1405 getSCEV(I->getOperand(1))); 1406 break; 1407 1408 case Instruction::Sub: 1409 return SCEV::getMinusSCEV(getSCEV(I->getOperand(0)), 1410 getSCEV(I->getOperand(1))); 1411 case Instruction::Or: 1412 // If the RHS of the Or is a constant, we may have something like: 1413 // X*4+1 which got turned into X*4|1. Handle this as an add so loop 1414 // optimizations will transparently handle this case. 1415 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) { 1416 SCEVHandle LHS = getSCEV(I->getOperand(0)); 1417 APInt CommonFact(GetConstantFactor(LHS)); 1418 assert(!CommonFact.isMinValue() && 1419 "Common factor should at least be 1!"); 1420 if (CommonFact.ugt(CI->getValue())) { 1421 // If the LHS is a multiple that is larger than the RHS, use +. 1422 return SCEVAddExpr::get(LHS, 1423 getSCEV(I->getOperand(1))); 1424 } 1425 } 1426 break; 1427 case Instruction::Xor: 1428 // If the RHS of the xor is a signbit, then this is just an add. 1429 // Instcombine turns add of signbit into xor as a strength reduction step. 1430 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) { 1431 if (CI->getValue().isSignBit()) 1432 return SCEVAddExpr::get(getSCEV(I->getOperand(0)), 1433 getSCEV(I->getOperand(1))); 1434 } 1435 break; 1436 1437 case Instruction::Shl: 1438 // Turn shift left of a constant amount into a multiply. 1439 if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 1440 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 1441 Constant *X = ConstantInt::get( 1442 APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth))); 1443 return SCEVMulExpr::get(getSCEV(I->getOperand(0)), getSCEV(X)); 1444 } 1445 break; 1446 1447 case Instruction::Trunc: 1448 return SCEVTruncateExpr::get(getSCEV(I->getOperand(0)), I->getType()); 1449 1450 case Instruction::ZExt: 1451 return SCEVZeroExtendExpr::get(getSCEV(I->getOperand(0)), I->getType()); 1452 1453 case Instruction::BitCast: 1454 // BitCasts are no-op casts so we just eliminate the cast. 1455 if (I->getType()->isInteger() && 1456 I->getOperand(0)->getType()->isInteger()) 1457 return getSCEV(I->getOperand(0)); 1458 break; 1459 1460 case Instruction::PHI: 1461 return createNodeForPHI(cast<PHINode>(I)); 1462 1463 default: // We cannot analyze this expression. 1464 break; 1465 } 1466 } 1467 1468 return SCEVUnknown::get(V); 1469} 1470 1471 1472 1473//===----------------------------------------------------------------------===// 1474// Iteration Count Computation Code 1475// 1476 1477/// getIterationCount - If the specified loop has a predictable iteration 1478/// count, return it. Note that it is not valid to call this method on a 1479/// loop without a loop-invariant iteration count. 1480SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) { 1481 std::map<const Loop*, SCEVHandle>::iterator I = IterationCounts.find(L); 1482 if (I == IterationCounts.end()) { 1483 SCEVHandle ItCount = ComputeIterationCount(L); 1484 I = IterationCounts.insert(std::make_pair(L, ItCount)).first; 1485 if (ItCount != UnknownValue) { 1486 assert(ItCount->isLoopInvariant(L) && 1487 "Computed trip count isn't loop invariant for loop!"); 1488 ++NumTripCountsComputed; 1489 } else if (isa<PHINode>(L->getHeader()->begin())) { 1490 // Only count loops that have phi nodes as not being computable. 1491 ++NumTripCountsNotComputed; 1492 } 1493 } 1494 return I->second; 1495} 1496 1497/// ComputeIterationCount - Compute the number of times the specified loop 1498/// will iterate. 1499SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { 1500 // If the loop has a non-one exit block count, we can't analyze it. 1501 std::vector<BasicBlock*> ExitBlocks; 1502 L->getExitBlocks(ExitBlocks); 1503 if (ExitBlocks.size() != 1) return UnknownValue; 1504 1505 // Okay, there is one exit block. Try to find the condition that causes the 1506 // loop to be exited. 1507 BasicBlock *ExitBlock = ExitBlocks[0]; 1508 1509 BasicBlock *ExitingBlock = 0; 1510 for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock); 1511 PI != E; ++PI) 1512 if (L->contains(*PI)) { 1513 if (ExitingBlock == 0) 1514 ExitingBlock = *PI; 1515 else 1516 return UnknownValue; // More than one block exiting! 1517 } 1518 assert(ExitingBlock && "No exits from loop, something is broken!"); 1519 1520 // Okay, we've computed the exiting block. See what condition causes us to 1521 // exit. 1522 // 1523 // FIXME: we should be able to handle switch instructions (with a single exit) 1524 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 1525 if (ExitBr == 0) return UnknownValue; 1526 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!"); 1527 1528 // At this point, we know we have a conditional branch that determines whether 1529 // the loop is exited. However, we don't know if the branch is executed each 1530 // time through the loop. If not, then the execution count of the branch will 1531 // not be equal to the trip count of the loop. 1532 // 1533 // Currently we check for this by checking to see if the Exit branch goes to 1534 // the loop header. If so, we know it will always execute the same number of 1535 // times as the loop. We also handle the case where the exit block *is* the 1536 // loop header. This is common for un-rotated loops. More extensive analysis 1537 // could be done to handle more cases here. 1538 if (ExitBr->getSuccessor(0) != L->getHeader() && 1539 ExitBr->getSuccessor(1) != L->getHeader() && 1540 ExitBr->getParent() != L->getHeader()) 1541 return UnknownValue; 1542 1543 ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition()); 1544 1545 // If its not an integer comparison then compute it the hard way. 1546 // Note that ICmpInst deals with pointer comparisons too so we must check 1547 // the type of the operand. 1548 if (ExitCond == 0 || isa<PointerType>(ExitCond->getOperand(0)->getType())) 1549 return ComputeIterationCountExhaustively(L, ExitBr->getCondition(), 1550 ExitBr->getSuccessor(0) == ExitBlock); 1551 1552 // If the condition was exit on true, convert the condition to exit on false 1553 ICmpInst::Predicate Cond; 1554 if (ExitBr->getSuccessor(1) == ExitBlock) 1555 Cond = ExitCond->getPredicate(); 1556 else 1557 Cond = ExitCond->getInversePredicate(); 1558 1559 // Handle common loops like: for (X = "string"; *X; ++X) 1560 if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0))) 1561 if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) { 1562 SCEVHandle ItCnt = 1563 ComputeLoadConstantCompareIterationCount(LI, RHS, L, Cond); 1564 if (!isa<SCEVCouldNotCompute>(ItCnt)) return ItCnt; 1565 } 1566 1567 SCEVHandle LHS = getSCEV(ExitCond->getOperand(0)); 1568 SCEVHandle RHS = getSCEV(ExitCond->getOperand(1)); 1569 1570 // Try to evaluate any dependencies out of the loop. 1571 SCEVHandle Tmp = getSCEVAtScope(LHS, L); 1572 if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp; 1573 Tmp = getSCEVAtScope(RHS, L); 1574 if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp; 1575 1576 // At this point, we would like to compute how many iterations of the 1577 // loop the predicate will return true for these inputs. 1578 if (isa<SCEVConstant>(LHS) && !isa<SCEVConstant>(RHS)) { 1579 // If there is a constant, force it into the RHS. 1580 std::swap(LHS, RHS); 1581 Cond = ICmpInst::getSwappedPredicate(Cond); 1582 } 1583 1584 // FIXME: think about handling pointer comparisons! i.e.: 1585 // while (P != P+100) ++P; 1586 1587 // If we have a comparison of a chrec against a constant, try to use value 1588 // ranges to answer this query. 1589 if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) 1590 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS)) 1591 if (AddRec->getLoop() == L) { 1592 // Form the comparison range using the constant of the correct type so 1593 // that the ConstantRange class knows to do a signed or unsigned 1594 // comparison. 1595 ConstantInt *CompVal = RHSC->getValue(); 1596 const Type *RealTy = ExitCond->getOperand(0)->getType(); 1597 CompVal = dyn_cast<ConstantInt>( 1598 ConstantExpr::getBitCast(CompVal, RealTy)); 1599 if (CompVal) { 1600 // Form the constant range. 1601 ConstantRange CompRange( 1602 ICmpInst::makeConstantRange(Cond, CompVal->getValue())); 1603 1604 SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, 1605 false /*Always treat as unsigned range*/); 1606 if (!isa<SCEVCouldNotCompute>(Ret)) return Ret; 1607 } 1608 } 1609 1610 switch (Cond) { 1611 case ICmpInst::ICMP_NE: { // while (X != Y) 1612 // Convert to: while (X-Y != 0) 1613 SCEVHandle TC = HowFarToZero(SCEV::getMinusSCEV(LHS, RHS), L); 1614 if (!isa<SCEVCouldNotCompute>(TC)) return TC; 1615 break; 1616 } 1617 case ICmpInst::ICMP_EQ: { 1618 // Convert to: while (X-Y == 0) // while (X == Y) 1619 SCEVHandle TC = HowFarToNonZero(SCEV::getMinusSCEV(LHS, RHS), L); 1620 if (!isa<SCEVCouldNotCompute>(TC)) return TC; 1621 break; 1622 } 1623 case ICmpInst::ICMP_SLT: { 1624 SCEVHandle TC = HowManyLessThans(LHS, RHS, L); 1625 if (!isa<SCEVCouldNotCompute>(TC)) return TC; 1626 break; 1627 } 1628 case ICmpInst::ICMP_SGT: { 1629 SCEVHandle TC = HowManyLessThans(RHS, LHS, L); 1630 if (!isa<SCEVCouldNotCompute>(TC)) return TC; 1631 break; 1632 } 1633 default: 1634#if 0 1635 cerr << "ComputeIterationCount "; 1636 if (ExitCond->getOperand(0)->getType()->isUnsigned()) 1637 cerr << "[unsigned] "; 1638 cerr << *LHS << " " 1639 << Instruction::getOpcodeName(Instruction::ICmp) 1640 << " " << *RHS << "\n"; 1641#endif 1642 break; 1643 } 1644 return ComputeIterationCountExhaustively(L, ExitCond, 1645 ExitBr->getSuccessor(0) == ExitBlock); 1646} 1647 1648static ConstantInt * 1649EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, Constant *C) { 1650 SCEVHandle InVal = SCEVConstant::get(cast<ConstantInt>(C)); 1651 SCEVHandle Val = AddRec->evaluateAtIteration(InVal); 1652 assert(isa<SCEVConstant>(Val) && 1653 "Evaluation of SCEV at constant didn't fold correctly?"); 1654 return cast<SCEVConstant>(Val)->getValue(); 1655} 1656 1657/// GetAddressedElementFromGlobal - Given a global variable with an initializer 1658/// and a GEP expression (missing the pointer index) indexing into it, return 1659/// the addressed element of the initializer or null if the index expression is 1660/// invalid. 1661static Constant * 1662GetAddressedElementFromGlobal(GlobalVariable *GV, 1663 const std::vector<ConstantInt*> &Indices) { 1664 Constant *Init = GV->getInitializer(); 1665 for (unsigned i = 0, e = Indices.size(); i != e; ++i) { 1666 uint64_t Idx = Indices[i]->getZExtValue(); 1667 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) { 1668 assert(Idx < CS->getNumOperands() && "Bad struct index!"); 1669 Init = cast<Constant>(CS->getOperand(Idx)); 1670 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) { 1671 if (Idx >= CA->getNumOperands()) return 0; // Bogus program 1672 Init = cast<Constant>(CA->getOperand(Idx)); 1673 } else if (isa<ConstantAggregateZero>(Init)) { 1674 if (const StructType *STy = dyn_cast<StructType>(Init->getType())) { 1675 assert(Idx < STy->getNumElements() && "Bad struct index!"); 1676 Init = Constant::getNullValue(STy->getElementType(Idx)); 1677 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) { 1678 if (Idx >= ATy->getNumElements()) return 0; // Bogus program 1679 Init = Constant::getNullValue(ATy->getElementType()); 1680 } else { 1681 assert(0 && "Unknown constant aggregate type!"); 1682 } 1683 return 0; 1684 } else { 1685 return 0; // Unknown initializer type 1686 } 1687 } 1688 return Init; 1689} 1690 1691/// ComputeLoadConstantCompareIterationCount - Given an exit condition of 1692/// 'setcc load X, cst', try to se if we can compute the trip count. 1693SCEVHandle ScalarEvolutionsImpl:: 1694ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS, 1695 const Loop *L, 1696 ICmpInst::Predicate predicate) { 1697 if (LI->isVolatile()) return UnknownValue; 1698 1699 // Check to see if the loaded pointer is a getelementptr of a global. 1700 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0)); 1701 if (!GEP) return UnknownValue; 1702 1703 // Make sure that it is really a constant global we are gepping, with an 1704 // initializer, and make sure the first IDX is really 0. 1705 GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)); 1706 if (!GV || !GV->isConstant() || !GV->hasInitializer() || 1707 GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) || 1708 !cast<Constant>(GEP->getOperand(1))->isNullValue()) 1709 return UnknownValue; 1710 1711 // Okay, we allow one non-constant index into the GEP instruction. 1712 Value *VarIdx = 0; 1713 std::vector<ConstantInt*> Indexes; 1714 unsigned VarIdxNum = 0; 1715 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) 1716 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) { 1717 Indexes.push_back(CI); 1718 } else if (!isa<ConstantInt>(GEP->getOperand(i))) { 1719 if (VarIdx) return UnknownValue; // Multiple non-constant idx's. 1720 VarIdx = GEP->getOperand(i); 1721 VarIdxNum = i-2; 1722 Indexes.push_back(0); 1723 } 1724 1725 // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant. 1726 // Check to see if X is a loop variant variable value now. 1727 SCEVHandle Idx = getSCEV(VarIdx); 1728 SCEVHandle Tmp = getSCEVAtScope(Idx, L); 1729 if (!isa<SCEVCouldNotCompute>(Tmp)) Idx = Tmp; 1730 1731 // We can only recognize very limited forms of loop index expressions, in 1732 // particular, only affine AddRec's like {C1,+,C2}. 1733 SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx); 1734 if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) || 1735 !isa<SCEVConstant>(IdxExpr->getOperand(0)) || 1736 !isa<SCEVConstant>(IdxExpr->getOperand(1))) 1737 return UnknownValue; 1738 1739 unsigned MaxSteps = MaxBruteForceIterations; 1740 for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) { 1741 ConstantInt *ItCst = 1742 ConstantInt::get(IdxExpr->getType(), IterationNum); 1743 ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst); 1744 1745 // Form the GEP offset. 1746 Indexes[VarIdxNum] = Val; 1747 1748 Constant *Result = GetAddressedElementFromGlobal(GV, Indexes); 1749 if (Result == 0) break; // Cannot compute! 1750 1751 // Evaluate the condition for this iteration. 1752 Result = ConstantExpr::getICmp(predicate, Result, RHS); 1753 if (!isa<ConstantInt>(Result)) break; // Couldn't decide for sure 1754 if (cast<ConstantInt>(Result)->getValue().isMinValue()) { 1755#if 0 1756 cerr << "\n***\n*** Computed loop count " << *ItCst 1757 << "\n*** From global " << *GV << "*** BB: " << *L->getHeader() 1758 << "***\n"; 1759#endif 1760 ++NumArrayLenItCounts; 1761 return SCEVConstant::get(ItCst); // Found terminating iteration! 1762 } 1763 } 1764 return UnknownValue; 1765} 1766 1767 1768/// CanConstantFold - Return true if we can constant fold an instruction of the 1769/// specified type, assuming that all operands were constants. 1770static bool CanConstantFold(const Instruction *I) { 1771 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) || 1772 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I)) 1773 return true; 1774 1775 if (const CallInst *CI = dyn_cast<CallInst>(I)) 1776 if (const Function *F = CI->getCalledFunction()) 1777 return canConstantFoldCallTo((Function*)F); // FIXME: elim cast 1778 return false; 1779} 1780 1781/// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node 1782/// in the loop that V is derived from. We allow arbitrary operations along the 1783/// way, but the operands of an operation must either be constants or a value 1784/// derived from a constant PHI. If this expression does not fit with these 1785/// constraints, return null. 1786static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { 1787 // If this is not an instruction, or if this is an instruction outside of the 1788 // loop, it can't be derived from a loop PHI. 1789 Instruction *I = dyn_cast<Instruction>(V); 1790 if (I == 0 || !L->contains(I->getParent())) return 0; 1791 1792 if (PHINode *PN = dyn_cast<PHINode>(I)) 1793 if (L->getHeader() == I->getParent()) 1794 return PN; 1795 else 1796 // We don't currently keep track of the control flow needed to evaluate 1797 // PHIs, so we cannot handle PHIs inside of loops. 1798 return 0; 1799 1800 // If we won't be able to constant fold this expression even if the operands 1801 // are constants, return early. 1802 if (!CanConstantFold(I)) return 0; 1803 1804 // Otherwise, we can evaluate this instruction if all of its operands are 1805 // constant or derived from a PHI node themselves. 1806 PHINode *PHI = 0; 1807 for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op) 1808 if (!(isa<Constant>(I->getOperand(Op)) || 1809 isa<GlobalValue>(I->getOperand(Op)))) { 1810 PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L); 1811 if (P == 0) return 0; // Not evolving from PHI 1812 if (PHI == 0) 1813 PHI = P; 1814 else if (PHI != P) 1815 return 0; // Evolving from multiple different PHIs. 1816 } 1817 1818 // This is a expression evolving from a constant PHI! 1819 return PHI; 1820} 1821 1822/// EvaluateExpression - Given an expression that passes the 1823/// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node 1824/// in the loop has the value PHIVal. If we can't fold this expression for some 1825/// reason, return null. 1826static Constant *EvaluateExpression(Value *V, Constant *PHIVal) { 1827 if (isa<PHINode>(V)) return PHIVal; 1828 if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) 1829 return GV; 1830 if (Constant *C = dyn_cast<Constant>(V)) return C; 1831 Instruction *I = cast<Instruction>(V); 1832 1833 std::vector<Constant*> Operands; 1834 Operands.resize(I->getNumOperands()); 1835 1836 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 1837 Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal); 1838 if (Operands[i] == 0) return 0; 1839 } 1840 1841 return ConstantFoldInstOperands(I, &Operands[0], Operands.size()); 1842} 1843 1844/// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 1845/// in the header of its containing loop, we know the loop executes a 1846/// constant number of times, and the PHI node is just a recurrence 1847/// involving constants, fold it. 1848Constant *ScalarEvolutionsImpl:: 1849getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its, const Loop *L){ 1850 std::map<PHINode*, Constant*>::iterator I = 1851 ConstantEvolutionLoopExitValue.find(PN); 1852 if (I != ConstantEvolutionLoopExitValue.end()) 1853 return I->second; 1854 1855 if (Its.ugt(APInt(Its.getBitWidth(),MaxBruteForceIterations))) 1856 return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it. 1857 1858 Constant *&RetVal = ConstantEvolutionLoopExitValue[PN]; 1859 1860 // Since the loop is canonicalized, the PHI node must have two entries. One 1861 // entry must be a constant (coming in from outside of the loop), and the 1862 // second must be derived from the same PHI. 1863 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); 1864 Constant *StartCST = 1865 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge)); 1866 if (StartCST == 0) 1867 return RetVal = 0; // Must be a constant. 1868 1869 Value *BEValue = PN->getIncomingValue(SecondIsBackedge); 1870 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); 1871 if (PN2 != PN) 1872 return RetVal = 0; // Not derived from same PHI. 1873 1874 // Execute the loop symbolically to determine the exit value. 1875 if (Its.getActiveBits() >= 32) 1876 return RetVal = 0; // More than 2^32-1 iterations?? Not doing it! 1877 1878 unsigned NumIterations = Its.getZExtValue(); // must be in range 1879 unsigned IterationNum = 0; 1880 for (Constant *PHIVal = StartCST; ; ++IterationNum) { 1881 if (IterationNum == NumIterations) 1882 return RetVal = PHIVal; // Got exit value! 1883 1884 // Compute the value of the PHI node for the next iteration. 1885 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal); 1886 if (NextPHI == PHIVal) 1887 return RetVal = NextPHI; // Stopped evolving! 1888 if (NextPHI == 0) 1889 return 0; // Couldn't evaluate! 1890 PHIVal = NextPHI; 1891 } 1892} 1893 1894/// ComputeIterationCountExhaustively - If the trip is known to execute a 1895/// constant number of times (the condition evolves only from constants), 1896/// try to evaluate a few iterations of the loop until we get the exit 1897/// condition gets a value of ExitWhen (true or false). If we cannot 1898/// evaluate the trip count of the loop, return UnknownValue. 1899SCEVHandle ScalarEvolutionsImpl:: 1900ComputeIterationCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) { 1901 PHINode *PN = getConstantEvolvingPHI(Cond, L); 1902 if (PN == 0) return UnknownValue; 1903 1904 // Since the loop is canonicalized, the PHI node must have two entries. One 1905 // entry must be a constant (coming in from outside of the loop), and the 1906 // second must be derived from the same PHI. 1907 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); 1908 Constant *StartCST = 1909 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge)); 1910 if (StartCST == 0) return UnknownValue; // Must be a constant. 1911 1912 Value *BEValue = PN->getIncomingValue(SecondIsBackedge); 1913 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); 1914 if (PN2 != PN) return UnknownValue; // Not derived from same PHI. 1915 1916 // Okay, we find a PHI node that defines the trip count of this loop. Execute 1917 // the loop symbolically to determine when the condition gets a value of 1918 // "ExitWhen". 1919 unsigned IterationNum = 0; 1920 unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis. 1921 for (Constant *PHIVal = StartCST; 1922 IterationNum != MaxIterations; ++IterationNum) { 1923 ConstantInt *CondVal = 1924 dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal)); 1925 1926 // Couldn't symbolically evaluate. 1927 if (!CondVal) return UnknownValue; 1928 1929 if (CondVal->getValue() == uint64_t(ExitWhen)) { 1930 ConstantEvolutionLoopExitValue[PN] = PHIVal; 1931 ++NumBruteForceTripCountsComputed; 1932 return SCEVConstant::get(ConstantInt::get(Type::Int32Ty, IterationNum)); 1933 } 1934 1935 // Compute the value of the PHI node for the next iteration. 1936 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal); 1937 if (NextPHI == 0 || NextPHI == PHIVal) 1938 return UnknownValue; // Couldn't evaluate or not making progress... 1939 PHIVal = NextPHI; 1940 } 1941 1942 // Too many iterations were needed to evaluate. 1943 return UnknownValue; 1944} 1945 1946/// getSCEVAtScope - Compute the value of the specified expression within the 1947/// indicated loop (which may be null to indicate in no loop). If the 1948/// expression cannot be evaluated, return UnknownValue. 1949SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { 1950 // FIXME: this should be turned into a virtual method on SCEV! 1951 1952 if (isa<SCEVConstant>(V)) return V; 1953 1954 // If this instruction is evolves from a constant-evolving PHI, compute the 1955 // exit value from the loop without using SCEVs. 1956 if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) { 1957 if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) { 1958 const Loop *LI = this->LI[I->getParent()]; 1959 if (LI && LI->getParentLoop() == L) // Looking for loop exit value. 1960 if (PHINode *PN = dyn_cast<PHINode>(I)) 1961 if (PN->getParent() == LI->getHeader()) { 1962 // Okay, there is no closed form solution for the PHI node. Check 1963 // to see if the loop that contains it has a known iteration count. 1964 // If so, we may be able to force computation of the exit value. 1965 SCEVHandle IterationCount = getIterationCount(LI); 1966 if (SCEVConstant *ICC = dyn_cast<SCEVConstant>(IterationCount)) { 1967 // Okay, we know how many times the containing loop executes. If 1968 // this is a constant evolving PHI node, get the final value at 1969 // the specified iteration number. 1970 Constant *RV = getConstantEvolutionLoopExitValue(PN, 1971 ICC->getValue()->getValue(), 1972 LI); 1973 if (RV) return SCEVUnknown::get(RV); 1974 } 1975 } 1976 1977 // Okay, this is an expression that we cannot symbolically evaluate 1978 // into a SCEV. Check to see if it's possible to symbolically evaluate 1979 // the arguments into constants, and if so, try to constant propagate the 1980 // result. This is particularly useful for computing loop exit values. 1981 if (CanConstantFold(I)) { 1982 std::vector<Constant*> Operands; 1983 Operands.reserve(I->getNumOperands()); 1984 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 1985 Value *Op = I->getOperand(i); 1986 if (Constant *C = dyn_cast<Constant>(Op)) { 1987 Operands.push_back(C); 1988 } else { 1989 SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L); 1990 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) 1991 Operands.push_back(ConstantExpr::getIntegerCast(SC->getValue(), 1992 Op->getType(), 1993 false)); 1994 else if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) { 1995 if (Constant *C = dyn_cast<Constant>(SU->getValue())) 1996 Operands.push_back(ConstantExpr::getIntegerCast(C, 1997 Op->getType(), 1998 false)); 1999 else 2000 return V; 2001 } else { 2002 return V; 2003 } 2004 } 2005 } 2006 Constant *C =ConstantFoldInstOperands(I, &Operands[0], Operands.size()); 2007 return SCEVUnknown::get(C); 2008 } 2009 } 2010 2011 // This is some other type of SCEVUnknown, just return it. 2012 return V; 2013 } 2014 2015 if (SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) { 2016 // Avoid performing the look-up in the common case where the specified 2017 // expression has no loop-variant portions. 2018 for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) { 2019 SCEVHandle OpAtScope = getSCEVAtScope(Comm->getOperand(i), L); 2020 if (OpAtScope != Comm->getOperand(i)) { 2021 if (OpAtScope == UnknownValue) return UnknownValue; 2022 // Okay, at least one of these operands is loop variant but might be 2023 // foldable. Build a new instance of the folded commutative expression. 2024 std::vector<SCEVHandle> NewOps(Comm->op_begin(), Comm->op_begin()+i); 2025 NewOps.push_back(OpAtScope); 2026 2027 for (++i; i != e; ++i) { 2028 OpAtScope = getSCEVAtScope(Comm->getOperand(i), L); 2029 if (OpAtScope == UnknownValue) return UnknownValue; 2030 NewOps.push_back(OpAtScope); 2031 } 2032 if (isa<SCEVAddExpr>(Comm)) 2033 return SCEVAddExpr::get(NewOps); 2034 assert(isa<SCEVMulExpr>(Comm) && "Only know about add and mul!"); 2035 return SCEVMulExpr::get(NewOps); 2036 } 2037 } 2038 // If we got here, all operands are loop invariant. 2039 return Comm; 2040 } 2041 2042 if (SCEVSDivExpr *Div = dyn_cast<SCEVSDivExpr>(V)) { 2043 SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L); 2044 if (LHS == UnknownValue) return LHS; 2045 SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L); 2046 if (RHS == UnknownValue) return RHS; 2047 if (LHS == Div->getLHS() && RHS == Div->getRHS()) 2048 return Div; // must be loop invariant 2049 return SCEVSDivExpr::get(LHS, RHS); 2050 } 2051 2052 // If this is a loop recurrence for a loop that does not contain L, then we 2053 // are dealing with the final value computed by the loop. 2054 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) { 2055 if (!L || !AddRec->getLoop()->contains(L->getHeader())) { 2056 // To evaluate this recurrence, we need to know how many times the AddRec 2057 // loop iterates. Compute this now. 2058 SCEVHandle IterationCount = getIterationCount(AddRec->getLoop()); 2059 if (IterationCount == UnknownValue) return UnknownValue; 2060 IterationCount = getTruncateOrZeroExtend(IterationCount, 2061 AddRec->getType()); 2062 2063 // If the value is affine, simplify the expression evaluation to just 2064 // Start + Step*IterationCount. 2065 if (AddRec->isAffine()) 2066 return SCEVAddExpr::get(AddRec->getStart(), 2067 SCEVMulExpr::get(IterationCount, 2068 AddRec->getOperand(1))); 2069 2070 // Otherwise, evaluate it the hard way. 2071 return AddRec->evaluateAtIteration(IterationCount); 2072 } 2073 return UnknownValue; 2074 } 2075 2076 //assert(0 && "Unknown SCEV type!"); 2077 return UnknownValue; 2078} 2079 2080 2081/// SolveQuadraticEquation - Find the roots of the quadratic equation for the 2082/// given quadratic chrec {L,+,M,+,N}. This returns either the two roots (which 2083/// might be the same) or two SCEVCouldNotCompute objects. 2084/// 2085static std::pair<SCEVHandle,SCEVHandle> 2086SolveQuadraticEquation(const SCEVAddRecExpr *AddRec) { 2087 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!"); 2088 SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0)); 2089 SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1)); 2090 SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2)); 2091 2092 // We currently can only solve this if the coefficients are constants. 2093 if (!LC || !MC || !NC) { 2094 SCEV *CNC = new SCEVCouldNotCompute(); 2095 return std::make_pair(CNC, CNC); 2096 } 2097 2098 uint32_t BitWidth = LC->getValue()->getValue().getBitWidth(); 2099 const APInt& L = LC->getValue()->getValue(); 2100 const APInt& M = MC->getValue()->getValue(); 2101 const APInt& N = MC->getValue()->getValue(); 2102 APInt Two(BitWidth, 2); 2103 APInt Four(BitWidth, 4); 2104 2105 { 2106 using namespace APIntOps; 2107 const APInt& C = L; 2108 // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C 2109 // The B coefficient is M-N/2 2110 APInt B(M); 2111 B -= sdiv(N,Two); 2112 2113 // The A coefficient is N/2 2114 APInt A(N.sdiv(Two)); 2115 2116 // Compute the B^2-4ac term. 2117 APInt SqrtTerm(B); 2118 SqrtTerm *= B; 2119 SqrtTerm -= Four * (A * C); 2120 2121 // Compute sqrt(B^2-4ac). This is guaranteed to be the nearest 2122 // integer value or else APInt::sqrt() will assert. 2123 APInt SqrtVal(SqrtTerm.sqrt()); 2124 2125 // Compute the two solutions for the quadratic formula. 2126 // The divisions must be performed as signed divisions. 2127 APInt NegB(-B); 2128 APInt TwoA( A * Two ); 2129 ConstantInt *Solution1 = ConstantInt::get((NegB + SqrtVal).sdiv(TwoA)); 2130 ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA)); 2131 2132 return std::make_pair(SCEVUnknown::get(Solution1), 2133 SCEVUnknown::get(Solution2)); 2134 } // end APIntOps namespace 2135} 2136 2137/// HowFarToZero - Return the number of times a backedge comparing the specified 2138/// value to zero will execute. If not computable, return UnknownValue 2139SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) { 2140 // If the value is a constant 2141 if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) { 2142 // If the value is already zero, the branch will execute zero times. 2143 if (C->getValue()->isZero()) return C; 2144 return UnknownValue; // Otherwise it will loop infinitely. 2145 } 2146 2147 SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V); 2148 if (!AddRec || AddRec->getLoop() != L) 2149 return UnknownValue; 2150 2151 if (AddRec->isAffine()) { 2152 // If this is an affine expression the execution count of this branch is 2153 // equal to: 2154 // 2155 // (0 - Start/Step) iff Start % Step == 0 2156 // 2157 // Get the initial value for the loop. 2158 SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop()); 2159 if (isa<SCEVCouldNotCompute>(Start)) return UnknownValue; 2160 SCEVHandle Step = AddRec->getOperand(1); 2161 2162 Step = getSCEVAtScope(Step, L->getParentLoop()); 2163 2164 // Figure out if Start % Step == 0. 2165 // FIXME: We should add DivExpr and RemExpr operations to our AST. 2166 if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) { 2167 if (StepC->getValue()->equalsInt(1)) // N % 1 == 0 2168 return SCEV::getNegativeSCEV(Start); // 0 - Start/1 == -Start 2169 if (StepC->getValue()->isAllOnesValue()) // N % -1 == 0 2170 return Start; // 0 - Start/-1 == Start 2171 2172 // Check to see if Start is divisible by SC with no remainder. 2173 if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) { 2174 ConstantInt *StartCC = StartC->getValue(); 2175 Constant *StartNegC = ConstantExpr::getNeg(StartCC); 2176 Constant *Rem = ConstantExpr::getSRem(StartNegC, StepC->getValue()); 2177 if (Rem->isNullValue()) { 2178 Constant *Result =ConstantExpr::getSDiv(StartNegC,StepC->getValue()); 2179 return SCEVUnknown::get(Result); 2180 } 2181 } 2182 } 2183 } else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) { 2184 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of 2185 // the quadratic equation to solve it. 2186 std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec); 2187 SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first); 2188 SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second); 2189 if (R1) { 2190#if 0 2191 cerr << "HFTZ: " << *V << " - sol#1: " << *R1 2192 << " sol#2: " << *R2 << "\n"; 2193#endif 2194 // Pick the smallest positive root value. 2195 if (ConstantInt *CB = 2196 dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, 2197 R1->getValue(), R2->getValue()))) { 2198 if (CB->getZExtValue() == false) 2199 std::swap(R1, R2); // R1 is the minimum root now. 2200 2201 // We can only use this value if the chrec ends up with an exact zero 2202 // value at this index. When solving for "X*X != 5", for example, we 2203 // should not accept a root of 2. 2204 SCEVHandle Val = AddRec->evaluateAtIteration(R1); 2205 if (SCEVConstant *EvalVal = dyn_cast<SCEVConstant>(Val)) 2206 if (EvalVal->getValue()->isZero()) 2207 return R1; // We found a quadratic root! 2208 } 2209 } 2210 } 2211 2212 return UnknownValue; 2213} 2214 2215/// HowFarToNonZero - Return the number of times a backedge checking the 2216/// specified value for nonzero will execute. If not computable, return 2217/// UnknownValue 2218SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) { 2219 // Loops that look like: while (X == 0) are very strange indeed. We don't 2220 // handle them yet except for the trivial case. This could be expanded in the 2221 // future as needed. 2222 2223 // If the value is a constant, check to see if it is known to be non-zero 2224 // already. If so, the backedge will execute zero times. 2225 if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) { 2226 Constant *Zero = Constant::getNullValue(C->getValue()->getType()); 2227 Constant *NonZero = 2228 ConstantExpr::getICmp(ICmpInst::ICMP_NE, C->getValue(), Zero); 2229 if (NonZero == ConstantInt::getTrue()) 2230 return getSCEV(Zero); 2231 return UnknownValue; // Otherwise it will loop infinitely. 2232 } 2233 2234 // We could implement others, but I really doubt anyone writes loops like 2235 // this, and if they did, they would already be constant folded. 2236 return UnknownValue; 2237} 2238 2239/// HowManyLessThans - Return the number of times a backedge containing the 2240/// specified less-than comparison will execute. If not computable, return 2241/// UnknownValue. 2242SCEVHandle ScalarEvolutionsImpl:: 2243HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L) { 2244 // Only handle: "ADDREC < LoopInvariant". 2245 if (!RHS->isLoopInvariant(L)) return UnknownValue; 2246 2247 SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS); 2248 if (!AddRec || AddRec->getLoop() != L) 2249 return UnknownValue; 2250 2251 if (AddRec->isAffine()) { 2252 // FORNOW: We only support unit strides. 2253 SCEVHandle One = SCEVUnknown::getIntegerSCEV(1, RHS->getType()); 2254 if (AddRec->getOperand(1) != One) 2255 return UnknownValue; 2256 2257 // The number of iterations for "[n,+,1] < m", is m-n. However, we don't 2258 // know that m is >= n on input to the loop. If it is, the condition return 2259 // true zero times. What we really should return, for full generality, is 2260 // SMAX(0, m-n). Since we cannot check this, we will instead check for a 2261 // canonical loop form: most do-loops will have a check that dominates the 2262 // loop, that only enters the loop if [n-1]<m. If we can find this check, 2263 // we know that the SMAX will evaluate to m-n, because we know that m >= n. 2264 2265 // Search for the check. 2266 BasicBlock *Preheader = L->getLoopPreheader(); 2267 BasicBlock *PreheaderDest = L->getHeader(); 2268 if (Preheader == 0) return UnknownValue; 2269 2270 BranchInst *LoopEntryPredicate = 2271 dyn_cast<BranchInst>(Preheader->getTerminator()); 2272 if (!LoopEntryPredicate) return UnknownValue; 2273 2274 // This might be a critical edge broken out. If the loop preheader ends in 2275 // an unconditional branch to the loop, check to see if the preheader has a 2276 // single predecessor, and if so, look for its terminator. 2277 while (LoopEntryPredicate->isUnconditional()) { 2278 PreheaderDest = Preheader; 2279 Preheader = Preheader->getSinglePredecessor(); 2280 if (!Preheader) return UnknownValue; // Multiple preds. 2281 2282 LoopEntryPredicate = 2283 dyn_cast<BranchInst>(Preheader->getTerminator()); 2284 if (!LoopEntryPredicate) return UnknownValue; 2285 } 2286 2287 // Now that we found a conditional branch that dominates the loop, check to 2288 // see if it is the comparison we are looking for. 2289 if (ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition())){ 2290 Value *PreCondLHS = ICI->getOperand(0); 2291 Value *PreCondRHS = ICI->getOperand(1); 2292 ICmpInst::Predicate Cond; 2293 if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest) 2294 Cond = ICI->getPredicate(); 2295 else 2296 Cond = ICI->getInversePredicate(); 2297 2298 switch (Cond) { 2299 case ICmpInst::ICMP_UGT: 2300 std::swap(PreCondLHS, PreCondRHS); 2301 Cond = ICmpInst::ICMP_ULT; 2302 break; 2303 case ICmpInst::ICMP_SGT: 2304 std::swap(PreCondLHS, PreCondRHS); 2305 Cond = ICmpInst::ICMP_SLT; 2306 break; 2307 default: break; 2308 } 2309 2310 if (Cond == ICmpInst::ICMP_SLT) { 2311 if (PreCondLHS->getType()->isInteger()) { 2312 if (RHS != getSCEV(PreCondRHS)) 2313 return UnknownValue; // Not a comparison against 'm'. 2314 2315 if (SCEV::getMinusSCEV(AddRec->getOperand(0), One) 2316 != getSCEV(PreCondLHS)) 2317 return UnknownValue; // Not a comparison against 'n-1'. 2318 } 2319 else return UnknownValue; 2320 } else if (Cond == ICmpInst::ICMP_ULT) 2321 return UnknownValue; 2322 2323 // cerr << "Computed Loop Trip Count as: " 2324 // << // *SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)) << "\n"; 2325 return SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)); 2326 } 2327 else 2328 return UnknownValue; 2329 } 2330 2331 return UnknownValue; 2332} 2333 2334/// getNumIterationsInRange - Return the number of iterations of this loop that 2335/// produce values in the specified constant range. Another way of looking at 2336/// this is that it returns the first iteration number where the value is not in 2337/// the condition, thus computing the exit count. If the iteration count can't 2338/// be computed, an instance of SCEVCouldNotCompute is returned. 2339SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, 2340 bool isSigned) const { 2341 if (Range.isFullSet()) // Infinite loop. 2342 return new SCEVCouldNotCompute(); 2343 2344 // If the start is a non-zero constant, shift the range to simplify things. 2345 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart())) 2346 if (!SC->getValue()->isZero()) { 2347 std::vector<SCEVHandle> Operands(op_begin(), op_end()); 2348 Operands[0] = SCEVUnknown::getIntegerSCEV(0, SC->getType()); 2349 SCEVHandle Shifted = SCEVAddRecExpr::get(Operands, getLoop()); 2350 if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted)) 2351 return ShiftedAddRec->getNumIterationsInRange( 2352 Range.subtract(SC->getValue()->getValue()),isSigned); 2353 // This is strange and shouldn't happen. 2354 return new SCEVCouldNotCompute(); 2355 } 2356 2357 // The only time we can solve this is when we have all constant indices. 2358 // Otherwise, we cannot determine the overflow conditions. 2359 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 2360 if (!isa<SCEVConstant>(getOperand(i))) 2361 return new SCEVCouldNotCompute(); 2362 2363 2364 // Okay at this point we know that all elements of the chrec are constants and 2365 // that the start element is zero. 2366 2367 // First check to see if the range contains zero. If not, the first 2368 // iteration exits. 2369 if (!Range.contains(APInt(getBitWidth(),0))) 2370 return SCEVConstant::get(ConstantInt::get(getType(),0)); 2371 2372 if (isAffine()) { 2373 // If this is an affine expression then we have this situation: 2374 // Solve {0,+,A} in Range === Ax in Range 2375 2376 // Since we know that zero is in the range, we know that the upper value of 2377 // the range must be the first possible exit value. Also note that we 2378 // already checked for a full range. 2379 const APInt &Upper = Range.getUpper(); 2380 APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue(); 2381 APInt One(getBitWidth(),1); 2382 2383 // The exit value should be (Upper+A-1)/A. 2384 APInt ExitVal(Upper); 2385 if (A != One) 2386 ExitVal = (Upper + A - One).sdiv(A); 2387 ConstantInt *ExitValue = ConstantInt::get(ExitVal); 2388 2389 // Evaluate at the exit value. If we really did fall out of the valid 2390 // range, then we computed our trip count, otherwise wrap around or other 2391 // things must have happened. 2392 ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue); 2393 if (Range.contains(Val->getValue())) 2394 return new SCEVCouldNotCompute(); // Something strange happened 2395 2396 // Ensure that the previous value is in the range. This is a sanity check. 2397 assert(Range.contains( 2398 EvaluateConstantChrecAtConstant(this, 2399 ConstantInt::get(ExitVal - One))->getValue()) && 2400 "Linear scev computation is off in a bad way!"); 2401 return SCEVConstant::get(cast<ConstantInt>(ExitValue)); 2402 } else if (isQuadratic()) { 2403 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the 2404 // quadratic equation to solve it. To do this, we must frame our problem in 2405 // terms of figuring out when zero is crossed, instead of when 2406 // Range.getUpper() is crossed. 2407 std::vector<SCEVHandle> NewOps(op_begin(), op_end()); 2408 NewOps[0] = SCEV::getNegativeSCEV(SCEVUnknown::get( 2409 ConstantInt::get(Range.getUpper()))); 2410 SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, getLoop()); 2411 2412 // Next, solve the constructed addrec 2413 std::pair<SCEVHandle,SCEVHandle> Roots = 2414 SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec)); 2415 SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first); 2416 SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second); 2417 if (R1) { 2418 // Pick the smallest positive root value. 2419 if (ConstantInt *CB = 2420 dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, 2421 R1->getValue(), R2->getValue()))) { 2422 if (CB->getZExtValue() == false) 2423 std::swap(R1, R2); // R1 is the minimum root now. 2424 2425 // Make sure the root is not off by one. The returned iteration should 2426 // not be in the range, but the previous one should be. When solving 2427 // for "X*X < 5", for example, we should not return a root of 2. 2428 ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this, 2429 R1->getValue()); 2430 if (Range.contains(R1Val->getValue())) { 2431 // The next iteration must be out of the range... 2432 Constant *NextVal = ConstantInt::get(R1->getValue()->getValue()+1); 2433 2434 R1Val = EvaluateConstantChrecAtConstant(this, NextVal); 2435 if (!Range.contains(R1Val->getValue())) 2436 return SCEVUnknown::get(NextVal); 2437 return new SCEVCouldNotCompute(); // Something strange happened 2438 } 2439 2440 // If R1 was not in the range, then it is a good return value. Make 2441 // sure that R1-1 WAS in the range though, just in case. 2442 Constant *NextVal = ConstantInt::get(R1->getValue()->getValue()-1); 2443 R1Val = EvaluateConstantChrecAtConstant(this, NextVal); 2444 if (Range.contains(R1Val->getValue())) 2445 return R1; 2446 return new SCEVCouldNotCompute(); // Something strange happened 2447 } 2448 } 2449 } 2450 2451 // Fallback, if this is a general polynomial, figure out the progression 2452 // through brute force: evaluate until we find an iteration that fails the 2453 // test. This is likely to be slow, but getting an accurate trip count is 2454 // incredibly important, we will be able to simplify the exit test a lot, and 2455 // we are almost guaranteed to get a trip count in this case. 2456 ConstantInt *TestVal = ConstantInt::get(getType(), 0); 2457 ConstantInt *EndVal = TestVal; // Stop when we wrap around. 2458 do { 2459 ++NumBruteForceEvaluations; 2460 SCEVHandle Val = evaluateAtIteration(SCEVConstant::get(TestVal)); 2461 if (!isa<SCEVConstant>(Val)) // This shouldn't happen. 2462 return new SCEVCouldNotCompute(); 2463 2464 // Check to see if we found the value! 2465 if (!Range.contains(cast<SCEVConstant>(Val)->getValue()->getValue())) 2466 return SCEVConstant::get(TestVal); 2467 2468 // Increment to test the next index. 2469 TestVal = ConstantInt::get(TestVal->getValue()+1); 2470 } while (TestVal != EndVal); 2471 2472 return new SCEVCouldNotCompute(); 2473} 2474 2475 2476 2477//===----------------------------------------------------------------------===// 2478// ScalarEvolution Class Implementation 2479//===----------------------------------------------------------------------===// 2480 2481bool ScalarEvolution::runOnFunction(Function &F) { 2482 Impl = new ScalarEvolutionsImpl(F, getAnalysis<LoopInfo>()); 2483 return false; 2484} 2485 2486void ScalarEvolution::releaseMemory() { 2487 delete (ScalarEvolutionsImpl*)Impl; 2488 Impl = 0; 2489} 2490 2491void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const { 2492 AU.setPreservesAll(); 2493 AU.addRequiredTransitive<LoopInfo>(); 2494} 2495 2496SCEVHandle ScalarEvolution::getSCEV(Value *V) const { 2497 return ((ScalarEvolutionsImpl*)Impl)->getSCEV(V); 2498} 2499 2500/// hasSCEV - Return true if the SCEV for this value has already been 2501/// computed. 2502bool ScalarEvolution::hasSCEV(Value *V) const { 2503 return ((ScalarEvolutionsImpl*)Impl)->hasSCEV(V); 2504} 2505 2506 2507/// setSCEV - Insert the specified SCEV into the map of current SCEVs for 2508/// the specified value. 2509void ScalarEvolution::setSCEV(Value *V, const SCEVHandle &H) { 2510 ((ScalarEvolutionsImpl*)Impl)->setSCEV(V, H); 2511} 2512 2513 2514SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const { 2515 return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L); 2516} 2517 2518bool ScalarEvolution::hasLoopInvariantIterationCount(const Loop *L) const { 2519 return !isa<SCEVCouldNotCompute>(getIterationCount(L)); 2520} 2521 2522SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) const { 2523 return ((ScalarEvolutionsImpl*)Impl)->getSCEVAtScope(getSCEV(V), L); 2524} 2525 2526void ScalarEvolution::deleteInstructionFromRecords(Instruction *I) const { 2527 return ((ScalarEvolutionsImpl*)Impl)->deleteInstructionFromRecords(I); 2528} 2529 2530static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE, 2531 const Loop *L) { 2532 // Print all inner loops first 2533 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 2534 PrintLoopInfo(OS, SE, *I); 2535 2536 cerr << "Loop " << L->getHeader()->getName() << ": "; 2537 2538 std::vector<BasicBlock*> ExitBlocks; 2539 L->getExitBlocks(ExitBlocks); 2540 if (ExitBlocks.size() != 1) 2541 cerr << "<multiple exits> "; 2542 2543 if (SE->hasLoopInvariantIterationCount(L)) { 2544 cerr << *SE->getIterationCount(L) << " iterations! "; 2545 } else { 2546 cerr << "Unpredictable iteration count. "; 2547 } 2548 2549 cerr << "\n"; 2550} 2551 2552void ScalarEvolution::print(std::ostream &OS, const Module* ) const { 2553 Function &F = ((ScalarEvolutionsImpl*)Impl)->F; 2554 LoopInfo &LI = ((ScalarEvolutionsImpl*)Impl)->LI; 2555 2556 OS << "Classifying expressions for: " << F.getName() << "\n"; 2557 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 2558 if (I->getType()->isInteger()) { 2559 OS << *I; 2560 OS << " --> "; 2561 SCEVHandle SV = getSCEV(&*I); 2562 SV->print(OS); 2563 OS << "\t\t"; 2564 2565 if ((*I).getType()->isInteger()) { 2566 ConstantRange Bounds = SV->getValueRange(); 2567 if (!Bounds.isFullSet()) 2568 OS << "Bounds: " << Bounds << " "; 2569 } 2570 2571 if (const Loop *L = LI.getLoopFor((*I).getParent())) { 2572 OS << "Exits: "; 2573 SCEVHandle ExitValue = getSCEVAtScope(&*I, L->getParentLoop()); 2574 if (isa<SCEVCouldNotCompute>(ExitValue)) { 2575 OS << "<<Unknown>>"; 2576 } else { 2577 OS << *ExitValue; 2578 } 2579 } 2580 2581 2582 OS << "\n"; 2583 } 2584 2585 OS << "Determining loop execution counts for: " << F.getName() << "\n"; 2586 for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I) 2587 PrintLoopInfo(OS, this, *I); 2588} 2589 2590