1 //===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This file contains the implementation of the scalar evolution expander,
11 // which is used to generate the code corresponding to a given scalar evolution
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/Analysis/ScalarEvolutionExpander.h"
20 Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) {
21 const Type *Ty = S->getType();
22 int FirstOp = 0; // Set if we should emit a subtract.
23 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0)))
24 if (SC->getValue()->isAllOnesValue())
27 int i = S->getNumOperands()-2;
28 Value *V = expandInTy(S->getOperand(i+1), Ty);
30 // Emit a bunch of multiply instructions
31 for (; i >= FirstOp; --i)
32 V = BinaryOperator::createMul(V, expandInTy(S->getOperand(i), Ty),
34 // -1 * ... ---> 0 - ...
36 V = BinaryOperator::createNeg(V, "tmp.", InsertPt);
40 Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
41 const Type *Ty = S->getType();
42 const Loop *L = S->getLoop();
43 // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F}
44 assert(Ty->isIntegral() && "Cannot expand fp recurrences yet!");
46 // {X,+,F} --> X + {0,+,F}
47 if (!isa<SCEVConstant>(S->getStart()) ||
48 !cast<SCEVConstant>(S->getStart())->getValue()->isNullValue()) {
49 Value *Start = expandInTy(S->getStart(), Ty);
50 std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end());
51 NewOps[0] = SCEVUnknown::getIntegerSCEV(0, Ty);
52 Value *Rest = expandInTy(SCEVAddRecExpr::get(NewOps, L), Ty);
54 // FIXME: look for an existing add to use.
55 return BinaryOperator::createAdd(Rest, Start, "tmp.", InsertPt);
58 // {0,+,1} --> Insert a canonical induction variable into the loop!
59 if (S->getNumOperands() == 2 &&
60 S->getOperand(1) == SCEVUnknown::getIntegerSCEV(1, Ty)) {
61 // Create and insert the PHI node for the induction variable in the
63 BasicBlock *Header = L->getHeader();
64 PHINode *PN = new PHINode(Ty, "indvar", Header->begin());
65 PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader());
67 pred_iterator HPI = pred_begin(Header);
68 assert(HPI != pred_end(Header) && "Loop with zero preds???");
69 if (!L->contains(*HPI)) ++HPI;
70 assert(HPI != pred_end(Header) && L->contains(*HPI) &&
71 "No backedge in loop?");
73 // Insert a unit add instruction right before the terminator corresponding
75 Constant *One = Ty->isFloatingPoint() ? (Constant*)ConstantFP::get(Ty, 1.0)
76 : ConstantInt::get(Ty, 1);
77 Instruction *Add = BinaryOperator::createAdd(PN, One, "indvar.next",
78 (*HPI)->getTerminator());
80 pred_iterator PI = pred_begin(Header);
81 if (*PI == L->getLoopPreheader())
83 PN->addIncoming(Add, *PI);
87 // Get the canonical induction variable I for this loop.
88 Value *I = getOrInsertCanonicalInductionVariable(L, Ty);
90 if (S->getNumOperands() == 2) { // {0,+,F} --> i*F
91 Value *F = expandInTy(S->getOperand(1), Ty);
92 return BinaryOperator::createMul(I, F, "tmp.", InsertPt);
95 // If this is a chain of recurrences, turn it into a closed form, using the
96 // folders, then expandCodeFor the closed form. This allows the folders to
97 // simplify the expression without having to build a bunch of special code
99 SCEVHandle IH = SCEVUnknown::get(I); // Get I as a "symbolic" SCEV.
101 SCEVHandle V = S->evaluateAtIteration(IH);
102 //std::cerr << "Evaluated: " << *this << "\n to: " << *V << "\n";
104 return expandInTy(V, Ty);