ScalarEvolutionExpander.h revision 267a385342f2e7388f178b327dd87c5f29afd51b
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 1736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#include "llvm/Analysis/ScalarEvolutionExpressions.h" 18267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman#include "llvm/Support/IRBuilder.h" 19267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman#include "llvm/Support/TargetFolder.h" 2036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 2136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begemannamespace llvm { 2236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// SCEVExpander - This class uses information about analyze scalars to 2336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// rewrite expressions in canonical form. 2436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// 2536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// Clients should create an instance of this class when rewriting is needed, 263da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer /// and destroy it when finished to allow the release of the associated 2736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman /// memory. 2836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> { 2936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman ScalarEvolution &SE; 30667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman std::map<std::pair<const SCEV *, Instruction *>, AssertingVH<Value> > 31667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertedExpressions; 3299a1302ae4c438ab532826685280c0b69687e163Dan Gohman std::set<Value*> InsertedValues; 3336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 34267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman typedef IRBuilder<true, TargetFolder> BuilderType; 35267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BuilderType Builder; 3636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 3736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman friend struct SCEVVisitor<SCEVExpander, Value*>; 3836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman public: 395be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman explicit SCEVExpander(ScalarEvolution &se) 40267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman : SE(se), Builder(TargetFolder(se.TD)) {} 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. 56267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *expandCodeFor(const SCEV* SH, const Type *Ty, Instruction *IP) { 57267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Builder.SetInsertPoint(IP->getParent(), IP); 58752ec7da506f5d41c08bd37e195750b57550ce68Dan Gohman return expandCodeFor(SH, Ty); 59752ec7da506f5d41c08bd37e195750b57550ce68Dan Gohman } 6036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 61267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman private: 62267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman /// InsertBinop - Insert the specified binary operator, doing a small amount 63267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman /// of work to avoid inserting an obviously redundant operation. 64267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS); 65af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 66af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman /// InsertNoopCastOfTo - Insert a cast of V to the specified type, 67267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman /// which must be possible with a noop cast, doing what we can to 68267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman /// share the casts. 69af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman Value *InsertNoopCastOfTo(Value *V, const Type *Ty); 70af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 715be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP 725be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman /// instead of using ptrtoint+arithmetic+inttoptr. 73372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson Value *expandAddToGEP(const SCEV* const *op_begin, 74372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* const *op_end, 75453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman const PointerType *PTy, const Type *Ty, Value *V); 765be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 77890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *expand(const SCEV *S); 782d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 79667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// expandCodeFor - Insert code to directly compute the specified SCEV 80667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// expression into the program. The inserted code is inserted into the 81667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// SCEVExpander's current insertion point. If a type is specified, the 82667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// result will be expanded to have that type, with a cast if necessary. 83667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *expandCodeFor(const SCEV* SH, const Type *Ty = 0); 84667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman 85667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// isInsertedInstruction - Return true if the specified instruction was 86667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// inserted by the code rewriter. If so, the client should not modify the 87667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman /// instruction. 88667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman bool isInsertedInstruction(Instruction *I) const { 89667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman return InsertedValues.count(I); 90667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman } 91667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman 92890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitConstant(const SCEVConstant *S) { 9336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return S->getValue(); 9436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 9536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 96890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitTruncateExpr(const SCEVTruncateExpr *S); 9736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 98890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S); 9936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 100890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitSignExtendExpr(const SCEVSignExtendExpr *S); 101d19534add90a2a894af61523b830887097bb780bDan Gohman 102890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitAddExpr(const SCEVAddExpr *S); 10336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 104890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitMulExpr(const SCEVMulExpr *S); 10536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 106890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitUDivExpr(const SCEVUDivExpr *S); 10736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 108890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitAddRecExpr(const SCEVAddRecExpr *S); 10936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 110890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitSMaxExpr(const SCEVSMaxExpr *S); 111c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 112890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitUMaxExpr(const SCEVUMaxExpr *S); 1133e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 114890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman Value *visitUnknown(const SCEVUnknown *S) { 11536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return S->getValue(); 11636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 11736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman }; 11836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 11936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 12036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#endif 121789558db70d9513a017c11c5be30945839fdff1cNick Lewycky 122