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