ScalarEvolution.cpp revision 16011e6201a11ec16968c27a6f62ebf32537969f
1//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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. These classes are reference counted, managed by the SCEVHandle 18// class. We only create one SCEV of a particular shape, so pointer-comparisons 19// for equality are legal. 20// 21// One important aspect of the SCEV objects is that they are never cyclic, even 22// if there is a cycle in the dataflow for an expression (ie, a PHI node). If 23// the PHI node is one of the idioms that we can represent (e.g., a polynomial 24// recurrence) then we represent it directly as a recurrence node, otherwise we 25// represent it as a SCEVUnknown node. 26// 27// In addition to being able to represent expressions of various types, we also 28// have folders that are used to build the *canonical* representation for a 29// particular expression. These folders are capable of using a variety of 30// rewrite rules to simplify the expressions. 31// 32// Once the folders are defined, we can implement the more interesting 33// higher-level code, such as the code that recognizes PHI nodes of various 34// types, computes the execution count of a loop, etc. 35// 36// Orthogonal to the analysis of code above, this file also implements the 37// ScalarEvolutionRewriter class, which is used to emit code that represents the 38// various recurrences present in a loop, in canonical forms. 39// 40// TODO: We should use these routines and value representations to implement 41// dependence analysis! 42// 43//===----------------------------------------------------------------------===// 44// 45// There are several good references for the techniques used in this analysis. 46// 47// Chains of recurrences -- a method to expedite the evaluation 48// of closed-form functions 49// Olaf Bachmann, Paul S. Wang, Eugene V. Zima 50// 51// On computational properties of chains of recurrences 52// Eugene V. Zima 53// 54// Symbolic Evaluation of Chains of Recurrences for Loop Optimization 55// Robert A. van Engelen 56// 57// Efficient Symbolic Analysis for Optimizing Compilers 58// Robert A. van Engelen 59// 60// Using the chains of recurrences algebra for data dependence testing and 61// induction variable substitution 62// MS Thesis, Johnie Birch 63// 64//===----------------------------------------------------------------------===// 65 66#include "llvm/Analysis/ScalarEvolution.h" 67#include "llvm/Constants.h" 68#include "llvm/DerivedTypes.h" 69#include "llvm/Instructions.h" 70#include "llvm/Type.h" 71#include "llvm/Value.h" 72#include "llvm/Analysis/LoopInfo.h" 73#include "llvm/Assembly/Writer.h" 74#include "llvm/Transforms/Scalar.h" 75#include "llvm/Support/CFG.h" 76#include "llvm/Support/ConstantRange.h" 77#include "llvm/Support/InstIterator.h" 78#include "Support/Statistic.h" 79using namespace llvm; 80 81namespace { 82 RegisterAnalysis<ScalarEvolution> 83 R("scalar-evolution", "Scalar Evolution Analysis Printer"); 84 85 Statistic<> 86 NumBruteForceEvaluations("scalar-evolution", 87 "Number of brute force evaluations needed to calculate high-order polynomial exit values"); 88 Statistic<> 89 NumTripCountsComputed("scalar-evolution", 90 "Number of loops with predictable loop counts"); 91 Statistic<> 92 NumTripCountsNotComputed("scalar-evolution", 93 "Number of loops without predictable loop counts"); 94} 95 96//===----------------------------------------------------------------------===// 97// SCEV class definitions 98//===----------------------------------------------------------------------===// 99 100//===----------------------------------------------------------------------===// 101// Implementation of the SCEV class. 102// 103namespace { 104 enum SCEVTypes { 105 // These should be ordered in terms of increasing complexity to make the 106 // folders simpler. 107 scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scUDivExpr, 108 scAddRecExpr, scUnknown, scCouldNotCompute 109 }; 110 111 /// SCEVComplexityCompare - Return true if the complexity of the LHS is less 112 /// than the complexity of the RHS. If the SCEVs have identical complexity, 113 /// order them by their addresses. This comparator is used to canonicalize 114 /// expressions. 115 struct SCEVComplexityCompare { 116 bool operator()(SCEV *LHS, SCEV *RHS) { 117 if (LHS->getSCEVType() < RHS->getSCEVType()) 118 return true; 119 if (LHS->getSCEVType() == RHS->getSCEVType()) 120 return LHS < RHS; 121 return false; 122 } 123 }; 124} 125 126SCEV::~SCEV() {} 127void SCEV::dump() const { 128 print(std::cerr); 129} 130 131/// getValueRange - Return the tightest constant bounds that this value is 132/// known to have. This method is only valid on integer SCEV objects. 133ConstantRange SCEV::getValueRange() const { 134 const Type *Ty = getType(); 135 assert(Ty->isInteger() && "Can't get range for a non-integer SCEV!"); 136 Ty = Ty->getUnsignedVersion(); 137 // Default to a full range if no better information is available. 138 return ConstantRange(getType()); 139} 140 141 142SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {} 143 144bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const { 145 assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); 146 return false; 147} 148 149const Type *SCEVCouldNotCompute::getType() const { 150 assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); 151 return 0; 152} 153 154bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const { 155 assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); 156 return false; 157} 158 159Value *SCEVCouldNotCompute::expandCodeFor(ScalarEvolutionRewriter &SER, 160 Instruction *InsertPt) { 161 assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); 162 return 0; 163} 164 165 166void SCEVCouldNotCompute::print(std::ostream &OS) const { 167 OS << "***COULDNOTCOMPUTE***"; 168} 169 170bool SCEVCouldNotCompute::classof(const SCEV *S) { 171 return S->getSCEVType() == scCouldNotCompute; 172} 173 174 175//===----------------------------------------------------------------------===// 176// SCEVConstant - This class represents a constant integer value. 177// 178namespace { 179 class SCEVConstant; 180 // SCEVConstants - Only allow the creation of one SCEVConstant for any 181 // particular value. Don't use a SCEVHandle here, or else the object will 182 // never be deleted! 183 std::map<ConstantInt*, SCEVConstant*> SCEVConstants; 184 185 class SCEVConstant : public SCEV { 186 ConstantInt *V; 187 SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {} 188 189 virtual ~SCEVConstant() { 190 SCEVConstants.erase(V); 191 } 192 public: 193 /// get method - This just gets and returns a new SCEVConstant object. 194 /// 195 static SCEVHandle get(ConstantInt *V) { 196 // Make sure that SCEVConstant instances are all unsigned. 197 if (V->getType()->isSigned()) { 198 const Type *NewTy = V->getType()->getUnsignedVersion(); 199 V = cast<ConstantUInt>(ConstantExpr::getCast(V, NewTy)); 200 } 201 202 SCEVConstant *&R = SCEVConstants[V]; 203 if (R == 0) R = new SCEVConstant(V); 204 return R; 205 } 206 207 ConstantInt *getValue() const { return V; } 208 209 /// getValueRange - Return the tightest constant bounds that this value is 210 /// known to have. This method is only valid on integer SCEV objects. 211 virtual ConstantRange getValueRange() const { 212 return ConstantRange(V); 213 } 214 215 virtual bool isLoopInvariant(const Loop *L) const { 216 return true; 217 } 218 219 virtual bool hasComputableLoopEvolution(const Loop *L) const { 220 return false; // Not loop variant 221 } 222 223 virtual const Type *getType() const { return V->getType(); } 224 225 Value *expandCodeFor(ScalarEvolutionRewriter &SER, 226 Instruction *InsertPt) { 227 return getValue(); 228 } 229 230 virtual void print(std::ostream &OS) const { 231 WriteAsOperand(OS, V, false); 232 } 233 234 /// Methods for support type inquiry through isa, cast, and dyn_cast: 235 static inline bool classof(const SCEVConstant *S) { return true; } 236 static inline bool classof(const SCEV *S) { 237 return S->getSCEVType() == scConstant; 238 } 239 }; 240} 241 242 243//===----------------------------------------------------------------------===// 244// SCEVTruncateExpr - This class represents a truncation of an integer value to 245// a smaller integer value. 246// 247namespace { 248 class SCEVTruncateExpr; 249 // SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any 250 // particular input. Don't use a SCEVHandle here, or else the object will 251 // never be deleted! 252 std::map<std::pair<SCEV*, const Type*>, SCEVTruncateExpr*> SCEVTruncates; 253 254 class SCEVTruncateExpr : public SCEV { 255 SCEVHandle Op; 256 const Type *Ty; 257 SCEVTruncateExpr(const SCEVHandle &op, const Type *ty) 258 : SCEV(scTruncate), Op(op), Ty(ty) { 259 assert(Op->getType()->isInteger() && Ty->isInteger() && 260 Ty->isUnsigned() && 261 "Cannot truncate non-integer value!"); 262 assert(Op->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() && 263 "This is not a truncating conversion!"); 264 } 265 266 virtual ~SCEVTruncateExpr() { 267 SCEVTruncates.erase(std::make_pair(Op, Ty)); 268 } 269 public: 270 /// get method - This just gets and returns a new SCEVTruncate object 271 /// 272 static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 273 274 const SCEVHandle &getOperand() const { return Op; } 275 virtual const Type *getType() const { return Ty; } 276 277 virtual bool isLoopInvariant(const Loop *L) const { 278 return Op->isLoopInvariant(L); 279 } 280 281 virtual bool hasComputableLoopEvolution(const Loop *L) const { 282 return Op->hasComputableLoopEvolution(L); 283 } 284 285 /// getValueRange - Return the tightest constant bounds that this value is 286 /// known to have. This method is only valid on integer SCEV objects. 287 virtual ConstantRange getValueRange() const { 288 return getOperand()->getValueRange().truncate(getType()); 289 } 290 291 Value *expandCodeFor(ScalarEvolutionRewriter &SER, 292 Instruction *InsertPt); 293 294 virtual void print(std::ostream &OS) const { 295 OS << "(truncate " << *Op << " to " << *Ty << ")"; 296 } 297 298 /// Methods for support type inquiry through isa, cast, and dyn_cast: 299 static inline bool classof(const SCEVTruncateExpr *S) { return true; } 300 static inline bool classof(const SCEV *S) { 301 return S->getSCEVType() == scTruncate; 302 } 303 }; 304} 305 306 307//===----------------------------------------------------------------------===// 308// SCEVZeroExtendExpr - This class represents a zero extension of a small 309// integer value to a larger integer value. 310// 311namespace { 312 class SCEVZeroExtendExpr; 313 // SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any 314 // particular input. Don't use a SCEVHandle here, or else the object will 315 // never be deleted! 316 std::map<std::pair<SCEV*, const Type*>, SCEVZeroExtendExpr*> SCEVZeroExtends; 317 318 class SCEVZeroExtendExpr : public SCEV { 319 SCEVHandle Op; 320 const Type *Ty; 321 SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty) 322 : SCEV(scTruncate), Op(Op), Ty(ty) { 323 assert(Op->getType()->isInteger() && Ty->isInteger() && 324 Ty->isUnsigned() && 325 "Cannot zero extend non-integer value!"); 326 assert(Op->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() && 327 "This is not an extending conversion!"); 328 } 329 330 virtual ~SCEVZeroExtendExpr() { 331 SCEVZeroExtends.erase(std::make_pair(Op, Ty)); 332 } 333 public: 334 /// get method - This just gets and returns a new SCEVZeroExtend object 335 /// 336 static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 337 338 const SCEVHandle &getOperand() const { return Op; } 339 virtual const Type *getType() const { return Ty; } 340 341 virtual bool isLoopInvariant(const Loop *L) const { 342 return Op->isLoopInvariant(L); 343 } 344 345 virtual bool hasComputableLoopEvolution(const Loop *L) const { 346 return Op->hasComputableLoopEvolution(L); 347 } 348 349 /// getValueRange - Return the tightest constant bounds that this value is 350 /// known to have. This method is only valid on integer SCEV objects. 351 virtual ConstantRange getValueRange() const { 352 return getOperand()->getValueRange().zeroExtend(getType()); 353 } 354 355 Value *expandCodeFor(ScalarEvolutionRewriter &SER, 356 Instruction *InsertPt); 357 358 virtual void print(std::ostream &OS) const { 359 OS << "(zeroextend " << *Op << " to " << *Ty << ")"; 360 } 361 362 /// Methods for support type inquiry through isa, cast, and dyn_cast: 363 static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 364 static inline bool classof(const SCEV *S) { 365 return S->getSCEVType() == scZeroExtend; 366 } 367 }; 368} 369 370 371//===----------------------------------------------------------------------===// 372// SCEVCommutativeExpr - This node is the base class for n'ary commutative 373// operators. 374 375namespace { 376 class SCEVCommutativeExpr; 377 // SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any 378 // particular input. Don't use a SCEVHandle here, or else the object will 379 // never be deleted! 380 std::map<std::pair<unsigned, std::vector<SCEV*> >, 381 SCEVCommutativeExpr*> SCEVCommExprs; 382 383 class SCEVCommutativeExpr : public SCEV { 384 std::vector<SCEVHandle> Operands; 385 386 protected: 387 SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops) 388 : SCEV(T) { 389 Operands.reserve(ops.size()); 390 Operands.insert(Operands.end(), ops.begin(), ops.end()); 391 } 392 393 ~SCEVCommutativeExpr() { 394 SCEVCommExprs.erase(std::make_pair(getSCEVType(), 395 std::vector<SCEV*>(Operands.begin(), 396 Operands.end()))); 397 } 398 399 public: 400 unsigned getNumOperands() const { return Operands.size(); } 401 const SCEVHandle &getOperand(unsigned i) const { 402 assert(i < Operands.size() && "Operand index out of range!"); 403 return Operands[i]; 404 } 405 406 const std::vector<SCEVHandle> &getOperands() const { return Operands; } 407 typedef std::vector<SCEVHandle>::const_iterator op_iterator; 408 op_iterator op_begin() const { return Operands.begin(); } 409 op_iterator op_end() const { return Operands.end(); } 410 411 412 virtual bool isLoopInvariant(const Loop *L) const { 413 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 414 if (!getOperand(i)->isLoopInvariant(L)) return false; 415 return true; 416 } 417 418 virtual bool hasComputableLoopEvolution(const Loop *L) const { 419 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 420 if (getOperand(i)->hasComputableLoopEvolution(L)) return true; 421 return false; 422 } 423 424 virtual const Type *getType() const { return getOperand(0)->getType(); } 425 426 virtual const char *getOperationStr() const = 0; 427 428 virtual void print(std::ostream &OS) const { 429 assert(Operands.size() > 1 && "This plus expr shouldn't exist!"); 430 const char *OpStr = getOperationStr(); 431 OS << "(" << *Operands[0]; 432 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 433 OS << OpStr << *Operands[i]; 434 OS << ")"; 435 } 436 437 /// Methods for support type inquiry through isa, cast, and dyn_cast: 438 static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 439 static inline bool classof(const SCEV *S) { 440 return S->getSCEVType() == scAddExpr || 441 S->getSCEVType() == scMulExpr; 442 } 443 }; 444} 445 446//===----------------------------------------------------------------------===// 447// SCEVAddExpr - This node represents an addition of some number of SCEV's. 448// 449namespace { 450 class SCEVAddExpr : public SCEVCommutativeExpr { 451 SCEVAddExpr(const std::vector<SCEVHandle> &ops) 452 : SCEVCommutativeExpr(scAddExpr, ops) { 453 } 454 455 public: 456 static SCEVHandle get(std::vector<SCEVHandle> &Ops); 457 458 static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 459 std::vector<SCEVHandle> Ops; 460 Ops.push_back(LHS); 461 Ops.push_back(RHS); 462 return get(Ops); 463 } 464 465 static SCEVHandle get(const SCEVHandle &Op0, const SCEVHandle &Op1, 466 const SCEVHandle &Op2) { 467 std::vector<SCEVHandle> Ops; 468 Ops.push_back(Op0); 469 Ops.push_back(Op1); 470 Ops.push_back(Op2); 471 return get(Ops); 472 } 473 474 virtual const char *getOperationStr() const { return " + "; } 475 476 Value *expandCodeFor(ScalarEvolutionRewriter &SER, 477 Instruction *InsertPt); 478 479 /// Methods for support type inquiry through isa, cast, and dyn_cast: 480 static inline bool classof(const SCEVAddExpr *S) { return true; } 481 static inline bool classof(const SCEV *S) { 482 return S->getSCEVType() == scAddExpr; 483 } 484 }; 485} 486 487//===----------------------------------------------------------------------===// 488// SCEVMulExpr - This node represents multiplication of some number of SCEV's. 489// 490namespace { 491 class SCEVMulExpr : public SCEVCommutativeExpr { 492 SCEVMulExpr(const std::vector<SCEVHandle> &ops) 493 : SCEVCommutativeExpr(scMulExpr, ops) { 494 } 495 496 public: 497 static SCEVHandle get(std::vector<SCEVHandle> &Ops); 498 499 static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 500 std::vector<SCEVHandle> Ops; 501 Ops.push_back(LHS); 502 Ops.push_back(RHS); 503 return get(Ops); 504 } 505 506 virtual const char *getOperationStr() const { return " * "; } 507 508 Value *expandCodeFor(ScalarEvolutionRewriter &SER, 509 Instruction *InsertPt); 510 511 /// Methods for support type inquiry through isa, cast, and dyn_cast: 512 static inline bool classof(const SCEVMulExpr *S) { return true; } 513 static inline bool classof(const SCEV *S) { 514 return S->getSCEVType() == scMulExpr; 515 } 516 }; 517} 518 519 520//===----------------------------------------------------------------------===// 521// SCEVUDivExpr - This class represents a binary unsigned division operation. 522// 523namespace { 524 class SCEVUDivExpr; 525 // SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular 526 // input. Don't use a SCEVHandle here, or else the object will never be 527 // deleted! 528 std::map<std::pair<SCEV*, SCEV*>, SCEVUDivExpr*> SCEVUDivs; 529 530 class SCEVUDivExpr : public SCEV { 531 SCEVHandle LHS, RHS; 532 SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs) 533 : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {} 534 535 virtual ~SCEVUDivExpr() { 536 SCEVUDivs.erase(std::make_pair(LHS, RHS)); 537 } 538 public: 539 /// get method - This just gets and returns a new SCEVUDiv object. 540 /// 541 static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS); 542 543 const SCEVHandle &getLHS() const { return LHS; } 544 const SCEVHandle &getRHS() const { return RHS; } 545 546 virtual bool isLoopInvariant(const Loop *L) const { 547 return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 548 } 549 550 virtual bool hasComputableLoopEvolution(const Loop *L) const { 551 return LHS->hasComputableLoopEvolution(L) && 552 RHS->hasComputableLoopEvolution(L); 553 } 554 555 virtual const Type *getType() const { 556 const Type *Ty = LHS->getType(); 557 if (Ty->isSigned()) Ty = Ty->getUnsignedVersion(); 558 return Ty; 559 } 560 561 Value *expandCodeFor(ScalarEvolutionRewriter &SER, 562 Instruction *InsertPt); 563 564 virtual void print(std::ostream &OS) const { 565 OS << "(" << *LHS << " /u " << *RHS << ")"; 566 } 567 568 /// Methods for support type inquiry through isa, cast, and dyn_cast: 569 static inline bool classof(const SCEVUDivExpr *S) { return true; } 570 static inline bool classof(const SCEV *S) { 571 return S->getSCEVType() == scUDivExpr; 572 } 573 }; 574} 575 576 577//===----------------------------------------------------------------------===// 578 579// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 580// count of the specified loop. 581// 582// All operands of an AddRec are required to be loop invariant. 583// 584namespace { 585 class SCEVAddRecExpr; 586 // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any 587 // particular input. Don't use a SCEVHandle here, or else the object will 588 // never be deleted! 589 std::map<std::pair<const Loop *, std::vector<SCEV*> >, 590 SCEVAddRecExpr*> SCEVAddRecExprs; 591 592 class SCEVAddRecExpr : public SCEV { 593 std::vector<SCEVHandle> Operands; 594 const Loop *L; 595 596 SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l) 597 : SCEV(scAddRecExpr), Operands(ops), L(l) { 598 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 599 assert(Operands[i]->isLoopInvariant(l) && 600 "Operands of AddRec must be loop-invariant!"); 601 } 602 ~SCEVAddRecExpr() { 603 SCEVAddRecExprs.erase(std::make_pair(L, 604 std::vector<SCEV*>(Operands.begin(), 605 Operands.end()))); 606 } 607 public: 608 static SCEVHandle get(const SCEVHandle &Start, const SCEVHandle &Step, 609 const Loop *); 610 static SCEVHandle get(std::vector<SCEVHandle> &Operands, 611 const Loop *); 612 static SCEVHandle get(const std::vector<SCEVHandle> &Operands, 613 const Loop *L) { 614 std::vector<SCEVHandle> NewOp(Operands); 615 return get(NewOp, L); 616 } 617 618 typedef std::vector<SCEVHandle>::const_iterator op_iterator; 619 op_iterator op_begin() const { return Operands.begin(); } 620 op_iterator op_end() const { return Operands.end(); } 621 622 unsigned getNumOperands() const { return Operands.size(); } 623 const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; } 624 const SCEVHandle &getStart() const { return Operands[0]; } 625 const Loop *getLoop() const { return L; } 626 627 628 /// getStepRecurrence - This method constructs and returns the recurrence 629 /// indicating how much this expression steps by. If this is a polynomial 630 /// of degree N, it returns a chrec of degree N-1. 631 SCEVHandle getStepRecurrence() const { 632 if (getNumOperands() == 2) return getOperand(1); 633 return SCEVAddRecExpr::get(std::vector<SCEVHandle>(op_begin()+1,op_end()), 634 getLoop()); 635 } 636 637 virtual bool hasComputableLoopEvolution(const Loop *QL) const { 638 if (L == QL) return true; 639 /// FIXME: What if the start or step value a recurrence for the specified 640 /// loop? 641 return false; 642 } 643 644 645 virtual bool isLoopInvariant(const Loop *QueryLoop) const { 646 // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't 647 // contain L. 648 return !QueryLoop->contains(L->getHeader()); 649 } 650 651 virtual const Type *getType() const { return Operands[0]->getType(); } 652 653 Value *expandCodeFor(ScalarEvolutionRewriter &SER, 654 Instruction *InsertPt); 655 656 657 /// isAffine - Return true if this is an affine AddRec (i.e., it represents 658 /// an expressions A+B*x where A and B are loop invariant values. 659 bool isAffine() const { 660 // We know that the start value is invariant. This expression is thus 661 // affine iff the step is also invariant. 662 return getNumOperands() == 2; 663 } 664 665 /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 666 /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 667 /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 668 bool isQuadratic() const { 669 return getNumOperands() == 3; 670 } 671 672 /// evaluateAtIteration - Return the value of this chain of recurrences at 673 /// the specified iteration number. 674 SCEVHandle evaluateAtIteration(SCEVHandle It) const; 675 676 /// getNumIterationsInRange - Return the number of iterations of this loop 677 /// that produce values in the specified constant range. Another way of 678 /// looking at this is that it returns the first iteration number where the 679 /// value is not in the condition, thus computing the exit count. If the 680 /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 681 /// returned. 682 SCEVHandle getNumIterationsInRange(ConstantRange Range) const; 683 684 685 virtual void print(std::ostream &OS) const { 686 OS << "{" << *Operands[0]; 687 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 688 OS << ",+," << *Operands[i]; 689 OS << "}<" << L->getHeader()->getName() + ">"; 690 } 691 692 /// Methods for support type inquiry through isa, cast, and dyn_cast: 693 static inline bool classof(const SCEVAddRecExpr *S) { return true; } 694 static inline bool classof(const SCEV *S) { 695 return S->getSCEVType() == scAddRecExpr; 696 } 697 }; 698} 699 700 701//===----------------------------------------------------------------------===// 702// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 703// value, and only represent it as it's LLVM Value. This is the "bottom" value 704// for the analysis. 705// 706namespace { 707 class SCEVUnknown; 708 // SCEVUnknowns - Only allow the creation of one SCEVUnknown for any 709 // particular value. Don't use a SCEVHandle here, or else the object will 710 // never be deleted! 711 std::map<Value*, SCEVUnknown*> SCEVUnknowns; 712 713 class SCEVUnknown : public SCEV { 714 Value *V; 715 SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {} 716 717 protected: 718 ~SCEVUnknown() { SCEVUnknowns.erase(V); } 719 public: 720 /// get method - For SCEVUnknown, this just gets and returns a new 721 /// SCEVUnknown. 722 static SCEVHandle get(Value *V) { 723 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 724 return SCEVConstant::get(CI); 725 SCEVUnknown *&Result = SCEVUnknowns[V]; 726 if (Result == 0) Result = new SCEVUnknown(V); 727 return Result; 728 } 729 730 Value *getValue() const { return V; } 731 732 Value *expandCodeFor(ScalarEvolutionRewriter &SER, 733 Instruction *InsertPt) { 734 return V; 735 } 736 737 virtual bool isLoopInvariant(const Loop *L) const { 738 // All non-instruction values are loop invariant. All instructions are 739 // loop invariant if they are not contained in the specified loop. 740 if (Instruction *I = dyn_cast<Instruction>(V)) 741 return !L->contains(I->getParent()); 742 return true; 743 } 744 745 virtual bool hasComputableLoopEvolution(const Loop *QL) const { 746 return false; // not computable 747 } 748 749 virtual const Type *getType() const { return V->getType(); } 750 751 virtual void print(std::ostream &OS) const { 752 WriteAsOperand(OS, V, false); 753 } 754 755 /// Methods for support type inquiry through isa, cast, and dyn_cast: 756 static inline bool classof(const SCEVUnknown *S) { return true; } 757 static inline bool classof(const SCEV *S) { 758 return S->getSCEVType() == scUnknown; 759 } 760 }; 761} 762 763//===----------------------------------------------------------------------===// 764// Simple SCEV method implementations 765//===----------------------------------------------------------------------===// 766 767/// getIntegerSCEV - Given an integer or FP type, create a constant for the 768/// specified signed integer value and return a SCEV for the constant. 769static SCEVHandle getIntegerSCEV(int Val, const Type *Ty) { 770 Constant *C; 771 if (Val == 0) 772 C = Constant::getNullValue(Ty); 773 else if (Ty->isFloatingPoint()) 774 C = ConstantFP::get(Ty, Val); 775 else if (Ty->isSigned()) 776 C = ConstantSInt::get(Ty, Val); 777 else { 778 C = ConstantSInt::get(Ty->getSignedVersion(), Val); 779 C = ConstantExpr::getCast(C, Ty); 780 } 781 return SCEVUnknown::get(C); 782} 783 784/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the 785/// input value to the specified type. If the type must be extended, it is zero 786/// extended. 787static SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty) { 788 const Type *SrcTy = V->getType(); 789 assert(SrcTy->isInteger() && Ty->isInteger() && 790 "Cannot truncate or zero extend with non-integer arguments!"); 791 if (SrcTy->getPrimitiveSize() == Ty->getPrimitiveSize()) 792 return V; // No conversion 793 if (SrcTy->getPrimitiveSize() > Ty->getPrimitiveSize()) 794 return SCEVTruncateExpr::get(V, Ty); 795 return SCEVZeroExtendExpr::get(V, Ty); 796} 797 798/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V 799/// 800static SCEVHandle getNegativeSCEV(const SCEVHandle &V) { 801 if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) 802 return SCEVUnknown::get(ConstantExpr::getNeg(VC->getValue())); 803 804 return SCEVMulExpr::get(V, getIntegerSCEV(-1, V->getType())); 805} 806 807/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS. 808/// 809static SCEVHandle getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS) { 810 // X - Y --> X + -Y 811 return SCEVAddExpr::get(LHS, getNegativeSCEV(RHS)); 812} 813 814 815/// Binomial - Evaluate N!/((N-M)!*M!) . Note that N is often large and M is 816/// often very small, so we try to reduce the number of N! terms we need to 817/// evaluate by evaluating this as (N!/(N-M)!)/M! 818static ConstantInt *Binomial(ConstantInt *N, unsigned M) { 819 uint64_t NVal = N->getRawValue(); 820 uint64_t FirstTerm = 1; 821 for (unsigned i = 0; i != M; ++i) 822 FirstTerm *= NVal-i; 823 824 unsigned MFactorial = 1; 825 for (; M; --M) 826 MFactorial *= M; 827 828 Constant *Result = ConstantUInt::get(Type::ULongTy, FirstTerm/MFactorial); 829 Result = ConstantExpr::getCast(Result, N->getType()); 830 assert(isa<ConstantInt>(Result) && "Cast of integer not folded??"); 831 return cast<ConstantInt>(Result); 832} 833 834/// PartialFact - Compute V!/(V-NumSteps)! 835static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) { 836 // Handle this case efficiently, it is common to have constant iteration 837 // counts while computing loop exit values. 838 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) { 839 uint64_t Val = SC->getValue()->getRawValue(); 840 uint64_t Result = 1; 841 for (; NumSteps; --NumSteps) 842 Result *= Val-(NumSteps-1); 843 Constant *Res = ConstantUInt::get(Type::ULongTy, Result); 844 return SCEVUnknown::get(ConstantExpr::getCast(Res, V->getType())); 845 } 846 847 const Type *Ty = V->getType(); 848 if (NumSteps == 0) 849 return getIntegerSCEV(1, Ty); 850 851 SCEVHandle Result = V; 852 for (unsigned i = 1; i != NumSteps; ++i) 853 Result = SCEVMulExpr::get(Result, getMinusSCEV(V, getIntegerSCEV(i, Ty))); 854 return Result; 855} 856 857 858/// evaluateAtIteration - Return the value of this chain of recurrences at 859/// the specified iteration number. We can evaluate this recurrence by 860/// multiplying each element in the chain by the binomial coefficient 861/// corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as: 862/// 863/// A*choose(It, 0) + B*choose(It, 1) + C*choose(It, 2) + D*choose(It, 3) 864/// 865/// FIXME/VERIFY: I don't trust that this is correct in the face of overflow. 866/// Is the binomial equation safe using modular arithmetic?? 867/// 868SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const { 869 SCEVHandle Result = getStart(); 870 int Divisor = 1; 871 const Type *Ty = It->getType(); 872 for (unsigned i = 1, e = getNumOperands(); i != e; ++i) { 873 SCEVHandle BC = PartialFact(It, i); 874 Divisor *= i; 875 SCEVHandle Val = SCEVUDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)), 876 getIntegerSCEV(Divisor, Ty)); 877 Result = SCEVAddExpr::get(Result, Val); 878 } 879 return Result; 880} 881 882 883//===----------------------------------------------------------------------===// 884// SCEV Expression folder implementations 885//===----------------------------------------------------------------------===// 886 887SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) { 888 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) 889 return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty)); 890 891 // If the input value is a chrec scev made out of constants, truncate 892 // all of the constants. 893 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) { 894 std::vector<SCEVHandle> Operands; 895 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) 896 // FIXME: This should allow truncation of other expression types! 897 if (isa<SCEVConstant>(AddRec->getOperand(i))) 898 Operands.push_back(get(AddRec->getOperand(i), Ty)); 899 else 900 break; 901 if (Operands.size() == AddRec->getNumOperands()) 902 return SCEVAddRecExpr::get(Operands, AddRec->getLoop()); 903 } 904 905 SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)]; 906 if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty); 907 return Result; 908} 909 910SCEVHandle SCEVZeroExtendExpr::get(const SCEVHandle &Op, const Type *Ty) { 911 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) 912 return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty)); 913 914 // FIXME: If the input value is a chrec scev, and we can prove that the value 915 // did not overflow the old, smaller, value, we can zero extend all of the 916 // operands (often constants). This would allow analysis of something like 917 // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; } 918 919 SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)]; 920 if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty); 921 return Result; 922} 923 924// get - Get a canonical add expression, or something simpler if possible. 925SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) { 926 assert(!Ops.empty() && "Cannot get empty add!"); 927 if (Ops.size() == 1) return Ops[0]; 928 929 // Sort by complexity, this groups all similar expression types together. 930 std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare()); 931 932 // If there are any constants, fold them together. 933 unsigned Idx = 0; 934 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 935 ++Idx; 936 assert(Idx < Ops.size()); 937 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 938 // We found two constants, fold them together! 939 Constant *Fold = ConstantExpr::getAdd(LHSC->getValue(), RHSC->getValue()); 940 if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) { 941 Ops[0] = SCEVConstant::get(CI); 942 Ops.erase(Ops.begin()+1); // Erase the folded element 943 if (Ops.size() == 1) return Ops[0]; 944 } else { 945 // If we couldn't fold the expression, move to the next constant. Note 946 // that this is impossible to happen in practice because we always 947 // constant fold constant ints to constant ints. 948 ++Idx; 949 } 950 } 951 952 // If we are left with a constant zero being added, strip it off. 953 if (cast<SCEVConstant>(Ops[0])->getValue()->isNullValue()) { 954 Ops.erase(Ops.begin()); 955 --Idx; 956 } 957 } 958 959 if (Ops.size() == 1) return Ops[0]; 960 961 // Okay, check to see if the same value occurs in the operand list twice. If 962 // so, merge them together into an multiply expression. Since we sorted the 963 // list, these values are required to be adjacent. 964 const Type *Ty = Ops[0]->getType(); 965 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 966 if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2 967 // Found a match, merge the two values into a multiply, and add any 968 // remaining values to the result. 969 SCEVHandle Two = getIntegerSCEV(2, Ty); 970 SCEVHandle Mul = SCEVMulExpr::get(Ops[i], Two); 971 if (Ops.size() == 2) 972 return Mul; 973 Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 974 Ops.push_back(Mul); 975 return SCEVAddExpr::get(Ops); 976 } 977 978 // Okay, now we know the first non-constant operand. If there are add 979 // operands they would be next. 980 if (Idx < Ops.size()) { 981 bool DeletedAdd = false; 982 while (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) { 983 // If we have an add, expand the add operands onto the end of the operands 984 // list. 985 Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); 986 Ops.erase(Ops.begin()+Idx); 987 DeletedAdd = true; 988 } 989 990 // If we deleted at least one add, we added operands to the end of the list, 991 // and they are not necessarily sorted. Recurse to resort and resimplify 992 // any operands we just aquired. 993 if (DeletedAdd) 994 return get(Ops); 995 } 996 997 // Skip over the add expression until we get to a multiply. 998 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) 999 ++Idx; 1000 1001 // If we are adding something to a multiply expression, make sure the 1002 // something is not already an operand of the multiply. If so, merge it into 1003 // the multiply. 1004 for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) { 1005 SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]); 1006 for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) { 1007 SCEV *MulOpSCEV = Mul->getOperand(MulOp); 1008 for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp) 1009 if (MulOpSCEV == Ops[AddOp] && 1010 (Mul->getNumOperands() != 2 || !isa<SCEVConstant>(MulOpSCEV))) { 1011 // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1)) 1012 SCEVHandle InnerMul = Mul->getOperand(MulOp == 0); 1013 if (Mul->getNumOperands() != 2) { 1014 // If the multiply has more than two operands, we must get the 1015 // Y*Z term. 1016 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end()); 1017 MulOps.erase(MulOps.begin()+MulOp); 1018 InnerMul = SCEVMulExpr::get(MulOps); 1019 } 1020 SCEVHandle One = getIntegerSCEV(1, Ty); 1021 SCEVHandle AddOne = SCEVAddExpr::get(InnerMul, One); 1022 SCEVHandle OuterMul = SCEVMulExpr::get(AddOne, Ops[AddOp]); 1023 if (Ops.size() == 2) return OuterMul; 1024 if (AddOp < Idx) { 1025 Ops.erase(Ops.begin()+AddOp); 1026 Ops.erase(Ops.begin()+Idx-1); 1027 } else { 1028 Ops.erase(Ops.begin()+Idx); 1029 Ops.erase(Ops.begin()+AddOp-1); 1030 } 1031 Ops.push_back(OuterMul); 1032 return SCEVAddExpr::get(Ops); 1033 } 1034 1035 // Check this multiply against other multiplies being added together. 1036 for (unsigned OtherMulIdx = Idx+1; 1037 OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]); 1038 ++OtherMulIdx) { 1039 SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]); 1040 // If MulOp occurs in OtherMul, we can fold the two multiplies 1041 // together. 1042 for (unsigned OMulOp = 0, e = OtherMul->getNumOperands(); 1043 OMulOp != e; ++OMulOp) 1044 if (OtherMul->getOperand(OMulOp) == MulOpSCEV) { 1045 // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E)) 1046 SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0); 1047 if (Mul->getNumOperands() != 2) { 1048 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end()); 1049 MulOps.erase(MulOps.begin()+MulOp); 1050 InnerMul1 = SCEVMulExpr::get(MulOps); 1051 } 1052 SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0); 1053 if (OtherMul->getNumOperands() != 2) { 1054 std::vector<SCEVHandle> MulOps(OtherMul->op_begin(), 1055 OtherMul->op_end()); 1056 MulOps.erase(MulOps.begin()+OMulOp); 1057 InnerMul2 = SCEVMulExpr::get(MulOps); 1058 } 1059 SCEVHandle InnerMulSum = SCEVAddExpr::get(InnerMul1,InnerMul2); 1060 SCEVHandle OuterMul = SCEVMulExpr::get(MulOpSCEV, InnerMulSum); 1061 if (Ops.size() == 2) return OuterMul; 1062 Ops.erase(Ops.begin()+Idx); 1063 Ops.erase(Ops.begin()+OtherMulIdx-1); 1064 Ops.push_back(OuterMul); 1065 return SCEVAddExpr::get(Ops); 1066 } 1067 } 1068 } 1069 } 1070 1071 // If there are any add recurrences in the operands list, see if any other 1072 // added values are loop invariant. If so, we can fold them into the 1073 // recurrence. 1074 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) 1075 ++Idx; 1076 1077 // Scan over all recurrences, trying to fold loop invariants into them. 1078 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) { 1079 // Scan all of the other operands to this add and add them to the vector if 1080 // they are loop invariant w.r.t. the recurrence. 1081 std::vector<SCEVHandle> LIOps; 1082 SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]); 1083 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 1084 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { 1085 LIOps.push_back(Ops[i]); 1086 Ops.erase(Ops.begin()+i); 1087 --i; --e; 1088 } 1089 1090 // If we found some loop invariants, fold them into the recurrence. 1091 if (!LIOps.empty()) { 1092 // NLI + LI + { Start,+,Step} --> NLI + { LI+Start,+,Step } 1093 LIOps.push_back(AddRec->getStart()); 1094 1095 std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end()); 1096 AddRecOps[0] = SCEVAddExpr::get(LIOps); 1097 1098 SCEVHandle NewRec = SCEVAddRecExpr::get(AddRecOps, AddRec->getLoop()); 1099 // If all of the other operands were loop invariant, we are done. 1100 if (Ops.size() == 1) return NewRec; 1101 1102 // Otherwise, add the folded AddRec by the non-liv parts. 1103 for (unsigned i = 0;; ++i) 1104 if (Ops[i] == AddRec) { 1105 Ops[i] = NewRec; 1106 break; 1107 } 1108 return SCEVAddExpr::get(Ops); 1109 } 1110 1111 // Okay, if there weren't any loop invariants to be folded, check to see if 1112 // there are multiple AddRec's with the same loop induction variable being 1113 // added together. If so, we can fold them. 1114 for (unsigned OtherIdx = Idx+1; 1115 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx) 1116 if (OtherIdx != Idx) { 1117 SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]); 1118 if (AddRec->getLoop() == OtherAddRec->getLoop()) { 1119 // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D} 1120 std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end()); 1121 for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) { 1122 if (i >= NewOps.size()) { 1123 NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i, 1124 OtherAddRec->op_end()); 1125 break; 1126 } 1127 NewOps[i] = SCEVAddExpr::get(NewOps[i], OtherAddRec->getOperand(i)); 1128 } 1129 SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, AddRec->getLoop()); 1130 1131 if (Ops.size() == 2) return NewAddRec; 1132 1133 Ops.erase(Ops.begin()+Idx); 1134 Ops.erase(Ops.begin()+OtherIdx-1); 1135 Ops.push_back(NewAddRec); 1136 return SCEVAddExpr::get(Ops); 1137 } 1138 } 1139 1140 // Otherwise couldn't fold anything into this recurrence. Move onto the 1141 // next one. 1142 } 1143 1144 // Okay, it looks like we really DO need an add expr. Check to see if we 1145 // already have one, otherwise create a new one. 1146 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end()); 1147 SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scAddExpr, 1148 SCEVOps)]; 1149 if (Result == 0) Result = new SCEVAddExpr(Ops); 1150 return Result; 1151} 1152 1153 1154SCEVHandle SCEVMulExpr::get(std::vector<SCEVHandle> &Ops) { 1155 assert(!Ops.empty() && "Cannot get empty mul!"); 1156 1157 // Sort by complexity, this groups all similar expression types together. 1158 std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare()); 1159 1160 // If there are any constants, fold them together. 1161 unsigned Idx = 0; 1162 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 1163 1164 // C1*(C2+V) -> C1*C2 + C1*V 1165 if (Ops.size() == 2) 1166 if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) 1167 if (Add->getNumOperands() == 2 && 1168 isa<SCEVConstant>(Add->getOperand(0))) 1169 return SCEVAddExpr::get(SCEVMulExpr::get(LHSC, Add->getOperand(0)), 1170 SCEVMulExpr::get(LHSC, Add->getOperand(1))); 1171 1172 1173 ++Idx; 1174 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 1175 // We found two constants, fold them together! 1176 Constant *Fold = ConstantExpr::getMul(LHSC->getValue(), RHSC->getValue()); 1177 if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) { 1178 Ops[0] = SCEVConstant::get(CI); 1179 Ops.erase(Ops.begin()+1); // Erase the folded element 1180 if (Ops.size() == 1) return Ops[0]; 1181 } else { 1182 // If we couldn't fold the expression, move to the next constant. Note 1183 // that this is impossible to happen in practice because we always 1184 // constant fold constant ints to constant ints. 1185 ++Idx; 1186 } 1187 } 1188 1189 // If we are left with a constant one being multiplied, strip it off. 1190 if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) { 1191 Ops.erase(Ops.begin()); 1192 --Idx; 1193 } else if (cast<SCEVConstant>(Ops[0])->getValue()->isNullValue()) { 1194 // If we have a multiply of zero, it will always be zero. 1195 return Ops[0]; 1196 } 1197 } 1198 1199 // Skip over the add expression until we get to a multiply. 1200 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) 1201 ++Idx; 1202 1203 if (Ops.size() == 1) 1204 return Ops[0]; 1205 1206 // If there are mul operands inline them all into this expression. 1207 if (Idx < Ops.size()) { 1208 bool DeletedMul = false; 1209 while (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) { 1210 // If we have an mul, expand the mul operands onto the end of the operands 1211 // list. 1212 Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end()); 1213 Ops.erase(Ops.begin()+Idx); 1214 DeletedMul = true; 1215 } 1216 1217 // If we deleted at least one mul, we added operands to the end of the list, 1218 // and they are not necessarily sorted. Recurse to resort and resimplify 1219 // any operands we just aquired. 1220 if (DeletedMul) 1221 return get(Ops); 1222 } 1223 1224 // If there are any add recurrences in the operands list, see if any other 1225 // added values are loop invariant. If so, we can fold them into the 1226 // recurrence. 1227 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) 1228 ++Idx; 1229 1230 // Scan over all recurrences, trying to fold loop invariants into them. 1231 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) { 1232 // Scan all of the other operands to this mul and add them to the vector if 1233 // they are loop invariant w.r.t. the recurrence. 1234 std::vector<SCEVHandle> LIOps; 1235 SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]); 1236 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 1237 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { 1238 LIOps.push_back(Ops[i]); 1239 Ops.erase(Ops.begin()+i); 1240 --i; --e; 1241 } 1242 1243 // If we found some loop invariants, fold them into the recurrence. 1244 if (!LIOps.empty()) { 1245 // NLI * LI * { Start,+,Step} --> NLI * { LI*Start,+,LI*Step } 1246 std::vector<SCEVHandle> NewOps; 1247 NewOps.reserve(AddRec->getNumOperands()); 1248 if (LIOps.size() == 1) { 1249 SCEV *Scale = LIOps[0]; 1250 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) 1251 NewOps.push_back(SCEVMulExpr::get(Scale, AddRec->getOperand(i))); 1252 } else { 1253 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { 1254 std::vector<SCEVHandle> MulOps(LIOps); 1255 MulOps.push_back(AddRec->getOperand(i)); 1256 NewOps.push_back(SCEVMulExpr::get(MulOps)); 1257 } 1258 } 1259 1260 SCEVHandle NewRec = SCEVAddRecExpr::get(NewOps, AddRec->getLoop()); 1261 1262 // If all of the other operands were loop invariant, we are done. 1263 if (Ops.size() == 1) return NewRec; 1264 1265 // Otherwise, multiply the folded AddRec by the non-liv parts. 1266 for (unsigned i = 0;; ++i) 1267 if (Ops[i] == AddRec) { 1268 Ops[i] = NewRec; 1269 break; 1270 } 1271 return SCEVMulExpr::get(Ops); 1272 } 1273 1274 // Okay, if there weren't any loop invariants to be folded, check to see if 1275 // there are multiple AddRec's with the same loop induction variable being 1276 // multiplied together. If so, we can fold them. 1277 for (unsigned OtherIdx = Idx+1; 1278 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx) 1279 if (OtherIdx != Idx) { 1280 SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]); 1281 if (AddRec->getLoop() == OtherAddRec->getLoop()) { 1282 // F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D} 1283 SCEVAddRecExpr *F = AddRec, *G = OtherAddRec; 1284 SCEVHandle NewStart = SCEVMulExpr::get(F->getStart(), 1285 G->getStart()); 1286 SCEVHandle B = F->getStepRecurrence(); 1287 SCEVHandle D = G->getStepRecurrence(); 1288 SCEVHandle NewStep = SCEVAddExpr::get(SCEVMulExpr::get(F, D), 1289 SCEVMulExpr::get(G, B), 1290 SCEVMulExpr::get(B, D)); 1291 SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewStart, NewStep, 1292 F->getLoop()); 1293 if (Ops.size() == 2) return NewAddRec; 1294 1295 Ops.erase(Ops.begin()+Idx); 1296 Ops.erase(Ops.begin()+OtherIdx-1); 1297 Ops.push_back(NewAddRec); 1298 return SCEVMulExpr::get(Ops); 1299 } 1300 } 1301 1302 // Otherwise couldn't fold anything into this recurrence. Move onto the 1303 // next one. 1304 } 1305 1306 // Okay, it looks like we really DO need an mul expr. Check to see if we 1307 // already have one, otherwise create a new one. 1308 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end()); 1309 SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scMulExpr, 1310 SCEVOps)]; 1311 if (Result == 0) Result = new SCEVMulExpr(Ops); 1312 return Result; 1313} 1314 1315SCEVHandle SCEVUDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 1316 if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) { 1317 if (RHSC->getValue()->equalsInt(1)) 1318 return LHS; // X /u 1 --> x 1319 if (RHSC->getValue()->isAllOnesValue()) 1320 return getNegativeSCEV(LHS); // X /u -1 --> -x 1321 1322 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) { 1323 Constant *LHSCV = LHSC->getValue(); 1324 Constant *RHSCV = RHSC->getValue(); 1325 if (LHSCV->getType()->isSigned()) 1326 LHSCV = ConstantExpr::getCast(LHSCV, 1327 LHSCV->getType()->getUnsignedVersion()); 1328 if (RHSCV->getType()->isSigned()) 1329 RHSCV = ConstantExpr::getCast(RHSCV, LHSCV->getType()); 1330 return SCEVUnknown::get(ConstantExpr::getDiv(LHSCV, RHSCV)); 1331 } 1332 } 1333 1334 // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow. 1335 1336 SCEVUDivExpr *&Result = SCEVUDivs[std::make_pair(LHS, RHS)]; 1337 if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS); 1338 return Result; 1339} 1340 1341 1342/// SCEVAddRecExpr::get - Get a add recurrence expression for the 1343/// specified loop. Simplify the expression as much as possible. 1344SCEVHandle SCEVAddRecExpr::get(const SCEVHandle &Start, 1345 const SCEVHandle &Step, const Loop *L) { 1346 std::vector<SCEVHandle> Operands; 1347 Operands.push_back(Start); 1348 if (SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step)) 1349 if (StepChrec->getLoop() == L) { 1350 Operands.insert(Operands.end(), StepChrec->op_begin(), 1351 StepChrec->op_end()); 1352 return get(Operands, L); 1353 } 1354 1355 Operands.push_back(Step); 1356 return get(Operands, L); 1357} 1358 1359/// SCEVAddRecExpr::get - Get a add recurrence expression for the 1360/// specified loop. Simplify the expression as much as possible. 1361SCEVHandle SCEVAddRecExpr::get(std::vector<SCEVHandle> &Operands, 1362 const Loop *L) { 1363 if (Operands.size() == 1) return Operands[0]; 1364 1365 if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Operands.back())) 1366 if (StepC->getValue()->isNullValue()) { 1367 Operands.pop_back(); 1368 return get(Operands, L); // { X,+,0 } --> X 1369 } 1370 1371 SCEVAddRecExpr *&Result = 1372 SCEVAddRecExprs[std::make_pair(L, std::vector<SCEV*>(Operands.begin(), 1373 Operands.end()))]; 1374 if (Result == 0) Result = new SCEVAddRecExpr(Operands, L); 1375 return Result; 1376} 1377 1378 1379//===----------------------------------------------------------------------===// 1380// Non-trivial closed-form SCEV Expanders 1381//===----------------------------------------------------------------------===// 1382 1383Value *SCEVTruncateExpr::expandCodeFor(ScalarEvolutionRewriter &SER, 1384 Instruction *InsertPt) { 1385 Value *V = SER.ExpandCodeFor(getOperand(), InsertPt); 1386 return new CastInst(V, getType(), "tmp.", InsertPt); 1387} 1388 1389Value *SCEVZeroExtendExpr::expandCodeFor(ScalarEvolutionRewriter &SER, 1390 Instruction *InsertPt) { 1391 Value *V = SER.ExpandCodeFor(getOperand(), InsertPt, 1392 getOperand()->getType()->getUnsignedVersion()); 1393 return new CastInst(V, getType(), "tmp.", InsertPt); 1394} 1395 1396Value *SCEVAddExpr::expandCodeFor(ScalarEvolutionRewriter &SER, 1397 Instruction *InsertPt) { 1398 const Type *Ty = getType(); 1399 Value *V = SER.ExpandCodeFor(getOperand(getNumOperands()-1), InsertPt, Ty); 1400 1401 // Emit a bunch of add instructions 1402 for (int i = getNumOperands()-2; i >= 0; --i) 1403 V = BinaryOperator::create(Instruction::Add, V, 1404 SER.ExpandCodeFor(getOperand(i), InsertPt, Ty), 1405 "tmp.", InsertPt); 1406 return V; 1407} 1408 1409Value *SCEVMulExpr::expandCodeFor(ScalarEvolutionRewriter &SER, 1410 Instruction *InsertPt) { 1411 const Type *Ty = getType(); 1412 int FirstOp = 0; // Set if we should emit a subtract. 1413 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getOperand(0))) 1414 if (SC->getValue()->isAllOnesValue()) 1415 FirstOp = 1; 1416 1417 int i = getNumOperands()-2; 1418 Value *V = SER.ExpandCodeFor(getOperand(i+1), InsertPt, Ty); 1419 1420 // Emit a bunch of multiply instructions 1421 for (; i >= FirstOp; --i) 1422 V = BinaryOperator::create(Instruction::Mul, V, 1423 SER.ExpandCodeFor(getOperand(i), InsertPt, Ty), 1424 "tmp.", InsertPt); 1425 // -1 * ... ---> 0 - ... 1426 if (FirstOp == 1) 1427 V = BinaryOperator::create(Instruction::Sub, Constant::getNullValue(Ty), V, 1428 "tmp.", InsertPt); 1429 return V; 1430} 1431 1432Value *SCEVUDivExpr::expandCodeFor(ScalarEvolutionRewriter &SER, 1433 Instruction *InsertPt) { 1434 const Type *Ty = getType(); 1435 Value *LHS = SER.ExpandCodeFor(getLHS(), InsertPt, Ty); 1436 Value *RHS = SER.ExpandCodeFor(getRHS(), InsertPt, Ty); 1437 return BinaryOperator::create(Instruction::Div, LHS, RHS, "tmp.", InsertPt); 1438} 1439 1440Value *SCEVAddRecExpr::expandCodeFor(ScalarEvolutionRewriter &SER, 1441 Instruction *InsertPt) { 1442 const Type *Ty = getType(); 1443 // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F} 1444 assert(Ty->isIntegral() && "Cannot expand fp recurrences yet!"); 1445 1446 // {X,+,F} --> X + {0,+,F} 1447 if (!isa<SCEVConstant>(getStart()) || 1448 !cast<SCEVConstant>(getStart())->getValue()->isNullValue()) { 1449 Value *Start = SER.ExpandCodeFor(getStart(), InsertPt, Ty); 1450 std::vector<SCEVHandle> NewOps(op_begin(), op_end()); 1451 NewOps[0] = getIntegerSCEV(0, getType()); 1452 Value *Rest = SER.ExpandCodeFor(SCEVAddRecExpr::get(NewOps, getLoop()), 1453 InsertPt, getType()); 1454 1455 // FIXME: look for an existing add to use. 1456 return BinaryOperator::create(Instruction::Add, Rest, Start, "tmp.", 1457 InsertPt); 1458 } 1459 1460 // {0,+,1} --> Insert a canonical induction variable into the loop! 1461 if (getNumOperands() == 2 && getOperand(1) == getIntegerSCEV(1, getType())) { 1462 // Create and insert the PHI node for the induction variable in the 1463 // specified loop. 1464 BasicBlock *Header = getLoop()->getHeader(); 1465 PHINode *PN = new PHINode(Ty, "indvar", Header->begin()); 1466 PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); 1467 1468 pred_iterator HPI = pred_begin(Header); 1469 assert(HPI != pred_end(Header) && "Loop with zero preds???"); 1470 if (!getLoop()->contains(*HPI)) ++HPI; 1471 assert(HPI != pred_end(Header) && getLoop()->contains(*HPI) && 1472 "No backedge in loop?"); 1473 1474 // Insert a unit add instruction right before the terminator corresponding 1475 // to the back-edge. 1476 Constant *One = Ty->isFloatingPoint() ? (Constant*)ConstantFP::get(Ty, 1.0) 1477 : (Constant*)ConstantInt::get(Ty, 1); 1478 Instruction *Add = BinaryOperator::create(Instruction::Add, PN, One, 1479 "indvar.next", 1480 (*HPI)->getTerminator()); 1481 1482 pred_iterator PI = pred_begin(Header); 1483 if (*PI == L->getLoopPreheader()) 1484 ++PI; 1485 PN->addIncoming(Add, *PI); 1486 return PN; 1487 } 1488 1489 // Get the canonical induction variable I for this loop. 1490 Value *I = SER.GetOrInsertCanonicalInductionVariable(getLoop(), Ty); 1491 1492 if (getNumOperands() == 2) { // {0,+,F} --> i*F 1493 Value *F = SER.ExpandCodeFor(getOperand(1), InsertPt, Ty); 1494 return BinaryOperator::create(Instruction::Mul, I, F, "tmp.", InsertPt); 1495 } 1496 1497 // If this is a chain of recurrences, turn it into a closed form, using the 1498 // folders, then expandCodeFor the closed form. This allows the folders to 1499 // simplify the expression without having to build a bunch of special code 1500 // into this folder. 1501 SCEVHandle IH = SCEVUnknown::get(I); // Get I as a "symbolic" SCEV. 1502 1503 SCEVHandle V = evaluateAtIteration(IH); 1504 //std::cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 1505 1506 return SER.ExpandCodeFor(V, InsertPt, Ty); 1507} 1508 1509 1510//===----------------------------------------------------------------------===// 1511// ScalarEvolutionsImpl Definition and Implementation 1512//===----------------------------------------------------------------------===// 1513// 1514/// ScalarEvolutionsImpl - This class implements the main driver for the scalar 1515/// evolution code. 1516/// 1517namespace { 1518 struct ScalarEvolutionsImpl { 1519 /// F - The function we are analyzing. 1520 /// 1521 Function &F; 1522 1523 /// LI - The loop information for the function we are currently analyzing. 1524 /// 1525 LoopInfo &LI; 1526 1527 /// UnknownValue - This SCEV is used to represent unknown trip counts and 1528 /// things. 1529 SCEVHandle UnknownValue; 1530 1531 /// Scalars - This is a cache of the scalars we have analyzed so far. 1532 /// 1533 std::map<Value*, SCEVHandle> Scalars; 1534 1535 /// IterationCounts - Cache the iteration count of the loops for this 1536 /// function as they are computed. 1537 std::map<const Loop*, SCEVHandle> IterationCounts; 1538 1539 public: 1540 ScalarEvolutionsImpl(Function &f, LoopInfo &li) 1541 : F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {} 1542 1543 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the 1544 /// expression and create a new one. 1545 SCEVHandle getSCEV(Value *V); 1546 1547 /// getSCEVAtScope - Compute the value of the specified expression within 1548 /// the indicated loop (which may be null to indicate in no loop). If the 1549 /// expression cannot be evaluated, return UnknownValue itself. 1550 SCEVHandle getSCEVAtScope(SCEV *V, const Loop *L); 1551 1552 1553 /// hasLoopInvariantIterationCount - Return true if the specified loop has 1554 /// an analyzable loop-invariant iteration count. 1555 bool hasLoopInvariantIterationCount(const Loop *L); 1556 1557 /// getIterationCount - If the specified loop has a predictable iteration 1558 /// count, return it. Note that it is not valid to call this method on a 1559 /// loop without a loop-invariant iteration count. 1560 SCEVHandle getIterationCount(const Loop *L); 1561 1562 /// deleteInstructionFromRecords - This method should be called by the 1563 /// client before it removes an instruction from the program, to make sure 1564 /// that no dangling references are left around. 1565 void deleteInstructionFromRecords(Instruction *I); 1566 1567 private: 1568 /// createSCEV - We know that there is no SCEV for the specified value. 1569 /// Analyze the expression. 1570 SCEVHandle createSCEV(Value *V); 1571 SCEVHandle createNodeForCast(CastInst *CI); 1572 1573 /// createNodeForPHI - Provide the special handling we need to analyze PHI 1574 /// SCEVs. 1575 SCEVHandle createNodeForPHI(PHINode *PN); 1576 void UpdatePHIUserScalarEntries(Instruction *I, PHINode *PN, 1577 std::set<Instruction*> &UpdatedInsts); 1578 1579 /// ComputeIterationCount - Compute the number of times the specified loop 1580 /// will iterate. 1581 SCEVHandle ComputeIterationCount(const Loop *L); 1582 1583 /// HowFarToZero - Return the number of times a backedge comparing the 1584 /// specified value to zero will execute. If not computable, return 1585 /// UnknownValue 1586 SCEVHandle HowFarToZero(SCEV *V, const Loop *L); 1587 1588 /// HowFarToNonZero - Return the number of times a backedge checking the 1589 /// specified value for nonzero will execute. If not computable, return 1590 /// UnknownValue 1591 SCEVHandle HowFarToNonZero(SCEV *V, const Loop *L); 1592 }; 1593} 1594 1595//===----------------------------------------------------------------------===// 1596// Basic SCEV Analysis and PHI Idiom Recognition Code 1597// 1598 1599/// deleteInstructionFromRecords - This method should be called by the 1600/// client before it removes an instruction from the program, to make sure 1601/// that no dangling references are left around. 1602void ScalarEvolutionsImpl::deleteInstructionFromRecords(Instruction *I) { 1603 Scalars.erase(I); 1604} 1605 1606 1607/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the 1608/// expression and create a new one. 1609SCEVHandle ScalarEvolutionsImpl::getSCEV(Value *V) { 1610 assert(V->getType() != Type::VoidTy && "Can't analyze void expressions!"); 1611 1612 std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V); 1613 if (I != Scalars.end()) return I->second; 1614 SCEVHandle S = createSCEV(V); 1615 Scalars.insert(std::make_pair(V, S)); 1616 return S; 1617} 1618 1619 1620/// UpdatePHIUserScalarEntries - After PHI node analysis, we have a bunch of 1621/// entries in the scalar map that refer to the "symbolic" PHI value instead of 1622/// the recurrence value. After we resolve the PHI we must loop over all of the 1623/// using instructions that have scalar map entries and update them. 1624void ScalarEvolutionsImpl::UpdatePHIUserScalarEntries(Instruction *I, 1625 PHINode *PN, 1626 std::set<Instruction*> &UpdatedInsts) { 1627 std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I); 1628 if (SI == Scalars.end()) return; // This scalar wasn't previous processed. 1629 if (UpdatedInsts.insert(I).second) { 1630 Scalars.erase(SI); // Remove the old entry 1631 getSCEV(I); // Calculate the new entry 1632 1633 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 1634 UI != E; ++UI) 1635 UpdatePHIUserScalarEntries(cast<Instruction>(*UI), PN, UpdatedInsts); 1636 } 1637} 1638 1639 1640/// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in 1641/// a loop header, making it a potential recurrence, or it doesn't. 1642/// 1643SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) { 1644 if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized. 1645 if (const Loop *L = LI.getLoopFor(PN->getParent())) 1646 if (L->getHeader() == PN->getParent()) { 1647 // If it lives in the loop header, it has two incoming values, one 1648 // from outside the loop, and one from inside. 1649 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 1650 unsigned BackEdge = IncomingEdge^1; 1651 1652 // While we are analyzing this PHI node, handle its value symbolically. 1653 SCEVHandle SymbolicName = SCEVUnknown::get(PN); 1654 assert(Scalars.find(PN) == Scalars.end() && 1655 "PHI node already processed?"); 1656 Scalars.insert(std::make_pair(PN, SymbolicName)); 1657 1658 // Using this symbolic name for the PHI, analyze the value coming around 1659 // the back-edge. 1660 SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge)); 1661 1662 // NOTE: If BEValue is loop invariant, we know that the PHI node just 1663 // has a special value for the first iteration of the loop. 1664 1665 // If the value coming around the backedge is an add with the symbolic 1666 // value we just inserted, then we found a simple induction variable! 1667 if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) { 1668 // If there is a single occurrence of the symbolic value, replace it 1669 // with a recurrence. 1670 unsigned FoundIndex = Add->getNumOperands(); 1671 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) 1672 if (Add->getOperand(i) == SymbolicName) 1673 if (FoundIndex == e) { 1674 FoundIndex = i; 1675 break; 1676 } 1677 1678 if (FoundIndex != Add->getNumOperands()) { 1679 // Create an add with everything but the specified operand. 1680 std::vector<SCEVHandle> Ops; 1681 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) 1682 if (i != FoundIndex) 1683 Ops.push_back(Add->getOperand(i)); 1684 SCEVHandle Accum = SCEVAddExpr::get(Ops); 1685 1686 // This is not a valid addrec if the step amount is varying each 1687 // loop iteration, but is not itself an addrec in this loop. 1688 if (Accum->isLoopInvariant(L) || 1689 (isa<SCEVAddRecExpr>(Accum) && 1690 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) { 1691 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); 1692 SCEVHandle PHISCEV = SCEVAddRecExpr::get(StartVal, Accum, L); 1693 1694 // Okay, for the entire analysis of this edge we assumed the PHI 1695 // to be symbolic. We now need to go back and update all of the 1696 // entries for the scalars that use the PHI (except for the PHI 1697 // itself) to use the new analyzed value instead of the "symbolic" 1698 // value. 1699 Scalars.find(PN)->second = PHISCEV; // Update the PHI value 1700 std::set<Instruction*> UpdatedInsts; 1701 UpdatedInsts.insert(PN); 1702 for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); 1703 UI != E; ++UI) 1704 UpdatePHIUserScalarEntries(cast<Instruction>(*UI), PN, 1705 UpdatedInsts); 1706 return PHISCEV; 1707 } 1708 } 1709 } 1710 1711 return SymbolicName; 1712 } 1713 1714 // If it's not a loop phi, we can't handle it yet. 1715 return SCEVUnknown::get(PN); 1716} 1717 1718/// createNodeForCast - Handle the various forms of casts that we support. 1719/// 1720SCEVHandle ScalarEvolutionsImpl::createNodeForCast(CastInst *CI) { 1721 const Type *SrcTy = CI->getOperand(0)->getType(); 1722 const Type *DestTy = CI->getType(); 1723 1724 // If this is a noop cast (ie, conversion from int to uint), ignore it. 1725 if (SrcTy->isLosslesslyConvertibleTo(DestTy)) 1726 return getSCEV(CI->getOperand(0)); 1727 1728 if (SrcTy->isInteger() && DestTy->isInteger()) { 1729 // Otherwise, if this is a truncating integer cast, we can represent this 1730 // cast. 1731 if (SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize()) 1732 return SCEVTruncateExpr::get(getSCEV(CI->getOperand(0)), 1733 CI->getType()->getUnsignedVersion()); 1734 if (SrcTy->isUnsigned() && 1735 SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize()) 1736 return SCEVZeroExtendExpr::get(getSCEV(CI->getOperand(0)), 1737 CI->getType()->getUnsignedVersion()); 1738 } 1739 1740 // If this is an sign or zero extending cast and we can prove that the value 1741 // will never overflow, we could do similar transformations. 1742 1743 // Otherwise, we can't handle this cast! 1744 return SCEVUnknown::get(CI); 1745} 1746 1747 1748/// createSCEV - We know that there is no SCEV for the specified value. 1749/// Analyze the expression. 1750/// 1751SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) { 1752 if (Instruction *I = dyn_cast<Instruction>(V)) { 1753 switch (I->getOpcode()) { 1754 case Instruction::Add: 1755 return SCEVAddExpr::get(getSCEV(I->getOperand(0)), 1756 getSCEV(I->getOperand(1))); 1757 case Instruction::Mul: 1758 return SCEVMulExpr::get(getSCEV(I->getOperand(0)), 1759 getSCEV(I->getOperand(1))); 1760 case Instruction::Div: 1761 if (V->getType()->isInteger() && V->getType()->isUnsigned()) 1762 return SCEVUDivExpr::get(getSCEV(I->getOperand(0)), 1763 getSCEV(I->getOperand(1))); 1764 break; 1765 1766 case Instruction::Sub: 1767 return getMinusSCEV(getSCEV(I->getOperand(0)), getSCEV(I->getOperand(1))); 1768 1769 case Instruction::Shl: 1770 // Turn shift left of a constant amount into a multiply. 1771 if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 1772 Constant *X = ConstantInt::get(V->getType(), 1); 1773 X = ConstantExpr::getShl(X, SA); 1774 return SCEVMulExpr::get(getSCEV(I->getOperand(0)), getSCEV(X)); 1775 } 1776 break; 1777 1778 case Instruction::Shr: 1779 if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1))) 1780 if (V->getType()->isUnsigned()) { 1781 Constant *X = ConstantInt::get(V->getType(), 1); 1782 X = ConstantExpr::getShl(X, SA); 1783 return SCEVUDivExpr::get(getSCEV(I->getOperand(0)), getSCEV(X)); 1784 } 1785 break; 1786 1787 case Instruction::Cast: 1788 return createNodeForCast(cast<CastInst>(I)); 1789 1790 case Instruction::PHI: 1791 return createNodeForPHI(cast<PHINode>(I)); 1792 1793 default: // We cannot analyze this expression. 1794 break; 1795 } 1796 } 1797 1798 return SCEVUnknown::get(V); 1799} 1800 1801 1802 1803//===----------------------------------------------------------------------===// 1804// Iteration Count Computation Code 1805// 1806 1807/// getIterationCount - If the specified loop has a predictable iteration 1808/// count, return it. Note that it is not valid to call this method on a 1809/// loop without a loop-invariant iteration count. 1810SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) { 1811 std::map<const Loop*, SCEVHandle>::iterator I = IterationCounts.find(L); 1812 if (I == IterationCounts.end()) { 1813 SCEVHandle ItCount = ComputeIterationCount(L); 1814 I = IterationCounts.insert(std::make_pair(L, ItCount)).first; 1815 if (ItCount != UnknownValue) { 1816 assert(ItCount->isLoopInvariant(L) && 1817 "Computed trip count isn't loop invariant for loop!"); 1818 ++NumTripCountsComputed; 1819 } else if (isa<PHINode>(L->getHeader()->begin())) { 1820 // Only count loops that have phi nodes as not being computable. 1821 ++NumTripCountsNotComputed; 1822 } 1823 } 1824 return I->second; 1825} 1826 1827/// ComputeIterationCount - Compute the number of times the specified loop 1828/// will iterate. 1829SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { 1830 // If the loop has a non-one exit block count, we can't analyze it. 1831 if (L->getExitBlocks().size() != 1) return UnknownValue; 1832 1833 // Okay, there is one exit block. Try to find the condition that causes the 1834 // loop to be exited. 1835 BasicBlock *ExitBlock = L->getExitBlocks()[0]; 1836 1837 BasicBlock *ExitingBlock = 0; 1838 for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock); 1839 PI != E; ++PI) 1840 if (L->contains(*PI)) { 1841 if (ExitingBlock == 0) 1842 ExitingBlock = *PI; 1843 else 1844 return UnknownValue; // More than one block exiting! 1845 } 1846 assert(ExitingBlock && "No exits from loop, something is broken!"); 1847 1848 // Okay, we've computed the exiting block. See what condition causes us to 1849 // exit. 1850 // 1851 // FIXME: we should be able to handle switch instructions (with a single exit) 1852 // FIXME: We should handle cast of int to bool as well 1853 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 1854 if (ExitBr == 0) return UnknownValue; 1855 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!"); 1856 SetCondInst *ExitCond = dyn_cast<SetCondInst>(ExitBr->getCondition()); 1857 if (ExitCond == 0) return UnknownValue; 1858 1859 SCEVHandle LHS = getSCEV(ExitCond->getOperand(0)); 1860 SCEVHandle RHS = getSCEV(ExitCond->getOperand(1)); 1861 1862 // Try to evaluate any dependencies out of the loop. 1863 SCEVHandle Tmp = getSCEVAtScope(LHS, L); 1864 if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp; 1865 Tmp = getSCEVAtScope(RHS, L); 1866 if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp; 1867 1868 // If the condition was exit on true, convert the condition to exit on false. 1869 Instruction::BinaryOps Cond; 1870 if (ExitBr->getSuccessor(1) == ExitBlock) 1871 Cond = ExitCond->getOpcode(); 1872 else 1873 Cond = ExitCond->getInverseCondition(); 1874 1875 // At this point, we would like to compute how many iterations of the loop the 1876 // predicate will return true for these inputs. 1877 if (isa<SCEVConstant>(LHS) && !isa<SCEVConstant>(RHS)) { 1878 // If there is a constant, force it into the RHS. 1879 std::swap(LHS, RHS); 1880 Cond = SetCondInst::getSwappedCondition(Cond); 1881 } 1882 1883 // FIXME: think about handling pointer comparisons! i.e.: 1884 // while (P != P+100) ++P; 1885 1886 // If we have a comparison of a chrec against a constant, try to use value 1887 // ranges to answer this query. 1888 if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) 1889 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS)) 1890 if (AddRec->getLoop() == L) { 1891 // Form the comparison range using the constant of the correct type so 1892 // that the ConstantRange class knows to do a signed or unsigned 1893 // comparison. 1894 ConstantInt *CompVal = RHSC->getValue(); 1895 const Type *RealTy = ExitCond->getOperand(0)->getType(); 1896 CompVal = dyn_cast<ConstantInt>(ConstantExpr::getCast(CompVal, RealTy)); 1897 if (CompVal) { 1898 // Form the constant range. 1899 ConstantRange CompRange(Cond, CompVal); 1900 1901 // Now that we have it, if it's signed, convert it to an unsigned 1902 // range. 1903 if (CompRange.getLower()->getType()->isSigned()) { 1904 const Type *NewTy = RHSC->getValue()->getType(); 1905 Constant *NewL = ConstantExpr::getCast(CompRange.getLower(), NewTy); 1906 Constant *NewU = ConstantExpr::getCast(CompRange.getUpper(), NewTy); 1907 CompRange = ConstantRange(NewL, NewU); 1908 } 1909 1910 SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange); 1911 if (!isa<SCEVCouldNotCompute>(Ret)) return Ret; 1912 } 1913 } 1914 1915 switch (Cond) { 1916 case Instruction::SetNE: // while (X != Y) 1917 // Convert to: while (X-Y != 0) 1918 if (LHS->getType()->isInteger()) 1919 return HowFarToZero(getMinusSCEV(LHS, RHS), L); 1920 break; 1921 case Instruction::SetEQ: 1922 // Convert to: while (X-Y == 0) // while (X == Y) 1923 if (LHS->getType()->isInteger()) 1924 return HowFarToNonZero(getMinusSCEV(LHS, RHS), L); 1925 break; 1926 default: 1927#if 0 1928 std::cerr << "ComputeIterationCount "; 1929 if (ExitCond->getOperand(0)->getType()->isUnsigned()) 1930 std::cerr << "[unsigned] "; 1931 std::cerr << *LHS << " " 1932 << Instruction::getOpcodeName(Cond) << " " << *RHS << "\n"; 1933#endif 1934 break; 1935 } 1936 return UnknownValue; 1937} 1938 1939/// getSCEVAtScope - Compute the value of the specified expression within the 1940/// indicated loop (which may be null to indicate in no loop). If the 1941/// expression cannot be evaluated, return UnknownValue. 1942SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { 1943 // FIXME: this should be turned into a virtual method on SCEV! 1944 1945 if (isa<SCEVConstant>(V) || isa<SCEVUnknown>(V)) return V; 1946 if (SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) { 1947 // Avoid performing the look-up in the common case where the specified 1948 // expression has no loop-variant portions. 1949 for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) { 1950 SCEVHandle OpAtScope = getSCEVAtScope(Comm->getOperand(i), L); 1951 if (OpAtScope != Comm->getOperand(i)) { 1952 if (OpAtScope == UnknownValue) return UnknownValue; 1953 // Okay, at least one of these operands is loop variant but might be 1954 // foldable. Build a new instance of the folded commutative expression. 1955 std::vector<SCEVHandle> NewOps(Comm->op_begin(), Comm->op_begin()+i-1); 1956 NewOps.push_back(OpAtScope); 1957 1958 for (++i; i != e; ++i) { 1959 OpAtScope = getSCEVAtScope(Comm->getOperand(i), L); 1960 if (OpAtScope == UnknownValue) return UnknownValue; 1961 NewOps.push_back(OpAtScope); 1962 } 1963 if (isa<SCEVAddExpr>(Comm)) 1964 return SCEVAddExpr::get(NewOps); 1965 assert(isa<SCEVMulExpr>(Comm) && "Only know about add and mul!"); 1966 return SCEVMulExpr::get(NewOps); 1967 } 1968 } 1969 // If we got here, all operands are loop invariant. 1970 return Comm; 1971 } 1972 1973 if (SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(V)) { 1974 SCEVHandle LHS = getSCEVAtScope(UDiv->getLHS(), L); 1975 if (LHS == UnknownValue) return LHS; 1976 SCEVHandle RHS = getSCEVAtScope(UDiv->getRHS(), L); 1977 if (RHS == UnknownValue) return RHS; 1978 if (LHS == UDiv->getLHS() && RHS == UDiv->getRHS()) 1979 return UDiv; // must be loop invariant 1980 return SCEVUDivExpr::get(LHS, RHS); 1981 } 1982 1983 // If this is a loop recurrence for a loop that does not contain L, then we 1984 // are dealing with the final value computed by the loop. 1985 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) { 1986 if (!L || !AddRec->getLoop()->contains(L->getHeader())) { 1987 // To evaluate this recurrence, we need to know how many times the AddRec 1988 // loop iterates. Compute this now. 1989 SCEVHandle IterationCount = getIterationCount(AddRec->getLoop()); 1990 if (IterationCount == UnknownValue) return UnknownValue; 1991 IterationCount = getTruncateOrZeroExtend(IterationCount, 1992 AddRec->getType()); 1993 1994 // If the value is affine, simplify the expression evaluation to just 1995 // Start + Step*IterationCount. 1996 if (AddRec->isAffine()) 1997 return SCEVAddExpr::get(AddRec->getStart(), 1998 SCEVMulExpr::get(IterationCount, 1999 AddRec->getOperand(1))); 2000 2001 // Otherwise, evaluate it the hard way. 2002 return AddRec->evaluateAtIteration(IterationCount); 2003 } 2004 return UnknownValue; 2005 } 2006 2007 //assert(0 && "Unknown SCEV type!"); 2008 return UnknownValue; 2009} 2010 2011 2012/// SolveQuadraticEquation - Find the roots of the quadratic equation for the 2013/// given quadratic chrec {L,+,M,+,N}. This returns either the two roots (which 2014/// might be the same) or two SCEVCouldNotCompute objects. 2015/// 2016static std::pair<SCEVHandle,SCEVHandle> 2017SolveQuadraticEquation(const SCEVAddRecExpr *AddRec) { 2018 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!"); 2019 SCEVConstant *L = dyn_cast<SCEVConstant>(AddRec->getOperand(0)); 2020 SCEVConstant *M = dyn_cast<SCEVConstant>(AddRec->getOperand(1)); 2021 SCEVConstant *N = dyn_cast<SCEVConstant>(AddRec->getOperand(2)); 2022 2023 // We currently can only solve this if the coefficients are constants. 2024 if (!L || !M || !N) { 2025 SCEV *CNC = new SCEVCouldNotCompute(); 2026 return std::make_pair(CNC, CNC); 2027 } 2028 2029 Constant *Two = ConstantInt::get(L->getValue()->getType(), 2); 2030 2031 // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C 2032 Constant *C = L->getValue(); 2033 // The B coefficient is M-N/2 2034 Constant *B = ConstantExpr::getSub(M->getValue(), 2035 ConstantExpr::getDiv(N->getValue(), 2036 Two)); 2037 // The A coefficient is N/2 2038 Constant *A = ConstantExpr::getDiv(N->getValue(), Two); 2039 2040 // Compute the B^2-4ac term. 2041 Constant *SqrtTerm = 2042 ConstantExpr::getMul(ConstantInt::get(C->getType(), 4), 2043 ConstantExpr::getMul(A, C)); 2044 SqrtTerm = ConstantExpr::getSub(ConstantExpr::getMul(B, B), SqrtTerm); 2045 2046 // Compute floor(sqrt(B^2-4ac)) 2047 ConstantUInt *SqrtVal = 2048 cast<ConstantUInt>(ConstantExpr::getCast(SqrtTerm, 2049 SqrtTerm->getType()->getUnsignedVersion())); 2050 uint64_t SqrtValV = SqrtVal->getValue(); 2051 uint64_t SqrtValV2 = (uint64_t)sqrt(SqrtValV); 2052 // The square root might not be precise for arbitrary 64-bit integer 2053 // values. Do some sanity checks to ensure it's correct. 2054 if (SqrtValV2*SqrtValV2 > SqrtValV || 2055 (SqrtValV2+1)*(SqrtValV2+1) <= SqrtValV) { 2056 SCEV *CNC = new SCEVCouldNotCompute(); 2057 return std::make_pair(CNC, CNC); 2058 } 2059 2060 SqrtVal = ConstantUInt::get(Type::ULongTy, SqrtValV2); 2061 SqrtTerm = ConstantExpr::getCast(SqrtVal, SqrtTerm->getType()); 2062 2063 Constant *NegB = ConstantExpr::getNeg(B); 2064 Constant *TwoA = ConstantExpr::getMul(A, Two); 2065 2066 // The divisions must be performed as signed divisions. 2067 const Type *SignedTy = NegB->getType()->getSignedVersion(); 2068 NegB = ConstantExpr::getCast(NegB, SignedTy); 2069 TwoA = ConstantExpr::getCast(TwoA, SignedTy); 2070 SqrtTerm = ConstantExpr::getCast(SqrtTerm, SignedTy); 2071 2072 Constant *Solution1 = 2073 ConstantExpr::getDiv(ConstantExpr::getAdd(NegB, SqrtTerm), TwoA); 2074 Constant *Solution2 = 2075 ConstantExpr::getDiv(ConstantExpr::getSub(NegB, SqrtTerm), TwoA); 2076 return std::make_pair(SCEVUnknown::get(Solution1), 2077 SCEVUnknown::get(Solution2)); 2078} 2079 2080/// HowFarToZero - Return the number of times a backedge comparing the specified 2081/// value to zero will execute. If not computable, return UnknownValue 2082SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) { 2083 // If the value is a constant 2084 if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) { 2085 // If the value is already zero, the branch will execute zero times. 2086 if (C->getValue()->isNullValue()) return C; 2087 return UnknownValue; // Otherwise it will loop infinitely. 2088 } 2089 2090 SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V); 2091 if (!AddRec || AddRec->getLoop() != L) 2092 return UnknownValue; 2093 2094 if (AddRec->isAffine()) { 2095 // If this is an affine expression the execution count of this branch is 2096 // equal to: 2097 // 2098 // (0 - Start/Step) iff Start % Step == 0 2099 // 2100 // Get the initial value for the loop. 2101 SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop()); 2102 SCEVHandle Step = AddRec->getOperand(1); 2103 2104 Step = getSCEVAtScope(Step, L->getParentLoop()); 2105 2106 // Figure out if Start % Step == 0. 2107 // FIXME: We should add DivExpr and RemExpr operations to our AST. 2108 if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) { 2109 if (StepC->getValue()->equalsInt(1)) // N % 1 == 0 2110 return getNegativeSCEV(Start); // 0 - Start/1 == -Start 2111 if (StepC->getValue()->isAllOnesValue()) // N % -1 == 0 2112 return Start; // 0 - Start/-1 == Start 2113 2114 // Check to see if Start is divisible by SC with no remainder. 2115 if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) { 2116 ConstantInt *StartCC = StartC->getValue(); 2117 Constant *StartNegC = ConstantExpr::getNeg(StartCC); 2118 Constant *Rem = ConstantExpr::getRem(StartNegC, StepC->getValue()); 2119 if (Rem->isNullValue()) { 2120 Constant *Result =ConstantExpr::getDiv(StartNegC,StepC->getValue()); 2121 return SCEVUnknown::get(Result); 2122 } 2123 } 2124 } 2125 } else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) { 2126 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of 2127 // the quadratic equation to solve it. 2128 std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec); 2129 SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first); 2130 SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second); 2131 if (R1) { 2132#if 0 2133 std::cerr << "HFTZ: " << *V << " - sol#1: " << *R1 2134 << " sol#2: " << *R2 << "\n"; 2135#endif 2136 // Pick the smallest positive root value. 2137 assert(R1->getType()->isUnsigned()&&"Didn't canonicalize to unsigned?"); 2138 if (ConstantBool *CB = 2139 dyn_cast<ConstantBool>(ConstantExpr::getSetLT(R1->getValue(), 2140 R2->getValue()))) { 2141 if (CB != ConstantBool::True) 2142 std::swap(R1, R2); // R1 is the minimum root now. 2143 2144 // We can only use this value if the chrec ends up with an exact zero 2145 // value at this index. When solving for "X*X != 5", for example, we 2146 // should not accept a root of 2. 2147 SCEVHandle Val = AddRec->evaluateAtIteration(R1); 2148 if (SCEVConstant *EvalVal = dyn_cast<SCEVConstant>(Val)) 2149 if (EvalVal->getValue()->isNullValue()) 2150 return R1; // We found a quadratic root! 2151 } 2152 } 2153 } 2154 2155 return UnknownValue; 2156} 2157 2158/// HowFarToNonZero - Return the number of times a backedge checking the 2159/// specified value for nonzero will execute. If not computable, return 2160/// UnknownValue 2161SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) { 2162 // Loops that look like: while (X == 0) are very strange indeed. We don't 2163 // handle them yet except for the trivial case. This could be expanded in the 2164 // future as needed. 2165 2166 // If the value is a constant, check to see if it is known to be non-zero 2167 // already. If so, the backedge will execute zero times. 2168 if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) { 2169 Constant *Zero = Constant::getNullValue(C->getValue()->getType()); 2170 Constant *NonZero = ConstantExpr::getSetNE(C->getValue(), Zero); 2171 if (NonZero == ConstantBool::True) 2172 return getSCEV(Zero); 2173 return UnknownValue; // Otherwise it will loop infinitely. 2174 } 2175 2176 // We could implement others, but I really doubt anyone writes loops like 2177 // this, and if they did, they would already be constant folded. 2178 return UnknownValue; 2179} 2180 2181static ConstantInt * 2182EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, Constant *C) { 2183 SCEVHandle InVal = SCEVConstant::get(cast<ConstantInt>(C)); 2184 SCEVHandle Val = AddRec->evaluateAtIteration(InVal); 2185 assert(isa<SCEVConstant>(Val) && 2186 "Evaluation of SCEV at constant didn't fold correctly?"); 2187 return cast<SCEVConstant>(Val)->getValue(); 2188} 2189 2190 2191/// getNumIterationsInRange - Return the number of iterations of this loop that 2192/// produce values in the specified constant range. Another way of looking at 2193/// this is that it returns the first iteration number where the value is not in 2194/// the condition, thus computing the exit count. If the iteration count can't 2195/// be computed, an instance of SCEVCouldNotCompute is returned. 2196SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { 2197 if (Range.isFullSet()) // Infinite loop. 2198 return new SCEVCouldNotCompute(); 2199 2200 // If the start is a non-zero constant, shift the range to simplify things. 2201 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart())) 2202 if (!SC->getValue()->isNullValue()) { 2203 std::vector<SCEVHandle> Operands(op_begin(), op_end()); 2204 Operands[0] = getIntegerSCEV(0, SC->getType()); 2205 SCEVHandle Shifted = SCEVAddRecExpr::get(Operands, getLoop()); 2206 if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted)) 2207 return ShiftedAddRec->getNumIterationsInRange( 2208 Range.subtract(SC->getValue())); 2209 // This is strange and shouldn't happen. 2210 return new SCEVCouldNotCompute(); 2211 } 2212 2213 // The only time we can solve this is when we have all constant indices. 2214 // Otherwise, we cannot determine the overflow conditions. 2215 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 2216 if (!isa<SCEVConstant>(getOperand(i))) 2217 return new SCEVCouldNotCompute(); 2218 2219 2220 // Okay at this point we know that all elements of the chrec are constants and 2221 // that the start element is zero. 2222 2223 // First check to see if the range contains zero. If not, the first 2224 // iteration exits. 2225 ConstantInt *Zero = ConstantInt::get(getType(), 0); 2226 if (!Range.contains(Zero)) return SCEVConstant::get(Zero); 2227 2228 if (isAffine()) { 2229 // If this is an affine expression then we have this situation: 2230 // Solve {0,+,A} in Range === Ax in Range 2231 2232 // Since we know that zero is in the range, we know that the upper value of 2233 // the range must be the first possible exit value. Also note that we 2234 // already checked for a full range. 2235 ConstantInt *Upper = cast<ConstantInt>(Range.getUpper()); 2236 ConstantInt *A = cast<SCEVConstant>(getOperand(1))->getValue(); 2237 ConstantInt *One = ConstantInt::get(getType(), 1); 2238 2239 // The exit value should be (Upper+A-1)/A. 2240 Constant *ExitValue = Upper; 2241 if (A != One) { 2242 ExitValue = ConstantExpr::getSub(ConstantExpr::getAdd(Upper, A), One); 2243 ExitValue = ConstantExpr::getDiv(ExitValue, A); 2244 } 2245 assert(isa<ConstantInt>(ExitValue) && 2246 "Constant folding of integers not implemented?"); 2247 2248 // Evaluate at the exit value. If we really did fall out of the valid 2249 // range, then we computed our trip count, otherwise wrap around or other 2250 // things must have happened. 2251 ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue); 2252 if (Range.contains(Val)) 2253 return new SCEVCouldNotCompute(); // Something strange happened 2254 2255 // Ensure that the previous value is in the range. This is a sanity check. 2256 assert(Range.contains(EvaluateConstantChrecAtConstant(this, 2257 ConstantExpr::getSub(ExitValue, One))) && 2258 "Linear scev computation is off in a bad way!"); 2259 return SCEVConstant::get(cast<ConstantInt>(ExitValue)); 2260 } else if (isQuadratic()) { 2261 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the 2262 // quadratic equation to solve it. To do this, we must frame our problem in 2263 // terms of figuring out when zero is crossed, instead of when 2264 // Range.getUpper() is crossed. 2265 std::vector<SCEVHandle> NewOps(op_begin(), op_end()); 2266 NewOps[0] = getNegativeSCEV(SCEVUnknown::get(Range.getUpper())); 2267 SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, getLoop()); 2268 2269 // Next, solve the constructed addrec 2270 std::pair<SCEVHandle,SCEVHandle> Roots = 2271 SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec)); 2272 SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first); 2273 SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second); 2274 if (R1) { 2275 // Pick the smallest positive root value. 2276 assert(R1->getType()->isUnsigned() && "Didn't canonicalize to unsigned?"); 2277 if (ConstantBool *CB = 2278 dyn_cast<ConstantBool>(ConstantExpr::getSetLT(R1->getValue(), 2279 R2->getValue()))) { 2280 if (CB != ConstantBool::True) 2281 std::swap(R1, R2); // R1 is the minimum root now. 2282 2283 // Make sure the root is not off by one. The returned iteration should 2284 // not be in the range, but the previous one should be. When solving 2285 // for "X*X < 5", for example, we should not return a root of 2. 2286 ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this, 2287 R1->getValue()); 2288 if (Range.contains(R1Val)) { 2289 // The next iteration must be out of the range... 2290 Constant *NextVal = 2291 ConstantExpr::getAdd(R1->getValue(), 2292 ConstantInt::get(R1->getType(), 1)); 2293 2294 R1Val = EvaluateConstantChrecAtConstant(this, NextVal); 2295 if (!Range.contains(R1Val)) 2296 return SCEVUnknown::get(NextVal); 2297 return new SCEVCouldNotCompute(); // Something strange happened 2298 } 2299 2300 // If R1 was not in the range, then it is a good return value. Make 2301 // sure that R1-1 WAS in the range though, just in case. 2302 Constant *NextVal = 2303 ConstantExpr::getSub(R1->getValue(), 2304 ConstantInt::get(R1->getType(), 1)); 2305 R1Val = EvaluateConstantChrecAtConstant(this, NextVal); 2306 if (Range.contains(R1Val)) 2307 return R1; 2308 return new SCEVCouldNotCompute(); // Something strange happened 2309 } 2310 } 2311 } 2312 2313 // Fallback, if this is a general polynomial, figure out the progression 2314 // through brute force: evaluate until we find an iteration that fails the 2315 // test. This is likely to be slow, but getting an accurate trip count is 2316 // incredibly important, we will be able to simplify the exit test a lot, and 2317 // we are almost guaranteed to get a trip count in this case. 2318 ConstantInt *TestVal = ConstantInt::get(getType(), 0); 2319 ConstantInt *One = ConstantInt::get(getType(), 1); 2320 ConstantInt *EndVal = TestVal; // Stop when we wrap around. 2321 do { 2322 ++NumBruteForceEvaluations; 2323 SCEVHandle Val = evaluateAtIteration(SCEVConstant::get(TestVal)); 2324 if (!isa<SCEVConstant>(Val)) // This shouldn't happen. 2325 return new SCEVCouldNotCompute(); 2326 2327 // Check to see if we found the value! 2328 if (!Range.contains(cast<SCEVConstant>(Val)->getValue())) 2329 return SCEVConstant::get(TestVal); 2330 2331 // Increment to test the next index. 2332 TestVal = cast<ConstantInt>(ConstantExpr::getAdd(TestVal, One)); 2333 } while (TestVal != EndVal); 2334 2335 return new SCEVCouldNotCompute(); 2336} 2337 2338 2339 2340//===----------------------------------------------------------------------===// 2341// ScalarEvolution Class Implementation 2342//===----------------------------------------------------------------------===// 2343 2344bool ScalarEvolution::runOnFunction(Function &F) { 2345 Impl = new ScalarEvolutionsImpl(F, getAnalysis<LoopInfo>()); 2346 return false; 2347} 2348 2349void ScalarEvolution::releaseMemory() { 2350 delete (ScalarEvolutionsImpl*)Impl; 2351 Impl = 0; 2352} 2353 2354void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const { 2355 AU.setPreservesAll(); 2356 AU.addRequiredID(LoopSimplifyID); 2357 AU.addRequiredTransitive<LoopInfo>(); 2358} 2359 2360SCEVHandle ScalarEvolution::getSCEV(Value *V) const { 2361 return ((ScalarEvolutionsImpl*)Impl)->getSCEV(V); 2362} 2363 2364SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const { 2365 return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L); 2366} 2367 2368bool ScalarEvolution::hasLoopInvariantIterationCount(const Loop *L) const { 2369 return !isa<SCEVCouldNotCompute>(getIterationCount(L)); 2370} 2371 2372SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) const { 2373 return ((ScalarEvolutionsImpl*)Impl)->getSCEVAtScope(getSCEV(V), L); 2374} 2375 2376void ScalarEvolution::deleteInstructionFromRecords(Instruction *I) const { 2377 return ((ScalarEvolutionsImpl*)Impl)->deleteInstructionFromRecords(I); 2378} 2379 2380 2381/// shouldSubstituteIndVar - Return true if we should perform induction variable 2382/// substitution for this variable. This is a hack because we don't have a 2383/// strength reduction pass yet. When we do we will promote all vars, because 2384/// we can strength reduce them later as desired. 2385bool ScalarEvolution::shouldSubstituteIndVar(const SCEV *S) const { 2386 // Don't substitute high degree polynomials. 2387 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) 2388 if (AddRec->getNumOperands() > 3) return false; 2389 return true; 2390} 2391 2392 2393static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE, 2394 const Loop *L) { 2395 // Print all inner loops first 2396 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 2397 PrintLoopInfo(OS, SE, *I); 2398 2399 std::cerr << "Loop " << L->getHeader()->getName() << ": "; 2400 if (L->getExitBlocks().size() != 1) 2401 std::cerr << "<multiple exits> "; 2402 2403 if (SE->hasLoopInvariantIterationCount(L)) { 2404 std::cerr << *SE->getIterationCount(L) << " iterations! "; 2405 } else { 2406 std::cerr << "Unpredictable iteration count. "; 2407 } 2408 2409 std::cerr << "\n"; 2410} 2411 2412void ScalarEvolution::print(std::ostream &OS) const { 2413 Function &F = ((ScalarEvolutionsImpl*)Impl)->F; 2414 LoopInfo &LI = ((ScalarEvolutionsImpl*)Impl)->LI; 2415 2416 OS << "Classifying expressions for: " << F.getName() << "\n"; 2417 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 2418 if ((*I)->getType()->isInteger()) { 2419 OS << **I; 2420 OS << " --> "; 2421 SCEVHandle SV = getSCEV(*I); 2422 SV->print(OS); 2423 OS << "\t\t"; 2424 2425 if ((*I)->getType()->isIntegral()) { 2426 ConstantRange Bounds = SV->getValueRange(); 2427 if (!Bounds.isFullSet()) 2428 OS << "Bounds: " << Bounds << " "; 2429 } 2430 2431 if (const Loop *L = LI.getLoopFor((*I)->getParent())) { 2432 OS << "Exits: "; 2433 SCEVHandle ExitValue = getSCEVAtScope(*I, L->getParentLoop()); 2434 if (isa<SCEVCouldNotCompute>(ExitValue)) { 2435 OS << "<<Unknown>>"; 2436 } else { 2437 OS << *ExitValue; 2438 } 2439 } 2440 2441 2442 OS << "\n"; 2443 } 2444 2445 OS << "Determining loop execution counts for: " << F.getName() << "\n"; 2446 for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I) 2447 PrintLoopInfo(OS, this, *I); 2448} 2449 2450//===----------------------------------------------------------------------===// 2451// ScalarEvolutionRewriter Class Implementation 2452//===----------------------------------------------------------------------===// 2453 2454Value *ScalarEvolutionRewriter:: 2455GetOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty) { 2456 assert((Ty->isInteger() || Ty->isFloatingPoint()) && 2457 "Can only insert integer or floating point induction variables!"); 2458 2459 // Check to see if we already inserted one. 2460 SCEVHandle H = SCEVAddRecExpr::get(getIntegerSCEV(0, Ty), 2461 getIntegerSCEV(1, Ty), L); 2462 return ExpandCodeFor(H, 0, Ty); 2463} 2464 2465/// ExpandCodeFor - Insert code to directly compute the specified SCEV 2466/// expression into the program. The inserted code is inserted into the 2467/// specified block. 2468Value *ScalarEvolutionRewriter::ExpandCodeFor(SCEVHandle SH, 2469 Instruction *InsertPt, 2470 const Type *Ty) { 2471 std::map<SCEVHandle, Value*>::iterator ExistVal =InsertedExpressions.find(SH); 2472 Value *V; 2473 if (ExistVal != InsertedExpressions.end()) { 2474 V = ExistVal->second; 2475 } else { 2476 // Ask the recurrence object to expand the code for itself. 2477 V = SH->expandCodeFor(*this, InsertPt); 2478 // Cache the generated result. 2479 InsertedExpressions.insert(std::make_pair(SH, V)); 2480 } 2481 2482 if (Ty == 0 || V->getType() == Ty) 2483 return V; 2484 if (Constant *C = dyn_cast<Constant>(V)) 2485 return ConstantExpr::getCast(C, Ty); 2486 else if (Instruction *I = dyn_cast<Instruction>(V)) { 2487 // FIXME: check to see if there is already a cast! 2488 BasicBlock::iterator IP = I; ++IP; 2489 if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 2490 IP = II->getNormalDest()->begin(); 2491 while (isa<PHINode>(IP)) ++IP; 2492 return new CastInst(V, Ty, V->getName(), IP); 2493 } else { 2494 // FIXME: check to see if there is already a cast! 2495 return new CastInst(V, Ty, V->getName(), InsertPt); 2496 } 2497} 2498