ScalarEvolution.cpp revision 0bac95e2e2044b574f3aea14a3fdb31c1b95240f
1//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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/Dominators.h" 70#include "llvm/Analysis/LoopInfo.h" 71#include "llvm/Assembly/Writer.h" 72#include "llvm/Target/TargetData.h" 73#include "llvm/Support/CommandLine.h" 74#include "llvm/Support/Compiler.h" 75#include "llvm/Support/ConstantRange.h" 76#include "llvm/Support/GetElementPtrTypeIterator.h" 77#include "llvm/Support/InstIterator.h" 78#include "llvm/Support/ManagedStatic.h" 79#include "llvm/Support/MathExtras.h" 80#include "llvm/Support/raw_ostream.h" 81#include "llvm/ADT/Statistic.h" 82#include "llvm/ADT/STLExtras.h" 83#include <ostream> 84#include <algorithm> 85using namespace llvm; 86 87STATISTIC(NumArrayLenItCounts, 88 "Number of trip counts computed with array length"); 89STATISTIC(NumTripCountsComputed, 90 "Number of loops with predictable loop counts"); 91STATISTIC(NumTripCountsNotComputed, 92 "Number of loops without predictable loop counts"); 93STATISTIC(NumBruteForceTripCountsComputed, 94 "Number of loops with trip counts computed by force"); 95 96static cl::opt<unsigned> 97MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, 98 cl::desc("Maximum number of iterations SCEV will " 99 "symbolically execute a constant derived loop"), 100 cl::init(100)); 101 102static RegisterPass<ScalarEvolution> 103R("scalar-evolution", "Scalar Evolution Analysis", false, true); 104char ScalarEvolution::ID = 0; 105 106//===----------------------------------------------------------------------===// 107// SCEV class definitions 108//===----------------------------------------------------------------------===// 109 110//===----------------------------------------------------------------------===// 111// Implementation of the SCEV class. 112// 113SCEV::~SCEV() {} 114void SCEV::dump() const { 115 print(errs()); 116 errs() << '\n'; 117} 118 119void SCEV::print(std::ostream &o) const { 120 raw_os_ostream OS(o); 121 print(OS); 122} 123 124bool SCEV::isZero() const { 125 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this)) 126 return SC->getValue()->isZero(); 127 return false; 128} 129 130bool SCEV::isOne() const { 131 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this)) 132 return SC->getValue()->isOne(); 133 return false; 134} 135 136SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {} 137SCEVCouldNotCompute::~SCEVCouldNotCompute() {} 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, 157 ScalarEvolution &SE) const { 158 return this; 159} 160 161void SCEVCouldNotCompute::print(raw_ostream &OS) const { 162 OS << "***COULDNOTCOMPUTE***"; 163} 164 165bool SCEVCouldNotCompute::classof(const SCEV *S) { 166 return S->getSCEVType() == scCouldNotCompute; 167} 168 169 170// SCEVConstants - Only allow the creation of one SCEVConstant for any 171// particular value. Don't use a SCEVHandle here, or else the object will 172// never be deleted! 173static ManagedStatic<std::map<ConstantInt*, SCEVConstant*> > SCEVConstants; 174 175 176SCEVConstant::~SCEVConstant() { 177 SCEVConstants->erase(V); 178} 179 180SCEVHandle ScalarEvolution::getConstant(ConstantInt *V) { 181 SCEVConstant *&R = (*SCEVConstants)[V]; 182 if (R == 0) R = new SCEVConstant(V); 183 return R; 184} 185 186SCEVHandle ScalarEvolution::getConstant(const APInt& Val) { 187 return getConstant(ConstantInt::get(Val)); 188} 189 190const Type *SCEVConstant::getType() const { return V->getType(); } 191 192void SCEVConstant::print(raw_ostream &OS) const { 193 WriteAsOperand(OS, V, false); 194} 195 196SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy, 197 const SCEVHandle &op, const Type *ty) 198 : SCEV(SCEVTy), Op(op), Ty(ty) {} 199 200SCEVCastExpr::~SCEVCastExpr() {} 201 202bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { 203 return Op->dominates(BB, DT); 204} 205 206// SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any 207// particular input. Don't use a SCEVHandle here, or else the object will 208// never be deleted! 209static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>, 210 SCEVTruncateExpr*> > SCEVTruncates; 211 212SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty) 213 : SCEVCastExpr(scTruncate, op, ty) { 214 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) && 215 (Ty->isInteger() || isa<PointerType>(Ty)) && 216 "Cannot truncate non-integer value!"); 217} 218 219SCEVTruncateExpr::~SCEVTruncateExpr() { 220 SCEVTruncates->erase(std::make_pair(Op, Ty)); 221} 222 223void SCEVTruncateExpr::print(raw_ostream &OS) const { 224 OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; 225} 226 227// SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any 228// particular input. Don't use a SCEVHandle here, or else the object will never 229// be deleted! 230static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>, 231 SCEVZeroExtendExpr*> > SCEVZeroExtends; 232 233SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty) 234 : SCEVCastExpr(scZeroExtend, op, ty) { 235 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) && 236 (Ty->isInteger() || isa<PointerType>(Ty)) && 237 "Cannot zero extend non-integer value!"); 238} 239 240SCEVZeroExtendExpr::~SCEVZeroExtendExpr() { 241 SCEVZeroExtends->erase(std::make_pair(Op, Ty)); 242} 243 244void SCEVZeroExtendExpr::print(raw_ostream &OS) const { 245 OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; 246} 247 248// SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any 249// particular input. Don't use a SCEVHandle here, or else the object will never 250// be deleted! 251static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>, 252 SCEVSignExtendExpr*> > SCEVSignExtends; 253 254SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty) 255 : SCEVCastExpr(scSignExtend, op, ty) { 256 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) && 257 (Ty->isInteger() || isa<PointerType>(Ty)) && 258 "Cannot sign extend non-integer value!"); 259} 260 261SCEVSignExtendExpr::~SCEVSignExtendExpr() { 262 SCEVSignExtends->erase(std::make_pair(Op, Ty)); 263} 264 265void SCEVSignExtendExpr::print(raw_ostream &OS) const { 266 OS << "(sext " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; 267} 268 269// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any 270// particular input. Don't use a SCEVHandle here, or else the object will never 271// be deleted! 272static ManagedStatic<std::map<std::pair<unsigned, std::vector<const SCEV*> >, 273 SCEVCommutativeExpr*> > SCEVCommExprs; 274 275SCEVCommutativeExpr::~SCEVCommutativeExpr() { 276 std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end()); 277 SCEVCommExprs->erase(std::make_pair(getSCEVType(), SCEVOps)); 278} 279 280void SCEVCommutativeExpr::print(raw_ostream &OS) const { 281 assert(Operands.size() > 1 && "This plus expr shouldn't exist!"); 282 const char *OpStr = getOperationStr(); 283 OS << "(" << *Operands[0]; 284 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 285 OS << OpStr << *Operands[i]; 286 OS << ")"; 287} 288 289SCEVHandle SCEVCommutativeExpr:: 290replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 291 const SCEVHandle &Conc, 292 ScalarEvolution &SE) const { 293 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 294 SCEVHandle H = 295 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 296 if (H != getOperand(i)) { 297 std::vector<SCEVHandle> NewOps; 298 NewOps.reserve(getNumOperands()); 299 for (unsigned j = 0; j != i; ++j) 300 NewOps.push_back(getOperand(j)); 301 NewOps.push_back(H); 302 for (++i; i != e; ++i) 303 NewOps.push_back(getOperand(i)-> 304 replaceSymbolicValuesWithConcrete(Sym, Conc, SE)); 305 306 if (isa<SCEVAddExpr>(this)) 307 return SE.getAddExpr(NewOps); 308 else if (isa<SCEVMulExpr>(this)) 309 return SE.getMulExpr(NewOps); 310 else if (isa<SCEVSMaxExpr>(this)) 311 return SE.getSMaxExpr(NewOps); 312 else if (isa<SCEVUMaxExpr>(this)) 313 return SE.getUMaxExpr(NewOps); 314 else 315 assert(0 && "Unknown commutative expr!"); 316 } 317 } 318 return this; 319} 320 321bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { 322 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 323 if (!getOperand(i)->dominates(BB, DT)) 324 return false; 325 } 326 return true; 327} 328 329 330// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular 331// input. Don't use a SCEVHandle here, or else the object will never be 332// deleted! 333static ManagedStatic<std::map<std::pair<const SCEV*, const SCEV*>, 334 SCEVUDivExpr*> > SCEVUDivs; 335 336SCEVUDivExpr::~SCEVUDivExpr() { 337 SCEVUDivs->erase(std::make_pair(LHS, RHS)); 338} 339 340bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { 341 return LHS->dominates(BB, DT) && RHS->dominates(BB, DT); 342} 343 344void SCEVUDivExpr::print(raw_ostream &OS) const { 345 OS << "(" << *LHS << " /u " << *RHS << ")"; 346} 347 348const Type *SCEVUDivExpr::getType() const { 349 return LHS->getType(); 350} 351 352// SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any 353// particular input. Don't use a SCEVHandle here, or else the object will never 354// be deleted! 355static ManagedStatic<std::map<std::pair<const Loop *, 356 std::vector<const SCEV*> >, 357 SCEVAddRecExpr*> > SCEVAddRecExprs; 358 359SCEVAddRecExpr::~SCEVAddRecExpr() { 360 std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end()); 361 SCEVAddRecExprs->erase(std::make_pair(L, SCEVOps)); 362} 363 364SCEVHandle SCEVAddRecExpr:: 365replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 366 const SCEVHandle &Conc, 367 ScalarEvolution &SE) const { 368 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 369 SCEVHandle H = 370 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 371 if (H != getOperand(i)) { 372 std::vector<SCEVHandle> NewOps; 373 NewOps.reserve(getNumOperands()); 374 for (unsigned j = 0; j != i; ++j) 375 NewOps.push_back(getOperand(j)); 376 NewOps.push_back(H); 377 for (++i; i != e; ++i) 378 NewOps.push_back(getOperand(i)-> 379 replaceSymbolicValuesWithConcrete(Sym, Conc, SE)); 380 381 return SE.getAddRecExpr(NewOps, L); 382 } 383 } 384 return this; 385} 386 387 388bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const { 389 // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't 390 // contain L and if the start is invariant. 391 return !QueryLoop->contains(L->getHeader()) && 392 getOperand(0)->isLoopInvariant(QueryLoop); 393} 394 395 396void SCEVAddRecExpr::print(raw_ostream &OS) const { 397 OS << "{" << *Operands[0]; 398 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 399 OS << ",+," << *Operands[i]; 400 OS << "}<" << L->getHeader()->getName() + ">"; 401} 402 403// SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular 404// value. Don't use a SCEVHandle here, or else the object will never be 405// deleted! 406static ManagedStatic<std::map<Value*, SCEVUnknown*> > SCEVUnknowns; 407 408SCEVUnknown::~SCEVUnknown() { SCEVUnknowns->erase(V); } 409 410bool SCEVUnknown::isLoopInvariant(const Loop *L) const { 411 // All non-instruction values are loop invariant. All instructions are loop 412 // invariant if they are not contained in the specified loop. 413 if (Instruction *I = dyn_cast<Instruction>(V)) 414 return !L->contains(I->getParent()); 415 return true; 416} 417 418bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const { 419 if (Instruction *I = dyn_cast<Instruction>(getValue())) 420 return DT->dominates(I->getParent(), BB); 421 return true; 422} 423 424const Type *SCEVUnknown::getType() const { 425 return V->getType(); 426} 427 428void SCEVUnknown::print(raw_ostream &OS) const { 429 WriteAsOperand(OS, V, false); 430} 431 432//===----------------------------------------------------------------------===// 433// SCEV Utilities 434//===----------------------------------------------------------------------===// 435 436namespace { 437 /// SCEVComplexityCompare - Return true if the complexity of the LHS is less 438 /// than the complexity of the RHS. This comparator is used to canonicalize 439 /// expressions. 440 class VISIBILITY_HIDDEN SCEVComplexityCompare { 441 LoopInfo *LI; 442 public: 443 explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {} 444 445 bool operator()(const SCEV *LHS, const SCEV *RHS) const { 446 // Primarily, sort the SCEVs by their getSCEVType(). 447 if (LHS->getSCEVType() != RHS->getSCEVType()) 448 return LHS->getSCEVType() < RHS->getSCEVType(); 449 450 // Aside from the getSCEVType() ordering, the particular ordering 451 // isn't very important except that it's beneficial to be consistent, 452 // so that (a + b) and (b + a) don't end up as different expressions. 453 454 // Sort SCEVUnknown values with some loose heuristics. TODO: This is 455 // not as complete as it could be. 456 if (const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS)) { 457 const SCEVUnknown *RU = cast<SCEVUnknown>(RHS); 458 459 // Compare getValueID values. 460 if (LU->getValue()->getValueID() != RU->getValue()->getValueID()) 461 return LU->getValue()->getValueID() < RU->getValue()->getValueID(); 462 463 // Sort arguments by their position. 464 if (const Argument *LA = dyn_cast<Argument>(LU->getValue())) { 465 const Argument *RA = cast<Argument>(RU->getValue()); 466 return LA->getArgNo() < RA->getArgNo(); 467 } 468 469 // For instructions, compare their loop depth, and their opcode. 470 // This is pretty loose. 471 if (Instruction *LV = dyn_cast<Instruction>(LU->getValue())) { 472 Instruction *RV = cast<Instruction>(RU->getValue()); 473 474 // Compare loop depths. 475 if (LI->getLoopDepth(LV->getParent()) != 476 LI->getLoopDepth(RV->getParent())) 477 return LI->getLoopDepth(LV->getParent()) < 478 LI->getLoopDepth(RV->getParent()); 479 480 // Compare opcodes. 481 if (LV->getOpcode() != RV->getOpcode()) 482 return LV->getOpcode() < RV->getOpcode(); 483 484 // Compare the number of operands. 485 if (LV->getNumOperands() != RV->getNumOperands()) 486 return LV->getNumOperands() < RV->getNumOperands(); 487 } 488 489 return false; 490 } 491 492 // Constant sorting doesn't matter since they'll be folded. 493 if (isa<SCEVConstant>(LHS)) 494 return false; 495 496 // Lexicographically compare n-ary expressions. 497 if (const SCEVNAryExpr *LC = dyn_cast<SCEVNAryExpr>(LHS)) { 498 const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS); 499 for (unsigned i = 0, e = LC->getNumOperands(); i != e; ++i) { 500 if (i >= RC->getNumOperands()) 501 return false; 502 if (operator()(LC->getOperand(i), RC->getOperand(i))) 503 return true; 504 if (operator()(RC->getOperand(i), LC->getOperand(i))) 505 return false; 506 } 507 return LC->getNumOperands() < RC->getNumOperands(); 508 } 509 510 // Lexicographically compare udiv expressions. 511 if (const SCEVUDivExpr *LC = dyn_cast<SCEVUDivExpr>(LHS)) { 512 const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS); 513 if (operator()(LC->getLHS(), RC->getLHS())) 514 return true; 515 if (operator()(RC->getLHS(), LC->getLHS())) 516 return false; 517 if (operator()(LC->getRHS(), RC->getRHS())) 518 return true; 519 if (operator()(RC->getRHS(), LC->getRHS())) 520 return false; 521 return false; 522 } 523 524 // Compare cast expressions by operand. 525 if (const SCEVCastExpr *LC = dyn_cast<SCEVCastExpr>(LHS)) { 526 const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS); 527 return operator()(LC->getOperand(), RC->getOperand()); 528 } 529 530 assert(0 && "Unknown SCEV kind!"); 531 return false; 532 } 533 }; 534} 535 536/// GroupByComplexity - Given a list of SCEV objects, order them by their 537/// complexity, and group objects of the same complexity together by value. 538/// When this routine is finished, we know that any duplicates in the vector are 539/// consecutive and that complexity is monotonically increasing. 540/// 541/// Note that we go take special precautions to ensure that we get determinstic 542/// results from this routine. In other words, we don't want the results of 543/// this to depend on where the addresses of various SCEV objects happened to 544/// land in memory. 545/// 546static void GroupByComplexity(std::vector<SCEVHandle> &Ops, 547 LoopInfo *LI) { 548 if (Ops.size() < 2) return; // Noop 549 if (Ops.size() == 2) { 550 // This is the common case, which also happens to be trivially simple. 551 // Special case it. 552 if (SCEVComplexityCompare(LI)(Ops[1], Ops[0])) 553 std::swap(Ops[0], Ops[1]); 554 return; 555 } 556 557 // Do the rough sort by complexity. 558 std::stable_sort(Ops.begin(), Ops.end(), SCEVComplexityCompare(LI)); 559 560 // Now that we are sorted by complexity, group elements of the same 561 // complexity. Note that this is, at worst, N^2, but the vector is likely to 562 // be extremely short in practice. Note that we take this approach because we 563 // do not want to depend on the addresses of the objects we are grouping. 564 for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) { 565 const SCEV *S = Ops[i]; 566 unsigned Complexity = S->getSCEVType(); 567 568 // If there are any objects of the same complexity and same value as this 569 // one, group them. 570 for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) { 571 if (Ops[j] == S) { // Found a duplicate. 572 // Move it to immediately after i'th element. 573 std::swap(Ops[i+1], Ops[j]); 574 ++i; // no need to rescan it. 575 if (i == e-2) return; // Done! 576 } 577 } 578 } 579} 580 581 582 583//===----------------------------------------------------------------------===// 584// Simple SCEV method implementations 585//===----------------------------------------------------------------------===// 586 587/// BinomialCoefficient - Compute BC(It, K). The result has width W. 588// Assume, K > 0. 589static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K, 590 ScalarEvolution &SE, 591 const Type* ResultTy) { 592 // Handle the simplest case efficiently. 593 if (K == 1) 594 return SE.getTruncateOrZeroExtend(It, ResultTy); 595 596 // We are using the following formula for BC(It, K): 597 // 598 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / K! 599 // 600 // Suppose, W is the bitwidth of the return value. We must be prepared for 601 // overflow. Hence, we must assure that the result of our computation is 602 // equal to the accurate one modulo 2^W. Unfortunately, division isn't 603 // safe in modular arithmetic. 604 // 605 // However, this code doesn't use exactly that formula; the formula it uses 606 // is something like the following, where T is the number of factors of 2 in 607 // K! (i.e. trailing zeros in the binary representation of K!), and ^ is 608 // exponentiation: 609 // 610 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / 2^T / (K! / 2^T) 611 // 612 // This formula is trivially equivalent to the previous formula. However, 613 // this formula can be implemented much more efficiently. The trick is that 614 // K! / 2^T is odd, and exact division by an odd number *is* safe in modular 615 // arithmetic. To do exact division in modular arithmetic, all we have 616 // to do is multiply by the inverse. Therefore, this step can be done at 617 // width W. 618 // 619 // The next issue is how to safely do the division by 2^T. The way this 620 // is done is by doing the multiplication step at a width of at least W + T 621 // bits. This way, the bottom W+T bits of the product are accurate. Then, 622 // when we perform the division by 2^T (which is equivalent to a right shift 623 // by T), the bottom W bits are accurate. Extra bits are okay; they'll get 624 // truncated out after the division by 2^T. 625 // 626 // In comparison to just directly using the first formula, this technique 627 // is much more efficient; using the first formula requires W * K bits, 628 // but this formula less than W + K bits. Also, the first formula requires 629 // a division step, whereas this formula only requires multiplies and shifts. 630 // 631 // It doesn't matter whether the subtraction step is done in the calculation 632 // width or the input iteration count's width; if the subtraction overflows, 633 // the result must be zero anyway. We prefer here to do it in the width of 634 // the induction variable because it helps a lot for certain cases; CodeGen 635 // isn't smart enough to ignore the overflow, which leads to much less 636 // efficient code if the width of the subtraction is wider than the native 637 // register width. 638 // 639 // (It's possible to not widen at all by pulling out factors of 2 before 640 // the multiplication; for example, K=2 can be calculated as 641 // It/2*(It+(It*INT_MIN/INT_MIN)+-1). However, it requires 642 // extra arithmetic, so it's not an obvious win, and it gets 643 // much more complicated for K > 3.) 644 645 // Protection from insane SCEVs; this bound is conservative, 646 // but it probably doesn't matter. 647 if (K > 1000) 648 return SE.getCouldNotCompute(); 649 650 unsigned W = SE.getTypeSizeInBits(ResultTy); 651 652 // Calculate K! / 2^T and T; we divide out the factors of two before 653 // multiplying for calculating K! / 2^T to avoid overflow. 654 // Other overflow doesn't matter because we only care about the bottom 655 // W bits of the result. 656 APInt OddFactorial(W, 1); 657 unsigned T = 1; 658 for (unsigned i = 3; i <= K; ++i) { 659 APInt Mult(W, i); 660 unsigned TwoFactors = Mult.countTrailingZeros(); 661 T += TwoFactors; 662 Mult = Mult.lshr(TwoFactors); 663 OddFactorial *= Mult; 664 } 665 666 // We need at least W + T bits for the multiplication step 667 unsigned CalculationBits = W + T; 668 669 // Calcuate 2^T, at width T+W. 670 APInt DivFactor = APInt(CalculationBits, 1).shl(T); 671 672 // Calculate the multiplicative inverse of K! / 2^T; 673 // this multiplication factor will perform the exact division by 674 // K! / 2^T. 675 APInt Mod = APInt::getSignedMinValue(W+1); 676 APInt MultiplyFactor = OddFactorial.zext(W+1); 677 MultiplyFactor = MultiplyFactor.multiplicativeInverse(Mod); 678 MultiplyFactor = MultiplyFactor.trunc(W); 679 680 // Calculate the product, at width T+W 681 const IntegerType *CalculationTy = IntegerType::get(CalculationBits); 682 SCEVHandle Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy); 683 for (unsigned i = 1; i != K; ++i) { 684 SCEVHandle S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType())); 685 Dividend = SE.getMulExpr(Dividend, 686 SE.getTruncateOrZeroExtend(S, CalculationTy)); 687 } 688 689 // Divide by 2^T 690 SCEVHandle DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor)); 691 692 // Truncate the result, and divide by K! / 2^T. 693 694 return SE.getMulExpr(SE.getConstant(MultiplyFactor), 695 SE.getTruncateOrZeroExtend(DivResult, ResultTy)); 696} 697 698/// evaluateAtIteration - Return the value of this chain of recurrences at 699/// the specified iteration number. We can evaluate this recurrence by 700/// multiplying each element in the chain by the binomial coefficient 701/// corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as: 702/// 703/// A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3) 704/// 705/// where BC(It, k) stands for binomial coefficient. 706/// 707SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It, 708 ScalarEvolution &SE) const { 709 SCEVHandle Result = getStart(); 710 for (unsigned i = 1, e = getNumOperands(); i != e; ++i) { 711 // The computation is correct in the face of overflow provided that the 712 // multiplication is performed _after_ the evaluation of the binomial 713 // coefficient. 714 SCEVHandle Coeff = BinomialCoefficient(It, i, SE, getType()); 715 if (isa<SCEVCouldNotCompute>(Coeff)) 716 return Coeff; 717 718 Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff)); 719 } 720 return Result; 721} 722 723//===----------------------------------------------------------------------===// 724// SCEV Expression folder implementations 725//===----------------------------------------------------------------------===// 726 727SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op, 728 const Type *Ty) { 729 assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) && 730 "This is not a truncating conversion!"); 731 assert(isSCEVable(Ty) && 732 "This is not a conversion to a SCEVable type!"); 733 Ty = getEffectiveSCEVType(Ty); 734 735 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) 736 return getUnknown( 737 ConstantExpr::getTrunc(SC->getValue(), Ty)); 738 739 // trunc(trunc(x)) --> trunc(x) 740 if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) 741 return getTruncateExpr(ST->getOperand(), Ty); 742 743 // trunc(sext(x)) --> sext(x) if widening or trunc(x) if narrowing 744 if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op)) 745 return getTruncateOrSignExtend(SS->getOperand(), Ty); 746 747 // trunc(zext(x)) --> zext(x) if widening or trunc(x) if narrowing 748 if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op)) 749 return getTruncateOrZeroExtend(SZ->getOperand(), Ty); 750 751 // If the input value is a chrec scev made out of constants, truncate 752 // all of the constants. 753 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) { 754 std::vector<SCEVHandle> Operands; 755 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) 756 Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty)); 757 return getAddRecExpr(Operands, AddRec->getLoop()); 758 } 759 760 SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)]; 761 if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty); 762 return Result; 763} 764 765SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op, 766 const Type *Ty) { 767 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) && 768 "This is not an extending conversion!"); 769 assert(isSCEVable(Ty) && 770 "This is not a conversion to a SCEVable type!"); 771 Ty = getEffectiveSCEVType(Ty); 772 773 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) { 774 const Type *IntTy = getEffectiveSCEVType(Ty); 775 Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy); 776 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty); 777 return getUnknown(C); 778 } 779 780 // zext(zext(x)) --> zext(x) 781 if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op)) 782 return getZeroExtendExpr(SZ->getOperand(), Ty); 783 784 // If the input value is a chrec scev, and we can prove that the value 785 // did not overflow the old, smaller, value, we can zero extend all of the 786 // operands (often constants). This allows analysis of something like 787 // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; } 788 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op)) 789 if (AR->isAffine()) { 790 // Check whether the backedge-taken count is SCEVCouldNotCompute. 791 // Note that this serves two purposes: It filters out loops that are 792 // simply not analyzable, and it covers the case where this code is 793 // being called from within backedge-taken count analysis, such that 794 // attempting to ask for the backedge-taken count would likely result 795 // in infinite recursion. In the later case, the analysis code will 796 // cope with a conservative value, and it will take care to purge 797 // that value once it has finished. 798 SCEVHandle MaxBECount = getMaxBackedgeTakenCount(AR->getLoop()); 799 if (!isa<SCEVCouldNotCompute>(MaxBECount)) { 800 // Manually compute the final value for AR, checking for 801 // overflow. 802 SCEVHandle Start = AR->getStart(); 803 SCEVHandle Step = AR->getStepRecurrence(*this); 804 805 // Check whether the backedge-taken count can be losslessly casted to 806 // the addrec's type. The count is always unsigned. 807 SCEVHandle CastedMaxBECount = 808 getTruncateOrZeroExtend(MaxBECount, Start->getType()); 809 SCEVHandle RecastedMaxBECount = 810 getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType()); 811 if (MaxBECount == RecastedMaxBECount) { 812 const Type *WideTy = 813 IntegerType::get(getTypeSizeInBits(Start->getType()) * 2); 814 // Check whether Start+Step*MaxBECount has no unsigned overflow. 815 SCEVHandle ZMul = 816 getMulExpr(CastedMaxBECount, 817 getTruncateOrZeroExtend(Step, Start->getType())); 818 SCEVHandle Add = getAddExpr(Start, ZMul); 819 SCEVHandle OperandExtendedAdd = 820 getAddExpr(getZeroExtendExpr(Start, WideTy), 821 getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), 822 getZeroExtendExpr(Step, WideTy))); 823 if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) 824 // Return the expression with the addrec on the outside. 825 return getAddRecExpr(getZeroExtendExpr(Start, Ty), 826 getZeroExtendExpr(Step, Ty), 827 AR->getLoop()); 828 829 // Similar to above, only this time treat the step value as signed. 830 // This covers loops that count down. 831 SCEVHandle SMul = 832 getMulExpr(CastedMaxBECount, 833 getTruncateOrSignExtend(Step, Start->getType())); 834 Add = getAddExpr(Start, SMul); 835 OperandExtendedAdd = 836 getAddExpr(getZeroExtendExpr(Start, WideTy), 837 getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), 838 getSignExtendExpr(Step, WideTy))); 839 if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) 840 // Return the expression with the addrec on the outside. 841 return getAddRecExpr(getZeroExtendExpr(Start, Ty), 842 getSignExtendExpr(Step, Ty), 843 AR->getLoop()); 844 } 845 } 846 } 847 848 SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)]; 849 if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty); 850 return Result; 851} 852 853SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, 854 const Type *Ty) { 855 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) && 856 "This is not an extending conversion!"); 857 assert(isSCEVable(Ty) && 858 "This is not a conversion to a SCEVable type!"); 859 Ty = getEffectiveSCEVType(Ty); 860 861 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) { 862 const Type *IntTy = getEffectiveSCEVType(Ty); 863 Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy); 864 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty); 865 return getUnknown(C); 866 } 867 868 // sext(sext(x)) --> sext(x) 869 if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op)) 870 return getSignExtendExpr(SS->getOperand(), Ty); 871 872 // If the input value is a chrec scev, and we can prove that the value 873 // did not overflow the old, smaller, value, we can sign extend all of the 874 // operands (often constants). This allows analysis of something like 875 // this: for (signed char X = 0; X < 100; ++X) { int Y = X; } 876 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op)) 877 if (AR->isAffine()) { 878 // Check whether the backedge-taken count is SCEVCouldNotCompute. 879 // Note that this serves two purposes: It filters out loops that are 880 // simply not analyzable, and it covers the case where this code is 881 // being called from within backedge-taken count analysis, such that 882 // attempting to ask for the backedge-taken count would likely result 883 // in infinite recursion. In the later case, the analysis code will 884 // cope with a conservative value, and it will take care to purge 885 // that value once it has finished. 886 SCEVHandle MaxBECount = getMaxBackedgeTakenCount(AR->getLoop()); 887 if (!isa<SCEVCouldNotCompute>(MaxBECount)) { 888 // Manually compute the final value for AR, checking for 889 // overflow. 890 SCEVHandle Start = AR->getStart(); 891 SCEVHandle Step = AR->getStepRecurrence(*this); 892 893 // Check whether the backedge-taken count can be losslessly casted to 894 // the addrec's type. The count is always unsigned. 895 SCEVHandle CastedMaxBECount = 896 getTruncateOrZeroExtend(MaxBECount, Start->getType()); 897 SCEVHandle RecastedMaxBECount = 898 getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType()); 899 if (MaxBECount == RecastedMaxBECount) { 900 const Type *WideTy = 901 IntegerType::get(getTypeSizeInBits(Start->getType()) * 2); 902 // Check whether Start+Step*MaxBECount has no signed overflow. 903 SCEVHandle SMul = 904 getMulExpr(CastedMaxBECount, 905 getTruncateOrSignExtend(Step, Start->getType())); 906 SCEVHandle Add = getAddExpr(Start, SMul); 907 SCEVHandle OperandExtendedAdd = 908 getAddExpr(getSignExtendExpr(Start, WideTy), 909 getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), 910 getSignExtendExpr(Step, WideTy))); 911 if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) 912 // Return the expression with the addrec on the outside. 913 return getAddRecExpr(getSignExtendExpr(Start, Ty), 914 getSignExtendExpr(Step, Ty), 915 AR->getLoop()); 916 } 917 } 918 } 919 920 SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)]; 921 if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty); 922 return Result; 923} 924 925// get - Get a canonical add expression, or something simpler if possible. 926SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) { 927 assert(!Ops.empty() && "Cannot get empty add!"); 928 if (Ops.size() == 1) return Ops[0]; 929#ifndef NDEBUG 930 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 931 assert(getEffectiveSCEVType(Ops[i]->getType()) == 932 getEffectiveSCEVType(Ops[0]->getType()) && 933 "SCEVAddExpr operand types don't match!"); 934#endif 935 936 // Sort by complexity, this groups all similar expression types together. 937 GroupByComplexity(Ops, LI); 938 939 // If there are any constants, fold them together. 940 unsigned Idx = 0; 941 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 942 ++Idx; 943 assert(Idx < Ops.size()); 944 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 945 // We found two constants, fold them together! 946 ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() + 947 RHSC->getValue()->getValue()); 948 Ops[0] = getConstant(Fold); 949 Ops.erase(Ops.begin()+1); // Erase the folded element 950 if (Ops.size() == 1) return Ops[0]; 951 LHSC = cast<SCEVConstant>(Ops[0]); 952 } 953 954 // If we are left with a constant zero being added, strip it off. 955 if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) { 956 Ops.erase(Ops.begin()); 957 --Idx; 958 } 959 } 960 961 if (Ops.size() == 1) return Ops[0]; 962 963 // Okay, check to see if the same value occurs in the operand list twice. If 964 // so, merge them together into an multiply expression. Since we sorted the 965 // list, these values are required to be adjacent. 966 const Type *Ty = Ops[0]->getType(); 967 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 968 if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2 969 // Found a match, merge the two values into a multiply, and add any 970 // remaining values to the result. 971 SCEVHandle Two = getIntegerSCEV(2, Ty); 972 SCEVHandle Mul = getMulExpr(Ops[i], Two); 973 if (Ops.size() == 2) 974 return Mul; 975 Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 976 Ops.push_back(Mul); 977 return getAddExpr(Ops); 978 } 979 980 // Check for truncates. If all the operands are truncated from the same 981 // type, see if factoring out the truncate would permit the result to be 982 // folded. eg., trunc(x) + m*trunc(n) --> trunc(x + trunc(m)*n) 983 // if the contents of the resulting outer trunc fold to something simple. 984 for (; Idx < Ops.size() && isa<SCEVTruncateExpr>(Ops[Idx]); ++Idx) { 985 const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Ops[Idx]); 986 const Type *DstType = Trunc->getType(); 987 const Type *SrcType = Trunc->getOperand()->getType(); 988 std::vector<SCEVHandle> LargeOps; 989 bool Ok = true; 990 // Check all the operands to see if they can be represented in the 991 // source type of the truncate. 992 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 993 if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Ops[i])) { 994 if (T->getOperand()->getType() != SrcType) { 995 Ok = false; 996 break; 997 } 998 LargeOps.push_back(T->getOperand()); 999 } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) { 1000 // This could be either sign or zero extension, but sign extension 1001 // is much more likely to be foldable here. 1002 LargeOps.push_back(getSignExtendExpr(C, SrcType)); 1003 } else if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) { 1004 std::vector<SCEVHandle> LargeMulOps; 1005 for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) { 1006 if (const SCEVTruncateExpr *T = 1007 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) { 1008 if (T->getOperand()->getType() != SrcType) { 1009 Ok = false; 1010 break; 1011 } 1012 LargeMulOps.push_back(T->getOperand()); 1013 } else if (const SCEVConstant *C = 1014 dyn_cast<SCEVConstant>(M->getOperand(j))) { 1015 // This could be either sign or zero extension, but sign extension 1016 // is much more likely to be foldable here. 1017 LargeMulOps.push_back(getSignExtendExpr(C, SrcType)); 1018 } else { 1019 Ok = false; 1020 break; 1021 } 1022 } 1023 if (Ok) 1024 LargeOps.push_back(getMulExpr(LargeMulOps)); 1025 } else { 1026 Ok = false; 1027 break; 1028 } 1029 } 1030 if (Ok) { 1031 // Evaluate the expression in the larger type. 1032 SCEVHandle Fold = getAddExpr(LargeOps); 1033 // If it folds to something simple, use it. Otherwise, don't. 1034 if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold)) 1035 return getTruncateExpr(Fold, DstType); 1036 } 1037 } 1038 1039 // Skip past any other cast SCEVs. 1040 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr) 1041 ++Idx; 1042 1043 // If there are add operands they would be next. 1044 if (Idx < Ops.size()) { 1045 bool DeletedAdd = false; 1046 while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) { 1047 // If we have an add, expand the add operands onto the end of the operands 1048 // list. 1049 Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); 1050 Ops.erase(Ops.begin()+Idx); 1051 DeletedAdd = true; 1052 } 1053 1054 // If we deleted at least one add, we added operands to the end of the list, 1055 // and they are not necessarily sorted. Recurse to resort and resimplify 1056 // any operands we just aquired. 1057 if (DeletedAdd) 1058 return getAddExpr(Ops); 1059 } 1060 1061 // Skip over the add expression until we get to a multiply. 1062 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) 1063 ++Idx; 1064 1065 // If we are adding something to a multiply expression, make sure the 1066 // something is not already an operand of the multiply. If so, merge it into 1067 // the multiply. 1068 for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) { 1069 const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]); 1070 for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) { 1071 const SCEV *MulOpSCEV = Mul->getOperand(MulOp); 1072 for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp) 1073 if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(MulOpSCEV)) { 1074 // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1)) 1075 SCEVHandle InnerMul = Mul->getOperand(MulOp == 0); 1076 if (Mul->getNumOperands() != 2) { 1077 // If the multiply has more than two operands, we must get the 1078 // Y*Z term. 1079 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end()); 1080 MulOps.erase(MulOps.begin()+MulOp); 1081 InnerMul = getMulExpr(MulOps); 1082 } 1083 SCEVHandle One = getIntegerSCEV(1, Ty); 1084 SCEVHandle AddOne = getAddExpr(InnerMul, One); 1085 SCEVHandle OuterMul = getMulExpr(AddOne, Ops[AddOp]); 1086 if (Ops.size() == 2) return OuterMul; 1087 if (AddOp < Idx) { 1088 Ops.erase(Ops.begin()+AddOp); 1089 Ops.erase(Ops.begin()+Idx-1); 1090 } else { 1091 Ops.erase(Ops.begin()+Idx); 1092 Ops.erase(Ops.begin()+AddOp-1); 1093 } 1094 Ops.push_back(OuterMul); 1095 return getAddExpr(Ops); 1096 } 1097 1098 // Check this multiply against other multiplies being added together. 1099 for (unsigned OtherMulIdx = Idx+1; 1100 OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]); 1101 ++OtherMulIdx) { 1102 const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]); 1103 // If MulOp occurs in OtherMul, we can fold the two multiplies 1104 // together. 1105 for (unsigned OMulOp = 0, e = OtherMul->getNumOperands(); 1106 OMulOp != e; ++OMulOp) 1107 if (OtherMul->getOperand(OMulOp) == MulOpSCEV) { 1108 // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E)) 1109 SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0); 1110 if (Mul->getNumOperands() != 2) { 1111 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end()); 1112 MulOps.erase(MulOps.begin()+MulOp); 1113 InnerMul1 = getMulExpr(MulOps); 1114 } 1115 SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0); 1116 if (OtherMul->getNumOperands() != 2) { 1117 std::vector<SCEVHandle> MulOps(OtherMul->op_begin(), 1118 OtherMul->op_end()); 1119 MulOps.erase(MulOps.begin()+OMulOp); 1120 InnerMul2 = getMulExpr(MulOps); 1121 } 1122 SCEVHandle InnerMulSum = getAddExpr(InnerMul1,InnerMul2); 1123 SCEVHandle OuterMul = getMulExpr(MulOpSCEV, InnerMulSum); 1124 if (Ops.size() == 2) return OuterMul; 1125 Ops.erase(Ops.begin()+Idx); 1126 Ops.erase(Ops.begin()+OtherMulIdx-1); 1127 Ops.push_back(OuterMul); 1128 return getAddExpr(Ops); 1129 } 1130 } 1131 } 1132 } 1133 1134 // If there are any add recurrences in the operands list, see if any other 1135 // added values are loop invariant. If so, we can fold them into the 1136 // recurrence. 1137 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) 1138 ++Idx; 1139 1140 // Scan over all recurrences, trying to fold loop invariants into them. 1141 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) { 1142 // Scan all of the other operands to this add and add them to the vector if 1143 // they are loop invariant w.r.t. the recurrence. 1144 std::vector<SCEVHandle> LIOps; 1145 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]); 1146 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 1147 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { 1148 LIOps.push_back(Ops[i]); 1149 Ops.erase(Ops.begin()+i); 1150 --i; --e; 1151 } 1152 1153 // If we found some loop invariants, fold them into the recurrence. 1154 if (!LIOps.empty()) { 1155 // NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step} 1156 LIOps.push_back(AddRec->getStart()); 1157 1158 std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end()); 1159 AddRecOps[0] = getAddExpr(LIOps); 1160 1161 SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop()); 1162 // If all of the other operands were loop invariant, we are done. 1163 if (Ops.size() == 1) return NewRec; 1164 1165 // Otherwise, add the folded AddRec by the non-liv parts. 1166 for (unsigned i = 0;; ++i) 1167 if (Ops[i] == AddRec) { 1168 Ops[i] = NewRec; 1169 break; 1170 } 1171 return getAddExpr(Ops); 1172 } 1173 1174 // Okay, if there weren't any loop invariants to be folded, check to see if 1175 // there are multiple AddRec's with the same loop induction variable being 1176 // added together. If so, we can fold them. 1177 for (unsigned OtherIdx = Idx+1; 1178 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx) 1179 if (OtherIdx != Idx) { 1180 const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]); 1181 if (AddRec->getLoop() == OtherAddRec->getLoop()) { 1182 // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D} 1183 std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end()); 1184 for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) { 1185 if (i >= NewOps.size()) { 1186 NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i, 1187 OtherAddRec->op_end()); 1188 break; 1189 } 1190 NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i)); 1191 } 1192 SCEVHandle NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop()); 1193 1194 if (Ops.size() == 2) return NewAddRec; 1195 1196 Ops.erase(Ops.begin()+Idx); 1197 Ops.erase(Ops.begin()+OtherIdx-1); 1198 Ops.push_back(NewAddRec); 1199 return getAddExpr(Ops); 1200 } 1201 } 1202 1203 // Otherwise couldn't fold anything into this recurrence. Move onto the 1204 // next one. 1205 } 1206 1207 // Okay, it looks like we really DO need an add expr. Check to see if we 1208 // already have one, otherwise create a new one. 1209 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end()); 1210 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr, 1211 SCEVOps)]; 1212 if (Result == 0) Result = new SCEVAddExpr(Ops); 1213 return Result; 1214} 1215 1216 1217SCEVHandle ScalarEvolution::getMulExpr(std::vector<SCEVHandle> &Ops) { 1218 assert(!Ops.empty() && "Cannot get empty mul!"); 1219#ifndef NDEBUG 1220 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 1221 assert(getEffectiveSCEVType(Ops[i]->getType()) == 1222 getEffectiveSCEVType(Ops[0]->getType()) && 1223 "SCEVMulExpr operand types don't match!"); 1224#endif 1225 1226 // Sort by complexity, this groups all similar expression types together. 1227 GroupByComplexity(Ops, LI); 1228 1229 // If there are any constants, fold them together. 1230 unsigned Idx = 0; 1231 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 1232 1233 // C1*(C2+V) -> C1*C2 + C1*V 1234 if (Ops.size() == 2) 1235 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) 1236 if (Add->getNumOperands() == 2 && 1237 isa<SCEVConstant>(Add->getOperand(0))) 1238 return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)), 1239 getMulExpr(LHSC, Add->getOperand(1))); 1240 1241 1242 ++Idx; 1243 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 1244 // We found two constants, fold them together! 1245 ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() * 1246 RHSC->getValue()->getValue()); 1247 Ops[0] = getConstant(Fold); 1248 Ops.erase(Ops.begin()+1); // Erase the folded element 1249 if (Ops.size() == 1) return Ops[0]; 1250 LHSC = cast<SCEVConstant>(Ops[0]); 1251 } 1252 1253 // If we are left with a constant one being multiplied, strip it off. 1254 if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) { 1255 Ops.erase(Ops.begin()); 1256 --Idx; 1257 } else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) { 1258 // If we have a multiply of zero, it will always be zero. 1259 return Ops[0]; 1260 } 1261 } 1262 1263 // Skip over the add expression until we get to a multiply. 1264 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) 1265 ++Idx; 1266 1267 if (Ops.size() == 1) 1268 return Ops[0]; 1269 1270 // If there are mul operands inline them all into this expression. 1271 if (Idx < Ops.size()) { 1272 bool DeletedMul = false; 1273 while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) { 1274 // If we have an mul, expand the mul operands onto the end of the operands 1275 // list. 1276 Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end()); 1277 Ops.erase(Ops.begin()+Idx); 1278 DeletedMul = true; 1279 } 1280 1281 // If we deleted at least one mul, we added operands to the end of the list, 1282 // and they are not necessarily sorted. Recurse to resort and resimplify 1283 // any operands we just aquired. 1284 if (DeletedMul) 1285 return getMulExpr(Ops); 1286 } 1287 1288 // If there are any add recurrences in the operands list, see if any other 1289 // added values are loop invariant. If so, we can fold them into the 1290 // recurrence. 1291 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) 1292 ++Idx; 1293 1294 // Scan over all recurrences, trying to fold loop invariants into them. 1295 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) { 1296 // Scan all of the other operands to this mul and add them to the vector if 1297 // they are loop invariant w.r.t. the recurrence. 1298 std::vector<SCEVHandle> LIOps; 1299 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]); 1300 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 1301 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { 1302 LIOps.push_back(Ops[i]); 1303 Ops.erase(Ops.begin()+i); 1304 --i; --e; 1305 } 1306 1307 // If we found some loop invariants, fold them into the recurrence. 1308 if (!LIOps.empty()) { 1309 // NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step} 1310 std::vector<SCEVHandle> NewOps; 1311 NewOps.reserve(AddRec->getNumOperands()); 1312 if (LIOps.size() == 1) { 1313 const SCEV *Scale = LIOps[0]; 1314 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) 1315 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i))); 1316 } else { 1317 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { 1318 std::vector<SCEVHandle> MulOps(LIOps); 1319 MulOps.push_back(AddRec->getOperand(i)); 1320 NewOps.push_back(getMulExpr(MulOps)); 1321 } 1322 } 1323 1324 SCEVHandle NewRec = getAddRecExpr(NewOps, AddRec->getLoop()); 1325 1326 // If all of the other operands were loop invariant, we are done. 1327 if (Ops.size() == 1) return NewRec; 1328 1329 // Otherwise, multiply the folded AddRec by the non-liv parts. 1330 for (unsigned i = 0;; ++i) 1331 if (Ops[i] == AddRec) { 1332 Ops[i] = NewRec; 1333 break; 1334 } 1335 return getMulExpr(Ops); 1336 } 1337 1338 // Okay, if there weren't any loop invariants to be folded, check to see if 1339 // there are multiple AddRec's with the same loop induction variable being 1340 // multiplied together. If so, we can fold them. 1341 for (unsigned OtherIdx = Idx+1; 1342 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx) 1343 if (OtherIdx != Idx) { 1344 const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]); 1345 if (AddRec->getLoop() == OtherAddRec->getLoop()) { 1346 // F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D} 1347 const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec; 1348 SCEVHandle NewStart = getMulExpr(F->getStart(), 1349 G->getStart()); 1350 SCEVHandle B = F->getStepRecurrence(*this); 1351 SCEVHandle D = G->getStepRecurrence(*this); 1352 SCEVHandle NewStep = getAddExpr(getMulExpr(F, D), 1353 getMulExpr(G, B), 1354 getMulExpr(B, D)); 1355 SCEVHandle NewAddRec = getAddRecExpr(NewStart, NewStep, 1356 F->getLoop()); 1357 if (Ops.size() == 2) return NewAddRec; 1358 1359 Ops.erase(Ops.begin()+Idx); 1360 Ops.erase(Ops.begin()+OtherIdx-1); 1361 Ops.push_back(NewAddRec); 1362 return getMulExpr(Ops); 1363 } 1364 } 1365 1366 // Otherwise couldn't fold anything into this recurrence. Move onto the 1367 // next one. 1368 } 1369 1370 // Okay, it looks like we really DO need an mul expr. Check to see if we 1371 // already have one, otherwise create a new one. 1372 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end()); 1373 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr, 1374 SCEVOps)]; 1375 if (Result == 0) 1376 Result = new SCEVMulExpr(Ops); 1377 return Result; 1378} 1379 1380SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, 1381 const SCEVHandle &RHS) { 1382 assert(getEffectiveSCEVType(LHS->getType()) == 1383 getEffectiveSCEVType(RHS->getType()) && 1384 "SCEVUDivExpr operand types don't match!"); 1385 1386 if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) { 1387 if (RHSC->getValue()->equalsInt(1)) 1388 return LHS; // X udiv 1 --> x 1389 if (RHSC->isZero()) 1390 return getIntegerSCEV(0, LHS->getType()); // value is undefined 1391 1392 // Determine if the division can be folded into the operands of 1393 // its operands. 1394 // TODO: Generalize this to non-constants by using known-bits information. 1395 const Type *Ty = LHS->getType(); 1396 unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros(); 1397 unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ; 1398 // For non-power-of-two values, effectively round the value up to the 1399 // nearest power of two. 1400 if (!RHSC->getValue()->getValue().isPowerOf2()) 1401 ++MaxShiftAmt; 1402 const IntegerType *ExtTy = 1403 IntegerType::get(getTypeSizeInBits(Ty) + MaxShiftAmt); 1404 // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded. 1405 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS)) 1406 if (const SCEVConstant *Step = 1407 dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this))) 1408 if (!Step->getValue()->getValue() 1409 .urem(RHSC->getValue()->getValue()) && 1410 getZeroExtendExpr(AR, ExtTy) == 1411 getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy), 1412 getZeroExtendExpr(Step, ExtTy), 1413 AR->getLoop())) { 1414 std::vector<SCEVHandle> Operands; 1415 for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i) 1416 Operands.push_back(getUDivExpr(AR->getOperand(i), RHS)); 1417 return getAddRecExpr(Operands, AR->getLoop()); 1418 } 1419 // (A*B)/C --> A*(B/C) if safe and B/C can be folded. 1420 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) { 1421 std::vector<SCEVHandle> Operands; 1422 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) 1423 Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy)); 1424 if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands)) 1425 // Find an operand that's safely divisible. 1426 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) { 1427 SCEVHandle Op = M->getOperand(i); 1428 SCEVHandle Div = getUDivExpr(Op, RHSC); 1429 if (!isa<SCEVUDivExpr>(Div) && getMulExpr(Div, RHSC) == Op) { 1430 Operands = M->getOperands(); 1431 Operands[i] = Div; 1432 return getMulExpr(Operands); 1433 } 1434 } 1435 } 1436 // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded. 1437 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(LHS)) { 1438 std::vector<SCEVHandle> Operands; 1439 for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) 1440 Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy)); 1441 if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) { 1442 Operands.clear(); 1443 for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) { 1444 SCEVHandle Op = getUDivExpr(A->getOperand(i), RHS); 1445 if (isa<SCEVUDivExpr>(Op) || getMulExpr(Op, RHS) != A->getOperand(i)) 1446 break; 1447 Operands.push_back(Op); 1448 } 1449 if (Operands.size() == A->getNumOperands()) 1450 return getAddExpr(Operands); 1451 } 1452 } 1453 1454 // Fold if both operands are constant. 1455 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) { 1456 Constant *LHSCV = LHSC->getValue(); 1457 Constant *RHSCV = RHSC->getValue(); 1458 return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV)); 1459 } 1460 } 1461 1462 SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)]; 1463 if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS); 1464 return Result; 1465} 1466 1467 1468/// SCEVAddRecExpr::get - Get a add recurrence expression for the 1469/// specified loop. Simplify the expression as much as possible. 1470SCEVHandle ScalarEvolution::getAddRecExpr(const SCEVHandle &Start, 1471 const SCEVHandle &Step, const Loop *L) { 1472 std::vector<SCEVHandle> Operands; 1473 Operands.push_back(Start); 1474 if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step)) 1475 if (StepChrec->getLoop() == L) { 1476 Operands.insert(Operands.end(), StepChrec->op_begin(), 1477 StepChrec->op_end()); 1478 return getAddRecExpr(Operands, L); 1479 } 1480 1481 Operands.push_back(Step); 1482 return getAddRecExpr(Operands, L); 1483} 1484 1485/// SCEVAddRecExpr::get - Get a add recurrence expression for the 1486/// specified loop. Simplify the expression as much as possible. 1487SCEVHandle ScalarEvolution::getAddRecExpr(std::vector<SCEVHandle> &Operands, 1488 const Loop *L) { 1489 if (Operands.size() == 1) return Operands[0]; 1490#ifndef NDEBUG 1491 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 1492 assert(getEffectiveSCEVType(Operands[i]->getType()) == 1493 getEffectiveSCEVType(Operands[0]->getType()) && 1494 "SCEVAddRecExpr operand types don't match!"); 1495#endif 1496 1497 if (Operands.back()->isZero()) { 1498 Operands.pop_back(); 1499 return getAddRecExpr(Operands, L); // {X,+,0} --> X 1500 } 1501 1502 // Canonicalize nested AddRecs in by nesting them in order of loop depth. 1503 if (const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) { 1504 const Loop* NestedLoop = NestedAR->getLoop(); 1505 if (L->getLoopDepth() < NestedLoop->getLoopDepth()) { 1506 std::vector<SCEVHandle> NestedOperands(NestedAR->op_begin(), 1507 NestedAR->op_end()); 1508 SCEVHandle NestedARHandle(NestedAR); 1509 Operands[0] = NestedAR->getStart(); 1510 NestedOperands[0] = getAddRecExpr(Operands, L); 1511 return getAddRecExpr(NestedOperands, NestedLoop); 1512 } 1513 } 1514 1515 std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end()); 1516 SCEVAddRecExpr *&Result = (*SCEVAddRecExprs)[std::make_pair(L, SCEVOps)]; 1517 if (Result == 0) Result = new SCEVAddRecExpr(Operands, L); 1518 return Result; 1519} 1520 1521SCEVHandle ScalarEvolution::getSMaxExpr(const SCEVHandle &LHS, 1522 const SCEVHandle &RHS) { 1523 std::vector<SCEVHandle> Ops; 1524 Ops.push_back(LHS); 1525 Ops.push_back(RHS); 1526 return getSMaxExpr(Ops); 1527} 1528 1529SCEVHandle ScalarEvolution::getSMaxExpr(std::vector<SCEVHandle> Ops) { 1530 assert(!Ops.empty() && "Cannot get empty smax!"); 1531 if (Ops.size() == 1) return Ops[0]; 1532#ifndef NDEBUG 1533 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 1534 assert(getEffectiveSCEVType(Ops[i]->getType()) == 1535 getEffectiveSCEVType(Ops[0]->getType()) && 1536 "SCEVSMaxExpr operand types don't match!"); 1537#endif 1538 1539 // Sort by complexity, this groups all similar expression types together. 1540 GroupByComplexity(Ops, LI); 1541 1542 // If there are any constants, fold them together. 1543 unsigned Idx = 0; 1544 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 1545 ++Idx; 1546 assert(Idx < Ops.size()); 1547 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 1548 // We found two constants, fold them together! 1549 ConstantInt *Fold = ConstantInt::get( 1550 APIntOps::smax(LHSC->getValue()->getValue(), 1551 RHSC->getValue()->getValue())); 1552 Ops[0] = getConstant(Fold); 1553 Ops.erase(Ops.begin()+1); // Erase the folded element 1554 if (Ops.size() == 1) return Ops[0]; 1555 LHSC = cast<SCEVConstant>(Ops[0]); 1556 } 1557 1558 // If we are left with a constant -inf, strip it off. 1559 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) { 1560 Ops.erase(Ops.begin()); 1561 --Idx; 1562 } 1563 } 1564 1565 if (Ops.size() == 1) return Ops[0]; 1566 1567 // Find the first SMax 1568 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr) 1569 ++Idx; 1570 1571 // Check to see if one of the operands is an SMax. If so, expand its operands 1572 // onto our operand list, and recurse to simplify. 1573 if (Idx < Ops.size()) { 1574 bool DeletedSMax = false; 1575 while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) { 1576 Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end()); 1577 Ops.erase(Ops.begin()+Idx); 1578 DeletedSMax = true; 1579 } 1580 1581 if (DeletedSMax) 1582 return getSMaxExpr(Ops); 1583 } 1584 1585 // Okay, check to see if the same value occurs in the operand list twice. If 1586 // so, delete one. Since we sorted the list, these values are required to 1587 // be adjacent. 1588 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 1589 if (Ops[i] == Ops[i+1]) { // X smax Y smax Y --> X smax Y 1590 Ops.erase(Ops.begin()+i, Ops.begin()+i+1); 1591 --i; --e; 1592 } 1593 1594 if (Ops.size() == 1) return Ops[0]; 1595 1596 assert(!Ops.empty() && "Reduced smax down to nothing!"); 1597 1598 // Okay, it looks like we really DO need an smax expr. Check to see if we 1599 // already have one, otherwise create a new one. 1600 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end()); 1601 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr, 1602 SCEVOps)]; 1603 if (Result == 0) Result = new SCEVSMaxExpr(Ops); 1604 return Result; 1605} 1606 1607SCEVHandle ScalarEvolution::getUMaxExpr(const SCEVHandle &LHS, 1608 const SCEVHandle &RHS) { 1609 std::vector<SCEVHandle> Ops; 1610 Ops.push_back(LHS); 1611 Ops.push_back(RHS); 1612 return getUMaxExpr(Ops); 1613} 1614 1615SCEVHandle ScalarEvolution::getUMaxExpr(std::vector<SCEVHandle> Ops) { 1616 assert(!Ops.empty() && "Cannot get empty umax!"); 1617 if (Ops.size() == 1) return Ops[0]; 1618#ifndef NDEBUG 1619 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 1620 assert(getEffectiveSCEVType(Ops[i]->getType()) == 1621 getEffectiveSCEVType(Ops[0]->getType()) && 1622 "SCEVUMaxExpr operand types don't match!"); 1623#endif 1624 1625 // Sort by complexity, this groups all similar expression types together. 1626 GroupByComplexity(Ops, LI); 1627 1628 // If there are any constants, fold them together. 1629 unsigned Idx = 0; 1630 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 1631 ++Idx; 1632 assert(Idx < Ops.size()); 1633 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 1634 // We found two constants, fold them together! 1635 ConstantInt *Fold = ConstantInt::get( 1636 APIntOps::umax(LHSC->getValue()->getValue(), 1637 RHSC->getValue()->getValue())); 1638 Ops[0] = getConstant(Fold); 1639 Ops.erase(Ops.begin()+1); // Erase the folded element 1640 if (Ops.size() == 1) return Ops[0]; 1641 LHSC = cast<SCEVConstant>(Ops[0]); 1642 } 1643 1644 // If we are left with a constant zero, strip it off. 1645 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) { 1646 Ops.erase(Ops.begin()); 1647 --Idx; 1648 } 1649 } 1650 1651 if (Ops.size() == 1) return Ops[0]; 1652 1653 // Find the first UMax 1654 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr) 1655 ++Idx; 1656 1657 // Check to see if one of the operands is a UMax. If so, expand its operands 1658 // onto our operand list, and recurse to simplify. 1659 if (Idx < Ops.size()) { 1660 bool DeletedUMax = false; 1661 while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) { 1662 Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end()); 1663 Ops.erase(Ops.begin()+Idx); 1664 DeletedUMax = true; 1665 } 1666 1667 if (DeletedUMax) 1668 return getUMaxExpr(Ops); 1669 } 1670 1671 // Okay, check to see if the same value occurs in the operand list twice. If 1672 // so, delete one. Since we sorted the list, these values are required to 1673 // be adjacent. 1674 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 1675 if (Ops[i] == Ops[i+1]) { // X umax Y umax Y --> X umax Y 1676 Ops.erase(Ops.begin()+i, Ops.begin()+i+1); 1677 --i; --e; 1678 } 1679 1680 if (Ops.size() == 1) return Ops[0]; 1681 1682 assert(!Ops.empty() && "Reduced umax down to nothing!"); 1683 1684 // Okay, it looks like we really DO need a umax expr. Check to see if we 1685 // already have one, otherwise create a new one. 1686 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end()); 1687 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr, 1688 SCEVOps)]; 1689 if (Result == 0) Result = new SCEVUMaxExpr(Ops); 1690 return Result; 1691} 1692 1693SCEVHandle ScalarEvolution::getUnknown(Value *V) { 1694 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 1695 return getConstant(CI); 1696 if (isa<ConstantPointerNull>(V)) 1697 return getIntegerSCEV(0, V->getType()); 1698 SCEVUnknown *&Result = (*SCEVUnknowns)[V]; 1699 if (Result == 0) Result = new SCEVUnknown(V); 1700 return Result; 1701} 1702 1703//===----------------------------------------------------------------------===// 1704// Basic SCEV Analysis and PHI Idiom Recognition Code 1705// 1706 1707/// isSCEVable - Test if values of the given type are analyzable within 1708/// the SCEV framework. This primarily includes integer types, and it 1709/// can optionally include pointer types if the ScalarEvolution class 1710/// has access to target-specific information. 1711bool ScalarEvolution::isSCEVable(const Type *Ty) const { 1712 // Integers are always SCEVable. 1713 if (Ty->isInteger()) 1714 return true; 1715 1716 // Pointers are SCEVable if TargetData information is available 1717 // to provide pointer size information. 1718 if (isa<PointerType>(Ty)) 1719 return TD != NULL; 1720 1721 // Otherwise it's not SCEVable. 1722 return false; 1723} 1724 1725/// getTypeSizeInBits - Return the size in bits of the specified type, 1726/// for which isSCEVable must return true. 1727uint64_t ScalarEvolution::getTypeSizeInBits(const Type *Ty) const { 1728 assert(isSCEVable(Ty) && "Type is not SCEVable!"); 1729 1730 // If we have a TargetData, use it! 1731 if (TD) 1732 return TD->getTypeSizeInBits(Ty); 1733 1734 // Otherwise, we support only integer types. 1735 assert(Ty->isInteger() && "isSCEVable permitted a non-SCEVable type!"); 1736 return Ty->getPrimitiveSizeInBits(); 1737} 1738 1739/// getEffectiveSCEVType - Return a type with the same bitwidth as 1740/// the given type and which represents how SCEV will treat the given 1741/// type, for which isSCEVable must return true. For pointer types, 1742/// this is the pointer-sized integer type. 1743const Type *ScalarEvolution::getEffectiveSCEVType(const Type *Ty) const { 1744 assert(isSCEVable(Ty) && "Type is not SCEVable!"); 1745 1746 if (Ty->isInteger()) 1747 return Ty; 1748 1749 assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!"); 1750 return TD->getIntPtrType(); 1751} 1752 1753SCEVHandle ScalarEvolution::getCouldNotCompute() { 1754 return UnknownValue; 1755} 1756 1757/// hasSCEV - Return true if the SCEV for this value has already been 1758/// computed. 1759bool ScalarEvolution::hasSCEV(Value *V) const { 1760 return Scalars.count(V); 1761} 1762 1763/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the 1764/// expression and create a new one. 1765SCEVHandle ScalarEvolution::getSCEV(Value *V) { 1766 assert(isSCEVable(V->getType()) && "Value is not SCEVable!"); 1767 1768 std::map<SCEVCallbackVH, SCEVHandle>::iterator I = Scalars.find(V); 1769 if (I != Scalars.end()) return I->second; 1770 SCEVHandle S = createSCEV(V); 1771 Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S)); 1772 return S; 1773} 1774 1775/// getIntegerSCEV - Given an integer or FP type, create a constant for the 1776/// specified signed integer value and return a SCEV for the constant. 1777SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) { 1778 Ty = getEffectiveSCEVType(Ty); 1779 Constant *C; 1780 if (Val == 0) 1781 C = Constant::getNullValue(Ty); 1782 else if (Ty->isFloatingPoint()) 1783 C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle : 1784 APFloat::IEEEdouble, Val)); 1785 else 1786 C = ConstantInt::get(Ty, Val); 1787 return getUnknown(C); 1788} 1789 1790/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V 1791/// 1792SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) { 1793 if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) 1794 return getUnknown(ConstantExpr::getNeg(VC->getValue())); 1795 1796 const Type *Ty = V->getType(); 1797 Ty = getEffectiveSCEVType(Ty); 1798 return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(Ty))); 1799} 1800 1801/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V 1802SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) { 1803 if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) 1804 return getUnknown(ConstantExpr::getNot(VC->getValue())); 1805 1806 const Type *Ty = V->getType(); 1807 Ty = getEffectiveSCEVType(Ty); 1808 SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(Ty)); 1809 return getMinusSCEV(AllOnes, V); 1810} 1811 1812/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS. 1813/// 1814SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS, 1815 const SCEVHandle &RHS) { 1816 // X - Y --> X + -Y 1817 return getAddExpr(LHS, getNegativeSCEV(RHS)); 1818} 1819 1820/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the 1821/// input value to the specified type. If the type must be extended, it is zero 1822/// extended. 1823SCEVHandle 1824ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V, 1825 const Type *Ty) { 1826 const Type *SrcTy = V->getType(); 1827 assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) && 1828 (Ty->isInteger() || (TD && isa<PointerType>(Ty))) && 1829 "Cannot truncate or zero extend with non-integer arguments!"); 1830 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 1831 return V; // No conversion 1832 if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty)) 1833 return getTruncateExpr(V, Ty); 1834 return getZeroExtendExpr(V, Ty); 1835} 1836 1837/// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion of the 1838/// input value to the specified type. If the type must be extended, it is sign 1839/// extended. 1840SCEVHandle 1841ScalarEvolution::getTruncateOrSignExtend(const SCEVHandle &V, 1842 const Type *Ty) { 1843 const Type *SrcTy = V->getType(); 1844 assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) && 1845 (Ty->isInteger() || (TD && isa<PointerType>(Ty))) && 1846 "Cannot truncate or zero extend with non-integer arguments!"); 1847 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 1848 return V; // No conversion 1849 if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty)) 1850 return getTruncateExpr(V, Ty); 1851 return getSignExtendExpr(V, Ty); 1852} 1853 1854/// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of the 1855/// input value to the specified type. If the type must be extended, it is zero 1856/// extended. The conversion must not be narrowing. 1857SCEVHandle 1858ScalarEvolution::getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty) { 1859 const Type *SrcTy = V->getType(); 1860 assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) && 1861 (Ty->isInteger() || (TD && isa<PointerType>(Ty))) && 1862 "Cannot noop or zero extend with non-integer arguments!"); 1863 assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) && 1864 "getNoopOrZeroExtend cannot truncate!"); 1865 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 1866 return V; // No conversion 1867 return getZeroExtendExpr(V, Ty); 1868} 1869 1870/// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of the 1871/// input value to the specified type. If the type must be extended, it is sign 1872/// extended. The conversion must not be narrowing. 1873SCEVHandle 1874ScalarEvolution::getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty) { 1875 const Type *SrcTy = V->getType(); 1876 assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) && 1877 (Ty->isInteger() || (TD && isa<PointerType>(Ty))) && 1878 "Cannot noop or sign extend with non-integer arguments!"); 1879 assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) && 1880 "getNoopOrSignExtend cannot truncate!"); 1881 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 1882 return V; // No conversion 1883 return getSignExtendExpr(V, Ty); 1884} 1885 1886/// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 1887/// input value to the specified type. The conversion must not be widening. 1888SCEVHandle 1889ScalarEvolution::getTruncateOrNoop(const SCEVHandle &V, const Type *Ty) { 1890 const Type *SrcTy = V->getType(); 1891 assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) && 1892 (Ty->isInteger() || (TD && isa<PointerType>(Ty))) && 1893 "Cannot truncate or noop with non-integer arguments!"); 1894 assert(getTypeSizeInBits(SrcTy) >= getTypeSizeInBits(Ty) && 1895 "getTruncateOrNoop cannot extend!"); 1896 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 1897 return V; // No conversion 1898 return getTruncateExpr(V, Ty); 1899} 1900 1901/// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for 1902/// the specified instruction and replaces any references to the symbolic value 1903/// SymName with the specified value. This is used during PHI resolution. 1904void ScalarEvolution:: 1905ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName, 1906 const SCEVHandle &NewVal) { 1907 std::map<SCEVCallbackVH, SCEVHandle>::iterator SI = 1908 Scalars.find(SCEVCallbackVH(I, this)); 1909 if (SI == Scalars.end()) return; 1910 1911 SCEVHandle NV = 1912 SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, *this); 1913 if (NV == SI->second) return; // No change. 1914 1915 SI->second = NV; // Update the scalars map! 1916 1917 // Any instruction values that use this instruction might also need to be 1918 // updated! 1919 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1920 UI != E; ++UI) 1921 ReplaceSymbolicValueWithConcrete(cast<Instruction>(*UI), SymName, NewVal); 1922} 1923 1924/// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in 1925/// a loop header, making it a potential recurrence, or it doesn't. 1926/// 1927SCEVHandle ScalarEvolution::createNodeForPHI(PHINode *PN) { 1928 if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized. 1929 if (const Loop *L = LI->getLoopFor(PN->getParent())) 1930 if (L->getHeader() == PN->getParent()) { 1931 // If it lives in the loop header, it has two incoming values, one 1932 // from outside the loop, and one from inside. 1933 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 1934 unsigned BackEdge = IncomingEdge^1; 1935 1936 // While we are analyzing this PHI node, handle its value symbolically. 1937 SCEVHandle SymbolicName = getUnknown(PN); 1938 assert(Scalars.find(PN) == Scalars.end() && 1939 "PHI node already processed?"); 1940 Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName)); 1941 1942 // Using this symbolic name for the PHI, analyze the value coming around 1943 // the back-edge. 1944 SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge)); 1945 1946 // NOTE: If BEValue is loop invariant, we know that the PHI node just 1947 // has a special value for the first iteration of the loop. 1948 1949 // If the value coming around the backedge is an add with the symbolic 1950 // value we just inserted, then we found a simple induction variable! 1951 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) { 1952 // If there is a single occurrence of the symbolic value, replace it 1953 // with a recurrence. 1954 unsigned FoundIndex = Add->getNumOperands(); 1955 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) 1956 if (Add->getOperand(i) == SymbolicName) 1957 if (FoundIndex == e) { 1958 FoundIndex = i; 1959 break; 1960 } 1961 1962 if (FoundIndex != Add->getNumOperands()) { 1963 // Create an add with everything but the specified operand. 1964 std::vector<SCEVHandle> Ops; 1965 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) 1966 if (i != FoundIndex) 1967 Ops.push_back(Add->getOperand(i)); 1968 SCEVHandle Accum = getAddExpr(Ops); 1969 1970 // This is not a valid addrec if the step amount is varying each 1971 // loop iteration, but is not itself an addrec in this loop. 1972 if (Accum->isLoopInvariant(L) || 1973 (isa<SCEVAddRecExpr>(Accum) && 1974 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) { 1975 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); 1976 SCEVHandle PHISCEV = getAddRecExpr(StartVal, Accum, L); 1977 1978 // Okay, for the entire analysis of this edge we assumed the PHI 1979 // to be symbolic. We now need to go back and update all of the 1980 // entries for the scalars that use the PHI (except for the PHI 1981 // itself) to use the new analyzed value instead of the "symbolic" 1982 // value. 1983 ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV); 1984 return PHISCEV; 1985 } 1986 } 1987 } else if (const SCEVAddRecExpr *AddRec = 1988 dyn_cast<SCEVAddRecExpr>(BEValue)) { 1989 // Otherwise, this could be a loop like this: 1990 // i = 0; for (j = 1; ..; ++j) { .... i = j; } 1991 // In this case, j = {1,+,1} and BEValue is j. 1992 // Because the other in-value of i (0) fits the evolution of BEValue 1993 // i really is an addrec evolution. 1994 if (AddRec->getLoop() == L && AddRec->isAffine()) { 1995 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); 1996 1997 // If StartVal = j.start - j.stride, we can use StartVal as the 1998 // initial step of the addrec evolution. 1999 if (StartVal == getMinusSCEV(AddRec->getOperand(0), 2000 AddRec->getOperand(1))) { 2001 SCEVHandle PHISCEV = 2002 getAddRecExpr(StartVal, AddRec->getOperand(1), L); 2003 2004 // Okay, for the entire analysis of this edge we assumed the PHI 2005 // to be symbolic. We now need to go back and update all of the 2006 // entries for the scalars that use the PHI (except for the PHI 2007 // itself) to use the new analyzed value instead of the "symbolic" 2008 // value. 2009 ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV); 2010 return PHISCEV; 2011 } 2012 } 2013 } 2014 2015 return SymbolicName; 2016 } 2017 2018 // If it's not a loop phi, we can't handle it yet. 2019 return getUnknown(PN); 2020} 2021 2022/// createNodeForGEP - Expand GEP instructions into add and multiply 2023/// operations. This allows them to be analyzed by regular SCEV code. 2024/// 2025SCEVHandle ScalarEvolution::createNodeForGEP(User *GEP) { 2026 2027 const Type *IntPtrTy = TD->getIntPtrType(); 2028 Value *Base = GEP->getOperand(0); 2029 // Don't attempt to analyze GEPs over unsized objects. 2030 if (!cast<PointerType>(Base->getType())->getElementType()->isSized()) 2031 return getUnknown(GEP); 2032 SCEVHandle TotalOffset = getIntegerSCEV(0, IntPtrTy); 2033 gep_type_iterator GTI = gep_type_begin(GEP); 2034 for (GetElementPtrInst::op_iterator I = next(GEP->op_begin()), 2035 E = GEP->op_end(); 2036 I != E; ++I) { 2037 Value *Index = *I; 2038 // Compute the (potentially symbolic) offset in bytes for this index. 2039 if (const StructType *STy = dyn_cast<StructType>(*GTI++)) { 2040 // For a struct, add the member offset. 2041 const StructLayout &SL = *TD->getStructLayout(STy); 2042 unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 2043 uint64_t Offset = SL.getElementOffset(FieldNo); 2044 TotalOffset = getAddExpr(TotalOffset, 2045 getIntegerSCEV(Offset, IntPtrTy)); 2046 } else { 2047 // For an array, add the element offset, explicitly scaled. 2048 SCEVHandle LocalOffset = getSCEV(Index); 2049 if (!isa<PointerType>(LocalOffset->getType())) 2050 // Getelementptr indicies are signed. 2051 LocalOffset = getTruncateOrSignExtend(LocalOffset, 2052 IntPtrTy); 2053 LocalOffset = 2054 getMulExpr(LocalOffset, 2055 getIntegerSCEV(TD->getTypeAllocSize(*GTI), 2056 IntPtrTy)); 2057 TotalOffset = getAddExpr(TotalOffset, LocalOffset); 2058 } 2059 } 2060 return getAddExpr(getSCEV(Base), TotalOffset); 2061} 2062 2063/// GetMinTrailingZeros - Determine the minimum number of zero bits that S is 2064/// guaranteed to end in (at every loop iteration). It is, at the same time, 2065/// the minimum number of times S is divisible by 2. For example, given {4,+,8} 2066/// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S. 2067static uint32_t GetMinTrailingZeros(SCEVHandle S, const ScalarEvolution &SE) { 2068 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) 2069 return C->getValue()->getValue().countTrailingZeros(); 2070 2071 if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S)) 2072 return std::min(GetMinTrailingZeros(T->getOperand(), SE), 2073 (uint32_t)SE.getTypeSizeInBits(T->getType())); 2074 2075 if (const SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) { 2076 uint32_t OpRes = GetMinTrailingZeros(E->getOperand(), SE); 2077 return OpRes == SE.getTypeSizeInBits(E->getOperand()->getType()) ? 2078 SE.getTypeSizeInBits(E->getType()) : OpRes; 2079 } 2080 2081 if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) { 2082 uint32_t OpRes = GetMinTrailingZeros(E->getOperand(), SE); 2083 return OpRes == SE.getTypeSizeInBits(E->getOperand()->getType()) ? 2084 SE.getTypeSizeInBits(E->getType()) : OpRes; 2085 } 2086 2087 if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 2088 // The result is the min of all operands results. 2089 uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE); 2090 for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i) 2091 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), SE)); 2092 return MinOpRes; 2093 } 2094 2095 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) { 2096 // The result is the sum of all operands results. 2097 uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0), SE); 2098 uint32_t BitWidth = SE.getTypeSizeInBits(M->getType()); 2099 for (unsigned i = 1, e = M->getNumOperands(); 2100 SumOpRes != BitWidth && i != e; ++i) 2101 SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i), SE), 2102 BitWidth); 2103 return SumOpRes; 2104 } 2105 2106 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 2107 // The result is the min of all operands results. 2108 uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE); 2109 for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i) 2110 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), SE)); 2111 return MinOpRes; 2112 } 2113 2114 if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) { 2115 // The result is the min of all operands results. 2116 uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE); 2117 for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i) 2118 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), SE)); 2119 return MinOpRes; 2120 } 2121 2122 if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) { 2123 // The result is the min of all operands results. 2124 uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE); 2125 for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i) 2126 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), SE)); 2127 return MinOpRes; 2128 } 2129 2130 // SCEVUDivExpr, SCEVUnknown 2131 return 0; 2132} 2133 2134/// createSCEV - We know that there is no SCEV for the specified value. 2135/// Analyze the expression. 2136/// 2137SCEVHandle ScalarEvolution::createSCEV(Value *V) { 2138 if (!isSCEVable(V->getType())) 2139 return getUnknown(V); 2140 2141 unsigned Opcode = Instruction::UserOp1; 2142 if (Instruction *I = dyn_cast<Instruction>(V)) 2143 Opcode = I->getOpcode(); 2144 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 2145 Opcode = CE->getOpcode(); 2146 else 2147 return getUnknown(V); 2148 2149 User *U = cast<User>(V); 2150 switch (Opcode) { 2151 case Instruction::Add: 2152 return getAddExpr(getSCEV(U->getOperand(0)), 2153 getSCEV(U->getOperand(1))); 2154 case Instruction::Mul: 2155 return getMulExpr(getSCEV(U->getOperand(0)), 2156 getSCEV(U->getOperand(1))); 2157 case Instruction::UDiv: 2158 return getUDivExpr(getSCEV(U->getOperand(0)), 2159 getSCEV(U->getOperand(1))); 2160 case Instruction::Sub: 2161 return getMinusSCEV(getSCEV(U->getOperand(0)), 2162 getSCEV(U->getOperand(1))); 2163 case Instruction::And: 2164 // For an expression like x&255 that merely masks off the high bits, 2165 // use zext(trunc(x)) as the SCEV expression. 2166 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) { 2167 if (CI->isNullValue()) 2168 return getSCEV(U->getOperand(1)); 2169 if (CI->isAllOnesValue()) 2170 return getSCEV(U->getOperand(0)); 2171 const APInt &A = CI->getValue(); 2172 unsigned Ones = A.countTrailingOnes(); 2173 if (APIntOps::isMask(Ones, A)) 2174 return 2175 getZeroExtendExpr(getTruncateExpr(getSCEV(U->getOperand(0)), 2176 IntegerType::get(Ones)), 2177 U->getType()); 2178 } 2179 break; 2180 case Instruction::Or: 2181 // If the RHS of the Or is a constant, we may have something like: 2182 // X*4+1 which got turned into X*4|1. Handle this as an Add so loop 2183 // optimizations will transparently handle this case. 2184 // 2185 // In order for this transformation to be safe, the LHS must be of the 2186 // form X*(2^n) and the Or constant must be less than 2^n. 2187 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) { 2188 SCEVHandle LHS = getSCEV(U->getOperand(0)); 2189 const APInt &CIVal = CI->getValue(); 2190 if (GetMinTrailingZeros(LHS, *this) >= 2191 (CIVal.getBitWidth() - CIVal.countLeadingZeros())) 2192 return getAddExpr(LHS, getSCEV(U->getOperand(1))); 2193 } 2194 break; 2195 case Instruction::Xor: 2196 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) { 2197 // If the RHS of the xor is a signbit, then this is just an add. 2198 // Instcombine turns add of signbit into xor as a strength reduction step. 2199 if (CI->getValue().isSignBit()) 2200 return getAddExpr(getSCEV(U->getOperand(0)), 2201 getSCEV(U->getOperand(1))); 2202 2203 // If the RHS of xor is -1, then this is a not operation. 2204 if (CI->isAllOnesValue()) 2205 return getNotSCEV(getSCEV(U->getOperand(0))); 2206 } 2207 break; 2208 2209 case Instruction::Shl: 2210 // Turn shift left of a constant amount into a multiply. 2211 if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) { 2212 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 2213 Constant *X = ConstantInt::get( 2214 APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth))); 2215 return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X)); 2216 } 2217 break; 2218 2219 case Instruction::LShr: 2220 // Turn logical shift right of a constant into a unsigned divide. 2221 if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) { 2222 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 2223 Constant *X = ConstantInt::get( 2224 APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth))); 2225 return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X)); 2226 } 2227 break; 2228 2229 case Instruction::AShr: 2230 // For a two-shift sext-inreg, use sext(trunc(x)) as the SCEV expression. 2231 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) 2232 if (Instruction *L = dyn_cast<Instruction>(U->getOperand(0))) 2233 if (L->getOpcode() == Instruction::Shl && 2234 L->getOperand(1) == U->getOperand(1)) { 2235 unsigned BitWidth = getTypeSizeInBits(U->getType()); 2236 uint64_t Amt = BitWidth - CI->getZExtValue(); 2237 if (Amt == BitWidth) 2238 return getSCEV(L->getOperand(0)); // shift by zero --> noop 2239 if (Amt > BitWidth) 2240 return getIntegerSCEV(0, U->getType()); // value is undefined 2241 return 2242 getSignExtendExpr(getTruncateExpr(getSCEV(L->getOperand(0)), 2243 IntegerType::get(Amt)), 2244 U->getType()); 2245 } 2246 break; 2247 2248 case Instruction::Trunc: 2249 return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType()); 2250 2251 case Instruction::ZExt: 2252 return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType()); 2253 2254 case Instruction::SExt: 2255 return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType()); 2256 2257 case Instruction::BitCast: 2258 // BitCasts are no-op casts so we just eliminate the cast. 2259 if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) 2260 return getSCEV(U->getOperand(0)); 2261 break; 2262 2263 case Instruction::IntToPtr: 2264 if (!TD) break; // Without TD we can't analyze pointers. 2265 return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)), 2266 TD->getIntPtrType()); 2267 2268 case Instruction::PtrToInt: 2269 if (!TD) break; // Without TD we can't analyze pointers. 2270 return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)), 2271 U->getType()); 2272 2273 case Instruction::GetElementPtr: 2274 if (!TD) break; // Without TD we can't analyze pointers. 2275 return createNodeForGEP(U); 2276 2277 case Instruction::PHI: 2278 return createNodeForPHI(cast<PHINode>(U)); 2279 2280 case Instruction::Select: 2281 // This could be a smax or umax that was lowered earlier. 2282 // Try to recover it. 2283 if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) { 2284 Value *LHS = ICI->getOperand(0); 2285 Value *RHS = ICI->getOperand(1); 2286 switch (ICI->getPredicate()) { 2287 case ICmpInst::ICMP_SLT: 2288 case ICmpInst::ICMP_SLE: 2289 std::swap(LHS, RHS); 2290 // fall through 2291 case ICmpInst::ICMP_SGT: 2292 case ICmpInst::ICMP_SGE: 2293 if (LHS == U->getOperand(1) && RHS == U->getOperand(2)) 2294 return getSMaxExpr(getSCEV(LHS), getSCEV(RHS)); 2295 else if (LHS == U->getOperand(2) && RHS == U->getOperand(1)) 2296 // ~smax(~x, ~y) == smin(x, y). 2297 return getNotSCEV(getSMaxExpr( 2298 getNotSCEV(getSCEV(LHS)), 2299 getNotSCEV(getSCEV(RHS)))); 2300 break; 2301 case ICmpInst::ICMP_ULT: 2302 case ICmpInst::ICMP_ULE: 2303 std::swap(LHS, RHS); 2304 // fall through 2305 case ICmpInst::ICMP_UGT: 2306 case ICmpInst::ICMP_UGE: 2307 if (LHS == U->getOperand(1) && RHS == U->getOperand(2)) 2308 return getUMaxExpr(getSCEV(LHS), getSCEV(RHS)); 2309 else if (LHS == U->getOperand(2) && RHS == U->getOperand(1)) 2310 // ~umax(~x, ~y) == umin(x, y) 2311 return getNotSCEV(getUMaxExpr(getNotSCEV(getSCEV(LHS)), 2312 getNotSCEV(getSCEV(RHS)))); 2313 break; 2314 default: 2315 break; 2316 } 2317 } 2318 2319 default: // We cannot analyze this expression. 2320 break; 2321 } 2322 2323 return getUnknown(V); 2324} 2325 2326 2327 2328//===----------------------------------------------------------------------===// 2329// Iteration Count Computation Code 2330// 2331 2332/// getBackedgeTakenCount - If the specified loop has a predictable 2333/// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 2334/// object. The backedge-taken count is the number of times the loop header 2335/// will be branched to from within the loop. This is one less than the 2336/// trip count of the loop, since it doesn't count the first iteration, 2337/// when the header is branched to from outside the loop. 2338/// 2339/// Note that it is not valid to call this method on a loop without a 2340/// loop-invariant backedge-taken count (see 2341/// hasLoopInvariantBackedgeTakenCount). 2342/// 2343SCEVHandle ScalarEvolution::getBackedgeTakenCount(const Loop *L) { 2344 return getBackedgeTakenInfo(L).Exact; 2345} 2346 2347/// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 2348/// return the least SCEV value that is known never to be less than the 2349/// actual backedge taken count. 2350SCEVHandle ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) { 2351 return getBackedgeTakenInfo(L).Max; 2352} 2353 2354const ScalarEvolution::BackedgeTakenInfo & 2355ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { 2356 // Initially insert a CouldNotCompute for this loop. If the insertion 2357 // succeeds, procede to actually compute a backedge-taken count and 2358 // update the value. The temporary CouldNotCompute value tells SCEV 2359 // code elsewhere that it shouldn't attempt to request a new 2360 // backedge-taken count, which could result in infinite recursion. 2361 std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair = 2362 BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute())); 2363 if (Pair.second) { 2364 BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L); 2365 if (ItCount.Exact != UnknownValue) { 2366 assert(ItCount.Exact->isLoopInvariant(L) && 2367 ItCount.Max->isLoopInvariant(L) && 2368 "Computed trip count isn't loop invariant for loop!"); 2369 ++NumTripCountsComputed; 2370 2371 // Update the value in the map. 2372 Pair.first->second = ItCount; 2373 } else if (isa<PHINode>(L->getHeader()->begin())) { 2374 // Only count loops that have phi nodes as not being computable. 2375 ++NumTripCountsNotComputed; 2376 } 2377 2378 // Now that we know more about the trip count for this loop, forget any 2379 // existing SCEV values for PHI nodes in this loop since they are only 2380 // conservative estimates made without the benefit 2381 // of trip count information. 2382 if (ItCount.hasAnyInfo()) 2383 forgetLoopPHIs(L); 2384 } 2385 return Pair.first->second; 2386} 2387 2388/// forgetLoopBackedgeTakenCount - This method should be called by the 2389/// client when it has changed a loop in a way that may effect 2390/// ScalarEvolution's ability to compute a trip count, or if the loop 2391/// is deleted. 2392void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) { 2393 BackedgeTakenCounts.erase(L); 2394 forgetLoopPHIs(L); 2395} 2396 2397/// forgetLoopPHIs - Delete the memoized SCEVs associated with the 2398/// PHI nodes in the given loop. This is used when the trip count of 2399/// the loop may have changed. 2400void ScalarEvolution::forgetLoopPHIs(const Loop *L) { 2401 BasicBlock *Header = L->getHeader(); 2402 2403 // Push all Loop-header PHIs onto the Worklist stack, except those 2404 // that are presently represented via a SCEVUnknown. SCEVUnknown for 2405 // a PHI either means that it has an unrecognized structure, or it's 2406 // a PHI that's in the progress of being computed by createNodeForPHI. 2407 // In the former case, additional loop trip count information isn't 2408 // going to change anything. In the later case, createNodeForPHI will 2409 // perform the necessary updates on its own when it gets to that point. 2410 SmallVector<Instruction *, 16> Worklist; 2411 for (BasicBlock::iterator I = Header->begin(); 2412 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 2413 std::map<SCEVCallbackVH, SCEVHandle>::iterator It = Scalars.find((Value*)I); 2414 if (It != Scalars.end() && !isa<SCEVUnknown>(It->second)) 2415 Worklist.push_back(PN); 2416 } 2417 2418 while (!Worklist.empty()) { 2419 Instruction *I = Worklist.pop_back_val(); 2420 if (Scalars.erase(I)) 2421 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 2422 UI != UE; ++UI) 2423 Worklist.push_back(cast<Instruction>(UI)); 2424 } 2425} 2426 2427/// ComputeBackedgeTakenCount - Compute the number of times the backedge 2428/// of the specified loop will execute. 2429ScalarEvolution::BackedgeTakenInfo 2430ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) { 2431 // If the loop has a non-one exit block count, we can't analyze it. 2432 SmallVector<BasicBlock*, 8> ExitBlocks; 2433 L->getExitBlocks(ExitBlocks); 2434 if (ExitBlocks.size() != 1) return UnknownValue; 2435 2436 // Okay, there is one exit block. Try to find the condition that causes the 2437 // loop to be exited. 2438 BasicBlock *ExitBlock = ExitBlocks[0]; 2439 2440 BasicBlock *ExitingBlock = 0; 2441 for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock); 2442 PI != E; ++PI) 2443 if (L->contains(*PI)) { 2444 if (ExitingBlock == 0) 2445 ExitingBlock = *PI; 2446 else 2447 return UnknownValue; // More than one block exiting! 2448 } 2449 assert(ExitingBlock && "No exits from loop, something is broken!"); 2450 2451 // Okay, we've computed the exiting block. See what condition causes us to 2452 // exit. 2453 // 2454 // FIXME: we should be able to handle switch instructions (with a single exit) 2455 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 2456 if (ExitBr == 0) return UnknownValue; 2457 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!"); 2458 2459 // At this point, we know we have a conditional branch that determines whether 2460 // the loop is exited. However, we don't know if the branch is executed each 2461 // time through the loop. If not, then the execution count of the branch will 2462 // not be equal to the trip count of the loop. 2463 // 2464 // Currently we check for this by checking to see if the Exit branch goes to 2465 // the loop header. If so, we know it will always execute the same number of 2466 // times as the loop. We also handle the case where the exit block *is* the 2467 // loop header. This is common for un-rotated loops. More extensive analysis 2468 // could be done to handle more cases here. 2469 if (ExitBr->getSuccessor(0) != L->getHeader() && 2470 ExitBr->getSuccessor(1) != L->getHeader() && 2471 ExitBr->getParent() != L->getHeader()) 2472 return UnknownValue; 2473 2474 ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition()); 2475 2476 // If it's not an integer or pointer comparison then compute it the hard way. 2477 if (ExitCond == 0) 2478 return ComputeBackedgeTakenCountExhaustively(L, ExitBr->getCondition(), 2479 ExitBr->getSuccessor(0) == ExitBlock); 2480 2481 // If the condition was exit on true, convert the condition to exit on false 2482 ICmpInst::Predicate Cond; 2483 if (ExitBr->getSuccessor(1) == ExitBlock) 2484 Cond = ExitCond->getPredicate(); 2485 else 2486 Cond = ExitCond->getInversePredicate(); 2487 2488 // Handle common loops like: for (X = "string"; *X; ++X) 2489 if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0))) 2490 if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) { 2491 SCEVHandle ItCnt = 2492 ComputeLoadConstantCompareBackedgeTakenCount(LI, RHS, L, Cond); 2493 if (!isa<SCEVCouldNotCompute>(ItCnt)) return ItCnt; 2494 } 2495 2496 SCEVHandle LHS = getSCEV(ExitCond->getOperand(0)); 2497 SCEVHandle RHS = getSCEV(ExitCond->getOperand(1)); 2498 2499 // Try to evaluate any dependencies out of the loop. 2500 SCEVHandle Tmp = getSCEVAtScope(LHS, L); 2501 if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp; 2502 Tmp = getSCEVAtScope(RHS, L); 2503 if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp; 2504 2505 // At this point, we would like to compute how many iterations of the 2506 // loop the predicate will return true for these inputs. 2507 if (LHS->isLoopInvariant(L) && !RHS->isLoopInvariant(L)) { 2508 // If there is a loop-invariant, force it into the RHS. 2509 std::swap(LHS, RHS); 2510 Cond = ICmpInst::getSwappedPredicate(Cond); 2511 } 2512 2513 // If we have a comparison of a chrec against a constant, try to use value 2514 // ranges to answer this query. 2515 if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) 2516 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS)) 2517 if (AddRec->getLoop() == L) { 2518 // Form the constant range. 2519 ConstantRange CompRange( 2520 ICmpInst::makeConstantRange(Cond, RHSC->getValue()->getValue())); 2521 2522 SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, *this); 2523 if (!isa<SCEVCouldNotCompute>(Ret)) return Ret; 2524 } 2525 2526 switch (Cond) { 2527 case ICmpInst::ICMP_NE: { // while (X != Y) 2528 // Convert to: while (X-Y != 0) 2529 SCEVHandle TC = HowFarToZero(getMinusSCEV(LHS, RHS), L); 2530 if (!isa<SCEVCouldNotCompute>(TC)) return TC; 2531 break; 2532 } 2533 case ICmpInst::ICMP_EQ: { 2534 // Convert to: while (X-Y == 0) // while (X == Y) 2535 SCEVHandle TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L); 2536 if (!isa<SCEVCouldNotCompute>(TC)) return TC; 2537 break; 2538 } 2539 case ICmpInst::ICMP_SLT: { 2540 BackedgeTakenInfo BTI = HowManyLessThans(LHS, RHS, L, true); 2541 if (BTI.hasAnyInfo()) return BTI; 2542 break; 2543 } 2544 case ICmpInst::ICMP_SGT: { 2545 BackedgeTakenInfo BTI = HowManyLessThans(getNotSCEV(LHS), 2546 getNotSCEV(RHS), L, true); 2547 if (BTI.hasAnyInfo()) return BTI; 2548 break; 2549 } 2550 case ICmpInst::ICMP_ULT: { 2551 BackedgeTakenInfo BTI = HowManyLessThans(LHS, RHS, L, false); 2552 if (BTI.hasAnyInfo()) return BTI; 2553 break; 2554 } 2555 case ICmpInst::ICMP_UGT: { 2556 BackedgeTakenInfo BTI = HowManyLessThans(getNotSCEV(LHS), 2557 getNotSCEV(RHS), L, false); 2558 if (BTI.hasAnyInfo()) return BTI; 2559 break; 2560 } 2561 default: 2562#if 0 2563 errs() << "ComputeBackedgeTakenCount "; 2564 if (ExitCond->getOperand(0)->getType()->isUnsigned()) 2565 errs() << "[unsigned] "; 2566 errs() << *LHS << " " 2567 << Instruction::getOpcodeName(Instruction::ICmp) 2568 << " " << *RHS << "\n"; 2569#endif 2570 break; 2571 } 2572 return 2573 ComputeBackedgeTakenCountExhaustively(L, ExitCond, 2574 ExitBr->getSuccessor(0) == ExitBlock); 2575} 2576 2577static ConstantInt * 2578EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, 2579 ScalarEvolution &SE) { 2580 SCEVHandle InVal = SE.getConstant(C); 2581 SCEVHandle Val = AddRec->evaluateAtIteration(InVal, SE); 2582 assert(isa<SCEVConstant>(Val) && 2583 "Evaluation of SCEV at constant didn't fold correctly?"); 2584 return cast<SCEVConstant>(Val)->getValue(); 2585} 2586 2587/// GetAddressedElementFromGlobal - Given a global variable with an initializer 2588/// and a GEP expression (missing the pointer index) indexing into it, return 2589/// the addressed element of the initializer or null if the index expression is 2590/// invalid. 2591static Constant * 2592GetAddressedElementFromGlobal(GlobalVariable *GV, 2593 const std::vector<ConstantInt*> &Indices) { 2594 Constant *Init = GV->getInitializer(); 2595 for (unsigned i = 0, e = Indices.size(); i != e; ++i) { 2596 uint64_t Idx = Indices[i]->getZExtValue(); 2597 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) { 2598 assert(Idx < CS->getNumOperands() && "Bad struct index!"); 2599 Init = cast<Constant>(CS->getOperand(Idx)); 2600 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) { 2601 if (Idx >= CA->getNumOperands()) return 0; // Bogus program 2602 Init = cast<Constant>(CA->getOperand(Idx)); 2603 } else if (isa<ConstantAggregateZero>(Init)) { 2604 if (const StructType *STy = dyn_cast<StructType>(Init->getType())) { 2605 assert(Idx < STy->getNumElements() && "Bad struct index!"); 2606 Init = Constant::getNullValue(STy->getElementType(Idx)); 2607 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) { 2608 if (Idx >= ATy->getNumElements()) return 0; // Bogus program 2609 Init = Constant::getNullValue(ATy->getElementType()); 2610 } else { 2611 assert(0 && "Unknown constant aggregate type!"); 2612 } 2613 return 0; 2614 } else { 2615 return 0; // Unknown initializer type 2616 } 2617 } 2618 return Init; 2619} 2620 2621/// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of 2622/// 'icmp op load X, cst', try to see if we can compute the backedge 2623/// execution count. 2624SCEVHandle ScalarEvolution:: 2625ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS, 2626 const Loop *L, 2627 ICmpInst::Predicate predicate) { 2628 if (LI->isVolatile()) return UnknownValue; 2629 2630 // Check to see if the loaded pointer is a getelementptr of a global. 2631 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0)); 2632 if (!GEP) return UnknownValue; 2633 2634 // Make sure that it is really a constant global we are gepping, with an 2635 // initializer, and make sure the first IDX is really 0. 2636 GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)); 2637 if (!GV || !GV->isConstant() || !GV->hasInitializer() || 2638 GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) || 2639 !cast<Constant>(GEP->getOperand(1))->isNullValue()) 2640 return UnknownValue; 2641 2642 // Okay, we allow one non-constant index into the GEP instruction. 2643 Value *VarIdx = 0; 2644 std::vector<ConstantInt*> Indexes; 2645 unsigned VarIdxNum = 0; 2646 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) 2647 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) { 2648 Indexes.push_back(CI); 2649 } else if (!isa<ConstantInt>(GEP->getOperand(i))) { 2650 if (VarIdx) return UnknownValue; // Multiple non-constant idx's. 2651 VarIdx = GEP->getOperand(i); 2652 VarIdxNum = i-2; 2653 Indexes.push_back(0); 2654 } 2655 2656 // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant. 2657 // Check to see if X is a loop variant variable value now. 2658 SCEVHandle Idx = getSCEV(VarIdx); 2659 SCEVHandle Tmp = getSCEVAtScope(Idx, L); 2660 if (!isa<SCEVCouldNotCompute>(Tmp)) Idx = Tmp; 2661 2662 // We can only recognize very limited forms of loop index expressions, in 2663 // particular, only affine AddRec's like {C1,+,C2}. 2664 const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx); 2665 if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) || 2666 !isa<SCEVConstant>(IdxExpr->getOperand(0)) || 2667 !isa<SCEVConstant>(IdxExpr->getOperand(1))) 2668 return UnknownValue; 2669 2670 unsigned MaxSteps = MaxBruteForceIterations; 2671 for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) { 2672 ConstantInt *ItCst = 2673 ConstantInt::get(IdxExpr->getType(), IterationNum); 2674 ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this); 2675 2676 // Form the GEP offset. 2677 Indexes[VarIdxNum] = Val; 2678 2679 Constant *Result = GetAddressedElementFromGlobal(GV, Indexes); 2680 if (Result == 0) break; // Cannot compute! 2681 2682 // Evaluate the condition for this iteration. 2683 Result = ConstantExpr::getICmp(predicate, Result, RHS); 2684 if (!isa<ConstantInt>(Result)) break; // Couldn't decide for sure 2685 if (cast<ConstantInt>(Result)->getValue().isMinValue()) { 2686#if 0 2687 errs() << "\n***\n*** Computed loop count " << *ItCst 2688 << "\n*** From global " << *GV << "*** BB: " << *L->getHeader() 2689 << "***\n"; 2690#endif 2691 ++NumArrayLenItCounts; 2692 return getConstant(ItCst); // Found terminating iteration! 2693 } 2694 } 2695 return UnknownValue; 2696} 2697 2698 2699/// CanConstantFold - Return true if we can constant fold an instruction of the 2700/// specified type, assuming that all operands were constants. 2701static bool CanConstantFold(const Instruction *I) { 2702 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) || 2703 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I)) 2704 return true; 2705 2706 if (const CallInst *CI = dyn_cast<CallInst>(I)) 2707 if (const Function *F = CI->getCalledFunction()) 2708 return canConstantFoldCallTo(F); 2709 return false; 2710} 2711 2712/// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node 2713/// in the loop that V is derived from. We allow arbitrary operations along the 2714/// way, but the operands of an operation must either be constants or a value 2715/// derived from a constant PHI. If this expression does not fit with these 2716/// constraints, return null. 2717static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { 2718 // If this is not an instruction, or if this is an instruction outside of the 2719 // loop, it can't be derived from a loop PHI. 2720 Instruction *I = dyn_cast<Instruction>(V); 2721 if (I == 0 || !L->contains(I->getParent())) return 0; 2722 2723 if (PHINode *PN = dyn_cast<PHINode>(I)) { 2724 if (L->getHeader() == I->getParent()) 2725 return PN; 2726 else 2727 // We don't currently keep track of the control flow needed to evaluate 2728 // PHIs, so we cannot handle PHIs inside of loops. 2729 return 0; 2730 } 2731 2732 // If we won't be able to constant fold this expression even if the operands 2733 // are constants, return early. 2734 if (!CanConstantFold(I)) return 0; 2735 2736 // Otherwise, we can evaluate this instruction if all of its operands are 2737 // constant or derived from a PHI node themselves. 2738 PHINode *PHI = 0; 2739 for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op) 2740 if (!(isa<Constant>(I->getOperand(Op)) || 2741 isa<GlobalValue>(I->getOperand(Op)))) { 2742 PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L); 2743 if (P == 0) return 0; // Not evolving from PHI 2744 if (PHI == 0) 2745 PHI = P; 2746 else if (PHI != P) 2747 return 0; // Evolving from multiple different PHIs. 2748 } 2749 2750 // This is a expression evolving from a constant PHI! 2751 return PHI; 2752} 2753 2754/// EvaluateExpression - Given an expression that passes the 2755/// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node 2756/// in the loop has the value PHIVal. If we can't fold this expression for some 2757/// reason, return null. 2758static Constant *EvaluateExpression(Value *V, Constant *PHIVal) { 2759 if (isa<PHINode>(V)) return PHIVal; 2760 if (Constant *C = dyn_cast<Constant>(V)) return C; 2761 if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV; 2762 Instruction *I = cast<Instruction>(V); 2763 2764 std::vector<Constant*> Operands; 2765 Operands.resize(I->getNumOperands()); 2766 2767 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 2768 Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal); 2769 if (Operands[i] == 0) return 0; 2770 } 2771 2772 if (const CmpInst *CI = dyn_cast<CmpInst>(I)) 2773 return ConstantFoldCompareInstOperands(CI->getPredicate(), 2774 &Operands[0], Operands.size()); 2775 else 2776 return ConstantFoldInstOperands(I->getOpcode(), I->getType(), 2777 &Operands[0], Operands.size()); 2778} 2779 2780/// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 2781/// in the header of its containing loop, we know the loop executes a 2782/// constant number of times, and the PHI node is just a recurrence 2783/// involving constants, fold it. 2784Constant *ScalarEvolution:: 2785getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L){ 2786 std::map<PHINode*, Constant*>::iterator I = 2787 ConstantEvolutionLoopExitValue.find(PN); 2788 if (I != ConstantEvolutionLoopExitValue.end()) 2789 return I->second; 2790 2791 if (BEs.ugt(APInt(BEs.getBitWidth(),MaxBruteForceIterations))) 2792 return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it. 2793 2794 Constant *&RetVal = ConstantEvolutionLoopExitValue[PN]; 2795 2796 // Since the loop is canonicalized, the PHI node must have two entries. One 2797 // entry must be a constant (coming in from outside of the loop), and the 2798 // second must be derived from the same PHI. 2799 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); 2800 Constant *StartCST = 2801 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge)); 2802 if (StartCST == 0) 2803 return RetVal = 0; // Must be a constant. 2804 2805 Value *BEValue = PN->getIncomingValue(SecondIsBackedge); 2806 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); 2807 if (PN2 != PN) 2808 return RetVal = 0; // Not derived from same PHI. 2809 2810 // Execute the loop symbolically to determine the exit value. 2811 if (BEs.getActiveBits() >= 32) 2812 return RetVal = 0; // More than 2^32-1 iterations?? Not doing it! 2813 2814 unsigned NumIterations = BEs.getZExtValue(); // must be in range 2815 unsigned IterationNum = 0; 2816 for (Constant *PHIVal = StartCST; ; ++IterationNum) { 2817 if (IterationNum == NumIterations) 2818 return RetVal = PHIVal; // Got exit value! 2819 2820 // Compute the value of the PHI node for the next iteration. 2821 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal); 2822 if (NextPHI == PHIVal) 2823 return RetVal = NextPHI; // Stopped evolving! 2824 if (NextPHI == 0) 2825 return 0; // Couldn't evaluate! 2826 PHIVal = NextPHI; 2827 } 2828} 2829 2830/// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute a 2831/// constant number of times (the condition evolves only from constants), 2832/// try to evaluate a few iterations of the loop until we get the exit 2833/// condition gets a value of ExitWhen (true or false). If we cannot 2834/// evaluate the trip count of the loop, return UnknownValue. 2835SCEVHandle ScalarEvolution:: 2836ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) { 2837 PHINode *PN = getConstantEvolvingPHI(Cond, L); 2838 if (PN == 0) return UnknownValue; 2839 2840 // Since the loop is canonicalized, the PHI node must have two entries. One 2841 // entry must be a constant (coming in from outside of the loop), and the 2842 // second must be derived from the same PHI. 2843 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); 2844 Constant *StartCST = 2845 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge)); 2846 if (StartCST == 0) return UnknownValue; // Must be a constant. 2847 2848 Value *BEValue = PN->getIncomingValue(SecondIsBackedge); 2849 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); 2850 if (PN2 != PN) return UnknownValue; // Not derived from same PHI. 2851 2852 // Okay, we find a PHI node that defines the trip count of this loop. Execute 2853 // the loop symbolically to determine when the condition gets a value of 2854 // "ExitWhen". 2855 unsigned IterationNum = 0; 2856 unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis. 2857 for (Constant *PHIVal = StartCST; 2858 IterationNum != MaxIterations; ++IterationNum) { 2859 ConstantInt *CondVal = 2860 dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal)); 2861 2862 // Couldn't symbolically evaluate. 2863 if (!CondVal) return UnknownValue; 2864 2865 if (CondVal->getValue() == uint64_t(ExitWhen)) { 2866 ConstantEvolutionLoopExitValue[PN] = PHIVal; 2867 ++NumBruteForceTripCountsComputed; 2868 return getConstant(ConstantInt::get(Type::Int32Ty, IterationNum)); 2869 } 2870 2871 // Compute the value of the PHI node for the next iteration. 2872 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal); 2873 if (NextPHI == 0 || NextPHI == PHIVal) 2874 return UnknownValue; // Couldn't evaluate or not making progress... 2875 PHIVal = NextPHI; 2876 } 2877 2878 // Too many iterations were needed to evaluate. 2879 return UnknownValue; 2880} 2881 2882/// getSCEVAtScope - Return a SCEV expression handle for the specified value 2883/// at the specified scope in the program. The L value specifies a loop 2884/// nest to evaluate the expression at, where null is the top-level or a 2885/// specified loop is immediately inside of the loop. 2886/// 2887/// This method can be used to compute the exit value for a variable defined 2888/// in a loop by querying what the value will hold in the parent loop. 2889/// 2890/// If this value is not computable at this scope, a SCEVCouldNotCompute 2891/// object is returned. 2892SCEVHandle ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { 2893 // FIXME: this should be turned into a virtual method on SCEV! 2894 2895 if (isa<SCEVConstant>(V)) return V; 2896 2897 // If this instruction is evolved from a constant-evolving PHI, compute the 2898 // exit value from the loop without using SCEVs. 2899 if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) { 2900 if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) { 2901 const Loop *LI = (*this->LI)[I->getParent()]; 2902 if (LI && LI->getParentLoop() == L) // Looking for loop exit value. 2903 if (PHINode *PN = dyn_cast<PHINode>(I)) 2904 if (PN->getParent() == LI->getHeader()) { 2905 // Okay, there is no closed form solution for the PHI node. Check 2906 // to see if the loop that contains it has a known backedge-taken 2907 // count. If so, we may be able to force computation of the exit 2908 // value. 2909 SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(LI); 2910 if (const SCEVConstant *BTCC = 2911 dyn_cast<SCEVConstant>(BackedgeTakenCount)) { 2912 // Okay, we know how many times the containing loop executes. If 2913 // this is a constant evolving PHI node, get the final value at 2914 // the specified iteration number. 2915 Constant *RV = getConstantEvolutionLoopExitValue(PN, 2916 BTCC->getValue()->getValue(), 2917 LI); 2918 if (RV) return getUnknown(RV); 2919 } 2920 } 2921 2922 // Okay, this is an expression that we cannot symbolically evaluate 2923 // into a SCEV. Check to see if it's possible to symbolically evaluate 2924 // the arguments into constants, and if so, try to constant propagate the 2925 // result. This is particularly useful for computing loop exit values. 2926 if (CanConstantFold(I)) { 2927 // Check to see if we've folded this instruction at this loop before. 2928 std::map<const Loop *, Constant *> &Values = ValuesAtScopes[I]; 2929 std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair = 2930 Values.insert(std::make_pair(L, static_cast<Constant *>(0))); 2931 if (!Pair.second) 2932 return Pair.first->second ? &*getUnknown(Pair.first->second) : V; 2933 2934 std::vector<Constant*> Operands; 2935 Operands.reserve(I->getNumOperands()); 2936 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 2937 Value *Op = I->getOperand(i); 2938 if (Constant *C = dyn_cast<Constant>(Op)) { 2939 Operands.push_back(C); 2940 } else { 2941 // If any of the operands is non-constant and if they are 2942 // non-integer and non-pointer, don't even try to analyze them 2943 // with scev techniques. 2944 if (!isSCEVable(Op->getType())) 2945 return V; 2946 2947 SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L); 2948 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) { 2949 Constant *C = SC->getValue(); 2950 if (C->getType() != Op->getType()) 2951 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 2952 Op->getType(), 2953 false), 2954 C, Op->getType()); 2955 Operands.push_back(C); 2956 } else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) { 2957 if (Constant *C = dyn_cast<Constant>(SU->getValue())) { 2958 if (C->getType() != Op->getType()) 2959 C = 2960 ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 2961 Op->getType(), 2962 false), 2963 C, Op->getType()); 2964 Operands.push_back(C); 2965 } else 2966 return V; 2967 } else { 2968 return V; 2969 } 2970 } 2971 } 2972 2973 Constant *C; 2974 if (const CmpInst *CI = dyn_cast<CmpInst>(I)) 2975 C = ConstantFoldCompareInstOperands(CI->getPredicate(), 2976 &Operands[0], Operands.size()); 2977 else 2978 C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), 2979 &Operands[0], Operands.size()); 2980 Pair.first->second = C; 2981 return getUnknown(C); 2982 } 2983 } 2984 2985 // This is some other type of SCEVUnknown, just return it. 2986 return V; 2987 } 2988 2989 if (const SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) { 2990 // Avoid performing the look-up in the common case where the specified 2991 // expression has no loop-variant portions. 2992 for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) { 2993 SCEVHandle OpAtScope = getSCEVAtScope(Comm->getOperand(i), L); 2994 if (OpAtScope != Comm->getOperand(i)) { 2995 if (OpAtScope == UnknownValue) return UnknownValue; 2996 // Okay, at least one of these operands is loop variant but might be 2997 // foldable. Build a new instance of the folded commutative expression. 2998 std::vector<SCEVHandle> NewOps(Comm->op_begin(), Comm->op_begin()+i); 2999 NewOps.push_back(OpAtScope); 3000 3001 for (++i; i != e; ++i) { 3002 OpAtScope = getSCEVAtScope(Comm->getOperand(i), L); 3003 if (OpAtScope == UnknownValue) return UnknownValue; 3004 NewOps.push_back(OpAtScope); 3005 } 3006 if (isa<SCEVAddExpr>(Comm)) 3007 return getAddExpr(NewOps); 3008 if (isa<SCEVMulExpr>(Comm)) 3009 return getMulExpr(NewOps); 3010 if (isa<SCEVSMaxExpr>(Comm)) 3011 return getSMaxExpr(NewOps); 3012 if (isa<SCEVUMaxExpr>(Comm)) 3013 return getUMaxExpr(NewOps); 3014 assert(0 && "Unknown commutative SCEV type!"); 3015 } 3016 } 3017 // If we got here, all operands are loop invariant. 3018 return Comm; 3019 } 3020 3021 if (const SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) { 3022 SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L); 3023 if (LHS == UnknownValue) return LHS; 3024 SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L); 3025 if (RHS == UnknownValue) return RHS; 3026 if (LHS == Div->getLHS() && RHS == Div->getRHS()) 3027 return Div; // must be loop invariant 3028 return getUDivExpr(LHS, RHS); 3029 } 3030 3031 // If this is a loop recurrence for a loop that does not contain L, then we 3032 // are dealing with the final value computed by the loop. 3033 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) { 3034 if (!L || !AddRec->getLoop()->contains(L->getHeader())) { 3035 // To evaluate this recurrence, we need to know how many times the AddRec 3036 // loop iterates. Compute this now. 3037 SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); 3038 if (BackedgeTakenCount == UnknownValue) return UnknownValue; 3039 3040 // Then, evaluate the AddRec. 3041 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this); 3042 } 3043 return UnknownValue; 3044 } 3045 3046 if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) { 3047 SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L); 3048 if (Op == UnknownValue) return Op; 3049 if (Op == Cast->getOperand()) 3050 return Cast; // must be loop invariant 3051 return getZeroExtendExpr(Op, Cast->getType()); 3052 } 3053 3054 if (const SCEVSignExtendExpr *Cast = dyn_cast<SCEVSignExtendExpr>(V)) { 3055 SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L); 3056 if (Op == UnknownValue) return Op; 3057 if (Op == Cast->getOperand()) 3058 return Cast; // must be loop invariant 3059 return getSignExtendExpr(Op, Cast->getType()); 3060 } 3061 3062 if (const SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) { 3063 SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L); 3064 if (Op == UnknownValue) return Op; 3065 if (Op == Cast->getOperand()) 3066 return Cast; // must be loop invariant 3067 return getTruncateExpr(Op, Cast->getType()); 3068 } 3069 3070 assert(0 && "Unknown SCEV type!"); 3071} 3072 3073/// getSCEVAtScope - This is a convenience function which does 3074/// getSCEVAtScope(getSCEV(V), L). 3075SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) { 3076 return getSCEVAtScope(getSCEV(V), L); 3077} 3078 3079/// SolveLinEquationWithOverflow - Finds the minimum unsigned root of the 3080/// following equation: 3081/// 3082/// A * X = B (mod N) 3083/// 3084/// where N = 2^BW and BW is the common bit width of A and B. The signedness of 3085/// A and B isn't important. 3086/// 3087/// If the equation does not have a solution, SCEVCouldNotCompute is returned. 3088static SCEVHandle SolveLinEquationWithOverflow(const APInt &A, const APInt &B, 3089 ScalarEvolution &SE) { 3090 uint32_t BW = A.getBitWidth(); 3091 assert(BW == B.getBitWidth() && "Bit widths must be the same."); 3092 assert(A != 0 && "A must be non-zero."); 3093 3094 // 1. D = gcd(A, N) 3095 // 3096 // The gcd of A and N may have only one prime factor: 2. The number of 3097 // trailing zeros in A is its multiplicity 3098 uint32_t Mult2 = A.countTrailingZeros(); 3099 // D = 2^Mult2 3100 3101 // 2. Check if B is divisible by D. 3102 // 3103 // B is divisible by D if and only if the multiplicity of prime factor 2 for B 3104 // is not less than multiplicity of this prime factor for D. 3105 if (B.countTrailingZeros() < Mult2) 3106 return SE.getCouldNotCompute(); 3107 3108 // 3. Compute I: the multiplicative inverse of (A / D) in arithmetic 3109 // modulo (N / D). 3110 // 3111 // (N / D) may need BW+1 bits in its representation. Hence, we'll use this 3112 // bit width during computations. 3113 APInt AD = A.lshr(Mult2).zext(BW + 1); // AD = A / D 3114 APInt Mod(BW + 1, 0); 3115 Mod.set(BW - Mult2); // Mod = N / D 3116 APInt I = AD.multiplicativeInverse(Mod); 3117 3118 // 4. Compute the minimum unsigned root of the equation: 3119 // I * (B / D) mod (N / D) 3120 APInt Result = (I * B.lshr(Mult2).zext(BW + 1)).urem(Mod); 3121 3122 // The result is guaranteed to be less than 2^BW so we may truncate it to BW 3123 // bits. 3124 return SE.getConstant(Result.trunc(BW)); 3125} 3126 3127/// SolveQuadraticEquation - Find the roots of the quadratic equation for the 3128/// given quadratic chrec {L,+,M,+,N}. This returns either the two roots (which 3129/// might be the same) or two SCEVCouldNotCompute objects. 3130/// 3131static std::pair<SCEVHandle,SCEVHandle> 3132SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { 3133 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!"); 3134 const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0)); 3135 const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1)); 3136 const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2)); 3137 3138 // We currently can only solve this if the coefficients are constants. 3139 if (!LC || !MC || !NC) { 3140 const SCEV *CNC = SE.getCouldNotCompute(); 3141 return std::make_pair(CNC, CNC); 3142 } 3143 3144 uint32_t BitWidth = LC->getValue()->getValue().getBitWidth(); 3145 const APInt &L = LC->getValue()->getValue(); 3146 const APInt &M = MC->getValue()->getValue(); 3147 const APInt &N = NC->getValue()->getValue(); 3148 APInt Two(BitWidth, 2); 3149 APInt Four(BitWidth, 4); 3150 3151 { 3152 using namespace APIntOps; 3153 const APInt& C = L; 3154 // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C 3155 // The B coefficient is M-N/2 3156 APInt B(M); 3157 B -= sdiv(N,Two); 3158 3159 // The A coefficient is N/2 3160 APInt A(N.sdiv(Two)); 3161 3162 // Compute the B^2-4ac term. 3163 APInt SqrtTerm(B); 3164 SqrtTerm *= B; 3165 SqrtTerm -= Four * (A * C); 3166 3167 // Compute sqrt(B^2-4ac). This is guaranteed to be the nearest 3168 // integer value or else APInt::sqrt() will assert. 3169 APInt SqrtVal(SqrtTerm.sqrt()); 3170 3171 // Compute the two solutions for the quadratic formula. 3172 // The divisions must be performed as signed divisions. 3173 APInt NegB(-B); 3174 APInt TwoA( A << 1 ); 3175 if (TwoA.isMinValue()) { 3176 const SCEV *CNC = SE.getCouldNotCompute(); 3177 return std::make_pair(CNC, CNC); 3178 } 3179 3180 ConstantInt *Solution1 = ConstantInt::get((NegB + SqrtVal).sdiv(TwoA)); 3181 ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA)); 3182 3183 return std::make_pair(SE.getConstant(Solution1), 3184 SE.getConstant(Solution2)); 3185 } // end APIntOps namespace 3186} 3187 3188/// HowFarToZero - Return the number of times a backedge comparing the specified 3189/// value to zero will execute. If not computable, return UnknownValue 3190SCEVHandle ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { 3191 // If the value is a constant 3192 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) { 3193 // If the value is already zero, the branch will execute zero times. 3194 if (C->getValue()->isZero()) return C; 3195 return UnknownValue; // Otherwise it will loop infinitely. 3196 } 3197 3198 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V); 3199 if (!AddRec || AddRec->getLoop() != L) 3200 return UnknownValue; 3201 3202 if (AddRec->isAffine()) { 3203 // If this is an affine expression, the execution count of this branch is 3204 // the minimum unsigned root of the following equation: 3205 // 3206 // Start + Step*N = 0 (mod 2^BW) 3207 // 3208 // equivalent to: 3209 // 3210 // Step*N = -Start (mod 2^BW) 3211 // 3212 // where BW is the common bit width of Start and Step. 3213 3214 // Get the initial value for the loop. 3215 SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop()); 3216 if (isa<SCEVCouldNotCompute>(Start)) return UnknownValue; 3217 3218 SCEVHandle Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop()); 3219 3220 if (const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) { 3221 // For now we handle only constant steps. 3222 3223 // First, handle unitary steps. 3224 if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so: 3225 return getNegativeSCEV(Start); // N = -Start (as unsigned) 3226 if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so: 3227 return Start; // N = Start (as unsigned) 3228 3229 // Then, try to solve the above equation provided that Start is constant. 3230 if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) 3231 return SolveLinEquationWithOverflow(StepC->getValue()->getValue(), 3232 -StartC->getValue()->getValue(), 3233 *this); 3234 } 3235 } else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) { 3236 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of 3237 // the quadratic equation to solve it. 3238 std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec, 3239 *this); 3240 const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first); 3241 const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second); 3242 if (R1) { 3243#if 0 3244 errs() << "HFTZ: " << *V << " - sol#1: " << *R1 3245 << " sol#2: " << *R2 << "\n"; 3246#endif 3247 // Pick the smallest positive root value. 3248 if (ConstantInt *CB = 3249 dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, 3250 R1->getValue(), R2->getValue()))) { 3251 if (CB->getZExtValue() == false) 3252 std::swap(R1, R2); // R1 is the minimum root now. 3253 3254 // We can only use this value if the chrec ends up with an exact zero 3255 // value at this index. When solving for "X*X != 5", for example, we 3256 // should not accept a root of 2. 3257 SCEVHandle Val = AddRec->evaluateAtIteration(R1, *this); 3258 if (Val->isZero()) 3259 return R1; // We found a quadratic root! 3260 } 3261 } 3262 } 3263 3264 return UnknownValue; 3265} 3266 3267/// HowFarToNonZero - Return the number of times a backedge checking the 3268/// specified value for nonzero will execute. If not computable, return 3269/// UnknownValue 3270SCEVHandle ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) { 3271 // Loops that look like: while (X == 0) are very strange indeed. We don't 3272 // handle them yet except for the trivial case. This could be expanded in the 3273 // future as needed. 3274 3275 // If the value is a constant, check to see if it is known to be non-zero 3276 // already. If so, the backedge will execute zero times. 3277 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) { 3278 if (!C->getValue()->isNullValue()) 3279 return getIntegerSCEV(0, C->getType()); 3280 return UnknownValue; // Otherwise it will loop infinitely. 3281 } 3282 3283 // We could implement others, but I really doubt anyone writes loops like 3284 // this, and if they did, they would already be constant folded. 3285 return UnknownValue; 3286} 3287 3288/// getLoopPredecessor - If the given loop's header has exactly one unique 3289/// predecessor outside the loop, return it. Otherwise return null. 3290/// 3291BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) { 3292 BasicBlock *Header = L->getHeader(); 3293 BasicBlock *Pred = 0; 3294 for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); 3295 PI != E; ++PI) 3296 if (!L->contains(*PI)) { 3297 if (Pred && Pred != *PI) return 0; // Multiple predecessors. 3298 Pred = *PI; 3299 } 3300 return Pred; 3301} 3302 3303/// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 3304/// (which may not be an immediate predecessor) which has exactly one 3305/// successor from which BB is reachable, or null if no such block is 3306/// found. 3307/// 3308BasicBlock * 3309ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) { 3310 // If the block has a unique predecessor, then there is no path from the 3311 // predecessor to the block that does not go through the direct edge 3312 // from the predecessor to the block. 3313 if (BasicBlock *Pred = BB->getSinglePredecessor()) 3314 return Pred; 3315 3316 // A loop's header is defined to be a block that dominates the loop. 3317 // If the header has a unique predecessor outside the loop, it must be 3318 // a block that has exactly one successor that can reach the loop. 3319 if (Loop *L = LI->getLoopFor(BB)) 3320 return getLoopPredecessor(L); 3321 3322 return 0; 3323} 3324 3325/// isLoopGuardedByCond - Test whether entry to the loop is protected by 3326/// a conditional between LHS and RHS. This is used to help avoid max 3327/// expressions in loop trip counts. 3328bool ScalarEvolution::isLoopGuardedByCond(const Loop *L, 3329 ICmpInst::Predicate Pred, 3330 const SCEV *LHS, const SCEV *RHS) { 3331 // Interpret a null as meaning no loop, where there is obviously no guard 3332 // (interprocedural conditions notwithstanding). 3333 if (!L) return false; 3334 3335 BasicBlock *Predecessor = getLoopPredecessor(L); 3336 BasicBlock *PredecessorDest = L->getHeader(); 3337 3338 // Starting at the loop predecessor, climb up the predecessor chain, as long 3339 // as there are predecessors that can be found that have unique successors 3340 // leading to the original header. 3341 for (; Predecessor; 3342 PredecessorDest = Predecessor, 3343 Predecessor = getPredecessorWithUniqueSuccessorForBB(Predecessor)) { 3344 3345 BranchInst *LoopEntryPredicate = 3346 dyn_cast<BranchInst>(Predecessor->getTerminator()); 3347 if (!LoopEntryPredicate || 3348 LoopEntryPredicate->isUnconditional()) 3349 continue; 3350 3351 ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition()); 3352 if (!ICI) continue; 3353 3354 // Now that we found a conditional branch that dominates the loop, check to 3355 // see if it is the comparison we are looking for. 3356 Value *PreCondLHS = ICI->getOperand(0); 3357 Value *PreCondRHS = ICI->getOperand(1); 3358 ICmpInst::Predicate Cond; 3359 if (LoopEntryPredicate->getSuccessor(0) == PredecessorDest) 3360 Cond = ICI->getPredicate(); 3361 else 3362 Cond = ICI->getInversePredicate(); 3363 3364 if (Cond == Pred) 3365 ; // An exact match. 3366 else if (!ICmpInst::isTrueWhenEqual(Cond) && Pred == ICmpInst::ICMP_NE) 3367 ; // The actual condition is beyond sufficient. 3368 else 3369 // Check a few special cases. 3370 switch (Cond) { 3371 case ICmpInst::ICMP_UGT: 3372 if (Pred == ICmpInst::ICMP_ULT) { 3373 std::swap(PreCondLHS, PreCondRHS); 3374 Cond = ICmpInst::ICMP_ULT; 3375 break; 3376 } 3377 continue; 3378 case ICmpInst::ICMP_SGT: 3379 if (Pred == ICmpInst::ICMP_SLT) { 3380 std::swap(PreCondLHS, PreCondRHS); 3381 Cond = ICmpInst::ICMP_SLT; 3382 break; 3383 } 3384 continue; 3385 case ICmpInst::ICMP_NE: 3386 // Expressions like (x >u 0) are often canonicalized to (x != 0), 3387 // so check for this case by checking if the NE is comparing against 3388 // a minimum or maximum constant. 3389 if (!ICmpInst::isTrueWhenEqual(Pred)) 3390 if (ConstantInt *CI = dyn_cast<ConstantInt>(PreCondRHS)) { 3391 const APInt &A = CI->getValue(); 3392 switch (Pred) { 3393 case ICmpInst::ICMP_SLT: 3394 if (A.isMaxSignedValue()) break; 3395 continue; 3396 case ICmpInst::ICMP_SGT: 3397 if (A.isMinSignedValue()) break; 3398 continue; 3399 case ICmpInst::ICMP_ULT: 3400 if (A.isMaxValue()) break; 3401 continue; 3402 case ICmpInst::ICMP_UGT: 3403 if (A.isMinValue()) break; 3404 continue; 3405 default: 3406 continue; 3407 } 3408 Cond = ICmpInst::ICMP_NE; 3409 // NE is symmetric but the original comparison may not be. Swap 3410 // the operands if necessary so that they match below. 3411 if (isa<SCEVConstant>(LHS)) 3412 std::swap(PreCondLHS, PreCondRHS); 3413 break; 3414 } 3415 continue; 3416 default: 3417 // We weren't able to reconcile the condition. 3418 continue; 3419 } 3420 3421 if (!PreCondLHS->getType()->isInteger()) continue; 3422 3423 SCEVHandle PreCondLHSSCEV = getSCEV(PreCondLHS); 3424 SCEVHandle PreCondRHSSCEV = getSCEV(PreCondRHS); 3425 if ((LHS == PreCondLHSSCEV && RHS == PreCondRHSSCEV) || 3426 (LHS == getNotSCEV(PreCondRHSSCEV) && 3427 RHS == getNotSCEV(PreCondLHSSCEV))) 3428 return true; 3429 } 3430 3431 return false; 3432} 3433 3434/// HowManyLessThans - Return the number of times a backedge containing the 3435/// specified less-than comparison will execute. If not computable, return 3436/// UnknownValue. 3437ScalarEvolution::BackedgeTakenInfo ScalarEvolution:: 3438HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 3439 const Loop *L, bool isSigned) { 3440 // Only handle: "ADDREC < LoopInvariant". 3441 if (!RHS->isLoopInvariant(L)) return UnknownValue; 3442 3443 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS); 3444 if (!AddRec || AddRec->getLoop() != L) 3445 return UnknownValue; 3446 3447 if (AddRec->isAffine()) { 3448 // FORNOW: We only support unit strides. 3449 unsigned BitWidth = getTypeSizeInBits(AddRec->getType()); 3450 SCEVHandle Step = AddRec->getStepRecurrence(*this); 3451 SCEVHandle NegOne = getIntegerSCEV(-1, AddRec->getType()); 3452 3453 // TODO: handle non-constant strides. 3454 const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step); 3455 if (!CStep || CStep->isZero()) 3456 return UnknownValue; 3457 if (CStep->isOne()) { 3458 // With unit stride, the iteration never steps past the limit value. 3459 } else if (CStep->getValue()->getValue().isStrictlyPositive()) { 3460 if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) { 3461 // Test whether a positive iteration iteration can step past the limit 3462 // value and past the maximum value for its type in a single step. 3463 if (isSigned) { 3464 APInt Max = APInt::getSignedMaxValue(BitWidth); 3465 if ((Max - CStep->getValue()->getValue()) 3466 .slt(CLimit->getValue()->getValue())) 3467 return UnknownValue; 3468 } else { 3469 APInt Max = APInt::getMaxValue(BitWidth); 3470 if ((Max - CStep->getValue()->getValue()) 3471 .ult(CLimit->getValue()->getValue())) 3472 return UnknownValue; 3473 } 3474 } else 3475 // TODO: handle non-constant limit values below. 3476 return UnknownValue; 3477 } else 3478 // TODO: handle negative strides below. 3479 return UnknownValue; 3480 3481 // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant 3482 // m. So, we count the number of iterations in which {n,+,s} < m is true. 3483 // Note that we cannot simply return max(m-n,0)/s because it's not safe to 3484 // treat m-n as signed nor unsigned due to overflow possibility. 3485 3486 // First, we get the value of the LHS in the first iteration: n 3487 SCEVHandle Start = AddRec->getOperand(0); 3488 3489 // Determine the minimum constant start value. 3490 SCEVHandle MinStart = isa<SCEVConstant>(Start) ? Start : 3491 getConstant(isSigned ? APInt::getSignedMinValue(BitWidth) : 3492 APInt::getMinValue(BitWidth)); 3493 3494 // If we know that the condition is true in order to enter the loop, 3495 // then we know that it will run exactly (m-n)/s times. Otherwise, we 3496 // only know if will execute (max(m,n)-n)/s times. In both cases, the 3497 // division must round up. 3498 SCEVHandle End = RHS; 3499 if (!isLoopGuardedByCond(L, 3500 isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, 3501 getMinusSCEV(Start, Step), RHS)) 3502 End = isSigned ? getSMaxExpr(RHS, Start) 3503 : getUMaxExpr(RHS, Start); 3504 3505 // Determine the maximum constant end value. 3506 SCEVHandle MaxEnd = isa<SCEVConstant>(End) ? End : 3507 getConstant(isSigned ? APInt::getSignedMaxValue(BitWidth) : 3508 APInt::getMaxValue(BitWidth)); 3509 3510 // Finally, we subtract these two values and divide, rounding up, to get 3511 // the number of times the backedge is executed. 3512 SCEVHandle BECount = getUDivExpr(getAddExpr(getMinusSCEV(End, Start), 3513 getAddExpr(Step, NegOne)), 3514 Step); 3515 3516 // The maximum backedge count is similar, except using the minimum start 3517 // value and the maximum end value. 3518 SCEVHandle MaxBECount = getUDivExpr(getAddExpr(getMinusSCEV(MaxEnd, 3519 MinStart), 3520 getAddExpr(Step, NegOne)), 3521 Step); 3522 3523 return BackedgeTakenInfo(BECount, MaxBECount); 3524 } 3525 3526 return UnknownValue; 3527} 3528 3529/// getNumIterationsInRange - Return the number of iterations of this loop that 3530/// produce values in the specified constant range. Another way of looking at 3531/// this is that it returns the first iteration number where the value is not in 3532/// the condition, thus computing the exit count. If the iteration count can't 3533/// be computed, an instance of SCEVCouldNotCompute is returned. 3534SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, 3535 ScalarEvolution &SE) const { 3536 if (Range.isFullSet()) // Infinite loop. 3537 return SE.getCouldNotCompute(); 3538 3539 // If the start is a non-zero constant, shift the range to simplify things. 3540 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart())) 3541 if (!SC->getValue()->isZero()) { 3542 std::vector<SCEVHandle> Operands(op_begin(), op_end()); 3543 Operands[0] = SE.getIntegerSCEV(0, SC->getType()); 3544 SCEVHandle Shifted = SE.getAddRecExpr(Operands, getLoop()); 3545 if (const SCEVAddRecExpr *ShiftedAddRec = 3546 dyn_cast<SCEVAddRecExpr>(Shifted)) 3547 return ShiftedAddRec->getNumIterationsInRange( 3548 Range.subtract(SC->getValue()->getValue()), SE); 3549 // This is strange and shouldn't happen. 3550 return SE.getCouldNotCompute(); 3551 } 3552 3553 // The only time we can solve this is when we have all constant indices. 3554 // Otherwise, we cannot determine the overflow conditions. 3555 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 3556 if (!isa<SCEVConstant>(getOperand(i))) 3557 return SE.getCouldNotCompute(); 3558 3559 3560 // Okay at this point we know that all elements of the chrec are constants and 3561 // that the start element is zero. 3562 3563 // First check to see if the range contains zero. If not, the first 3564 // iteration exits. 3565 unsigned BitWidth = SE.getTypeSizeInBits(getType()); 3566 if (!Range.contains(APInt(BitWidth, 0))) 3567 return SE.getConstant(ConstantInt::get(getType(),0)); 3568 3569 if (isAffine()) { 3570 // If this is an affine expression then we have this situation: 3571 // Solve {0,+,A} in Range === Ax in Range 3572 3573 // We know that zero is in the range. If A is positive then we know that 3574 // the upper value of the range must be the first possible exit value. 3575 // If A is negative then the lower of the range is the last possible loop 3576 // value. Also note that we already checked for a full range. 3577 APInt One(BitWidth,1); 3578 APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue(); 3579 APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower(); 3580 3581 // The exit value should be (End+A)/A. 3582 APInt ExitVal = (End + A).udiv(A); 3583 ConstantInt *ExitValue = ConstantInt::get(ExitVal); 3584 3585 // Evaluate at the exit value. If we really did fall out of the valid 3586 // range, then we computed our trip count, otherwise wrap around or other 3587 // things must have happened. 3588 ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE); 3589 if (Range.contains(Val->getValue())) 3590 return SE.getCouldNotCompute(); // Something strange happened 3591 3592 // Ensure that the previous value is in the range. This is a sanity check. 3593 assert(Range.contains( 3594 EvaluateConstantChrecAtConstant(this, 3595 ConstantInt::get(ExitVal - One), SE)->getValue()) && 3596 "Linear scev computation is off in a bad way!"); 3597 return SE.getConstant(ExitValue); 3598 } else if (isQuadratic()) { 3599 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the 3600 // quadratic equation to solve it. To do this, we must frame our problem in 3601 // terms of figuring out when zero is crossed, instead of when 3602 // Range.getUpper() is crossed. 3603 std::vector<SCEVHandle> NewOps(op_begin(), op_end()); 3604 NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper())); 3605 SCEVHandle NewAddRec = SE.getAddRecExpr(NewOps, getLoop()); 3606 3607 // Next, solve the constructed addrec 3608 std::pair<SCEVHandle,SCEVHandle> Roots = 3609 SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE); 3610 const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first); 3611 const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second); 3612 if (R1) { 3613 // Pick the smallest positive root value. 3614 if (ConstantInt *CB = 3615 dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, 3616 R1->getValue(), R2->getValue()))) { 3617 if (CB->getZExtValue() == false) 3618 std::swap(R1, R2); // R1 is the minimum root now. 3619 3620 // Make sure the root is not off by one. The returned iteration should 3621 // not be in the range, but the previous one should be. When solving 3622 // for "X*X < 5", for example, we should not return a root of 2. 3623 ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this, 3624 R1->getValue(), 3625 SE); 3626 if (Range.contains(R1Val->getValue())) { 3627 // The next iteration must be out of the range... 3628 ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()+1); 3629 3630 R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE); 3631 if (!Range.contains(R1Val->getValue())) 3632 return SE.getConstant(NextVal); 3633 return SE.getCouldNotCompute(); // Something strange happened 3634 } 3635 3636 // If R1 was not in the range, then it is a good return value. Make 3637 // sure that R1-1 WAS in the range though, just in case. 3638 ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()-1); 3639 R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE); 3640 if (Range.contains(R1Val->getValue())) 3641 return R1; 3642 return SE.getCouldNotCompute(); // Something strange happened 3643 } 3644 } 3645 } 3646 3647 return SE.getCouldNotCompute(); 3648} 3649 3650 3651 3652//===----------------------------------------------------------------------===// 3653// SCEVCallbackVH Class Implementation 3654//===----------------------------------------------------------------------===// 3655 3656void SCEVCallbackVH::deleted() { 3657 assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!"); 3658 if (PHINode *PN = dyn_cast<PHINode>(getValPtr())) 3659 SE->ConstantEvolutionLoopExitValue.erase(PN); 3660 if (Instruction *I = dyn_cast<Instruction>(getValPtr())) 3661 SE->ValuesAtScopes.erase(I); 3662 SE->Scalars.erase(getValPtr()); 3663 // this now dangles! 3664} 3665 3666void SCEVCallbackVH::allUsesReplacedWith(Value *) { 3667 assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!"); 3668 3669 // Forget all the expressions associated with users of the old value, 3670 // so that future queries will recompute the expressions using the new 3671 // value. 3672 SmallVector<User *, 16> Worklist; 3673 Value *Old = getValPtr(); 3674 bool DeleteOld = false; 3675 for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end(); 3676 UI != UE; ++UI) 3677 Worklist.push_back(*UI); 3678 while (!Worklist.empty()) { 3679 User *U = Worklist.pop_back_val(); 3680 // Deleting the Old value will cause this to dangle. Postpone 3681 // that until everything else is done. 3682 if (U == Old) { 3683 DeleteOld = true; 3684 continue; 3685 } 3686 if (PHINode *PN = dyn_cast<PHINode>(U)) 3687 SE->ConstantEvolutionLoopExitValue.erase(PN); 3688 if (Instruction *I = dyn_cast<Instruction>(U)) 3689 SE->ValuesAtScopes.erase(I); 3690 if (SE->Scalars.erase(U)) 3691 for (Value::use_iterator UI = U->use_begin(), UE = U->use_end(); 3692 UI != UE; ++UI) 3693 Worklist.push_back(*UI); 3694 } 3695 if (DeleteOld) { 3696 if (PHINode *PN = dyn_cast<PHINode>(Old)) 3697 SE->ConstantEvolutionLoopExitValue.erase(PN); 3698 if (Instruction *I = dyn_cast<Instruction>(Old)) 3699 SE->ValuesAtScopes.erase(I); 3700 SE->Scalars.erase(Old); 3701 // this now dangles! 3702 } 3703 // this may dangle! 3704} 3705 3706SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se) 3707 : CallbackVH(V), SE(se) {} 3708 3709//===----------------------------------------------------------------------===// 3710// ScalarEvolution Class Implementation 3711//===----------------------------------------------------------------------===// 3712 3713ScalarEvolution::ScalarEvolution() 3714 : FunctionPass(&ID), UnknownValue(new SCEVCouldNotCompute()) { 3715} 3716 3717bool ScalarEvolution::runOnFunction(Function &F) { 3718 this->F = &F; 3719 LI = &getAnalysis<LoopInfo>(); 3720 TD = getAnalysisIfAvailable<TargetData>(); 3721 return false; 3722} 3723 3724void ScalarEvolution::releaseMemory() { 3725 Scalars.clear(); 3726 BackedgeTakenCounts.clear(); 3727 ConstantEvolutionLoopExitValue.clear(); 3728 ValuesAtScopes.clear(); 3729} 3730 3731void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const { 3732 AU.setPreservesAll(); 3733 AU.addRequiredTransitive<LoopInfo>(); 3734} 3735 3736bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) { 3737 return !isa<SCEVCouldNotCompute>(getBackedgeTakenCount(L)); 3738} 3739 3740static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, 3741 const Loop *L) { 3742 // Print all inner loops first 3743 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 3744 PrintLoopInfo(OS, SE, *I); 3745 3746 OS << "Loop " << L->getHeader()->getName() << ": "; 3747 3748 SmallVector<BasicBlock*, 8> ExitBlocks; 3749 L->getExitBlocks(ExitBlocks); 3750 if (ExitBlocks.size() != 1) 3751 OS << "<multiple exits> "; 3752 3753 if (SE->hasLoopInvariantBackedgeTakenCount(L)) { 3754 OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L); 3755 } else { 3756 OS << "Unpredictable backedge-taken count. "; 3757 } 3758 3759 OS << "\n"; 3760} 3761 3762void ScalarEvolution::print(raw_ostream &OS, const Module* ) const { 3763 // ScalarEvolution's implementaiton of the print method is to print 3764 // out SCEV values of all instructions that are interesting. Doing 3765 // this potentially causes it to create new SCEV objects though, 3766 // which technically conflicts with the const qualifier. This isn't 3767 // observable from outside the class though (the hasSCEV function 3768 // notwithstanding), so casting away the const isn't dangerous. 3769 ScalarEvolution &SE = *const_cast<ScalarEvolution*>(this); 3770 3771 OS << "Classifying expressions for: " << F->getName() << "\n"; 3772 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 3773 if (isSCEVable(I->getType())) { 3774 OS << *I; 3775 OS << " --> "; 3776 SCEVHandle SV = SE.getSCEV(&*I); 3777 SV->print(OS); 3778 OS << "\t\t"; 3779 3780 if (const Loop *L = LI->getLoopFor((*I).getParent())) { 3781 OS << "Exits: "; 3782 SCEVHandle ExitValue = SE.getSCEVAtScope(&*I, L->getParentLoop()); 3783 if (isa<SCEVCouldNotCompute>(ExitValue)) { 3784 OS << "<<Unknown>>"; 3785 } else { 3786 OS << *ExitValue; 3787 } 3788 } 3789 3790 3791 OS << "\n"; 3792 } 3793 3794 OS << "Determining loop execution counts for: " << F->getName() << "\n"; 3795 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 3796 PrintLoopInfo(OS, &SE, *I); 3797} 3798 3799void ScalarEvolution::print(std::ostream &o, const Module *M) const { 3800 raw_os_ostream OS(o); 3801 print(OS, M); 3802} 3803