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
27using namespace llvm;
28
29/// Add a successor MBB to ParentMBB< creating a new MachineBB for BB if SuccMBB
30/// is 0.
31MachineBasicBlock *
32StackProtectorDescriptor::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).
56static 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.
129MachineBasicBlock::iterator
130llvm::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
179FPClassTest 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
221static 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
230static 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
249static 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.
265static 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
308void 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