| 1 | //===-- CodeGenCommonISel.cpp ---------------------------------------------===// |
| 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 file defines common utilies that are shared between SelectionDAG and |
| 10 | // GlobalISel frameworks. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "llvm/CodeGen/CodeGenCommonISel.h" |
| 15 | #include "llvm/ADT/SmallPtrSet.h" |
| 16 | #include "llvm/Analysis/BranchProbabilityInfo.h" |
| 17 | #include "llvm/CodeGen/MachineBasicBlock.h" |
| 18 | #include "llvm/CodeGen/MachineFunction.h" |
| 19 | #include "llvm/CodeGen/TargetInstrInfo.h" |
| 20 | #include "llvm/CodeGen/TargetOpcodes.h" |
| 21 | #include "llvm/IR/DebugInfoMetadata.h" |
| 22 | #include "llvm/IR/Instruction.h" |
| 23 | #include "llvm/Support/Casting.h" |
| 24 | |
| 25 | #define DEBUG_TYPE "codegen-common" |
| 26 | |
| 27 | using namespace llvm; |
| 28 | |
| 29 | /// Add a successor MBB to ParentMBB< creating a new MachineBB for BB if SuccMBB |
| 30 | /// is 0. |
| 31 | MachineBasicBlock * |
| 32 | StackProtectorDescriptor::addSuccessorMBB( |
| 33 | const BasicBlock *BB, MachineBasicBlock *ParentMBB, bool IsLikely, |
| 34 | MachineBasicBlock *SuccMBB) { |
| 35 | // If SuccBB has not been created yet, create it. |
| 36 | if (!SuccMBB) { |
| 37 | MachineFunction *MF = ParentMBB->getParent(); |
| 38 | MachineFunction::iterator BBI(ParentMBB); |
| 39 | SuccMBB = MF->CreateMachineBasicBlock(BB); |
| 40 | MF->insert(MBBI: ++BBI, MBB: SuccMBB); |
| 41 | } |
| 42 | // Add it as a successor of ParentMBB. |
| 43 | ParentMBB->addSuccessor( |
| 44 | Succ: SuccMBB, Prob: BranchProbabilityInfo::getBranchProbStackProtector(IsLikely)); |
| 45 | return SuccMBB; |
| 46 | } |
| 47 | |
| 48 | /// Given that the input MI is before a partial terminator sequence TSeq, return |
| 49 | /// true if M + TSeq also a partial terminator sequence. |
| 50 | /// |
| 51 | /// A Terminator sequence is a sequence of MachineInstrs which at this point in |
| 52 | /// lowering copy vregs into physical registers, which are then passed into |
| 53 | /// terminator instructors so we can satisfy ABI constraints. A partial |
| 54 | /// terminator sequence is an improper subset of a terminator sequence (i.e. it |
| 55 | /// may be the whole terminator sequence). |
| 56 | static bool MIIsInTerminatorSequence(const MachineInstr &MI) { |
| 57 | // If we do not have a copy or an implicit def, we return true if and only if |
| 58 | // MI is a debug value. |
| 59 | if (!MI.isCopy() && !MI.isImplicitDef()) { |
| 60 | // Sometimes DBG_VALUE MI sneak in between the copies from the vregs to the |
| 61 | // physical registers if there is debug info associated with the terminator |
| 62 | // of our mbb. We want to include said debug info in our terminator |
| 63 | // sequence, so we return true in that case. |
| 64 | if (MI.isDebugInstr()) |
| 65 | return true; |
| 66 | |
| 67 | // For GlobalISel, we may have extension instructions for arguments within |
| 68 | // copy sequences. Allow these. |
| 69 | switch (MI.getOpcode()) { |
| 70 | case TargetOpcode::G_TRUNC: |
| 71 | case TargetOpcode::G_ZEXT: |
| 72 | case TargetOpcode::G_ANYEXT: |
| 73 | case TargetOpcode::G_SEXT: |
| 74 | case TargetOpcode::G_MERGE_VALUES: |
| 75 | case TargetOpcode::G_UNMERGE_VALUES: |
| 76 | case TargetOpcode::G_CONCAT_VECTORS: |
| 77 | case TargetOpcode::G_BUILD_VECTOR: |
| 78 | case TargetOpcode::G_EXTRACT: |
| 79 | return true; |
| 80 | default: |
| 81 | return false; |
| 82 | } |
| 83 | } |
| 84 | |
| 85 | // We have left the terminator sequence if we are not doing one of the |
| 86 | // following: |
| 87 | // |
| 88 | // 1. Copying a vreg into a physical register. |
| 89 | // 2. Copying a vreg into a vreg. |
| 90 | // 3. Defining a register via an implicit def. |
| 91 | |
| 92 | // OPI should always be a register definition... |
| 93 | MachineInstr::const_mop_iterator OPI = MI.operands_begin(); |
| 94 | if (!OPI->isReg() || !OPI->isDef()) |
| 95 | return false; |
| 96 | |
| 97 | // Defining any register via an implicit def is always ok. |
| 98 | if (MI.isImplicitDef()) |
| 99 | return true; |
| 100 | |
| 101 | // Grab the copy source... |
| 102 | MachineInstr::const_mop_iterator OPI2 = OPI; |
| 103 | ++OPI2; |
| 104 | assert(OPI2 != MI.operands_end() |
| 105 | && "Should have a copy implying we should have 2 arguments." ); |
| 106 | |
| 107 | // Make sure that the copy dest is not a vreg when the copy source is a |
| 108 | // physical register. |
| 109 | if (!OPI2->isReg() || |
| 110 | (!OPI->getReg().isPhysical() && OPI2->getReg().isPhysical())) |
| 111 | return false; |
| 112 | |
| 113 | return true; |
| 114 | } |
| 115 | |
| 116 | /// Find the split point at which to splice the end of BB into its success stack |
| 117 | /// protector check machine basic block. |
| 118 | /// |
| 119 | /// On many platforms, due to ABI constraints, terminators, even before register |
| 120 | /// allocation, use physical registers. This creates an issue for us since |
| 121 | /// physical registers at this point can not travel across basic |
| 122 | /// blocks. Luckily, selectiondag always moves physical registers into vregs |
| 123 | /// when they enter functions and moves them through a sequence of copies back |
| 124 | /// into the physical registers right before the terminator creating a |
| 125 | /// ``Terminator Sequence''. This function is searching for the beginning of the |
| 126 | /// terminator sequence so that we can ensure that we splice off not just the |
| 127 | /// terminator, but additionally the copies that move the vregs into the |
| 128 | /// physical registers. |
| 129 | MachineBasicBlock::iterator |
| 130 | llvm::findSplitPointForStackProtector(MachineBasicBlock *BB, |
| 131 | const TargetInstrInfo &TII) { |
| 132 | MachineBasicBlock::iterator SplitPoint = BB->getFirstTerminator(); |
| 133 | if (SplitPoint == BB->begin()) |
| 134 | return SplitPoint; |
| 135 | |
| 136 | MachineBasicBlock::iterator Start = BB->begin(); |
| 137 | MachineBasicBlock::iterator Previous = SplitPoint; |
| 138 | do { |
| 139 | --Previous; |
| 140 | } while (Previous != Start && Previous->isDebugInstr()); |
| 141 | |
| 142 | if (TII.isTailCall(Inst: *SplitPoint) && |
| 143 | Previous->getOpcode() == TII.getCallFrameDestroyOpcode()) { |
| 144 | // Call frames cannot be nested, so if this frame is describing the tail |
| 145 | // call itself, then we must insert before the sequence even starts. For |
| 146 | // example: |
| 147 | // <split point> |
| 148 | // ADJCALLSTACKDOWN ... |
| 149 | // <Moves> |
| 150 | // ADJCALLSTACKUP ... |
| 151 | // TAILJMP somewhere |
| 152 | // On the other hand, it could be an unrelated call in which case this tail |
| 153 | // call has no register moves of its own and should be the split point. For |
| 154 | // example: |
| 155 | // ADJCALLSTACKDOWN |
| 156 | // CALL something_else |
| 157 | // ADJCALLSTACKUP |
| 158 | // <split point> |
| 159 | // TAILJMP somewhere |
| 160 | do { |
| 161 | --Previous; |
| 162 | if (Previous->isCall()) |
| 163 | return SplitPoint; |
| 164 | } while(Previous->getOpcode() != TII.getCallFrameSetupOpcode()); |
| 165 | |
| 166 | return Previous; |
| 167 | } |
| 168 | |
| 169 | while (MIIsInTerminatorSequence(MI: *Previous)) { |
| 170 | SplitPoint = Previous; |
| 171 | if (Previous == Start) |
| 172 | break; |
| 173 | --Previous; |
| 174 | } |
| 175 | |
| 176 | return SplitPoint; |
| 177 | } |
| 178 | |
| 179 | FPClassTest llvm::invertFPClassTestIfSimpler(FPClassTest Test, bool UseFCmp) { |
| 180 | FPClassTest InvertedTest = ~Test; |
| 181 | |
| 182 | // Pick the direction with fewer tests |
| 183 | // TODO: Handle more combinations of cases that can be handled together |
| 184 | switch (static_cast<unsigned>(InvertedTest)) { |
| 185 | case fcNan: |
| 186 | case fcSNan: |
| 187 | case fcQNan: |
| 188 | case fcInf: |
| 189 | case fcPosInf: |
| 190 | case fcNegInf: |
| 191 | case fcNormal: |
| 192 | case fcPosNormal: |
| 193 | case fcNegNormal: |
| 194 | case fcSubnormal: |
| 195 | case fcPosSubnormal: |
| 196 | case fcNegSubnormal: |
| 197 | case fcZero: |
| 198 | case fcPosZero: |
| 199 | case fcNegZero: |
| 200 | case fcFinite: |
| 201 | case fcPosFinite: |
| 202 | case fcNegFinite: |
| 203 | case fcZero | fcNan: |
| 204 | case fcSubnormal | fcZero: |
| 205 | case fcSubnormal | fcZero | fcNan: |
| 206 | return InvertedTest; |
| 207 | case fcInf | fcNan: |
| 208 | case fcPosInf | fcNan: |
| 209 | case fcNegInf | fcNan: |
| 210 | // If we're trying to use fcmp, we can take advantage of the nan check |
| 211 | // behavior of the compare (but this is more instructions in the integer |
| 212 | // expansion). |
| 213 | return UseFCmp ? InvertedTest : fcNone; |
| 214 | default: |
| 215 | return fcNone; |
| 216 | } |
| 217 | |
| 218 | llvm_unreachable("covered FPClassTest" ); |
| 219 | } |
| 220 | |
| 221 | static MachineOperand *getSalvageOpsForCopy(const MachineRegisterInfo &MRI, |
| 222 | MachineInstr &Copy) { |
| 223 | assert((Copy.getOpcode() == TargetOpcode::COPY || |
| 224 | Copy.getOpcode() == TargetOpcode::G_BITCAST) && |
| 225 | "Must be a COPY or G_BITCAST" ); |
| 226 | |
| 227 | return &Copy.getOperand(i: 1); |
| 228 | } |
| 229 | |
| 230 | static MachineOperand *getSalvageOpsForTrunc(const MachineRegisterInfo &MRI, |
| 231 | MachineInstr &Trunc, |
| 232 | SmallVectorImpl<uint64_t> &Ops) { |
| 233 | assert(Trunc.getOpcode() == TargetOpcode::G_TRUNC && "Must be a G_TRUNC" ); |
| 234 | |
| 235 | const auto FromLLT = MRI.getType(Reg: Trunc.getOperand(i: 1).getReg()); |
| 236 | const auto ToLLT = MRI.getType(Reg: Trunc.defs().begin()->getReg()); |
| 237 | |
| 238 | // TODO: Support non-scalar types. |
| 239 | if (!FromLLT.isScalar()) { |
| 240 | return nullptr; |
| 241 | } |
| 242 | |
| 243 | auto ExtOps = DIExpression::getExtOps(FromSize: FromLLT.getSizeInBits(), |
| 244 | ToSize: ToLLT.getSizeInBits(), Signed: false); |
| 245 | Ops.append(in_start: ExtOps.begin(), in_end: ExtOps.end()); |
| 246 | return &Trunc.getOperand(i: 1); |
| 247 | } |
| 248 | |
| 249 | static MachineOperand *salvageDebugInfoImpl(const MachineRegisterInfo &MRI, |
| 250 | MachineInstr &MI, |
| 251 | SmallVectorImpl<uint64_t> &Ops) { |
| 252 | switch (MI.getOpcode()) { |
| 253 | case TargetOpcode::G_TRUNC: |
| 254 | return getSalvageOpsForTrunc(MRI, Trunc&: MI, Ops); |
| 255 | case TargetOpcode::COPY: |
| 256 | case TargetOpcode::G_BITCAST: |
| 257 | return getSalvageOpsForCopy(MRI, Copy&: MI); |
| 258 | default: |
| 259 | return nullptr; |
| 260 | } |
| 261 | } |
| 262 | |
| 263 | /// Replace \p DbgMI, which describes the result of \p BuildVector, with one |
| 264 | /// fragment debug value per vector element. |
| 265 | static void salvageBuildVector(const MachineRegisterInfo &MRI, |
| 266 | MachineInstr &BuildVector, MachineInstr &DbgMI) { |
| 267 | const DIExpression *Expr = DbgMI.getDebugExpression(); |
| 268 | if (DbgMI.getNumDebugOperands() != 1 || !Expr->isSingleLocationExpression() || |
| 269 | Expr->isComplex()) |
| 270 | return; |
| 271 | |
| 272 | unsigned VecSize = MRI.getType(Reg: BuildVector.getOperand(i: 0).getReg()) |
| 273 | .getSizeInBits() |
| 274 | .getFixedValue(); |
| 275 | if (auto Fragment = Expr->getFragmentInfo()) { |
| 276 | if (VecSize > Fragment->SizeInBits) |
| 277 | return; |
| 278 | } else if (auto VarSize = DbgMI.getDebugVariable()->getSizeInBits()) { |
| 279 | if (VecSize > *VarSize) |
| 280 | return; |
| 281 | } |
| 282 | |
| 283 | unsigned NumElts = BuildVector.getNumOperands() - 1; |
| 284 | unsigned EltSize = VecSize / NumElts; |
| 285 | SmallVector<DIExpression *, 8> FragExprs; |
| 286 | for (unsigned I = 0; I != NumElts; ++I) { |
| 287 | auto FragExpr = |
| 288 | DIExpression::createFragmentExpression(Expr, OffsetInBits: I * EltSize, SizeInBits: EltSize); |
| 289 | if (!FragExpr) |
| 290 | return; |
| 291 | FragExprs.push_back(Elt: *FragExpr); |
| 292 | } |
| 293 | |
| 294 | MachineBasicBlock &MBB = *DbgMI.getParent(); |
| 295 | MachineFunction &MF = *MBB.getParent(); |
| 296 | for (unsigned I = NumElts - 1; I != 0; --I) { |
| 297 | MachineInstr *NewMI = MF.CloneMachineInstr(Orig: &DbgMI); |
| 298 | NewMI->getDebugOperand(Index: 0).setReg(BuildVector.getOperand(i: I + 1).getReg()); |
| 299 | NewMI->getDebugExpressionOp().setMetadata(FragExprs[I]); |
| 300 | MBB.insertAfter(I: DbgMI.getIterator(), MI: NewMI); |
| 301 | LLVM_DEBUG(dbgs() << "SALVAGE: " << *NewMI << '\n'); |
| 302 | } |
| 303 | DbgMI.getDebugOperand(Index: 0).setReg(BuildVector.getOperand(i: 1).getReg()); |
| 304 | DbgMI.getDebugExpressionOp().setMetadata(FragExprs[0]); |
| 305 | LLVM_DEBUG(dbgs() << "SALVAGE: " << DbgMI << '\n'); |
| 306 | } |
| 307 | |
| 308 | void llvm::salvageDebugInfoForDbgValue(const MachineRegisterInfo &MRI, |
| 309 | MachineInstr &MI, |
| 310 | ArrayRef<MachineOperand *> DbgUsers) { |
| 311 | // These are arbitrary chosen limits on the maximum number of values and the |
| 312 | // maximum size of a debug expression we can salvage up to, used for |
| 313 | // performance reasons. |
| 314 | const unsigned MaxExpressionSize = 128; |
| 315 | |
| 316 | SmallPtrSet<MachineInstr *, 4> Visited; |
| 317 | for (auto *DefMO : DbgUsers) { |
| 318 | MachineInstr *DbgMI = DefMO->getParent(); |
| 319 | // A DBG_VALUE_LIST may use the salvaged register in several location |
| 320 | // operands; all of them are rewritten the first time it is seen. |
| 321 | if (!Visited.insert(Ptr: DbgMI).second) |
| 322 | continue; |
| 323 | if (DbgMI->isIndirectDebugValue()) { |
| 324 | continue; |
| 325 | } |
| 326 | |
| 327 | Register Reg = DefMO->getReg(); |
| 328 | assert(DbgMI->hasDebugOperandForReg(Reg) && |
| 329 | "Must use salvaged instruction as its location" ); |
| 330 | |
| 331 | if (MI.getOpcode() == TargetOpcode::G_BUILD_VECTOR) { |
| 332 | assert(DbgMI->isDebugValue() && |
| 333 | "Must be either DBG_VALUE or DBG_VALUE_LIST" ); |
| 334 | salvageBuildVector(MRI, BuildVector&: MI, DbgMI&: *DbgMI); |
| 335 | continue; |
| 336 | } |
| 337 | |
| 338 | const DIExpression *SalvagedExpr = DbgMI->getDebugExpression(); |
| 339 | |
| 340 | SmallVector<uint64_t, 16> Ops; |
| 341 | auto Op0 = salvageDebugInfoImpl(MRI, MI, Ops); |
| 342 | if (!Op0) |
| 343 | continue; |
| 344 | |
| 345 | SmallVector<MachineOperand *, 2> LocMOs( |
| 346 | make_pointer_range(Range: DbgMI->getDebugOperandsForReg(Reg))); |
| 347 | for (MachineOperand *LocMO : LocMOs) |
| 348 | SalvagedExpr = DIExpression::appendOpsToArg( |
| 349 | Expr: SalvagedExpr, Ops, ArgNo: DbgMI->getDebugOperandIndex(Op: LocMO), StackValue: true); |
| 350 | |
| 351 | bool IsValidSalvageExpr = |
| 352 | SalvagedExpr->getNumElements() <= MaxExpressionSize; |
| 353 | if (IsValidSalvageExpr) { |
| 354 | for (MachineOperand *LocMO : LocMOs) { |
| 355 | LocMO->setReg(Op0->getReg()); |
| 356 | LocMO->setSubReg(Op0->getSubReg()); |
| 357 | } |
| 358 | DbgMI->getDebugExpressionOp().setMetadata(SalvagedExpr); |
| 359 | |
| 360 | LLVM_DEBUG(dbgs() << "SALVAGE: " << *DbgMI << '\n'); |
| 361 | } |
| 362 | } |
| 363 | } |
| 364 | |