1//===- llvm/CodeGen/GlobalISel/IRTranslator.cpp - IRTranslator ---*- 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/// \file
9/// This file implements the IRTranslator class.
10//===----------------------------------------------------------------------===//
11
12#include "llvm/CodeGen/GlobalISel/IRTranslator.h"
13#include "llvm/ADT/PostOrderIterator.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/ScopeExit.h"
16#include "llvm/ADT/SmallSet.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/Analysis/BranchProbabilityInfo.h"
19#include "llvm/Analysis/Loads.h"
20#include "llvm/Analysis/OptimizationRemarkEmitter.h"
21#include "llvm/Analysis/ValueTracking.h"
22#include "llvm/CodeGen/Analysis.h"
23#include "llvm/CodeGen/GlobalISel/CallLowering.h"
24#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
25#include "llvm/CodeGen/GlobalISel/InlineAsmLowering.h"
26#include "llvm/CodeGen/LowLevelType.h"
27#include "llvm/CodeGen/MachineBasicBlock.h"
28#include "llvm/CodeGen/MachineFrameInfo.h"
29#include "llvm/CodeGen/MachineFunction.h"
30#include "llvm/CodeGen/MachineInstrBuilder.h"
31#include "llvm/CodeGen/MachineMemOperand.h"
32#include "llvm/CodeGen/MachineModuleInfo.h"
33#include "llvm/CodeGen/MachineOperand.h"
34#include "llvm/CodeGen/MachineRegisterInfo.h"
35#include "llvm/CodeGen/StackProtector.h"
36#include "llvm/CodeGen/SwitchLoweringUtils.h"
37#include "llvm/CodeGen/TargetFrameLowering.h"
38#include "llvm/CodeGen/TargetInstrInfo.h"
39#include "llvm/CodeGen/TargetLowering.h"
40#include "llvm/CodeGen/TargetPassConfig.h"
41#include "llvm/CodeGen/TargetRegisterInfo.h"
42#include "llvm/CodeGen/TargetSubtargetInfo.h"
43#include "llvm/IR/BasicBlock.h"
44#include "llvm/IR/CFG.h"
45#include "llvm/IR/Constant.h"
46#include "llvm/IR/Constants.h"
47#include "llvm/IR/DataLayout.h"
48#include "llvm/IR/DebugInfo.h"
49#include "llvm/IR/DerivedTypes.h"
50#include "llvm/IR/Function.h"
51#include "llvm/IR/GetElementPtrTypeIterator.h"
52#include "llvm/IR/InlineAsm.h"
53#include "llvm/IR/InstrTypes.h"
54#include "llvm/IR/Instructions.h"
55#include "llvm/IR/IntrinsicInst.h"
56#include "llvm/IR/Intrinsics.h"
57#include "llvm/IR/LLVMContext.h"
58#include "llvm/IR/Metadata.h"
59#include "llvm/IR/PatternMatch.h"
60#include "llvm/IR/Type.h"
61#include "llvm/IR/User.h"
62#include "llvm/IR/Value.h"
63#include "llvm/InitializePasses.h"
64#include "llvm/MC/MCContext.h"
65#include "llvm/Pass.h"
66#include "llvm/Support/Casting.h"
67#include "llvm/Support/CodeGen.h"
68#include "llvm/Support/Debug.h"
69#include "llvm/Support/ErrorHandling.h"
70#include "llvm/Support/LowLevelTypeImpl.h"
71#include "llvm/Support/MathExtras.h"
72#include "llvm/Support/raw_ostream.h"
73#include "llvm/Target/TargetIntrinsicInfo.h"
74#include "llvm/Target/TargetMachine.h"
75#include <algorithm>
76#include <cassert>
77#include <cstddef>
78#include <cstdint>
79#include <iterator>
80#include <string>
81#include <utility>
82#include <vector>
83
84#define DEBUG_TYPE "irtranslator"
85
86using namespace llvm;
87
88static cl::opt<bool>
89 EnableCSEInIRTranslator("enable-cse-in-irtranslator",
90 cl::desc("Should enable CSE in irtranslator"),
91 cl::Optional, cl::init(false));
92char IRTranslator::ID = 0;
93
94INITIALIZE_PASS_BEGIN(IRTranslator, DEBUG_TYPE, "IRTranslator LLVM IR -> MI",
95 false, false)
96INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
97INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
98INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
99INITIALIZE_PASS_DEPENDENCY(StackProtector)
100INITIALIZE_PASS_END(IRTranslator, DEBUG_TYPE, "IRTranslator LLVM IR -> MI",
101 false, false)
102
103static void reportTranslationError(MachineFunction &MF,
104 const TargetPassConfig &TPC,
105 OptimizationRemarkEmitter &ORE,
106 OptimizationRemarkMissed &R) {
107 MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
108
109 // Print the function name explicitly if we don't have a debug location (which
110 // makes the diagnostic less useful) or if we're going to emit a raw error.
111 if (!R.getLocation().isValid() || TPC.isGlobalISelAbortEnabled())
112 R << (" (in function: " + MF.getName() + ")").str();
113
114 if (TPC.isGlobalISelAbortEnabled())
115 report_fatal_error(R.getMsg());
116 else
117 ORE.emit(R);
118}
119
120IRTranslator::IRTranslator(CodeGenOpt::Level optlevel)
121 : MachineFunctionPass(ID), OptLevel(optlevel) {}
122
123#ifndef NDEBUG
124namespace {
125/// Verify that every instruction created has the same DILocation as the
126/// instruction being translated.
127class DILocationVerifier : public GISelChangeObserver {
128 const Instruction *CurrInst = nullptr;
129
130public:
131 DILocationVerifier() = default;
132 ~DILocationVerifier() = default;
133
134 const Instruction *getCurrentInst() const { return CurrInst; }
135 void setCurrentInst(const Instruction *Inst) { CurrInst = Inst; }
136
137 void erasingInstr(MachineInstr &MI) override {}
138 void changingInstr(MachineInstr &MI) override {}
139 void changedInstr(MachineInstr &MI) override {}
140
141 void createdInstr(MachineInstr &MI) override {
142 assert(getCurrentInst() && "Inserted instruction without a current MI");
143
144 // Only print the check message if we're actually checking it.
145#ifndef NDEBUG
146 LLVM_DEBUG(dbgs() << "Checking DILocation from " << *CurrInst
147 << " was copied to " << MI);
148#endif
149 // We allow insts in the entry block to have a debug loc line of 0 because
150 // they could have originated from constants, and we don't want a jumpy
151 // debug experience.
152 assert((CurrInst->getDebugLoc() == MI.getDebugLoc() ||
153 MI.getDebugLoc().getLine() == 0) &&
154 "Line info was not transferred to all instructions");
155 }
156};
157} // namespace
158#endif // ifndef NDEBUG
159
160
161void IRTranslator::getAnalysisUsage(AnalysisUsage &AU) const {
162 AU.addRequired<StackProtector>();
163 AU.addRequired<TargetPassConfig>();
164 AU.addRequired<GISelCSEAnalysisWrapperPass>();
165 if (OptLevel != CodeGenOpt::None)
166 AU.addRequired<BranchProbabilityInfoWrapperPass>();
167 getSelectionDAGFallbackAnalysisUsage(AU);
168 MachineFunctionPass::getAnalysisUsage(AU);
169}
170
171IRTranslator::ValueToVRegInfo::VRegListT &
172IRTranslator::allocateVRegs(const Value &Val) {
173 auto VRegsIt = VMap.findVRegs(Val);
174 if (VRegsIt != VMap.vregs_end())
175 return *VRegsIt->second;
176 auto *Regs = VMap.getVRegs(Val);
177 auto *Offsets = VMap.getOffsets(Val);
178 SmallVector<LLT, 4> SplitTys;
179 computeValueLLTs(*DL, *Val.getType(), SplitTys,
180 Offsets->empty() ? Offsets : nullptr);
181 for (unsigned i = 0; i < SplitTys.size(); ++i)
182 Regs->push_back(0);
183 return *Regs;
184}
185
186ArrayRef<Register> IRTranslator::getOrCreateVRegs(const Value &Val) {
187 auto VRegsIt = VMap.findVRegs(Val);
188 if (VRegsIt != VMap.vregs_end())
189 return *VRegsIt->second;
190
191 if (Val.getType()->isVoidTy())
192 return *VMap.getVRegs(Val);
193
194 // Create entry for this type.
195 auto *VRegs = VMap.getVRegs(Val);
196 auto *Offsets = VMap.getOffsets(Val);
197
198 assert(Val.getType()->isSized() &&
199 "Don't know how to create an empty vreg");
200
201 SmallVector<LLT, 4> SplitTys;
202 computeValueLLTs(*DL, *Val.getType(), SplitTys,
203 Offsets->empty() ? Offsets : nullptr);
204
205 if (!isa<Constant>(Val)) {
206 for (auto Ty : SplitTys)
207 VRegs->push_back(MRI->createGenericVirtualRegister(Ty));
208 return *VRegs;
209 }
210
211 if (Val.getType()->isAggregateType()) {
212 // UndefValue, ConstantAggregateZero
213 auto &C = cast<Constant>(Val);
214 unsigned Idx = 0;
215 while (auto Elt = C.getAggregateElement(Idx++)) {
216 auto EltRegs = getOrCreateVRegs(*Elt);
217 llvm::copy(EltRegs, std::back_inserter(*VRegs));
218 }
219 } else {
220 assert(SplitTys.size() == 1 && "unexpectedly split LLT");
221 VRegs->push_back(MRI->createGenericVirtualRegister(SplitTys[0]));
222 bool Success = translate(cast<Constant>(Val), VRegs->front());
223 if (!Success) {
224 OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
225 MF->getFunction().getSubprogram(),
226 &MF->getFunction().getEntryBlock());
227 R << "unable to translate constant: " << ore::NV("Type", Val.getType());
228 reportTranslationError(*MF, *TPC, *ORE, R);
229 return *VRegs;
230 }
231 }
232
233 return *VRegs;
234}
235
236int IRTranslator::getOrCreateFrameIndex(const AllocaInst &AI) {
237 auto MapEntry = FrameIndices.find(&AI);
238 if (MapEntry != FrameIndices.end())
239 return MapEntry->second;
240
241 uint64_t ElementSize = DL->getTypeAllocSize(AI.getAllocatedType());
242 uint64_t Size =
243 ElementSize * cast<ConstantInt>(AI.getArraySize())->getZExtValue();
244
245 // Always allocate at least one byte.
246 Size = std::max<uint64_t>(Size, 1u);
247
248 int &FI = FrameIndices[&AI];
249 FI = MF->getFrameInfo().CreateStackObject(Size, AI.getAlign(), false, &AI);
250 return FI;
251}
252
253Align IRTranslator::getMemOpAlign(const Instruction &I) {
254 if (const StoreInst *SI = dyn_cast<StoreInst>(&I))
255 return SI->getAlign();
256 if (const LoadInst *LI = dyn_cast<LoadInst>(&I))
257 return LI->getAlign();
258 if (const AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I))
259 return AI->getAlign();
260 if (const AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I))
261 return AI->getAlign();
262
263 OptimizationRemarkMissed R("gisel-irtranslator", "", &I);
264 R << "unable to translate memop: " << ore::NV("Opcode", &I);
265 reportTranslationError(*MF, *TPC, *ORE, R);
266 return Align(1);
267}
268
269MachineBasicBlock &IRTranslator::getMBB(const BasicBlock &BB) {
270 MachineBasicBlock *&MBB = BBToMBB[&BB];
271 assert(MBB && "BasicBlock was not encountered before");
272 return *MBB;
273}
274
275void IRTranslator::addMachineCFGPred(CFGEdge Edge, MachineBasicBlock *NewPred) {
276 assert(NewPred && "new predecessor must be a real MachineBasicBlock");
277 MachinePreds[Edge].push_back(NewPred);
278}
279
280bool IRTranslator::translateBinaryOp(unsigned Opcode, const User &U,
281 MachineIRBuilder &MIRBuilder) {
282 // Get or create a virtual register for each value.
283 // Unless the value is a Constant => loadimm cst?
284 // or inline constant each time?
285 // Creation of a virtual register needs to have a size.
286 Register Op0 = getOrCreateVReg(*U.getOperand(0));
287 Register Op1 = getOrCreateVReg(*U.getOperand(1));
288 Register Res = getOrCreateVReg(U);
289 uint16_t Flags = 0;
290 if (isa<Instruction>(U)) {
291 const Instruction &I = cast<Instruction>(U);
292 Flags = MachineInstr::copyFlagsFromInstruction(I);
293 }
294
295 MIRBuilder.buildInstr(Opcode, {Res}, {Op0, Op1}, Flags);
296 return true;
297}
298
299bool IRTranslator::translateUnaryOp(unsigned Opcode, const User &U,
300 MachineIRBuilder &MIRBuilder) {
301 Register Op0 = getOrCreateVReg(*U.getOperand(0));
302 Register Res = getOrCreateVReg(U);
303 uint16_t Flags = 0;
304 if (isa<Instruction>(U)) {
305 const Instruction &I = cast<Instruction>(U);
306 Flags = MachineInstr::copyFlagsFromInstruction(I);
307 }
308 MIRBuilder.buildInstr(Opcode, {Res}, {Op0}, Flags);
309 return true;
310}
311
312bool IRTranslator::translateFNeg(const User &U, MachineIRBuilder &MIRBuilder) {
313 return translateUnaryOp(TargetOpcode::G_FNEG, U, MIRBuilder);
314}
315
316bool IRTranslator::translateCompare(const User &U,
317 MachineIRBuilder &MIRBuilder) {
318 auto *CI = dyn_cast<CmpInst>(&U);
319 Register Op0 = getOrCreateVReg(*U.getOperand(0));
320 Register Op1 = getOrCreateVReg(*U.getOperand(1));
321 Register Res = getOrCreateVReg(U);
322 CmpInst::Predicate Pred =
323 CI ? CI->getPredicate() : static_cast<CmpInst::Predicate>(
324 cast<ConstantExpr>(U).getPredicate());
325 if (CmpInst::isIntPredicate(Pred))
326 MIRBuilder.buildICmp(Pred, Res, Op0, Op1);
327 else if (Pred == CmpInst::FCMP_FALSE)
328 MIRBuilder.buildCopy(
329 Res, getOrCreateVReg(*Constant::getNullValue(U.getType())));
330 else if (Pred == CmpInst::FCMP_TRUE)
331 MIRBuilder.buildCopy(
332 Res, getOrCreateVReg(*Constant::getAllOnesValue(U.getType())));
333 else {
334 assert(CI && "Instruction should be CmpInst");
335 MIRBuilder.buildFCmp(Pred, Res, Op0, Op1,
336 MachineInstr::copyFlagsFromInstruction(*CI));
337 }
338
339 return true;
340}
341
342bool IRTranslator::translateRet(const User &U, MachineIRBuilder &MIRBuilder) {
343 const ReturnInst &RI = cast<ReturnInst>(U);
344 const Value *Ret = RI.getReturnValue();
345 if (Ret && DL->getTypeStoreSize(Ret->getType()) == 0)
346 Ret = nullptr;
347
348 ArrayRef<Register> VRegs;
349 if (Ret)
350 VRegs = getOrCreateVRegs(*Ret);
351
352 Register SwiftErrorVReg = 0;
353 if (CLI->supportSwiftError() && SwiftError.getFunctionArg()) {
354 SwiftErrorVReg = SwiftError.getOrCreateVRegUseAt(
355 &RI, &MIRBuilder.getMBB(), SwiftError.getFunctionArg());
356 }
357
358 // The target may mess up with the insertion point, but
359 // this is not important as a return is the last instruction
360 // of the block anyway.
361 return CLI->lowerReturn(MIRBuilder, Ret, VRegs, FuncInfo, SwiftErrorVReg);
362}
363
364void IRTranslator::emitBranchForMergedCondition(
365 const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB,
366 MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB,
367 BranchProbability TProb, BranchProbability FProb, bool InvertCond) {
368 // If the leaf of the tree is a comparison, merge the condition into
369 // the caseblock.
370 if (const CmpInst *BOp = dyn_cast<CmpInst>(Cond)) {
371 CmpInst::Predicate Condition;
372 if (const ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
373 Condition = InvertCond ? IC->getInversePredicate() : IC->getPredicate();
374 } else {
375 const FCmpInst *FC = cast<FCmpInst>(Cond);
376 Condition = InvertCond ? FC->getInversePredicate() : FC->getPredicate();
377 }
378
379 SwitchCG::CaseBlock CB(Condition, false, BOp->getOperand(0),
380 BOp->getOperand(1), nullptr, TBB, FBB, CurBB,
381 CurBuilder->getDebugLoc(), TProb, FProb);
382 SL->SwitchCases.push_back(CB);
383 return;
384 }
385
386 // Create a CaseBlock record representing this branch.
387 CmpInst::Predicate Pred = InvertCond ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ;
388 SwitchCG::CaseBlock CB(
389 Pred, false, Cond, ConstantInt::getTrue(MF->getFunction().getContext()),
390 nullptr, TBB, FBB, CurBB, CurBuilder->getDebugLoc(), TProb, FProb);
391 SL->SwitchCases.push_back(CB);
392}
393
394static bool isValInBlock(const Value *V, const BasicBlock *BB) {
395 if (const Instruction *I = dyn_cast<Instruction>(V))
396 return I->getParent() == BB;
397 return true;
398}
399
400void IRTranslator::findMergedConditions(
401 const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB,
402 MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB,
403 Instruction::BinaryOps Opc, BranchProbability TProb,
404 BranchProbability FProb, bool InvertCond) {
405 using namespace PatternMatch;
406 assert((Opc == Instruction::And || Opc == Instruction::Or) &&
407 "Expected Opc to be AND/OR");
408 // Skip over not part of the tree and remember to invert op and operands at
409 // next level.
410 Value *NotCond;
411 if (match(Cond, m_OneUse(m_Not(m_Value(NotCond)))) &&
412 isValInBlock(NotCond, CurBB->getBasicBlock())) {
413 findMergedConditions(NotCond, TBB, FBB, CurBB, SwitchBB, Opc, TProb, FProb,
414 !InvertCond);
415 return;
416 }
417
418 const Instruction *BOp = dyn_cast<Instruction>(Cond);
419 const Value *BOpOp0, *BOpOp1;
420 // Compute the effective opcode for Cond, taking into account whether it needs
421 // to be inverted, e.g.
422 // and (not (or A, B)), C
423 // gets lowered as
424 // and (and (not A, not B), C)
425 Instruction::BinaryOps BOpc = (Instruction::BinaryOps)0;
426 if (BOp) {
427 BOpc = match(BOp, m_LogicalAnd(m_Value(BOpOp0), m_Value(BOpOp1)))
428 ? Instruction::And
429 : (match(BOp, m_LogicalOr(m_Value(BOpOp0), m_Value(BOpOp1)))
430 ? Instruction::Or
431 : (Instruction::BinaryOps)0);
432 if (InvertCond) {
433 if (BOpc == Instruction::And)
434 BOpc = Instruction::Or;
435 else if (BOpc == Instruction::Or)
436 BOpc = Instruction::And;
437 }
438 }
439
440 // If this node is not part of the or/and tree, emit it as a branch.
441 // Note that all nodes in the tree should have same opcode.
442 bool BOpIsInOrAndTree = BOpc && BOpc == Opc && BOp->hasOneUse();
443 if (!BOpIsInOrAndTree || BOp->getParent() != CurBB->getBasicBlock() ||
444 !isValInBlock(BOpOp0, CurBB->getBasicBlock()) ||
445 !isValInBlock(BOpOp1, CurBB->getBasicBlock())) {
446 emitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB, TProb, FProb,
447 InvertCond);
448 return;
449 }
450
451 // Create TmpBB after CurBB.
452 MachineFunction::iterator BBI(CurBB);
453 MachineBasicBlock *TmpBB =
454 MF->CreateMachineBasicBlock(CurBB->getBasicBlock());
455 CurBB->getParent()->insert(++BBI, TmpBB);
456
457 if (Opc == Instruction::Or) {
458 // Codegen X | Y as:
459 // BB1:
460 // jmp_if_X TBB
461 // jmp TmpBB
462 // TmpBB:
463 // jmp_if_Y TBB
464 // jmp FBB
465 //
466
467 // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
468 // The requirement is that
469 // TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB)
470 // = TrueProb for original BB.
471 // Assuming the original probabilities are A and B, one choice is to set
472 // BB1's probabilities to A/2 and A/2+B, and set TmpBB's probabilities to
473 // A/(1+B) and 2B/(1+B). This choice assumes that
474 // TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB.
475 // Another choice is to assume TrueProb for BB1 equals to TrueProb for
476 // TmpBB, but the math is more complicated.
477
478 auto NewTrueProb = TProb / 2;
479 auto NewFalseProb = TProb / 2 + FProb;
480 // Emit the LHS condition.
481 findMergedConditions(BOpOp0, TBB, TmpBB, CurBB, SwitchBB, Opc, NewTrueProb,
482 NewFalseProb, InvertCond);
483
484 // Normalize A/2 and B to get A/(1+B) and 2B/(1+B).
485 SmallVector<BranchProbability, 2> Probs{TProb / 2, FProb};
486 BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
487 // Emit the RHS condition into TmpBB.
488 findMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0],
489 Probs[1], InvertCond);
490 } else {
491 assert(Opc == Instruction::And && "Unknown merge op!");
492 // Codegen X & Y as:
493 // BB1:
494 // jmp_if_X TmpBB
495 // jmp FBB
496 // TmpBB:
497 // jmp_if_Y TBB
498 // jmp FBB
499 //
500 // This requires creation of TmpBB after CurBB.
501
502 // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
503 // The requirement is that
504 // FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB)
505 // = FalseProb for original BB.
506 // Assuming the original probabilities are A and B, one choice is to set
507 // BB1's probabilities to A+B/2 and B/2, and set TmpBB's probabilities to
508 // 2A/(1+A) and B/(1+A). This choice assumes that FalseProb for BB1 ==
509 // TrueProb for BB1 * FalseProb for TmpBB.
510
511 auto NewTrueProb = TProb + FProb / 2;
512 auto NewFalseProb = FProb / 2;
513 // Emit the LHS condition.
514 findMergedConditions(BOpOp0, TmpBB, FBB, CurBB, SwitchBB, Opc, NewTrueProb,
515 NewFalseProb, InvertCond);
516
517 // Normalize A and B/2 to get 2A/(1+A) and B/(1+A).
518 SmallVector<BranchProbability, 2> Probs{TProb, FProb / 2};
519 BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
520 // Emit the RHS condition into TmpBB.
521 findMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0],
522 Probs[1], InvertCond);
523 }
524}
525
526bool IRTranslator::shouldEmitAsBranches(
527 const std::vector<SwitchCG::CaseBlock> &Cases) {
528 // For multiple cases, it's better to emit as branches.
529 if (Cases.size() != 2)
530 return true;
531
532 // If this is two comparisons of the same values or'd or and'd together, they
533 // will get folded into a single comparison, so don't emit two blocks.
534 if ((Cases[0].CmpLHS == Cases[1].CmpLHS &&
535 Cases[0].CmpRHS == Cases[1].CmpRHS) ||
536 (Cases[0].CmpRHS == Cases[1].CmpLHS &&
537 Cases[0].CmpLHS == Cases[1].CmpRHS)) {
538 return false;
539 }
540
541 // Handle: (X != null) | (Y != null) --> (X|Y) != 0
542 // Handle: (X == null) & (Y == null) --> (X|Y) == 0
543 if (Cases[0].CmpRHS == Cases[1].CmpRHS &&
544 Cases[0].PredInfo.Pred == Cases[1].PredInfo.Pred &&
545 isa<Constant>(Cases[0].CmpRHS) &&
546 cast<Constant>(Cases[0].CmpRHS)->isNullValue()) {
547 if (Cases[0].PredInfo.Pred == CmpInst::ICMP_EQ &&
548 Cases[0].TrueBB == Cases[1].ThisBB)
549 return false;
550 if (Cases[0].PredInfo.Pred == CmpInst::ICMP_NE &&
551 Cases[0].FalseBB == Cases[1].ThisBB)
552 return false;
553 }
554
555 return true;
556}
557
558bool IRTranslator::translateBr(const User &U, MachineIRBuilder &MIRBuilder) {
559 const BranchInst &BrInst = cast<BranchInst>(U);
560 auto &CurMBB = MIRBuilder.getMBB();
561 auto *Succ0MBB = &getMBB(*BrInst.getSuccessor(0));
562
563 if (BrInst.isUnconditional()) {
564 // If the unconditional target is the layout successor, fallthrough.
565 if (!CurMBB.isLayoutSuccessor(Succ0MBB))
566 MIRBuilder.buildBr(*Succ0MBB);
567
568 // Link successors.
569 for (const BasicBlock *Succ : successors(&BrInst))
570 CurMBB.addSuccessor(&getMBB(*Succ));
571 return true;
572 }
573
574 // If this condition is one of the special cases we handle, do special stuff
575 // now.
576 const Value *CondVal = BrInst.getCondition();
577 MachineBasicBlock *Succ1MBB = &getMBB(*BrInst.getSuccessor(1));
578
579 const auto &TLI = *MF->getSubtarget().getTargetLowering();
580
581 // If this is a series of conditions that are or'd or and'd together, emit
582 // this as a sequence of branches instead of setcc's with and/or operations.
583 // As long as jumps are not expensive (exceptions for multi-use logic ops,
584 // unpredictable branches, and vector extracts because those jumps are likely
585 // expensive for any target), this should improve performance.
586 // For example, instead of something like:
587 // cmp A, B
588 // C = seteq
589 // cmp D, E
590 // F = setle
591 // or C, F
592 // jnz foo
593 // Emit:
594 // cmp A, B
595 // je foo
596 // cmp D, E
597 // jle foo
598 using namespace PatternMatch;
599 const Instruction *CondI = dyn_cast<Instruction>(CondVal);
600 if (!TLI.isJumpExpensive() && CondI && CondI->hasOneUse() &&
601 !BrInst.hasMetadata(LLVMContext::MD_unpredictable)) {
602 Instruction::BinaryOps Opcode = (Instruction::BinaryOps)0;
603 Value *Vec;
604 const Value *BOp0, *BOp1;
605 if (match(CondI, m_LogicalAnd(m_Value(BOp0), m_Value(BOp1))))
606 Opcode = Instruction::And;
607 else if (match(CondI, m_LogicalOr(m_Value(BOp0), m_Value(BOp1))))
608 Opcode = Instruction::Or;
609
610 if (Opcode && !(match(BOp0, m_ExtractElt(m_Value(Vec), m_Value())) &&
611 match(BOp1, m_ExtractElt(m_Specific(Vec), m_Value())))) {
612 findMergedConditions(CondI, Succ0MBB, Succ1MBB, &CurMBB, &CurMBB, Opcode,
613 getEdgeProbability(&CurMBB, Succ0MBB),
614 getEdgeProbability(&CurMBB, Succ1MBB),
615 /*InvertCond=*/false);
616 assert(SL->SwitchCases[0].ThisBB == &CurMBB && "Unexpected lowering!");
617
618 // Allow some cases to be rejected.
619 if (shouldEmitAsBranches(SL->SwitchCases)) {
620 // Emit the branch for this block.
621 emitSwitchCase(SL->SwitchCases[0], &CurMBB, *CurBuilder);
622 SL->SwitchCases.erase(SL->SwitchCases.begin());
623 return true;
624 }
625
626 // Okay, we decided not to do this, remove any inserted MBB's and clear
627 // SwitchCases.
628 for (unsigned I = 1, E = SL->SwitchCases.size(); I != E; ++I)
629 MF->erase(SL->SwitchCases[I].ThisBB);
630
631 SL->SwitchCases.clear();
632 }
633 }
634
635 // Create a CaseBlock record representing this branch.
636 SwitchCG::CaseBlock CB(CmpInst::ICMP_EQ, false, CondVal,
637 ConstantInt::getTrue(MF->getFunction().getContext()),
638 nullptr, Succ0MBB, Succ1MBB, &CurMBB,
639 CurBuilder->getDebugLoc());
640
641 // Use emitSwitchCase to actually insert the fast branch sequence for this
642 // cond branch.
643 emitSwitchCase(CB, &CurMBB, *CurBuilder);
644 return true;
645}
646
647void IRTranslator::addSuccessorWithProb(MachineBasicBlock *Src,
648 MachineBasicBlock *Dst,
649 BranchProbability Prob) {
650 if (!FuncInfo.BPI) {
651 Src->addSuccessorWithoutProb(Dst);
652 return;
653 }
654 if (Prob.isUnknown())
655 Prob = getEdgeProbability(Src, Dst);
656 Src->addSuccessor(Dst, Prob);
657}
658
659BranchProbability
660IRTranslator::getEdgeProbability(const MachineBasicBlock *Src,
661 const MachineBasicBlock *Dst) const {
662 const BasicBlock *SrcBB = Src->getBasicBlock();
663 const BasicBlock *DstBB = Dst->getBasicBlock();
664 if (!FuncInfo.BPI) {
665 // If BPI is not available, set the default probability as 1 / N, where N is
666 // the number of successors.
667 auto SuccSize = std::max<uint32_t>(succ_size(SrcBB), 1);
668 return BranchProbability(1, SuccSize);
669 }
670 return FuncInfo.BPI->getEdgeProbability(SrcBB, DstBB);
671}
672
673bool IRTranslator::translateSwitch(const User &U, MachineIRBuilder &MIB) {
674 using namespace SwitchCG;
675 // Extract cases from the switch.
676 const SwitchInst &SI = cast<SwitchInst>(U);
677 BranchProbabilityInfo *BPI = FuncInfo.BPI;
678 CaseClusterVector Clusters;
679 Clusters.reserve(SI.getNumCases());
680 for (auto &I : SI.cases()) {
681 MachineBasicBlock *Succ = &getMBB(*I.getCaseSuccessor());
682 assert(Succ && "Could not find successor mbb in mapping");
683 const ConstantInt *CaseVal = I.getCaseValue();
684 BranchProbability Prob =
685 BPI ? BPI->getEdgeProbability(SI.getParent(), I.getSuccessorIndex())
686 : BranchProbability(1, SI.getNumCases() + 1);
687 Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Prob));
688 }
689
690 MachineBasicBlock *DefaultMBB = &getMBB(*SI.getDefaultDest());
691
692 // Cluster adjacent cases with the same destination. We do this at all
693 // optimization levels because it's cheap to do and will make codegen faster
694 // if there are many clusters.
695 sortAndRangeify(Clusters);
696
697 MachineBasicBlock *SwitchMBB = &getMBB(*SI.getParent());
698
699 // If there is only the default destination, jump there directly.
700 if (Clusters.empty()) {
701 SwitchMBB->addSuccessor(DefaultMBB);
702 if (DefaultMBB != SwitchMBB->getNextNode())
703 MIB.buildBr(*DefaultMBB);
704 return true;
705 }
706
707 SL->findJumpTables(Clusters, &SI, DefaultMBB, nullptr, nullptr);
708 SL->findBitTestClusters(Clusters, &SI);
709
710 LLVM_DEBUG({
711 dbgs() << "Case clusters: ";
712 for (const CaseCluster &C : Clusters) {
713 if (C.Kind == CC_JumpTable)
714 dbgs() << "JT:";
715 if (C.Kind == CC_BitTests)
716 dbgs() << "BT:";
717
718 C.Low->getValue().print(dbgs(), true);
719 if (C.Low != C.High) {
720 dbgs() << '-';
721 C.High->getValue().print(dbgs(), true);
722 }
723 dbgs() << ' ';
724 }
725 dbgs() << '\n';
726 });
727
728 assert(!Clusters.empty());
729 SwitchWorkList WorkList;
730 CaseClusterIt First = Clusters.begin();
731 CaseClusterIt Last = Clusters.end() - 1;
732 auto DefaultProb = getEdgeProbability(SwitchMBB, DefaultMBB);
733 WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultProb});
734
735 // FIXME: At the moment we don't do any splitting optimizations here like
736 // SelectionDAG does, so this worklist only has one entry.
737 while (!WorkList.empty()) {
738 SwitchWorkListItem W = WorkList.back();
739 WorkList.pop_back();
740 if (!lowerSwitchWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB, MIB))
741 return false;
742 }
743 return true;
744}
745
746void IRTranslator::emitJumpTable(SwitchCG::JumpTable &JT,
747 MachineBasicBlock *MBB) {
748 // Emit the code for the jump table
749 assert(JT.Reg != -1U && "Should lower JT Header first!");
750 MachineIRBuilder MIB(*MBB->getParent());
751 MIB.setMBB(*MBB);
752 MIB.setDebugLoc(CurBuilder->getDebugLoc());
753
754 Type *PtrIRTy = Type::getInt8PtrTy(MF->getFunction().getContext());
755 const LLT PtrTy = getLLTForType(*PtrIRTy, *DL);
756
757 auto Table = MIB.buildJumpTable(PtrTy, JT.JTI);
758 MIB.buildBrJT(Table.getReg(0), JT.JTI, JT.Reg);
759}
760
761bool IRTranslator::emitJumpTableHeader(SwitchCG::JumpTable &JT,
762 SwitchCG::JumpTableHeader &JTH,
763 MachineBasicBlock *HeaderBB) {
764 MachineIRBuilder MIB(*HeaderBB->getParent());
765 MIB.setMBB(*HeaderBB);
766 MIB.setDebugLoc(CurBuilder->getDebugLoc());
767
768 const Value &SValue = *JTH.SValue;
769 // Subtract the lowest switch case value from the value being switched on.
770 const LLT SwitchTy = getLLTForType(*SValue.getType(), *DL);
771 Register SwitchOpReg = getOrCreateVReg(SValue);
772 auto FirstCst = MIB.buildConstant(SwitchTy, JTH.First);
773 auto Sub = MIB.buildSub({SwitchTy}, SwitchOpReg, FirstCst);
774
775 // This value may be smaller or larger than the target's pointer type, and
776 // therefore require extension or truncating.
777 Type *PtrIRTy = SValue.getType()->getPointerTo();
778 const LLT PtrScalarTy = LLT::scalar(DL->getTypeSizeInBits(PtrIRTy));
779 Sub = MIB.buildZExtOrTrunc(PtrScalarTy, Sub);
780
781 JT.Reg = Sub.getReg(0);
782
783 if (JTH.OmitRangeCheck) {
784 if (JT.MBB != HeaderBB->getNextNode())
785 MIB.buildBr(*JT.MBB);
786 return true;
787 }
788
789 // Emit the range check for the jump table, and branch to the default block
790 // for the switch statement if the value being switched on exceeds the
791 // largest case in the switch.
792 auto Cst = getOrCreateVReg(
793 *ConstantInt::get(SValue.getType(), JTH.Last - JTH.First));
794 Cst = MIB.buildZExtOrTrunc(PtrScalarTy, Cst).getReg(0);
795 auto Cmp = MIB.buildICmp(CmpInst::ICMP_UGT, LLT::scalar(1), Sub, Cst);
796
797 auto BrCond = MIB.buildBrCond(Cmp.getReg(0), *JT.Default);
798
799 // Avoid emitting unnecessary branches to the next block.
800 if (JT.MBB != HeaderBB->getNextNode())
801 BrCond = MIB.buildBr(*JT.MBB);
802 return true;
803}
804
805void IRTranslator::emitSwitchCase(SwitchCG::CaseBlock &CB,
806 MachineBasicBlock *SwitchBB,
807 MachineIRBuilder &MIB) {
808 Register CondLHS = getOrCreateVReg(*CB.CmpLHS);
809 Register Cond;
810 DebugLoc OldDbgLoc = MIB.getDebugLoc();
811 MIB.setDebugLoc(CB.DbgLoc);
812 MIB.setMBB(*CB.ThisBB);
813
814 if (CB.PredInfo.NoCmp) {
815 // Branch or fall through to TrueBB.
816 addSuccessorWithProb(CB.ThisBB, CB.TrueBB, CB.TrueProb);
817 addMachineCFGPred({SwitchBB->getBasicBlock(), CB.TrueBB->getBasicBlock()},
818 CB.ThisBB);
819 CB.ThisBB->normalizeSuccProbs();
820 if (CB.TrueBB != CB.ThisBB->getNextNode())
821 MIB.buildBr(*CB.TrueBB);
822 MIB.setDebugLoc(OldDbgLoc);
823 return;
824 }
825
826 const LLT i1Ty = LLT::scalar(1);
827 // Build the compare.
828 if (!CB.CmpMHS) {
829 const auto *CI = dyn_cast<ConstantInt>(CB.CmpRHS);
830 // For conditional branch lowering, we might try to do something silly like
831 // emit an G_ICMP to compare an existing G_ICMP i1 result with true. If so,
832 // just re-use the existing condition vreg.
833 if (MRI->getType(CondLHS).getSizeInBits() == 1 && CI &&
834 CI->getZExtValue() == 1 && CB.PredInfo.Pred == CmpInst::ICMP_EQ) {
835 Cond = CondLHS;
836 } else {
837 Register CondRHS = getOrCreateVReg(*CB.CmpRHS);
838 if (CmpInst::isFPPredicate(CB.PredInfo.Pred))
839 Cond =
840 MIB.buildFCmp(CB.PredInfo.Pred, i1Ty, CondLHS, CondRHS).getReg(0);
841 else
842 Cond =
843 MIB.buildICmp(CB.PredInfo.Pred, i1Ty, CondLHS, CondRHS).getReg(0);
844 }
845 } else {
846 assert(CB.PredInfo.Pred == CmpInst::ICMP_SLE &&
847 "Can only handle SLE ranges");
848
849 const APInt& Low = cast<ConstantInt>(CB.CmpLHS)->getValue();
850 const APInt& High = cast<ConstantInt>(CB.CmpRHS)->getValue();
851
852 Register CmpOpReg = getOrCreateVReg(*CB.CmpMHS);
853 if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
854 Register CondRHS = getOrCreateVReg(*CB.CmpRHS);
855 Cond =
856 MIB.buildICmp(CmpInst::ICMP_SLE, i1Ty, CmpOpReg, CondRHS).getReg(0);
857 } else {
858 const LLT CmpTy = MRI->getType(CmpOpReg);
859 auto Sub = MIB.buildSub({CmpTy}, CmpOpReg, CondLHS);
860 auto Diff = MIB.buildConstant(CmpTy, High - Low);
861 Cond = MIB.buildICmp(CmpInst::ICMP_ULE, i1Ty, Sub, Diff).getReg(0);
862 }
863 }
864
865 // Update successor info
866 addSuccessorWithProb(CB.ThisBB, CB.TrueBB, CB.TrueProb);
867
868 addMachineCFGPred({SwitchBB->getBasicBlock(), CB.TrueBB->getBasicBlock()},
869 CB.ThisBB);
870
871 // TrueBB and FalseBB are always different unless the incoming IR is
872 // degenerate. This only happens when running llc on weird IR.
873 if (CB.TrueBB != CB.FalseBB)
874 addSuccessorWithProb(CB.ThisBB, CB.FalseBB, CB.FalseProb);
875 CB.ThisBB->normalizeSuccProbs();
876
877 addMachineCFGPred({SwitchBB->getBasicBlock(), CB.FalseBB->getBasicBlock()},
878 CB.ThisBB);
879
880 MIB.buildBrCond(Cond, *CB.TrueBB);
881 MIB.buildBr(*CB.FalseBB);
882 MIB.setDebugLoc(OldDbgLoc);
883}
884
885bool IRTranslator::lowerJumpTableWorkItem(SwitchCG::SwitchWorkListItem W,
886 MachineBasicBlock *SwitchMBB,
887 MachineBasicBlock *CurMBB,
888 MachineBasicBlock *DefaultMBB,
889 MachineIRBuilder &MIB,
890 MachineFunction::iterator BBI,
891 BranchProbability UnhandledProbs,
892 SwitchCG::CaseClusterIt I,
893 MachineBasicBlock *Fallthrough,
894 bool FallthroughUnreachable) {
895 using namespace SwitchCG;
896 MachineFunction *CurMF = SwitchMBB->getParent();
897 // FIXME: Optimize away range check based on pivot comparisons.
898 JumpTableHeader *JTH = &SL->JTCases[I->JTCasesIndex].first;
899 SwitchCG::JumpTable *JT = &SL->JTCases[I->JTCasesIndex].second;
900 BranchProbability DefaultProb = W.DefaultProb;
901
902 // The jump block hasn't been inserted yet; insert it here.
903 MachineBasicBlock *JumpMBB = JT->MBB;
904 CurMF->insert(BBI, JumpMBB);
905
906 // Since the jump table block is separate from the switch block, we need
907 // to keep track of it as a machine predecessor to the default block,
908 // otherwise we lose the phi edges.
909 addMachineCFGPred({SwitchMBB->getBasicBlock(), DefaultMBB->getBasicBlock()},
910 CurMBB);
911 addMachineCFGPred({SwitchMBB->getBasicBlock(), DefaultMBB->getBasicBlock()},
912 JumpMBB);
913
914 auto JumpProb = I->Prob;
915 auto FallthroughProb = UnhandledProbs;
916
917 // If the default statement is a target of the jump table, we evenly
918 // distribute the default probability to successors of CurMBB. Also
919 // update the probability on the edge from JumpMBB to Fallthrough.
920 for (MachineBasicBlock::succ_iterator SI = JumpMBB->succ_begin(),
921 SE = JumpMBB->succ_end();
922 SI != SE; ++SI) {
923 if (*SI == DefaultMBB) {
924 JumpProb += DefaultProb / 2;
925 FallthroughProb -= DefaultProb / 2;
926 JumpMBB->setSuccProbability(SI, DefaultProb / 2);
927 JumpMBB->normalizeSuccProbs();
928 } else {
929 // Also record edges from the jump table block to it's successors.
930 addMachineCFGPred({SwitchMBB->getBasicBlock(), (*SI)->getBasicBlock()},
931 JumpMBB);
932 }
933 }
934
935 // Skip the range check if the fallthrough block is unreachable.
936 if (FallthroughUnreachable)
937 JTH->OmitRangeCheck = true;
938
939 if (!JTH->OmitRangeCheck)
940 addSuccessorWithProb(CurMBB, Fallthrough, FallthroughProb);
941 addSuccessorWithProb(CurMBB, JumpMBB, JumpProb);
942 CurMBB->normalizeSuccProbs();
943
944 // The jump table header will be inserted in our current block, do the
945 // range check, and fall through to our fallthrough block.
946 JTH->HeaderBB = CurMBB;
947 JT->Default = Fallthrough; // FIXME: Move Default to JumpTableHeader.
948
949 // If we're in the right place, emit the jump table header right now.
950 if (CurMBB == SwitchMBB) {
951 if (!emitJumpTableHeader(*JT, *JTH, CurMBB))
952 return false;
953 JTH->Emitted = true;
954 }
955 return true;
956}
957bool IRTranslator::lowerSwitchRangeWorkItem(SwitchCG::CaseClusterIt I,
958 Value *Cond,
959 MachineBasicBlock *Fallthrough,
960 bool FallthroughUnreachable,
961 BranchProbability UnhandledProbs,
962 MachineBasicBlock *CurMBB,
963 MachineIRBuilder &MIB,
964 MachineBasicBlock *SwitchMBB) {
965 using namespace SwitchCG;
966 const Value *RHS, *LHS, *MHS;
967 CmpInst::Predicate Pred;
968 if (I->Low == I->High) {
969 // Check Cond == I->Low.
970 Pred = CmpInst::ICMP_EQ;
971 LHS = Cond;
972 RHS = I->Low;
973 MHS = nullptr;
974 } else {
975 // Check I->Low <= Cond <= I->High.
976 Pred = CmpInst::ICMP_SLE;
977 LHS = I->Low;
978 MHS = Cond;
979 RHS = I->High;
980 }
981
982 // If Fallthrough is unreachable, fold away the comparison.
983 // The false probability is the sum of all unhandled cases.
984 CaseBlock CB(Pred, FallthroughUnreachable, LHS, RHS, MHS, I->MBB, Fallthrough,
985 CurMBB, MIB.getDebugLoc(), I->Prob, UnhandledProbs);
986
987 emitSwitchCase(CB, SwitchMBB, MIB);
988 return true;
989}
990
991void IRTranslator::emitBitTestHeader(SwitchCG::BitTestBlock &B,
992 MachineBasicBlock *SwitchBB) {
993 MachineIRBuilder &MIB = *CurBuilder;
994 MIB.setMBB(*SwitchBB);
995
996 // Subtract the minimum value.
997 Register SwitchOpReg = getOrCreateVReg(*B.SValue);
998
999 LLT SwitchOpTy = MRI->getType(SwitchOpReg);
1000 Register MinValReg = MIB.buildConstant(SwitchOpTy, B.First).getReg(0);
1001 auto RangeSub = MIB.buildSub(SwitchOpTy, SwitchOpReg, MinValReg);
1002
1003 // Ensure that the type will fit the mask value.
1004 LLT MaskTy = SwitchOpTy;
1005 for (unsigned I = 0, E = B.Cases.size(); I != E; ++I) {
1006 if (!isUIntN(SwitchOpTy.getSizeInBits(), B.Cases[I].Mask)) {
1007 // Switch table case range are encoded into series of masks.
1008 // Just use pointer type, it's guaranteed to fit.
1009 MaskTy = LLT::scalar(64);
1010 break;
1011 }
1012 }
1013 Register SubReg = RangeSub.getReg(0);
1014 if (SwitchOpTy != MaskTy)
1015 SubReg = MIB.buildZExtOrTrunc(MaskTy, SubReg).getReg(0);
1016
1017 B.RegVT = getMVTForLLT(MaskTy);
1018 B.Reg = SubReg;
1019
1020 MachineBasicBlock *MBB = B.Cases[0].ThisBB;
1021
1022 if (!B.OmitRangeCheck)
1023 addSuccessorWithProb(SwitchBB, B.Default, B.DefaultProb);
1024 addSuccessorWithProb(SwitchBB, MBB, B.Prob);
1025
1026 SwitchBB->normalizeSuccProbs();
1027
1028 if (!B.OmitRangeCheck) {
1029 // Conditional branch to the default block.
1030 auto RangeCst = MIB.buildConstant(SwitchOpTy, B.Range);
1031 auto RangeCmp = MIB.buildICmp(CmpInst::Predicate::ICMP_UGT, LLT::scalar(1),
1032 RangeSub, RangeCst);
1033 MIB.buildBrCond(RangeCmp, *B.Default);
1034 }
1035
1036 // Avoid emitting unnecessary branches to the next block.
1037 if (MBB != SwitchBB->getNextNode())
1038 MIB.buildBr(*MBB);
1039}
1040
1041void IRTranslator::emitBitTestCase(SwitchCG::BitTestBlock &BB,
1042 MachineBasicBlock *NextMBB,
1043 BranchProbability BranchProbToNext,
1044 Register Reg, SwitchCG::BitTestCase &B,
1045 MachineBasicBlock *SwitchBB) {
1046 MachineIRBuilder &MIB = *CurBuilder;
1047 MIB.setMBB(*SwitchBB);
1048
1049 LLT SwitchTy = getLLTForMVT(BB.RegVT);
1050 Register Cmp;
1051 unsigned PopCount = countPopulation(B.Mask);
1052 if (PopCount == 1) {
1053 // Testing for a single bit; just compare the shift count with what it
1054 // would need to be to shift a 1 bit in that position.
1055 auto MaskTrailingZeros =
1056 MIB.buildConstant(SwitchTy, countTrailingZeros(B.Mask));
1057 Cmp =
1058 MIB.buildICmp(ICmpInst::ICMP_EQ, LLT::scalar(1), Reg, MaskTrailingZeros)
1059 .getReg(0);
1060 } else if (PopCount == BB.Range) {
1061 // There is only one zero bit in the range, test for it directly.
1062 auto MaskTrailingOnes =
1063 MIB.buildConstant(SwitchTy, countTrailingOnes(B.Mask));
1064 Cmp = MIB.buildICmp(CmpInst::ICMP_NE, LLT::scalar(1), Reg, MaskTrailingOnes)
1065 .getReg(0);
1066 } else {
1067 // Make desired shift.
1068 auto CstOne = MIB.buildConstant(SwitchTy, 1);
1069 auto SwitchVal = MIB.buildShl(SwitchTy, CstOne, Reg);
1070
1071 // Emit bit tests and jumps.
1072 auto CstMask = MIB.buildConstant(SwitchTy, B.Mask);
1073 auto AndOp = MIB.buildAnd(SwitchTy, SwitchVal, CstMask);
1074 auto CstZero = MIB.buildConstant(SwitchTy, 0);
1075 Cmp = MIB.buildICmp(CmpInst::ICMP_NE, LLT::scalar(1), AndOp, CstZero)
1076 .getReg(0);
1077 }
1078
1079 // The branch probability from SwitchBB to B.TargetBB is B.ExtraProb.
1080 addSuccessorWithProb(SwitchBB, B.TargetBB, B.ExtraProb);
1081 // The branch probability from SwitchBB to NextMBB is BranchProbToNext.
1082 addSuccessorWithProb(SwitchBB, NextMBB, BranchProbToNext);
1083 // It is not guaranteed that the sum of B.ExtraProb and BranchProbToNext is
1084 // one as they are relative probabilities (and thus work more like weights),
1085 // and hence we need to normalize them to let the sum of them become one.
1086 SwitchBB->normalizeSuccProbs();
1087
1088 // Record the fact that the IR edge from the header to the bit test target
1089 // will go through our new block. Neeeded for PHIs to have nodes added.
1090 addMachineCFGPred({BB.Parent->getBasicBlock(), B.TargetBB->getBasicBlock()},
1091 SwitchBB);
1092
1093 MIB.buildBrCond(Cmp, *B.TargetBB);
1094
1095 // Avoid emitting unnecessary branches to the next block.
1096 if (NextMBB != SwitchBB->getNextNode())
1097 MIB.buildBr(*NextMBB);
1098}
1099
1100bool IRTranslator::lowerBitTestWorkItem(
1101 SwitchCG::SwitchWorkListItem W, MachineBasicBlock *SwitchMBB,
1102 MachineBasicBlock *CurMBB, MachineBasicBlock *DefaultMBB,
1103 MachineIRBuilder &MIB, MachineFunction::iterator BBI,
1104 BranchProbability DefaultProb, BranchProbability UnhandledProbs,
1105 SwitchCG::CaseClusterIt I, MachineBasicBlock *Fallthrough,
1106 bool FallthroughUnreachable) {
1107 using namespace SwitchCG;
1108 MachineFunction *CurMF = SwitchMBB->getParent();
1109 // FIXME: Optimize away range check based on pivot comparisons.
1110 BitTestBlock *BTB = &SL->BitTestCases[I->BTCasesIndex];
1111 // The bit test blocks haven't been inserted yet; insert them here.
1112 for (BitTestCase &BTC : BTB->Cases)
1113 CurMF->insert(BBI, BTC.ThisBB);
1114
1115 // Fill in fields of the BitTestBlock.
1116 BTB->Parent = CurMBB;
1117 BTB->Default = Fallthrough;
1118
1119 BTB->DefaultProb = UnhandledProbs;
1120 // If the cases in bit test don't form a contiguous range, we evenly
1121 // distribute the probability on the edge to Fallthrough to two
1122 // successors of CurMBB.
1123 if (!BTB->ContiguousRange) {
1124 BTB->Prob += DefaultProb / 2;
1125 BTB->DefaultProb -= DefaultProb / 2;
1126 }
1127
1128 if (FallthroughUnreachable) {
1129 // Skip the range check if the fallthrough block is unreachable.
1130 BTB->OmitRangeCheck = true;
1131 }
1132
1133 // If we're in the right place, emit the bit test header right now.
1134 if (CurMBB == SwitchMBB) {
1135 emitBitTestHeader(*BTB, SwitchMBB);
1136 BTB->Emitted = true;
1137 }
1138 return true;
1139}
1140
1141bool IRTranslator::lowerSwitchWorkItem(SwitchCG::SwitchWorkListItem W,
1142 Value *Cond,
1143 MachineBasicBlock *SwitchMBB,
1144 MachineBasicBlock *DefaultMBB,
1145 MachineIRBuilder &MIB) {
1146 using namespace SwitchCG;
1147 MachineFunction *CurMF = FuncInfo.MF;
1148 MachineBasicBlock *NextMBB = nullptr;
1149 MachineFunction::iterator BBI(W.MBB);
1150 if (++BBI != FuncInfo.MF->end())
1151 NextMBB = &*BBI;
1152
1153 if (EnableOpts) {
1154 // Here, we order cases by probability so the most likely case will be
1155 // checked first. However, two clusters can have the same probability in
1156 // which case their relative ordering is non-deterministic. So we use Low
1157 // as a tie-breaker as clusters are guaranteed to never overlap.
1158 llvm::sort(W.FirstCluster, W.LastCluster + 1,
1159 [](const CaseCluster &a, const CaseCluster &b) {
1160 return a.Prob != b.Prob
1161 ? a.Prob > b.Prob
1162 : a.Low->getValue().slt(b.Low->getValue());
1163 });
1164
1165 // Rearrange the case blocks so that the last one falls through if possible
1166 // without changing the order of probabilities.
1167 for (CaseClusterIt I = W.LastCluster; I > W.FirstCluster;) {
1168 --I;
1169 if (I->Prob > W.LastCluster->Prob)
1170 break;
1171 if (I->Kind == CC_Range && I->MBB == NextMBB) {
1172 std::swap(*I, *W.LastCluster);
1173 break;
1174 }
1175 }
1176 }
1177
1178 // Compute total probability.
1179 BranchProbability DefaultProb = W.DefaultProb;
1180 BranchProbability UnhandledProbs = DefaultProb;
1181 for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I)
1182 UnhandledProbs += I->Prob;
1183
1184 MachineBasicBlock *CurMBB = W.MBB;
1185 for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) {
1186 bool FallthroughUnreachable = false;
1187 MachineBasicBlock *Fallthrough;
1188 if (I == W.LastCluster) {
1189 // For the last cluster, fall through to the default destination.
1190 Fallthrough = DefaultMBB;
1191 FallthroughUnreachable = isa<UnreachableInst>(
1192 DefaultMBB->getBasicBlock()->getFirstNonPHIOrDbg());
1193 } else {
1194 Fallthrough = CurMF->CreateMachineBasicBlock(CurMBB->getBasicBlock());
1195 CurMF->insert(BBI, Fallthrough);
1196 }
1197 UnhandledProbs -= I->Prob;
1198
1199 switch (I->Kind) {
1200 case CC_BitTests: {
1201 if (!lowerBitTestWorkItem(W, SwitchMBB, CurMBB, DefaultMBB, MIB, BBI,
1202 DefaultProb, UnhandledProbs, I, Fallthrough,
1203 FallthroughUnreachable)) {
1204 LLVM_DEBUG(dbgs() << "Failed to lower bit test for switch");
1205 return false;
1206 }
1207 break;
1208 }
1209
1210 case CC_JumpTable: {
1211 if (!lowerJumpTableWorkItem(W, SwitchMBB, CurMBB, DefaultMBB, MIB, BBI,
1212 UnhandledProbs, I, Fallthrough,
1213 FallthroughUnreachable)) {
1214 LLVM_DEBUG(dbgs() << "Failed to lower jump table");
1215 return false;
1216 }
1217 break;
1218 }
1219 case CC_Range: {
1220 if (!lowerSwitchRangeWorkItem(I, Cond, Fallthrough,
1221 FallthroughUnreachable, UnhandledProbs,
1222 CurMBB, MIB, SwitchMBB)) {
1223 LLVM_DEBUG(dbgs() << "Failed to lower switch range");
1224 return false;
1225 }
1226 break;
1227 }
1228 }
1229 CurMBB = Fallthrough;
1230 }
1231
1232 return true;
1233}
1234
1235bool IRTranslator::translateIndirectBr(const User &U,
1236 MachineIRBuilder &MIRBuilder) {
1237 const IndirectBrInst &BrInst = cast<IndirectBrInst>(U);
1238
1239 const Register Tgt = getOrCreateVReg(*BrInst.getAddress());
1240 MIRBuilder.buildBrIndirect(Tgt);
1241
1242 // Link successors.
1243 SmallPtrSet<const BasicBlock *, 32> AddedSuccessors;
1244 MachineBasicBlock &CurBB = MIRBuilder.getMBB();
1245 for (const BasicBlock *Succ : successors(&BrInst)) {
1246 // It's legal for indirectbr instructions to have duplicate blocks in the
1247 // destination list. We don't allow this in MIR. Skip anything that's
1248 // already a successor.
1249 if (!AddedSuccessors.insert(Succ).second)
1250 continue;
1251 CurBB.addSuccessor(&getMBB(*Succ));
1252 }
1253
1254 return true;
1255}
1256
1257static bool isSwiftError(const Value *V) {
1258 if (auto Arg = dyn_cast<Argument>(V))
1259 return Arg->hasSwiftErrorAttr();
1260 if (auto AI = dyn_cast<AllocaInst>(V))
1261 return AI->isSwiftError();
1262 return false;
1263}
1264
1265bool IRTranslator::translateLoad(const User &U, MachineIRBuilder &MIRBuilder) {
1266 const LoadInst &LI = cast<LoadInst>(U);
1267 if (DL->getTypeStoreSize(LI.getType()) == 0)
1268 return true;
1269
1270 ArrayRef<Register> Regs = getOrCreateVRegs(LI);
1271 ArrayRef<uint64_t> Offsets = *VMap.getOffsets(LI);
1272 Register Base = getOrCreateVReg(*LI.getPointerOperand());
1273
1274 Type *OffsetIRTy = DL->getIntPtrType(LI.getPointerOperandType());
1275 LLT OffsetTy = getLLTForType(*OffsetIRTy, *DL);
1276
1277 if (CLI->supportSwiftError() && isSwiftError(LI.getPointerOperand())) {
1278 assert(Regs.size() == 1 && "swifterror should be single pointer");
1279 Register VReg = SwiftError.getOrCreateVRegUseAt(&LI, &MIRBuilder.getMBB(),
1280 LI.getPointerOperand());
1281 MIRBuilder.buildCopy(Regs[0], VReg);
1282 return true;
1283 }
1284
1285 auto &TLI = *MF->getSubtarget().getTargetLowering();
1286 MachineMemOperand::Flags Flags = TLI.getLoadMemOperandFlags(LI, *DL);
1287
1288 const MDNode *Ranges =
1289 Regs.size() == 1 ? LI.getMetadata(LLVMContext::MD_range) : nullptr;
1290 for (unsigned i = 0; i < Regs.size(); ++i) {
1291 Register Addr;
1292 MIRBuilder.materializePtrAdd(Addr, Base, OffsetTy, Offsets[i] / 8);
1293
1294 MachinePointerInfo Ptr(LI.getPointerOperand(), Offsets[i] / 8);
1295 Align BaseAlign = getMemOpAlign(LI);
1296 AAMDNodes AAMetadata;
1297 LI.getAAMetadata(AAMetadata);
1298 auto MMO = MF->getMachineMemOperand(
1299 Ptr, Flags, MRI->getType(Regs[i]).getSizeInBytes(),
1300 commonAlignment(BaseAlign, Offsets[i] / 8), AAMetadata, Ranges,
1301 LI.getSyncScopeID(), LI.getOrdering());
1302 MIRBuilder.buildLoad(Regs[i], Addr, *MMO);
1303 }
1304
1305 return true;
1306}
1307
1308bool IRTranslator::translateStore(const User &U, MachineIRBuilder &MIRBuilder) {
1309 const StoreInst &SI = cast<StoreInst>(U);
1310 if (DL->getTypeStoreSize(SI.getValueOperand()->getType()) == 0)
1311 return true;
1312
1313 ArrayRef<Register> Vals = getOrCreateVRegs(*SI.getValueOperand());
1314 ArrayRef<uint64_t> Offsets = *VMap.getOffsets(*SI.getValueOperand());
1315 Register Base = getOrCreateVReg(*SI.getPointerOperand());
1316
1317 Type *OffsetIRTy = DL->getIntPtrType(SI.getPointerOperandType());
1318 LLT OffsetTy = getLLTForType(*OffsetIRTy, *DL);
1319
1320 if (CLI->supportSwiftError() && isSwiftError(SI.getPointerOperand())) {
1321 assert(Vals.size() == 1 && "swifterror should be single pointer");
1322
1323 Register VReg = SwiftError.getOrCreateVRegDefAt(&SI, &MIRBuilder.getMBB(),
1324 SI.getPointerOperand());
1325 MIRBuilder.buildCopy(VReg, Vals[0]);
1326 return true;
1327 }
1328
1329 auto &TLI = *MF->getSubtarget().getTargetLowering();
1330 MachineMemOperand::Flags Flags = TLI.getStoreMemOperandFlags(SI, *DL);
1331
1332 for (unsigned i = 0; i < Vals.size(); ++i) {
1333 Register Addr;
1334 MIRBuilder.materializePtrAdd(Addr, Base, OffsetTy, Offsets[i] / 8);
1335
1336 MachinePointerInfo Ptr(SI.getPointerOperand(), Offsets[i] / 8);
1337 Align BaseAlign = getMemOpAlign(SI);
1338 AAMDNodes AAMetadata;
1339 SI.getAAMetadata(AAMetadata);
1340 auto MMO = MF->getMachineMemOperand(
1341 Ptr, Flags, MRI->getType(Vals[i]).getSizeInBytes(),
1342 commonAlignment(BaseAlign, Offsets[i] / 8), AAMetadata, nullptr,
1343 SI.getSyncScopeID(), SI.getOrdering());
1344 MIRBuilder.buildStore(Vals[i], Addr, *MMO);
1345 }
1346 return true;
1347}
1348
1349static uint64_t getOffsetFromIndices(const User &U, const DataLayout &DL) {
1350 const Value *Src = U.getOperand(0);
1351 Type *Int32Ty = Type::getInt32Ty(U.getContext());
1352
1353 // getIndexedOffsetInType is designed for GEPs, so the first index is the
1354 // usual array element rather than looking into the actual aggregate.
1355 SmallVector<Value *, 1> Indices;
1356 Indices.push_back(ConstantInt::get(Int32Ty, 0));
1357
1358 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(&U)) {
1359 for (auto Idx : EVI->indices())
1360 Indices.push_back(ConstantInt::get(Int32Ty, Idx));
1361 } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(&U)) {
1362 for (auto Idx : IVI->indices())
1363 Indices.push_back(ConstantInt::get(Int32Ty, Idx));
1364 } else {
1365 for (unsigned i = 1; i < U.getNumOperands(); ++i)
1366 Indices.push_back(U.getOperand(i));
1367 }
1368
1369 return 8 * static_cast<uint64_t>(
1370 DL.getIndexedOffsetInType(Src->getType(), Indices));
1371}
1372
1373bool IRTranslator::translateExtractValue(const User &U,
1374 MachineIRBuilder &MIRBuilder) {
1375 const Value *Src = U.getOperand(0);
1376 uint64_t Offset = getOffsetFromIndices(U, *DL);
1377 ArrayRef<Register> SrcRegs = getOrCreateVRegs(*Src);
1378 ArrayRef<uint64_t> Offsets = *VMap.getOffsets(*Src);
1379 unsigned Idx = llvm::lower_bound(Offsets, Offset) - Offsets.begin();
1380 auto &DstRegs = allocateVRegs(U);
1381
1382 for (unsigned i = 0; i < DstRegs.size(); ++i)
1383 DstRegs[i] = SrcRegs[Idx++];
1384
1385 return true;
1386}
1387
1388bool IRTranslator::translateInsertValue(const User &U,
1389 MachineIRBuilder &MIRBuilder) {
1390 const Value *Src = U.getOperand(0);
1391 uint64_t Offset = getOffsetFromIndices(U, *DL);
1392 auto &DstRegs = allocateVRegs(U);
1393 ArrayRef<uint64_t> DstOffsets = *VMap.getOffsets(U);
1394 ArrayRef<Register> SrcRegs = getOrCreateVRegs(*Src);
1395 ArrayRef<Register> InsertedRegs = getOrCreateVRegs(*U.getOperand(1));
1396 auto InsertedIt = InsertedRegs.begin();
1397
1398 for (unsigned i = 0; i < DstRegs.size(); ++i) {
1399 if (DstOffsets[i] >= Offset && InsertedIt != InsertedRegs.end())
1400 DstRegs[i] = *InsertedIt++;
1401 else
1402 DstRegs[i] = SrcRegs[i];
1403 }
1404
1405 return true;
1406}
1407
1408bool IRTranslator::translateSelect(const User &U,
1409 MachineIRBuilder &MIRBuilder) {
1410 Register Tst = getOrCreateVReg(*U.getOperand(0));
1411 ArrayRef<Register> ResRegs = getOrCreateVRegs(U);
1412 ArrayRef<Register> Op0Regs = getOrCreateVRegs(*U.getOperand(1));
1413 ArrayRef<Register> Op1Regs = getOrCreateVRegs(*U.getOperand(2));
1414
1415 uint16_t Flags = 0;
1416 if (const SelectInst *SI = dyn_cast<SelectInst>(&U))
1417 Flags = MachineInstr::copyFlagsFromInstruction(*SI);
1418
1419 for (unsigned i = 0; i < ResRegs.size(); ++i) {
1420 MIRBuilder.buildSelect(ResRegs[i], Tst, Op0Regs[i], Op1Regs[i], Flags);
1421 }
1422
1423 return true;
1424}
1425
1426bool IRTranslator::translateCopy(const User &U, const Value &V,
1427 MachineIRBuilder &MIRBuilder) {
1428 Register Src = getOrCreateVReg(V);
1429 auto &Regs = *VMap.getVRegs(U);
1430 if (Regs.empty()) {
1431 Regs.push_back(Src);
1432 VMap.getOffsets(U)->push_back(0);
1433 } else {
1434 // If we already assigned a vreg for this instruction, we can't change that.
1435 // Emit a copy to satisfy the users we already emitted.
1436 MIRBuilder.buildCopy(Regs[0], Src);
1437 }
1438 return true;
1439}
1440
1441bool IRTranslator::translateBitCast(const User &U,
1442 MachineIRBuilder &MIRBuilder) {
1443 // If we're bitcasting to the source type, we can reuse the source vreg.
1444 if (getLLTForType(*U.getOperand(0)->getType(), *DL) ==
1445 getLLTForType(*U.getType(), *DL))
1446 return translateCopy(U, *U.getOperand(0), MIRBuilder);
1447
1448 return translateCast(TargetOpcode::G_BITCAST, U, MIRBuilder);
1449}
1450
1451bool IRTranslator::translateCast(unsigned Opcode, const User &U,
1452 MachineIRBuilder &MIRBuilder) {
1453 Register Op = getOrCreateVReg(*U.getOperand(0));
1454 Register Res = getOrCreateVReg(U);
1455 MIRBuilder.buildInstr(Opcode, {Res}, {Op});
1456 return true;
1457}
1458
1459bool IRTranslator::translateGetElementPtr(const User &U,
1460 MachineIRBuilder &MIRBuilder) {
1461 Value &Op0 = *U.getOperand(0);
1462 Register BaseReg = getOrCreateVReg(Op0);
1463 Type *PtrIRTy = Op0.getType();
1464 LLT PtrTy = getLLTForType(*PtrIRTy, *DL);
1465 Type *OffsetIRTy = DL->getIntPtrType(PtrIRTy);
1466 LLT OffsetTy = getLLTForType(*OffsetIRTy, *DL);
1467
1468 // Normalize Vector GEP - all scalar operands should be converted to the
1469 // splat vector.
1470 unsigned VectorWidth = 0;
1471 if (auto *VT = dyn_cast<VectorType>(U.getType()))
1472 VectorWidth = cast<FixedVectorType>(VT)->getNumElements();
1473
1474 // We might need to splat the base pointer into a vector if the offsets
1475 // are vectors.
1476 if (VectorWidth && !PtrTy.isVector()) {
1477 BaseReg =
1478 MIRBuilder.buildSplatVector(LLT::vector(VectorWidth, PtrTy), BaseReg)
1479 .getReg(0);
1480 PtrIRTy = FixedVectorType::get(PtrIRTy, VectorWidth);
1481 PtrTy = getLLTForType(*PtrIRTy, *DL);
1482 OffsetIRTy = DL->getIntPtrType(PtrIRTy);
1483 OffsetTy = getLLTForType(*OffsetIRTy, *DL);
1484 }
1485
1486 int64_t Offset = 0;
1487 for (gep_type_iterator GTI = gep_type_begin(&U), E = gep_type_end(&U);
1488 GTI != E; ++GTI) {
1489 const Value *Idx = GTI.getOperand();
1490 if (StructType *StTy = GTI.getStructTypeOrNull()) {
1491 unsigned Field = cast<Constant>(Idx)->getUniqueInteger().getZExtValue();
1492 Offset += DL->getStructLayout(StTy)->getElementOffset(Field);
1493 continue;
1494 } else {
1495 uint64_t ElementSize = DL->getTypeAllocSize(GTI.getIndexedType());
1496
1497 // If this is a scalar constant or a splat vector of constants,
1498 // handle it quickly.
1499 if (const auto *CI = dyn_cast<ConstantInt>(Idx)) {
1500 Offset += ElementSize * CI->getSExtValue();
1501 continue;
1502 }
1503
1504 if (Offset != 0) {
1505 auto OffsetMIB = MIRBuilder.buildConstant({OffsetTy}, Offset);
1506 BaseReg = MIRBuilder.buildPtrAdd(PtrTy, BaseReg, OffsetMIB.getReg(0))
1507 .getReg(0);
1508 Offset = 0;
1509 }
1510
1511 Register IdxReg = getOrCreateVReg(*Idx);
1512 LLT IdxTy = MRI->getType(IdxReg);
1513 if (IdxTy != OffsetTy) {
1514 if (!IdxTy.isVector() && VectorWidth) {
1515 IdxReg = MIRBuilder.buildSplatVector(
1516 OffsetTy.changeElementType(IdxTy), IdxReg).getReg(0);
1517 }
1518
1519 IdxReg = MIRBuilder.buildSExtOrTrunc(OffsetTy, IdxReg).getReg(0);
1520 }
1521
1522 // N = N + Idx * ElementSize;
1523 // Avoid doing it for ElementSize of 1.
1524 Register GepOffsetReg;
1525 if (ElementSize != 1) {
1526 auto ElementSizeMIB = MIRBuilder.buildConstant(
1527 getLLTForType(*OffsetIRTy, *DL), ElementSize);
1528 GepOffsetReg =
1529 MIRBuilder.buildMul(OffsetTy, IdxReg, ElementSizeMIB).getReg(0);
1530 } else
1531 GepOffsetReg = IdxReg;
1532
1533 BaseReg = MIRBuilder.buildPtrAdd(PtrTy, BaseReg, GepOffsetReg).getReg(0);
1534 }
1535 }
1536
1537 if (Offset != 0) {
1538 auto OffsetMIB =
1539 MIRBuilder.buildConstant(OffsetTy, Offset);
1540 MIRBuilder.buildPtrAdd(getOrCreateVReg(U), BaseReg, OffsetMIB.getReg(0));
1541 return true;
1542 }
1543
1544 MIRBuilder.buildCopy(getOrCreateVReg(U), BaseReg);
1545 return true;
1546}
1547
1548bool IRTranslator::translateMemFunc(const CallInst &CI,
1549 MachineIRBuilder &MIRBuilder,
1550 unsigned Opcode) {
1551
1552 // If the source is undef, then just emit a nop.
1553 if (isa<UndefValue>(CI.getArgOperand(1)))
1554 return true;
1555
1556 SmallVector<Register, 3> SrcRegs;
1557
1558 unsigned MinPtrSize = UINT_MAX;
1559 for (auto AI = CI.arg_begin(), AE = CI.arg_end(); std::next(AI) != AE; ++AI) {
1560 Register SrcReg = getOrCreateVReg(**AI);
1561 LLT SrcTy = MRI->getType(SrcReg);
1562 if (SrcTy.isPointer())
1563 MinPtrSize = std::min(SrcTy.getSizeInBits(), MinPtrSize);
1564 SrcRegs.push_back(SrcReg);
1565 }
1566
1567 LLT SizeTy = LLT::scalar(MinPtrSize);
1568
1569 // The size operand should be the minimum of the pointer sizes.
1570 Register &SizeOpReg = SrcRegs[SrcRegs.size() - 1];
1571 if (MRI->getType(SizeOpReg) != SizeTy)
1572 SizeOpReg = MIRBuilder.buildZExtOrTrunc(SizeTy, SizeOpReg).getReg(0);
1573
1574 auto ICall = MIRBuilder.buildInstr(Opcode);
1575 for (Register SrcReg : SrcRegs)
1576 ICall.addUse(SrcReg);
1577
1578 Align DstAlign;
1579 Align SrcAlign;
1580 unsigned IsVol =
1581 cast<ConstantInt>(CI.getArgOperand(CI.getNumArgOperands() - 1))
1582 ->getZExtValue();
1583
1584 if (auto *MCI = dyn_cast<MemCpyInst>(&CI)) {
1585 DstAlign = MCI->getDestAlign().valueOrOne();
1586 SrcAlign = MCI->getSourceAlign().valueOrOne();
1587 } else if (auto *MMI = dyn_cast<MemMoveInst>(&CI)) {
1588 DstAlign = MMI->getDestAlign().valueOrOne();
1589 SrcAlign = MMI->getSourceAlign().valueOrOne();
1590 } else {
1591 auto *MSI = cast<MemSetInst>(&CI);
1592 DstAlign = MSI->getDestAlign().valueOrOne();
1593 }
1594
1595 // We need to propagate the tail call flag from the IR inst as an argument.
1596 // Otherwise, we have to pessimize and assume later that we cannot tail call
1597 // any memory intrinsics.
1598 ICall.addImm(CI.isTailCall() ? 1 : 0);
1599
1600 // Create mem operands to store the alignment and volatile info.
1601 auto VolFlag = IsVol ? MachineMemOperand::MOVolatile : MachineMemOperand::MONone;
1602 ICall.addMemOperand(MF->getMachineMemOperand(
1603 MachinePointerInfo(CI.getArgOperand(0)),
1604 MachineMemOperand::MOStore | VolFlag, 1, DstAlign));
1605 if (Opcode != TargetOpcode::G_MEMSET)
1606 ICall.addMemOperand(MF->getMachineMemOperand(
1607 MachinePointerInfo(CI.getArgOperand(1)),
1608 MachineMemOperand::MOLoad | VolFlag, 1, SrcAlign));
1609
1610 return true;
1611}
1612
1613void IRTranslator::getStackGuard(Register DstReg,
1614 MachineIRBuilder &MIRBuilder) {
1615 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
1616 MRI->setRegClass(DstReg, TRI->getPointerRegClass(*MF));
1617 auto MIB =
1618 MIRBuilder.buildInstr(TargetOpcode::LOAD_STACK_GUARD, {DstReg}, {});
1619
1620 auto &TLI = *MF->getSubtarget().getTargetLowering();
1621 Value *Global = TLI.getSDagStackGuard(*MF->getFunction().getParent());
1622 if (!Global)
1623 return;
1624
1625 MachinePointerInfo MPInfo(Global);
1626 auto Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOInvariant |
1627 MachineMemOperand::MODereferenceable;
1628 MachineMemOperand *MemRef =
1629 MF->getMachineMemOperand(MPInfo, Flags, DL->getPointerSizeInBits() / 8,
1630 DL->getPointerABIAlignment(0));
1631 MIB.setMemRefs({MemRef});
1632}
1633
1634bool IRTranslator::translateOverflowIntrinsic(const CallInst &CI, unsigned Op,
1635 MachineIRBuilder &MIRBuilder) {
1636 ArrayRef<Register> ResRegs = getOrCreateVRegs(CI);
1637 MIRBuilder.buildInstr(
1638 Op, {ResRegs[0], ResRegs[1]},
1639 {getOrCreateVReg(*CI.getOperand(0)), getOrCreateVReg(*CI.getOperand(1))});
1640
1641 return true;
1642}
1643
1644bool IRTranslator::translateFixedPointIntrinsic(unsigned Op, const CallInst &CI,
1645 MachineIRBuilder &MIRBuilder) {
1646 Register Dst = getOrCreateVReg(CI);
1647 Register Src0 = getOrCreateVReg(*CI.getOperand(0));
1648 Register Src1 = getOrCreateVReg(*CI.getOperand(1));
1649 uint64_t Scale = cast<ConstantInt>(CI.getOperand(2))->getZExtValue();
1650 MIRBuilder.buildInstr(Op, {Dst}, { Src0, Src1, Scale });
1651 return true;
1652}
1653
1654unsigned IRTranslator::getSimpleIntrinsicOpcode(Intrinsic::ID ID) {
1655 switch (ID) {
1656 default:
1657 break;
1658 case Intrinsic::bswap:
1659 return TargetOpcode::G_BSWAP;
1660 case Intrinsic::bitreverse:
1661 return TargetOpcode::G_BITREVERSE;
1662 case Intrinsic::fshl:
1663 return TargetOpcode::G_FSHL;
1664 case Intrinsic::fshr:
1665 return TargetOpcode::G_FSHR;
1666 case Intrinsic::ceil:
1667 return TargetOpcode::G_FCEIL;
1668 case Intrinsic::cos:
1669 return TargetOpcode::G_FCOS;
1670 case Intrinsic::ctpop:
1671 return TargetOpcode::G_CTPOP;
1672 case Intrinsic::exp:
1673 return TargetOpcode::G_FEXP;
1674 case Intrinsic::exp2:
1675 return TargetOpcode::G_FEXP2;
1676 case Intrinsic::fabs:
1677 return TargetOpcode::G_FABS;
1678 case Intrinsic::copysign:
1679 return TargetOpcode::G_FCOPYSIGN;
1680 case Intrinsic::minnum:
1681 return TargetOpcode::G_FMINNUM;
1682 case Intrinsic::maxnum:
1683 return TargetOpcode::G_FMAXNUM;
1684 case Intrinsic::minimum:
1685 return TargetOpcode::G_FMINIMUM;
1686 case Intrinsic::maximum:
1687 return TargetOpcode::G_FMAXIMUM;
1688 case Intrinsic::canonicalize:
1689 return TargetOpcode::G_FCANONICALIZE;
1690 case Intrinsic::floor:
1691 return TargetOpcode::G_FFLOOR;
1692 case Intrinsic::fma:
1693 return TargetOpcode::G_FMA;
1694 case Intrinsic::log:
1695 return TargetOpcode::G_FLOG;
1696 case Intrinsic::log2:
1697 return TargetOpcode::G_FLOG2;
1698 case Intrinsic::log10:
1699 return TargetOpcode::G_FLOG10;
1700 case Intrinsic::nearbyint:
1701 return TargetOpcode::G_FNEARBYINT;
1702 case Intrinsic::pow:
1703 return TargetOpcode::G_FPOW;
1704 case Intrinsic::powi:
1705 return TargetOpcode::G_FPOWI;
1706 case Intrinsic::rint:
1707 return TargetOpcode::G_FRINT;
1708 case Intrinsic::round:
1709 return TargetOpcode::G_INTRINSIC_ROUND;
1710 case Intrinsic::roundeven:
1711 return TargetOpcode::G_INTRINSIC_ROUNDEVEN;
1712 case Intrinsic::sin:
1713 return TargetOpcode::G_FSIN;
1714 case Intrinsic::sqrt:
1715 return TargetOpcode::G_FSQRT;
1716 case Intrinsic::trunc:
1717 return TargetOpcode::G_INTRINSIC_TRUNC;
1718 case Intrinsic::readcyclecounter:
1719 return TargetOpcode::G_READCYCLECOUNTER;
1720 case Intrinsic::ptrmask:
1721 return TargetOpcode::G_PTRMASK;
1722 case Intrinsic::lrint:
1723 return TargetOpcode::G_INTRINSIC_LRINT;
1724 // FADD/FMUL require checking the FMF, so are handled elsewhere.
1725 case Intrinsic::vector_reduce_fmin:
1726 return TargetOpcode::G_VECREDUCE_FMIN;
1727 case Intrinsic::vector_reduce_fmax:
1728 return TargetOpcode::G_VECREDUCE_FMAX;
1729 case Intrinsic::vector_reduce_add:
1730 return TargetOpcode::G_VECREDUCE_ADD;
1731 case Intrinsic::vector_reduce_mul:
1732 return TargetOpcode::G_VECREDUCE_MUL;
1733 case Intrinsic::vector_reduce_and:
1734 return TargetOpcode::G_VECREDUCE_AND;
1735 case Intrinsic::vector_reduce_or:
1736 return TargetOpcode::G_VECREDUCE_OR;
1737 case Intrinsic::vector_reduce_xor:
1738 return TargetOpcode::G_VECREDUCE_XOR;
1739 case Intrinsic::vector_reduce_smax:
1740 return TargetOpcode::G_VECREDUCE_SMAX;
1741 case Intrinsic::vector_reduce_smin:
1742 return TargetOpcode::G_VECREDUCE_SMIN;
1743 case Intrinsic::vector_reduce_umax:
1744 return TargetOpcode::G_VECREDUCE_UMAX;
1745 case Intrinsic::vector_reduce_umin:
1746 return TargetOpcode::G_VECREDUCE_UMIN;
1747 }
1748 return Intrinsic::not_intrinsic;
1749}
1750
1751bool IRTranslator::translateSimpleIntrinsic(const CallInst &CI,
1752 Intrinsic::ID ID,
1753 MachineIRBuilder &MIRBuilder) {
1754
1755 unsigned Op = getSimpleIntrinsicOpcode(ID);
1756
1757 // Is this a simple intrinsic?
1758 if (Op == Intrinsic::not_intrinsic)
1759 return false;
1760
1761 // Yes. Let's translate it.
1762 SmallVector<llvm::SrcOp, 4> VRegs;
1763 for (auto &Arg : CI.arg_operands())
1764 VRegs.push_back(getOrCreateVReg(*Arg));
1765
1766 MIRBuilder.buildInstr(Op, {getOrCreateVReg(CI)}, VRegs,
1767 MachineInstr::copyFlagsFromInstruction(CI));
1768 return true;
1769}
1770
1771// TODO: Include ConstainedOps.def when all strict instructions are defined.
1772static unsigned getConstrainedOpcode(Intrinsic::ID ID) {
1773 switch (ID) {
1774 case Intrinsic::experimental_constrained_fadd:
1775 return TargetOpcode::G_STRICT_FADD;
1776 case Intrinsic::experimental_constrained_fsub:
1777 return TargetOpcode::G_STRICT_FSUB;
1778 case Intrinsic::experimental_constrained_fmul:
1779 return TargetOpcode::G_STRICT_FMUL;
1780 case Intrinsic::experimental_constrained_fdiv:
1781 return TargetOpcode::G_STRICT_FDIV;
1782 case Intrinsic::experimental_constrained_frem:
1783 return TargetOpcode::G_STRICT_FREM;
1784 case Intrinsic::experimental_constrained_fma:
1785 return TargetOpcode::G_STRICT_FMA;
1786 case Intrinsic::experimental_constrained_sqrt:
1787 return TargetOpcode::G_STRICT_FSQRT;
1788 default:
1789 return 0;
1790 }
1791}
1792
1793bool IRTranslator::translateConstrainedFPIntrinsic(
1794 const ConstrainedFPIntrinsic &FPI, MachineIRBuilder &MIRBuilder) {
1795 fp::ExceptionBehavior EB = FPI.getExceptionBehavior().getValue();
1796
1797 unsigned Opcode = getConstrainedOpcode(FPI.getIntrinsicID());
1798 if (!Opcode)
1799 return false;
1800
1801 unsigned Flags = MachineInstr::copyFlagsFromInstruction(FPI);
1802 if (EB == fp::ExceptionBehavior::ebIgnore)
1803 Flags |= MachineInstr::NoFPExcept;
1804
1805 SmallVector<llvm::SrcOp, 4> VRegs;
1806 VRegs.push_back(getOrCreateVReg(*FPI.getArgOperand(0)));
1807 if (!FPI.isUnaryOp())
1808 VRegs.push_back(getOrCreateVReg(*FPI.getArgOperand(1)));
1809 if (FPI.isTernaryOp())
1810 VRegs.push_back(getOrCreateVReg(*FPI.getArgOperand(2)));
1811
1812 MIRBuilder.buildInstr(Opcode, {getOrCreateVReg(FPI)}, VRegs, Flags);
1813 return true;
1814}
1815
1816bool IRTranslator::translateKnownIntrinsic(const CallInst &CI, Intrinsic::ID ID,
1817 MachineIRBuilder &MIRBuilder) {
1818
1819 // If this is a simple intrinsic (that is, we just need to add a def of
1820 // a vreg, and uses for each arg operand, then translate it.
1821 if (translateSimpleIntrinsic(CI, ID, MIRBuilder))
1822 return true;
1823
1824 switch (ID) {
1825 default:
1826 break;
1827 case Intrinsic::lifetime_start:
1828 case Intrinsic::lifetime_end: {
1829 // No stack colouring in O0, discard region information.
1830 if (MF->getTarget().getOptLevel() == CodeGenOpt::None)
1831 return true;
1832
1833 unsigned Op = ID == Intrinsic::lifetime_start ? TargetOpcode::LIFETIME_START
1834 : TargetOpcode::LIFETIME_END;
1835
1836 // Get the underlying objects for the location passed on the lifetime
1837 // marker.
1838 SmallVector<const Value *, 4> Allocas;
1839 getUnderlyingObjects(CI.getArgOperand(1), Allocas);
1840
1841 // Iterate over each underlying object, creating lifetime markers for each
1842 // static alloca. Quit if we find a non-static alloca.
1843 for (const Value *V :