1 //===- AddrModeMatcher.h - Addressing mode matching facility ----*- 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 // AddressingModeMatcher - This class exposes a single public method, which is
11 // used to construct a "maximal munch" of the addressing mode for the target
12 // specified by TLI for an access to "V" with an access type of AccessTy.  This
13 // returns the addressing mode that is actually matched by value, but also
14 // returns the list of instructions involved in that addressing computation in
15 // AddrModeInsts.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #ifndef LLVM_TRANSFORMS_UTILS_ADDRMODEMATCHER_H
20 #define LLVM_TRANSFORMS_UTILS_ADDRMODEMATCHER_H
21 
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/Target/TargetLowering.h"
24 
25 namespace llvm {
26 
27 class GlobalValue;
28 class Instruction;
29 class Value;
30 class Type;
31 class User;
32 class raw_ostream;
33 
34 /// ExtAddrMode - This is an extended version of TargetLowering::AddrMode
35 /// which holds actual Value*'s for register values.
36 struct ExtAddrMode : public TargetLowering::AddrMode {
37   Value *BaseReg;
38   Value *ScaledReg;
ExtAddrModeExtAddrMode39   ExtAddrMode() : BaseReg(0), ScaledReg(0) {}
40   void print(raw_ostream &OS) const;
41   void dump() const;
42 
43   bool operator==(const ExtAddrMode& O) const {
44     return (BaseReg == O.BaseReg) && (ScaledReg == O.ScaledReg) &&
45            (BaseGV == O.BaseGV) && (BaseOffs == O.BaseOffs) &&
46            (HasBaseReg == O.HasBaseReg) && (Scale == O.Scale);
47   }
48 };
49 
50 static inline raw_ostream &operator<<(raw_ostream &OS, const ExtAddrMode &AM) {
51   AM.print(OS);
52   return OS;
53 }
54 
55 class AddressingModeMatcher {
56   SmallVectorImpl<Instruction*> &AddrModeInsts;
57   const TargetLowering &TLI;
58 
59   /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and
60   /// the memory instruction that we're computing this address for.
61   Type *AccessTy;
62   Instruction *MemoryInst;
63 
64   /// AddrMode - This is the addressing mode that we're building up.  This is
65   /// part of the return value of this addressing mode matching stuff.
66   ExtAddrMode &AddrMode;
67 
68   /// IgnoreProfitability - This is set to true when we should not do
69   /// profitability checks.  When true, IsProfitableToFoldIntoAddressingMode
70   /// always returns true.
71   bool IgnoreProfitability;
72 
AddressingModeMatcher(SmallVectorImpl<Instruction * > & AMI,const TargetLowering & T,Type * AT,Instruction * MI,ExtAddrMode & AM)73   AddressingModeMatcher(SmallVectorImpl<Instruction*> &AMI,
74                         const TargetLowering &T, Type *AT,
75                         Instruction *MI, ExtAddrMode &AM)
76     : AddrModeInsts(AMI), TLI(T), AccessTy(AT), MemoryInst(MI), AddrMode(AM) {
77     IgnoreProfitability = false;
78   }
79 public:
80 
81   /// Match - Find the maximal addressing mode that a load/store of V can fold,
82   /// give an access type of AccessTy.  This returns a list of involved
83   /// instructions in AddrModeInsts.
Match(Value * V,Type * AccessTy,Instruction * MemoryInst,SmallVectorImpl<Instruction * > & AddrModeInsts,const TargetLowering & TLI)84   static ExtAddrMode Match(Value *V, Type *AccessTy,
85                            Instruction *MemoryInst,
86                            SmallVectorImpl<Instruction*> &AddrModeInsts,
87                            const TargetLowering &TLI) {
88     ExtAddrMode Result;
89 
90     bool Success =
91       AddressingModeMatcher(AddrModeInsts, TLI, AccessTy,
92                             MemoryInst, Result).MatchAddr(V, 0);
93     (void)Success; assert(Success && "Couldn't select *anything*?");
94     return Result;
95   }
96 private:
97   bool MatchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth);
98   bool MatchAddr(Value *V, unsigned Depth);
99   bool MatchOperationAddr(User *Operation, unsigned Opcode, unsigned Depth);
100   bool IsProfitableToFoldIntoAddressingMode(Instruction *I,
101                                             ExtAddrMode &AMBefore,
102                                             ExtAddrMode &AMAfter);
103   bool ValueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
104 };
105 
106 } // End llvm namespace
107 
108 #endif
109