1 //== llvm/CodeGen/GlobalISel/LoadStoreOpt.h - LoadStoreOpt -------*- C++ -*-==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// This is an optimization pass for GlobalISel generic memory operations.
10 /// Specifically, it focuses on merging stores and loads to consecutive
11 /// addresses.
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CODEGEN_GLOBALISEL_LOADSTOREOPT_H
15 #define LLVM_CODEGEN_GLOBALISEL_LOADSTOREOPT_H
16 
17 #include "llvm/ADT/BitVector.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/Analysis/AliasAnalysis.h"
20 #include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
21 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
22 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
23 #include "llvm/CodeGen/GlobalISel/Utils.h"
24 #include "llvm/CodeGen/MachineBasicBlock.h"
25 #include "llvm/CodeGen/MachineFunction.h"
26 #include "llvm/CodeGen/MachineFunctionPass.h"
27 #include "llvm/CodeGen/MachineInstr.h"
28 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
29 
30 namespace llvm {
31 // Forward declarations.
32 class MachineRegisterInfo;
33 namespace GISelAddressing {
34 /// Helper struct to store a base, index and offset that forms an address
35 struct BaseIndexOffset {
36   Register BaseReg;
37   Register IndexReg;
38   int64_t Offset = 0;
39   bool IsIndexSignExt = false;
40 };
41 
42 /// Returns a BaseIndexOffset which describes the pointer in \p Ptr.
43 BaseIndexOffset getPointerInfo(Register Ptr, MachineRegisterInfo &MRI);
44 
45 /// Compute whether or not a memory access at \p MI1 aliases with an access at
46 /// \p MI2 \returns true if either alias/no-alias is known. Sets \p IsAlias
47 /// accordingly.
48 bool aliasIsKnownForLoadStore(const MachineInstr &MI1, const MachineInstr &MI2,
49                               bool &IsAlias, MachineRegisterInfo &MRI);
50 
51 /// Returns true if the instruction \p MI may alias \p Other.
52 /// This function uses multiple strategies to detect aliasing, whereas
53 /// aliasIsKnownForLoadStore just looks at the addresses of load/stores and is
54 /// tries to reason about base/index/offsets.
55 bool instMayAlias(const MachineInstr &MI, const MachineInstr &Other,
56                   MachineRegisterInfo &MRI, AliasAnalysis *AA);
57 } // namespace GISelAddressing
58 
59 using namespace GISelAddressing;
60 
61 class LoadStoreOpt : public MachineFunctionPass {
62 public:
63   static char ID;
64 
65 private:
66   /// An input function to decide if the pass should run or not
67   /// on the given MachineFunction.
68   std::function<bool(const MachineFunction &)> DoNotRunPass;
69 
70   MachineRegisterInfo *MRI;
71   const TargetLowering *TLI;
72   MachineFunction *MF;
73   AliasAnalysis *AA;
74   const LegalizerInfo *LI;
75 
76   MachineIRBuilder Builder;
77 
78   /// Initialize the field members using \p MF.
79   void init(MachineFunction &MF);
80 
81   class StoreMergeCandidate {
82   public:
83     // The base pointer used as the base for all stores in this candidate.
84     Register BasePtr;
85     // Our algorithm is very simple at the moment. We assume that in instruction
86     // order stores are writing to incremeneting consecutive addresses. So when
87     // we walk the block in reverse order, the next eligible store must write to
88     // an offset one store width lower than CurrentLowestOffset.
89     uint64_t CurrentLowestOffset;
90     SmallVector<GStore *> Stores;
91     // A vector of MachineInstr/unsigned pairs to denote potential aliases that
92     // need to be checked before the candidate is considered safe to merge. The
93     // unsigned value is an index into the Stores vector. The indexed store is
94     // the highest-indexed store that has already been checked to not have an
95     // alias with the instruction. We record this so we don't have to repeat
96     // alias checks that have been already done, only those with stores added
97     // after the potential alias is recorded.
98     SmallVector<std::pair<MachineInstr *, unsigned>> PotentialAliases;
99 
100     void addPotentialAlias(MachineInstr &MI);
101 
102     /// Reset this candidate back to an empty one.
103     void reset() {
104       Stores.clear();
105       PotentialAliases.clear();
106       CurrentLowestOffset = 0;
107       BasePtr = Register();
108     }
109   };
110 
111   bool isLegalOrBeforeLegalizer(const LegalityQuery &Query,
112                                 MachineFunction &MF) const;
113   /// If the given store is valid to be a member of the candidate, add it and
114   /// return true. Otherwise, returns false.
115   bool addStoreToCandidate(GStore &MI, StoreMergeCandidate &C);
116   /// Returns true if the instruction \p MI would potentially alias with any
117   /// stores in the candidate \p C.
118   bool operationAliasesWithCandidate(MachineInstr &MI, StoreMergeCandidate &C);
119   /// Merges the stores in the given vector into a wide store.
120   /// \p returns true if at least some of the stores were merged.
121   /// This may decide not to merge stores if heuristics predict it will not be
122   /// worth it.
123   bool mergeStores(SmallVectorImpl<GStore *> &StoresToMerge);
124   /// Perform a merge of all the stores in \p Stores into a single store.
125   /// Erases the old stores from the block when finished.
126   /// \returns true if merging was done. It may fail to perform a merge if
127   /// there are issues with materializing legal wide values.
128   bool doSingleStoreMerge(SmallVectorImpl<GStore *> &Stores);
129   bool processMergeCandidate(StoreMergeCandidate &C);
130   bool mergeBlockStores(MachineBasicBlock &MBB);
131   bool mergeFunctionStores(MachineFunction &MF);
132 
133   /// Initialize some target-specific data structures for the store merging
134   /// optimization. \p AddrSpace indicates which address space to use when
135   /// probing the legalizer info for legal stores.
136   void initializeStoreMergeTargetInfo(unsigned AddrSpace = 0);
137   /// A map between address space numbers and a bitvector of supported stores
138   /// sizes. Each bit in the bitvector represents whether a store size of
139   /// that bit's value is legal. E.g. if bit 64 is set, then 64 bit scalar
140   /// stores are legal.
141   DenseMap<unsigned, BitVector> LegalStoreSizes;
142   bool IsPreLegalizer;
143   /// Contains instructions to be erased at the end of a block scan.
144   SmallSet<MachineInstr *, 16> InstsToErase;
145 
146 public:
147   LoadStoreOpt();
148   LoadStoreOpt(std::function<bool(const MachineFunction &)>);
149 
150   StringRef getPassName() const override { return "LoadStoreOpt"; }
151 
152   MachineFunctionProperties getRequiredProperties() const override {
153     return MachineFunctionProperties()
154         .set(MachineFunctionProperties::Property::IsSSA);
155   }
156 
157   void getAnalysisUsage(AnalysisUsage &AU) const override;
158 
159   bool runOnMachineFunction(MachineFunction &MF) override;
160 };
161 
162 } // End namespace llvm.
163 
164 #endif
165