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