ScalarEvolutionExpander.h revision 60a05cc118763c680834a61280f48530482a1f86
119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project//===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===// 219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project// 319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project// The LLVM Compiler Infrastructure 419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project// 519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project// This file was developed by the LLVM research group and is distributed under 619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project// the University of Illinois Open Source License. See LICENSE.TXT for details. 719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project// 819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project//===----------------------------------------------------------------------===// 919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project// 1019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project// This file defines the classes used to generate code from scalar expressions. 1119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project// 123984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt//===----------------------------------------------------------------------===// 1319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 1419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H 1519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H 1619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 1719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#include "llvm/BasicBlock.h" 1819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#include "llvm/Constants.h" 1919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#include "llvm/Instructions.h" 2019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#include "llvm/Type.h" 2119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#include "llvm/Analysis/ScalarEvolution.h" 2219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#include "llvm/Analysis/ScalarEvolutionExpressions.h" 2319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project#include "llvm/Support/CFG.h" 2419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 2519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Projectnamespace llvm { 2619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// SCEVExpander - This class uses information about analyze scalars to 2719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// rewrite expressions in canonical form. 2819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// 2919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// Clients should create an instance of this class when rewriting is needed, 3019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// and destroying it when finished to allow the release of the associated 313984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt /// memory. 323984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> { 3319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project ScalarEvolution &SE; 3419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project LoopInfo &LI; 3519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project std::map<SCEVHandle, Value*> InsertedExpressions; 3619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project std::set<Instruction*> InsertedInstructions; 3719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 3819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project Instruction *InsertPt; 3919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 4019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project friend struct SCEVVisitor<SCEVExpander, Value*>; 4119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project public: 4219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project SCEVExpander(ScalarEvolution &se, LoopInfo &li) : SE(se), LI(li) {} 4319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 4419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project LoopInfo &getLoopInfo() const { return LI; } 4519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 4619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// clear - Erase the contents of the InsertedExpressions map so that users 4719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// trying to expand the same expression into multiple BasicBlocks or 4819dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// different places within the same BasicBlock can do so. 4919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project void clear() { InsertedExpressions.clear(); } 5019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 5119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// isInsertedInstruction - Return true if the specified instruction was 5219dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// inserted by the code rewriter. If so, the client should not modify the 5319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// instruction. 5419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project bool isInsertedInstruction(Instruction *I) const { 5519dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project return InsertedInstructions.count(I); 5619dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project } 5719dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project 583984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt /// getOrInsertCanonicalInductionVariable - This method returns the 5919dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// canonical induction variable of the specified type for the specified 6019dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// loop (inserting one if there is none). A canonical induction variable 6119dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project /// starts at zero and steps by one on each iteration. 623984b61df41c68966bdfbb2a5e5a45ef4b9a536cDmitry Shmidt Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty){ 6319dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project assert((Ty->isInteger() || Ty->isFloatingPoint()) && 6419dacda2b02bb08c0ffb649f84526b249c749279The Android Open Source Project "Can only insert integer or floating point induction variables!"); 65 SCEVHandle H = SCEVAddRecExpr::get(SCEVUnknown::getIntegerSCEV(0, Ty), 66 SCEVUnknown::getIntegerSCEV(1, Ty), L); 67 return expand(H); 68 } 69 70 /// addInsertedValue - Remember the specified instruction as being the 71 /// canonical form for the specified SCEV. 72 void addInsertedValue(Instruction *I, SCEV *S) { 73 InsertedExpressions[S] = (Value*)I; 74 InsertedInstructions.insert(I); 75 } 76 77 /// expandCodeFor - Insert code to directly compute the specified SCEV 78 /// expression into the program. The inserted code is inserted into the 79 /// specified block. 80 /// 81 /// If a particular value sign is required, a type may be specified for the 82 /// result. 83 Value *expandCodeFor(SCEVHandle SH, Instruction *IP, const Type *Ty = 0) { 84 // Expand the code for this SCEV. 85 this->InsertPt = IP; 86 return expandInTy(SH, Ty); 87 } 88 89 /// InsertCastOfTo - Insert a cast of V to the specified type, doing what 90 /// we can to share the casts. 91 static Value *InsertCastOfTo(Value *V, const Type *Ty); 92 93 protected: 94 Value *expand(SCEV *S) { 95 // Check to see if we already expanded this. 96 std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S); 97 if (I != InsertedExpressions.end()) 98 return I->second; 99 100 Value *V = visit(S); 101 InsertedExpressions[S] = V; 102 return V; 103 } 104 105 Value *expandInTy(SCEV *S, const Type *Ty) { 106 Value *V = expand(S); 107 if (Ty && V->getType() != Ty) 108 return InsertCastOfTo(V, Ty); 109 return V; 110 } 111 112 Value *visitConstant(SCEVConstant *S) { 113 return S->getValue(); 114 } 115 116 Value *visitTruncateExpr(SCEVTruncateExpr *S) { 117 Value *V = expand(S->getOperand()); 118 return new CastInst(V, S->getType(), "tmp.", InsertPt); 119 } 120 121 Value *visitZeroExtendExpr(SCEVZeroExtendExpr *S) { 122 Value *V = expandInTy(S->getOperand(),S->getType()->getUnsignedVersion()); 123 return new CastInst(V, S->getType(), "tmp.", InsertPt); 124 } 125 126 Value *visitAddExpr(SCEVAddExpr *S) { 127 const Type *Ty = S->getType(); 128 Value *V = expandInTy(S->getOperand(S->getNumOperands()-1), Ty); 129 130 // Emit a bunch of add instructions 131 for (int i = S->getNumOperands()-2; i >= 0; --i) 132 V = BinaryOperator::createAdd(V, expandInTy(S->getOperand(i), Ty), 133 "tmp.", InsertPt); 134 return V; 135 } 136 137 Value *visitMulExpr(SCEVMulExpr *S); 138 139 Value *visitSDivExpr(SCEVSDivExpr *S) { 140 const Type *Ty = S->getType(); 141 Value *LHS = expandInTy(S->getLHS(), Ty); 142 Value *RHS = expandInTy(S->getRHS(), Ty); 143 return BinaryOperator::createDiv(LHS, RHS, "tmp.", InsertPt); 144 } 145 146 Value *visitAddRecExpr(SCEVAddRecExpr *S); 147 148 Value *visitUnknown(SCEVUnknown *S) { 149 return S->getValue(); 150 } 151 }; 152} 153 154#endif 155 156