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