ScalarEvolution.cpp revision d594e6f0345b3e1e4b640a7099596ca613da16d6
1//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains the implementation of the scalar evolution analysis 11// engine, which is used primarily to analyze expressions involving induction 12// variables in loops. 13// 14// There are several aspects to this library. First is the representation of 15// scalar expressions, which are represented as subclasses of the SCEV class. 16// These classes are used to represent certain types of subexpressions that we 17// can handle. These classes are reference counted, managed by the SCEVHandle 18// class. We only create one SCEV of a particular shape, so pointer-comparisons 19// for equality are legal. 20// 21// One important aspect of the SCEV objects is that they are never cyclic, even 22// if there is a cycle in the dataflow for an expression (ie, a PHI node). If 23// the PHI node is one of the idioms that we can represent (e.g., a polynomial 24// recurrence) then we represent it directly as a recurrence node, otherwise we 25// represent it as a SCEVUnknown node. 26// 27// In addition to being able to represent expressions of various types, we also 28// have folders that are used to build the *canonical* representation for a 29// particular expression. These folders are capable of using a variety of 30// rewrite rules to simplify the expressions. 31// 32// Once the folders are defined, we can implement the more interesting 33// higher-level code, such as the code that recognizes PHI nodes of various 34// types, computes the execution count of a loop, etc. 35// 36// TODO: We should use these routines and value representations to implement 37// dependence analysis! 38// 39//===----------------------------------------------------------------------===// 40// 41// There are several good references for the techniques used in this analysis. 42// 43// Chains of recurrences -- a method to expedite the evaluation 44// of closed-form functions 45// Olaf Bachmann, Paul S. Wang, Eugene V. Zima 46// 47// On computational properties of chains of recurrences 48// Eugene V. Zima 49// 50// Symbolic Evaluation of Chains of Recurrences for Loop Optimization 51// Robert A. van Engelen 52// 53// Efficient Symbolic Analysis for Optimizing Compilers 54// Robert A. van Engelen 55// 56// Using the chains of recurrences algebra for data dependence testing and 57// induction variable substitution 58// MS Thesis, Johnie Birch 59// 60//===----------------------------------------------------------------------===// 61 62#define DEBUG_TYPE "scalar-evolution" 63#include "llvm/Analysis/ScalarEvolutionExpressions.h" 64#include "llvm/Constants.h" 65#include "llvm/DerivedTypes.h" 66#include "llvm/GlobalVariable.h" 67#include "llvm/Instructions.h" 68#include "llvm/Analysis/ConstantFolding.h" 69#include "llvm/Analysis/Dominators.h" 70#include "llvm/Analysis/LoopInfo.h" 71#include "llvm/Assembly/Writer.h" 72#include "llvm/Target/TargetData.h" 73#include "llvm/Support/CommandLine.h" 74#include "llvm/Support/Compiler.h" 75#include "llvm/Support/ConstantRange.h" 76#include "llvm/Support/GetElementPtrTypeIterator.h" 77#include "llvm/Support/InstIterator.h" 78#include "llvm/Support/ManagedStatic.h" 79#include "llvm/Support/MathExtras.h" 80#include "llvm/Support/raw_ostream.h" 81#include "llvm/ADT/Statistic.h" 82#include "llvm/ADT/STLExtras.h" 83#include <ostream> 84#include <algorithm> 85using namespace llvm; 86 87STATISTIC(NumArrayLenItCounts, 88 "Number of trip counts computed with array length"); 89STATISTIC(NumTripCountsComputed, 90 "Number of loops with predictable loop counts"); 91STATISTIC(NumTripCountsNotComputed, 92 "Number of loops without predictable loop counts"); 93STATISTIC(NumBruteForceTripCountsComputed, 94 "Number of loops with trip counts computed by force"); 95 96static cl::opt<unsigned> 97MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, 98 cl::desc("Maximum number of iterations SCEV will " 99 "symbolically execute a constant derived loop"), 100 cl::init(100)); 101 102static RegisterPass<ScalarEvolution> 103R("scalar-evolution", "Scalar Evolution Analysis", false, true); 104char ScalarEvolution::ID = 0; 105 106//===----------------------------------------------------------------------===// 107// SCEV class definitions 108//===----------------------------------------------------------------------===// 109 110//===----------------------------------------------------------------------===// 111// Implementation of the SCEV class. 112// 113SCEV::~SCEV() {} 114void SCEV::dump() const { 115 print(errs()); 116 errs() << '\n'; 117} 118 119void SCEV::print(std::ostream &o) const { 120 raw_os_ostream OS(o); 121 print(OS); 122} 123 124bool SCEV::isZero() const { 125 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this)) 126 return SC->getValue()->isZero(); 127 return false; 128} 129 130bool SCEV::isOne() const { 131 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this)) 132 return SC->getValue()->isOne(); 133 return false; 134} 135 136SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {} 137SCEVCouldNotCompute::~SCEVCouldNotCompute() {} 138 139bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const { 140 assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); 141 return false; 142} 143 144const Type *SCEVCouldNotCompute::getType() const { 145 assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); 146 return 0; 147} 148 149bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const { 150 assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); 151 return false; 152} 153 154SCEVHandle SCEVCouldNotCompute:: 155replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 156 const SCEVHandle &Conc, 157 ScalarEvolution &SE) const { 158 return this; 159} 160 161void SCEVCouldNotCompute::print(raw_ostream &OS) const { 162 OS << "***COULDNOTCOMPUTE***"; 163} 164 165bool SCEVCouldNotCompute::classof(const SCEV *S) { 166 return S->getSCEVType() == scCouldNotCompute; 167} 168 169 170// SCEVConstants - Only allow the creation of one SCEVConstant for any 171// particular value. Don't use a SCEVHandle here, or else the object will 172// never be deleted! 173static ManagedStatic<std::map<ConstantInt*, SCEVConstant*> > SCEVConstants; 174 175 176SCEVConstant::~SCEVConstant() { 177 SCEVConstants->erase(V); 178} 179 180SCEVHandle ScalarEvolution::getConstant(ConstantInt *V) { 181 SCEVConstant *&R = (*SCEVConstants)[V]; 182 if (R == 0) R = new SCEVConstant(V); 183 return R; 184} 185 186SCEVHandle ScalarEvolution::getConstant(const APInt& Val) { 187 return getConstant(ConstantInt::get(Val)); 188} 189 190const Type *SCEVConstant::getType() const { return V->getType(); } 191 192void SCEVConstant::print(raw_ostream &OS) const { 193 WriteAsOperand(OS, V, false); 194} 195 196SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy, 197 const SCEVHandle &op, const Type *ty) 198 : SCEV(SCEVTy), Op(op), Ty(ty) {} 199 200SCEVCastExpr::~SCEVCastExpr() {} 201 202bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { 203 return Op->dominates(BB, DT); 204} 205 206// SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any 207// particular input. Don't use a SCEVHandle here, or else the object will 208// never be deleted! 209static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>, 210 SCEVTruncateExpr*> > SCEVTruncates; 211 212SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty) 213 : SCEVCastExpr(scTruncate, op, ty) { 214 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) && 215 (Ty->isInteger() || isa<PointerType>(Ty)) && 216 "Cannot truncate non-integer value!"); 217} 218 219SCEVTruncateExpr::~SCEVTruncateExpr() { 220 SCEVTruncates->erase(std::make_pair(Op, Ty)); 221} 222 223void SCEVTruncateExpr::print(raw_ostream &OS) const { 224 OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; 225} 226 227// SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any 228// particular input. Don't use a SCEVHandle here, or else the object will never 229// be deleted! 230static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>, 231 SCEVZeroExtendExpr*> > SCEVZeroExtends; 232 233SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty) 234 : SCEVCastExpr(scZeroExtend, op, ty) { 235 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) && 236 (Ty->isInteger() || isa<PointerType>(Ty)) && 237 "Cannot zero extend non-integer value!"); 238} 239 240SCEVZeroExtendExpr::~SCEVZeroExtendExpr() { 241 SCEVZeroExtends->erase(std::make_pair(Op, Ty)); 242} 243 244void SCEVZeroExtendExpr::print(raw_ostream &OS) const { 245 OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; 246} 247 248// SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any 249// particular input. Don't use a SCEVHandle here, or else the object will never 250// be deleted! 251static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>, 252 SCEVSignExtendExpr*> > SCEVSignExtends; 253 254SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty) 255 : SCEVCastExpr(scSignExtend, op, ty) { 256 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) && 257 (Ty->isInteger() || isa<PointerType>(Ty)) && 258 "Cannot sign extend non-integer value!"); 259} 260 261SCEVSignExtendExpr::~SCEVSignExtendExpr() { 262 SCEVSignExtends->erase(std::make_pair(Op, Ty)); 263} 264 265void SCEVSignExtendExpr::print(raw_ostream &OS) const { 266 OS << "(sext " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; 267} 268 269// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any 270// particular input. Don't use a SCEVHandle here, or else the object will never 271// be deleted! 272static ManagedStatic<std::map<std::pair<unsigned, std::vector<const SCEV*> >, 273 SCEVCommutativeExpr*> > SCEVCommExprs; 274 275SCEVCommutativeExpr::~SCEVCommutativeExpr() { 276 std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end()); 277 SCEVCommExprs->erase(std::make_pair(getSCEVType(), SCEVOps)); 278} 279 280void SCEVCommutativeExpr::print(raw_ostream &OS) const { 281 assert(Operands.size() > 1 && "This plus expr shouldn't exist!"); 282 const char *OpStr = getOperationStr(); 283 OS << "(" << *Operands[0]; 284 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 285 OS << OpStr << *Operands[i]; 286 OS << ")"; 287} 288 289SCEVHandle SCEVCommutativeExpr:: 290replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 291 const SCEVHandle &Conc, 292 ScalarEvolution &SE) const { 293 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 294 SCEVHandle H = 295 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 296 if (H != getOperand(i)) { 297 std::vector<SCEVHandle> NewOps; 298 NewOps.reserve(getNumOperands()); 299 for (unsigned j = 0; j != i; ++j) 300 NewOps.push_back(getOperand(j)); 301 NewOps.push_back(H); 302 for (++i; i != e; ++i) 303 NewOps.push_back(getOperand(i)-> 304 replaceSymbolicValuesWithConcrete(Sym, Conc, SE)); 305 306 if (isa<SCEVAddExpr>(this)) 307 return SE.getAddExpr(NewOps); 308 else if (isa<SCEVMulExpr>(this)) 309 return SE.getMulExpr(NewOps); 310 else if (isa<SCEVSMaxExpr>(this)) 311 return SE.getSMaxExpr(NewOps); 312 else if (isa<SCEVUMaxExpr>(this)) 313 return SE.getUMaxExpr(NewOps); 314 else 315 assert(0 && "Unknown commutative expr!"); 316 } 317 } 318 return this; 319} 320 321bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { 322 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 323 if (!getOperand(i)->dominates(BB, DT)) 324 return false; 325 } 326 return true; 327} 328 329 330// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular 331// input. Don't use a SCEVHandle here, or else the object will never be 332// deleted! 333static ManagedStatic<std::map<std::pair<const SCEV*, const SCEV*>, 334 SCEVUDivExpr*> > SCEVUDivs; 335 336SCEVUDivExpr::~SCEVUDivExpr() { 337 SCEVUDivs->erase(std::make_pair(LHS, RHS)); 338} 339 340bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { 341 return LHS->dominates(BB, DT) && RHS->dominates(BB, DT); 342} 343 344void SCEVUDivExpr::print(raw_ostream &OS) const { 345 OS << "(" << *LHS << " /u " << *RHS << ")"; 346} 347 348const Type *SCEVUDivExpr::getType() const { 349 return LHS->getType(); 350} 351 352// SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any 353// particular input. Don't use a SCEVHandle here, or else the object will never 354// be deleted! 355static ManagedStatic<std::map<std::pair<const Loop *, 356 std::vector<const SCEV*> >, 357 SCEVAddRecExpr*> > SCEVAddRecExprs; 358 359SCEVAddRecExpr::~SCEVAddRecExpr() { 360 std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end()); 361 SCEVAddRecExprs->erase(std::make_pair(L, SCEVOps)); 362} 363 364SCEVHandle SCEVAddRecExpr:: 365replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 366 const SCEVHandle &Conc, 367 ScalarEvolution &SE) const { 368 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 369 SCEVHandle H = 370 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 371 if (H != getOperand(i)) { 372 std::vector<SCEVHandle> NewOps; 373 NewOps.reserve(getNumOperands()); 374 for (unsigned j = 0; j != i; ++j) 375 NewOps.push_back(getOperand(j)); 376 NewOps.push_back(H); 377 for (++i; i != e; ++i) 378 NewOps.push_back(getOperand(i)-> 379 replaceSymbolicValuesWithConcrete(Sym, Conc, SE)); 380 381 return SE.getAddRecExpr(NewOps, L); 382 } 383 } 384 return this; 385} 386 387 388bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const { 389 // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't 390 // contain L and if the start is invariant. 391 // Add recurrences are never invariant in the function-body (null loop). 392 return QueryLoop && 393 !QueryLoop->contains(L->getHeader()) && 394 getOperand(0)->isLoopInvariant(QueryLoop); 395} 396 397 398void SCEVAddRecExpr::print(raw_ostream &OS) const { 399 OS << "{" << *Operands[0]; 400 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 401 OS << ",+," << *Operands[i]; 402 OS << "}<" << L->getHeader()->getName() + ">"; 403} 404 405// SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular 406// value. Don't use a SCEVHandle here, or else the object will never be 407// deleted! 408static ManagedStatic<std::map<Value*, SCEVUnknown*> > SCEVUnknowns; 409 410SCEVUnknown::~SCEVUnknown() { SCEVUnknowns->erase(V); } 411 412bool SCEVUnknown::isLoopInvariant(const Loop *L) const { 413 // All non-instruction values are loop invariant. All instructions are loop 414 // invariant if they are not contained in the specified loop. 415 // Instructions are never considered invariant in the function body 416 // (null loop) because they are defined within the "loop". 417 if (Instruction *I = dyn_cast<Instruction>(V)) 418 return L && !L->contains(I->getParent()); 419 return true; 420} 421 422bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const { 423 if (Instruction *I = dyn_cast<Instruction>(getValue())) 424 return DT->dominates(I->getParent(), BB); 425 return true; 426} 427 428const Type *SCEVUnknown::getType() const { 429 return V->getType(); 430} 431 432void SCEVUnknown::print(raw_ostream &OS) const { 433 WriteAsOperand(OS, V, false); 434} 435 436//===----------------------------------------------------------------------===// 437// SCEV Utilities 438//===----------------------------------------------------------------------===// 439 440namespace { 441 /// SCEVComplexityCompare - Return true if the complexity of the LHS is less 442 /// than the complexity of the RHS. This comparator is used to canonicalize 443 /// expressions. 444 class VISIBILITY_HIDDEN SCEVComplexityCompare { 445 LoopInfo *LI; 446 public: 447 explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {} 448 449 bool operator()(const SCEV *LHS, const SCEV *RHS) const { 450 // Primarily, sort the SCEVs by their getSCEVType(). 451 if (LHS->getSCEVType() != RHS->getSCEVType()) 452 return LHS->getSCEVType() < RHS->getSCEVType(); 453 454 // Aside from the getSCEVType() ordering, the particular ordering 455 // isn't very important except that it's beneficial to be consistent, 456 // so that (a + b) and (b + a) don't end up as different expressions. 457 458 // Sort SCEVUnknown values with some loose heuristics. TODO: This is 459 // not as complete as it could be. 460 if (const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS)) { 461 const SCEVUnknown *RU = cast<SCEVUnknown>(RHS); 462 463 // Order pointer values after integer values. This helps SCEVExpander 464 // form GEPs. 465 if (isa<PointerType>(LU->getType()) && !isa<PointerType>(RU->getType())) 466 return false; 467 if (isa<PointerType>(RU->getType()) && !isa<PointerType>(LU->getType())) 468 return true; 469 470 // Compare getValueID values. 471 if (LU->getValue()->getValueID() != RU->getValue()->getValueID()) 472 return LU->getValue()->getValueID() < RU->getValue()->getValueID(); 473 474 // Sort arguments by their position. 475 if (const Argument *LA = dyn_cast<Argument>(LU->getValue())) { 476 const Argument *RA = cast<Argument>(RU->getValue()); 477 return LA->getArgNo() < RA->getArgNo(); 478 } 479 480 // For instructions, compare their loop depth, and their opcode. 481 // This is pretty loose. 482 if (Instruction *LV = dyn_cast<Instruction>(LU->getValue())) { 483 Instruction *RV = cast<Instruction>(RU->getValue()); 484 485 // Compare loop depths. 486 if (LI->getLoopDepth(LV->getParent()) != 487 LI->getLoopDepth(RV->getParent())) 488 return LI->getLoopDepth(LV->getParent()) < 489 LI->getLoopDepth(RV->getParent()); 490 491 // Compare opcodes. 492 if (LV->getOpcode() != RV->getOpcode()) 493 return LV->getOpcode() < RV->getOpcode(); 494 495 // Compare the number of operands. 496 if (LV->getNumOperands() != RV->getNumOperands()) 497 return LV->getNumOperands() < RV->getNumOperands(); 498 } 499 500 return false; 501 } 502 503 // Constant sorting doesn't matter since they'll be folded. 504 if (isa<SCEVConstant>(LHS)) 505 return false; 506 507 // Lexicographically compare n-ary expressions. 508 if (const SCEVNAryExpr *LC = dyn_cast<SCEVNAryExpr>(LHS)) { 509 const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS); 510 for (unsigned i = 0, e = LC->getNumOperands(); i != e; ++i) { 511 if (i >= RC->getNumOperands()) 512 return false; 513 if (operator()(LC->getOperand(i), RC->getOperand(i))) 514 return true; 515 if (operator()(RC->getOperand(i), LC->getOperand(i))) 516 return false; 517 } 518 return LC->getNumOperands() < RC->getNumOperands(); 519 } 520 521 // Lexicographically compare udiv expressions. 522 if (const SCEVUDivExpr *LC = dyn_cast<SCEVUDivExpr>(LHS)) { 523 const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS); 524 if (operator()(LC->getLHS(), RC->getLHS())) 525 return true; 526 if (operator()(RC->getLHS(), LC->getLHS())) 527 return false; 528 if (operator()(LC->getRHS(), RC->getRHS())) 529 return true; 530 if (operator()(RC->getRHS(), LC->getRHS())) 531 return false; 532 return false; 533 } 534 535 // Compare cast expressions by operand. 536 if (const SCEVCastExpr *LC = dyn_cast<SCEVCastExpr>(LHS)) { 537 const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS); 538 return operator()(LC->getOperand(), RC->getOperand()); 539 } 540 541 assert(0 && "Unknown SCEV kind!"); 542 return false; 543 } 544 }; 545} 546 547/// GroupByComplexity - Given a list of SCEV objects, order them by their 548/// complexity, and group objects of the same complexity together by value. 549/// When this routine is finished, we know that any duplicates in the vector are 550/// consecutive and that complexity is monotonically increasing. 551/// 552/// Note that we go take special precautions to ensure that we get determinstic 553/// results from this routine. In other words, we don't want the results of 554/// this to depend on where the addresses of various SCEV objects happened to 555/// land in memory. 556/// 557static void GroupByComplexity(std::vector<SCEVHandle> &Ops, 558 LoopInfo *LI) { 559 if (Ops.size() < 2) return; // Noop 560 if (Ops.size() == 2) { 561 // This is the common case, which also happens to be trivially simple. 562 // Special case it. 563 if (SCEVComplexityCompare(LI)(Ops[1], Ops[0])) 564 std::swap(Ops[0], Ops[1]); 565 return; 566 } 567 568 // Do the rough sort by complexity. 569 std::stable_sort(Ops.begin(), Ops.end(), SCEVComplexityCompare(LI)); 570 571 // Now that we are sorted by complexity, group elements of the same 572 // complexity. Note that this is, at worst, N^2, but the vector is likely to 573 // be extremely short in practice. Note that we take this approach because we 574 // do not want to depend on the addresses of the objects we are grouping. 575 for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) { 576 const SCEV *S = Ops[i]; 577 unsigned Complexity = S->getSCEVType(); 578 579 // If there are any objects of the same complexity and same value as this 580 // one, group them. 581 for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) { 582 if (Ops[j] == S) { // Found a duplicate. 583 // Move it to immediately after i'th element. 584 std::swap(Ops[i+1], Ops[j]); 585 ++i; // no need to rescan it. 586 if (i == e-2) return; // Done! 587 } 588 } 589 } 590} 591 592 593 594//===----------------------------------------------------------------------===// 595// Simple SCEV method implementations 596//===----------------------------------------------------------------------===// 597 598/// BinomialCoefficient - Compute BC(It, K). The result has width W. 599// Assume, K > 0. 600static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K, 601 ScalarEvolution &SE, 602 const Type* ResultTy) { 603 // Handle the simplest case efficiently. 604 if (K == 1) 605 return SE.getTruncateOrZeroExtend(It, ResultTy); 606 607 // We are using the following formula for BC(It, K): 608 // 609 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / K! 610 // 611 // Suppose, W is the bitwidth of the return value. We must be prepared for 612 // overflow. Hence, we must assure that the result of our computation is 613 // equal to the accurate one modulo 2^W. Unfortunately, division isn't 614 // safe in modular arithmetic. 615 // 616 // However, this code doesn't use exactly that formula; the formula it uses 617 // is something like the following, where T is the number of factors of 2 in 618 // K! (i.e. trailing zeros in the binary representation of K!), and ^ is 619 // exponentiation: 620 // 621 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / 2^T / (K! / 2^T) 622 // 623 // This formula is trivially equivalent to the previous formula. However, 624 // this formula can be implemented much more efficiently. The trick is that 625 // K! / 2^T is odd, and exact division by an odd number *is* safe in modular 626 // arithmetic. To do exact division in modular arithmetic, all we have 627 // to do is multiply by the inverse. Therefore, this step can be done at 628 // width W. 629 // 630 // The next issue is how to safely do the division by 2^T. The way this 631 // is done is by doing the multiplication step at a width of at least W + T 632 // bits. This way, the bottom W+T bits of the product are accurate. Then, 633 // when we perform the division by 2^T (which is equivalent to a right shift 634 // by T), the bottom W bits are accurate. Extra bits are okay; they'll get 635 // truncated out after the division by 2^T. 636 // 637 // In comparison to just directly using the first formula, this technique 638 // is much more efficient; using the first formula requires W * K bits, 639 // but this formula less than W + K bits. Also, the first formula requires 640 // a division step, whereas this formula only requires multiplies and shifts. 641 // 642 // It doesn't matter whether the subtraction step is done in the calculation 643 // width or the input iteration count's width; if the subtraction overflows, 644 // the result must be zero anyway. We prefer here to do it in the width of 645 // the induction variable because it helps a lot for certain cases; CodeGen 646 // isn't smart enough to ignore the overflow, which leads to much less 647 // efficient code if the width of the subtraction is wider than the native 648 // register width. 649 // 650 // (It's possible to not widen at all by pulling out factors of 2 before 651 // the multiplication; for example, K=2 can be calculated as 652 // It/2*(It+(It*INT_MIN/INT_MIN)+-1). However, it requires 653 // extra arithmetic, so it's not an obvious win, and it gets 654 // much more complicated for K > 3.) 655 656 // Protection from insane SCEVs; this bound is conservative, 657 // but it probably doesn't matter. 658 if (K > 1000) 659 return SE.getCouldNotCompute(); 660 661 unsigned W = SE.getTypeSizeInBits(ResultTy); 662 663 // Calculate K! / 2^T and T; we divide out the factors of two before 664 // multiplying for calculating K! / 2^T to avoid overflow. 665 // Other overflow doesn't matter because we only care about the bottom 666 // W bits of the result. 667 APInt OddFactorial(W, 1); 668 unsigned T = 1; 669 for (unsigned i = 3; i <= K; ++i) { 670 APInt Mult(W, i); 671 unsigned TwoFactors = Mult.countTrailingZeros(); 672 T += TwoFactors; 673 Mult = Mult.lshr(TwoFactors); 674 OddFactorial *= Mult; 675 } 676 677 // We need at least W + T bits for the multiplication step 678 unsigned CalculationBits = W + T; 679 680 // Calcuate 2^T, at width T+W. 681 APInt DivFactor = APInt(CalculationBits, 1).shl(T); 682 683 // Calculate the multiplicative inverse of K! / 2^T; 684 // this multiplication factor will perform the exact division by 685 // K! / 2^T. 686 APInt Mod = APInt::getSignedMinValue(W+1); 687 APInt MultiplyFactor = OddFactorial.zext(W+1); 688 MultiplyFactor = MultiplyFactor.multiplicativeInverse(Mod); 689 MultiplyFactor = MultiplyFactor.trunc(W); 690 691 // Calculate the product, at width T+W 692 const IntegerType *CalculationTy = IntegerType::get(CalculationBits); 693 SCEVHandle Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy); 694 for (unsigned i = 1; i != K; ++i) { 695 SCEVHandle S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType())); 696 Dividend = SE.getMulExpr(Dividend, 697 SE.getTruncateOrZeroExtend(S, CalculationTy)); 698 } 699 700 // Divide by 2^T 701 SCEVHandle DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor)); 702 703 // Truncate the result, and divide by K! / 2^T. 704 705 return SE.getMulExpr(SE.getConstant(MultiplyFactor), 706 SE.getTruncateOrZeroExtend(DivResult, ResultTy)); 707} 708 709/// evaluateAtIteration - Return the value of this chain of recurrences at 710/// the specified iteration number. We can evaluate this recurrence by 711/// multiplying each element in the chain by the binomial coefficient 712/// corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as: 713/// 714/// A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3) 715/// 716/// where BC(It, k) stands for binomial coefficient. 717/// 718SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It, 719 ScalarEvolution &SE) const { 720 SCEVHandle Result = getStart(); 721 for (unsigned i = 1, e = getNumOperands(); i != e; ++i) { 722 // The computation is correct in the face of overflow provided that the 723 // multiplication is performed _after_ the evaluation of the binomial 724 // coefficient. 725 SCEVHandle Coeff = BinomialCoefficient(It, i, SE, getType()); 726 if (isa<SCEVCouldNotCompute>(Coeff)) 727 return Coeff; 728 729 Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff)); 730 } 731 return Result; 732} 733 734//===----------------------------------------------------------------------===// 735// SCEV Expression folder implementations 736//===----------------------------------------------------------------------===// 737 738SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op, 739 const Type *Ty) { 740 assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) && 741 "This is not a truncating conversion!"); 742 assert(isSCEVable(Ty) && 743 "This is not a conversion to a SCEVable type!"); 744 Ty = getEffectiveSCEVType(Ty); 745 746 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) 747 return getUnknown( 748 ConstantExpr::getTrunc(SC->getValue(), Ty)); 749 750 // trunc(trunc(x)) --> trunc(x) 751 if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) 752 return getTruncateExpr(ST->getOperand(), Ty); 753 754 // trunc(sext(x)) --> sext(x) if widening or trunc(x) if narrowing 755 if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op)) 756 return getTruncateOrSignExtend(SS->getOperand(), Ty); 757 758 // trunc(zext(x)) --> zext(x) if widening or trunc(x) if narrowing 759 if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op)) 760 return getTruncateOrZeroExtend(SZ->getOperand(), Ty); 761 762 // If the input value is a chrec scev made out of constants, truncate 763 // all of the constants. 764 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) { 765 std::vector<SCEVHandle> Operands; 766 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) 767 Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty)); 768 return getAddRecExpr(Operands, AddRec->getLoop()); 769 } 770 771 SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)]; 772 if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty); 773 return Result; 774} 775 776SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op, 777 const Type *Ty) { 778 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) && 779 "This is not an extending conversion!"); 780 assert(isSCEVable(Ty) && 781 "This is not a conversion to a SCEVable type!"); 782 Ty = getEffectiveSCEVType(Ty); 783 784 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) { 785 const Type *IntTy = getEffectiveSCEVType(Ty); 786 Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy); 787 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty); 788 return getUnknown(C); 789 } 790 791 // zext(zext(x)) --> zext(x) 792 if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op)) 793 return getZeroExtendExpr(SZ->getOperand(), Ty); 794 795 // If the input value is a chrec scev, and we can prove that the value 796 // did not overflow the old, smaller, value, we can zero extend all of the 797 // operands (often constants). This allows analysis of something like 798 // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; } 799 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op)) 800 if (AR->isAffine()) { 801 // Check whether the backedge-taken count is SCEVCouldNotCompute. 802 // Note that this serves two purposes: It filters out loops that are 803 // simply not analyzable, and it covers the case where this code is 804 // being called from within backedge-taken count analysis, such that 805 // attempting to ask for the backedge-taken count would likely result 806 // in infinite recursion. In the later case, the analysis code will 807 // cope with a conservative value, and it will take care to purge 808 // that value once it has finished. 809 SCEVHandle MaxBECount = getMaxBackedgeTakenCount(AR->getLoop()); 810 if (!isa<SCEVCouldNotCompute>(MaxBECount)) { 811 // Manually compute the final value for AR, checking for 812 // overflow. 813 SCEVHandle Start = AR->getStart(); 814 SCEVHandle Step = AR->getStepRecurrence(*this); 815 816 // Check whether the backedge-taken count can be losslessly casted to 817 // the addrec's type. The count is always unsigned. 818 SCEVHandle CastedMaxBECount = 819 getTruncateOrZeroExtend(MaxBECount, Start->getType()); 820 SCEVHandle RecastedMaxBECount = 821 getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType()); 822 if (MaxBECount == RecastedMaxBECount) { 823 const Type *WideTy = 824 IntegerType::get(getTypeSizeInBits(Start->getType()) * 2); 825 // Check whether Start+Step*MaxBECount has no unsigned overflow. 826 SCEVHandle ZMul = 827 getMulExpr(CastedMaxBECount, 828 getTruncateOrZeroExtend(Step, Start->getType())); 829 SCEVHandle Add = getAddExpr(Start, ZMul); 830 SCEVHandle OperandExtendedAdd = 831 getAddExpr(getZeroExtendExpr(Start, WideTy), 832 getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), 833 getZeroExtendExpr(Step, WideTy))); 834 if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) 835 // Return the expression with the addrec on the outside. 836 return getAddRecExpr(getZeroExtendExpr(Start, Ty), 837 getZeroExtendExpr(Step, Ty), 838 AR->getLoop()); 839 840 // Similar to above, only this time treat the step value as signed. 841 // This covers loops that count down. 842 SCEVHandle SMul = 843 getMulExpr(CastedMaxBECount, 844 getTruncateOrSignExtend(Step, Start->getType())); 845 Add = getAddExpr(Start, SMul); 846 OperandExtendedAdd = 847 getAddExpr(getZeroExtendExpr(Start, WideTy), 848 getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), 849 getSignExtendExpr(Step, WideTy))); 850 if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) 851 // Return the expression with the addrec on the outside. 852 return getAddRecExpr(getZeroExtendExpr(Start, Ty), 853 getSignExtendExpr(Step, Ty), 854 AR->getLoop()); 855 } 856 } 857 } 858 859 SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)]; 860 if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty); 861 return Result; 862} 863 864SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, 865 const Type *Ty) { 866 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) && 867 "This is not an extending conversion!"); 868 assert(isSCEVable(Ty) && 869 "This is not a conversion to a SCEVable type!"); 870 Ty = getEffectiveSCEVType(Ty); 871 872 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) { 873 const Type *IntTy = getEffectiveSCEVType(Ty); 874 Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy); 875 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty); 876 return getUnknown(C); 877 } 878 879 // sext(sext(x)) --> sext(x) 880 if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op)) 881 return getSignExtendExpr(SS->getOperand(), Ty); 882 883 // If the input value is a chrec scev, and we can prove that the value 884 // did not overflow the old, smaller, value, we can sign extend all of the 885 // operands (often constants). This allows analysis of something like 886 // this: for (signed char X = 0; X < 100; ++X) { int Y = X; } 887 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op)) 888 if (AR->isAffine()) { 889 // Check whether the backedge-taken count is SCEVCouldNotCompute. 890 // Note that this serves two purposes: It filters out loops that are 891 // simply not analyzable, and it covers the case where this code is 892 // being called from within backedge-taken count analysis, such that 893 // attempting to ask for the backedge-taken count would likely result 894 // in infinite recursion. In the later case, the analysis code will 895 // cope with a conservative value, and it will take care to purge 896 // that value once it has finished. 897 SCEVHandle MaxBECount = getMaxBackedgeTakenCount(AR->getLoop()); 898 if (!isa<SCEVCouldNotCompute>(MaxBECount)) { 899 // Manually compute the final value for AR, checking for 900 // overflow. 901 SCEVHandle Start = AR->getStart(); 902 SCEVHandle Step = AR->getStepRecurrence(*this); 903 904 // Check whether the backedge-taken count can be losslessly casted to 905 // the addrec's type. The count is always unsigned. 906 SCEVHandle CastedMaxBECount = 907 getTruncateOrZeroExtend(MaxBECount, Start->getType()); 908 SCEVHandle RecastedMaxBECount = 909 getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType()); 910 if (MaxBECount == RecastedMaxBECount) { 911 const Type *WideTy = 912 IntegerType::get(getTypeSizeInBits(Start->getType()) * 2); 913 // Check whether Start+Step*MaxBECount has no signed overflow. 914 SCEVHandle SMul = 915 getMulExpr(CastedMaxBECount, 916 getTruncateOrSignExtend(Step, Start->getType())); 917 SCEVHandle Add = getAddExpr(Start, SMul); 918 SCEVHandle OperandExtendedAdd = 919 getAddExpr(getSignExtendExpr(Start, WideTy), 920 getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), 921 getSignExtendExpr(Step, WideTy))); 922 if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) 923 // Return the expression with the addrec on the outside. 924 return getAddRecExpr(getSignExtendExpr(Start, Ty), 925 getSignExtendExpr(Step, Ty), 926 AR->getLoop()); 927 } 928 } 929 } 930 931 SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)]; 932 if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty); 933 return Result; 934} 935 936// get - Get a canonical add expression, or something simpler if possible. 937SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) { 938 assert(!Ops.empty() && "Cannot get empty add!"); 939 if (Ops.size() == 1) return Ops[0]; 940#ifndef NDEBUG 941 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 942 assert(getEffectiveSCEVType(Ops[i]->getType()) == 943 getEffectiveSCEVType(Ops[0]->getType()) && 944 "SCEVAddExpr operand types don't match!"); 945#endif 946 947 // Sort by complexity, this groups all similar expression types together. 948 GroupByComplexity(Ops, LI); 949 950 // If there are any constants, fold them together. 951 unsigned Idx = 0; 952 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 953 ++Idx; 954 assert(Idx < Ops.size()); 955 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 956 // We found two constants, fold them together! 957 ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() + 958 RHSC->getValue()->getValue()); 959 Ops[0] = getConstant(Fold); 960 Ops.erase(Ops.begin()+1); // Erase the folded element 961 if (Ops.size() == 1) return Ops[0]; 962 LHSC = cast<SCEVConstant>(Ops[0]); 963 } 964 965 // If we are left with a constant zero being added, strip it off. 966 if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) { 967 Ops.erase(Ops.begin()); 968 --Idx; 969 } 970 } 971 972 if (Ops.size() == 1) return Ops[0]; 973 974 // Okay, check to see if the same value occurs in the operand list twice. If 975 // so, merge them together into an multiply expression. Since we sorted the 976 // list, these values are required to be adjacent. 977 const Type *Ty = Ops[0]->getType(); 978 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 979 if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2 980 // Found a match, merge the two values into a multiply, and add any 981 // remaining values to the result. 982 SCEVHandle Two = getIntegerSCEV(2, Ty); 983 SCEVHandle Mul = getMulExpr(Ops[i], Two); 984 if (Ops.size() == 2) 985 return Mul; 986 Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 987 Ops.push_back(Mul); 988 return getAddExpr(Ops); 989 } 990 991 // Check for truncates. If all the operands are truncated from the same 992 // type, see if factoring out the truncate would permit the result to be 993 // folded. eg., trunc(x) + m*trunc(n) --> trunc(x + trunc(m)*n) 994 // if the contents of the resulting outer trunc fold to something simple. 995 for (; Idx < Ops.size() && isa<SCEVTruncateExpr>(Ops[Idx]); ++Idx) { 996 const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Ops[Idx]); 997 const Type *DstType = Trunc->getType(); 998 const Type *SrcType = Trunc->getOperand()->getType(); 999 std::vector<SCEVHandle> LargeOps; 1000 bool Ok = true; 1001 // Check all the operands to see if they can be represented in the 1002 // source type of the truncate. 1003 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1004 if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Ops[i])) { 1005 if (T->getOperand()->getType() != SrcType) { 1006 Ok = false; 1007 break; 1008 } 1009 LargeOps.push_back(T->getOperand()); 1010 } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) { 1011 // This could be either sign or zero extension, but sign extension 1012 // is much more likely to be foldable here. 1013 LargeOps.push_back(getSignExtendExpr(C, SrcType)); 1014 } else if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) { 1015 std::vector<SCEVHandle> LargeMulOps; 1016 for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) { 1017 if (const SCEVTruncateExpr *T = 1018 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) { 1019 if (T->getOperand()->getType() != SrcType) { 1020 Ok = false; 1021 break; 1022 } 1023 LargeMulOps.push_back(T->getOperand()); 1024 } else if (const SCEVConstant *C = 1025 dyn_cast<SCEVConstant>(M->getOperand(j))) { 1026 // This could be either sign or zero extension, but sign extension 1027 // is much more likely to be foldable here. 1028 LargeMulOps.push_back(getSignExtendExpr(C, SrcType)); 1029 } else { 1030 Ok = false; 1031 break; 1032 } 1033 } 1034 if (Ok) 1035 LargeOps.push_back(getMulExpr(LargeMulOps)); 1036 } else { 1037 Ok = false; 1038 break; 1039 } 1040 } 1041 if (Ok) { 1042 // Evaluate the expression in the larger type. 1043 SCEVHandle Fold = getAddExpr(LargeOps); 1044 // If it folds to something simple, use it. Otherwise, don't. 1045 if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold)) 1046 return getTruncateExpr(Fold, DstType); 1047 } 1048 } 1049 1050 // Skip past any other cast SCEVs. 1051 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr) 1052 ++Idx; 1053 1054 // If there are add operands they would be next. 1055 if (Idx < Ops.size()) { 1056 bool DeletedAdd = false; 1057 while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) { 1058 // If we have an add, expand the add operands onto the end of the operands 1059 // list. 1060 Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); 1061 Ops.erase(Ops.begin()+Idx); 1062 DeletedAdd = true; 1063 } 1064 1065 // If we deleted at least one add, we added operands to the end of the list, 1066 // and they are not necessarily sorted. Recurse to resort and resimplify 1067 // any operands we just aquired. 1068 if (DeletedAdd) 1069 return getAddExpr(Ops); 1070 } 1071 1072 // Skip over the add expression until we get to a multiply. 1073 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) 1074 ++Idx; 1075 1076 // If we are adding something to a multiply expression, make sure the 1077 // something is not already an operand of the multiply. If so, merge it into 1078 // the multiply. 1079 for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) { 1080 const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]); 1081 for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) { 1082 const SCEV *MulOpSCEV = Mul->getOperand(MulOp); 1083 for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp) 1084 if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(MulOpSCEV)) { 1085 // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1)) 1086 SCEVHandle InnerMul = Mul->getOperand(MulOp == 0); 1087 if (Mul->getNumOperands() != 2) { 1088 // If the multiply has more than two operands, we must get the 1089 // Y*Z term. 1090 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end()); 1091 MulOps.erase(MulOps.begin()+MulOp); 1092 InnerMul = getMulExpr(MulOps); 1093 } 1094 SCEVHandle One = getIntegerSCEV(1, Ty); 1095 SCEVHandle AddOne = getAddExpr(InnerMul, One); 1096 SCEVHandle OuterMul = getMulExpr(AddOne, Ops[AddOp]); 1097 if (Ops.size() == 2) return OuterMul; 1098 if (AddOp < Idx) { 1099 Ops.erase(Ops.begin()+AddOp); 1100 Ops.erase(Ops.begin()+Idx-1); 1101 } else { 1102 Ops.erase(Ops.begin()+Idx); 1103 Ops.erase(Ops.begin()+AddOp-1); 1104 } 1105 Ops.push_back(OuterMul); 1106 return getAddExpr(Ops); 1107 } 1108 1109 // Check this multiply against other multiplies being added together. 1110 for (unsigned OtherMulIdx = Idx+1; 1111 OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]); 1112 ++OtherMulIdx) { 1113 const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]); 1114 // If MulOp occurs in OtherMul, we can fold the two multiplies 1115 // together. 1116 for (unsigned OMulOp = 0, e = OtherMul->getNumOperands(); 1117 OMulOp != e; ++OMulOp) 1118 if (OtherMul->getOperand(OMulOp) == MulOpSCEV) { 1119 // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E)) 1120 SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0); 1121 if (Mul->getNumOperands() != 2) { 1122 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end()); 1123 MulOps.erase(MulOps.begin()+MulOp); 1124 InnerMul1 = getMulExpr(MulOps); 1125 } 1126 SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0); 1127 if (OtherMul->getNumOperands() != 2) { 1128 std::vector<SCEVHandle> MulOps(OtherMul->op_begin(), 1129 OtherMul->op_end()); 1130 MulOps.erase(MulOps.begin()+OMulOp); 1131 InnerMul2 = getMulExpr(MulOps); 1132 } 1133 SCEVHandle InnerMulSum = getAddExpr(InnerMul1,InnerMul2); 1134 SCEVHandle OuterMul = getMulExpr(MulOpSCEV, InnerMulSum); 1135 if (Ops.size() == 2) return OuterMul; 1136 Ops.erase(Ops.begin()+Idx); 1137 Ops.erase(Ops.begin()+OtherMulIdx-1); 1138 Ops.push_back(OuterMul); 1139 return getAddExpr(Ops); 1140 } 1141 } 1142 } 1143 } 1144 1145 // If there are any add recurrences in the operands list, see if any other 1146 // added values are loop invariant. If so, we can fold them into the 1147 // recurrence. 1148 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) 1149 ++Idx; 1150 1151 // Scan over all recurrences, trying to fold loop invariants into them. 1152 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) { 1153 // Scan all of the other operands to this add and add them to the vector if 1154 // they are loop invariant w.r.t. the recurrence. 1155 std::vector<SCEVHandle> LIOps; 1156 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]); 1157 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 1158 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { 1159 LIOps.push_back(Ops[i]); 1160 Ops.erase(Ops.begin()+i); 1161 --i; --e; 1162 } 1163 1164 // If we found some loop invariants, fold them into the recurrence. 1165 if (!LIOps.empty()) { 1166 // NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step} 1167 LIOps.push_back(AddRec->getStart()); 1168 1169 std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end()); 1170 AddRecOps[0] = getAddExpr(LIOps); 1171 1172 SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop()); 1173 // If all of the other operands were loop invariant, we are done. 1174 if (Ops.size() == 1) return NewRec; 1175 1176 // Otherwise, add the folded AddRec by the non-liv parts. 1177 for (unsigned i = 0;; ++i) 1178 if (Ops[i] == AddRec) { 1179 Ops[i] = NewRec; 1180 break; 1181 } 1182 return getAddExpr(Ops); 1183 } 1184 1185 // Okay, if there weren't any loop invariants to be folded, check to see if 1186 // there are multiple AddRec's with the same loop induction variable being 1187 // added together. If so, we can fold them. 1188 for (unsigned OtherIdx = Idx+1; 1189 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx) 1190 if (OtherIdx != Idx) { 1191 const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]); 1192 if (AddRec->getLoop() == OtherAddRec->getLoop()) { 1193 // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D} 1194 std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end()); 1195 for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) { 1196 if (i >= NewOps.size()) { 1197 NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i, 1198 OtherAddRec->op_end()); 1199 break; 1200 } 1201 NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i)); 1202 } 1203 SCEVHandle NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop()); 1204 1205 if (Ops.size() == 2) return NewAddRec; 1206 1207 Ops.erase(Ops.begin()+Idx); 1208 Ops.erase(Ops.begin()+OtherIdx-1); 1209 Ops.push_back(NewAddRec); 1210 return getAddExpr(Ops); 1211 } 1212 } 1213 1214 // Otherwise couldn't fold anything into this recurrence. Move onto the 1215 // next one. 1216 } 1217 1218 // Okay, it looks like we really DO need an add expr. Check to see if we 1219 // already have one, otherwise create a new one. 1220 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end()); 1221 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr, 1222 SCEVOps)]; 1223 if (Result == 0) Result = new SCEVAddExpr(Ops); 1224 return Result; 1225} 1226 1227 1228SCEVHandle ScalarEvolution::getMulExpr(std::vector<SCEVHandle> &Ops) { 1229 assert(!Ops.empty() && "Cannot get empty mul!"); 1230#ifndef NDEBUG 1231 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 1232 assert(getEffectiveSCEVType(Ops[i]->getType()) == 1233 getEffectiveSCEVType(Ops[0]->getType()) && 1234 "SCEVMulExpr operand types don't match!"); 1235#endif 1236 1237 // Sort by complexity, this groups all similar expression types together. 1238 GroupByComplexity(Ops, LI); 1239 1240 // If there are any constants, fold them together. 1241 unsigned Idx = 0; 1242 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 1243 1244 // C1*(C2+V) -> C1*C2 + C1*V 1245 if (Ops.size() == 2) 1246 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) 1247 if (Add->getNumOperands() == 2 && 1248 isa<SCEVConstant>(Add->getOperand(0))) 1249 return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)), 1250 getMulExpr(LHSC, Add->getOperand(1))); 1251 1252 1253 ++Idx; 1254 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 1255 // We found two constants, fold them together! 1256 ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() * 1257 RHSC->getValue()->getValue()); 1258 Ops[0] = getConstant(Fold); 1259 Ops.erase(Ops.begin()+1); // Erase the folded element 1260 if (Ops.size() == 1) return Ops[0]; 1261 LHSC = cast<SCEVConstant>(Ops[0]); 1262 } 1263 1264 // If we are left with a constant one being multiplied, strip it off. 1265 if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) { 1266 Ops.erase(Ops.begin()); 1267 --Idx; 1268 } else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) { 1269 // If we have a multiply of zero, it will always be zero. 1270 return Ops[0]; 1271 } 1272 } 1273 1274 // Skip over the add expression until we get to a multiply. 1275 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) 1276 ++Idx; 1277 1278 if (Ops.size() == 1) 1279 return Ops[0]; 1280 1281 // If there are mul operands inline them all into this expression. 1282 if (Idx < Ops.size()) { 1283 bool DeletedMul = false; 1284 while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) { 1285 // If we have an mul, expand the mul operands onto the end of the operands 1286 // list. 1287 Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end()); 1288 Ops.erase(Ops.begin()+Idx); 1289 DeletedMul = true; 1290 } 1291 1292 // If we deleted at least one mul, we added operands to the end of the list, 1293 // and they are not necessarily sorted. Recurse to resort and resimplify 1294 // any operands we just aquired. 1295 if (DeletedMul) 1296 return getMulExpr(Ops); 1297 } 1298 1299 // If there are any add recurrences in the operands list, see if any other 1300 // added values are loop invariant. If so, we can fold them into the 1301 // recurrence. 1302 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) 1303 ++Idx; 1304 1305 // Scan over all recurrences, trying to fold loop invariants into them. 1306 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) { 1307 // Scan all of the other operands to this mul and add them to the vector if 1308 // they are loop invariant w.r.t. the recurrence. 1309 std::vector<SCEVHandle> LIOps; 1310 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]); 1311 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 1312 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { 1313 LIOps.push_back(Ops[i]); 1314 Ops.erase(Ops.begin()+i); 1315 --i; --e; 1316 } 1317 1318 // If we found some loop invariants, fold them into the recurrence. 1319 if (!LIOps.empty()) { 1320 // NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step} 1321 std::vector<SCEVHandle> NewOps; 1322 NewOps.reserve(AddRec->getNumOperands()); 1323 if (LIOps.size() == 1) { 1324 const SCEV *Scale = LIOps[0]; 1325 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) 1326 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i))); 1327 } else { 1328 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { 1329 std::vector<SCEVHandle> MulOps(LIOps); 1330 MulOps.push_back(AddRec->getOperand(i)); 1331 NewOps.push_back(getMulExpr(MulOps)); 1332 } 1333 } 1334 1335 SCEVHandle NewRec = getAddRecExpr(NewOps, AddRec->getLoop()); 1336 1337 // If all of the other operands were loop invariant, we are done. 1338 if (Ops.size() == 1) return NewRec; 1339 1340 // Otherwise, multiply the folded AddRec by the non-liv parts. 1341 for (unsigned i = 0;; ++i) 1342 if (Ops[i] == AddRec) { 1343 Ops[i] = NewRec; 1344 break; 1345 } 1346 return getMulExpr(Ops); 1347 } 1348 1349 // Okay, if there weren't any loop invariants to be folded, check to see if 1350 // there are multiple AddRec's with the same loop induction variable being 1351 // multiplied together. If so, we can fold them. 1352 for (unsigned OtherIdx = Idx+1; 1353 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx) 1354 if (OtherIdx != Idx) { 1355 const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]); 1356 if (AddRec->getLoop() == OtherAddRec->getLoop()) { 1357 // F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D} 1358 const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec; 1359 SCEVHandle NewStart = getMulExpr(F->getStart(), 1360 G->getStart()); 1361 SCEVHandle B = F->getStepRecurrence(*this); 1362 SCEVHandle D = G->getStepRecurrence(*this); 1363 SCEVHandle NewStep = getAddExpr(getMulExpr(F, D), 1364 getMulExpr(G, B), 1365 getMulExpr(B, D)); 1366 SCEVHandle NewAddRec = getAddRecExpr(NewStart, NewStep, 1367 F->getLoop()); 1368 if (Ops.size() == 2) return NewAddRec; 1369 1370 Ops.erase(Ops.begin()+Idx); 1371 Ops.erase(Ops.begin()+OtherIdx-1); 1372 Ops.push_back(NewAddRec); 1373 return getMulExpr(Ops); 1374 } 1375 } 1376 1377 // Otherwise couldn't fold anything into this recurrence. Move onto the 1378 // next one. 1379 } 1380 1381 // Okay, it looks like we really DO need an mul expr. Check to see if we 1382 // already have one, otherwise create a new one. 1383 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end()); 1384 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr, 1385 SCEVOps)]; 1386 if (Result == 0) 1387 Result = new SCEVMulExpr(Ops); 1388 return Result; 1389} 1390 1391SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, 1392 const SCEVHandle &RHS) { 1393 assert(getEffectiveSCEVType(LHS->getType()) == 1394 getEffectiveSCEVType(RHS->getType()) && 1395 "SCEVUDivExpr operand types don't match!"); 1396 1397 if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) { 1398 if (RHSC->getValue()->equalsInt(1)) 1399 return LHS; // X udiv 1 --> x 1400 if (RHSC->isZero()) 1401 return getIntegerSCEV(0, LHS->getType()); // value is undefined 1402 1403 // Determine if the division can be folded into the operands of 1404 // its operands. 1405 // TODO: Generalize this to non-constants by using known-bits information. 1406 const Type *Ty = LHS->getType(); 1407 unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros(); 1408 unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ; 1409 // For non-power-of-two values, effectively round the value up to the 1410 // nearest power of two. 1411 if (!RHSC->getValue()->getValue().isPowerOf2()) 1412 ++MaxShiftAmt; 1413 const IntegerType *ExtTy = 1414 IntegerType::get(getTypeSizeInBits(Ty) + MaxShiftAmt); 1415 // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded. 1416 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS)) 1417 if (const SCEVConstant *Step = 1418 dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this))) 1419 if (!Step->getValue()->getValue() 1420 .urem(RHSC->getValue()->getValue()) && 1421 getZeroExtendExpr(AR, ExtTy) == 1422 getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy), 1423 getZeroExtendExpr(Step, ExtTy), 1424 AR->getLoop())) { 1425 std::vector<SCEVHandle> Operands; 1426 for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i) 1427 Operands.push_back(getUDivExpr(AR->getOperand(i), RHS)); 1428 return getAddRecExpr(Operands, AR->getLoop()); 1429 } 1430 // (A*B)/C --> A*(B/C) if safe and B/C can be folded. 1431 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) { 1432 std::vector<SCEVHandle> Operands; 1433 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) 1434 Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy)); 1435 if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands)) 1436 // Find an operand that's safely divisible. 1437 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) { 1438 SCEVHandle Op = M->getOperand(i); 1439 SCEVHandle Div = getUDivExpr(Op, RHSC); 1440 if (!isa<SCEVUDivExpr>(Div) && getMulExpr(Div, RHSC) == Op) { 1441 Operands = M->getOperands(); 1442 Operands[i] = Div; 1443 return getMulExpr(Operands); 1444 } 1445 } 1446 } 1447 // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded. 1448 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(LHS)) { 1449 std::vector<SCEVHandle> Operands; 1450 for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) 1451 Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy)); 1452 if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) { 1453 Operands.clear(); 1454 for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) { 1455 SCEVHandle Op = getUDivExpr(A->getOperand(i), RHS); 1456 if (isa<SCEVUDivExpr>(Op) || getMulExpr(Op, RHS) != A->getOperand(i)) 1457 break; 1458 Operands.push_back(Op); 1459 } 1460 if (Operands.size() == A->getNumOperands()) 1461 return getAddExpr(Operands); 1462 } 1463 } 1464 1465 // Fold if both operands are constant. 1466 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) { 1467 Constant *LHSCV = LHSC->getValue(); 1468 Constant *RHSCV = RHSC->getValue(); 1469 return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV)); 1470 } 1471 } 1472 1473 SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)]; 1474 if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS); 1475 return Result; 1476} 1477 1478 1479/// SCEVAddRecExpr::get - Get a add recurrence expression for the 1480/// specified loop. Simplify the expression as much as possible. 1481SCEVHandle ScalarEvolution::getAddRecExpr(const SCEVHandle &Start, 1482 const SCEVHandle &Step, const Loop *L) { 1483 std::vector<SCEVHandle> Operands; 1484 Operands.push_back(Start); 1485 if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step)) 1486 if (StepChrec->getLoop() == L) { 1487 Operands.insert(Operands.end(), StepChrec->op_begin(), 1488 StepChrec->op_end()); 1489 return getAddRecExpr(Operands, L); 1490 } 1491 1492 Operands.push_back(Step); 1493 return getAddRecExpr(Operands, L); 1494} 1495 1496/// SCEVAddRecExpr::get - Get a add recurrence expression for the 1497/// specified loop. Simplify the expression as much as possible. 1498SCEVHandle ScalarEvolution::getAddRecExpr(std::vector<SCEVHandle> &Operands, 1499 const Loop *L) { 1500 if (Operands.size() == 1) return Operands[0]; 1501#ifndef NDEBUG 1502 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 1503 assert(getEffectiveSCEVType(Operands[i]->getType()) == 1504 getEffectiveSCEVType(Operands[0]->getType()) && 1505 "SCEVAddRecExpr operand types don't match!"); 1506#endif 1507 1508 if (Operands.back()->isZero()) { 1509 Operands.pop_back(); 1510 return getAddRecExpr(Operands, L); // {X,+,0} --> X 1511 } 1512 1513 // Canonicalize nested AddRecs in by nesting them in order of loop depth. 1514 if (const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) { 1515 const Loop* NestedLoop = NestedAR->getLoop(); 1516 if (L->getLoopDepth() < NestedLoop->getLoopDepth()) { 1517 std::vector<SCEVHandle> NestedOperands(NestedAR->op_begin(), 1518 NestedAR->op_end()); 1519 SCEVHandle NestedARHandle(NestedAR); 1520 Operands[0] = NestedAR->getStart(); 1521 NestedOperands[0] = getAddRecExpr(Operands, L); 1522 return getAddRecExpr(NestedOperands, NestedLoop); 1523 } 1524 } 1525 1526 std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end()); 1527 SCEVAddRecExpr *&Result = (*SCEVAddRecExprs)[std::make_pair(L, SCEVOps)]; 1528 if (Result == 0) Result = new SCEVAddRecExpr(Operands, L); 1529 return Result; 1530} 1531 1532SCEVHandle ScalarEvolution::getSMaxExpr(const SCEVHandle &LHS, 1533 const SCEVHandle &RHS) { 1534 std::vector<SCEVHandle> Ops; 1535 Ops.push_back(LHS); 1536 Ops.push_back(RHS); 1537 return getSMaxExpr(Ops); 1538} 1539 1540SCEVHandle ScalarEvolution::getSMaxExpr(std::vector<SCEVHandle> Ops) { 1541 assert(!Ops.empty() && "Cannot get empty smax!"); 1542 if (Ops.size() == 1) return Ops[0]; 1543#ifndef NDEBUG 1544 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 1545 assert(getEffectiveSCEVType(Ops[i]->getType()) == 1546 getEffectiveSCEVType(Ops[0]->getType()) && 1547 "SCEVSMaxExpr operand types don't match!"); 1548#endif 1549 1550 // Sort by complexity, this groups all similar expression types together. 1551 GroupByComplexity(Ops, LI); 1552 1553 // If there are any constants, fold them together. 1554 unsigned Idx = 0; 1555 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 1556 ++Idx; 1557 assert(Idx < Ops.size()); 1558 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 1559 // We found two constants, fold them together! 1560 ConstantInt *Fold = ConstantInt::get( 1561 APIntOps::smax(LHSC->getValue()->getValue(), 1562 RHSC->getValue()->getValue())); 1563 Ops[0] = getConstant(Fold); 1564 Ops.erase(Ops.begin()+1); // Erase the folded element 1565 if (Ops.size() == 1) return Ops[0]; 1566 LHSC = cast<SCEVConstant>(Ops[0]); 1567 } 1568 1569 // If we are left with a constant -inf, strip it off. 1570 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) { 1571 Ops.erase(Ops.begin()); 1572 --Idx; 1573 } 1574 } 1575 1576 if (Ops.size() == 1) return Ops[0]; 1577 1578 // Find the first SMax 1579 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr) 1580 ++Idx; 1581 1582 // Check to see if one of the operands is an SMax. If so, expand its operands 1583 // onto our operand list, and recurse to simplify. 1584 if (Idx < Ops.size()) { 1585 bool DeletedSMax = false; 1586 while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) { 1587 Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end()); 1588 Ops.erase(Ops.begin()+Idx); 1589 DeletedSMax = true; 1590 } 1591 1592 if (DeletedSMax) 1593 return getSMaxExpr(Ops); 1594 } 1595 1596 // Okay, check to see if the same value occurs in the operand list twice. If 1597 // so, delete one. Since we sorted the list, these values are required to 1598 // be adjacent. 1599 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 1600 if (Ops[i] == Ops[i+1]) { // X smax Y smax Y --> X smax Y 1601 Ops.erase(Ops.begin()+i, Ops.begin()+i+1); 1602 --i; --e; 1603 } 1604 1605 if (Ops.size() == 1) return Ops[0]; 1606 1607 assert(!Ops.empty() && "Reduced smax down to nothing!"); 1608 1609 // Okay, it looks like we really DO need an smax expr. Check to see if we 1610 // already have one, otherwise create a new one. 1611 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end()); 1612 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr, 1613 SCEVOps)]; 1614 if (Result == 0) Result = new SCEVSMaxExpr(Ops); 1615 return Result; 1616} 1617 1618SCEVHandle ScalarEvolution::getUMaxExpr(const SCEVHandle &LHS, 1619 const SCEVHandle &RHS) { 1620 std::vector<SCEVHandle> Ops; 1621 Ops.push_back(LHS); 1622 Ops.push_back(RHS); 1623 return getUMaxExpr(Ops); 1624} 1625 1626SCEVHandle ScalarEvolution::getUMaxExpr(std::vector<SCEVHandle> Ops) { 1627 assert(!Ops.empty() && "Cannot get empty umax!"); 1628 if (Ops.size() == 1) return Ops[0]; 1629#ifndef NDEBUG 1630 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 1631 assert(getEffectiveSCEVType(Ops[i]->getType()) == 1632 getEffectiveSCEVType(Ops[0]->getType()) && 1633 "SCEVUMaxExpr operand types don't match!"); 1634#endif 1635 1636 // Sort by complexity, this groups all similar expression types together. 1637 GroupByComplexity(Ops, LI); 1638 1639 // If there are any constants, fold them together. 1640 unsigned Idx = 0; 1641 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 1642 ++Idx; 1643 assert(Idx < Ops.size()); 1644 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 1645 // We found two constants, fold them together! 1646 ConstantInt *Fold = ConstantInt::get( 1647 APIntOps::umax(LHSC->getValue()->getValue(), 1648 RHSC->getValue()->getValue())); 1649 Ops[0] = getConstant(Fold); 1650 Ops.erase(Ops.begin()+1); // Erase the folded element 1651 if (Ops.size() == 1) return Ops[0]; 1652 LHSC = cast<SCEVConstant>(Ops[0]); 1653 } 1654 1655 // If we are left with a constant zero, strip it off. 1656 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) { 1657 Ops.erase(Ops.begin()); 1658 --Idx; 1659 } 1660 } 1661 1662 if (Ops.size() == 1) return Ops[0]; 1663 1664 // Find the first UMax 1665 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr) 1666 ++Idx; 1667 1668 // Check to see if one of the operands is a UMax. If so, expand its operands 1669 // onto our operand list, and recurse to simplify. 1670 if (Idx < Ops.size()) { 1671 bool DeletedUMax = false; 1672 while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) { 1673 Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end()); 1674 Ops.erase(Ops.begin()+Idx); 1675 DeletedUMax = true; 1676 } 1677 1678 if (DeletedUMax) 1679 return getUMaxExpr(Ops); 1680 } 1681 1682 // Okay, check to see if the same value occurs in the operand list twice. If 1683 // so, delete one. Since we sorted the list, these values are required to 1684 // be adjacent. 1685 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 1686 if (Ops[i] == Ops[i+1]) { // X umax Y umax Y --> X umax Y 1687 Ops.erase(Ops.begin()+i, Ops.begin()+i+1); 1688 --i; --e; 1689 } 1690 1691 if (Ops.size() == 1) return Ops[0]; 1692 1693 assert(!Ops.empty() && "Reduced umax down to nothing!"); 1694 1695 // Okay, it looks like we really DO need a umax expr. Check to see if we 1696 // already have one, otherwise create a new one. 1697 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end()); 1698 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr, 1699 SCEVOps)]; 1700 if (Result == 0) Result = new SCEVUMaxExpr(Ops); 1701 return Result; 1702} 1703 1704SCEVHandle ScalarEvolution::getUnknown(Value *V) { 1705 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 1706 return getConstant(CI); 1707 if (isa<ConstantPointerNull>(V)) 1708 return getIntegerSCEV(0, V->getType()); 1709 SCEVUnknown *&Result = (*SCEVUnknowns)[V]; 1710 if (Result == 0) Result = new SCEVUnknown(V); 1711 return Result; 1712} 1713 1714//===----------------------------------------------------------------------===// 1715// Basic SCEV Analysis and PHI Idiom Recognition Code 1716// 1717 1718/// isSCEVable - Test if values of the given type are analyzable within 1719/// the SCEV framework. This primarily includes integer types, and it 1720/// can optionally include pointer types if the ScalarEvolution class 1721/// has access to target-specific information. 1722bool ScalarEvolution::isSCEVable(const Type *Ty) const { 1723 // Integers are always SCEVable. 1724 if (Ty->isInteger()) 1725 return true; 1726 1727 // Pointers are SCEVable if TargetData information is available 1728 // to provide pointer size information. 1729 if (isa<PointerType>(Ty)) 1730 return TD != NULL; 1731 1732 // Otherwise it's not SCEVable. 1733 return false; 1734} 1735 1736/// getTypeSizeInBits - Return the size in bits of the specified type, 1737/// for which isSCEVable must return true. 1738uint64_t ScalarEvolution::getTypeSizeInBits(const Type *Ty) const { 1739 assert(isSCEVable(Ty) && "Type is not SCEVable!"); 1740 1741 // If we have a TargetData, use it! 1742 if (TD) 1743 return TD->getTypeSizeInBits(Ty); 1744 1745 // Otherwise, we support only integer types. 1746 assert(Ty->isInteger() && "isSCEVable permitted a non-SCEVable type!"); 1747 return Ty->getPrimitiveSizeInBits(); 1748} 1749 1750/// getEffectiveSCEVType - Return a type with the same bitwidth as 1751/// the given type and which represents how SCEV will treat the given 1752/// type, for which isSCEVable must return true. For pointer types, 1753/// this is the pointer-sized integer type. 1754const Type *ScalarEvolution::getEffectiveSCEVType(const Type *Ty) const { 1755 assert(isSCEVable(Ty) && "Type is not SCEVable!"); 1756 1757 if (Ty->isInteger()) 1758 return Ty; 1759 1760 assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!"); 1761 return TD->getIntPtrType(); 1762} 1763 1764SCEVHandle ScalarEvolution::getCouldNotCompute() { 1765 return UnknownValue; 1766} 1767 1768/// hasSCEV - Return true if the SCEV for this value has already been 1769/// computed. 1770bool ScalarEvolution::hasSCEV(Value *V) const { 1771 return Scalars.count(V); 1772} 1773 1774/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the 1775/// expression and create a new one. 1776SCEVHandle ScalarEvolution::getSCEV(Value *V) { 1777 assert(isSCEVable(V->getType()) && "Value is not SCEVable!"); 1778 1779 std::map<SCEVCallbackVH, SCEVHandle>::iterator I = Scalars.find(V); 1780 if (I != Scalars.end()) return I->second; 1781 SCEVHandle S = createSCEV(V); 1782 Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S)); 1783 return S; 1784} 1785 1786/// getIntegerSCEV - Given an integer or FP type, create a constant for the 1787/// specified signed integer value and return a SCEV for the constant. 1788SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) { 1789 Ty = getEffectiveSCEVType(Ty); 1790 Constant *C; 1791 if (Val == 0) 1792 C = Constant::getNullValue(Ty); 1793 else if (Ty->isFloatingPoint()) 1794 C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle : 1795 APFloat::IEEEdouble, Val)); 1796 else 1797 C = ConstantInt::get(Ty, Val); 1798 return getUnknown(C); 1799} 1800 1801/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V 1802/// 1803SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) { 1804 if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) 1805 return getUnknown(ConstantExpr::getNeg(VC->getValue())); 1806 1807 const Type *Ty = V->getType(); 1808 Ty = getEffectiveSCEVType(Ty); 1809 return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(Ty))); 1810} 1811 1812/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V 1813SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) { 1814 if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) 1815 return getUnknown(ConstantExpr::getNot(VC->getValue())); 1816 1817 const Type *Ty = V->getType(); 1818 Ty = getEffectiveSCEVType(Ty); 1819 SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(Ty)); 1820 return getMinusSCEV(AllOnes, V); 1821} 1822 1823/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS. 1824/// 1825SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS, 1826 const SCEVHandle &RHS) { 1827 // X - Y --> X + -Y 1828 return getAddExpr(LHS, getNegativeSCEV(RHS)); 1829} 1830 1831/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the 1832/// input value to the specified type. If the type must be extended, it is zero 1833/// extended. 1834SCEVHandle 1835ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V, 1836 const Type *Ty) { 1837 const Type *SrcTy = V->getType(); 1838 assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) && 1839 (Ty->isInteger() || (TD && isa<PointerType>(Ty))) && 1840 "Cannot truncate or zero extend with non-integer arguments!"); 1841 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 1842 return V; // No conversion 1843 if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty)) 1844 return getTruncateExpr(V, Ty); 1845 return getZeroExtendExpr(V, Ty); 1846} 1847 1848/// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion of the 1849/// input value to the specified type. If the type must be extended, it is sign 1850/// extended. 1851SCEVHandle 1852ScalarEvolution::getTruncateOrSignExtend(const SCEVHandle &V, 1853 const Type *Ty) { 1854 const Type *SrcTy = V->getType(); 1855 assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) && 1856 (Ty->isInteger() || (TD && isa<PointerType>(Ty))) && 1857 "Cannot truncate or zero extend with non-integer arguments!"); 1858 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 1859 return V; // No conversion 1860 if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty)) 1861 return getTruncateExpr(V, Ty); 1862 return getSignExtendExpr(V, Ty); 1863} 1864 1865/// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of the 1866/// input value to the specified type. If the type must be extended, it is zero 1867/// extended. The conversion must not be narrowing. 1868SCEVHandle 1869ScalarEvolution::getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty) { 1870 const Type *SrcTy = V->getType(); 1871 assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) && 1872 (Ty->isInteger() || (TD && isa<PointerType>(Ty))) && 1873 "Cannot noop or zero extend with non-integer arguments!"); 1874 assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) && 1875 "getNoopOrZeroExtend cannot truncate!"); 1876 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 1877 return V; // No conversion 1878 return getZeroExtendExpr(V, Ty); 1879} 1880 1881/// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of the 1882/// input value to the specified type. If the type must be extended, it is sign 1883/// extended. The conversion must not be narrowing. 1884SCEVHandle 1885ScalarEvolution::getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty) { 1886 const Type *SrcTy = V->getType(); 1887 assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) && 1888 (Ty->isInteger() || (TD && isa<PointerType>(Ty))) && 1889 "Cannot noop or sign extend with non-integer arguments!"); 1890 assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) && 1891 "getNoopOrSignExtend cannot truncate!"); 1892 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 1893 return V; // No conversion 1894 return getSignExtendExpr(V, Ty); 1895} 1896 1897/// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 1898/// input value to the specified type. The conversion must not be widening. 1899SCEVHandle 1900ScalarEvolution::getTruncateOrNoop(const SCEVHandle &V, const Type *Ty) { 1901 const Type *SrcTy = V->getType(); 1902 assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) && 1903 (Ty->isInteger() || (TD && isa<PointerType>(Ty))) && 1904 "Cannot truncate or noop with non-integer arguments!"); 1905 assert(getTypeSizeInBits(SrcTy) >= getTypeSizeInBits(Ty) && 1906 "getTruncateOrNoop cannot extend!"); 1907 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 1908 return V; // No conversion 1909 return getTruncateExpr(V, Ty); 1910} 1911 1912/// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for 1913/// the specified instruction and replaces any references to the symbolic value 1914/// SymName with the specified value. This is used during PHI resolution. 1915void ScalarEvolution:: 1916ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName, 1917 const SCEVHandle &NewVal) { 1918 std::map<SCEVCallbackVH, SCEVHandle>::iterator SI = 1919 Scalars.find(SCEVCallbackVH(I, this)); 1920 if (SI == Scalars.end()) return; 1921 1922 SCEVHandle NV = 1923 SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, *this); 1924 if (NV == SI->second) return; // No change. 1925 1926 SI->second = NV; // Update the scalars map! 1927 1928 // Any instruction values that use this instruction might also need to be 1929 // updated! 1930 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1931 UI != E; ++UI) 1932 ReplaceSymbolicValueWithConcrete(cast<Instruction>(*UI), SymName, NewVal); 1933} 1934 1935/// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in 1936/// a loop header, making it a potential recurrence, or it doesn't. 1937/// 1938SCEVHandle ScalarEvolution::createNodeForPHI(PHINode *PN) { 1939 if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized. 1940 if (const Loop *L = LI->getLoopFor(PN->getParent())) 1941 if (L->getHeader() == PN->getParent()) { 1942 // If it lives in the loop header, it has two incoming values, one 1943 // from outside the loop, and one from inside. 1944 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 1945 unsigned BackEdge = IncomingEdge^1; 1946 1947 // While we are analyzing this PHI node, handle its value symbolically. 1948 SCEVHandle SymbolicName = getUnknown(PN); 1949 assert(Scalars.find(PN) == Scalars.end() && 1950 "PHI node already processed?"); 1951 Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName)); 1952 1953 // Using this symbolic name for the PHI, analyze the value coming around 1954 // the back-edge. 1955 SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge)); 1956 1957 // NOTE: If BEValue is loop invariant, we know that the PHI node just 1958 // has a special value for the first iteration of the loop. 1959 1960 // If the value coming around the backedge is an add with the symbolic 1961 // value we just inserted, then we found a simple induction variable! 1962 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) { 1963 // If there is a single occurrence of the symbolic value, replace it 1964 // with a recurrence. 1965 unsigned FoundIndex = Add->getNumOperands(); 1966 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) 1967 if (Add->getOperand(i) == SymbolicName) 1968 if (FoundIndex == e) { 1969 FoundIndex = i; 1970 break; 1971 } 1972 1973 if (FoundIndex != Add->getNumOperands()) { 1974 // Create an add with everything but the specified operand. 1975 std::vector<SCEVHandle> Ops; 1976 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) 1977 if (i != FoundIndex) 1978 Ops.push_back(Add->getOperand(i)); 1979 SCEVHandle Accum = getAddExpr(Ops); 1980 1981 // This is not a valid addrec if the step amount is varying each 1982 // loop iteration, but is not itself an addrec in this loop. 1983 if (Accum->isLoopInvariant(L) || 1984 (isa<SCEVAddRecExpr>(Accum) && 1985 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) { 1986 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); 1987 SCEVHandle PHISCEV = getAddRecExpr(StartVal, Accum, L); 1988 1989 // Okay, for the entire analysis of this edge we assumed the PHI 1990 // to be symbolic. We now need to go back and update all of the 1991 // entries for the scalars that use the PHI (except for the PHI 1992 // itself) to use the new analyzed value instead of the "symbolic" 1993 // value. 1994 ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV); 1995 return PHISCEV; 1996 } 1997 } 1998 } else if (const SCEVAddRecExpr *AddRec = 1999 dyn_cast<SCEVAddRecExpr>(BEValue)) { 2000 // Otherwise, this could be a loop like this: 2001 // i = 0; for (j = 1; ..; ++j) { .... i = j; } 2002 // In this case, j = {1,+,1} and BEValue is j. 2003 // Because the other in-value of i (0) fits the evolution of BEValue 2004 // i really is an addrec evolution. 2005 if (AddRec->getLoop() == L && AddRec->isAffine()) { 2006 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); 2007 2008 // If StartVal = j.start - j.stride, we can use StartVal as the 2009 // initial step of the addrec evolution. 2010 if (StartVal == getMinusSCEV(AddRec->getOperand(0), 2011 AddRec->getOperand(1))) { 2012 SCEVHandle PHISCEV = 2013 getAddRecExpr(StartVal, AddRec->getOperand(1), L); 2014 2015 // Okay, for the entire analysis of this edge we assumed the PHI 2016 // to be symbolic. We now need to go back and update all of the 2017 // entries for the scalars that use the PHI (except for the PHI 2018 // itself) to use the new analyzed value instead of the "symbolic" 2019 // value. 2020 ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV); 2021 return PHISCEV; 2022 } 2023 } 2024 } 2025 2026 return SymbolicName; 2027 } 2028 2029 // If it's not a loop phi, we can't handle it yet. 2030 return getUnknown(PN); 2031} 2032 2033/// createNodeForGEP - Expand GEP instructions into add and multiply 2034/// operations. This allows them to be analyzed by regular SCEV code. 2035/// 2036SCEVHandle ScalarEvolution::createNodeForGEP(User *GEP) { 2037 2038 const Type *IntPtrTy = TD->getIntPtrType(); 2039 Value *Base = GEP->getOperand(0); 2040 // Don't attempt to analyze GEPs over unsized objects. 2041 if (!cast<PointerType>(Base->getType())->getElementType()->isSized()) 2042 return getUnknown(GEP); 2043 SCEVHandle TotalOffset = getIntegerSCEV(0, IntPtrTy); 2044 gep_type_iterator GTI = gep_type_begin(GEP); 2045 for (GetElementPtrInst::op_iterator I = next(GEP->op_begin()), 2046 E = GEP->op_end(); 2047 I != E; ++I) { 2048 Value *Index = *I; 2049 // Compute the (potentially symbolic) offset in bytes for this index. 2050 if (const StructType *STy = dyn_cast<StructType>(*GTI++)) { 2051 // For a struct, add the member offset. 2052 const StructLayout &SL = *TD->getStructLayout(STy); 2053 unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 2054 uint64_t Offset = SL.getElementOffset(FieldNo); 2055 TotalOffset = getAddExpr(TotalOffset, 2056 getIntegerSCEV(Offset, IntPtrTy)); 2057 } else { 2058 // For an array, add the element offset, explicitly scaled. 2059 SCEVHandle LocalOffset = getSCEV(Index); 2060 if (!isa<PointerType>(LocalOffset->getType())) 2061 // Getelementptr indicies are signed. 2062 LocalOffset = getTruncateOrSignExtend(LocalOffset, 2063 IntPtrTy); 2064 LocalOffset = 2065 getMulExpr(LocalOffset, 2066 getIntegerSCEV(TD->getTypeAllocSize(*GTI), 2067 IntPtrTy)); 2068 TotalOffset = getAddExpr(TotalOffset, LocalOffset); 2069 } 2070 } 2071 return getAddExpr(getSCEV(Base), TotalOffset); 2072} 2073 2074/// GetMinTrailingZeros - Determine the minimum number of zero bits that S is 2075/// guaranteed to end in (at every loop iteration). It is, at the same time, 2076/// the minimum number of times S is divisible by 2. For example, given {4,+,8} 2077/// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S. 2078static uint32_t GetMinTrailingZeros(SCEVHandle S, const ScalarEvolution &SE) { 2079 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) 2080 return C->getValue()->getValue().countTrailingZeros(); 2081 2082 if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S)) 2083 return std::min(GetMinTrailingZeros(T->getOperand(), SE), 2084 (uint32_t)SE.getTypeSizeInBits(T->getType())); 2085 2086 if (const SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) { 2087 uint32_t OpRes = GetMinTrailingZeros(E->getOperand(), SE); 2088 return OpRes == SE.getTypeSizeInBits(E->getOperand()->getType()) ? 2089 SE.getTypeSizeInBits(E->getType()) : OpRes; 2090 } 2091 2092 if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) { 2093 uint32_t OpRes = GetMinTrailingZeros(E->getOperand(), SE); 2094 return OpRes == SE.getTypeSizeInBits(E->getOperand()->getType()) ? 2095 SE.getTypeSizeInBits(E->getType()) : OpRes; 2096 } 2097 2098 if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 2099 // The result is the min of all operands results. 2100 uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE); 2101 for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i) 2102 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), SE)); 2103 return MinOpRes; 2104 } 2105 2106 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) { 2107 // The result is the sum of all operands results. 2108 uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0), SE); 2109 uint32_t BitWidth = SE.getTypeSizeInBits(M->getType()); 2110 for (unsigned i = 1, e = M->getNumOperands(); 2111 SumOpRes != BitWidth && i != e; ++i) 2112 SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i), SE), 2113 BitWidth); 2114 return SumOpRes; 2115 } 2116 2117 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 2118 // The result is the min of all operands results. 2119 uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE); 2120 for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i) 2121 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), SE)); 2122 return MinOpRes; 2123 } 2124 2125 if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) { 2126 // The result is the min of all operands results. 2127 uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE); 2128 for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i) 2129 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), SE)); 2130 return MinOpRes; 2131 } 2132 2133 if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) { 2134 // The result is the min of all operands results. 2135 uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE); 2136 for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i) 2137 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), SE)); 2138 return MinOpRes; 2139 } 2140 2141 // SCEVUDivExpr, SCEVUnknown 2142 return 0; 2143} 2144 2145/// createSCEV - We know that there is no SCEV for the specified value. 2146/// Analyze the expression. 2147/// 2148SCEVHandle ScalarEvolution::createSCEV(Value *V) { 2149 if (!isSCEVable(V->getType())) 2150 return getUnknown(V); 2151 2152 unsigned Opcode = Instruction::UserOp1; 2153 if (Instruction *I = dyn_cast<Instruction>(V)) 2154 Opcode = I->getOpcode(); 2155 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 2156 Opcode = CE->getOpcode(); 2157 else 2158 return getUnknown(V); 2159 2160 User *U = cast<User>(V); 2161 switch (Opcode) { 2162 case Instruction::Add: 2163 return getAddExpr(getSCEV(U->getOperand(0)), 2164 getSCEV(U->getOperand(1))); 2165 case Instruction::Mul: 2166 return getMulExpr(getSCEV(U->getOperand(0)), 2167 getSCEV(U->getOperand(1))); 2168 case Instruction::UDiv: 2169 return getUDivExpr(getSCEV(U->getOperand(0)), 2170 getSCEV(U->getOperand(1))); 2171 case Instruction::Sub: 2172 return getMinusSCEV(getSCEV(U->getOperand(0)), 2173 getSCEV(U->getOperand(1))); 2174 case Instruction::And: 2175 // For an expression like x&255 that merely masks off the high bits, 2176 // use zext(trunc(x)) as the SCEV expression. 2177 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) { 2178 if (CI->isNullValue()) 2179 return getSCEV(U->getOperand(1)); 2180 if (CI->isAllOnesValue()) 2181 return getSCEV(U->getOperand(0)); 2182 const APInt &A = CI->getValue(); 2183 unsigned Ones = A.countTrailingOnes(); 2184 if (APIntOps::isMask(Ones, A)) 2185 return 2186 getZeroExtendExpr(getTruncateExpr(getSCEV(U->getOperand(0)), 2187 IntegerType::get(Ones)), 2188 U->getType()); 2189 } 2190 break; 2191 case Instruction::Or: 2192 // If the RHS of the Or is a constant, we may have something like: 2193 // X*4+1 which got turned into X*4|1. Handle this as an Add so loop 2194 // optimizations will transparently handle this case. 2195 // 2196 // In order for this transformation to be safe, the LHS must be of the 2197 // form X*(2^n) and the Or constant must be less than 2^n. 2198 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) { 2199 SCEVHandle LHS = getSCEV(U->getOperand(0)); 2200 const APInt &CIVal = CI->getValue(); 2201 if (GetMinTrailingZeros(LHS, *this) >= 2202 (CIVal.getBitWidth() - CIVal.countLeadingZeros())) 2203 return getAddExpr(LHS, getSCEV(U->getOperand(1))); 2204 } 2205 break; 2206 case Instruction::Xor: 2207 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) { 2208 // If the RHS of the xor is a signbit, then this is just an add. 2209 // Instcombine turns add of signbit into xor as a strength reduction step. 2210 if (CI->getValue().isSignBit()) 2211 return getAddExpr(getSCEV(U->getOperand(0)), 2212 getSCEV(U->getOperand(1))); 2213 2214 // If the RHS of xor is -1, then this is a not operation. 2215 if (CI->isAllOnesValue()) 2216 return getNotSCEV(getSCEV(U->getOperand(0))); 2217 2218 // Model xor(and(x, C), C) as and(~x, C), if C is a low-bits mask. 2219 // This is a variant of the check for xor with -1, and it handles 2220 // the case where instcombine has trimmed non-demanded bits out 2221 // of an xor with -1. 2222 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U->getOperand(0))) 2223 if (ConstantInt *LCI = dyn_cast<ConstantInt>(BO->getOperand(1))) 2224 if (BO->getOpcode() == Instruction::And && 2225 LCI->getValue() == CI->getValue()) 2226 if (const SCEVZeroExtendExpr *Z = 2227 dyn_cast<SCEVZeroExtendExpr>(getSCEV(U->getOperand(0)))) 2228 return getZeroExtendExpr(getNotSCEV(Z->getOperand()), 2229 U->getType()); 2230 } 2231 break; 2232 2233 case Instruction::Shl: 2234 // Turn shift left of a constant amount into a multiply. 2235 if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) { 2236 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 2237 Constant *X = ConstantInt::get( 2238 APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth))); 2239 return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X)); 2240 } 2241 break; 2242 2243 case Instruction::LShr: 2244 // Turn logical shift right of a constant into a unsigned divide. 2245 if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) { 2246 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 2247 Constant *X = ConstantInt::get( 2248 APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth))); 2249 return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X)); 2250 } 2251 break; 2252 2253 case Instruction::AShr: 2254 // For a two-shift sext-inreg, use sext(trunc(x)) as the SCEV expression. 2255 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) 2256 if (Instruction *L = dyn_cast<Instruction>(U->getOperand(0))) 2257 if (L->getOpcode() == Instruction::Shl && 2258 L->getOperand(1) == U->getOperand(1)) { 2259 unsigned BitWidth = getTypeSizeInBits(U->getType()); 2260 uint64_t Amt = BitWidth - CI->getZExtValue(); 2261 if (Amt == BitWidth) 2262 return getSCEV(L->getOperand(0)); // shift by zero --> noop 2263 if (Amt > BitWidth) 2264 return getIntegerSCEV(0, U->getType()); // value is undefined 2265 return 2266 getSignExtendExpr(getTruncateExpr(getSCEV(L->getOperand(0)), 2267 IntegerType::get(Amt)), 2268 U->getType()); 2269 } 2270 break; 2271 2272 case Instruction::Trunc: 2273 return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType()); 2274 2275 case Instruction::ZExt: 2276 return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType()); 2277 2278 case Instruction::SExt: 2279 return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType()); 2280 2281 case Instruction::BitCast: 2282 // BitCasts are no-op casts so we just eliminate the cast. 2283 if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) 2284 return getSCEV(U->getOperand(0)); 2285 break; 2286 2287 case Instruction::IntToPtr: 2288 if (!TD) break; // Without TD we can't analyze pointers. 2289 return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)), 2290 TD->getIntPtrType()); 2291 2292 case Instruction::PtrToInt: 2293 if (!TD) break; // Without TD we can't analyze pointers. 2294 return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)), 2295 U->getType()); 2296 2297 case Instruction::GetElementPtr: 2298 if (!TD) break; // Without TD we can't analyze pointers. 2299 return createNodeForGEP(U); 2300 2301 case Instruction::PHI: 2302 return createNodeForPHI(cast<PHINode>(U)); 2303 2304 case Instruction::Select: 2305 // This could be a smax or umax that was lowered earlier. 2306 // Try to recover it. 2307 if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) { 2308 Value *LHS = ICI->getOperand(0); 2309 Value *RHS = ICI->getOperand(1); 2310 switch (ICI->getPredicate()) { 2311 case ICmpInst::ICMP_SLT: 2312 case ICmpInst::ICMP_SLE: 2313 std::swap(LHS, RHS); 2314 // fall through 2315 case ICmpInst::ICMP_SGT: 2316 case ICmpInst::ICMP_SGE: 2317 if (LHS == U->getOperand(1) && RHS == U->getOperand(2)) 2318 return getSMaxExpr(getSCEV(LHS), getSCEV(RHS)); 2319 else if (LHS == U->getOperand(2) && RHS == U->getOperand(1)) 2320 // ~smax(~x, ~y) == smin(x, y). 2321 return getNotSCEV(getSMaxExpr( 2322 getNotSCEV(getSCEV(LHS)), 2323 getNotSCEV(getSCEV(RHS)))); 2324 break; 2325 case ICmpInst::ICMP_ULT: 2326 case ICmpInst::ICMP_ULE: 2327 std::swap(LHS, RHS); 2328 // fall through 2329 case ICmpInst::ICMP_UGT: 2330 case ICmpInst::ICMP_UGE: 2331 if (LHS == U->getOperand(1) && RHS == U->getOperand(2)) 2332 return getUMaxExpr(getSCEV(LHS), getSCEV(RHS)); 2333 else if (LHS == U->getOperand(2) && RHS == U->getOperand(1)) 2334 // ~umax(~x, ~y) == umin(x, y) 2335 return getNotSCEV(getUMaxExpr(getNotSCEV(getSCEV(LHS)), 2336 getNotSCEV(getSCEV(RHS)))); 2337 break; 2338 default: 2339 break; 2340 } 2341 } 2342 2343 default: // We cannot analyze this expression. 2344 break; 2345 } 2346 2347 return getUnknown(V); 2348} 2349 2350 2351 2352//===----------------------------------------------------------------------===// 2353// Iteration Count Computation Code 2354// 2355 2356/// getBackedgeTakenCount - If the specified loop has a predictable 2357/// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 2358/// object. The backedge-taken count is the number of times the loop header 2359/// will be branched to from within the loop. This is one less than the 2360/// trip count of the loop, since it doesn't count the first iteration, 2361/// when the header is branched to from outside the loop. 2362/// 2363/// Note that it is not valid to call this method on a loop without a 2364/// loop-invariant backedge-taken count (see 2365/// hasLoopInvariantBackedgeTakenCount). 2366/// 2367SCEVHandle ScalarEvolution::getBackedgeTakenCount(const Loop *L) { 2368 return getBackedgeTakenInfo(L).Exact; 2369} 2370 2371/// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 2372/// return the least SCEV value that is known never to be less than the 2373/// actual backedge taken count. 2374SCEVHandle ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) { 2375 return getBackedgeTakenInfo(L).Max; 2376} 2377 2378const ScalarEvolution::BackedgeTakenInfo & 2379ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { 2380 // Initially insert a CouldNotCompute for this loop. If the insertion 2381 // succeeds, procede to actually compute a backedge-taken count and 2382 // update the value. The temporary CouldNotCompute value tells SCEV 2383 // code elsewhere that it shouldn't attempt to request a new 2384 // backedge-taken count, which could result in infinite recursion. 2385 std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair = 2386 BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute())); 2387 if (Pair.second) { 2388 BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L); 2389 if (ItCount.Exact != UnknownValue) { 2390 assert(ItCount.Exact->isLoopInvariant(L) && 2391 ItCount.Max->isLoopInvariant(L) && 2392 "Computed trip count isn't loop invariant for loop!"); 2393 ++NumTripCountsComputed; 2394 2395 // Update the value in the map. 2396 Pair.first->second = ItCount; 2397 } else if (isa<PHINode>(L->getHeader()->begin())) { 2398 // Only count loops that have phi nodes as not being computable. 2399 ++NumTripCountsNotComputed; 2400 } 2401 2402 // Now that we know more about the trip count for this loop, forget any 2403 // existing SCEV values for PHI nodes in this loop since they are only 2404 // conservative estimates made without the benefit 2405 // of trip count information. 2406 if (ItCount.hasAnyInfo()) 2407 forgetLoopPHIs(L); 2408 } 2409 return Pair.first->second; 2410} 2411 2412/// forgetLoopBackedgeTakenCount - This method should be called by the 2413/// client when it has changed a loop in a way that may effect 2414/// ScalarEvolution's ability to compute a trip count, or if the loop 2415/// is deleted. 2416void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) { 2417 BackedgeTakenCounts.erase(L); 2418 forgetLoopPHIs(L); 2419} 2420 2421/// forgetLoopPHIs - Delete the memoized SCEVs associated with the 2422/// PHI nodes in the given loop. This is used when the trip count of 2423/// the loop may have changed. 2424void ScalarEvolution::forgetLoopPHIs(const Loop *L) { 2425 BasicBlock *Header = L->getHeader(); 2426 2427 // Push all Loop-header PHIs onto the Worklist stack, except those 2428 // that are presently represented via a SCEVUnknown. SCEVUnknown for 2429 // a PHI either means that it has an unrecognized structure, or it's 2430 // a PHI that's in the progress of being computed by createNodeForPHI. 2431 // In the former case, additional loop trip count information isn't 2432 // going to change anything. In the later case, createNodeForPHI will 2433 // perform the necessary updates on its own when it gets to that point. 2434 SmallVector<Instruction *, 16> Worklist; 2435 for (BasicBlock::iterator I = Header->begin(); 2436 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 2437 std::map<SCEVCallbackVH, SCEVHandle>::iterator It = Scalars.find((Value*)I); 2438 if (It != Scalars.end() && !isa<SCEVUnknown>(It->second)) 2439 Worklist.push_back(PN); 2440 } 2441 2442 while (!Worklist.empty()) { 2443 Instruction *I = Worklist.pop_back_val(); 2444 if (Scalars.erase(I)) 2445 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 2446 UI != UE; ++UI) 2447 Worklist.push_back(cast<Instruction>(UI)); 2448 } 2449} 2450 2451/// ComputeBackedgeTakenCount - Compute the number of times the backedge 2452/// of the specified loop will execute. 2453ScalarEvolution::BackedgeTakenInfo 2454ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) { 2455 // If the loop has a non-one exit block count, we can't analyze it. 2456 SmallVector<BasicBlock*, 8> ExitBlocks; 2457 L->getExitBlocks(ExitBlocks); 2458 if (ExitBlocks.size() != 1) return UnknownValue; 2459 2460 // Okay, there is one exit block. Try to find the condition that causes the 2461 // loop to be exited. 2462 BasicBlock *ExitBlock = ExitBlocks[0]; 2463 2464 BasicBlock *ExitingBlock = 0; 2465 for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock); 2466 PI != E; ++PI) 2467 if (L->contains(*PI)) { 2468 if (ExitingBlock == 0) 2469 ExitingBlock = *PI; 2470 else 2471 return UnknownValue; // More than one block exiting! 2472 } 2473 assert(ExitingBlock && "No exits from loop, something is broken!"); 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 UnknownValue; 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 UnknownValue; 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 UnknownValue; 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 UnknownValue; 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 UnknownValue; 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 UnknownValue; // 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 UnknownValue; 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 UnknownValue; 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 UnknownValue. 2856SCEVHandle ScalarEvolution:: 2857ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) { 2858 PHINode *PN = getConstantEvolvingPHI(Cond, L); 2859 if (PN == 0) return UnknownValue; 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 UnknownValue; // Must be a constant. 2868 2869 Value *BEValue = PN->getIncomingValue(SecondIsBackedge); 2870 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); 2871 if (PN2 != PN) return UnknownValue; // 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 UnknownValue; 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 UnknownValue; // Couldn't evaluate or not making progress... 2896 PHIVal = NextPHI; 2897 } 2898 2899 // Too many iterations were needed to evaluate. 2900 return UnknownValue; 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 == UnknownValue) 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 UnknownValue 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 UnknownValue; // Otherwise it will loop infinitely. 3211 } 3212 3213 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V); 3214 if (!AddRec || AddRec->getLoop() != L) 3215 return UnknownValue; 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 UnknownValue; 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/// UnknownValue 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 UnknownValue; // 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 UnknownValue; 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/// UnknownValue. 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 UnknownValue; 3455 3456 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS); 3457 if (!AddRec || AddRec->getLoop() != L) 3458 return UnknownValue; 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 UnknownValue; 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 UnknownValue; 3481 } else { 3482 APInt Max = APInt::getMaxValue(BitWidth); 3483 if ((Max - CStep->getValue()->getValue()) 3484 .ult(CLimit->getValue()->getValue())) 3485 return UnknownValue; 3486 } 3487 } else 3488 // TODO: handle non-constant limit values below. 3489 return UnknownValue; 3490 } else 3491 // TODO: handle negative strides below. 3492 return UnknownValue; 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 if will execute (max(m,n)-n)/s times. In both cases, the 3510 // 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 UnknownValue; 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), UnknownValue(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