ScalarEvolutionExpander.cpp revision 4d177592f265ec5cc1148bd2c35f4b268c4956c4 
1//===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis --*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains the implementation of the scalar evolution expander,
11// which is used to generate the code corresponding to a given scalar evolution
12// expression.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Analysis/ScalarEvolutionExpander.h"
17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/Target/TargetData.h"
19using namespace llvm;
20
21/// InsertCastOfTo - Insert a cast of V to the specified type, doing what
22/// we can to share the casts.
23Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
24                                    const Type *Ty) {
25  // Short-circuit unnecessary bitcasts.
26  if (opcode == Instruction::BitCast && V->getType() == Ty)
27    return V;
28
29  // Short-circuit unnecessary inttoptr<->ptrtoint casts.
30  if (opcode == Instruction::PtrToInt && Ty == TD.getIntPtrType())
31    if (IntToPtrInst *ITP = dyn_cast<IntToPtrInst>(V))
32      return ITP->getOperand(0);
33  if (opcode == Instruction::IntToPtr && V->getType() == TD.getIntPtrType())
34    if (PtrToIntInst *PTI = dyn_cast<PtrToIntInst>(V))
35      return PTI->getOperand(0);
36
37  // FIXME: keep track of the cast instruction.
38  if (Constant *C = dyn_cast<Constant>(V))
39    return ConstantExpr::getCast(opcode, C, Ty);
40
41  if (Argument *A = dyn_cast<Argument>(V)) {
42    // Check to see if there is already a cast!
43    for (Value::use_iterator UI = A->use_begin(), E = A->use_end();
44         UI != E; ++UI) {
45      if ((*UI)->getType() == Ty)
46        if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI)))
47          if (CI->getOpcode() == opcode) {
48            // If the cast isn't the first instruction of the function, move it.
49            if (BasicBlock::iterator(CI) !=
50                A->getParent()->getEntryBlock().begin()) {
51              CI->moveBefore(A->getParent()->getEntryBlock().begin());
52            }
53            return CI;
54          }
55    }
56    return CastInst::Create(opcode, V, Ty, V->getName(),
57                            A->getParent()->getEntryBlock().begin());
58  }
59
60  Instruction *I = cast<Instruction>(V);
61
62  // Check to see if there is already a cast.  If there is, use it.
63  for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
64       UI != E; ++UI) {
65    if ((*UI)->getType() == Ty)
66      if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI)))
67        if (CI->getOpcode() == opcode) {
68          BasicBlock::iterator It = I; ++It;
69          if (isa<InvokeInst>(I))
70            It = cast<InvokeInst>(I)->getNormalDest()->begin();
71          while (isa<PHINode>(It)) ++It;
72          if (It != BasicBlock::iterator(CI)) {
73            // Splice the cast immediately after the operand in question.
74            CI->moveBefore(It);
75          }
76          return CI;
77        }
78  }
79  BasicBlock::iterator IP = I; ++IP;
80  if (InvokeInst *II = dyn_cast<InvokeInst>(I))
81    IP = II->getNormalDest()->begin();
82  while (isa<PHINode>(IP)) ++IP;
83  return CastInst::Create(opcode, V, Ty, V->getName(), IP);
84}
85
86/// InsertBinop - Insert the specified binary operator, doing a small amount
87/// of work to avoid inserting an obviously redundant operation.
88Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
89                                 Value *RHS, Instruction *InsertPt) {
90  // Fold a binop with constant operands.
91  if (Constant *CLHS = dyn_cast<Constant>(LHS))
92    if (Constant *CRHS = dyn_cast<Constant>(RHS))
93      return ConstantExpr::get(Opcode, CLHS, CRHS);
94
95  // Do a quick scan to see if we have this binop nearby.  If so, reuse it.
96  unsigned ScanLimit = 6;
97  BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin();
98  if (InsertPt != BlockBegin) {
99    // Scanning starts from the last instruction before InsertPt.
100    BasicBlock::iterator IP = InsertPt;
101    --IP;
102    for (; ScanLimit; --IP, --ScanLimit) {
103      if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(IP))
104        if (BinOp->getOpcode() == Opcode && BinOp->getOperand(0) == LHS &&
105            BinOp->getOperand(1) == RHS)
106          return BinOp;
107      if (IP == BlockBegin) break;
108    }
109  }
110
111  // If we haven't found this binop, insert it.
112  return BinaryOperator::Create(Opcode, LHS, RHS, "tmp", InsertPt);
113}
114
115Value *SCEVExpander::visitAddExpr(SCEVAddExpr *S) {
116  const Type *Ty = S->getType();
117  if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
118  Value *V = expand(S->getOperand(S->getNumOperands()-1));
119  V = InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty);
120
121  // Emit a bunch of add instructions
122  for (int i = S->getNumOperands()-2; i >= 0; --i) {
123    Value *W = expand(S->getOperand(i));
124    W = InsertCastOfTo(CastInst::getCastOpcode(W, false, Ty, false), W, Ty);
125    V = InsertBinop(Instruction::Add, V, W, InsertPt);
126  }
127  return V;
128}
129
130Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) {
131  const Type *Ty = S->getType();
132  if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
133  int FirstOp = 0;  // Set if we should emit a subtract.
134  if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0)))
135    if (SC->getValue()->isAllOnesValue())
136      FirstOp = 1;
137
138  int i = S->getNumOperands()-2;
139  Value *V = expand(S->getOperand(i+1));
140  V = InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty);
141
142  // Emit a bunch of multiply instructions
143  for (; i >= FirstOp; --i) {
144    Value *W = expand(S->getOperand(i));
145    W = InsertCastOfTo(CastInst::getCastOpcode(W, false, Ty, false), W, Ty);
146    V = InsertBinop(Instruction::Mul, V, W, InsertPt);
147  }
148
149  // -1 * ...  --->  0 - ...
150  if (FirstOp == 1)
151    V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V, InsertPt);
152  return V;
153}
154
155Value *SCEVExpander::visitUDivExpr(SCEVUDivExpr *S) {
156  const Type *Ty = S->getType();
157  if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
158
159  Value *LHS = expand(S->getLHS());
160  LHS = InsertCastOfTo(CastInst::getCastOpcode(LHS, false, Ty, false), LHS, Ty);
161  if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
162    const APInt &RHS = SC->getValue()->getValue();
163    if (RHS.isPowerOf2())
164      return InsertBinop(Instruction::LShr, LHS,
165                         ConstantInt::get(Ty, RHS.logBase2()),
166                         InsertPt);
167  }
168
169  Value *RHS = expand(S->getRHS());
170  RHS = InsertCastOfTo(CastInst::getCastOpcode(RHS, false, Ty, false), RHS, Ty);
171  return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt);
172}
173
174Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) {
175  const Type *Ty = S->getType();
176  const Loop *L = S->getLoop();
177  // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F}
178  assert((Ty->isInteger() || isa<PointerType>(Ty)) &&
179         "Cannot expand fp recurrences yet!");
180
181  // {X,+,F} --> X + {0,+,F}
182  if (!S->getStart()->isZero()) {
183    Value *Start = expand(S->getStart());
184    if (isa<PointerType>(Start->getType()))
185      Start = InsertCastOfTo(Instruction::PtrToInt, Start, TD.getIntPtrType());
186    std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end());
187    NewOps[0] = SE.getIntegerSCEV(0, Ty);
188    Value *Rest = expand(SE.getAddRecExpr(NewOps, L));
189    if (isa<PointerType>(Rest->getType()))
190      Rest = InsertCastOfTo(Instruction::PtrToInt, Rest, TD.getIntPtrType());
191
192    // FIXME: look for an existing add to use.
193    return InsertBinop(Instruction::Add, Rest, Start, InsertPt);
194  }
195
196  // {0,+,1} --> Insert a canonical induction variable into the loop!
197  if (S->isAffine() &&
198      S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) {
199    // Create and insert the PHI node for the induction variable in the
200    // specified loop.
201    BasicBlock *Header = L->getHeader();
202    PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin());
203    PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader());
204
205    pred_iterator HPI = pred_begin(Header);
206    assert(HPI != pred_end(Header) && "Loop with zero preds???");
207    if (!L->contains(*HPI)) ++HPI;
208    assert(HPI != pred_end(Header) && L->contains(*HPI) &&
209           "No backedge in loop?");
210
211    // Insert a unit add instruction right before the terminator corresponding
212    // to the back-edge.
213    Constant *One = ConstantInt::get(Ty, 1);
214    Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next",
215                                                 (*HPI)->getTerminator());
216
217    pred_iterator PI = pred_begin(Header);
218    if (*PI == L->getLoopPreheader())
219      ++PI;
220    PN->addIncoming(Add, *PI);
221    return PN;
222  }
223
224  // Get the canonical induction variable I for this loop.
225  Value *I = getOrInsertCanonicalInductionVariable(L, Ty);
226
227  // If this is a simple linear addrec, emit it now as a special case.
228  if (S->isAffine()) {   // {0,+,F} --> i*F
229    Value *F = expand(S->getOperand(1));
230    if (isa<PointerType>(F->getType()))
231      F = InsertCastOfTo(Instruction::PtrToInt, F, TD.getIntPtrType());
232
233    // IF the step is by one, just return the inserted IV.
234    if (ConstantInt *CI = dyn_cast<ConstantInt>(F))
235      if (CI->getValue() == 1)
236        return I;
237
238    // If the insert point is directly inside of the loop, emit the multiply at
239    // the insert point.  Otherwise, L is a loop that is a parent of the insert
240    // point loop.  If we can, move the multiply to the outer most loop that it
241    // is safe to be in.
242    Instruction *MulInsertPt = InsertPt;
243    Loop *InsertPtLoop = LI.getLoopFor(MulInsertPt->getParent());
244    if (InsertPtLoop != L && InsertPtLoop &&
245        L->contains(InsertPtLoop->getHeader())) {
246      do {
247        // If we cannot hoist the multiply out of this loop, don't.
248        if (!InsertPtLoop->isLoopInvariant(F)) break;
249
250        BasicBlock *InsertPtLoopPH = InsertPtLoop->getLoopPreheader();
251
252        // If this loop hasn't got a preheader, we aren't able to hoist the
253        // multiply.
254        if (!InsertPtLoopPH)
255          break;
256
257        // Otherwise, move the insert point to the preheader.
258        MulInsertPt = InsertPtLoopPH->getTerminator();
259        InsertPtLoop = InsertPtLoop->getParentLoop();
260      } while (InsertPtLoop != L);
261    }
262
263    return InsertBinop(Instruction::Mul, I, F, MulInsertPt);
264  }
265
266  // If this is a chain of recurrences, turn it into a closed form, using the
267  // folders, then expandCodeFor the closed form.  This allows the folders to
268  // simplify the expression without having to build a bunch of special code
269  // into this folder.
270  SCEVHandle IH = SE.getUnknown(I);   // Get I as a "symbolic" SCEV.
271
272  SCEVHandle V = S->evaluateAtIteration(IH, SE);
273  //cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
274
275  return expand(V);
276}
277
278Value *SCEVExpander::visitTruncateExpr(SCEVTruncateExpr *S) {
279  Value *V = expand(S->getOperand());
280  if (isa<PointerType>(V->getType()))
281    V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType());
282  return CastInst::CreateTruncOrBitCast(V, S->getType(), "tmp.", InsertPt);
283}
284
285Value *SCEVExpander::visitZeroExtendExpr(SCEVZeroExtendExpr *S) {
286  const Type *Ty = S->getType();
287  if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
288  Value *V = expand(S->getOperand());
289  if (isa<PointerType>(V->getType()))
290    V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType());
291  return CastInst::CreateZExtOrBitCast(V, Ty, "tmp.", InsertPt);
292}
293
294Value *SCEVExpander::visitSignExtendExpr(SCEVSignExtendExpr *S) {
295  const Type *Ty = S->getType();
296  if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
297  Value *V = expand(S->getOperand());
298  if (isa<PointerType>(V->getType()))
299    V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType());
300  return CastInst::CreateSExtOrBitCast(V, Ty, "tmp.", InsertPt);
301}
302
303Value *SCEVExpander::visitSMaxExpr(SCEVSMaxExpr *S) {
304  const Type *Ty = S->getType();
305  Value *LHS = expand(S->getOperand(0));
306  LHS = InsertCastOfTo(CastInst::getCastOpcode(LHS, false, Ty, false), LHS, Ty);
307  for (unsigned i = 1; i < S->getNumOperands(); ++i) {
308    Value *RHS = expand(S->getOperand(i));
309    RHS = InsertCastOfTo(CastInst::getCastOpcode(RHS, false, Ty, false),
310                         RHS, Ty);
311    Value *ICmp = new ICmpInst(ICmpInst::ICMP_SGT, LHS, RHS, "tmp", InsertPt);
312    LHS = SelectInst::Create(ICmp, LHS, RHS, "smax", InsertPt);
313  }
314  return LHS;
315}
316
317Value *SCEVExpander::visitUMaxExpr(SCEVUMaxExpr *S) {
318  const Type *Ty = S->getType();
319  Value *LHS = expand(S->getOperand(0));
320  LHS = InsertCastOfTo(CastInst::getCastOpcode(LHS, false, Ty, false), LHS, Ty);
321  for (unsigned i = 1; i < S->getNumOperands(); ++i) {
322    Value *RHS = expand(S->getOperand(i));
323    RHS = InsertCastOfTo(CastInst::getCastOpcode(RHS, false, Ty, false),
324                         RHS, Ty);
325    Value *ICmp = new ICmpInst(ICmpInst::ICMP_UGT, LHS, RHS, "tmp", InsertPt);
326    LHS = SelectInst::Create(ICmp, LHS, RHS, "umax", InsertPt);
327  }
328  return LHS;
329}
330
331Value *SCEVExpander::expandCodeFor(SCEVHandle SH, const Type *Ty,
332                                   Instruction *IP) {
333  // Expand the code for this SCEV.
334  assert(TD.getTypeSizeInBits(Ty) == TD.getTypeSizeInBits(SH->getType()) &&
335         "non-trivial casts should be done with the SCEVs directly!");
336  this->InsertPt = IP;
337  Value *V = expand(SH);
338  return InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty);
339}
340
341Value *SCEVExpander::expand(SCEV *S) {
342  // Check to see if we already expanded this.
343  std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S);
344  if (I != InsertedExpressions.end())
345    return I->second;
346
347  Value *V = visit(S);
348  InsertedExpressions[S] = V;
349  return V;
350}
351