181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman//===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===// 281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman// 381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman// The LLVM Compiler Infrastructure 481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman// 581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman// This file is distributed under the University of Illinois Open Source 681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman// License. See LICENSE.TXT for details. 781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman// 881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman//===----------------------------------------------------------------------===// 981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman// 1081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman// This file implements bookkeeping for "interesting" users of expressions 1181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman// computed from induction variables. 1281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman// 1381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman//===----------------------------------------------------------------------===// 1481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#ifndef LLVM_ANALYSIS_IVUSERS_H 1681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#define LLVM_ANALYSIS_IVUSERS_H 1781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Analysis/LoopPass.h" 19448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman#include "llvm/Analysis/ScalarEvolutionNormalization.h" 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/ValueHandle.h" 2181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 2281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmannamespace llvm { 2381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 2481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanclass DominatorTree; 2581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanclass Instruction; 2681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanclass Value; 27572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohmanclass ScalarEvolution; 28572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohmanclass SCEV; 29448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmanclass IVUsers; 303574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowclass DataLayout; 31572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 32572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman/// IVStrideUse - Keep track of one use of a strided induction variable. 33572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman/// The Expr member keeps track of the expression, User is the actual user 34572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman/// instruction of the operand, and 'OperandValToReplace' is the operand of 35572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman/// the User that is the use. 3681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanclass IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { 37448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman friend class IVUsers; 3881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanpublic: 394417e537b65c14b378aeca75b2773582dd102f63Andrew Trick IVStrideUse(IVUsers *P, Instruction* U, Value *O) 404417e537b65c14b378aeca75b2773582dd102f63Andrew Trick : CallbackVH(U), Parent(P), OperandValToReplace(O) { 4181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 4281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 4381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// getUser - Return the user instruction for this use. 4481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *getUser() const { 4581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return cast<Instruction>(getValPtr()); 4681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 4781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 4881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// setUser - Assign a new user instruction for this use. 4981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman void setUser(Instruction *NewUser) { 5081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman setValPtr(NewUser); 5181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 5281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 5381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// getOperandValToReplace - Return the Value of the operand in the user 5481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// instruction that this IVStrideUse is representing. 5581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Value *getOperandValToReplace() const { 5681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return OperandValToReplace; 5781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 5881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 5981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// setOperandValToReplace - Assign a new Value as the operand value 6081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// to replace. 6181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman void setOperandValToReplace(Value *Op) { 6281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman OperandValToReplace = Op; 6381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 6481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 65448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman /// getPostIncLoops - Return the set of loops for which the expression has 66448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman /// been adjusted to use post-inc mode. 67448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman const PostIncLoopSet &getPostIncLoops() const { 68448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return PostIncLoops; 6981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 7081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 71448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman /// transformToPostInc - Transform the expression to post-inc form for the 72448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman /// given loop. 73448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman void transformToPostInc(const Loop *L); 7481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 7581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanprivate: 76572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman /// Parent - a pointer to the IVUsers that owns this IVStrideUse. 77572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman IVUsers *Parent; 78572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 7981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// OperandValToReplace - The Value of the operand in the user instruction 8081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// that this IVStrideUse is representing. 8181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman WeakVH OperandValToReplace; 8281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 83448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman /// PostIncLoops - The set of loops for which Expr has been adjusted to 84448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept. 85448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman PostIncLoopSet PostIncLoops; 8681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 8781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// Deleted - Implementation of CallbackVH virtual function to 883f46a3abeedba8d517b4182de34c821d752db058Dan Gohman /// receive notification when the User is deleted. 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void deleted() override; 9081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman}; 9181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 9281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmantemplate<> struct ilist_traits<IVStrideUse> 9381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman : public ilist_default_traits<IVStrideUse> { 9481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // createSentinel is used to get hold of a node that marks the end of 9581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // the list... 9681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // The sentinel is relative to this instance, so we use a non-static 9781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // method. 9881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IVStrideUse *createSentinel() const { 9981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // since i(p)lists always publicly derive from the corresponding 10081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // traits, placing a data member in this class will augment i(p)list. 10181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // But since the NodeTy is expected to publicly derive from 10281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // ilist_node<NodeTy>, there is a legal viable downcast from it 10381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // to NodeTy. We use this trick to superpose i(p)list with a "ghostly" 10481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // NodeTy, which becomes the sentinel. Dereferencing the sentinel is 10581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // forbidden (save the ilist_node<NodeTy>) so no one will ever notice 10681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // the superposition. 10781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return static_cast<IVStrideUse*>(&Sentinel); 10881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 10981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman static void destroySentinel(IVStrideUse*) {} 11081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 11181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IVStrideUse *provideInitialHead() const { return createSentinel(); } 11281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); } 11381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman static void noteHead(IVStrideUse*, IVStrideUse*) {} 11481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 11581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanprivate: 11681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman mutable ilist_node<IVStrideUse> Sentinel; 11781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman}; 11881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 11981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanclass IVUsers : public LoopPass { 120572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman friend class IVStrideUse; 12181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Loop *L; 12281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman LoopInfo *LI; 12381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman DominatorTree *DT; 12481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ScalarEvolution *SE; 12536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DataLayout *DL; 126191bd64a39490fa75d35b9aaecdd57b00c7a8b5fDan Gohman SmallPtrSet<Instruction*,16> Processed; 12781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 12881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// IVUses - A list of all tracked IV uses of induction variable expressions 12981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// we are interested in. 130572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ilist<IVStrideUse> IVUses; 13181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 13381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 13436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnLoop(Loop *L, LPPassManager &LPM) override; 13581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 13636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseMemory() override; 13781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 13881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanpublic: 13981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman static char ID; // Pass ID, replacement for typeid 14081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IVUsers(); 14181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1424b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick Loop *getLoop() const { return L; } 1434b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick 144191bd64a39490fa75d35b9aaecdd57b00c7a8b5fDan Gohman /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a 145191bd64a39490fa75d35b9aaecdd57b00c7a8b5fDan Gohman /// reducible SCEV, recursively add its users to the IVUsesByStride set and 146191bd64a39490fa75d35b9aaecdd57b00c7a8b5fDan Gohman /// return true. Otherwise, return false. 1471508e5e0495a3b3d034cb8e0b9be16b01749d8b3Andrew Trick bool AddUsersIfInteresting(Instruction *I); 14881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1494417e537b65c14b378aeca75b2773582dd102f63Andrew Trick IVStrideUse &AddUser(Instruction *User, Value *Operand); 150586f69a11881d828c056ce017b3fb432341d9657Evan Cheng 15181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// getReplacementExpr - Return a SCEV expression which computes the 15281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// value of the OperandValToReplace of the given IVStrideUse. 153c056454ecfe66f7c646fedef594f4ed48a9f3bf0Dan Gohman const SCEV *getReplacementExpr(const IVStrideUse &IU) const; 154c056454ecfe66f7c646fedef594f4ed48a9f3bf0Dan Gohman 155c056454ecfe66f7c646fedef594f4ed48a9f3bf0Dan Gohman /// getExpr - Return the expression for the use. 156c056454ecfe66f7c646fedef594f4ed48a9f3bf0Dan Gohman const SCEV *getExpr(const IVStrideUse &IU) const; 157c056454ecfe66f7c646fedef594f4ed48a9f3bf0Dan Gohman 158c056454ecfe66f7c646fedef594f4ed48a9f3bf0Dan Gohman const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const; 15981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 160572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman typedef ilist<IVStrideUse>::iterator iterator; 161572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman typedef ilist<IVStrideUse>::const_iterator const_iterator; 162572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman iterator begin() { return IVUses.begin(); } 163572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman iterator end() { return IVUses.end(); } 164572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const_iterator begin() const { return IVUses.begin(); } 165572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const_iterator end() const { return IVUses.end(); } 166572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman bool empty() const { return IVUses.empty(); } 167572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 168260bf5364e151754c16f723d62c4080009bf98cbAndrew Trick bool isIVUserOrOperand(Instruction *Inst) const { 169260bf5364e151754c16f723d62c4080009bf98cbAndrew Trick return Processed.count(Inst); 170260bf5364e151754c16f723d62c4080009bf98cbAndrew Trick } 171260bf5364e151754c16f723d62c4080009bf98cbAndrew Trick 172dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void print(raw_ostream &OS, const Module* = nullptr) const override; 17381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 17481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman /// dump - This method is used for debugging. 17581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman void dump() const; 1761508e5e0495a3b3d034cb8e0b9be16b01749d8b3Andrew Trickprotected: 1771508e5e0495a3b3d034cb8e0b9be16b01749d8b3Andrew Trick bool AddUsersImpl(Instruction *I, SmallPtrSet<Loop*,16> &SimpleLoopNests); 17881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman}; 17981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 18081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan GohmanPass *createIVUsersPass(); 18181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 18281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 18381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 18481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#endif 185