IVUsers.h revision 81db61a2e6d3c95a2738c3559a108e05e9d7a05a
15faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org//===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===// 25faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org// 35faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org// The LLVM Compiler Infrastructure 45faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org// 55faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org// This file is distributed under the University of Illinois Open Source 65faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org// License. See LICENSE.TXT for details. 75faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org// 85faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org//===----------------------------------------------------------------------===// 95faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org// 105faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org// This file implements bookkeeping for "interesting" users of expressions 118b0e8ac5f582de80356019406e2975079bf0829dcommit-bot@chromium.org// computed from induction variables. 128b0e8ac5f582de80356019406e2975079bf0829dcommit-bot@chromium.org// 135faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org//===----------------------------------------------------------------------===// 148640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org 155faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org#ifndef LLVM_ANALYSIS_IVUSERS_H 163bc16c8bc1ecb9ac4450f58093cc9e3edb8a50b8senorblanco@chromium.org#define LLVM_ANALYSIS_IVUSERS_H 17d698f77c13d97c61109b861eac4d25b14a5de935bsalomon@google.com 18dbe49f735484f8862e378b63d0a074a301093dd0bsalomon@google.com#include "llvm/Analysis/LoopPass.h" 192eaaefd7e6a58339b3f93333f1e9cc92252cc303bsalomon@google.com#include "llvm/Analysis/ScalarEvolution.h" 2017fc651dbe2e0624f6c85fb6e081d28a87d5a08bbsalomon@google.com#include <llvm/ADT/SmallVector.h> 2117fc651dbe2e0624f6c85fb6e081d28a87d5a08bbsalomon@google.com#include <map> 223bc16c8bc1ecb9ac4450f58093cc9e3edb8a50b8senorblanco@chromium.org 233bc16c8bc1ecb9ac4450f58093cc9e3edb8a50b8senorblanco@chromium.orgnamespace llvm { 24c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.org 25c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.orgclass DominatorTree; 26c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.orgclass Instruction; 27c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.orgclass Value; 28c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.orgclass IVUsersOfOneStride; 29c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.org 30c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.org/// IVStrideUse - Keep track of one use of a strided induction variable, where 31c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.org/// the stride is stored externally. The Offset member keeps track of the 32c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.org/// offset from the IV, User is the actual user of the operand, and 33c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.org/// 'OperandValToReplace' is the operand of the User that is the use. 34c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.orgclass IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { 35c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.orgpublic: 367938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org IVStrideUse(IVUsersOfOneStride *parent, 377938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org const SCEVHandle &offset, 387938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org Instruction* U, Value *O, bool issigned) 397938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org : CallbackVH(U), Parent(parent), Offset(offset), 407938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org OperandValToReplace(O), IsSigned(issigned), 417938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org IsUseOfPostIncrementedValue(false) { 427938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org } 437938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org 447938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org /// getUser - Return the user instruction for this use. 457938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org Instruction *getUser() const { 467938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org return cast<Instruction>(getValPtr()); 475faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org } 485faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 495faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// setUser - Assign a new user instruction for this use. 505faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org void setUser(Instruction *NewUser) { 518640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org setValPtr(NewUser); 528640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org } 535faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 545faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// getParent - Return a pointer to the IVUsersOfOneStride that owns 555faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// this IVStrideUse. 563bc16c8bc1ecb9ac4450f58093cc9e3edb8a50b8senorblanco@chromium.org IVUsersOfOneStride *getParent() const { return Parent; } 575faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 585faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// getOffset - Return the offset to add to a theoeretical induction 595faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// variable that starts at zero and counts up by the stride to compute 605faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// the value for the use. This always has the same type as the stride, 618b0e8ac5f582de80356019406e2975079bf0829dcommit-bot@chromium.org /// which may need to be casted to match the type of the use. 62ce33d60187718e7bb01944ee130c9f5d9fb335eccommit-bot@chromium.org SCEVHandle getOffset() const { return Offset; } 63025128811219dc45fd99b6c4d1d14f833cf7a26ecommit-bot@chromium.org 64025128811219dc45fd99b6c4d1d14f833cf7a26ecommit-bot@chromium.org /// setOffset - Assign a new offset to this use. 65025128811219dc45fd99b6c4d1d14f833cf7a26ecommit-bot@chromium.org void setOffset(SCEVHandle Val) { 665faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org Offset = Val; 675faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org } 68d594dbec0407343b7ac13af9c4580ec5933ab060commit-bot@chromium.org 69d594dbec0407343b7ac13af9c4580ec5933ab060commit-bot@chromium.org /// getOperandValToReplace - Return the Value of the operand in the user 70d594dbec0407343b7ac13af9c4580ec5933ab060commit-bot@chromium.org /// instruction that this IVStrideUse is representing. 71d594dbec0407343b7ac13af9c4580ec5933ab060commit-bot@chromium.org Value *getOperandValToReplace() const { 72025128811219dc45fd99b6c4d1d14f833cf7a26ecommit-bot@chromium.org return OperandValToReplace; 73025128811219dc45fd99b6c4d1d14f833cf7a26ecommit-bot@chromium.org } 74d594dbec0407343b7ac13af9c4580ec5933ab060commit-bot@chromium.org 75025128811219dc45fd99b6c4d1d14f833cf7a26ecommit-bot@chromium.org /// setOperandValToReplace - Assign a new Value as the operand value 76025128811219dc45fd99b6c4d1d14f833cf7a26ecommit-bot@chromium.org /// to replace. 77d594dbec0407343b7ac13af9c4580ec5933ab060commit-bot@chromium.org void setOperandValToReplace(Value *Op) { 78d594dbec0407343b7ac13af9c4580ec5933ab060commit-bot@chromium.org OperandValToReplace = Op; 79d594dbec0407343b7ac13af9c4580ec5933ab060commit-bot@chromium.org } 805faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 815faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// isSigned - The stride (and thus also the Offset) of this use may be in 82528952b5afea0e82bf6db9ef22128533d50ef9e3senorblanco@chromium.org /// a narrower type than the use itself (OperandValToReplace->getType()). 83528952b5afea0e82bf6db9ef22128533d50ef9e3senorblanco@chromium.org /// When this is the case, isSigned() indicates whether the IV expression 845faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// should be signed-extended instead of zero-extended to fit the type of 858640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org /// the use. 86d594dbec0407343b7ac13af9c4580ec5933ab060commit-bot@chromium.org bool isSigned() const { return IsSigned; } 87d594dbec0407343b7ac13af9c4580ec5933ab060commit-bot@chromium.org 88c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.org /// isUseOfPostIncrementedValue - True if this should use the 89c0b7e10c6a68f59e1653e6c18e6bc954b3c3f0cfcommit-bot@chromium.org /// post-incremented version of this IV, not the preincremented version. 905faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// This can only be set in special cases, such as the terminating setcc 915faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// instruction for a loop or uses dominated by the loop. 928b0e8ac5f582de80356019406e2975079bf0829dcommit-bot@chromium.org bool isUseOfPostIncrementedValue() const { 935faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org return IsUseOfPostIncrementedValue; 945faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org } 955faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 965faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// setIsUseOfPostIncrmentedValue - set the flag that indicates whether 975faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// this is a post-increment use. 985faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org void setIsUseOfPostIncrementedValue(bool Val) { 99528952b5afea0e82bf6db9ef22128533d50ef9e3senorblanco@chromium.org IsUseOfPostIncrementedValue = Val; 100528952b5afea0e82bf6db9ef22128533d50ef9e3senorblanco@chromium.org } 1015faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 1028640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.orgprivate: 1035faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// Parent - a pointer to the IVUsersOfOneStride that owns this IVStrideUse. 1045faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org IVUsersOfOneStride *Parent; 1055faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 1065faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// Offset - The offset to add to the base induction expression. 1075faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org SCEVHandle Offset; 1085faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 1095faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// OperandValToReplace - The Value of the operand in the user instruction 1105faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// that this IVStrideUse is representing. 1117938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org WeakVH OperandValToReplace; 1125faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 1135faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// IsSigned - Determines whether the replacement value is sign or 1145faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// zero extended to the type of the use. 1155faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org bool IsSigned; 1165faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 1175faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// IsUseOfPostIncrementedValue - True if this should use the 1187938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org /// post-incremented version of this IV, not the preincremented version. 1197938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org bool IsUseOfPostIncrementedValue; 1207938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org 1215faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// Deleted - Implementation of CallbackVH virtual function to 1225faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// recieve notification when the User is deleted. 1235faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org virtual void deleted(); 1245faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org}; 1255faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 1265faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.orgtemplate<> struct ilist_traits<IVStrideUse> 1277938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org : public ilist_default_traits<IVStrideUse> { 1287938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org // createSentinel is used to get hold of a node that marks the end of 1297938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org // the list... 1307938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org // The sentinel is relative to this instance, so we use a non-static 1317938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org // method. 1325faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org IVStrideUse *createSentinel() const { 1337938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org // since i(p)lists always publicly derive from the corresponding 1347938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org // traits, placing a data member in this class will augment i(p)list. 1355faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org // But since the NodeTy is expected to publicly derive from 1365faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org // ilist_node<NodeTy>, there is a legal viable downcast from it 1375faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org // to NodeTy. We use this trick to superpose i(p)list with a "ghostly" 1385faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org // NodeTy, which becomes the sentinel. Dereferencing the sentinel is 1395faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org // forbidden (save the ilist_node<NodeTy>) so no one will ever notice 1405faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org // the superposition. 1415faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org return static_cast<IVStrideUse*>(&Sentinel); 1427938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org } 1437938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org static void destroySentinel(IVStrideUse*) {} 1445faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 1455faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org IVStrideUse *provideInitialHead() const { return createSentinel(); } 1465faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); } 1475faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org static void noteHead(IVStrideUse*, IVStrideUse*) {} 1485faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 1495faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.orgprivate: 1505faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org mutable ilist_node<IVStrideUse> Sentinel; 1518640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org}; 1527938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org 1537938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org/// IVUsersOfOneStride - This structure keeps track of all instructions that 1547938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org/// have an operand that is based on the trip count multiplied by some stride. 155ae761f7545d8ebf181d220169afac2056b057b8ccommit-bot@chromium.orgstruct IVUsersOfOneStride : public ilist_node<IVUsersOfOneStride> { 1565faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.orgprivate: 1577938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org IVUsersOfOneStride(const IVUsersOfOneStride &I); // do not implement 1585faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org void operator=(const IVUsersOfOneStride &I); // do not implement 1595faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 1605faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.orgpublic: 1615faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org IVUsersOfOneStride() : Stride(0) {} 1627938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org 1637938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org explicit IVUsersOfOneStride(const SCEV *stride) : Stride(stride) {} 1647938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org 1657938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org /// Stride - The stride for all the contained IVStrideUses. This is 1665faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// a constant for affine strides. 1678640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org const SCEV *Stride; 1688640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org 1698640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org /// Users - Keep track of all of the users of this stride as well as the 1705faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// initial value and the operand that uses the IV. 1715faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org ilist<IVStrideUse> Users; 1725faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 1735faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org void addUser(const SCEVHandle &Offset,Instruction *User, Value *Operand, 1745faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org bool isSigned) { 1758640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org Users.push_back(new IVStrideUse(this, Offset, User, Operand, isSigned)); 1768640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org } 1773bc16c8bc1ecb9ac4450f58093cc9e3edb8a50b8senorblanco@chromium.org}; 178cc9471c36d3967270f7eb26f8b53ce0f17bc9fbbsenorblanco@chromium.org 179cc9471c36d3967270f7eb26f8b53ce0f17bc9fbbsenorblanco@chromium.orgclass IVUsers : public LoopPass { 180cc9471c36d3967270f7eb26f8b53ce0f17bc9fbbsenorblanco@chromium.org friend class IVStrideUserVH; 1818640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org Loop *L; 1827938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org LoopInfo *LI; 1838640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org DominatorTree *DT; 1848640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org ScalarEvolution *SE; 1858640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org SmallPtrSet<Instruction*,16> Processed; 1868640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org 1875faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.orgpublic: 1885faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// IVUses - A list of all tracked IV uses of induction variable expressions 1895faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// we are interested in. 1905faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org ilist<IVUsersOfOneStride> IVUses; 1918640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org 1927938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org /// IVUsesByStride - A mapping from the strides in StrideOrder to the 1937938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org /// uses in IVUses. 1947938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org std::map<SCEVHandle, IVUsersOfOneStride*> IVUsesByStride; 195ae761f7545d8ebf181d220169afac2056b057b8ccommit-bot@chromium.org 1968640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable: 1977938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org /// We use this to iterate over the IVUsesByStride collection without being 1988640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org /// dependent on random ordering of pointers in the process. 1997938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org SmallVector<SCEVHandle, 16> StrideOrder; 2008640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org 2018640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.orgprivate: 2028640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org virtual void getAnalysisUsage(AnalysisUsage &AU) const; 2037938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org 2047938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 2057938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org 206ae761f7545d8ebf181d220169afac2056b057b8ccommit-bot@chromium.org virtual void releaseMemory(); 2077938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org 2085faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.orgpublic: 2095faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org static char ID; // Pass ID, replacement for typeid 2107938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org IVUsers(); 2117938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org 2127938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a 213ae761f7545d8ebf181d220169afac2056b057b8ccommit-bot@chromium.org /// reducible SCEV, recursively add its users to the IVUsesByStride set and 2145faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// return true. Otherwise, return false. 2155faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org bool AddUsersIfInteresting(Instruction *I); 2167938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org 2175faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// getReplacementExpr - Return a SCEV expression which computes the 2185faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org /// value of the OperandValToReplace of the given IVStrideUse. 2197938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org SCEVHandle getReplacementExpr(const IVStrideUse &U) const; 2205faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 2215faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org void print(raw_ostream &OS, const Module* = 0) const; 2227938bae14af94c1d48d122a2d686e123b66411a7senorblanco@chromium.org virtual void print(std::ostream &OS, const Module* = 0) const; 2235faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org void print(std::ostream *OS, const Module* M = 0) const { 2245faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org if (OS) print(*OS, M); 2255faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org } 2265faa2dc266ec933b3961f985e5718236f1ecbe47senorblanco@chromium.org 227377c14a1e648f4427bd11474fad8ac264d98aff2senorblanco@chromium.org /// dump - This method is used for debugging. 2288640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org void dump() const; 2298640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org}; 2308640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org 2318640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.orgPass *createIVUsersPass(); 2328640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org 2338640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org} 2348640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org 2358640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org#endif 2368640d5024d57da5508bdf7585849e3b1f1cb365bsenorblanco@chromium.org