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