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 "llvm/Transforms/Utils/MemoryOpRemark.h" 76 #include <algorithm> 77 #include <cassert> 78 #include <cstddef> 79 #include <cstdint> 80 #include <iterator> 81 #include <string> 82 #include <utility> 83 #include <vector> 84 85 #define DEBUG_TYPE "irtranslator" 86 87 using namespace llvm; 88 89 static cl::opt<bool> 90 EnableCSEInIRTranslator("enable-cse-in-irtranslator", 91 cl::desc("Should enable CSE in irtranslator"), 92 cl::Optional, cl::init(false)); 93 char IRTranslator::ID = 0; 94 95 INITIALIZE_PASS_BEGIN(IRTranslator, DEBUG_TYPE, "IRTranslator LLVM IR -> MI", 96 false, false) 97 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) 98 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass) 99 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 100 INITIALIZE_PASS_DEPENDENCY(StackProtector) 101 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 102 INITIALIZE_PASS_END(IRTranslator, DEBUG_TYPE, "IRTranslator LLVM IR -> MI", 103 false, false) 104 105 static void reportTranslationError(MachineFunction &MF, 106 const TargetPassConfig &TPC, 107 OptimizationRemarkEmitter &ORE, 108 OptimizationRemarkMissed &R) { 109 MF.getProperties().set(MachineFunctionProperties::Property::FailedISel); 110 111 // Print the function name explicitly if we don't have a debug location (which 112 // makes the diagnostic less useful) or if we're going to emit a raw error. 113 if (!R.getLocation().isValid() || TPC.isGlobalISelAbortEnabled()) 114 R << (" (in function: " + MF.getName() + ")").str(); 115 116 if (TPC.isGlobalISelAbortEnabled()) 117 report_fatal_error(R.getMsg()); 118 else 119 ORE.emit(R); 120 } 121 122 IRTranslator::IRTranslator(CodeGenOpt::Level optlevel) 123 : MachineFunctionPass(ID), OptLevel(optlevel) {} 124 125 #ifndef NDEBUG 126 namespace { 127 /// Verify that every instruction created has the same DILocation as the 128 /// instruction being translated. 129 class DILocationVerifier : public GISelChangeObserver { 130 const Instruction *CurrInst = nullptr; 131 132 public: 133 DILocationVerifier() = default; 134 ~DILocationVerifier() = default; 135 136 const Instruction *getCurrentInst() const { return CurrInst; } 137 void setCurrentInst(const Instruction *Inst) { CurrInst = Inst; } 138 139 void erasingInstr(MachineInstr &MI) override {} 140 void changingInstr(MachineInstr &MI) override {} 141 void changedInstr(MachineInstr &MI) override {} 142 143 void createdInstr(MachineInstr &MI) override { 144 assert(getCurrentInst() && "Inserted instruction without a current MI"); 145 146 // Only print the check message if we're actually checking it. 147 #ifndef NDEBUG 148 LLVM_DEBUG(dbgs() << "Checking DILocation from " << *CurrInst 149 << " was copied to " << MI); 150 #endif 151 // We allow insts in the entry block to have a debug loc line of 0 because 152 // they could have originated from constants, and we don't want a jumpy 153 // debug experience. 154 assert((CurrInst->getDebugLoc() == MI.getDebugLoc() || 155 MI.getDebugLoc().getLine() == 0) && 156 "Line info was not transferred to all instructions"); 157 } 158 }; 159 } // namespace 160 #endif // ifndef NDEBUG 161 162 163 void IRTranslator::getAnalysisUsage(AnalysisUsage &AU) const { 164 AU.addRequired<StackProtector>(); 165 AU.addRequired<TargetPassConfig>(); 166 AU.addRequired<GISelCSEAnalysisWrapperPass>(); 167 if (OptLevel != CodeGenOpt::None) 168 AU.addRequired<BranchProbabilityInfoWrapperPass>(); 169 AU.addRequired<TargetLibraryInfoWrapperPass>(); 170 AU.addPreserved<TargetLibraryInfoWrapperPass>(); 171 getSelectionDAGFallbackAnalysisUsage(AU); 172 MachineFunctionPass::getAnalysisUsage(AU); 173 } 174 175 IRTranslator::ValueToVRegInfo::VRegListT & 176 IRTranslator::allocateVRegs(const Value &Val) { 177 auto VRegsIt = VMap.findVRegs(Val); 178 if (VRegsIt != VMap.vregs_end()) 179 return *VRegsIt->second; 180 auto *Regs = VMap.getVRegs(Val); 181 auto *Offsets = VMap.getOffsets(Val); 182 SmallVector<LLT, 4> SplitTys; 183 computeValueLLTs(*DL, *Val.getType(), SplitTys, 184 Offsets->empty() ? Offsets : nullptr); 185 for (unsigned i = 0; i < SplitTys.size(); ++i) 186 Regs->push_back(0); 187 return *Regs; 188 } 189 190 ArrayRef<Register> IRTranslator::getOrCreateVRegs(const Value &Val) { 191 auto VRegsIt = VMap.findVRegs(Val); 192 if (VRegsIt != VMap.vregs_end()) 193 return *VRegsIt->second; 194 195 if (Val.getType()->isVoidTy()) 196 return *VMap.getVRegs(Val); 197 198 // Create entry for this type. 199 auto *VRegs = VMap.getVRegs(Val); 200 auto *Offsets = VMap.getOffsets(Val); 201 202 assert(Val.getType()->isSized() && 203 "Don't know how to create an empty vreg"); 204 205 SmallVector<LLT, 4> SplitTys; 206 computeValueLLTs(*DL, *Val.getType(), SplitTys, 207 Offsets->empty() ? Offsets : nullptr); 208 209 if (!isa<Constant>(Val)) { 210 for (auto Ty : SplitTys) 211 VRegs->push_back(MRI->createGenericVirtualRegister(Ty)); 212 return *VRegs; 213 } 214 215 if (Val.getType()->isAggregateType()) { 216 // UndefValue, ConstantAggregateZero 217 auto &C = cast<Constant>(Val); 218 unsigned Idx = 0; 219 while (auto Elt = C.getAggregateElement(Idx++)) { 220 auto EltRegs = getOrCreateVRegs(*Elt); 221 llvm::copy(EltRegs, std::back_inserter(*VRegs)); 222 } 223 } else { 224 assert(SplitTys.size() == 1 && "unexpectedly split LLT"); 225 VRegs->push_back(MRI->createGenericVirtualRegister(SplitTys[0])); 226 bool Success = translate(cast<Constant>(Val), VRegs->front()); 227 if (!Success) { 228 OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure", 229 MF->getFunction().getSubprogram(), 230 &MF->getFunction().getEntryBlock()); 231 R << "unable to translate constant: " << ore::NV("Type", Val.getType()); 232 reportTranslationError(*MF, *TPC, *ORE, R); 233 return *VRegs; 234 } 235 } 236 237 return *VRegs; 238 } 239 240 int IRTranslator::getOrCreateFrameIndex(const AllocaInst &AI) { 241 auto MapEntry = FrameIndices.find(&AI); 242 if (MapEntry != FrameIndices.end()) 243 return MapEntry->second; 244 245 uint64_t ElementSize = DL->getTypeAllocSize(AI.getAllocatedType()); 246 uint64_t Size = 247 ElementSize * cast<ConstantInt>(AI.getArraySize())->getZExtValue(); 248 249 // Always allocate at least one byte. 250 Size = std::max<uint64_t>(Size, 1u); 251 252 int &FI = FrameIndices[&AI]; 253 FI = MF->getFrameInfo().CreateStackObject(Size, AI.getAlign(), false, &AI); 254 return FI; 255 } 256 257 Align IRTranslator::getMemOpAlign(const Instruction &I) { 258 if (const StoreInst *SI = dyn_cast<StoreInst>(&I)) 259 return SI->getAlign(); 260 if (const LoadInst *LI = dyn_cast<LoadInst>(&I)) 261 return LI->getAlign(); 262 if (const AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I)) 263 return AI->getAlign(); 264 if (const AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I)) 265 return AI->getAlign(); 266 267 OptimizationRemarkMissed R("gisel-irtranslator", "", &I); 268 R << "unable to translate memop: " << ore::NV("Opcode", &I); 269 reportTranslationError(*MF, *TPC, *ORE, R); 270 return Align(1); 271 } 272 273 MachineBasicBlock &IRTranslator::getMBB(const BasicBlock &BB) { 274 MachineBasicBlock *&MBB = BBToMBB[&BB]; 275 assert(MBB && "BasicBlock was not encountered before"); 276 return *MBB; 277 } 278 279 void IRTranslator::addMachineCFGPred(CFGEdge Edge, MachineBasicBlock *NewPred) { 280 assert(NewPred && "new predecessor must be a real MachineBasicBlock"); 281 MachinePreds[Edge].push_back(NewPred); 282 } 283 284 bool IRTranslator::translateBinaryOp(unsigned Opcode, const User &U, 285 MachineIRBuilder &MIRBuilder) { 286 // Get or create a virtual register for each value. 287 // Unless the value is a Constant => loadimm cst? 288 // or inline constant each time? 289 // Creation of a virtual register needs to have a size. 290 Register Op0 = getOrCreateVReg(*U.getOperand(0)); 291 Register Op1 = getOrCreateVReg(*U.getOperand(1)); 292 Register Res = getOrCreateVReg(U); 293 uint16_t Flags = 0; 294 if (isa<Instruction>(U)) { 295 const Instruction &I = cast<Instruction>(U); 296 Flags = MachineInstr::copyFlagsFromInstruction(I); 297 } 298 299 MIRBuilder.buildInstr(Opcode, {Res}, {Op0, Op1}, Flags); 300 return true; 301 } 302 303 bool IRTranslator::translateUnaryOp(unsigned Opcode, const User &U, 304 MachineIRBuilder &MIRBuilder) { 305 Register Op0 = getOrCreateVReg(*U.getOperand(0)); 306 Register Res = getOrCreateVReg(U); 307 uint16_t Flags = 0; 308 if (isa<Instruction>(U)) { 309 const Instruction &I = cast<Instruction>(U); 310 Flags = MachineInstr::copyFlagsFromInstruction(I); 311 } 312 MIRBuilder.buildInstr(Opcode, {Res}, {Op0}, Flags); 313 return true; 314 } 315 316 bool IRTranslator::translateFNeg(const User &U, MachineIRBuilder &MIRBuilder) { 317 return translateUnaryOp(TargetOpcode::G_FNEG, U, MIRBuilder); 318 } 319 320 bool IRTranslator::translateCompare(const User &U, 321 MachineIRBuilder &MIRBuilder) { 322 auto *CI = dyn_cast<CmpInst>(&U); 323 Register Op0 = getOrCreateVReg(*U.getOperand(0)); 324 Register Op1 = getOrCreateVReg(*U.getOperand(1)); 325 Register Res = getOrCreateVReg(U); 326 CmpInst::Predicate Pred = 327 CI ? CI->getPredicate() : static_cast<CmpInst::Predicate>( 328 cast<ConstantExpr>(U).getPredicate()); 329 if (CmpInst::isIntPredicate(Pred)) 330 MIRBuilder.buildICmp(Pred, Res, Op0, Op1); 331 else if (Pred == CmpInst::FCMP_FALSE) 332 MIRBuilder.buildCopy( 333 Res, getOrCreateVReg(*Constant::getNullValue(U.getType()))); 334 else if (Pred == CmpInst::FCMP_TRUE) 335 MIRBuilder.buildCopy( 336 Res, getOrCreateVReg(*Constant::getAllOnesValue(U.getType()))); 337 else { 338 assert(CI && "Instruction should be CmpInst"); 339 MIRBuilder.buildFCmp(Pred, Res, Op0, Op1, 340 MachineInstr::copyFlagsFromInstruction(*CI)); 341 } 342 343 return true; 344 } 345 346 bool IRTranslator::translateRet(const User &U, MachineIRBuilder &MIRBuilder) { 347 const ReturnInst &RI = cast<ReturnInst>(U); 348 const Value *Ret = RI.getReturnValue(); 349 if (Ret && DL->getTypeStoreSize(Ret->getType()) == 0) 350 Ret = nullptr; 351 352 ArrayRef<Register> VRegs; 353 if (Ret) 354 VRegs = getOrCreateVRegs(*Ret); 355 356 Register SwiftErrorVReg = 0; 357 if (CLI->supportSwiftError() && SwiftError.getFunctionArg()) { 358 SwiftErrorVReg = SwiftError.getOrCreateVRegUseAt( 359 &RI, &MIRBuilder.getMBB(), SwiftError.getFunctionArg()); 360 } 361 362 // The target may mess up with the insertion point, but 363 // this is not important as a return is the last instruction 364 // of the block anyway. 365 return CLI->lowerReturn(MIRBuilder, Ret, VRegs, FuncInfo, SwiftErrorVReg); 366 } 367 368 void IRTranslator::emitBranchForMergedCondition( 369 const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, 370 MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, 371 BranchProbability TProb, BranchProbability FProb, bool InvertCond) { 372 // If the leaf of the tree is a comparison, merge the condition into 373 // the caseblock. 374 if (const CmpInst *BOp = dyn_cast<CmpInst>(Cond)) { 375 CmpInst::Predicate Condition; 376 if (const ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) { 377 Condition = InvertCond ? IC->getInversePredicate() : IC->getPredicate(); 378 } else { 379 const FCmpInst *FC = cast<FCmpInst>(Cond); 380 Condition = InvertCond ? FC->getInversePredicate() : FC->getPredicate(); 381 } 382 383 SwitchCG::CaseBlock CB(Condition, false, BOp->getOperand(0), 384 BOp->getOperand(1), nullptr, TBB, FBB, CurBB, 385 CurBuilder->getDebugLoc(), TProb, FProb); 386 SL->SwitchCases.push_back(CB); 387 return; 388 } 389 390 // Create a CaseBlock record representing this branch. 391 CmpInst::Predicate Pred = InvertCond ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ; 392 SwitchCG::CaseBlock CB( 393 Pred, false, Cond, ConstantInt::getTrue(MF->getFunction().getContext()), 394 nullptr, TBB, FBB, CurBB, CurBuilder->getDebugLoc(), TProb, FProb); 395 SL->SwitchCases.push_back(CB); 396 } 397 398 static bool isValInBlock(const Value *V, const BasicBlock *BB) { 399 if (const Instruction *I = dyn_cast<Instruction>(V)) 400 return I->getParent() == BB; 401 return true; 402 } 403 404 void IRTranslator::findMergedConditions( 405 const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, 406 MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, 407 Instruction::BinaryOps Opc, BranchProbability TProb, 408 BranchProbability FProb, bool InvertCond) { 409 using namespace PatternMatch; 410 assert((Opc == Instruction::And || Opc == Instruction::Or) && 411 "Expected Opc to be AND/OR"); 412 // Skip over not part of the tree and remember to invert op and operands at 413 // next level. 414 Value *NotCond; 415 if (match(Cond, m_OneUse(m_Not(m_Value(NotCond)))) && 416 isValInBlock(NotCond, CurBB->getBasicBlock())) { 417 findMergedConditions(NotCond, TBB, FBB, CurBB, SwitchBB, Opc, TProb, FProb, 418 !InvertCond); 419 return; 420 } 421 422 const Instruction *BOp = dyn_cast<Instruction>(Cond); 423 const Value *BOpOp0, *BOpOp1; 424 // Compute the effective opcode for Cond, taking into account whether it needs 425 // to be inverted, e.g. 426 // and (not (or A, B)), C 427 // gets lowered as 428 // and (and (not A, not B), C) 429 Instruction::BinaryOps BOpc = (Instruction::BinaryOps)0; 430 if (BOp) { 431 BOpc = match(BOp, m_LogicalAnd(m_Value(BOpOp0), m_Value(BOpOp1))) 432 ? Instruction::And 433 : (match(BOp, m_LogicalOr(m_Value(BOpOp0), m_Value(BOpOp1))) 434 ? Instruction::Or 435 : (Instruction::BinaryOps)0); 436 if (InvertCond) { 437 if (BOpc == Instruction::And) 438 BOpc = Instruction::Or; 439 else if (BOpc == Instruction::Or) 440 BOpc = Instruction::And; 441 } 442 } 443 444 // If this node is not part of the or/and tree, emit it as a branch. 445 // Note that all nodes in the tree should have same opcode. 446 bool BOpIsInOrAndTree = BOpc && BOpc == Opc && BOp->hasOneUse(); 447 if (!BOpIsInOrAndTree || BOp->getParent() != CurBB->getBasicBlock() || 448 !isValInBlock(BOpOp0, CurBB->getBasicBlock()) || 449 !isValInBlock(BOpOp1, CurBB->getBasicBlock())) { 450 emitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB, TProb, FProb, 451 InvertCond); 452 return; 453 } 454 455 // Create TmpBB after CurBB. 456 MachineFunction::iterator BBI(CurBB); 457 MachineBasicBlock *TmpBB = 458 MF->CreateMachineBasicBlock(CurBB->getBasicBlock()); 459 CurBB->getParent()->insert(++BBI, TmpBB); 460 461 if (Opc == Instruction::Or) { 462 // Codegen X | Y as: 463 // BB1: 464 // jmp_if_X TBB 465 // jmp TmpBB 466 // TmpBB: 467 // jmp_if_Y TBB 468 // jmp FBB 469 // 470 471 // We have flexibility in setting Prob for BB1 and Prob for TmpBB. 472 // The requirement is that 473 // TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB) 474 // = TrueProb for original BB. 475 // Assuming the original probabilities are A and B, one choice is to set 476 // BB1's probabilities to A/2 and A/2+B, and set TmpBB's probabilities to 477 // A/(1+B) and 2B/(1+B). This choice assumes that 478 // TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB. 479 // Another choice is to assume TrueProb for BB1 equals to TrueProb for 480 // TmpBB, but the math is more complicated. 481 482 auto NewTrueProb = TProb / 2; 483 auto NewFalseProb = TProb / 2 + FProb; 484 // Emit the LHS condition. 485 findMergedConditions(BOpOp0, TBB, TmpBB, CurBB, SwitchBB, Opc, NewTrueProb, 486 NewFalseProb, InvertCond); 487 488 // Normalize A/2 and B to get A/(1+B) and 2B/(1+B). 489 SmallVector<BranchProbability, 2> Probs{TProb / 2, FProb}; 490 BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); 491 // Emit the RHS condition into TmpBB. 492 findMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0], 493 Probs[1], InvertCond); 494 } else { 495 assert(Opc == Instruction::And && "Unknown merge op!"); 496 // Codegen X & Y as: 497 // BB1: 498 // jmp_if_X TmpBB 499 // jmp FBB 500 // TmpBB: 501 // jmp_if_Y TBB 502 // jmp FBB 503 // 504 // This requires creation of TmpBB after CurBB. 505 506 // We have flexibility in setting Prob for BB1 and Prob for TmpBB. 507 // The requirement is that 508 // FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB) 509 // = FalseProb for original BB. 510 // Assuming the original probabilities are A and B, one choice is to set 511 // BB1's probabilities to A+B/2 and B/2, and set TmpBB's probabilities to 512 // 2A/(1+A) and B/(1+A). This choice assumes that FalseProb for BB1 == 513 // TrueProb for BB1 * FalseProb for TmpBB. 514 515 auto NewTrueProb = TProb + FProb / 2; 516 auto NewFalseProb = FProb / 2; 517 // Emit the LHS condition. 518 findMergedConditions(BOpOp0, TmpBB, FBB, CurBB, SwitchBB, Opc, NewTrueProb, 519 NewFalseProb, InvertCond); 520 521 // Normalize A and B/2 to get 2A/(1+A) and B/(1+A). 522 SmallVector<BranchProbability, 2> Probs{TProb, FProb / 2}; 523 BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); 524 // Emit the RHS condition into TmpBB. 525 findMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0], 526 Probs[1], InvertCond); 527 } 528 } 529 530 bool IRTranslator::shouldEmitAsBranches( 531 const std::vector<SwitchCG::CaseBlock> &Cases) { 532 // For multiple cases, it's better to emit as branches. 533 if (Cases.size() != 2) 534 return true; 535 536 // If this is two comparisons of the same values or'd or and'd together, they 537 // will get folded into a single comparison, so don't emit two blocks. 538 if ((Cases[0].CmpLHS == Cases[1].CmpLHS && 539 Cases[0].CmpRHS == Cases[1].CmpRHS) || 540 (Cases[0].CmpRHS == Cases[1].CmpLHS && 541 Cases[0].CmpLHS == Cases[1].CmpRHS)) { 542 return false; 543 } 544 545 // Handle: (X != null) | (Y != null) --> (X|Y) != 0 546 // Handle: (X == null) & (Y == null) --> (X|Y) == 0 547 if (Cases[0].CmpRHS == Cases[1].CmpRHS && 548 Cases[0].PredInfo.Pred == Cases[1].PredInfo.Pred && 549 isa<Constant>(Cases[0].CmpRHS) && 550 cast<Constant>(Cases[0].CmpRHS)->isNullValue()) { 551 if (Cases[0].PredInfo.Pred == CmpInst::ICMP_EQ && 552 Cases[0].TrueBB == Cases[1].ThisBB) 553 return false; 554 if (Cases[0].PredInfo.Pred == CmpInst::ICMP_NE && 555 Cases[0].FalseBB == Cases[1].ThisBB) 556 return false; 557 } 558 559 return true; 560 } 561 562 bool IRTranslator::translateBr(const User &U, MachineIRBuilder &MIRBuilder) { 563 const BranchInst &BrInst = cast<BranchInst>(U); 564 auto &CurMBB = MIRBuilder.getMBB(); 565 auto *Succ0MBB = &getMBB(*BrInst.getSuccessor(0)); 566 567 if (BrInst.isUnconditional()) { 568 // If the unconditional target is the layout successor, fallthrough. 569 if (!CurMBB.isLayoutSuccessor(Succ0MBB)) 570 MIRBuilder.buildBr(*Succ0MBB); 571 572 // Link successors. 573 for (const BasicBlock *Succ : successors(&BrInst)) 574 CurMBB.addSuccessor(&getMBB(*Succ)); 575 return true; 576 } 577 578 // If this condition is one of the special cases we handle, do special stuff 579 // now. 580 const Value *CondVal = BrInst.getCondition(); 581 MachineBasicBlock *Succ1MBB = &getMBB(*BrInst.getSuccessor(1)); 582 583 const auto &TLI = *MF->getSubtarget().getTargetLowering(); 584 585 // If this is a series of conditions that are or'd or and'd together, emit 586 // this as a sequence of branches instead of setcc's with and/or operations. 587 // As long as jumps are not expensive (exceptions for multi-use logic ops, 588 // unpredictable branches, and vector extracts because those jumps are likely 589 // expensive for any target), this should improve performance. 590 // For example, instead of something like: 591 // cmp A, B 592 // C = seteq 593 // cmp D, E 594 // F = setle 595 // or C, F 596 // jnz foo 597 // Emit: 598 // cmp A, B 599 // je foo 600 // cmp D, E 601 // jle foo 602 using namespace PatternMatch; 603 const Instruction *CondI = dyn_cast<Instruction>(CondVal); 604 if (!TLI.isJumpExpensive() && CondI && CondI->hasOneUse() && 605 !BrInst.hasMetadata(LLVMContext::MD_unpredictable)) { 606 Instruction::BinaryOps Opcode = (Instruction::BinaryOps)0; 607 Value *Vec; 608 const Value *BOp0, *BOp1; 609 if (match(CondI, m_LogicalAnd(m_Value(BOp0), m_Value(BOp1)))) 610 Opcode = Instruction::And; 611 else if (match(CondI, m_LogicalOr(m_Value(BOp0), m_Value(BOp1)))) 612 Opcode = Instruction::Or; 613 614 if (Opcode && !(match(BOp0, m_ExtractElt(m_Value(Vec), m_Value())) && 615 match(BOp1, m_ExtractElt(m_Specific(Vec), m_Value())))) { 616 findMergedConditions(CondI, Succ0MBB, Succ1MBB, &CurMBB, &CurMBB, Opcode, 617 getEdgeProbability(&CurMBB, Succ0MBB), 618 getEdgeProbability(&CurMBB, Succ1MBB), 619 /*InvertCond=*/false); 620 assert(SL->SwitchCases[0].ThisBB == &CurMBB && "Unexpected lowering!"); 621 622 // Allow some cases to be rejected. 623 if (shouldEmitAsBranches(SL->SwitchCases)) { 624 // Emit the branch for this block. 625 emitSwitchCase(SL->SwitchCases[0], &CurMBB, *CurBuilder); 626 SL->SwitchCases.erase(SL->SwitchCases.begin()); 627 return true; 628 } 629 630 // Okay, we decided not to do this, remove any inserted MBB's and clear 631 // SwitchCases. 632 for (unsigned I = 1, E = SL->SwitchCases.size(); I != E; ++I) 633 MF->erase(SL->SwitchCases[I].ThisBB); 634 635 SL->SwitchCases.clear(); 636 } 637 } 638 639 // Create a CaseBlock record representing this branch. 640 SwitchCG::CaseBlock CB(CmpInst::ICMP_EQ, false, CondVal, 641 ConstantInt::getTrue(MF->getFunction().getContext()), 642 nullptr, Succ0MBB, Succ1MBB, &CurMBB, 643 CurBuilder->getDebugLoc()); 644 645 // Use emitSwitchCase to actually insert the fast branch sequence for this 646 // cond branch. 647 emitSwitchCase(CB, &CurMBB, *CurBuilder); 648 return true; 649 } 650 651 void IRTranslator::addSuccessorWithProb(MachineBasicBlock *Src, 652 MachineBasicBlock *Dst, 653 BranchProbability Prob) { 654 if (!FuncInfo.BPI) { 655 Src->addSuccessorWithoutProb(Dst); 656 return; 657 } 658 if (Prob.isUnknown()) 659 Prob = getEdgeProbability(Src, Dst); 660 Src->addSuccessor(Dst, Prob); 661 } 662 663 BranchProbability 664 IRTranslator::getEdgeProbability(const MachineBasicBlock *Src, 665 const MachineBasicBlock *Dst) const { 666 const BasicBlock *SrcBB = Src->getBasicBlock(); 667 const BasicBlock *DstBB = Dst->getBasicBlock(); 668 if (!FuncInfo.BPI) { 669 // If BPI is not available, set the default probability as 1 / N, where N is 670 // the number of successors. 671 auto SuccSize = std::max<uint32_t>(succ_size(SrcBB), 1); 672 return BranchProbability(1, SuccSize); 673 } 674 return FuncInfo.BPI->getEdgeProbability(SrcBB, DstBB); 675 } 676 677 bool IRTranslator::translateSwitch(const User &U, MachineIRBuilder &MIB) { 678 using namespace SwitchCG; 679 // Extract cases from the switch. 680 const SwitchInst &SI = cast<SwitchInst>(U); 681 BranchProbabilityInfo *BPI = FuncInfo.BPI; 682 CaseClusterVector Clusters; 683 Clusters.reserve(SI.getNumCases()); 684 for (auto &I : SI.cases()) { 685 MachineBasicBlock *Succ = &getMBB(*I.getCaseSuccessor()); 686 assert(Succ && "Could not find successor mbb in mapping"); 687 const ConstantInt *CaseVal = I.getCaseValue(); 688 BranchProbability Prob = 689 BPI ? BPI->getEdgeProbability(SI.getParent(), I.getSuccessorIndex()) 690 : BranchProbability(1, SI.getNumCases() + 1); 691 Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Prob)); 692 } 693 694 MachineBasicBlock *DefaultMBB = &getMBB(*SI.getDefaultDest()); 695 696 // Cluster adjacent cases with the same destination. We do this at all 697 // optimization levels because it's cheap to do and will make codegen faster 698 // if there are many clusters. 699 sortAndRangeify(Clusters); 700 701 MachineBasicBlock *SwitchMBB = &getMBB(*SI.getParent()); 702 703 // If there is only the default destination, jump there directly. 704 if (Clusters.empty()) { 705 SwitchMBB->addSuccessor(DefaultMBB); 706 if (DefaultMBB != SwitchMBB->getNextNode()) 707 MIB.buildBr(*DefaultMBB); 708 return true; 709 } 710 711 SL->findJumpTables(Clusters, &SI, DefaultMBB, nullptr, nullptr); 712 SL->findBitTestClusters(Clusters, &SI); 713 714 LLVM_DEBUG({ 715 dbgs() << "Case clusters: "; 716 for (const CaseCluster &C : Clusters) { 717 if (C.Kind == CC_JumpTable) 718 dbgs() << "JT:"; 719 if (C.Kind == CC_BitTests) 720 dbgs() << "BT:"; 721 722 C.Low->getValue().print(dbgs(), true); 723 if (C.Low != C.High) { 724 dbgs() << '-'; 725 C.High->getValue().print(dbgs(), true); 726 } 727 dbgs() << ' '; 728 } 729 dbgs() << '\n'; 730 }); 731 732 assert(!Clusters.empty()); 733 SwitchWorkList WorkList; 734 CaseClusterIt First = Clusters.begin(); 735 CaseClusterIt Last = Clusters.end() - 1; 736 auto DefaultProb = getEdgeProbability(SwitchMBB, DefaultMBB); 737 WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultProb}); 738 739 // FIXME: At the moment we don't do any splitting optimizations here like 740 // SelectionDAG does, so this worklist only has one entry. 741 while (!WorkList.empty()) { 742 SwitchWorkListItem W = WorkList.back(); 743 WorkList.pop_back(); 744 if (!lowerSwitchWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB, MIB)) 745 return false; 746 } 747 return true; 748 } 749 750 void IRTranslator::emitJumpTable(SwitchCG::JumpTable &JT, 751 MachineBasicBlock *MBB) { 752 // Emit the code for the jump table 753 assert(JT.Reg != -1U && "Should lower JT Header first!"); 754 MachineIRBuilder MIB(*MBB->getParent()); 755 MIB.setMBB(*MBB); 756 MIB.setDebugLoc(CurBuilder->getDebugLoc()); 757 758 Type *PtrIRTy = Type::getInt8PtrTy(MF->getFunction().getContext()); 759 const LLT PtrTy = getLLTForType(*PtrIRTy, *DL); 760 761 auto Table = MIB.buildJumpTable(PtrTy, JT.JTI); 762 MIB.buildBrJT(Table.getReg(0), JT.JTI, JT.Reg); 763 } 764 765 bool IRTranslator::emitJumpTableHeader(SwitchCG::JumpTable &JT, 766 SwitchCG::JumpTableHeader &JTH, 767 MachineBasicBlock *HeaderBB) { 768 MachineIRBuilder MIB(*HeaderBB->getParent()); 769 MIB.setMBB(*HeaderBB); 770 MIB.setDebugLoc(CurBuilder->getDebugLoc()); 771 772 const Value &SValue = *JTH.SValue; 773 // Subtract the lowest switch case value from the value being switched on. 774 const LLT SwitchTy = getLLTForType(*SValue.getType(), *DL); 775 Register SwitchOpReg = getOrCreateVReg(SValue); 776 auto FirstCst = MIB.buildConstant(SwitchTy, JTH.First); 777 auto Sub = MIB.buildSub({SwitchTy}, SwitchOpReg, FirstCst); 778 779 // This value may be smaller or larger than the target's pointer type, and 780 // therefore require extension or truncating. 781 Type *PtrIRTy = SValue.getType()->getPointerTo(); 782 const LLT PtrScalarTy = LLT::scalar(DL->getTypeSizeInBits(PtrIRTy)); 783 Sub = MIB.buildZExtOrTrunc(PtrScalarTy, Sub); 784 785 JT.Reg = Sub.getReg(0); 786 787 if (JTH.OmitRangeCheck) { 788 if (JT.MBB != HeaderBB->getNextNode()) 789 MIB.buildBr(*JT.MBB); 790 return true; 791 } 792 793 // Emit the range check for the jump table, and branch to the default block 794 // for the switch statement if the value being switched on exceeds the 795 // largest case in the switch. 796 auto Cst = getOrCreateVReg( 797 *ConstantInt::get(SValue.getType(), JTH.Last - JTH.First)); 798 Cst = MIB.buildZExtOrTrunc(PtrScalarTy, Cst).getReg(0); 799 auto Cmp = MIB.buildICmp(CmpInst::ICMP_UGT, LLT::scalar(1), Sub, Cst); 800 801 auto BrCond = MIB.buildBrCond(Cmp.getReg(0), *JT.Default); 802 803 // Avoid emitting unnecessary branches to the next block. 804 if (JT.MBB != HeaderBB->getNextNode()) 805 BrCond = MIB.buildBr(*JT.MBB); 806 return true; 807 } 808 809 void IRTranslator::emitSwitchCase(SwitchCG::CaseBlock &CB, 810 MachineBasicBlock *SwitchBB, 811 MachineIRBuilder &MIB) { 812 Register CondLHS = getOrCreateVReg(*CB.CmpLHS); 813 Register Cond; 814 DebugLoc OldDbgLoc = MIB.getDebugLoc(); 815 MIB.setDebugLoc(CB.DbgLoc); 816 MIB.setMBB(*CB.ThisBB); 817 818 if (CB.PredInfo.NoCmp) { 819 // Branch or fall through to TrueBB. 820 addSuccessorWithProb(CB.ThisBB, CB.TrueBB, CB.TrueProb); 821 addMachineCFGPred({SwitchBB->getBasicBlock(), CB.TrueBB->getBasicBlock()}, 822 CB.ThisBB); 823 CB.ThisBB->normalizeSuccProbs(); 824 if (CB.TrueBB != CB.ThisBB->getNextNode()) 825 MIB.buildBr(*CB.TrueBB); 826 MIB.setDebugLoc(OldDbgLoc); 827 return; 828 } 829 830 const LLT i1Ty = LLT::scalar(1); 831 // Build the compare. 832 if (!CB.CmpMHS) { 833 const auto *CI = dyn_cast<ConstantInt>(CB.CmpRHS); 834 // For conditional branch lowering, we might try to do something silly like 835 // emit an G_ICMP to compare an existing G_ICMP i1 result with true. If so, 836 // just re-use the existing condition vreg. 837 if (MRI->getType(CondLHS).getSizeInBits() == 1 && CI && 838 CI->getZExtValue() == 1 && CB.PredInfo.Pred == CmpInst::ICMP_EQ) { 839 Cond = CondLHS; 840 } else { 841 Register CondRHS = getOrCreateVReg(*CB.CmpRHS); 842 if (CmpInst::isFPPredicate(CB.PredInfo.Pred)) 843 Cond = 844 MIB.buildFCmp(CB.PredInfo.Pred, i1Ty, CondLHS, CondRHS).getReg(0); 845 else 846 Cond = 847 MIB.buildICmp(CB.PredInfo.Pred, i1Ty, CondLHS, CondRHS).getReg(0); 848 } 849 } else { 850 assert(CB.PredInfo.Pred == CmpInst::ICMP_SLE && 851 "Can only handle SLE ranges"); 852 853 const APInt& Low = cast<ConstantInt>(CB.CmpLHS)->getValue(); 854 const APInt& High = cast<ConstantInt>(CB.CmpRHS)->getValue(); 855 856 Register CmpOpReg = getOrCreateVReg(*CB.CmpMHS); 857 if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) { 858 Register CondRHS = getOrCreateVReg(*CB.CmpRHS); 859 Cond = 860 MIB.buildICmp(CmpInst::ICMP_SLE, i1Ty, CmpOpReg, CondRHS).getReg(0); 861 } else { 862 const LLT CmpTy = MRI->getType(CmpOpReg); 863 auto Sub = MIB.buildSub({CmpTy}, CmpOpReg, CondLHS); 864 auto Diff = MIB.buildConstant(CmpTy, High - Low); 865 Cond = MIB.buildICmp(CmpInst::ICMP_ULE, i1Ty, Sub, Diff).getReg(0); 866 } 867 } 868 869 // Update successor info 870 addSuccessorWithProb(CB.ThisBB, CB.TrueBB, CB.TrueProb); 871 872 addMachineCFGPred({SwitchBB->getBasicBlock(), CB.TrueBB->getBasicBlock()}, 873 CB.ThisBB); 874 875 // TrueBB and FalseBB are always different unless the incoming IR is 876 // degenerate. This only happens when running llc on weird IR. 877 if (CB.TrueBB != CB.FalseBB) 878 addSuccessorWithProb(CB.ThisBB, CB.FalseBB, CB.FalseProb); 879 CB.ThisBB->normalizeSuccProbs(); 880 881 addMachineCFGPred({SwitchBB->getBasicBlock(), CB.FalseBB->getBasicBlock()}, 882 CB.ThisBB); 883 884 MIB.buildBrCond(Cond, *CB.TrueBB); 885 MIB.buildBr(*CB.FalseBB); 886 MIB.setDebugLoc(OldDbgLoc); 887 } 888 889 bool IRTranslator::lowerJumpTableWorkItem(SwitchCG::SwitchWorkListItem W, 890 MachineBasicBlock *SwitchMBB, 891 MachineBasicBlock *CurMBB, 892 MachineBasicBlock *DefaultMBB, 893 MachineIRBuilder &MIB, 894 MachineFunction::iterator BBI, 895 BranchProbability UnhandledProbs, 896 SwitchCG::CaseClusterIt I, 897 MachineBasicBlock *Fallthrough, 898 bool FallthroughUnreachable) { 899 using namespace SwitchCG; 900 MachineFunction *CurMF = SwitchMBB->getParent(); 901 // FIXME: Optimize away range check based on pivot comparisons. 902 JumpTableHeader *JTH = &SL->JTCases[I->JTCasesIndex].first; 903 SwitchCG::JumpTable *JT = &SL->JTCases[I->JTCasesIndex].second; 904 BranchProbability DefaultProb = W.DefaultProb; 905 906 // The jump block hasn't been inserted yet; insert it here. 907 MachineBasicBlock *JumpMBB = JT->MBB; 908 CurMF->insert(BBI, JumpMBB); 909 910 // Since the jump table block is separate from the switch block, we need 911 // to keep track of it as a machine predecessor to the default block, 912 // otherwise we lose the phi edges. 913 addMachineCFGPred({SwitchMBB->getBasicBlock(), DefaultMBB->getBasicBlock()}, 914 CurMBB); 915 addMachineCFGPred({SwitchMBB->getBasicBlock(), DefaultMBB->getBasicBlock()}, 916 JumpMBB); 917 918 auto JumpProb = I->Prob; 919 auto FallthroughProb = UnhandledProbs; 920 921 // If the default statement is a target of the jump table, we evenly 922 // distribute the default probability to successors of CurMBB. Also 923 // update the probability on the edge from JumpMBB to Fallthrough. 924 for (MachineBasicBlock::succ_iterator SI = JumpMBB->succ_begin(), 925 SE = JumpMBB->succ_end(); 926 SI != SE; ++SI) { 927 if (*SI == DefaultMBB) { 928 JumpProb += DefaultProb / 2; 929 FallthroughProb -= DefaultProb / 2; 930 JumpMBB->setSuccProbability(SI, DefaultProb / 2); 931 JumpMBB->normalizeSuccProbs(); 932 } else { 933 // Also record edges from the jump table block to it's successors. 934 addMachineCFGPred({SwitchMBB->getBasicBlock(), (*SI)->getBasicBlock()}, 935 JumpMBB); 936 } 937 } 938 939 // Skip the range check if the fallthrough block is unreachable. 940 if (FallthroughUnreachable) 941 JTH->OmitRangeCheck = true; 942 943 if (!JTH->OmitRangeCheck) 944 addSuccessorWithProb(CurMBB, Fallthrough, FallthroughProb); 945 addSuccessorWithProb(CurMBB, JumpMBB, JumpProb); 946 CurMBB->normalizeSuccProbs(); 947 948 // The jump table header will be inserted in our current block, do the 949 // range check, and fall through to our fallthrough block. 950 JTH->HeaderBB = CurMBB; 951 JT->Default = Fallthrough; // FIXME: Move Default to JumpTableHeader. 952 953 // If we're in the right place, emit the jump table header right now. 954 if (CurMBB == SwitchMBB) { 955 if (!emitJumpTableHeader(*JT, *JTH, CurMBB)) 956 return false; 957 JTH->Emitted = true; 958 } 959 return true; 960 } 961 bool IRTranslator::lowerSwitchRangeWorkItem(SwitchCG::CaseClusterIt I, 962 Value *Cond, 963 MachineBasicBlock *Fallthrough, 964 bool FallthroughUnreachable, 965 BranchProbability UnhandledProbs, 966 MachineBasicBlock *CurMBB, 967 MachineIRBuilder &MIB, 968 MachineBasicBlock *SwitchMBB) { 969 using namespace SwitchCG; 970 const Value *RHS, *LHS, *MHS; 971 CmpInst::Predicate Pred; 972 if (I->Low == I->High) { 973 // Check Cond == I->Low. 974 Pred = CmpInst::ICMP_EQ; 975 LHS = Cond; 976 RHS = I->Low; 977 MHS = nullptr; 978 } else { 979 // Check I->Low <= Cond <= I->High. 980 Pred = CmpInst::ICMP_SLE; 981 LHS = I->Low; 982 MHS = Cond; 983 RHS = I->High; 984 } 985 986 // If Fallthrough is unreachable, fold away the comparison. 987 // The false probability is the sum of all unhandled cases. 988 CaseBlock CB(Pred, FallthroughUnreachable, LHS, RHS, MHS, I->MBB, Fallthrough, 989 CurMBB, MIB.getDebugLoc(), I->Prob, UnhandledProbs); 990 991 emitSwitchCase(CB, SwitchMBB, MIB); 992 return true; 993 } 994 995 void IRTranslator::emitBitTestHeader(SwitchCG::BitTestBlock &B, 996 MachineBasicBlock *SwitchBB) { 997 MachineIRBuilder &MIB = *CurBuilder; 998 MIB.setMBB(*SwitchBB); 999 1000 // Subtract the minimum value. 1001 Register SwitchOpReg = getOrCreateVReg(*B.SValue); 1002 1003 LLT SwitchOpTy = MRI->getType(SwitchOpReg); 1004 Register MinValReg = MIB.buildConstant(SwitchOpTy, B.First).getReg(0); 1005 auto RangeSub = MIB.buildSub(SwitchOpTy, SwitchOpReg, MinValReg); 1006 1007 // Ensure that the type will fit the mask value. 1008 LLT MaskTy = SwitchOpTy; 1009 for (unsigned I = 0, E = B.Cases.size(); I != E; ++I) { 1010 if (!isUIntN(SwitchOpTy.getSizeInBits(), B.Cases[I].Mask)) { 1011 // Switch table case range are encoded into series of masks. 1012 // Just use pointer type, it's guaranteed to fit. 1013 MaskTy = LLT::scalar(64); 1014 break; 1015 } 1016 } 1017 Register SubReg = RangeSub.getReg(0); 1018 if (SwitchOpTy != MaskTy) 1019 SubReg = MIB.buildZExtOrTrunc(MaskTy, SubReg).getReg(0); 1020 1021 B.RegVT = getMVTForLLT(MaskTy); 1022 B.Reg = SubReg; 1023 1024 MachineBasicBlock *MBB = B.Cases[0].ThisBB; 1025 1026 if (!B.OmitRangeCheck) 1027 addSuccessorWithProb(SwitchBB, B.Default, B.DefaultProb); 1028 addSuccessorWithProb(SwitchBB, MBB, B.Prob); 1029 1030 SwitchBB->normalizeSuccProbs(); 1031 1032 if (!B.OmitRangeCheck) { 1033 // Conditional branch to the default block. 1034 auto RangeCst = MIB.buildConstant(SwitchOpTy, B.Range); 1035 auto RangeCmp = MIB.buildICmp(CmpInst::Predicate::ICMP_UGT, LLT::scalar(1), 1036 RangeSub, RangeCst); 1037 MIB.buildBrCond(RangeCmp, *B.Default); 1038 } 1039 1040 // Avoid emitting unnecessary branches to the next block. 1041 if (MBB != SwitchBB->getNextNode()) 1042 MIB.buildBr(*MBB); 1043 } 1044 1045 void IRTranslator::emitBitTestCase(SwitchCG::BitTestBlock &BB, 1046 MachineBasicBlock *NextMBB, 1047 BranchProbability BranchProbToNext, 1048 Register Reg, SwitchCG::BitTestCase &B, 1049 MachineBasicBlock *SwitchBB) { 1050 MachineIRBuilder &MIB = *CurBuilder; 1051 MIB.setMBB(*SwitchBB); 1052 1053 LLT SwitchTy = getLLTForMVT(BB.RegVT); 1054 Register Cmp; 1055 unsigned PopCount = countPopulation(B.Mask); 1056 if (PopCount == 1) { 1057 // Testing for a single bit; just compare the shift count with what it 1058 // would need to be to shift a 1 bit in that position. 1059 auto MaskTrailingZeros = 1060 MIB.buildConstant(SwitchTy, countTrailingZeros(B.Mask)); 1061 Cmp = 1062 MIB.buildICmp(ICmpInst::ICMP_EQ, LLT::scalar(1), Reg, MaskTrailingZeros) 1063 .getReg(0); 1064 } else if (PopCount == BB.Range) { 1065 // There is only one zero bit in the range, test for it directly. 1066 auto MaskTrailingOnes = 1067 MIB.buildConstant(SwitchTy, countTrailingOnes(B.Mask)); 1068 Cmp = MIB.buildICmp(CmpInst::ICMP_NE, LLT::scalar(1), Reg, MaskTrailingOnes) 1069 .getReg(0); 1070 } else { 1071 // Make desired shift. 1072 auto CstOne = MIB.buildConstant(SwitchTy, 1); 1073 auto SwitchVal = MIB.buildShl(SwitchTy, CstOne, Reg); 1074 1075 // Emit bit tests and jumps. 1076 auto CstMask = MIB.buildConstant(SwitchTy, B.Mask); 1077 auto AndOp = MIB.buildAnd(SwitchTy, SwitchVal, CstMask); 1078 auto CstZero = MIB.buildConstant(SwitchTy, 0); 1079 Cmp = MIB.buildICmp(CmpInst::ICMP_NE, LLT::scalar(1), AndOp, CstZero) 1080 .getReg(0); 1081 } 1082 1083 // The branch probability from SwitchBB to B.TargetBB is B.ExtraProb. 1084 addSuccessorWithProb(SwitchBB, B.TargetBB, B.ExtraProb); 1085 // The branch probability from SwitchBB to NextMBB is BranchProbToNext. 1086 addSuccessorWithProb(SwitchBB, NextMBB, BranchProbToNext); 1087 // It is not guaranteed that the sum of B.ExtraProb and BranchProbToNext is 1088 // one as they are relative probabilities (and thus work more like weights), 1089 // and hence we need to normalize them to let the sum of them become one. 1090 SwitchBB->normalizeSuccProbs(); 1091 1092 // Record the fact that the IR edge from the header to the bit test target 1093 // will go through our new block. Neeeded for PHIs to have nodes added. 1094 addMachineCFGPred({BB.Parent->getBasicBlock(), B.TargetBB->getBasicBlock()}, 1095 SwitchBB); 1096 1097 MIB.buildBrCond(Cmp, *B.TargetBB); 1098 1099 // Avoid emitting unnecessary branches to the next block. 1100 if (NextMBB != SwitchBB->getNextNode()) 1101 MIB.buildBr(*NextMBB); 1102 } 1103 1104 bool IRTranslator::lowerBitTestWorkItem( 1105 SwitchCG::SwitchWorkListItem W, MachineBasicBlock *SwitchMBB, 1106 MachineBasicBlock *CurMBB, MachineBasicBlock *DefaultMBB, 1107 MachineIRBuilder &MIB, MachineFunction::iterator BBI, 1108 BranchProbability DefaultProb, BranchProbability UnhandledProbs, 1109 SwitchCG::CaseClusterIt I, MachineBasicBlock *Fallthrough, 1110 bool FallthroughUnreachable) { 1111 using namespace SwitchCG; 1112 MachineFunction *CurMF = SwitchMBB->getParent(); 1113 // FIXME: Optimize away range check based on pivot comparisons. 1114 BitTestBlock *BTB = &SL->BitTestCases[I->BTCasesIndex]; 1115 // The bit test blocks haven't been inserted yet; insert them here. 1116 for (BitTestCase &BTC : BTB->Cases) 1117 CurMF->insert(BBI, BTC.ThisBB); 1118 1119 // Fill in fields of the BitTestBlock. 1120 BTB->Parent = CurMBB; 1121 BTB->Default = Fallthrough; 1122 1123 BTB->DefaultProb = UnhandledProbs; 1124 // If the cases in bit test don't form a contiguous range, we evenly 1125 // distribute the probability on the edge to Fallthrough to two 1126 // successors of CurMBB. 1127 if (!BTB->ContiguousRange) { 1128 BTB->Prob += DefaultProb / 2; 1129 BTB->DefaultProb -= DefaultProb / 2; 1130 } 1131 1132 if (FallthroughUnreachable) { 1133 // Skip the range check if the fallthrough block is unreachable. 1134 BTB->OmitRangeCheck = true; 1135 } 1136 1137 // If we're in the right place, emit the bit test header right now. 1138 if (CurMBB == SwitchMBB) { 1139 emitBitTestHeader(*BTB, SwitchMBB); 1140 BTB->Emitted = true; 1141 } 1142 return true; 1143 } 1144 1145 bool IRTranslator::lowerSwitchWorkItem(SwitchCG::SwitchWorkListItem W, 1146 Value *Cond, 1147 MachineBasicBlock *SwitchMBB, 1148 MachineBasicBlock *DefaultMBB, 1149 MachineIRBuilder &MIB) { 1150 using namespace SwitchCG; 1151 MachineFunction *CurMF = FuncInfo.MF; 1152 MachineBasicBlock *NextMBB = nullptr; 1153 MachineFunction::iterator BBI(W.MBB); 1154 if (++BBI != FuncInfo.MF->end()) 1155 NextMBB = &*BBI; 1156 1157 if (EnableOpts) { 1158 // Here, we order cases by probability so the most likely case will be 1159 // checked first. However, two clusters can have the same probability in 1160 // which case their relative ordering is non-deterministic. So we use Low 1161 // as a tie-breaker as clusters are guaranteed to never overlap. 1162 llvm::sort(W.FirstCluster, W.LastCluster + 1, 1163 [](const CaseCluster &a, const CaseCluster &b) { 1164 return a.Prob != b.Prob 1165 ? a.Prob > b.Prob 1166 : a.Low->getValue().slt(b.Low->getValue()); 1167 }); 1168 1169 // Rearrange the case blocks so that the last one falls through if possible 1170 // without changing the order of probabilities. 1171 for (CaseClusterIt I = W.LastCluster; I > W.FirstCluster;) { 1172 --I; 1173 if (I->Prob > W.LastCluster->Prob) 1174 break; 1175 if (I->Kind == CC_Range && I->MBB == NextMBB) { 1176 std::swap(*I, *W.LastCluster); 1177 break; 1178 } 1179 } 1180 } 1181 1182 // Compute total probability. 1183 BranchProbability DefaultProb = W.DefaultProb; 1184 BranchProbability UnhandledProbs = DefaultProb; 1185 for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I) 1186 UnhandledProbs += I->Prob; 1187 1188 MachineBasicBlock *CurMBB = W.MBB; 1189 for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) { 1190 bool FallthroughUnreachable = false; 1191 MachineBasicBlock *Fallthrough; 1192 if (I == W.LastCluster) { 1193 // For the last cluster, fall through to the default destination. 1194 Fallthrough = DefaultMBB; 1195 FallthroughUnreachable = isa<UnreachableInst>( 1196 DefaultMBB->getBasicBlock()->getFirstNonPHIOrDbg()); 1197 } else { 1198 Fallthrough = CurMF->CreateMachineBasicBlock(CurMBB->getBasicBlock()); 1199 CurMF->insert(BBI, Fallthrough); 1200 } 1201 UnhandledProbs -= I->Prob; 1202 1203 switch (I->Kind) { 1204 case CC_BitTests: { 1205 if (!lowerBitTestWorkItem(W, SwitchMBB, CurMBB, DefaultMBB, MIB, BBI, 1206 DefaultProb, UnhandledProbs, I, Fallthrough, 1207 FallthroughUnreachable)) { 1208 LLVM_DEBUG(dbgs() << "Failed to lower bit test for switch"); 1209 return false; 1210 } 1211 break; 1212 } 1213 1214 case CC_JumpTable: { 1215 if (!lowerJumpTableWorkItem(W, SwitchMBB, CurMBB, DefaultMBB, MIB, BBI, 1216 UnhandledProbs, I, Fallthrough, 1217 FallthroughUnreachable)) { 1218 LLVM_DEBUG(dbgs() << "Failed to lower jump table"); 1219 return false; 1220 } 1221 break; 1222 } 1223 case CC_Range: { 1224 if (!lowerSwitchRangeWorkItem(I, Cond, Fallthrough, 1225 FallthroughUnreachable, UnhandledProbs, 1226 CurMBB, MIB, SwitchMBB)) { 1227 LLVM_DEBUG(dbgs() << "Failed to lower switch range"); 1228 return false; 1229 } 1230 break; 1231 } 1232 } 1233 CurMBB = Fallthrough; 1234 } 1235 1236 return true; 1237 } 1238 1239 bool IRTranslator::translateIndirectBr(const User &U, 1240 MachineIRBuilder &MIRBuilder) { 1241 const IndirectBrInst &BrInst = cast<IndirectBrInst>(U); 1242 1243 const Register Tgt = getOrCreateVReg(*BrInst.getAddress()); 1244 MIRBuilder.buildBrIndirect(Tgt); 1245 1246 // Link successors. 1247 SmallPtrSet<const BasicBlock *, 32> AddedSuccessors; 1248 MachineBasicBlock &CurBB = MIRBuilder.getMBB(); 1249 for (const BasicBlock *Succ : successors(&BrInst)) { 1250 // It's legal for indirectbr instructions to have duplicate blocks in the 1251 // destination list. We don't allow this in MIR. Skip anything that's 1252 // already a successor. 1253 if (!AddedSuccessors.insert(Succ).second) 1254 continue; 1255 CurBB.addSuccessor(&getMBB(*Succ)); 1256 } 1257 1258 return true; 1259 } 1260 1261 static bool isSwiftError(const Value *V) { 1262 if (auto Arg = dyn_cast<Argument>(V)) 1263 return Arg->hasSwiftErrorAttr(); 1264 if (auto AI = dyn_cast<AllocaInst>(V)) 1265 return AI->isSwiftError(); 1266 return false; 1267 } 1268 1269 bool IRTranslator::translateLoad(const User &U, MachineIRBuilder &MIRBuilder) { 1270 const LoadInst &LI = cast<LoadInst>(U); 1271 if (DL->getTypeStoreSize(LI.getType()) == 0) 1272 return true; 1273 1274 ArrayRef<Register> Regs = getOrCreateVRegs(LI); 1275 ArrayRef<uint64_t> Offsets = *VMap.getOffsets(LI); 1276 Register Base = getOrCreateVReg(*LI.getPointerOperand()); 1277 1278 Type *OffsetIRTy = DL->getIntPtrType(LI.getPointerOperandType()); 1279 LLT OffsetTy = getLLTForType(*OffsetIRTy, *DL); 1280 1281 if (CLI->supportSwiftError() && isSwiftError(LI.getPointerOperand())) { 1282 assert(Regs.size() == 1 && "swifterror should be single pointer"); 1283 Register VReg = SwiftError.getOrCreateVRegUseAt(&LI, &MIRBuilder.getMBB(), 1284 LI.getPointerOperand()); 1285 MIRBuilder.buildCopy(Regs[0], VReg); 1286 return true; 1287 } 1288 1289 auto &TLI = *MF->getSubtarget().getTargetLowering(); 1290 MachineMemOperand::Flags Flags = TLI.getLoadMemOperandFlags(LI, *DL); 1291 1292 const MDNode *Ranges = 1293 Regs.size() == 1 ? LI.getMetadata(LLVMContext::MD_range) : nullptr; 1294 for (unsigned i = 0; i < Regs.size(); ++i) { 1295 Register Addr; 1296 MIRBuilder.materializePtrAdd(Addr, Base, OffsetTy, Offsets[i] / 8); 1297 1298 MachinePointerInfo Ptr(LI.getPointerOperand(), Offsets[i] / 8); 1299 Align BaseAlign = getMemOpAlign(LI); 1300 AAMDNodes AAMetadata; 1301 LI.getAAMetadata(AAMetadata); 1302 auto MMO = MF->getMachineMemOperand( 1303 Ptr, Flags, MRI->getType(Regs[i]), 1304 commonAlignment(BaseAlign, Offsets[i] / 8), AAMetadata, Ranges, 1305 LI.getSyncScopeID(), LI.getOrdering()); 1306 MIRBuilder.buildLoad(Regs[i], Addr, *MMO); 1307 } 1308 1309 return true; 1310 } 1311 1312 bool IRTranslator::translateStore(const User &U, MachineIRBuilder &MIRBuilder) { 1313 const StoreInst &SI = cast<StoreInst>(U); 1314 if (DL->getTypeStoreSize(SI.getValueOperand()->getType()) == 0) 1315 return true; 1316 1317 ArrayRef<Register> Vals = getOrCreateVRegs(*SI.getValueOperand()); 1318 ArrayRef<uint64_t> Offsets = *VMap.getOffsets(*SI.getValueOperand()); 1319 Register Base = getOrCreateVReg(*SI.getPointerOperand()); 1320 1321 Type *OffsetIRTy = DL->getIntPtrType(SI.getPointerOperandType()); 1322 LLT OffsetTy = getLLTForType(*OffsetIRTy, *DL); 1323 1324 if (CLI->supportSwiftError() && isSwiftError(SI.getPointerOperand())) { 1325 assert(Vals.size() == 1 && "swifterror should be single pointer"); 1326 1327 Register VReg = SwiftError.getOrCreateVRegDefAt(&SI, &MIRBuilder.getMBB(), 1328 SI.getPointerOperand()); 1329 MIRBuilder.buildCopy(VReg, Vals[0]); 1330 return true; 1331 } 1332 1333 auto &TLI = *MF->getSubtarget().getTargetLowering(); 1334 MachineMemOperand::Flags Flags = TLI.getStoreMemOperandFlags(SI, *DL); 1335 1336 for (unsigned i = 0; i < Vals.size(); ++i) { 1337 Register Addr; 1338 MIRBuilder.materializePtrAdd(Addr, Base, OffsetTy, Offsets[i] / 8); 1339 1340 MachinePointerInfo Ptr(SI.getPointerOperand(), Offsets[i] / 8); 1341 Align BaseAlign = getMemOpAlign(SI); 1342 AAMDNodes AAMetadata; 1343 SI.getAAMetadata(AAMetadata); 1344 auto MMO = MF->getMachineMemOperand( 1345 Ptr, Flags, MRI->getType(Vals[i]), 1346 commonAlignment(BaseAlign, Offsets[i] / 8), AAMetadata, nullptr, 1347 SI.getSyncScopeID(), SI.getOrdering()); 1348 MIRBuilder.buildStore(Vals[i], Addr, *MMO); 1349 } 1350 return true; 1351 } 1352 1353 static uint64_t getOffsetFromIndices(const User &U, const DataLayout &DL) { 1354 const Value *Src = U.getOperand(0); 1355 Type *Int32Ty = Type::getInt32Ty(U.getContext()); 1356 1357 // getIndexedOffsetInType is designed for GEPs, so the first index is the 1358 // usual array element rather than looking into the actual aggregate. 1359 SmallVector<Value *, 1> Indices; 1360 Indices.push_back(ConstantInt::get(Int32Ty, 0)); 1361 1362 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(&U)) { 1363 for (auto Idx : EVI->indices()) 1364 Indices.push_back(ConstantInt::get(Int32Ty, Idx)); 1365 } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(&U)) { 1366 for (auto Idx : IVI->indices()) 1367 Indices.push_back(ConstantInt::get(Int32Ty, Idx)); 1368 } else { 1369 for (unsigned i = 1; i < U.getNumOperands(); ++i) 1370 Indices.push_back(U.getOperand(i)); 1371 } 1372 1373 return 8 * static_cast<uint64_t>( 1374 DL.getIndexedOffsetInType(Src->getType(), Indices)); 1375 } 1376 1377 bool IRTranslator::translateExtractValue(const User &U, 1378 MachineIRBuilder &MIRBuilder) { 1379 const Value *Src = U.getOperand(0); 1380 uint64_t Offset = getOffsetFromIndices(U, *DL); 1381 ArrayRef<Register> SrcRegs = getOrCreateVRegs(*Src); 1382 ArrayRef<uint64_t> Offsets = *VMap.getOffsets(*Src); 1383 unsigned Idx = llvm::lower_bound(Offsets, Offset) - Offsets.begin(); 1384 auto &DstRegs = allocateVRegs(U); 1385 1386 for (unsigned i = 0; i < DstRegs.size(); ++i) 1387 DstRegs[i] = SrcRegs[Idx++]; 1388 1389 return true; 1390 } 1391 1392 bool IRTranslator::translateInsertValue(const User &U, 1393 MachineIRBuilder &MIRBuilder) { 1394 const Value *Src = U.getOperand(0); 1395 uint64_t Offset = getOffsetFromIndices(U, *DL); 1396 auto &DstRegs = allocateVRegs(U); 1397 ArrayRef<uint64_t> DstOffsets = *VMap.getOffsets(U); 1398 ArrayRef<Register> SrcRegs = getOrCreateVRegs(*Src); 1399 ArrayRef<Register> InsertedRegs = getOrCreateVRegs(*U.getOperand(1)); 1400 auto InsertedIt = InsertedRegs.begin(); 1401 1402 for (unsigned i = 0; i < DstRegs.size(); ++i) { 1403 if (DstOffsets[i] >= Offset && InsertedIt != InsertedRegs.end()) 1404 DstRegs[i] = *InsertedIt++; 1405 else 1406 DstRegs[i] = SrcRegs[i]; 1407 } 1408 1409 return true; 1410 } 1411 1412 bool IRTranslator::translateSelect(const User &U, 1413 MachineIRBuilder &MIRBuilder) { 1414 Register Tst = getOrCreateVReg(*U.getOperand(0)); 1415 ArrayRef<Register> ResRegs = getOrCreateVRegs(U); 1416 ArrayRef<Register> Op0Regs = getOrCreateVRegs(*U.getOperand(1)); 1417 ArrayRef<Register> Op1Regs = getOrCreateVRegs(*U.getOperand(2)); 1418 1419 uint16_t Flags = 0; 1420 if (const SelectInst *SI = dyn_cast<SelectInst>(&U)) 1421 Flags = MachineInstr::copyFlagsFromInstruction(*SI); 1422 1423 for (unsigned i = 0; i < ResRegs.size(); ++i) { 1424 MIRBuilder.buildSelect(ResRegs[i], Tst, Op0Regs[i], Op1Regs[i], Flags); 1425 } 1426 1427 return true; 1428 } 1429 1430 bool IRTranslator::translateCopy(const User &U, const Value &V, 1431 MachineIRBuilder &MIRBuilder) { 1432 Register Src = getOrCreateVReg(V); 1433 auto &Regs = *VMap.getVRegs(U); 1434 if (Regs.empty()) { 1435 Regs.push_back(Src); 1436 VMap.getOffsets(U)->push_back(0); 1437 } else { 1438 // If we already assigned a vreg for this instruction, we can't change that. 1439 // Emit a copy to satisfy the users we already emitted. 1440 MIRBuilder.buildCopy(Regs[0], Src); 1441 } 1442 return true; 1443 } 1444 1445 bool IRTranslator::translateBitCast(const User &U, 1446 MachineIRBuilder &MIRBuilder) { 1447 // If we're bitcasting to the source type, we can reuse the source vreg. 1448 if (getLLTForType(*U.getOperand(0)->getType(), *DL) == 1449 getLLTForType(*U.getType(), *DL)) 1450 return translateCopy(U, *U.getOperand(0), MIRBuilder); 1451 1452 return translateCast(TargetOpcode::G_BITCAST, U, MIRBuilder); 1453 } 1454 1455 bool IRTranslator::translateCast(unsigned Opcode, const User &U, 1456 MachineIRBuilder &MIRBuilder) { 1457 Register Op = getOrCreateVReg(*U.getOperand(0)); 1458 Register Res = getOrCreateVReg(U); 1459 MIRBuilder.buildInstr(Opcode, {Res}, {Op}); 1460 return true; 1461 } 1462 1463 bool IRTranslator::translateGetElementPtr(const User &U, 1464 MachineIRBuilder &MIRBuilder) { 1465 Value &Op0 = *U.getOperand(0); 1466 Register BaseReg = getOrCreateVReg(Op0); 1467 Type *PtrIRTy = Op0.getType(); 1468 LLT PtrTy = getLLTForType(*PtrIRTy, *DL); 1469 Type *OffsetIRTy = DL->getIntPtrType(PtrIRTy); 1470 LLT OffsetTy = getLLTForType(*OffsetIRTy, *DL); 1471 1472 // Normalize Vector GEP - all scalar operands should be converted to the 1473 // splat vector. 1474 unsigned VectorWidth = 0; 1475 1476 // True if we should use a splat vector; using VectorWidth alone is not 1477 // sufficient. 1478 bool WantSplatVector = false; 1479 if (auto *VT = dyn_cast<VectorType>(U.getType())) { 1480 VectorWidth = cast<FixedVectorType>(VT)->getNumElements(); 1481 // We don't produce 1 x N vectors; those are treated as scalars. 1482 WantSplatVector = VectorWidth > 1; 1483 } 1484 1485 // We might need to splat the base pointer into a vector if the offsets 1486 // are vectors. 1487 if (WantSplatVector && !PtrTy.isVector()) { 1488 BaseReg = 1489 MIRBuilder 1490 .buildSplatVector(LLT::fixed_vector(VectorWidth, PtrTy), BaseReg) 1491 .getReg(0); 1492 PtrIRTy = FixedVectorType::get(PtrIRTy, VectorWidth); 1493 PtrTy = getLLTForType(*PtrIRTy, *DL); 1494 OffsetIRTy = DL->getIntPtrType(PtrIRTy); 1495 OffsetTy = getLLTForType(*OffsetIRTy, *DL); 1496 } 1497 1498 int64_t Offset = 0; 1499 for (gep_type_iterator GTI = gep_type_begin(&U), E = gep_type_end(&U); 1500 GTI != E; ++GTI) { 1501 const Value *Idx = GTI.getOperand(); 1502 if (StructType *StTy = GTI.getStructTypeOrNull()) { 1503 unsigned Field = cast<Constant>(Idx)->getUniqueInteger().getZExtValue(); 1504 Offset += DL->getStructLayout(StTy)->getElementOffset(Field); 1505 continue; 1506 } else { 1507 uint64_t ElementSize = DL->getTypeAllocSize(GTI.getIndexedType()); 1508 1509 // If this is a scalar constant or a splat vector of constants, 1510 // handle it quickly. 1511 if (const auto *CI = dyn_cast<ConstantInt>(Idx)) { 1512 Offset += ElementSize * CI->getSExtValue(); 1513 continue; 1514 } 1515 1516 if (Offset != 0) { 1517 auto OffsetMIB = MIRBuilder.buildConstant({OffsetTy}, Offset); 1518 BaseReg = MIRBuilder.buildPtrAdd(PtrTy, BaseReg, OffsetMIB.getReg(0)) 1519 .getReg(0); 1520 Offset = 0; 1521 } 1522 1523 Register IdxReg = getOrCreateVReg(*Idx); 1524 LLT IdxTy = MRI->getType(IdxReg); 1525 if (IdxTy != OffsetTy) { 1526 if (!IdxTy.isVector() && WantSplatVector) { 1527 IdxReg = MIRBuilder.buildSplatVector( 1528 OffsetTy.changeElementType(IdxTy), IdxReg).getReg(0); 1529 } 1530 1531 IdxReg = MIRBuilder.buildSExtOrTrunc(OffsetTy, IdxReg).getReg(0); 1532 } 1533 1534 // N = N + Idx * ElementSize; 1535 // Avoid doing it for ElementSize of 1. 1536 Register GepOffsetReg; 1537 if (ElementSize != 1) { 1538 auto ElementSizeMIB = MIRBuilder.buildConstant( 1539 getLLTForType(*OffsetIRTy, *DL), ElementSize); 1540 GepOffsetReg = 1541 MIRBuilder.buildMul(OffsetTy, IdxReg, ElementSizeMIB).getReg(0); 1542 } else 1543 GepOffsetReg = IdxReg; 1544 1545 BaseReg = MIRBuilder.buildPtrAdd(PtrTy, BaseReg, GepOffsetReg).getReg(0); 1546 } 1547 } 1548 1549 if (Offset != 0) { 1550 auto OffsetMIB = 1551 MIRBuilder.buildConstant(OffsetTy, Offset); 1552 MIRBuilder.buildPtrAdd(getOrCreateVReg(U), BaseReg, OffsetMIB.getReg(0)); 1553 return true; 1554 } 1555 1556 MIRBuilder.buildCopy(getOrCreateVReg(U), BaseReg); 1557 return true; 1558 } 1559 1560 bool IRTranslator::translateMemFunc(const CallInst &CI, 1561 MachineIRBuilder &MIRBuilder, 1562 unsigned Opcode) { 1563 1564 // If the source is undef, then just emit a nop. 1565 if (isa<UndefValue>(CI.getArgOperand(1))) 1566 return true; 1567 1568 SmallVector<Register, 3> SrcRegs; 1569 1570 unsigned MinPtrSize = UINT_MAX; 1571 for (auto AI = CI.arg_begin(), AE = CI.arg_end(); std::next(AI) != AE; ++AI) { 1572 Register SrcReg = getOrCreateVReg(**AI); 1573 LLT SrcTy = MRI->getType(SrcReg); 1574 if (SrcTy.isPointer()) 1575 MinPtrSize = std::min<unsigned>(SrcTy.getSizeInBits(), MinPtrSize); 1576 SrcRegs.push_back(SrcReg); 1577 } 1578 1579 LLT SizeTy = LLT::scalar(MinPtrSize); 1580 1581 // The size operand should be the minimum of the pointer sizes. 1582 Register &SizeOpReg = SrcRegs[SrcRegs.size() - 1]; 1583 if (MRI->getType(SizeOpReg) != SizeTy) 1584 SizeOpReg = MIRBuilder.buildZExtOrTrunc(SizeTy, SizeOpReg).getReg(0); 1585 1586 auto ICall = MIRBuilder.buildInstr(Opcode); 1587 for (Register SrcReg : SrcRegs) 1588 ICall.addUse(SrcReg); 1589 1590 Align DstAlign; 1591 Align SrcAlign; 1592 unsigned IsVol = 1593 cast<ConstantInt>(CI.getArgOperand(CI.getNumArgOperands() - 1)) 1594 ->getZExtValue(); 1595 1596 if (auto *MCI = dyn_cast<MemCpyInst>(&CI)) { 1597 DstAlign = MCI->getDestAlign().valueOrOne(); 1598 SrcAlign = MCI->getSourceAlign().valueOrOne(); 1599 } else if (auto *MCI = dyn_cast<MemCpyInlineInst>(&CI)) { 1600 DstAlign = MCI->getDestAlign().valueOrOne(); 1601 SrcAlign = MCI->getSourceAlign().valueOrOne(); 1602 } else if (auto *MMI = dyn_cast<MemMoveInst>(&CI)) { 1603 DstAlign = MMI->getDestAlign().valueOrOne(); 1604 SrcAlign = MMI->getSourceAlign().valueOrOne(); 1605 } else { 1606 auto *MSI = cast<MemSetInst>(&CI); 1607 DstAlign = MSI->getDestAlign().valueOrOne(); 1608 } 1609 1610 if (Opcode != TargetOpcode::G_MEMCPY_INLINE) { 1611 // We need to propagate the tail call flag from the IR inst as an argument. 1612 // Otherwise, we have to pessimize and assume later that we cannot tail call 1613 // any memory intrinsics. 1614 ICall.addImm(CI.isTailCall() ? 1 : 0); 1615 } 1616 1617 // Create mem operands to store the alignment and volatile info. 1618 auto VolFlag = IsVol ? MachineMemOperand::MOVolatile : MachineMemOperand::MONone; 1619 ICall.addMemOperand(MF->getMachineMemOperand( 1620 MachinePointerInfo(CI.getArgOperand(0)), 1621 MachineMemOperand::MOStore | VolFlag, 1, DstAlign)); 1622 if (Opcode != TargetOpcode::G_MEMSET) 1623 ICall.addMemOperand(MF->getMachineMemOperand( 1624 MachinePointerInfo(CI.getArgOperand(1)), 1625 MachineMemOperand::MOLoad | VolFlag, 1, SrcAlign)); 1626 1627 return true; 1628 } 1629 1630 void IRTranslator::getStackGuard(Register DstReg, 1631 MachineIRBuilder &MIRBuilder) { 1632 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); 1633 MRI->setRegClass(DstReg, TRI->getPointerRegClass(*MF)); 1634 auto MIB = 1635 MIRBuilder.buildInstr(TargetOpcode::LOAD_STACK_GUARD, {DstReg}, {}); 1636 1637 auto &TLI = *MF->getSubtarget().getTargetLowering(); 1638 Value *Global = TLI.getSDagStackGuard(*MF->getFunction().getParent()); 1639 if (!Global) 1640 return; 1641 1642 unsigned AddrSpace = Global->getType()->getPointerAddressSpace(); 1643 LLT PtrTy = LLT::pointer(AddrSpace, DL->getPointerSizeInBits(AddrSpace)); 1644 1645 MachinePointerInfo MPInfo(Global); 1646 auto Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOInvariant | 1647 MachineMemOperand::MODereferenceable; 1648 MachineMemOperand *MemRef = MF->getMachineMemOperand( 1649 MPInfo, Flags, PtrTy, DL->getPointerABIAlignment(AddrSpace)); 1650 MIB.setMemRefs({MemRef}); 1651 } 1652 1653 bool IRTranslator::translateOverflowIntrinsic(const CallInst &CI, unsigned Op, 1654 MachineIRBuilder &MIRBuilder) { 1655 ArrayRef<Register> ResRegs = getOrCreateVRegs(CI); 1656 MIRBuilder.buildInstr( 1657 Op, {ResRegs[0], ResRegs[1]}, 1658 {getOrCreateVReg(*CI.getOperand(0)), getOrCreateVReg(*CI.getOperand(1))}); 1659 1660 return true; 1661 } 1662 1663 bool IRTranslator::translateFixedPointIntrinsic(unsigned Op, const CallInst &CI, 1664 MachineIRBuilder &MIRBuilder) { 1665 Register Dst = getOrCreateVReg(CI); 1666 Register Src0 = getOrCreateVReg(*CI.getOperand(0)); 1667 Register Src1 = getOrCreateVReg(*CI.getOperand(1)); 1668 uint64_t Scale = cast<ConstantInt>(CI.getOperand(2))->getZExtValue(); 1669 MIRBuilder.buildInstr(Op, {Dst}, { Src0, Src1, Scale }); 1670 return true; 1671 } 1672 1673 unsigned IRTranslator::getSimpleIntrinsicOpcode(Intrinsic::ID ID) { 1674 switch (ID) { 1675 default: 1676 break; 1677 case Intrinsic::bswap: 1678 return TargetOpcode::G_BSWAP; 1679 case Intrinsic::bitreverse: 1680 return TargetOpcode::G_BITREVERSE; 1681 case Intrinsic::fshl: 1682 return TargetOpcode::G_FSHL; 1683 case Intrinsic::fshr: 1684 return TargetOpcode::G_FSHR; 1685 case Intrinsic::ceil: 1686 return TargetOpcode::G_FCEIL; 1687 case Intrinsic::cos: 1688 return TargetOpcode::G_FCOS; 1689 case Intrinsic::ctpop: 1690 return TargetOpcode::G_CTPOP; 1691 case Intrinsic::exp: 1692 return TargetOpcode::G_FEXP; 1693 case Intrinsic::exp2: 1694 return TargetOpcode::G_FEXP2; 1695 case Intrinsic::fabs: 1696 return TargetOpcode::G_FABS; 1697 case Intrinsic::copysign: 1698 return TargetOpcode::G_FCOPYSIGN; 1699 case Intrinsic::minnum: 1700 return TargetOpcode::G_FMINNUM; 1701 case Intrinsic::maxnum: 1702 return TargetOpcode::G_FMAXNUM; 1703 case Intrinsic::minimum: 1704 return TargetOpcode::G_FMINIMUM; 1705 case Intrinsic::maximum: 1706 return TargetOpcode::G_FMAXIMUM; 1707 case Intrinsic::canonicalize: 1708 return TargetOpcode::G_FCANONICALIZE; 1709 case Intrinsic::floor: 1710 return TargetOpcode::G_FFLOOR; 1711 case Intrinsic::fma: 1712 return TargetOpcode::G_FMA; 1713 case Intrinsic::log: 1714 return TargetOpcode::G_FLOG; 1715 case Intrinsic::log2: 1716 return TargetOpcode::G_FLOG2; 1717 case Intrinsic::log10: 1718 return TargetOpcode::G_FLOG10; 1719 case Intrinsic::nearbyint: 1720 return TargetOpcode::G_FNEARBYINT; 1721 case Intrinsic::pow: 1722 return TargetOpcode::G_FPOW; 1723 case Intrinsic::powi: 1724 return TargetOpcode::G_FPOWI; 1725 case Intrinsic::rint: 1726 return TargetOpcode::G_FRINT; 1727 case Intrinsic::round: 1728 return TargetOpcode::G_INTRINSIC_ROUND; 1729 case Intrinsic::roundeven: 1730 return TargetOpcode::G_INTRINSIC_ROUNDEVEN; 1731 case Intrinsic::sin: 1732 return TargetOpcode::G_FSIN; 1733 case Intrinsic::sqrt: 1734 return TargetOpcode::G_FSQRT; 1735 case Intrinsic::trunc: 1736 return TargetOpcode::G_INTRINSIC_TRUNC; 1737 case Intrinsic::readcyclecounter: 1738 return TargetOpcode::G_READCYCLECOUNTER; 1739 case Intrinsic::ptrmask: 1740 return TargetOpcode::G_PTRMASK; 1741 case Intrinsic::lrint: 1742 return TargetOpcode::G_INTRINSIC_LRINT; 1743 // FADD/FMUL require checking the FMF, so are handled elsewhere. 1744 case Intrinsic::vector_reduce_fmin: 1745 return TargetOpcode::G_VECREDUCE_FMIN; 1746 case Intrinsic::vector_reduce_fmax: 1747 return TargetOpcode::G_VECREDUCE_FMAX; 1748 case Intrinsic::vector_reduce_add: 1749 return TargetOpcode::G_VECREDUCE_ADD; 1750 case Intrinsic::vector_reduce_mul: 1751 return TargetOpcode::G_VECREDUCE_MUL; 1752 case Intrinsic::vector_reduce_and: 1753 return TargetOpcode::G_VECREDUCE_AND; 1754 case Intrinsic::vector_reduce_or: 1755 return TargetOpcode::G_VECREDUCE_OR; 1756 case Intrinsic::vector_reduce_xor: 1757 return TargetOpcode::G_VECREDUCE_XOR; 1758 case Intrinsic::vector_reduce_smax: 1759 return TargetOpcode::G_VECREDUCE_SMAX; 1760 case Intrinsic::vector_reduce_smin: 1761 return TargetOpcode::G_VECREDUCE_SMIN; 1762 case Intrinsic::vector_reduce_umax: 1763 return TargetOpcode::G_VECREDUCE_UMAX; 1764 case Intrinsic::vector_reduce_umin: 1765 return TargetOpcode::G_VECREDUCE_UMIN; 1766 } 1767 return Intrinsic::not_intrinsic; 1768 } 1769 1770 bool IRTranslator::translateSimpleIntrinsic(const CallInst &CI, 1771 Intrinsic::ID ID, 1772 MachineIRBuilder &MIRBuilder) { 1773 1774 unsigned Op = getSimpleIntrinsicOpcode(ID); 1775 1776 // Is this a simple intrinsic? 1777 if (Op == Intrinsic::not_intrinsic) 1778 return false; 1779 1780 // Yes. Let's translate it. 1781 SmallVector<llvm::SrcOp, 4> VRegs; 1782 for (auto &Arg : CI.arg_operands()) 1783 VRegs.push_back(getOrCreateVReg(*Arg)); 1784 1785 MIRBuilder.buildInstr(Op, {getOrCreateVReg(CI)}, VRegs, 1786 MachineInstr::copyFlagsFromInstruction(CI)); 1787 return true; 1788 } 1789 1790 // TODO: Include ConstainedOps.def when all strict instructions are defined. 1791 static unsigned getConstrainedOpcode(Intrinsic::ID ID) { 1792 switch (ID) { 1793 case Intrinsic::experimental_constrained_fadd: 1794 return TargetOpcode::G_STRICT_FADD; 1795 case Intrinsic::experimental_constrained_fsub: 1796 return TargetOpcode::G_STRICT_FSUB; 1797 case Intrinsic::experimental_constrained_fmul: 1798 return TargetOpcode::G_STRICT_FMUL; 1799 case Intrinsic::experimental_constrained_fdiv: 1800 return TargetOpcode::G_STRICT_FDIV; 1801 case Intrinsic::experimental_constrained_frem: 1802 return TargetOpcode::G_STRICT_FREM; 1803 case Intrinsic::experimental_constrained_fma: 1804 return TargetOpcode::G_STRICT_FMA; 1805 case Intrinsic::experimental_constrained_sqrt: 1806 return TargetOpcode::G_STRICT_FSQRT; 1807 default: 1808 return 0; 1809 } 1810 } 1811 1812 bool IRTranslator::translateConstrainedFPIntrinsic( 1813 const ConstrainedFPIntrinsic &FPI, MachineIRBuilder &MIRBuilder) { 1814 fp::ExceptionBehavior EB = FPI.getExceptionBehavior().getValue(); 1815 1816 unsigned Opcode = getConstrainedOpcode(FPI.getIntrinsicID()); 1817 if (!Opcode) 1818 return false; 1819 1820 unsigned Flags = MachineInstr::copyFlagsFromInstruction(FPI); 1821 if (EB == fp::ExceptionBehavior::ebIgnore) 1822 Flags |= MachineInstr::NoFPExcept; 1823 1824 SmallVector<llvm::SrcOp, 4> VRegs; 1825 VRegs.push_back(getOrCreateVReg(*FPI.getArgOperand(0))); 1826 if (!FPI.isUnaryOp()) 1827 VRegs.push_back(getOrCreateVReg(*FPI.getArgOperand(1))); 1828 if (FPI.isTernaryOp()) 1829 VRegs.push_back(getOrCreateVReg(*FPI.getArgOperand(2))); 1830 1831 MIRBuilder.buildInstr(Opcode, {getOrCreateVReg(FPI)}, VRegs, Flags); 1832 return true; 1833 } 1834 1835 bool IRTranslator::translateKnownIntrinsic(const CallInst &CI, Intrinsic::ID ID, 1836 MachineIRBuilder &MIRBuilder) { 1837 if (auto *MI = dyn_cast<AnyMemIntrinsic>(&CI)) { 1838 if (ORE->enabled()) { 1839 const Function &F = *MI->getParent()->getParent(); 1840 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 1841 if (MemoryOpRemark::canHandle(MI, TLI)) { 1842 MemoryOpRemark R(*ORE, "gisel-irtranslator-memsize", *DL, TLI); 1843 R.visit(MI); 1844 } 1845 } 1846 } 1847 1848 // If this is a simple intrinsic (that is, we just need to add a def of 1849 // a vreg, and uses for each arg operand, then translate it. 1850 if (translateSimpleIntrinsic(CI, ID, MIRBuilder)) 1851 return true; 1852 1853 switch (ID) { 1854 default: 1855 break; 1856 case Intrinsic::lifetime_start: 1857 case Intrinsic::lifetime_end: { 1858 // No stack colouring in O0, discard region information. 1859 if (MF->getTarget().getOptLevel() == CodeGenOpt::None) 1860 return true; 1861 1862 unsigned Op = ID == Intrinsic::lifetime_start ? TargetOpcode::LIFETIME_START 1863 : TargetOpcode::LIFETIME_END; 1864 1865 // Get the underlying objects for the location passed on the lifetime 1866 // marker. 1867 SmallVector<const Value *, 4> Allocas; 1868 getUnderlyingObjects(CI.getArgOperand(1), Allocas); 1869 1870 // Iterate over each underlying object, creating lifetime markers for each 1871 // static alloca. Quit if we find a non-static alloca. 1872 for (const Value *V : Allocas) { 1873 const AllocaInst *AI = dyn_cast<AllocaInst>(V); 1874 if (!AI) 1875 continue; 1876 1877 if (!AI->isStaticAlloca()) 1878 return true; 1879 1880 MIRBuilder.buildInstr(Op).addFrameIndex(getOrCreateFrameIndex(*AI)); 1881 } 1882 return true; 1883 } 1884 case Intrinsic::dbg_declare: { 1885 const DbgDeclareInst &DI = cast<DbgDeclareInst>(CI); 1886 assert(DI.getVariable() && "Missing variable"); 1887 1888 const Value *Address = DI.getAddress(); 1889 if (!Address || isa<UndefValue>(Address)) { 1890 LLVM_DEBUG(dbgs() << "Dropping debug info for " << DI << "\n"); 1891 return true; 1892 } 1893 1894 assert(DI.getVariable()->isValidLocationForIntrinsic( 1895 MIRBuilder.getDebugLoc()) && 1896 "Expected inlined-at fields to agree"); 1897 auto AI = dyn_cast<AllocaInst>(Address); 1898 if (AI && AI->isStaticAlloca()) { 1899 // Static allocas are tracked at the MF level, no need for DBG_VALUE 1900 // instructions (in fact, they get ignored if they *do* exist). 1901 MF->setVariableDbgInfo(DI.getVariable(), DI.getExpression(), 1902 getOrCreateFrameIndex(*AI), DI.getDebugLoc()); 1903 } else { 1904 // A dbg.declare describes the address of a source variable, so lower it 1905 // into an indirect DBG_VALUE. 1906 MIRBuilder.buildIndirectDbgValue(getOrCreateVReg(*Address), 1907 DI.getVariable(), DI.getExpression()); 1908 } 1909 return true; 1910 } 1911 case Intrinsic::dbg_label: { 1912 const DbgLabelInst &DI = cast<DbgLabelInst>(CI); 1913 assert(DI.getLabel() && "Missing label"); 1914 1915 assert(DI.getLabel()->isValidLocationForIntrinsic( 1916 MIRBuilder.getDebugLoc()) && 1917 "Expected inlined-at fields to agree"); 1918 1919 MIRBuilder.buildDbgLabel(DI.getLabel()); 1920 return true; 1921 } 1922 case Intrinsic::vaend: 1923 // No target I know of cares about va_end. Certainly no in-tree target 1924 // does. Simplest intrinsic ever! 1925 return true; 1926 case Intrinsic::vastart: { 1927 auto &TLI = *MF->getSubtarget().getTargetLowering(); 1928 Value *Ptr = CI.getArgOperand(0); 1929 unsigned ListSize = TLI.getVaListSizeInBits(*DL) / 8; 1930 1931 // FIXME: Get alignment 1932 MIRBuilder.buildInstr(TargetOpcode::G_VASTART, {}, {getOrCreateVReg(*Ptr)}) 1933 .addMemOperand(MF->getMachineMemOperand(MachinePointerInfo(Ptr), 1934 MachineMemOperand::MOStore, 1935 ListSize, Align(1))); 1936 return true; 1937 } 1938 case Intrinsic::dbg_value: { 1939 // This form of DBG_VALUE is target-independent. 1940 const DbgValueInst &DI = cast<DbgValueInst>(CI); 1941 const Value *V = DI.getValue(); 1942 assert(DI.getVariable()->isValidLocationForIntrinsic( 1943 MIRBuilder.getDebugLoc()) && 1944 "Expected inlined-at fields to agree"); 1945 if (!V || DI.hasArgList()) { 1946 // DI cannot produce a valid DBG_VALUE, so produce an undef DBG_VALUE to 1947 // terminate any prior location. 1948 MIRBuilder.buildIndirectDbgValue(0, DI.getVariable(), DI.getExpression()); 1949 } else if (const auto *CI = dyn_cast<Constant>(V)) { 1950 MIRBuilder.buildConstDbgValue(*CI, DI.getVariable(), DI.getExpression()); 1951 } else { 1952 for (Register Reg : getOrCreateVRegs(*V)) { 1953 // FIXME: This does not handle register-indirect values at offset 0. The 1954 // direct/indirect thing shouldn't really be handled by something as 1955 // implicit as reg+noreg vs reg+imm in the first place, but it seems 1956 // pretty baked in right now. 1957 MIRBuilder.buildDirectDbgValue(Reg, DI.getVariable(), DI.getExpression()); 1958 } 1959 } 1960 return true; 1961 } 1962 case Intrinsic::uadd_with_overflow: 1963 return translateOverflowIntrinsic(CI, TargetOpcode::G_UADDO, MIRBuilder); 1964 case Intrinsic::sadd_with_overflow: 1965 return translateOverflowIntrinsic(CI, TargetOpcode::G_SADDO, MIRBuilder); 1966 case Intrinsic::usub_with_overflow: 1967 return translateOverflowIntrinsic(CI, TargetOpcode::G_USUBO, MIRBuilder); 1968 case Intrinsic::ssub_with_overflow: 1969 return translateOverflowIntrinsic(CI, TargetOpcode::G_SSUBO, MIRBuilder); 1970 case Intrinsic::umul_with_overflow: 1971 return translateOverflowIntrinsic(CI, TargetOpcode::G_UMULO, MIRBuilder); 1972 case Intrinsic::smul_with_overflow: 1973 return translateOverflowIntrinsic(CI, TargetOpcode::G_SMULO, MIRBuilder); 1974 case Intrinsic::uadd_sat: 1975 return translateBinaryOp(TargetOpcode::G_UADDSAT, CI, MIRBuilder); 1976 case Intrinsic::sadd_sat: 1977 return translateBinaryOp(TargetOpcode::G_SADDSAT, CI, MIRBuilder); 1978 case Intrinsic::usub_sat: 1979 return translateBinaryOp(TargetOpcode::G_USUBSAT, CI, MIRBuilder); 1980 case Intrinsic::ssub_sat: 1981 return translateBinaryOp(TargetOpcode::G_SSUBSAT, CI, MIRBuilder); 1982 case Intrinsic::ushl_sat: 1983 return translateBinaryOp(TargetOpcode::G_USHLSAT, CI, MIRBuilder); 1984 case Intrinsic::sshl_sat: 1985 return translateBinaryOp(TargetOpcode::G_SSHLSAT, CI, MIRBuilder); 1986 case Intrinsic::umin: 1987 return translateBinaryOp(TargetOpcode::G_UMIN, CI, MIRBuilder); 1988 case Intrinsic::umax: 1989 return translateBinaryOp(TargetOpcode::G_UMAX, CI, MIRBuilder); 1990 case Intrinsic::smin: 1991 return translateBinaryOp(TargetOpcode::G_SMIN, CI, MIRBuilder); 1992 case Intrinsic::smax: 1993 return translateBinaryOp(TargetOpcode::G_SMAX, CI, MIRBuilder); 1994 case Intrinsic::abs: 1995 // TODO: Preserve "int min is poison" arg in GMIR? 1996 return translateUnaryOp(TargetOpcode::G_ABS, CI, MIRBuilder); 1997 case Intrinsic::smul_fix: 1998 return translateFixedPointIntrinsic(TargetOpcode::G_SMULFIX, CI, MIRBuilder); 1999 case Intrinsic::umul_fix: 2000 return translateFixedPointIntrinsic(TargetOpcode::G_UMULFIX, CI, MIRBuilder); 2001 case Intrinsic::smul_fix_sat: 2002 return translateFixedPointIntrinsic(TargetOpcode::G_SMULFIXSAT, CI, MIRBuilder); 2003 case Intrinsic::umul_fix_sat: 2004 return translateFixedPointIntrinsic(TargetOpcode::G_UMULFIXSAT, CI, MIRBuilder); 2005 case Intrinsic::sdiv_fix: 2006 return translateFixedPointIntrinsic(TargetOpcode::G_SDIVFIX, CI, MIRBuilder); 2007 case Intrinsic::udiv_fix: 2008 return translateFixedPointIntrinsic(TargetOpcode::G_UDIVFIX, CI, MIRBuilder); 2009 case Intrinsic::sdiv_fix_sat: 2010 return translateFixedPointIntrinsic(TargetOpcode::G_SDIVFIXSAT, CI, MIRBuilder); 2011 case Intrinsic::udiv_fix_sat: 2012 return translateFixedPointIntrinsic(TargetOpcode::G_UDIVFIXSAT, CI, MIRBuilder); 2013 case Intrinsic::fmuladd: { 2014 const TargetMachine &TM = MF->getTarget(); 2015 const TargetLowering &TLI = *MF->getSubtarget().getTargetLowering(); 2016 Register Dst = getOrCreateVReg(CI); 2017 Register Op0 = getOrCreateVReg(*CI.getArgOperand(0)); 2018 Register Op1 = getOrCreateVReg(*CI.getArgOperand(1)); 2019 Register Op2 = getOrCreateVReg(*CI.getArgOperand(2)); 2020 if (TM.Options.AllowFPOpFusion != FPOpFusion::Strict && 2021 TLI.isFMAFasterThanFMulAndFAdd(*MF, 2022 TLI.getValueType(*DL, CI.getType()))) { 2023 // TODO: Revisit this to see if we should move this part of the 2024 // lowering to the combiner. 2025 MIRBuilder.buildFMA(Dst, Op0, Op1, Op2, 2026 MachineInstr::copyFlagsFromInstruction(CI)); 2027 } else { 2028 LLT Ty = getLLTForType(*CI.getType(), *DL); 2029 auto FMul = MIRBuilder.buildFMul( 2030 Ty, Op0, Op1, MachineInstr::copyFlagsFromInstruction(CI)); 2031 MIRBuilder.buildFAdd(Dst, FMul, Op2, 2032 MachineInstr::copyFlagsFromInstruction(CI)); 2033 } 2034 return true; 2035 } 2036 case Intrinsic::convert_from_fp16: 2037 // FIXME: This intrinsic should probably be removed from the IR. 2038 MIRBuilder.buildFPExt(getOrCreateVReg(CI), 2039 getOrCreateVReg(*CI.getArgOperand(0)), 2040 MachineInstr::copyFlagsFromInstruction(CI)); 2041 return true; 2042 case Intrinsic::convert_to_fp16: 2043 // FIXME: This intrinsic should probably be removed from the IR. 2044 MIRBuilder.buildFPTrunc(getOrCreateVReg(CI), 2045 getOrCreateVReg(*CI.getArgOperand(0)), 2046 MachineInstr::copyFlagsFromInstruction(CI)); 2047 return true; 2048 case Intrinsic::memcpy_inline: 2049 return translateMemFunc(CI, MIRBuilder, TargetOpcode::G_MEMCPY_INLINE); 2050 case Intrinsic::memcpy: 2051 return translateMemFunc(CI, MIRBuilder, TargetOpcode::G_MEMCPY); 2052 case Intrinsic::memmove: 2053 return translateMemFunc(CI, MIRBuilder, TargetOpcode::G_MEMMOVE); 2054 case Intrinsic::memset: 2055 return translateMemFunc(CI, MIRBuilder, TargetOpcode::G_MEMSET); 2056 case Intrinsic::eh_typeid_for: { 2057 GlobalValue *GV = ExtractTypeInfo(CI.getArgOperand(0)); 2058 Register Reg = getOrCreateVReg(CI); 2059 unsigned TypeID = MF->getTypeIDFor(GV); 2060 MIRBuilder.buildConstant(Reg, TypeID); 2061 return true; 2062 } 2063 case Intrinsic::objectsize: 2064 llvm_unreachable("llvm.objectsize.* should have been lowered already"); 2065 2066 case Intrinsic::is_constant: 2067 llvm_unreachable("llvm.is.constant.* should have been lowered already"); 2068 2069 case Intrinsic::stackguard: 2070 getStackGuard(getOrCreateVReg(CI), MIRBuilder); 2071 return true; 2072 case Intrinsic::stackprotector: { 2073 LLT PtrTy = getLLTForType(*CI.getArgOperand(0)->getType(), *DL); 2074 Register GuardVal = MRI->createGenericVirtualRegister(PtrTy); 2075 getStackGuard(GuardVal, MIRBuilder); 2076 2077 AllocaInst *Slot = cast<AllocaInst>(CI.getArgOperand(1)); 2078 int FI = getOrCreateFrameIndex(*Slot); 2079 MF->getFrameInfo().setStackProtectorIndex(FI); 2080 2081 MIRBuilder.buildStore( 2082 GuardVal, getOrCreateVReg(*Slot), 2083 *MF->getMachineMemOperand(MachinePointerInfo::getFixedStack(*MF, FI), 2084 MachineMemOperand::MOStore | 2085 MachineMemOperand::MOVolatile, 2086 PtrTy, Align(8))); 2087 return true; 2088 } 2089 case Intrinsic::stacksave: { 2090 // Save the stack pointer to the location provided by the intrinsic. 2091 Register Reg = getOrCreateVReg(CI); 2092 Register StackPtr = MF->getSubtarget() 2093 .getTargetLowering() 2094 ->getStackPointerRegisterToSaveRestore(); 2095 2096 // If the target doesn't specify a stack pointer, then fall back. 2097 if (!StackPtr) 2098 return false; 2099 2100 MIRBuilder.buildCopy(Reg, StackPtr); 2101 return true; 2102 } 2103 case Intrinsic::stackrestore: { 2104 // Restore the stack pointer from the location provided by the intrinsic. 2105 Register Reg = getOrCreateVReg(*CI.getArgOperand(0)); 2106 Register StackPtr = MF->getSubtarget() 2107 .getTargetLowering() 2108 ->getStackPointerRegisterToSaveRestore(); 2109 2110 // If the target doesn't specify a stack pointer, then fall back. 2111 if (!StackPtr) 2112 return false; 2113 2114 MIRBuilder.buildCopy(StackPtr, Reg); 2115 return true; 2116 } 2117 case Intrinsic::cttz: 2118 case Intrinsic::ctlz: { 2119 ConstantInt *Cst = cast<ConstantInt>(CI.getArgOperand(1)); 2120 bool isTrailing = ID == Intrinsic::cttz; 2121 unsigned Opcode = isTrailing 2122 ? Cst->isZero() ? TargetOpcode::G_CTTZ 2123 : TargetOpcode::G_CTTZ_ZERO_UNDEF 2124 : Cst->isZero() ? TargetOpcode::G_CTLZ 2125 : TargetOpcode::G_CTLZ_ZERO_UNDEF; 2126 MIRBuilder.buildInstr(Opcode, {getOrCreateVReg(CI)}, 2127 {getOrCreateVReg(*CI.getArgOperand(0))}); 2128 return true; 2129 } 2130 case Intrinsic::invariant_start: { 2131 LLT PtrTy = getLLTForType(*CI.getArgOperand(0)->getType(), *DL); 2132 Register Undef = MRI->createGenericVirtualRegister(PtrTy); 2133 MIRBuilder.buildUndef(Undef); 2134 return true; 2135 } 2136 case Intrinsic::invariant_end: 2137 return true; 2138 case Intrinsic::expect: 2139 case Intrinsic::annotation: 2140 case Intrinsic::ptr_annotation: 2141 case Intrinsic::launder_invariant_group: 2142 case Intrinsic::strip_invariant_group: { 2143 // Drop the intrinsic, but forward the value. 2144 MIRBuilder.buildCopy(getOrCreateVReg(CI), 2145 getOrCreateVReg(*CI.getArgOperand(0))); 2146 return true; 2147 } 2148 case Intrinsic::assume: 2149 case Intrinsic::experimental_noalias_scope_decl: 2150 case Intrinsic::var_annotation: 2151 case Intrinsic::sideeffect: 2152 // Discard annotate attributes, assumptions, and artificial side-effects. 2153 return true; 2154 case Intrinsic::read_volatile_register: 2155 case Intrinsic::read_register: { 2156 Value *Arg = CI.getArgOperand(0); 2157 MIRBuilder 2158 .buildInstr(TargetOpcode::G_READ_REGISTER, {getOrCreateVReg(CI)}, {}) 2159 .addMetadata(cast<MDNode>(cast<MetadataAsValue>(Arg)->getMetadata())); 2160 return true; 2161 } 2162 case Intrinsic::write_register: { 2163 Value *Arg = CI.getArgOperand(0); 2164 MIRBuilder.buildInstr(TargetOpcode::G_WRITE_REGISTER) 2165 .addMetadata(cast<MDNode>(cast<MetadataAsValue>(Arg)->getMetadata())) 2166 .addUse(getOrCreateVReg(*CI.getArgOperand(1))); 2167 return true; 2168 } 2169 case Intrinsic::localescape: { 2170 MachineBasicBlock &EntryMBB = MF->front(); 2171 StringRef EscapedName = GlobalValue::dropLLVMManglingEscape(MF->getName()); 2172 2173 // Directly emit some LOCAL_ESCAPE machine instrs. Label assignment emission 2174 // is the same on all targets. 2175 for (unsigned Idx = 0, E = CI.getNumArgOperands(); Idx < E; ++Idx) { 2176 Value *Arg = CI.getArgOperand(Idx)->stripPointerCasts(); 2177 if (isa<ConstantPointerNull>(Arg)) 2178 continue; // Skip null pointers. They represent a hole in index space. 2179 2180 int FI = getOrCreateFrameIndex(*cast<AllocaInst>(Arg)); 2181 MCSymbol *FrameAllocSym = 2182 MF->getMMI().getContext().getOrCreateFrameAllocSymbol(EscapedName, 2183 Idx); 2184 2185 // This should be inserted at the start of the entry block. 2186 auto LocalEscape = 2187 MIRBuilder.buildInstrNoInsert(TargetOpcode::LOCAL_ESCAPE) 2188 .addSym(FrameAllocSym) 2189 .addFrameIndex(FI); 2190 2191 EntryMBB.insert(EntryMBB.begin(), LocalEscape); 2192 } 2193 2194 return true; 2195 } 2196 case Intrinsic::vector_reduce_fadd: 2197 case Intrinsic::vector_reduce_fmul: { 2198 // Need to check for the reassoc flag to decide whether we want a 2199 // sequential reduction opcode or not. 2200 Register Dst = getOrCreateVReg(CI); 2201 Register ScalarSrc = getOrCreateVReg(*CI.getArgOperand(0)); 2202 Register VecSrc = getOrCreateVReg(*CI.getArgOperand(1)); 2203 unsigned Opc = 0; 2204 if (!CI.hasAllowReassoc()) { 2205 // The sequential ordering case. 2206 Opc = ID == Intrinsic::vector_reduce_fadd 2207 ? TargetOpcode::G_VECREDUCE_SEQ_FADD 2208 : TargetOpcode::G_VECREDUCE_SEQ_FMUL; 2209 MIRBuilder.buildInstr(Opc, {Dst}, {ScalarSrc, VecSrc}, 2210 MachineInstr::copyFlagsFromInstruction(CI)); 2211 return true; 2212 } 2213 // We split the operation into a separate G_FADD/G_FMUL + the reduce, 2214 // since the associativity doesn't matter. 2215 unsigned ScalarOpc; 2216 if (ID == Intrinsic::vector_reduce_fadd) { 2217 Opc = TargetOpcode::G_VECREDUCE_FADD; 2218 ScalarOpc = TargetOpcode::G_FADD; 2219 } else { 2220 Opc = TargetOpcode::G_VECREDUCE_FMUL; 2221 ScalarOpc = TargetOpcode::G_FMUL; 2222 } 2223 LLT DstTy = MRI->getType(Dst); 2224 auto Rdx = MIRBuilder.buildInstr( 2225 Opc, {DstTy}, {VecSrc}, MachineInstr::copyFlagsFromInstruction(CI)); 2226 MIRBuilder.buildInstr(ScalarOpc, {Dst}, {ScalarSrc, Rdx}, 2227 MachineInstr::copyFlagsFromInstruction(CI)); 2228 2229 return true; 2230 } 2231 #define INSTRUCTION(NAME, NARG, ROUND_MODE, INTRINSIC) \ 2232 case Intrinsic::INTRINSIC: 2233 #include "llvm/IR/ConstrainedOps.def" 2234 return translateConstrainedFPIntrinsic(cast<ConstrainedFPIntrinsic>(CI), 2235 MIRBuilder); 2236 2237 } 2238 return false; 2239 } 2240 2241 bool IRTranslator::translateInlineAsm(const CallBase &CB, 2242 MachineIRBuilder &MIRBuilder) { 2243 2244 const InlineAsmLowering *ALI = MF->getSubtarget().getInlineAsmLowering(); 2245 2246 if (!ALI) { 2247 LLVM_DEBUG( 2248 dbgs() << "Inline asm lowering is not supported for this target yet\n"); 2249 return false; 2250 } 2251 2252 return ALI->lowerInlineAsm( 2253 MIRBuilder, CB, [&](const Value &Val) { return getOrCreateVRegs(Val); }); 2254 } 2255 2256 bool IRTranslator::translateCallBase(const CallBase &CB, 2257 MachineIRBuilder &MIRBuilder) { 2258 ArrayRef<Register> Res = getOrCreateVRegs(CB); 2259 2260 SmallVector<ArrayRef<Register>, 8> Args; 2261 Register SwiftInVReg = 0; 2262 Register SwiftErrorVReg = 0; 2263 for (auto &Arg : CB.args()) { 2264 if (CLI->supportSwiftError() && isSwiftError(Arg)) { 2265 assert(SwiftInVReg == 0 && "Expected only one swift error argument"); 2266 LLT Ty = getLLTForType(*Arg->getType(), *DL); 2267 SwiftInVReg = MRI->createGenericVirtualRegister(Ty); 2268 MIRBuilder.buildCopy(SwiftInVReg, SwiftError.getOrCreateVRegUseAt( 2269 &CB, &MIRBuilder.getMBB(), Arg)); 2270 Args.emplace_back(makeArrayRef(SwiftInVReg)); 2271 SwiftErrorVReg = 2272 SwiftError.getOrCreateVRegDefAt(&CB, &MIRBuilder.getMBB(), Arg); 2273 continue; 2274 } 2275 Args.push_back(getOrCreateVRegs(*Arg)); 2276 } 2277 2278 if (auto *CI = dyn_cast<CallInst>(&CB)) { 2279 if (ORE->enabled()) { 2280 const Function &F = *CI->getParent()->getParent(); 2281 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 2282 if (MemoryOpRemark::canHandle(CI, TLI)) { 2283 MemoryOpRemark R(*ORE, "gisel-irtranslator-memsize", *DL, TLI); 2284 R.visit(CI); 2285 } 2286 } 2287 } 2288 2289 // We don't set HasCalls on MFI here yet because call lowering may decide to 2290 // optimize into tail calls. Instead, we defer that to selection where a final 2291 // scan is done to check if any instructions are calls. 2292 bool Success = 2293 CLI->lowerCall(MIRBuilder, CB, Res, Args, SwiftErrorVReg, 2294 [&]() { return getOrCreateVReg(*CB.getCalledOperand()); }); 2295 2296 // Check if we just inserted a tail call. 2297 if (Success) { 2298 assert(!HasTailCall && "Can't tail call return twice from block?"); 2299 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); 2300 HasTailCall = TII->isTailCall(*std::prev(MIRBuilder.getInsertPt())); 2301 } 2302 2303 return Success; 2304 } 2305 2306 bool IRTranslator::translateCall(const User &U, MachineIRBuilder &MIRBuilder) { 2307 const CallInst &CI = cast<CallInst>(U); 2308 auto TII = MF->getTarget().getIntrinsicInfo(); 2309 const Function *F = CI.getCalledFunction(); 2310 2311 // FIXME: support Windows dllimport function calls. 2312 if (F && (F->hasDLLImportStorageClass() || 2313 (MF->getTarget().getTargetTriple().isOSWindows() && 2314 F->hasExternalWeakLinkage()))) 2315 return false; 2316 2317 // FIXME: support control flow guard targets. 2318 if (CI.countOperandBundlesOfType(LLVMContext::OB_cfguardtarget)) 2319 return false; 2320 2321 if (CI.isInlineAsm()) 2322 return translateInlineAsm(CI, MIRBuilder); 2323 2324 Intrinsic::ID ID = Intrinsic::not_intrinsic; 2325 if (F && F->isIntrinsic()) { 2326 ID = F->getIntrinsicID(); 2327 if (TII && ID == Intrinsic::not_intrinsic) 2328 ID = static_cast<Intrinsic::ID>(TII->getIntrinsicID(F)); 2329 } 2330 2331 if (!F || !F->isIntrinsic() || ID == Intrinsic::not_intrinsic) 2332 return translateCallBase(CI, MIRBuilder); 2333 2334 assert(ID != Intrinsic::not_intrinsic && "unknown intrinsic"); 2335 2336 if (translateKnownIntrinsic(CI, ID, MIRBuilder)) 2337 return true; 2338 2339 ArrayRef<Register> ResultRegs; 2340 if (!CI.getType()->isVoidTy()) 2341 ResultRegs = getOrCreateVRegs(CI); 2342 2343 // Ignore the callsite attributes. Backend code is most likely not expecting 2344 // an intrinsic to sometimes have side effects and sometimes not. 2345 MachineInstrBuilder MIB = 2346 MIRBuilder.buildIntrinsic(ID, ResultRegs, !F->doesNotAccessMemory()); 2347 if (isa<FPMathOperator>(CI)) 2348 MIB->copyIRFlags(CI); 2349 2350 for (auto &Arg : enumerate(CI.arg_operands())) { 2351 // If this is required to be an immediate, don't materialize it in a 2352 // register. 2353 if (CI.paramHasAttr(Arg.index(), Attribute::ImmArg)) { 2354 if (ConstantInt *CI = dyn_cast<ConstantInt>(Arg.value())) { 2355 // imm arguments are more convenient than cimm (and realistically 2356 // probably sufficient), so use them. 2357 assert(CI->getBitWidth() <= 64 && 2358 "large intrinsic immediates not handled"); 2359 MIB.addImm(CI->getSExtValue()); 2360 } else { 2361 MIB.addFPImm(cast<ConstantFP>(Arg.value())); 2362 } 2363 } else if (auto MD = dyn_cast<MetadataAsValue>(Arg.value())) { 2364 auto *MDN = dyn_cast<MDNode>(MD->getMetadata()); 2365 if (!MDN) // This was probably an MDString. 2366 return false; 2367 MIB.addMetadata(MDN); 2368 } else { 2369 ArrayRef<Register> VRegs = getOrCreateVRegs(*Arg.value()); 2370 if (VRegs.size() > 1) 2371 return false; 2372 MIB.addUse(VRegs[0]); 2373 } 2374 } 2375 2376 // Add a MachineMemOperand if it is a target mem intrinsic. 2377 const TargetLowering &TLI = *MF->getSubtarget().getTargetLowering(); 2378 TargetLowering::IntrinsicInfo Info; 2379 // TODO: Add a GlobalISel version of getTgtMemIntrinsic. 2380 if (TLI.getTgtMemIntrinsic(Info, CI, *MF, ID)) { 2381 Align Alignment = Info.align.getValueOr( 2382 DL->getABITypeAlign(Info.memVT.getTypeForEVT(F->getContext()))); 2383 LLT MemTy = Info.memVT.isSimple() 2384 ? getLLTForMVT(Info.memVT.getSimpleVT()) 2385 : LLT::scalar(Info.memVT.getStoreSizeInBits()); 2386 MIB.addMemOperand(MF->getMachineMemOperand(MachinePointerInfo(Info.ptrVal), 2387 Info.flags, MemTy, Alignment)); 2388 } 2389 2390 return true; 2391 } 2392 2393 bool IRTranslator::findUnwindDestinations( 2394 const BasicBlock *EHPadBB, 2395 BranchProbability Prob, 2396 SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>> 2397 &UnwindDests) { 2398 EHPersonality Personality = classifyEHPersonality( 2399 EHPadBB->getParent()->getFunction().getPersonalityFn()); 2400 bool IsMSVCCXX = Personality == EHPersonality::MSVC_CXX; 2401 bool IsCoreCLR = Personality == EHPersonality::CoreCLR; 2402 bool IsWasmCXX = Personality == EHPersonality::Wasm_CXX; 2403 bool IsSEH = isAsynchronousEHPersonality(Personality); 2404 2405 if (IsWasmCXX) { 2406 // Ignore this for now. 2407 return false; 2408 } 2409 2410 while (EHPadBB) { 2411 const Instruction *Pad = EHPadBB->getFirstNonPHI(); 2412 BasicBlock *NewEHPadBB = nullptr; 2413 if (isa<LandingPadInst>(Pad)) { 2414 // Stop on landingpads. They are not funclets. 2415 UnwindDests.emplace_back(&getMBB(*EHPadBB), Prob); 2416 break; 2417 } 2418 if (isa<CleanupPadInst>(Pad)) { 2419 // Stop on cleanup pads. Cleanups are always funclet entries for all known 2420 // personalities. 2421 UnwindDests.emplace_back(&getMBB(*EHPadBB), Prob); 2422 UnwindDests.back().first->setIsEHScopeEntry(); 2423 UnwindDests.back().first->setIsEHFuncletEntry(); 2424 break; 2425 } 2426 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) { 2427 // Add the catchpad handlers to the possible destinations. 2428 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) { 2429 UnwindDests.emplace_back(&getMBB(*CatchPadBB), Prob); 2430 // For MSVC++ and the CLR, catchblocks are funclets and need prologues. 2431 if (IsMSVCCXX || IsCoreCLR) 2432 UnwindDests.back().first->setIsEHFuncletEntry(); 2433 if (!IsSEH) 2434 UnwindDests.back().first->setIsEHScopeEntry(); 2435 } 2436 NewEHPadBB = CatchSwitch->getUnwindDest(); 2437 } else { 2438 continue; 2439 } 2440 2441 BranchProbabilityInfo *BPI = FuncInfo.BPI; 2442 if (BPI && NewEHPadBB) 2443 Prob *= BPI->getEdgeProbability(EHPadBB, NewEHPadBB); 2444 EHPadBB = NewEHPadBB; 2445 } 2446 return true; 2447 } 2448 2449 bool IRTranslator::translateInvoke(const User &U, 2450 MachineIRBuilder &MIRBuilder) { 2451 const InvokeInst &I = cast<InvokeInst>(U); 2452 MCContext &Context = MF->getContext(); 2453 2454 const BasicBlock *ReturnBB = I.getSuccessor(0); 2455 const BasicBlock *EHPadBB = I.getSuccessor(1); 2456 2457 const Function *Fn = I.getCalledFunction(); 2458 2459 // FIXME: support invoking patchpoint and statepoint intrinsics. 2460 if (Fn && Fn->isIntrinsic()) 2461 return false; 2462 2463 // FIXME: support whatever these are. 2464 if (I.countOperandBundlesOfType(LLVMContext::OB_deopt)) 2465 return false; 2466 2467 // FIXME: support control flow guard targets. 2468 if (I.countOperandBundlesOfType(LLVMContext::OB_cfguardtarget)) 2469 return false; 2470 2471 // FIXME: support Windows exception handling. 2472 if (!isa<LandingPadInst>(EHPadBB->getFirstNonPHI())) 2473 return false; 2474 2475 bool LowerInlineAsm = false; 2476 if (I.isInlineAsm()) { 2477 const InlineAsm *IA = cast<InlineAsm>(I.getCalledOperand()); 2478 if (!IA->canThrow()) { 2479 // Fast path without emitting EH_LABELs. 2480 2481 if (!translateInlineAsm(I, MIRBuilder)) 2482 return false; 2483 2484 MachineBasicBlock *InvokeMBB = &MIRBuilder.getMBB(), 2485 *ReturnMBB = &getMBB(*ReturnBB); 2486 2487 // Update successor info. 2488 addSuccessorWithProb(InvokeMBB, ReturnMBB, BranchProbability::getOne()); 2489 2490 MIRBuilder.buildBr(*ReturnMBB); 2491 return true; 2492 } else { 2493 LowerInlineAsm = true; 2494 } 2495 } 2496 2497 // Emit the actual call, bracketed by EH_LABELs so that the MF knows about 2498 // the region covered by the try. 2499 MCSymbol *BeginSymbol = Context.createTempSymbol(); 2500 MIRBuilder.buildInstr(TargetOpcode::EH_LABEL).addSym(BeginSymbol); 2501 2502 if (LowerInlineAsm) { 2503 if (!translateInlineAsm(I, MIRBuilder)) 2504 return false; 2505 } else if (!translateCallBase(I, MIRBuilder)) 2506 return false; 2507 2508 MCSymbol *EndSymbol = Context.createTempSymbol(); 2509 MIRBuilder.buildInstr(TargetOpcode::EH_LABEL).addSym(EndSymbol); 2510 2511 SmallVector<std::pair<MachineBasicBlock *, BranchProbability>, 1> UnwindDests; 2512 BranchProbabilityInfo *BPI = FuncInfo.BPI; 2513 MachineBasicBlock *InvokeMBB = &MIRBuilder.getMBB(); 2514 BranchProbability EHPadBBProb = 2515 BPI ? BPI->getEdgeProbability(InvokeMBB->getBasicBlock(), EHPadBB) 2516 : BranchProbability::getZero(); 2517 2518 if (!findUnwindDestinations(EHPadBB, EHPadBBProb, UnwindDests)) 2519 return false; 2520 2521 MachineBasicBlock &EHPadMBB = getMBB(*EHPadBB), 2522 &ReturnMBB = getMBB(*ReturnBB); 2523 // Update successor info. 2524 addSuccessorWithProb(InvokeMBB, &ReturnMBB); 2525 for (auto &UnwindDest : UnwindDests) { 2526 UnwindDest.first->setIsEHPad(); 2527 addSuccessorWithProb(InvokeMBB, UnwindDest.first, UnwindDest.second); 2528 } 2529 InvokeMBB->normalizeSuccProbs(); 2530 2531 MF->addInvoke(&EHPadMBB, BeginSymbol, EndSymbol); 2532 MIRBuilder.buildBr(ReturnMBB); 2533 return true; 2534 } 2535 2536 bool IRTranslator::translateCallBr(const User &U, 2537 MachineIRBuilder &MIRBuilder) { 2538 // FIXME: Implement this. 2539 return false; 2540 } 2541 2542 bool IRTranslator::translateLandingPad(const User &U, 2543 MachineIRBuilder &MIRBuilder) { 2544 const LandingPadInst &LP = cast<LandingPadInst>(U); 2545 2546 MachineBasicBlock &MBB = MIRBuilder.getMBB(); 2547 2548 MBB.setIsEHPad(); 2549 2550 // If there aren't registers to copy the values into (e.g., during SjLj 2551 // exceptions), then don't bother. 2552 auto &TLI = *MF->getSubtarget().getTargetLowering(); 2553 const Constant *PersonalityFn = MF->getFunction().getPersonalityFn(); 2554 if (TLI.getExceptionPointerRegister(PersonalityFn) == 0 && 2555 TLI.getExceptionSelectorRegister(PersonalityFn) == 0) 2556 return true; 2557 2558 // If landingpad's return type is token type, we don't create DAG nodes 2559 // for its exception pointer and selector value. The extraction of exception 2560 // pointer or selector value from token type landingpads is not currently 2561 // supported. 2562 if (LP.getType()->isTokenTy()) 2563 return true; 2564 2565 // Add a label to mark the beginning of the landing pad. Deletion of the 2566 // landing pad can thus be detected via the MachineModuleInfo. 2567 MIRBuilder.buildInstr(TargetOpcode::EH_LABEL) 2568 .addSym(MF->addLandingPad(&MBB)); 2569 2570 // If the unwinder does not preserve all registers, ensure that the 2571 // function marks the clobbered registers as used. 2572 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo(); 2573 if (auto *RegMask = TRI.getCustomEHPadPreservedMask(*MF)) 2574 MF->getRegInfo().addPhysRegsUsedFromRegMask(RegMask); 2575 2576 LLT Ty = getLLTForType(*LP.getType(), *DL); 2577 Register Undef = MRI->createGenericVirtualRegister(Ty); 2578 MIRBuilder.buildUndef(Undef); 2579 2580 SmallVector<LLT, 2> Tys; 2581 for (Type *Ty : cast<StructType>(LP.getType())->elements()) 2582 Tys.push_back(getLLTForType(*Ty, *DL)); 2583 assert(Tys.size() == 2 && "Only two-valued landingpads are supported"); 2584 2585 // Mark exception register as live in. 2586 Register ExceptionReg = TLI.getExceptionPointerRegister(PersonalityFn); 2587 if (!ExceptionReg) 2588 return false; 2589 2590 MBB.addLiveIn(ExceptionReg); 2591 ArrayRef<Register> ResRegs = getOrCreateVRegs(LP); 2592 MIRBuilder.buildCopy(ResRegs[0], ExceptionReg); 2593 2594 Register SelectorReg = TLI.getExceptionSelectorRegister(PersonalityFn); 2595 if (!SelectorReg) 2596 return false; 2597 2598 MBB.addLiveIn(SelectorReg); 2599 Register PtrVReg = MRI->createGenericVirtualRegister(Tys[0]); 2600 MIRBuilder.buildCopy(PtrVReg, SelectorReg); 2601 MIRBuilder.buildCast(ResRegs[1], PtrVReg); 2602 2603 return true; 2604 } 2605 2606 bool IRTranslator::translateAlloca(const User &U, 2607 MachineIRBuilder &MIRBuilder) { 2608 auto &AI = cast<AllocaInst>(U); 2609 2610 if (AI.isSwiftError()) 2611 return true; 2612 2613 if (AI.isStaticAlloca()) { 2614 Register Res = getOrCreateVReg(AI); 2615 int FI = getOrCreateFrameIndex(AI); 2616 MIRBuilder.buildFrameIndex(Res, FI); 2617 return true; 2618 } 2619 2620 // FIXME: support stack probing for Windows. 2621 if (MF->getTarget().getTargetTriple().isOSWindows()) 2622 return false; 2623 2624 // Now we're in the harder dynamic case. 2625 Register NumElts = getOrCreateVReg(*AI.getArraySize()); 2626 Type *IntPtrIRTy = DL->getIntPtrType(AI.getType()); 2627 LLT IntPtrTy = getLLTForType(*IntPtrIRTy, *DL); 2628 if (MRI->getType(NumElts) != IntPtrTy) { 2629 Register ExtElts = MRI->createGenericVirtualRegister(IntPtrTy); 2630 MIRBuilder.buildZExtOrTrunc(ExtElts, NumElts); 2631 NumElts = ExtElts; 2632 } 2633 2634 Type *Ty = AI.getAllocatedType(); 2635 2636 Register AllocSize = MRI->createGenericVirtualRegister(IntPtrTy); 2637 Register TySize = 2638 getOrCreateVReg(*ConstantInt::get(IntPtrIRTy, DL->getTypeAllocSize(Ty))); 2639 MIRBuilder.buildMul(AllocSize, NumElts, TySize); 2640 2641 // Round the size of the allocation up to the stack alignment size 2642 // by add SA-1 to the size. This doesn't overflow because we're computing 2643 // an address inside an alloca. 2644 Align StackAlign = MF->getSubtarget().getFrameLowering()->getStackAlign(); 2645 auto SAMinusOne = MIRBuilder.buildConstant(IntPtrTy, StackAlign.value() - 1); 2646 auto AllocAdd = MIRBuilder.buildAdd(IntPtrTy, AllocSize, SAMinusOne, 2647 MachineInstr::NoUWrap); 2648 auto AlignCst = 2649 MIRBuilder.buildConstant(IntPtrTy, ~(uint64_t)(StackAlign.value() - 1)); 2650 auto AlignedAlloc = MIRBuilder.buildAnd(IntPtrTy, AllocAdd, AlignCst); 2651 2652 Align Alignment = std::max(AI.getAlign(), DL->getPrefTypeAlign(Ty)); 2653 if (Alignment <= StackAlign) 2654 Alignment = Align(1); 2655 MIRBuilder.buildDynStackAlloc(getOrCreateVReg(AI), AlignedAlloc, Alignment); 2656 2657 MF->getFrameInfo().CreateVariableSizedObject(Alignment, &AI); 2658 assert(MF->getFrameInfo().hasVarSizedObjects()); 2659 return true; 2660 } 2661 2662 bool IRTranslator::translateVAArg(const User &U, MachineIRBuilder &MIRBuilder) { 2663 // FIXME: We may need more info about the type. Because of how LLT works, 2664 // we're completely discarding the i64/double distinction here (amongst 2665 // others). Fortunately the ABIs I know of where that matters don't use va_arg 2666 // anyway but that's not guaranteed. 2667 MIRBuilder.buildInstr(TargetOpcode::G_VAARG, {getOrCreateVReg(U)}, 2668 {getOrCreateVReg(*U.getOperand(0)), 2669 DL->getABITypeAlign(U.getType()).value()}); 2670 return true; 2671 } 2672 2673 bool IRTranslator::translateInsertElement(const User &U, 2674 MachineIRBuilder &MIRBuilder) { 2675 // If it is a <1 x Ty> vector, use the scalar as it is 2676 // not a legal vector type in LLT. 2677 if (cast<FixedVectorType>(U.getType())->getNumElements() == 1) 2678 return translateCopy(U, *U.getOperand(1), MIRBuilder); 2679 2680 Register Res = getOrCreateVReg(U); 2681 Register Val = getOrCreateVReg(*U.getOperand(0)); 2682 Register Elt = getOrCreateVReg(*U.getOperand(1)); 2683 Register Idx = getOrCreateVReg(*U.getOperand(2)); 2684 MIRBuilder.buildInsertVectorElement(Res, Val, Elt, Idx); 2685 return true; 2686 } 2687 2688 bool IRTranslator::translateExtractElement(const User &U, 2689 MachineIRBuilder &MIRBuilder) { 2690 // If it is a <1 x Ty> vector, use the scalar as it is 2691 // not a legal vector type in LLT. 2692 if (cast<FixedVectorType>(U.getOperand(0)->getType())->getNumElements() == 1) 2693 return translateCopy(U, *U.getOperand(0), MIRBuilder); 2694 2695 Register Res = getOrCreateVReg(U); 2696 Register Val = getOrCreateVReg(*U.getOperand(0)); 2697 const auto &TLI = *MF->getSubtarget().getTargetLowering(); 2698 unsigned PreferredVecIdxWidth = TLI.getVectorIdxTy(*DL).getSizeInBits(); 2699 Register Idx; 2700 if (auto *CI = dyn_cast<ConstantInt>(U.getOperand(1))) { 2701 if (CI->getBitWidth() != PreferredVecIdxWidth) { 2702 APInt NewIdx = CI->getValue().sextOrTrunc(PreferredVecIdxWidth); 2703 auto *NewIdxCI = ConstantInt::get(CI->getContext(), NewIdx); 2704 Idx = getOrCreateVReg(*NewIdxCI); 2705 } 2706 } 2707 if (!Idx) 2708 Idx = getOrCreateVReg(*U.getOperand(1)); 2709 if (MRI->getType(Idx).getSizeInBits() != PreferredVecIdxWidth) { 2710 const LLT VecIdxTy = LLT::scalar(PreferredVecIdxWidth); 2711 Idx = MIRBuilder.buildSExtOrTrunc(VecIdxTy, Idx).getReg(0); 2712 } 2713 MIRBuilder.buildExtractVectorElement(Res, Val, Idx); 2714 return true; 2715 } 2716 2717 bool IRTranslator::translateShuffleVector(const User &U, 2718 MachineIRBuilder &MIRBuilder) { 2719 ArrayRef<int> Mask; 2720 if (auto *SVI = dyn_cast<ShuffleVectorInst>(&U)) 2721 Mask = SVI->getShuffleMask(); 2722 else 2723 Mask = cast<ConstantExpr>(U).getShuffleMask(); 2724 ArrayRef<int> MaskAlloc = MF->allocateShuffleMask(Mask); 2725 MIRBuilder 2726 .buildInstr(TargetOpcode::G_SHUFFLE_VECTOR, {getOrCreateVReg(U)}, 2727 {getOrCreateVReg(*U.getOperand(0)), 2728 getOrCreateVReg(*U.getOperand(1))}) 2729 .addShuffleMask(MaskAlloc); 2730 return true; 2731 } 2732 2733 bool IRTranslator::translatePHI(const User &U, MachineIRBuilder &MIRBuilder) { 2734 const PHINode &PI = cast<PHINode>(U); 2735 2736 SmallVector<MachineInstr *, 4> Insts; 2737 for (auto Reg : getOrCreateVRegs(PI)) { 2738 auto MIB = MIRBuilder.buildInstr(TargetOpcode::G_PHI, {Reg}, {}); 2739 Insts.push_back(MIB.getInstr()); 2740 } 2741 2742 PendingPHIs.emplace_back(&PI, std::move(Insts)); 2743 return true; 2744 } 2745 2746 bool IRTranslator::translateAtomicCmpXchg(const User &U, 2747 MachineIRBuilder &MIRBuilder) { 2748 const AtomicCmpXchgInst &I = cast<AtomicCmpXchgInst>(U); 2749 2750 auto &TLI = *MF->getSubtarget().getTargetLowering(); 2751 auto Flags = TLI.getAtomicMemOperandFlags(I, *DL); 2752 2753 auto Res = getOrCreateVRegs(I); 2754 Register OldValRes = Res[0]; 2755 Register SuccessRes = Res[1]; 2756 Register Addr = getOrCreateVReg(*I.getPointerOperand()); 2757 Register Cmp = getOrCreateVReg(*I.getCompareOperand()); 2758 Register NewVal = getOrCreateVReg(*I.getNewValOperand()); 2759 2760 AAMDNodes AAMetadata; 2761 I.getAAMetadata(AAMetadata); 2762 2763 MIRBuilder.buildAtomicCmpXchgWithSuccess( 2764 OldValRes, SuccessRes, Addr, Cmp, NewVal, 2765 *MF->getMachineMemOperand( 2766 MachinePointerInfo(I.getPointerOperand()), Flags, MRI->getType(Cmp), 2767 getMemOpAlign(I), AAMetadata, nullptr, I.getSyncScopeID(), 2768 I.getSuccessOrdering(), I.getFailureOrdering())); 2769 return true; 2770 } 2771 2772 bool IRTranslator::translateAtomicRMW(const User &U, 2773 MachineIRBuilder &MIRBuilder) { 2774 const AtomicRMWInst &I = cast<AtomicRMWInst>(U); 2775 auto &TLI = *MF->getSubtarget().getTargetLowering(); 2776 auto Flags = TLI.getAtomicMemOperandFlags(I, *DL); 2777 2778 Register Res = getOrCreateVReg(I); 2779 Register Addr = getOrCreateVReg(*I.getPointerOperand()); 2780 Register Val = getOrCreateVReg(*I.getValOperand()); 2781 2782 unsigned Opcode = 0; 2783 switch (I.getOperation()) { 2784 default: 2785 return false; 2786 case AtomicRMWInst::Xchg: 2787 Opcode = TargetOpcode::G_ATOMICRMW_XCHG; 2788 break; 2789 case AtomicRMWInst::Add: 2790 Opcode = TargetOpcode::G_ATOMICRMW_ADD; 2791 break; 2792 case AtomicRMWInst::Sub: 2793 Opcode = TargetOpcode::G_ATOMICRMW_SUB; 2794 break; 2795 case AtomicRMWInst::And: 2796 Opcode = TargetOpcode::G_ATOMICRMW_AND; 2797 break; 2798 case AtomicRMWInst::Nand: 2799 Opcode = TargetOpcode::G_ATOMICRMW_NAND; 2800 break; 2801 case AtomicRMWInst::Or: 2802 Opcode = TargetOpcode::G_ATOMICRMW_OR; 2803 break; 2804 case AtomicRMWInst::Xor: 2805 Opcode = TargetOpcode::G_ATOMICRMW_XOR; 2806 break; 2807 case AtomicRMWInst::Max: 2808 Opcode = TargetOpcode::G_ATOMICRMW_MAX; 2809 break; 2810 case AtomicRMWInst::Min: 2811 Opcode = TargetOpcode::G_ATOMICRMW_MIN; 2812 break; 2813 case AtomicRMWInst::UMax: 2814 Opcode = TargetOpcode::G_ATOMICRMW_UMAX; 2815 break; 2816 case AtomicRMWInst::UMin: 2817 Opcode = TargetOpcode::G_ATOMICRMW_UMIN; 2818 break; 2819 case AtomicRMWInst::FAdd: 2820 Opcode = TargetOpcode::G_ATOMICRMW_FADD; 2821 break; 2822 case AtomicRMWInst::FSub: 2823 Opcode = TargetOpcode::G_ATOMICRMW_FSUB; 2824 break; 2825 } 2826 2827 AAMDNodes AAMetadata; 2828 I.getAAMetadata(AAMetadata); 2829 2830 MIRBuilder.buildAtomicRMW( 2831 Opcode, Res, Addr, Val, 2832 *MF->getMachineMemOperand(MachinePointerInfo(I.getPointerOperand()), 2833 Flags, MRI->getType(Val), getMemOpAlign(I), 2834 AAMetadata, nullptr, I.getSyncScopeID(), 2835 I.getOrdering())); 2836 return true; 2837 } 2838 2839 bool IRTranslator::translateFence(const User &U, 2840 MachineIRBuilder &MIRBuilder) { 2841 const FenceInst &Fence = cast<FenceInst>(U); 2842 MIRBuilder.buildFence(static_cast<unsigned>(Fence.getOrdering()), 2843 Fence.getSyncScopeID()); 2844 return true; 2845 } 2846 2847 bool IRTranslator::translateFreeze(const User &U, 2848 MachineIRBuilder &MIRBuilder) { 2849 const ArrayRef<Register> DstRegs = getOrCreateVRegs(U); 2850 const ArrayRef<Register> SrcRegs = getOrCreateVRegs(*U.getOperand(0)); 2851 2852 assert(DstRegs.size() == SrcRegs.size() && 2853 "Freeze with different source and destination type?"); 2854 2855 for (unsigned I = 0; I < DstRegs.size(); ++I) { 2856 MIRBuilder.buildFreeze(DstRegs[I], SrcRegs[I]); 2857 } 2858 2859 return true; 2860 } 2861 2862 void IRTranslator::finishPendingPhis() { 2863 #ifndef NDEBUG 2864 DILocationVerifier Verifier; 2865 GISelObserverWrapper WrapperObserver(&Verifier); 2866 RAIIDelegateInstaller DelInstall(*MF, &WrapperObserver); 2867 #endif // ifndef NDEBUG 2868 for (auto &Phi : PendingPHIs) { 2869 const PHINode *PI = Phi.first; 2870 ArrayRef<MachineInstr *> ComponentPHIs = Phi.second; 2871 MachineBasicBlock *PhiMBB = ComponentPHIs[0]->getParent(); 2872 EntryBuilder->setDebugLoc(PI->getDebugLoc()); 2873 #ifndef NDEBUG 2874 Verifier.setCurrentInst(PI); 2875 #endif // ifndef NDEBUG 2876 2877 SmallSet<const MachineBasicBlock *, 16> SeenPreds; 2878 for (unsigned i = 0; i < PI->getNumIncomingValues(); ++i) { 2879 auto IRPred = PI->getIncomingBlock(i); 2880 ArrayRef<Register> ValRegs = getOrCreateVRegs(*PI->getIncomingValue(i)); 2881 for (auto Pred : getMachinePredBBs({IRPred, PI->getParent()})) { 2882 if (SeenPreds.count(Pred) || !PhiMBB->isPredecessor(Pred)) 2883 continue; 2884 SeenPreds.insert(Pred); 2885 for (unsigned j = 0; j < ValRegs.size(); ++j) { 2886 MachineInstrBuilder MIB(*MF, ComponentPHIs[j]); 2887 MIB.addUse(ValRegs[j]); 2888 MIB.addMBB(Pred); 2889 } 2890 } 2891 } 2892 } 2893 } 2894 2895 bool IRTranslator::valueIsSplit(const Value &V, 2896 SmallVectorImpl<uint64_t> *Offsets) { 2897 SmallVector<LLT, 4> SplitTys; 2898 if (Offsets && !Offsets->empty()) 2899 Offsets->clear(); 2900 computeValueLLTs(*DL, *V.getType(), SplitTys, Offsets); 2901 return SplitTys.size() > 1; 2902 } 2903 2904 bool IRTranslator::translate(const Instruction &Inst) { 2905 CurBuilder->setDebugLoc(Inst.getDebugLoc()); 2906 2907 auto &TLI = *MF->getSubtarget().getTargetLowering(); 2908 if (TLI.fallBackToDAGISel(Inst)) 2909 return false; 2910 2911 switch (Inst.getOpcode()) { 2912 #define HANDLE_INST(NUM, OPCODE, CLASS) \ 2913 case Instruction::OPCODE: \ 2914 return translate##OPCODE(Inst, *CurBuilder.get()); 2915 #include "llvm/IR/Instruction.def" 2916 default: 2917 return false; 2918 } 2919 } 2920 2921 bool IRTranslator::translate(const Constant &C, Register Reg) { 2922 // We only emit constants into the entry block from here. To prevent jumpy 2923 // debug behaviour set the line to 0. 2924 if (auto CurrInstDL = CurBuilder->getDL()) 2925 EntryBuilder->setDebugLoc(DILocation::get(C.getContext(), 0, 0, 2926 CurrInstDL.getScope(), 2927 CurrInstDL.getInlinedAt())); 2928 2929 if (auto CI = dyn_cast<ConstantInt>(&C)) 2930 EntryBuilder->buildConstant(Reg, *CI); 2931 else if (auto CF = dyn_cast<ConstantFP>(&C)) 2932 EntryBuilder->buildFConstant(Reg, *CF); 2933 else if (isa<UndefValue>(C)) 2934 EntryBuilder->buildUndef(Reg); 2935 else if (isa<ConstantPointerNull>(C)) 2936 EntryBuilder->buildConstant(Reg, 0); 2937 else if (auto GV = dyn_cast<GlobalValue>(&C)) 2938 EntryBuilder->buildGlobalValue(Reg, GV); 2939 else if (auto CAZ = dyn_cast<ConstantAggregateZero>(&C)) { 2940 if (!isa<FixedVectorType>(CAZ->getType())) 2941 return false; 2942 // Return the scalar if it is a <1 x Ty> vector. 2943 unsigned NumElts = CAZ->getElementCount().getFixedValue(); 2944 if (NumElts == 1) 2945 return translateCopy(C, *CAZ->getElementValue(0u), *EntryBuilder.get()); 2946 SmallVector<Register, 4> Ops; 2947 for (unsigned I = 0; I < NumElts; ++I) { 2948 Constant &Elt = *CAZ->getElementValue(I); 2949 Ops.push_back(getOrCreateVReg(Elt)); 2950 } 2951 EntryBuilder->buildBuildVector(Reg, Ops); 2952 } else if (auto CV = dyn_cast<ConstantDataVector>(&C)) { 2953 // Return the scalar if it is a <1 x Ty> vector. 2954 if (CV->getNumElements() == 1) 2955 return translateCopy(C, *CV->getElementAsConstant(0), 2956 *EntryBuilder.get()); 2957 SmallVector<Register, 4> Ops; 2958 for (unsigned i = 0; i < CV->getNumElements(); ++i) { 2959 Constant &Elt = *CV->getElementAsConstant(i); 2960 Ops.push_back(getOrCreateVReg(Elt)); 2961 } 2962 EntryBuilder->buildBuildVector(Reg, Ops); 2963 } else if (auto CE = dyn_cast<ConstantExpr>(&C)) { 2964 switch(CE->getOpcode()) { 2965 #define HANDLE_INST(NUM, OPCODE, CLASS) \ 2966 case Instruction::OPCODE: \ 2967 return translate##OPCODE(*CE, *EntryBuilder.get()); 2968 #include "llvm/IR/Instruction.def" 2969 default: 2970 return false; 2971 } 2972 } else if (auto CV = dyn_cast<ConstantVector>(&C)) { 2973 if (CV->getNumOperands() == 1) 2974 return translateCopy(C, *CV->getOperand(0), *EntryBuilder.get()); 2975 SmallVector<Register, 4> Ops; 2976 for (unsigned i = 0; i < CV->getNumOperands(); ++i) { 2977 Ops.push_back(getOrCreateVReg(*CV->getOperand(i))); 2978 } 2979 EntryBuilder->buildBuildVector(Reg, Ops); 2980 } else if (auto *BA = dyn_cast<BlockAddress>(&C)) { 2981 EntryBuilder->buildBlockAddress(Reg, BA); 2982 } else 2983 return false; 2984 2985 return true; 2986 } 2987 2988 void IRTranslator::finalizeBasicBlock() { 2989 for (auto &BTB : SL->BitTestCases) { 2990 // Emit header first, if it wasn't already emitted. 2991 if (!BTB.Emitted) 2992 emitBitTestHeader(BTB, BTB.Parent); 2993 2994 BranchProbability UnhandledProb = BTB.Prob; 2995 for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) { 2996 UnhandledProb -= BTB.Cases[j].ExtraProb; 2997 // Set the current basic block to the mbb we wish to insert the code into 2998 MachineBasicBlock *MBB = BTB.Cases[j].ThisBB; 2999 // If all cases cover a contiguous range, it is not necessary to jump to 3000 // the default block after the last bit test fails. This is because the 3001 // range check during bit test header creation has guaranteed that every 3002 // case here doesn't go outside the range. In this case, there is no need 3003 // to perform the last bit test, as it will always be true. Instead, make 3004 // the second-to-last bit-test fall through to the target of the last bit 3005 // test, and delete the last bit test. 3006 3007 MachineBasicBlock *NextMBB; 3008 if (BTB.ContiguousRange && j + 2 == ej) { 3009 // Second-to-last bit-test with contiguous range: fall through to the 3010 // target of the final bit test. 3011 NextMBB = BTB.Cases[j + 1].TargetBB; 3012 } else if (j + 1 == ej) { 3013 // For the last bit test, fall through to Default. 3014 NextMBB = BTB.Default; 3015 } else { 3016 // Otherwise, fall through to the next bit test. 3017 NextMBB = BTB.Cases[j + 1].ThisBB; 3018 } 3019 3020 emitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j], MBB); 3021 3022 if (BTB.ContiguousRange && j + 2 == ej) { 3023 // We need to record the replacement phi edge here that normally 3024 // happens in emitBitTestCase before we delete the case, otherwise the 3025 // phi edge will be lost. 3026 addMachineCFGPred({BTB.Parent->getBasicBlock(), 3027 BTB.Cases[ej - 1].TargetBB->getBasicBlock()}, 3028 MBB); 3029 // Since we're not going to use the final bit test, remove it. 3030 BTB.Cases.pop_back(); 3031 break; 3032 } 3033 } 3034 // This is "default" BB. We have two jumps to it. From "header" BB and from 3035 // last "case" BB, unless the latter was skipped. 3036 CFGEdge HeaderToDefaultEdge = {BTB.Parent->getBasicBlock(), 3037 BTB.Default->getBasicBlock()}; 3038 addMachineCFGPred(HeaderToDefaultEdge, BTB.Parent); 3039 if (!BTB.ContiguousRange) { 3040 addMachineCFGPred(HeaderToDefaultEdge, BTB.Cases.back().ThisBB); 3041 } 3042 } 3043 SL->BitTestCases.clear(); 3044 3045 for (auto &JTCase : SL->JTCases) { 3046 // Emit header first, if it wasn't already emitted. 3047 if (!JTCase.first.Emitted) 3048 emitJumpTableHeader(JTCase.second, JTCase.first, JTCase.first.HeaderBB); 3049 3050 emitJumpTable(JTCase.second, JTCase.second.MBB); 3051 } 3052 SL->JTCases.clear(); 3053 3054 for (auto &SwCase : SL->SwitchCases) 3055 emitSwitchCase(SwCase, &CurBuilder->getMBB(), *CurBuilder); 3056 SL->SwitchCases.clear(); 3057 } 3058 3059 void IRTranslator::finalizeFunction() { 3060 // Release the memory used by the different maps we 3061 // needed during the translation. 3062 PendingPHIs.clear(); 3063 VMap.reset(); 3064 FrameIndices.clear(); 3065 MachinePreds.clear(); 3066 // MachineIRBuilder::DebugLoc can outlive the DILocation it holds. Clear it 3067 // to avoid accessing free’d memory (in runOnMachineFunction) and to avoid 3068 // destroying it twice (in ~IRTranslator() and ~LLVMContext()) 3069 EntryBuilder.reset(); 3070 CurBuilder.reset(); 3071 FuncInfo.clear(); 3072 } 3073 3074 /// Returns true if a BasicBlock \p BB within a variadic function contains a 3075 /// variadic musttail call. 3076 static bool checkForMustTailInVarArgFn(bool IsVarArg, const BasicBlock &BB) { 3077 if (!IsVarArg) 3078 return false; 3079 3080 // Walk the block backwards, because tail calls usually only appear at the end 3081 // of a block. 3082 return std::any_of(BB.rbegin(), BB.rend(), [](const Instruction &I) { 3083 const auto *CI = dyn_cast<CallInst>(&I); 3084 return CI && CI->isMustTailCall(); 3085 }); 3086 } 3087 3088 bool IRTranslator::runOnMachineFunction(MachineFunction &CurMF) { 3089 MF = &CurMF; 3090 const Function &F = MF->getFunction(); 3091 if (F.empty()) 3092 return false; 3093 GISelCSEAnalysisWrapper &Wrapper = 3094 getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper(); 3095 // Set the CSEConfig and run the analysis. 3096 GISelCSEInfo *CSEInfo = nullptr; 3097 TPC = &getAnalysis<TargetPassConfig>(); 3098 bool EnableCSE = EnableCSEInIRTranslator.getNumOccurrences() 3099 ? EnableCSEInIRTranslator 3100 : TPC->isGISelCSEEnabled(); 3101 3102 if (EnableCSE) { 3103 EntryBuilder = std::make_unique<CSEMIRBuilder>(CurMF); 3104 CSEInfo = &Wrapper.get(TPC->getCSEConfig()); 3105 EntryBuilder->setCSEInfo(CSEInfo); 3106 CurBuilder = std::make_unique<CSEMIRBuilder>(CurMF); 3107 CurBuilder->setCSEInfo(CSEInfo); 3108 } else { 3109 EntryBuilder = std::make_unique<MachineIRBuilder>(); 3110 CurBuilder = std::make_unique<MachineIRBuilder>(); 3111 } 3112 CLI = MF->getSubtarget().getCallLowering(); 3113 CurBuilder->setMF(*MF); 3114 EntryBuilder->setMF(*MF); 3115 MRI = &MF->getRegInfo(); 3116 DL = &F.getParent()->getDataLayout(); 3117 ORE = std::make_unique<OptimizationRemarkEmitter>(&F); 3118 const TargetMachine &TM = MF->getTarget(); 3119 TM.resetTargetOptions(F); 3120 EnableOpts = OptLevel != CodeGenOpt::None && !skipFunction(F); 3121 FuncInfo.MF = MF; 3122 if (EnableOpts) 3123 FuncInfo.BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI(); 3124 else 3125 FuncInfo.BPI = nullptr; 3126 3127 FuncInfo.CanLowerReturn = CLI->checkReturnTypeForCallConv(*MF); 3128 3129 const auto &TLI = *MF->getSubtarget().getTargetLowering(); 3130 3131 SL = std::make_unique<GISelSwitchLowering>(this, FuncInfo); 3132 SL->init(TLI, TM, *DL); 3133 3134 3135 3136 assert(PendingPHIs.empty() && "stale PHIs"); 3137 3138 // Targets which want to use big endian can enable it using 3139 // enableBigEndian() 3140 if (!DL->isLittleEndian() && !CLI->enableBigEndian()) { 3141 // Currently we don't properly handle big endian code. 3142 OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure", 3143 F.getSubprogram(), &F.getEntryBlock()); 3144 R << "unable to translate in big endian mode"; 3145 reportTranslationError(*MF, *TPC, *ORE, R); 3146 } 3147 3148 // Release the per-function state when we return, whether we succeeded or not. 3149 auto FinalizeOnReturn = make_scope_exit([this]() { finalizeFunction(); }); 3150 3151 // Setup a separate basic-block for the arguments and constants 3152 MachineBasicBlock *EntryBB = MF->CreateMachineBasicBlock(); 3153 MF->push_back(EntryBB); 3154 EntryBuilder->setMBB(*EntryBB); 3155 3156 DebugLoc DbgLoc = F.getEntryBlock().getFirstNonPHI()->getDebugLoc(); 3157 SwiftError.setFunction(CurMF); 3158 SwiftError.createEntriesInEntryBlock(DbgLoc); 3159 3160 bool IsVarArg = F.isVarArg(); 3161 bool HasMustTailInVarArgFn = false; 3162 3163 // Create all blocks, in IR order, to preserve the layout. 3164 for (const BasicBlock &BB: F) { 3165 auto *&MBB = BBToMBB[&BB]; 3166 3167 MBB = MF->CreateMachineBasicBlock(&BB); 3168 MF->push_back(MBB); 3169 3170 if (BB.hasAddressTaken()) 3171 MBB->setHasAddressTaken(); 3172 3173 if (!HasMustTailInVarArgFn) 3174 HasMustTailInVarArgFn = checkForMustTailInVarArgFn(IsVarArg, BB); 3175 } 3176 3177 MF->getFrameInfo().setHasMustTailInVarArgFunc(HasMustTailInVarArgFn); 3178 3179 // Make our arguments/constants entry block fallthrough to the IR entry block. 3180 EntryBB->addSuccessor(&getMBB(F.front())); 3181 3182 if (CLI->fallBackToDAGISel(*MF)) { 3183 OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure", 3184 F.getSubprogram(), &F.getEntryBlock()); 3185 R << "unable to lower function: " << ore::NV("Prototype", F.getType()); 3186 reportTranslationError(*MF, *TPC, *ORE, R); 3187 return false; 3188 } 3189 3190 // Lower the actual args into this basic block. 3191 SmallVector<ArrayRef<Register>, 8> VRegArgs; 3192 for (const Argument &Arg: F.args()) { 3193 if (DL->getTypeStoreSize(Arg.getType()).isZero()) 3194 continue; // Don't handle zero sized types. 3195 ArrayRef<Register> VRegs = getOrCreateVRegs(Arg); 3196 VRegArgs.push_back(VRegs); 3197 3198 if (Arg.hasSwiftErrorAttr()) { 3199 assert(VRegs.size() == 1 && "Too many vregs for Swift error"); 3200 SwiftError.setCurrentVReg(EntryBB, SwiftError.getFunctionArg(), VRegs[0]); 3201 } 3202 } 3203 3204 if (!CLI->lowerFormalArguments(*EntryBuilder.get(), F, VRegArgs, FuncInfo)) { 3205 OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure", 3206 F.getSubprogram(), &F.getEntryBlock()); 3207 R << "unable to lower arguments: " << ore::NV("Prototype", F.getType()); 3208 reportTranslationError(*MF, *TPC, *ORE, R); 3209 return false; 3210 } 3211 3212 // Need to visit defs before uses when translating instructions. 3213 GISelObserverWrapper WrapperObserver; 3214 if (EnableCSE && CSEInfo) 3215 WrapperObserver.addObserver(CSEInfo); 3216 { 3217 ReversePostOrderTraversal<const Function *> RPOT(&F); 3218 #ifndef NDEBUG 3219 DILocationVerifier Verifier; 3220 WrapperObserver.addObserver(&Verifier); 3221 #endif // ifndef NDEBUG 3222 RAIIDelegateInstaller DelInstall(*MF, &WrapperObserver); 3223 RAIIMFObserverInstaller ObsInstall(*MF, WrapperObserver); 3224 for (const BasicBlock *BB : RPOT) { 3225 MachineBasicBlock &MBB = getMBB(*BB); 3226 // Set the insertion point of all the following translations to 3227 // the end of this basic block. 3228 CurBuilder->setMBB(MBB); 3229 HasTailCall = false; 3230 for (const Instruction &Inst : *BB) { 3231 // If we translated a tail call in the last step, then we know 3232 // everything after the call is either a return, or something that is 3233 // handled by the call itself. (E.g. a lifetime marker or assume 3234 // intrinsic.) In this case, we should stop translating the block and 3235 // move on. 3236 if (HasTailCall) 3237 break; 3238 #ifndef NDEBUG 3239 Verifier.setCurrentInst(&Inst); 3240 #endif // ifndef NDEBUG 3241 if (translate(Inst)) 3242 continue; 3243 3244 OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure", 3245 Inst.getDebugLoc(), BB); 3246 R << "unable to translate instruction: " << ore::NV("Opcode", &Inst); 3247 3248 if (ORE->allowExtraAnalysis("gisel-irtranslator")) { 3249 std::string InstStrStorage; 3250 raw_string_ostream InstStr(InstStrStorage); 3251 InstStr << Inst; 3252 3253 R << ": '" << InstStr.str() << "'"; 3254 } 3255 3256 reportTranslationError(*MF, *TPC, *ORE, R); 3257 return false; 3258 } 3259 3260 finalizeBasicBlock(); 3261 } 3262 #ifndef NDEBUG 3263 WrapperObserver.removeObserver(&Verifier); 3264 #endif 3265 } 3266 3267 finishPendingPhis(); 3268 3269 SwiftError.propagateVRegs(); 3270 3271 // Merge the argument lowering and constants block with its single 3272 // successor, the LLVM-IR entry block. We want the basic block to 3273 // be maximal. 3274 assert(EntryBB->succ_size() == 1 && 3275 "Custom BB used for lowering should have only one successor"); 3276 // Get the successor of the current entry block. 3277 MachineBasicBlock &NewEntryBB = **EntryBB->succ_begin(); 3278 assert(NewEntryBB.pred_size() == 1 && 3279 "LLVM-IR entry block has a predecessor!?"); 3280 // Move all the instruction from the current entry block to the 3281 // new entry block. 3282 NewEntryBB.splice(NewEntryBB.begin(), EntryBB, EntryBB->begin(), 3283 EntryBB->end()); 3284 3285 // Update the live-in information for the new entry block. 3286 for (const MachineBasicBlock::RegisterMaskPair &LiveIn : EntryBB->liveins()) 3287 NewEntryBB.addLiveIn(LiveIn); 3288 NewEntryBB.sortUniqueLiveIns(); 3289 3290 // Get rid of the now empty basic block. 3291 EntryBB->removeSuccessor(&NewEntryBB); 3292 MF->remove(EntryBB); 3293 MF->DeleteMachineBasicBlock(EntryBB); 3294 3295 assert(&MF->front() == &NewEntryBB && 3296 "New entry wasn't next in the list of basic block!"); 3297 3298 // Initialize stack protector information. 3299 StackProtector &SP = getAnalysis<StackProtector>(); 3300 SP.copyToMachineFrameInfo(MF->getFrameInfo()); 3301 3302 return false; 3303 } 3304