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