1 //===-- llvm/CodeGen/GlobalISel/CombinerHelper.h --------------*- 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 contains common combine transformations that may be used in a combine 10 /// pass,or by the target elsewhere. 11 /// Targets can pick individual opcode transformations from the helper or use 12 /// tryCombine which invokes all transformations. All of the transformations 13 /// return true if the MachineInstruction changed and false otherwise. 14 // 15 //===--------------------------------------------------------------------===// 16 17 #ifndef LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H 18 #define LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H 19 20 #include "llvm/CodeGen/LowLevelType.h" 21 #include "llvm/CodeGen/Register.h" 22 #include "llvm/Support/Alignment.h" 23 24 namespace llvm { 25 26 class GISelChangeObserver; 27 class MachineIRBuilder; 28 class MachineRegisterInfo; 29 class MachineInstr; 30 class MachineOperand; 31 class GISelKnownBits; 32 class MachineDominatorTree; 33 class LegalizerInfo; 34 35 struct PreferredTuple { 36 LLT Ty; // The result type of the extend. 37 unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT 38 MachineInstr *MI; 39 }; 40 41 struct IndexedLoadStoreMatchInfo { 42 Register Addr; 43 Register Base; 44 Register Offset; 45 bool IsPre; 46 }; 47 48 struct PtrAddChain { 49 int64_t Imm; 50 Register Base; 51 }; 52 53 class CombinerHelper { 54 protected: 55 MachineIRBuilder &Builder; 56 MachineRegisterInfo &MRI; 57 GISelChangeObserver &Observer; 58 GISelKnownBits *KB; 59 MachineDominatorTree *MDT; 60 const LegalizerInfo *LI; 61 62 public: 63 CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B, 64 GISelKnownBits *KB = nullptr, 65 MachineDominatorTree *MDT = nullptr, 66 const LegalizerInfo *LI = nullptr); 67 68 GISelKnownBits *getKnownBits() const { 69 return KB; 70 } 71 72 /// MachineRegisterInfo::replaceRegWith() and inform the observer of the changes 73 void replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, Register ToReg) const; 74 75 /// Replace a single register operand with a new register and inform the 76 /// observer of the changes. 77 void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromRegOp, 78 Register ToReg) const; 79 80 /// If \p MI is COPY, try to combine it. 81 /// Returns true if MI changed. 82 bool tryCombineCopy(MachineInstr &MI); 83 bool matchCombineCopy(MachineInstr &MI); 84 void applyCombineCopy(MachineInstr &MI); 85 86 /// Returns true if \p DefMI precedes \p UseMI or they are the same 87 /// instruction. Both must be in the same basic block. 88 bool isPredecessor(const MachineInstr &DefMI, const MachineInstr &UseMI); 89 90 /// Returns true if \p DefMI dominates \p UseMI. By definition an 91 /// instruction dominates itself. 92 /// 93 /// If we haven't been provided with a MachineDominatorTree during 94 /// construction, this function returns a conservative result that tracks just 95 /// a single basic block. 96 bool dominates(const MachineInstr &DefMI, const MachineInstr &UseMI); 97 98 /// If \p MI is extend that consumes the result of a load, try to combine it. 99 /// Returns true if MI changed. 100 bool tryCombineExtendingLoads(MachineInstr &MI); 101 bool matchCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo); 102 void applyCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo); 103 104 /// Combine \p MI into a pre-indexed or post-indexed load/store operation if 105 /// legal and the surrounding code makes it useful. 106 bool tryCombineIndexedLoadStore(MachineInstr &MI); 107 bool matchCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo); 108 void applyCombineIndexedLoadStore(MachineInstr &MI, IndexedLoadStoreMatchInfo &MatchInfo); 109 110 bool matchSextAlreadyExtended(MachineInstr &MI); 111 bool applySextAlreadyExtended(MachineInstr &MI); 112 113 bool matchElideBrByInvertingCond(MachineInstr &MI); 114 void applyElideBrByInvertingCond(MachineInstr &MI); 115 bool tryElideBrByInvertingCond(MachineInstr &MI); 116 117 /// If \p MI is G_CONCAT_VECTORS, try to combine it. 118 /// Returns true if MI changed. 119 /// Right now, we support: 120 /// - concat_vector(undef, undef) => undef 121 /// - concat_vector(build_vector(A, B), build_vector(C, D)) => 122 /// build_vector(A, B, C, D) 123 /// 124 /// \pre MI.getOpcode() == G_CONCAT_VECTORS. 125 bool tryCombineConcatVectors(MachineInstr &MI); 126 /// Check if the G_CONCAT_VECTORS \p MI is undef or if it 127 /// can be flattened into a build_vector. 128 /// In the first case \p IsUndef will be true. 129 /// In the second case \p Ops will contain the operands needed 130 /// to produce the flattened build_vector. 131 /// 132 /// \pre MI.getOpcode() == G_CONCAT_VECTORS. 133 bool matchCombineConcatVectors(MachineInstr &MI, bool &IsUndef, 134 SmallVectorImpl<Register> &Ops); 135 /// Replace \p MI with a flattened build_vector with \p Ops or an 136 /// implicit_def if IsUndef is true. 137 void applyCombineConcatVectors(MachineInstr &MI, bool IsUndef, 138 const ArrayRef<Register> Ops); 139 140 /// Try to combine G_SHUFFLE_VECTOR into G_CONCAT_VECTORS. 141 /// Returns true if MI changed. 142 /// 143 /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR. 144 bool tryCombineShuffleVector(MachineInstr &MI); 145 /// Check if the G_SHUFFLE_VECTOR \p MI can be replaced by a 146 /// concat_vectors. 147 /// \p Ops will contain the operands needed to produce the flattened 148 /// concat_vectors. 149 /// 150 /// \pre MI.getOpcode() == G_SHUFFLE_VECTOR. 151 bool matchCombineShuffleVector(MachineInstr &MI, 152 SmallVectorImpl<Register> &Ops); 153 /// Replace \p MI with a concat_vectors with \p Ops. 154 void applyCombineShuffleVector(MachineInstr &MI, 155 const ArrayRef<Register> Ops); 156 157 /// Optimize memcpy intrinsics et al, e.g. constant len calls. 158 /// /p MaxLen if non-zero specifies the max length of a mem libcall to inline. 159 /// 160 /// For example (pre-indexed): 161 /// 162 /// $addr = G_PTR_ADD $base, $offset 163 /// [...] 164 /// $val = G_LOAD $addr 165 /// [...] 166 /// $whatever = COPY $addr 167 /// 168 /// --> 169 /// 170 /// $val, $addr = G_INDEXED_LOAD $base, $offset, 1 (IsPre) 171 /// [...] 172 /// $whatever = COPY $addr 173 /// 174 /// or (post-indexed): 175 /// 176 /// G_STORE $val, $base 177 /// [...] 178 /// $addr = G_PTR_ADD $base, $offset 179 /// [...] 180 /// $whatever = COPY $addr 181 /// 182 /// --> 183 /// 184 /// $addr = G_INDEXED_STORE $val, $base, $offset 185 /// [...] 186 /// $whatever = COPY $addr 187 bool tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen = 0); 188 189 bool matchPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo); 190 bool applyPtrAddImmedChain(MachineInstr &MI, PtrAddChain &MatchInfo); 191 192 /// Transform a multiply by a power-of-2 value to a left shift. 193 bool matchCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal); 194 bool applyCombineMulToShl(MachineInstr &MI, unsigned &ShiftVal); 195 196 /// Reduce a shift by a constant to an unmerge and a shift on a half sized 197 /// type. This will not produce a shift smaller than \p TargetShiftSize. 198 bool matchCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftSize, 199 unsigned &ShiftVal); 200 bool applyCombineShiftToUnmerge(MachineInstr &MI, const unsigned &ShiftVal); 201 bool tryCombineShiftToUnmerge(MachineInstr &MI, unsigned TargetShiftAmount); 202 203 /// Return true if any explicit use operand on \p MI is defined by a 204 /// G_IMPLICIT_DEF. 205 bool matchAnyExplicitUseIsUndef(MachineInstr &MI); 206 207 /// Return true if all register explicit use operands on \p MI are defined by 208 /// a G_IMPLICIT_DEF. 209 bool matchAllExplicitUsesAreUndef(MachineInstr &MI); 210 211 /// Return true if a G_SHUFFLE_VECTOR instruction \p MI has an undef mask. 212 bool matchUndefShuffleVectorMask(MachineInstr &MI); 213 214 /// Return true if a G_STORE instruction \p MI is storing an undef value. 215 bool matchUndefStore(MachineInstr &MI); 216 217 /// Replace an instruction with a G_FCONSTANT with value \p C. 218 bool replaceInstWithFConstant(MachineInstr &MI, double C); 219 220 /// Replace an instruction with a G_CONSTANT with value \p C. 221 bool replaceInstWithConstant(MachineInstr &MI, int64_t C); 222 223 /// Replace an instruction with a G_IMPLICIT_DEF. 224 bool replaceInstWithUndef(MachineInstr &MI); 225 226 /// Delete \p MI and replace all of its uses with its \p OpIdx-th operand. 227 bool replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx); 228 229 /// Return true if \p MOP1 and \p MOP2 are register operands are defined by 230 /// equivalent instructions. 231 bool matchEqualDefs(const MachineOperand &MOP1, const MachineOperand &MOP2); 232 233 /// Return true if \p MOP is defined by a G_CONSTANT with a value equal to 234 /// \p C. 235 bool matchConstantOp(const MachineOperand &MOP, int64_t C); 236 237 /// Optimize (cond ? x : x) -> x 238 bool matchSelectSameVal(MachineInstr &MI); 239 240 /// Optimize (x op x) -> x 241 bool matchBinOpSameVal(MachineInstr &MI); 242 243 /// Check if operand \p OpIdx is zero. 244 bool matchOperandIsZero(MachineInstr &MI, unsigned OpIdx); 245 246 /// Erase \p MI 247 bool eraseInst(MachineInstr &MI); 248 249 /// Return true if MI is a G_ADD which can be simplified to a G_SUB. 250 bool matchSimplifyAddToSub(MachineInstr &MI, 251 std::tuple<Register, Register> &MatchInfo); 252 bool applySimplifyAddToSub(MachineInstr &MI, 253 std::tuple<Register, Register> &MatchInfo); 254 255 /// Try to transform \p MI by using all of the above 256 /// combine functions. Returns true if changed. 257 bool tryCombine(MachineInstr &MI); 258 259 private: 260 // Memcpy family optimization helpers. 261 bool optimizeMemcpy(MachineInstr &MI, Register Dst, Register Src, 262 unsigned KnownLen, Align DstAlign, Align SrcAlign, 263 bool IsVolatile); 264 bool optimizeMemmove(MachineInstr &MI, Register Dst, Register Src, 265 unsigned KnownLen, Align DstAlign, Align SrcAlign, 266 bool IsVolatile); 267 bool optimizeMemset(MachineInstr &MI, Register Dst, Register Val, 268 unsigned KnownLen, Align DstAlign, bool IsVolatile); 269 270 /// Given a non-indexed load or store instruction \p MI, find an offset that 271 /// can be usefully and legally folded into it as a post-indexing operation. 272 /// 273 /// \returns true if a candidate is found. 274 bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base, 275 Register &Offset); 276 277 /// Given a non-indexed load or store instruction \p MI, find an offset that 278 /// can be usefully and legally folded into it as a pre-indexing operation. 279 /// 280 /// \returns true if a candidate is found. 281 bool findPreIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base, 282 Register &Offset); 283 }; 284 } // namespace llvm 285 286 #endif 287