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