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