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