ScalarEvolutionExpander.h revision 667d787c0a21cf3f5dfcde03ca471162ba35b614
136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman//===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===// 236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// The LLVM Compiler Infrastructure 436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman//===----------------------------------------------------------------------===// 936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 1036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// This file defines the classes used to generate code from scalar expressions. 1136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 1236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman//===----------------------------------------------------------------------===// 1336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 1436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H 1536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H 1636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 17789558db70d9513a017c11c5be30945839fdff1cNick Lewycky#include "llvm/Instructions.h" 1836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#include "llvm/Type.h" 1936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#include "llvm/Analysis/ScalarEvolution.h" 2036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#include "llvm/Analysis/ScalarEvolutionExpressions.h" 2136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 2236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begemannamespace llvm { 2336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// SCEVExpander - This class uses information about analyze scalars to 2436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// rewrite expressions in canonical form. 2536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// 2636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// Clients should create an instance of this class when rewriting is needed, 273da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer /// and destroy it when finished to allow the release of the associated 2836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// memory. 2936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> { 3036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman ScalarEvolution &SE; 31667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman std::map<std::pair<const SCEV *, Instruction *>, AssertingVH<Value> > 32667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertedExpressions; 3399a1302ae4c438ab532826685280c0b69687e163Dan Gohman std::set<Value*> InsertedValues; 3436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 356cdc727f2d7f68734526ef078f4632798ad40791Dan Gohman BasicBlock::iterator InsertPt; 3636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 3736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman friend struct SCEVVisitor<SCEVExpander, Value*>; 3836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman public: 395be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman explicit SCEVExpander(ScalarEvolution &se) 405be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman : SE(se) {} 418f9f0d3a34ebbcd6d075fbb1250dc74f36579d50Chris Lattner 4236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// clear - Erase the contents of the InsertedExpressions map so that users 43d29b6aa608d69f19b57ebd2ae630b040b1c4951dJeff Cohen /// trying to expand the same expression into multiple BasicBlocks or 4436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// different places within the same BasicBlock can do so. 4536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman void clear() { InsertedExpressions.clear(); } 46d29b6aa608d69f19b57ebd2ae630b040b1c4951dJeff Cohen 4736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// getOrInsertCanonicalInductionVariable - This method returns the 4836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// canonical induction variable of the specified type for the specified 4936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// loop (inserting one if there is none). A canonical induction variable 5036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// starts at zero and steps by one on each iteration. 511d09de3eca23267855e28297fcb40de3632ea47bDan Gohman Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty); 5236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 53752ec7da506f5d41c08bd37e195750b57550ce68Dan Gohman /// expandCodeFor - Insert code to directly compute the specified SCEV 54752ec7da506f5d41c08bd37e195750b57550ce68Dan Gohman /// expression into the program. The inserted code is inserted into the 5536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// specified block. 56372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson Value *expandCodeFor(const SCEV* SH, const Type *Ty, 57752ec7da506f5d41c08bd37e195750b57550ce68Dan Gohman BasicBlock::iterator IP) { 58667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertPt = IP; 59752ec7da506f5d41c08bd37e195750b57550ce68Dan Gohman return expandCodeFor(SH, Ty); 60752ec7da506f5d41c08bd37e195750b57550ce68Dan Gohman } 6136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 62ed412ac2cbd21e877742fb460efde99887f69482Chris Lattner /// InsertCastOfTo - Insert a cast of V to the specified type, doing what 63ed412ac2cbd21e877742fb460efde99887f69482Chris Lattner /// we can to share the casts. 64f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman Value *InsertCastOfTo(Instruction::CastOps opcode, Value *V, 65f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman const Type *Ty); 66af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 67af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// InsertNoopCastOfTo - Insert a cast of V to the specified type, 68af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// which must be possible with a noop cast. 69af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman Value *InsertNoopCastOfTo(Value *V, const Type *Ty); 70af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 717fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner /// InsertBinop - Insert the specified binary operator, doing a small amount 727fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner /// of work to avoid inserting an obviously redundant operation. 73cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, 74cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Value *RHS, BasicBlock::iterator InsertPt); 75b928c57397f61e4c54274818dd63e61e21016d9dDan Gohman 76b928c57397f61e4c54274818dd63e61e21016d9dDan Gohman private: 775be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP 785be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman /// instead of using ptrtoint+arithmetic+inttoptr. 79372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson Value *expandAddToGEP(const SCEV* const *op_begin, 80372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* const *op_end, 81453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman const PointerType *PTy, const Type *Ty, Value *V); 825be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 83890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *expand(const SCEV *S); 842d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 85667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// expandCodeFor - Insert code to directly compute the specified SCEV 86667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// expression into the program. The inserted code is inserted into the 87667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// SCEVExpander's current insertion point. If a type is specified, the 88667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// result will be expanded to have that type, with a cast if necessary. 89667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *expandCodeFor(const SCEV* SH, const Type *Ty = 0); 90667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman 91667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// isInsertedInstruction - Return true if the specified instruction was 92667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// inserted by the code rewriter. If so, the client should not modify the 93667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// instruction. 94667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman bool isInsertedInstruction(Instruction *I) const { 95667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman return InsertedValues.count(I); 96667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman } 97667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman 98890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitConstant(const SCEVConstant *S) { 9936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return S->getValue(); 10036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 10136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 102890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitTruncateExpr(const SCEVTruncateExpr *S); 10336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 104890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S); 10536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 106890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitSignExtendExpr(const SCEVSignExtendExpr *S); 107d19534add90a2a894af61523b830887097bb780bDan Gohman 108890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitAddExpr(const SCEVAddExpr *S); 10936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 110890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitMulExpr(const SCEVMulExpr *S); 11136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 112890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitUDivExpr(const SCEVUDivExpr *S); 11336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 114890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitAddRecExpr(const SCEVAddRecExpr *S); 11536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 116890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitSMaxExpr(const SCEVSMaxExpr *S); 117c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 118890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitUMaxExpr(const SCEVUMaxExpr *S); 1193e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 120890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitUnknown(const SCEVUnknown *S) { 12136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return S->getValue(); 12236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 12336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman }; 12436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 12536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 12636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#endif 127789558db70d9513a017c11c5be30945839fdff1cNick Lewycky 128