ScalarEvolutionExpander.h revision c5701910604cdf65811fabd31d41e38f1d1d4eb1
1//===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- 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 defines the classes used to generate code from scalar expressions. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H 15#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H 16 17#include "llvm/Analysis/ScalarEvolutionExpressions.h" 18#include "llvm/Analysis/ScalarEvolutionNormalization.h" 19#include "llvm/Support/IRBuilder.h" 20#include "llvm/Support/TargetFolder.h" 21#include "llvm/Support/ValueHandle.h" 22#include <set> 23 24namespace llvm { 25 /// SCEVExpander - This class uses information about analyze scalars to 26 /// rewrite expressions in canonical form. 27 /// 28 /// Clients should create an instance of this class when rewriting is needed, 29 /// and destroy it when finished to allow the release of the associated 30 /// memory. 31 class SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> { 32 ScalarEvolution &SE; 33 34 // New instructions receive a name to identifies them with the current pass. 35 const char* IVName; 36 37 std::map<std::pair<const SCEV *, Instruction *>, AssertingVH<Value> > 38 InsertedExpressions; 39 std::set<AssertingVH<Value> > InsertedValues; 40 std::set<AssertingVH<Value> > InsertedPostIncValues; 41 42 /// RelevantLoops - A memoization of the "relevant" loop for a given SCEV. 43 DenseMap<const SCEV *, const Loop *> RelevantLoops; 44 45 /// PostIncLoops - Addrecs referring to any of the given loops are expanded 46 /// in post-inc mode. For example, expanding {1,+,1}<L> in post-inc mode 47 /// returns the add instruction that adds one to the phi for {0,+,1}<L>, 48 /// as opposed to a new phi starting at 1. This is only supported in 49 /// non-canonical mode. 50 PostIncLoopSet PostIncLoops; 51 52 /// IVIncInsertPos - When this is non-null, addrecs expanded in the 53 /// loop it indicates should be inserted with increments at 54 /// IVIncInsertPos. 55 const Loop *IVIncInsertLoop; 56 57 /// IVIncInsertPos - When expanding addrecs in the IVIncInsertLoop loop, 58 /// insert the IV increment at this position. 59 Instruction *IVIncInsertPos; 60 61 /// CanonicalMode - When true, expressions are expanded in "canonical" 62 /// form. In particular, addrecs are expanded as arithmetic based on 63 /// a canonical induction variable. When false, expression are expanded 64 /// in a more literal form. 65 bool CanonicalMode; 66 67 /// When invoked from LSR, the expander is in "strength reduction" mode. The 68 /// only difference is that phi's are only reused if they are already in 69 /// "expanded" form. 70 bool LSRMode; 71 72 typedef IRBuilder<true, TargetFolder> BuilderType; 73 BuilderType Builder; 74 75 friend struct SCEVVisitor<SCEVExpander, Value*>; 76 77 public: 78 /// SCEVExpander - Construct a SCEVExpander in "canonical" mode. 79 explicit SCEVExpander(ScalarEvolution &se, const char *name) 80 : SE(se), IVName(name), IVIncInsertLoop(0), IVIncInsertPos(0), 81 CanonicalMode(true), LSRMode(false), 82 Builder(se.getContext(), TargetFolder(se.TD)) {} 83 84 /// clear - Erase the contents of the InsertedExpressions map so that users 85 /// trying to expand the same expression into multiple BasicBlocks or 86 /// different places within the same BasicBlock can do so. 87 void clear() { 88 InsertedExpressions.clear(); 89 InsertedValues.clear(); 90 InsertedPostIncValues.clear(); 91 } 92 93 /// getOrInsertCanonicalInductionVariable - This method returns the 94 /// canonical induction variable of the specified type for the specified 95 /// loop (inserting one if there is none). A canonical induction variable 96 /// starts at zero and steps by one on each iteration. 97 PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty); 98 99 /// expandCodeFor - Insert code to directly compute the specified SCEV 100 /// expression into the program. The inserted code is inserted into the 101 /// specified block. 102 Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I); 103 104 /// setIVIncInsertPos - Set the current IV increment loop and position. 105 void setIVIncInsertPos(const Loop *L, Instruction *Pos) { 106 assert(!CanonicalMode && 107 "IV increment positions are not supported in CanonicalMode"); 108 IVIncInsertLoop = L; 109 IVIncInsertPos = Pos; 110 } 111 112 /// setPostInc - Enable post-inc expansion for addrecs referring to the 113 /// given loops. Post-inc expansion is only supported in non-canonical 114 /// mode. 115 void setPostInc(const PostIncLoopSet &L) { 116 assert(!CanonicalMode && 117 "Post-inc expansion is not supported in CanonicalMode"); 118 PostIncLoops = L; 119 } 120 121 /// clearPostInc - Disable all post-inc expansion. 122 void clearPostInc() { 123 PostIncLoops.clear(); 124 125 // When we change the post-inc loop set, cached expansions may no 126 // longer be valid. 127 InsertedPostIncValues.clear(); 128 } 129 130 /// disableCanonicalMode - Disable the behavior of expanding expressions in 131 /// canonical form rather than in a more literal form. Non-canonical mode 132 /// is useful for late optimization passes. 133 void disableCanonicalMode() { CanonicalMode = false; } 134 135 void enableLSRMode() { LSRMode = true; } 136 137 /// clearInsertPoint - Clear the current insertion point. This is useful 138 /// if the instruction that had been serving as the insertion point may 139 /// have been deleted. 140 void clearInsertPoint() { 141 Builder.ClearInsertionPoint(); 142 } 143 private: 144 LLVMContext &getContext() const { return SE.getContext(); } 145 146 /// InsertBinop - Insert the specified binary operator, doing a small amount 147 /// of work to avoid inserting an obviously redundant operation. 148 Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS); 149 150 /// ReuseOrCreateCast - Arange for there to be a cast of V to Ty at IP, 151 /// reusing an existing cast if a suitable one exists, moving an existing 152 /// cast if a suitable one exists but isn't in the right place, or 153 /// or creating a new one. 154 Value *ReuseOrCreateCast(Value *V, Type *Ty, 155 Instruction::CastOps Op, 156 BasicBlock::iterator IP); 157 158 /// InsertNoopCastOfTo - Insert a cast of V to the specified type, 159 /// which must be possible with a noop cast, doing what we can to 160 /// share the casts. 161 Value *InsertNoopCastOfTo(Value *V, Type *Ty); 162 163 /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP 164 /// instead of using ptrtoint+arithmetic+inttoptr. 165 Value *expandAddToGEP(const SCEV *const *op_begin, 166 const SCEV *const *op_end, 167 PointerType *PTy, Type *Ty, Value *V); 168 169 Value *expand(const SCEV *S); 170 171 /// expandCodeFor - Insert code to directly compute the specified SCEV 172 /// expression into the program. The inserted code is inserted into the 173 /// SCEVExpander's current insertion point. If a type is specified, the 174 /// result will be expanded to have that type, with a cast if necessary. 175 Value *expandCodeFor(const SCEV *SH, Type *Ty = 0); 176 177 /// isInsertedInstruction - Return true if the specified instruction was 178 /// inserted by the code rewriter. If so, the client should not modify the 179 /// instruction. 180 bool isInsertedInstruction(Instruction *I) const { 181 return InsertedValues.count(I) || InsertedPostIncValues.count(I); 182 } 183 184 /// getRelevantLoop - Determine the most "relevant" loop for the given SCEV. 185 const Loop *getRelevantLoop(const SCEV *); 186 187 Value *visitConstant(const SCEVConstant *S) { 188 return S->getValue(); 189 } 190 191 Value *visitTruncateExpr(const SCEVTruncateExpr *S); 192 193 Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S); 194 195 Value *visitSignExtendExpr(const SCEVSignExtendExpr *S); 196 197 Value *visitAddExpr(const SCEVAddExpr *S); 198 199 Value *visitMulExpr(const SCEVMulExpr *S); 200 201 Value *visitUDivExpr(const SCEVUDivExpr *S); 202 203 Value *visitAddRecExpr(const SCEVAddRecExpr *S); 204 205 Value *visitSMaxExpr(const SCEVSMaxExpr *S); 206 207 Value *visitUMaxExpr(const SCEVUMaxExpr *S); 208 209 Value *visitUnknown(const SCEVUnknown *S) { 210 return S->getValue(); 211 } 212 213 void rememberInstruction(Value *I); 214 215 void restoreInsertPoint(BasicBlock *BB, BasicBlock::iterator I); 216 217 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); 218 219 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L, 220 Type *ExpandTy); 221 222 Value *expandAddRecExprLiterally(const SCEVAddRecExpr *); 223 PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, 224 const Loop *L, 225 Type *ExpandTy, 226 Type *IntTy); 227 }; 228} 229 230#endif 231