Break SCEVExpander out of IndVarSimplify into its own .h/.cpp file so that
[oota-llvm.git] / lib / Analysis / ScalarEvolutionExpander.cpp
1 //===- ScalarEvolutionExpander.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 expander,
11 // which is used to generate the code corresponding to a given scalar evolution
12 // expression.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/Analysis/ScalarEvolutionExpander.h"
18 using namespace llvm;
19
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())
25       FirstOp = 1;
26
27   int i = S->getNumOperands()-2;
28   Value *V = expandInTy(S->getOperand(i+1), Ty);
29
30   // Emit a bunch of multiply instructions
31   for (; i >= FirstOp; --i)
32     V = BinaryOperator::createMul(V, expandInTy(S->getOperand(i), Ty),
33                                   "tmp.", InsertPt);
34   // -1 * ...  --->  0 - ...
35   if (FirstOp == 1)
36     V = BinaryOperator::createNeg(V, "tmp.", InsertPt);
37   return V;
38 }
39
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!");
45
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);
53
54     // FIXME: look for an existing add to use.
55     return BinaryOperator::createAdd(Rest, Start, "tmp.", InsertPt);
56   }
57
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
62     // specified loop.
63     BasicBlock *Header = L->getHeader();
64     PHINode *PN = new PHINode(Ty, "indvar", Header->begin());
65     PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader());
66
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?");
72
73     // Insert a unit add instruction right before the terminator corresponding
74     // to the back-edge.
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());
79
80     pred_iterator PI = pred_begin(Header);
81     if (*PI == L->getLoopPreheader())
82       ++PI;
83     PN->addIncoming(Add, *PI);
84     return PN;
85   }
86
87   // Get the canonical induction variable I for this loop.
88   Value *I = getOrInsertCanonicalInductionVariable(L, Ty);
89
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);
93   }
94
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
98   // into this folder.
99   SCEVHandle IH = SCEVUnknown::get(I);   // Get I as a "symbolic" SCEV.
100
101   SCEVHandle V = S->evaluateAtIteration(IH);
102   //std::cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
103
104   return expandInTy(V, Ty);
105 }