77#include "llvm/IR/IntrinsicsAArch64.h"
78#include "llvm/IR/IntrinsicsWebAssembly.h"
108using namespace PatternMatch;
109using namespace SwitchCG;
111#define DEBUG_TYPE "isel"
119 cl::desc(
"Insert the experimental `assertalign` node."),
124 cl::desc(
"Generate low-precision inline sequences "
125 "for some float libcalls"),
131 cl::desc(
"Set the case probability threshold for peeling the case from a "
132 "switch statement. A value greater than 100 will void this "
152 const SDValue *Parts,
unsigned NumParts,
154 std::optional<CallingConv::ID>
CC);
163 unsigned NumParts,
MVT PartVT,
EVT ValueVT,
const Value *V,
164 std::optional<CallingConv::ID>
CC = std::nullopt,
165 std::optional<ISD::NodeType> AssertOp = std::nullopt) {
169 PartVT, ValueVT,
CC))
176 assert(NumParts > 0 &&
"No parts to assemble!");
187 unsigned RoundBits = PartBits * RoundParts;
188 EVT RoundVT = RoundBits == ValueBits ?
194 if (RoundParts > 2) {
198 RoundParts / 2, PartVT, HalfVT, V);
209 if (RoundParts < NumParts) {
211 unsigned OddParts = NumParts - RoundParts;
242 !PartVT.
isVector() &&
"Unexpected split");
253 if (PartEVT == ValueVT)
257 ValueVT.
bitsLT(PartEVT)) {
270 if (ValueVT.
bitsLT(PartEVT)) {
275 Val = DAG.
getNode(*AssertOp,
DL, PartEVT, Val,
295 ValueVT.
bitsLT(PartEVT)) {
304 const Twine &ErrMsg) {
305 const Instruction *
I = dyn_cast_or_null<Instruction>(V);
309 const char *AsmError =
", possible invalid constraint for vector type";
310 if (
const CallInst *CI = dyn_cast<CallInst>(
I))
311 if (CI->isInlineAsm())
323 const SDValue *Parts,
unsigned NumParts,
325 std::optional<CallingConv::ID> CallConv) {
327 assert(NumParts > 0 &&
"No parts to assemble!");
328 const bool IsABIRegCopy = CallConv.has_value();
337 unsigned NumIntermediates;
342 *DAG.
getContext(), *CallConv, ValueVT, IntermediateVT,
343 NumIntermediates, RegisterVT);
347 NumIntermediates, RegisterVT);
350 assert(NumRegs == NumParts &&
"Part count doesn't match vector breakdown!");
352 assert(RegisterVT == PartVT &&
"Part type doesn't match vector breakdown!");
355 "Part type sizes don't match!");
359 if (NumIntermediates == NumParts) {
362 for (
unsigned i = 0; i != NumParts; ++i)
364 PartVT, IntermediateVT, V, CallConv);
365 }
else if (NumParts > 0) {
368 assert(NumParts % NumIntermediates == 0 &&
369 "Must expand into a divisible number of parts!");
370 unsigned Factor = NumParts / NumIntermediates;
371 for (
unsigned i = 0; i != NumIntermediates; ++i)
373 PartVT, IntermediateVT, V, CallConv);
388 DL, BuiltVectorTy, Ops);
394 if (PartEVT == ValueVT)
410 "Cannot narrow, it would be a lossy transformation");
416 if (PartEVT == ValueVT)
437 }
else if (ValueVT.
bitsLT(PartEVT)) {
446 *DAG.
getContext(), V,
"non-trivial scalar-to-vector conversion");
477 std::optional<CallingConv::ID> CallConv);
484 unsigned NumParts,
MVT PartVT,
const Value *V,
485 std::optional<CallingConv::ID> CallConv = std::nullopt,
499 unsigned OrigNumParts = NumParts;
501 "Copying to an illegal type!");
507 EVT PartEVT = PartVT;
508 if (PartEVT == ValueVT) {
509 assert(NumParts == 1 &&
"No-op copy with multiple parts!");
518 assert(NumParts == 1 &&
"Do not know what to promote to!");
529 "Unknown mismatch!");
531 Val = DAG.
getNode(ExtendKind,
DL, ValueVT, Val);
537 assert(NumParts == 1 && PartEVT != ValueVT);
543 "Unknown mismatch!");
553 "Failed to tile the value with PartVT!");
556 if (PartEVT != ValueVT) {
558 "scalar-to-vector conversion failed");
567 if (NumParts & (NumParts - 1)) {
570 "Do not know what to expand to!");
572 unsigned RoundBits = RoundParts * PartBits;
573 unsigned OddParts = NumParts - RoundParts;
582 std::reverse(Parts + RoundParts, Parts + NumParts);
584 NumParts = RoundParts;
596 for (
unsigned StepSize = NumParts; StepSize > 1; StepSize /= 2) {
597 for (
unsigned i = 0; i < NumParts; i += StepSize) {
598 unsigned ThisBits = StepSize * PartBits / 2;
601 SDValue &Part1 = Parts[i+StepSize/2];
608 if (ThisBits == PartBits && ThisVT != PartVT) {
616 std::reverse(Parts, Parts + OrigNumParts);
631 if (ElementCount::isKnownLE(PartNumElts, ValueNumElts) ||
648 Ops.
append((PartNumElts - ValueNumElts).getFixedValue(), EltUndef);
659 std::optional<CallingConv::ID> CallConv) {
663 const bool IsABIRegCopy = CallConv.has_value();
666 EVT PartEVT = PartVT;
667 if (PartEVT == ValueVT) {
686 TargetLowering::TypeWidenVector) {
704 "lossy conversion of vector to scalar type");
719 unsigned NumIntermediates;
723 *DAG.
getContext(), *CallConv, ValueVT, IntermediateVT, NumIntermediates,
728 NumIntermediates, RegisterVT);
731 assert(NumRegs == NumParts &&
"Part count doesn't match vector breakdown!");
733 assert(RegisterVT == PartVT &&
"Part type doesn't match vector breakdown!");
736 "Mixing scalable and fixed vectors when copying in parts");
738 std::optional<ElementCount> DestEltCnt;
748 if (ValueVT == BuiltVectorTy) {
772 for (
unsigned i = 0; i != NumIntermediates; ++i) {
787 if (NumParts == NumIntermediates) {
790 for (
unsigned i = 0; i != NumParts; ++i)
792 }
else if (NumParts > 0) {
795 assert(NumIntermediates != 0 &&
"division by zero");
796 assert(NumParts % NumIntermediates == 0 &&
797 "Must expand into a divisible number of parts!");
798 unsigned Factor = NumParts / NumIntermediates;
799 for (
unsigned i = 0; i != NumIntermediates; ++i)
806 EVT valuevt, std::optional<CallingConv::ID>
CC)
807 : ValueVTs(1, valuevt), RegVTs(1, regvt), Regs(regs),
808 RegCount(1, regs.
size()), CallConv(
CC) {}
812 std::optional<CallingConv::ID>
CC) {
826 for (
unsigned i = 0; i != NumRegs; ++i)
828 RegVTs.push_back(RegisterVT);
857 for (
unsigned i = 0; i != NumRegs; ++i) {
863 *Flag =
P.getValue(2);
866 Chain =
P.getValue(1);
899 }
else if (NumSignBits > 1) {
943 NumParts, RegisterVT, V,
CallConv, ExtendKind);
949 for (
unsigned i = 0; i != NumRegs; ++i) {
961 if (NumRegs == 1 || Flag)
972 Chain = Chains[NumRegs-1];
978 unsigned MatchingIdx,
const SDLoc &dl,
980 std::vector<SDValue> &Ops)
const {
1005 "No 1:1 mapping from clobbers to regs?");
1013 "If we clobbered the stack pointer, MFI should know about it.");
1022 for (
unsigned i = 0; i != NumRegs; ++i) {
1024 unsigned TheReg =
Regs[Reg++];
1035 unsigned RegCount = std::get<0>(CountAndVT);
1036 MVT RegisterVT = std::get<1>(CountAndVT);
1058 UnusedArgNodeMap.clear();
1060 PendingExports.clear();
1061 PendingConstrainedFP.clear();
1062 PendingConstrainedFPStrict.clear();
1070 DanglingDebugInfoMap.clear();
1077 if (Pending.
empty())
1083 unsigned i = 0, e = Pending.
size();
1084 for (; i != e; ++i) {
1085 assert(Pending[i].getNode()->getNumOperands() > 1);
1086 if (Pending[i].getNode()->getOperand(0) == Root)
1094 if (Pending.
size() == 1)
1113 PendingConstrainedFP.size() +
1114 PendingConstrainedFPStrict.size());
1116 PendingConstrainedFP.end());
1117 PendingLoads.append(PendingConstrainedFPStrict.begin(),
1118 PendingConstrainedFPStrict.end());
1119 PendingConstrainedFP.clear();
1120 PendingConstrainedFPStrict.clear();
1127 PendingExports.append(PendingConstrainedFPStrict.begin(),
1128 PendingConstrainedFPStrict.end());
1129 PendingConstrainedFPStrict.clear();
1130 return updateRoot(PendingExports);
1135 if (
I.isTerminator()) {
1136 HandlePHINodesInSuccessorBlocks(
I.getParent());
1144 for (
auto It = FnVarLocs->locs_begin(&
I), End = FnVarLocs->locs_end(&
I);
1146 auto *Var = FnVarLocs->getDILocalVariable(It->VariableID);
1150 It->Values.hasArgList()))
1156 if (!isa<DbgInfoIntrinsic>(
I))
1162 bool NodeInserted =
false;
1163 std::unique_ptr<SelectionDAG::DAGNodeInsertedListener> InsertedListener;
1164 MDNode *PCSectionsMD =
I.getMetadata(LLVMContext::MD_pcsections);
1166 InsertedListener = std::make_unique<SelectionDAG::DAGNodeInsertedListener>(
1167 DAG, [&](
SDNode *) { NodeInserted =
true; });
1173 !isa<GCStatepointInst>(
I))
1178 auto It = NodeMap.find(&
I);
1179 if (It != NodeMap.end()) {
1181 }
else if (NodeInserted) {
1184 errs() <<
"warning: loosing !pcsections metadata ["
1185 <<
I.getModule()->getName() <<
"]\n";
1194void SelectionDAGBuilder::visitPHI(
const PHINode &) {
1204#define HANDLE_INST(NUM, OPCODE, CLASS) \
1205 case Instruction::OPCODE: visit##OPCODE((const CLASS&)I); break;
1206#include "llvm/IR/Instruction.def"
1255 "DbgValueInst without an ArgList should have a single location "
1257 DanglingDebugInfoMap[DI->
getValue(0)].emplace_back(DI, Order);
1263 auto isMatchingDbgValue = [&](DanglingDebugInfo &DDI) {
1266 if (DanglingVariable == Variable && Expr->
fragmentsOverlap(DanglingExpr)) {
1267 LLVM_DEBUG(
dbgs() <<
"Dropping dangling debug info for " << printDDI(DDI)
1274 for (
auto &DDIMI : DanglingDebugInfoMap) {
1275 DanglingDebugInfoVector &DDIV = DDIMI.second;
1279 for (
auto &DDI : DDIV)
1280 if (isMatchingDbgValue(DDI))
1283 erase_if(DDIV, isMatchingDbgValue);
1291 auto DanglingDbgInfoIt = DanglingDebugInfoMap.find(V);
1292 if (DanglingDbgInfoIt == DanglingDebugInfoMap.end())
1295 DanglingDebugInfoVector &DDIV = DanglingDbgInfoIt->second;
1296 for (
auto &DDI : DDIV) {
1299 unsigned DbgSDNodeOrder = DDI.getSDNodeOrder();
1303 "Expected inlined-at fields to agree");
1312 if (!EmitFuncArgumentDbgValue(V, Variable, Expr,
DL,
1313 FuncArgumentDbgValueKind::Value, Val)) {
1314 LLVM_DEBUG(
dbgs() <<
"Resolve dangling debug info for " << printDDI(DDI)
1322 <<
"changing SDNodeOrder from " << DbgSDNodeOrder <<
" to "
1323 << ValSDNodeOrder <<
"\n");
1324 SDV = getDbgValue(Val, Variable, Expr,
DL,
1325 std::max(DbgSDNodeOrder, ValSDNodeOrder));
1329 << printDDI(DDI) <<
" in EmitFuncArgumentDbgValue\n");
1331 LLVM_DEBUG(
dbgs() <<
"Dropping debug info for " << printDDI(DDI) <<
"\n");
1346 Value *V = DDI.getVariableLocationOp(0);
1351 unsigned SDOrder = DDI.getSDNodeOrder();
1355 bool StackValue =
true;
1364 while (isa<Instruction>(V)) {
1379 if (!AdditionalValues.
empty())
1389 dbgs() <<
"Salvaged debug location info for:\n " << *Var <<
"\n"
1390 << *OrigV <<
"\nBy stripping back to:\n " << *V <<
"\n");
1398 assert(OrigV &&
"V shouldn't be null");
1402 LLVM_DEBUG(
dbgs() <<
"Dropping debug value info for:\n " << printDDI(DDI)
1409 unsigned Order,
bool IsVariadic) {
1414 for (
const Value *V : Values) {
1416 if (isa<ConstantInt>(V) || isa<ConstantFP>(V) || isa<UndefValue>(V) ||
1417 isa<ConstantPointerNull>(V)) {
1423 if (
auto *CE = dyn_cast<ConstantExpr>(V))
1424 if (CE->getOpcode() == Instruction::IntToPtr) {
1431 if (
const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1442 if (!
N.getNode() && isa<Argument>(V))
1443 N = UnusedArgNodeMap[V];
1447 EmitFuncArgumentDbgValue(V, Var, Expr, DbgLoc,
1448 FuncArgumentDbgValueKind::Value,
N))
1450 if (
auto *FISDN = dyn_cast<FrameIndexSDNode>(
N.getNode())) {
1475 bool IsParamOfFunc =
1483 auto VMI =
FuncInfo.ValueMap.find(V);
1484 if (VMI !=
FuncInfo.ValueMap.end()) {
1485 unsigned Reg = VMI->second;
1489 V->getType(), std::nullopt);
1495 unsigned BitsToDescribe = 0;
1497 BitsToDescribe = *VarSize;
1499 BitsToDescribe = Fragment->SizeInBits;
1502 if (
Offset >= BitsToDescribe)
1505 unsigned RegisterSize = RegAndSize.second;
1506 unsigned FragmentSize = (
Offset + RegisterSize > BitsToDescribe)
1507 ? BitsToDescribe -
Offset
1510 Expr,
Offset, FragmentSize);
1514 Var, *FragmentExpr, RegAndSize.first,
false, DbgLoc, SDNodeOrder);
1533 SDNodeOrder, IsVariadic);
1540 for (
auto &Pair : DanglingDebugInfoMap)
1541 for (
auto &DDI : Pair.second)
1552 if (It !=
FuncInfo.ValueMap.end()) {
1573 if (
N.getNode())
return N;
1593 if (isa<ConstantSDNode>(
N) || isa<ConstantFPSDNode>(
N)) {
1615 if (
const Constant *
C = dyn_cast<Constant>(V)) {
1624 if (isa<ConstantPointerNull>(
C)) {
1625 unsigned AS = V->getType()->getPointerAddressSpace();
1633 if (
const ConstantFP *CFP = dyn_cast<ConstantFP>(
C))
1636 if (isa<UndefValue>(
C) && !V->getType()->isAggregateType())
1640 visit(CE->getOpcode(), *CE);
1642 assert(N1.
getNode() &&
"visit didn't populate the NodeMap!");
1646 if (isa<ConstantStruct>(
C) || isa<ConstantArray>(
C)) {
1648 for (
const Use &U :
C->operands()) {
1654 for (
unsigned i = 0, e = Val->
getNumValues(); i != e; ++i)
1662 dyn_cast<ConstantDataSequential>(
C)) {
1664 for (
unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
1668 for (
unsigned i = 0, e = Val->
getNumValues(); i != e; ++i)
1672 if (isa<ArrayType>(CDS->getType()))
1677 if (
C->getType()->isStructTy() ||
C->getType()->isArrayTy()) {
1678 assert((isa<ConstantAggregateZero>(
C) || isa<UndefValue>(
C)) &&
1679 "Unknown struct or array constant!");
1683 unsigned NumElts = ValueVTs.
size();
1687 for (
unsigned i = 0; i != NumElts; ++i) {
1688 EVT EltVT = ValueVTs[i];
1689 if (isa<UndefValue>(
C))
1703 if (
const auto *Equiv = dyn_cast<DSOLocalEquivalent>(
C))
1704 return getValue(Equiv->getGlobalValue());
1706 if (
const auto *
NC = dyn_cast<NoCFIValue>(
C))
1709 VectorType *VecTy = cast<VectorType>(V->getType());
1715 unsigned NumElements = cast<FixedVectorType>(VecTy)->getNumElements();
1716 for (
unsigned i = 0; i != NumElements; ++i)
1722 if (isa<ConstantAggregateZero>(
C)) {
1740 if (
const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1749 if (
const Instruction *Inst = dyn_cast<Instruction>(V)) {
1753 Inst->getType(), std::nullopt);
1761 if (
const auto *BB = dyn_cast<BasicBlock>(V))
1767void SelectionDAGBuilder::visitCatchPad(
const CatchPadInst &
I) {
1776 if (IsMSVCCXX || IsCoreCLR)
1792 if (TargetMBB != NextBlock(
FuncInfo.MBB) ||
1803 Value *ParentPad =
I.getCatchSwitchParentPad();
1805 if (isa<ConstantTokenNone>(ParentPad))
1806 SuccessorColor = &
FuncInfo.Fn->getEntryBlock();
1808 SuccessorColor = cast<Instruction>(ParentPad)->
getParent();
1809 assert(SuccessorColor &&
"No parent funclet for catchret!");
1811 assert(SuccessorColorMBB &&
"No MBB for SuccessorColor!");
1820void SelectionDAGBuilder::visitCleanupPad(
const CleanupPadInst &CPI) {
1826 FuncInfo.MBB->setIsEHFuncletEntry();
1827 FuncInfo.MBB->setIsCleanupFuncletEntry();
1864 if (isa<CleanupPadInst>(Pad)) {
1866 UnwindDests.emplace_back(
FuncInfo.MBBMap[EHPadBB], Prob);
1867 UnwindDests.back().first->setIsEHScopeEntry();
1869 }
else if (
const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
1872 for (
const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
1873 UnwindDests.emplace_back(
FuncInfo.MBBMap[CatchPadBB], Prob);
1874 UnwindDests.back().first->setIsEHScopeEntry();
1905 assert(UnwindDests.size() <= 1 &&
1906 "There should be at most one unwind destination for wasm");
1913 if (isa<LandingPadInst>(Pad)) {
1915 UnwindDests.emplace_back(
FuncInfo.MBBMap[EHPadBB], Prob);
1917 }
else if (isa<CleanupPadInst>(Pad)) {
1920 UnwindDests.emplace_back(
FuncInfo.MBBMap[EHPadBB], Prob);
1921 UnwindDests.
back().first->setIsEHScopeEntry();
1922 UnwindDests.back().first->setIsEHFuncletEntry();
1924 }
else if (
const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
1926 for (
const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
1927 UnwindDests.emplace_back(
FuncInfo.MBBMap[CatchPadBB], Prob);
1929 if (IsMSVCCXX || IsCoreCLR)
1930 UnwindDests.back().first->setIsEHFuncletEntry();
1932 UnwindDests.back().first->setIsEHScopeEntry();
1934 NewEHPadBB = CatchSwitch->getUnwindDest();
1940 if (BPI && NewEHPadBB)
1942 EHPadBB = NewEHPadBB;
1949 auto UnwindDest =
I.getUnwindDest();
1956 for (
auto &UnwindDest : UnwindDests) {
1957 UnwindDest.first->setIsEHPad();
1958 addSuccessorWithProb(
FuncInfo.MBB, UnwindDest.first, UnwindDest.second);
1960 FuncInfo.MBB->normalizeSuccProbs();
1968void SelectionDAGBuilder::visitCatchSwitch(
const CatchSwitchInst &CSI) {
1972void SelectionDAGBuilder::visitRet(
const ReturnInst &
I) {
1986 if (
I.getParent()->getTerminatingDeoptimizeCall()) {
1992 unsigned DemoteReg =
FuncInfo.DemoteRegister;
1993 const Function *
F =
I.getParent()->getParent();
2000 F->getReturnType()->getPointerTo(
2012 unsigned NumValues = ValueVTs.
size();
2015 Align BaseAlign =
DL.getPrefTypeAlign(
I.getOperand(0)->getType());
2016 for (
unsigned i = 0; i != NumValues; ++i) {
2023 if (MemVTs[i] != ValueVTs[i])
2034 }
else if (
I.getNumOperands() != 0) {
2037 unsigned NumValues = ValueVTs.
size();
2041 const Function *
F =
I.getParent()->getParent();
2044 I.getOperand(0)->getType(),
F->getCallingConv(),
2048 if (
F->getAttributes().hasRetAttr(Attribute::SExt))
2050 else if (
F->getAttributes().hasRetAttr(Attribute::ZExt))
2054 bool RetInReg =
F->getAttributes().hasRetAttr(Attribute::InReg);
2056 for (
unsigned j = 0;
j != NumValues; ++
j) {
2057 EVT VT = ValueVTs[
j];
2069 &Parts[0], NumParts, PartVT, &
I,
CC, ExtendKind);
2076 if (
I.getOperand(0)->getType()->isPointerTy()) {
2078 Flags.setPointerAddrSpace(
2079 cast<PointerType>(
I.getOperand(0)->getType())->getAddressSpace());
2082 if (NeedsRegBlock) {
2083 Flags.setInConsecutiveRegs();
2084 if (j == NumValues - 1)
2085 Flags.setInConsecutiveRegsLast();
2094 for (
unsigned i = 0; i < NumParts; ++i) {
2096 Parts[i].getValueType().getSimpleVT(),
2107 const Function *
F =
I.getParent()->getParent();
2109 F->getAttributes().hasAttrSomewhere(Attribute::SwiftError)) {
2112 Flags.setSwiftError();
2131 "LowerReturn didn't return a valid chain!");
2142 if (V->getType()->isEmptyTy())
2146 if (VMI !=
FuncInfo.ValueMap.end()) {
2147 assert((!V->use_empty() || isa<CallBrInst>(V)) &&
2148 "Unused value assigned virtual registers!");
2158 if (!isa<Instruction>(V) && !isa<Argument>(V))
return;
2161 if (
FuncInfo.isExportedInst(V))
return;
2173 if (
VI->getParent() == FromBB)
2182 if (isa<Argument>(V)) {
2199 const BasicBlock *SrcBB = Src->getBasicBlock();
2200 const BasicBlock *DstBB = Dst->getBasicBlock();
2204 auto SuccSize = std::max<uint32_t>(
succ_size(SrcBB), 1);
2214 Src->addSuccessorWithoutProb(Dst);
2217 Prob = getEdgeProbability(Src, Dst);
2218 Src->addSuccessor(Dst, Prob);
2224 return I->getParent() == BB;
2244 if (
const CmpInst *BOp = dyn_cast<CmpInst>(
Cond)) {
2248 if (CurBB == SwitchBB ||
2254 InvertCond ? IC->getInversePredicate() : IC->getPredicate();
2259 InvertCond ? FC->getInversePredicate() : FC->getPredicate();
2265 CaseBlock CB(Condition, BOp->getOperand(0), BOp->getOperand(1),
nullptr,
2267 SL->SwitchCases.push_back(CB);
2276 SL->SwitchCases.push_back(CB);
2299 const Value *BOpOp0, *BOpOp1;
2313 if (BOpc == Instruction::And)
2314 BOpc = Instruction::Or;
2315 else if (BOpc == Instruction::Or)
2316 BOpc = Instruction::And;
2322 bool BOpIsInOrAndTree = BOpc && BOpc == Opc && BOp->
hasOneUse();
2327 TProb, FProb, InvertCond);
2337 if (Opc == Instruction::Or) {
2358 auto NewTrueProb = TProb / 2;
2359 auto NewFalseProb = TProb / 2 + FProb;
2362 NewFalseProb, InvertCond);
2369 Probs[1], InvertCond);
2371 assert(Opc == Instruction::And &&
"Unknown merge op!");
2391 auto NewTrueProb = TProb + FProb / 2;
2392 auto NewFalseProb = FProb / 2;
2395 NewFalseProb, InvertCond);
2402 Probs[1], InvertCond);
2411 if (Cases.size() != 2)
return true;
2415 if ((Cases[0].CmpLHS == Cases[1].CmpLHS &&
2416 Cases[0].CmpRHS == Cases[1].CmpRHS) ||
2417 (Cases[0].CmpRHS == Cases[1].CmpLHS &&
2418 Cases[0].CmpLHS == Cases[1].CmpRHS)) {
2424 if (Cases[0].CmpRHS == Cases[1].CmpRHS &&
2425 Cases[0].
CC == Cases[1].
CC &&
2426 isa<Constant>(Cases[0].CmpRHS) &&
2427 cast<Constant>(Cases[0].CmpRHS)->isNullValue()) {
2428 if (Cases[0].
CC ==
ISD::SETEQ && Cases[0].TrueBB == Cases[1].ThisBB)
2430 if (Cases[0].
CC ==
ISD::SETNE && Cases[0].FalseBB == Cases[1].ThisBB)
2437void SelectionDAGBuilder::visitBr(
const BranchInst &
I) {
2443 if (
I.isUnconditional()) {
2459 const Value *CondVal =
I.getCondition();
2479 const Instruction *BOp = dyn_cast<Instruction>(CondVal);
2481 BOp->
hasOneUse() && !
I.hasMetadata(LLVMContext::MD_unpredictable)) {
2483 const Value *BOp0, *BOp1;
2486 Opcode = Instruction::And;
2488 Opcode = Instruction::Or;
2493 getEdgeProbability(BrMBB, Succ0MBB),
2494 getEdgeProbability(BrMBB, Succ1MBB),
2499 assert(
SL->SwitchCases[0].ThisBB == BrMBB &&
"Unexpected lowering!");
2503 for (
unsigned i = 1, e =
SL->SwitchCases.size(); i != e; ++i) {
2510 SL->SwitchCases.erase(
SL->SwitchCases.begin());
2516 for (
unsigned i = 1, e =
SL->SwitchCases.size(); i != e; ++i)
2517 FuncInfo.MF->erase(
SL->SwitchCases[i].ThisBB);
2519 SL->SwitchCases.clear();
2525 nullptr, Succ0MBB, Succ1MBB, BrMBB,
getCurSDLoc());
2544 if (CB.
TrueBB != NextBlock(SwitchBB)) {
2586 if (cast<ConstantInt>(CB.
CmpLHS)->isMinValue(
true)) {
2607 if (CB.
TrueBB == NextBlock(SwitchBB)) {
2631 assert(JT.Reg != -1U &&
"Should lower JT Header first!");
2663 unsigned JumpTableReg =
2666 JumpTableReg, SwitchOp);
2667 JT.Reg = JumpTableReg;
2683 if (JT.MBB != NextBlock(SwitchBB))
2690 if (JT.MBB != NextBlock(SwitchBB))
2717 if (PtrTy != PtrMemTy)
2765 Entry.Node = GuardVal;
2767 if (GuardCheckFn->hasParamAttribute(0, Attribute::AttrKind::InReg))
2768 Entry.IsInReg =
true;
2769 Args.push_back(Entry);
2775 getValue(GuardCheckFn), std::move(Args));
2777 std::pair<SDValue, SDValue> Result = TLI.
LowerCallTo(CLI);
2791 Guard =
DAG.
getLoad(PtrMemTy, dl, Chain, GuardPtr,
2859 bool UsePtrType =
false;
2863 for (
unsigned i = 0, e =
B.Cases.size(); i != e; ++i)
2883 if (!
B.FallthroughUnreachable)
2884 addSuccessorWithProb(SwitchBB,
B.Default,
B.DefaultProb);
2885 addSuccessorWithProb(SwitchBB,
MBB,
B.Prob);
2889 if (!
B.FallthroughUnreachable) {
2902 if (
MBB != NextBlock(SwitchBB))
2921 if (PopCount == 1) {
2928 }
else if (PopCount == BB.
Range) {
2947 addSuccessorWithProb(SwitchBB,
B.TargetBB,
B.ExtraProb);
2949 addSuccessorWithProb(SwitchBB, NextMBB, BranchProbToNext);
2960 if (NextMBB != NextBlock(SwitchBB))
2967void SelectionDAGBuilder::visitInvoke(
const InvokeInst &
I) {
2977 assert(!
I.hasOperandBundlesOtherThan(
2978 {LLVMContext::OB_deopt, LLVMContext::OB_gc_transition,
2979 LLVMContext::OB_gc_live, LLVMContext::OB_funclet,
2980 LLVMContext::OB_cfguardtarget,
2981 LLVMContext::OB_clang_arc_attachedcall}) &&
2982 "Cannot lower invokes with arbitrary operand bundles yet!");
2986 if (isa<InlineAsm>(
Callee))
2987 visitInlineAsm(
I, EHPadBB);
2992 case Intrinsic::donothing:
2994 case Intrinsic::seh_try_begin:
2995 case Intrinsic::seh_scope_begin:
2996 case Intrinsic::seh_try_end:
2997 case Intrinsic::seh_scope_end:
2999 case Intrinsic::experimental_patchpoint_void:
3000 case Intrinsic::experimental_patchpoint_i64:
3001 visitPatchpoint(
I, EHPadBB);
3003 case Intrinsic::experimental_gc_statepoint:
3006 case Intrinsic::wasm_rethrow: {
3035 if (!isa<GCStatepointInst>(
I)) {
3047 addSuccessorWithProb(InvokeMBB, Return);
3048 for (
auto &UnwindDest : UnwindDests) {
3049 UnwindDest.first->setIsEHPad();
3050 addSuccessorWithProb(InvokeMBB, UnwindDest.first, UnwindDest.second);
3059void SelectionDAGBuilder::visitCallBr(
const CallBrInst &
I) {
3064 assert(!
I.hasOperandBundlesOtherThan(
3065 {LLVMContext::OB_deopt, LLVMContext::OB_funclet}) &&
3066 "Cannot lower callbrs with arbitrary operand bundles yet!");
3068 assert(
I.isInlineAsm() &&
"Only know how to handle inlineasm callbr");
3074 Dests.
insert(
I.getDefaultDest());
3079 for (
unsigned i = 0, e =
I.getNumIndirectDests(); i < e; ++i) {
3082 Target->setIsInlineAsmBrIndirectTarget();
3083 Target->setMachineBlockAddressTaken();
3084 Target->setLabelMustBeEmitted();
3086 if (Dests.
insert(Dest).second)
3097void SelectionDAGBuilder::visitResume(
const ResumeInst &RI) {
3098 llvm_unreachable(
"SelectionDAGBuilder shouldn't visit resume instructions!");
3101void SelectionDAGBuilder::visitLandingPad(
const LandingPadInst &LP) {
3103 "Call to landingpad not in landing pad!");
3123 assert(ValueVTs.
size() == 2 &&
"Only two-valued landingpads are supported");
3128 if (
FuncInfo.ExceptionPointerVirtReg) {
3153 if (JTB.first.HeaderBB == First)
3154 JTB.first.HeaderBB =
Last;
3167 for (
unsigned i = 0, e =
I.getNumSuccessors(); i != e; ++i) {
3169 bool Inserted =
Done.insert(BB).second;
3174 addSuccessorWithProb(IndirectBrMBB, Succ);
3193 if (
const CallInst *Call = dyn_cast<CallInst>(&*PredI)) {
3194 if (
Call->doesNotReturn())
3203void SelectionDAGBuilder::visitUnary(
const User &
I,
unsigned Opcode) {
3205 if (
auto *FPOp = dyn_cast<FPMathOperator>(&
I))
3206 Flags.copyFMF(*FPOp);
3214void SelectionDAGBuilder::visitBinary(
const User &
I,
unsigned Opcode) {
3216 if (
auto *OFBinOp = dyn_cast<OverflowingBinaryOperator>(&
I)) {
3217 Flags.setNoSignedWrap(OFBinOp->hasNoSignedWrap());
3218 Flags.setNoUnsignedWrap(OFBinOp->hasNoUnsignedWrap());
3220 if (
auto *ExactOp = dyn_cast<PossiblyExactOperator>(&
I))
3221 Flags.setExact(ExactOp->isExact());
3222 if (
auto *FPOp = dyn_cast<FPMathOperator>(&
I))
3223 Flags.copyFMF(*FPOp);
3232void SelectionDAGBuilder::visitShift(
const User &
I,
unsigned Opcode) {
3241 if (!
I.getType()->isVectorTy() && Op2.
getValueType() != ShiftTy) {
3243 "Unexpected shift type");
3254 dyn_cast<const OverflowingBinaryOperator>(&
I)) {
3255 nuw = OFBinOp->hasNoUnsignedWrap();
3256 nsw = OFBinOp->hasNoSignedWrap();
3259 dyn_cast<const PossiblyExactOperator>(&
I))
3260 exact = ExactOp->isExact();
3263 Flags.setExact(exact);
3264 Flags.setNoSignedWrap(nsw);
3265 Flags.setNoUnsignedWrap(nuw);
3271void SelectionDAGBuilder::visitSDiv(
const User &
I) {
3276 Flags.setExact(isa<PossiblyExactOperator>(&
I) &&
3277 cast<PossiblyExactOperator>(&
I)->isExact());
3282void SelectionDAGBuilder::visitICmp(
const User &
I) {
3284 if (
const ICmpInst *IC = dyn_cast<ICmpInst>(&
I))
3285 predicate = IC->getPredicate();
3286 else if (
const ConstantExpr *IC = dyn_cast<ConstantExpr>(&
I))
3309void SelectionDAGBuilder::visitFCmp(
const User &
I) {
3311 if (
const FCmpInst *FC = dyn_cast<FCmpInst>(&
I))
3312 predicate =
FC->getPredicate();
3313 else if (
const ConstantExpr *FC = dyn_cast<ConstantExpr>(&
I))
3319 auto *FPMO = cast<FPMathOperator>(&
I);
3324 Flags.copyFMF(*FPMO);
3336 return isa<SelectInst>(V);
3340void SelectionDAGBuilder::visitSelect(
const User &
I) {
3344 unsigned NumValues = ValueVTs.
size();
3345 if (NumValues == 0)
return;
3355 bool IsUnaryAbs =
false;
3356 bool Negate =
false;
3359 if (
auto *FPOp = dyn_cast<FPMathOperator>(&
I))
3360 Flags.copyFMF(*FPOp);
3364 EVT VT = ValueVTs[0];
3376 bool UseScalarMinMax = VT.
isVector() &&
3385 switch (SPR.Flavor) {
3391 switch (SPR.NaNBehavior) {
3404 switch (SPR.NaNBehavior) {
3448 for (
unsigned i = 0; i != NumValues; ++i) {
3457 for (
unsigned i = 0; i != NumValues; ++i) {
3471void SelectionDAGBuilder::visitTrunc(
const User &
I) {
3479void SelectionDAGBuilder::visitZExt(
const User &
I) {
3488void SelectionDAGBuilder::visitSExt(
const User &
I) {
3497void SelectionDAGBuilder::visitFPTrunc(
const User &
I) {
3508void SelectionDAGBuilder::visitFPExt(
const User &
I) {
3516void SelectionDAGBuilder::visitFPToUI(
const User &
I) {
3524void SelectionDAGBuilder::visitFPToSI(
const User &
I) {
3532void SelectionDAGBuilder::visitUIToFP(
const User &
I) {
3540void SelectionDAGBuilder::visitSIToFP(
const User &
I) {
3548void SelectionDAGBuilder::visitPtrToInt(
const User &
I) {
3562void SelectionDAGBuilder::visitIntToPtr(
const User &
I) {
3574void SelectionDAGBuilder::visitBitCast(
const User &
I) {
3582 if (DestVT !=
N.getValueType())
3589 else if(
ConstantInt *
C = dyn_cast<ConstantInt>(
I.getOperand(0)))
3596void SelectionDAGBuilder::visitAddrSpaceCast(
const User &
I) {
3598 const Value *SV =
I.getOperand(0);
3603 unsigned DestAS =
I.getType()->getPointerAddressSpace();
3611void SelectionDAGBuilder::visitInsertElement(
const User &
I) {
3619 InVec, InVal, InIdx));
3622void SelectionDAGBuilder::visitExtractElement(
const User &
I) {
3632void SelectionDAGBuilder::visitShuffleVector(
const User &
I) {
3636 if (
auto *SVI = dyn_cast<ShuffleVectorInst>(&
I))
3637 Mask = SVI->getShuffleMask();
3639 Mask = cast<ConstantExpr>(
I).getShuffleMask();
3645 if (
all_of(Mask, [](
int Elem) {
return Elem == 0; }) &&
3661 unsigned MaskNumElts =
Mask.size();
3663 if (SrcNumElts == MaskNumElts) {
3669 if (SrcNumElts < MaskNumElts) {
3673 if (MaskNumElts % SrcNumElts == 0) {
3677 unsigned NumConcat = MaskNumElts / SrcNumElts;
3678 bool IsConcat =
true;
3680 for (
unsigned i = 0; i != MaskNumElts; ++i) {
3686 if ((
Idx % SrcNumElts != (i % SrcNumElts)) ||
3687 (ConcatSrcs[i / SrcNumElts] >= 0 &&
3688 ConcatSrcs[i / SrcNumElts] != (
int)(
Idx / SrcNumElts))) {
3693 ConcatSrcs[i / SrcNumElts] =
Idx / SrcNumElts;
3700 for (
auto Src : ConcatSrcs) {
3713 unsigned PaddedMaskNumElts =
alignTo(MaskNumElts, SrcNumElts);
3714 unsigned NumConcat = PaddedMaskNumElts / SrcNumElts;
3731 for (
unsigned i = 0; i != MaskNumElts; ++i) {
3733 if (
Idx >= (
int)SrcNumElts)
3734 Idx -= SrcNumElts - PaddedMaskNumElts;
3742 if (MaskNumElts != PaddedMaskNumElts)
3750 if (SrcNumElts > MaskNumElts) {
3753 int StartIdx[2] = { -1, -1 };
3754 bool CanExtract =
true;
3755 for (
int Idx : Mask) {
3760 if (
Idx >= (
int)SrcNumElts) {
3769 if (NewStartIdx + MaskNumElts > SrcNumElts ||
3770 (StartIdx[Input] >= 0 && StartIdx[Input] != NewStartIdx))
3774 StartIdx[Input] = NewStartIdx;
3777 if (StartIdx[0] < 0 && StartIdx[1] < 0) {
3783 for (
unsigned Input = 0; Input < 2; ++Input) {
3784 SDValue &Src = Input == 0 ? Src1 : Src2;
3785 if (StartIdx[Input] < 0)
3795 for (
int &
Idx : MappedOps) {
3796 if (
Idx >= (
int)SrcNumElts)
3797 Idx -= SrcNumElts + StartIdx[1] - MaskNumElts;
3812 for (
int Idx : Mask) {
3818 SDValue &Src =
Idx < (int)SrcNumElts ? Src1 : Src2;
3819 if (
Idx >= (
int)SrcNumElts)
Idx -= SrcNumElts;
3833 const Value *Op0 =
I.getOperand(0);
3834 const Value *Op1 =
I.getOperand(1);
3835 Type *AggTy =
I.getType();
3837 bool IntoUndef = isa<UndefValue>(Op0);
3838 bool FromUndef = isa<UndefValue>(Op1);
3848 unsigned NumAggValues = AggValueVTs.
size();
3849 unsigned NumValValues = ValValueVTs.
size();
3853 if (!NumAggValues) {
3861 for (; i != LinearIndex; ++i)
3862 Values[i] = IntoUndef ?
DAG.
getUNDEF(AggValueVTs[i]) :
3867 for (; i != LinearIndex + NumValValues; ++i)
3868 Values[i] = FromUndef ?
DAG.
getUNDEF(AggValueVTs[i]) :
3872 for (; i != NumAggValues; ++i)
3873 Values[i] = IntoUndef ?
DAG.
getUNDEF(AggValueVTs[i]) :
3882 const Value *Op0 =
I.getOperand(0);
3884 Type *ValTy =
I.getType();
3885 bool OutOfUndef = isa<UndefValue>(Op0);
3893 unsigned NumValValues = ValValueVTs.
size();
3896 if (!NumValValues) {
3905 for (
unsigned i = LinearIndex; i != LinearIndex + NumValValues; ++i)
3906 Values[i - LinearIndex] =
3915void SelectionDAGBuilder::visitGetElementPtr(
const User &
I) {
3916 Value *Op0 =
I.getOperand(0);
3926 bool IsVectorGEP =
I.getType()->isVectorTy();
3928 IsVectorGEP ? cast<VectorType>(
I.getType())->getElementCount()
3931 if (IsVectorGEP && !
N.getValueType().isVector()) {
3939 const Value *
Idx = GTI.getOperand();
3940 if (
StructType *StTy = GTI.getStructTypeOrNull()) {
3941 unsigned Field = cast<Constant>(
Idx)->getUniqueInteger().getZExtValue();
3950 if (int64_t(
Offset) >= 0 && cast<GEPOperator>(
I).isInBounds())
3951 Flags.setNoUnsignedWrap(
true);
3967 bool ElementScalable = ElementSize.
isScalable();
3971 const auto *
C = dyn_cast<Constant>(
Idx);
3972 if (
C && isa<VectorType>(
C->getType()))
3973 C =
C->getSplatValue();
3975 const auto *CI = dyn_cast_or_null<ConstantInt>(
C);
3976 if (CI && CI->isZero())
3978 if (CI && !ElementScalable) {
3992 Flags.setNoUnsignedWrap(
true);
4005 VectorElementCount);
4013 if (ElementScalable) {
4014 EVT VScaleTy =
N.getValueType().getScalarType();
4024 if (ElementMul != 1) {
4025 if (ElementMul.isPowerOf2()) {
4026 unsigned Amt = ElementMul.logBase2();
4028 N.getValueType(), IdxN,
4034 N.getValueType(), IdxN, Scale);
4040 N.getValueType(),
N, IdxN);
4051 if (PtrMemTy != PtrTy && !cast<GEPOperator>(
I).isInBounds())
4057void SelectionDAGBuilder::visitAlloca(
const AllocaInst &
I) {
4064 Type *Ty =
I.getAllocatedType();
4068 MaybeAlign Alignment = std::max(
DL.getPrefTypeAlign(Ty),
I.getAlign());
4090 if (*Alignment <= StackAlign)
4091 Alignment = std::nullopt;
4098 Flags.setNoUnsignedWrap(
true);
4108 DAG.
getConstant(Alignment ? Alignment->value() : 0, dl, IntPtr)};
4117void SelectionDAGBuilder::visitLoad(
const LoadInst &
I) {
4119 return visitAtomicLoad(
I);
4122 const Value *SV =
I.getOperand(0);
4126 if (
const Argument *
Arg = dyn_cast<Argument>(SV)) {
4127 if (
Arg->hasSwiftErrorAttr())
4128 return visitLoadFromSwiftError(
I);
4131 if (
const AllocaInst *Alloca = dyn_cast<AllocaInst>(SV)) {
4132 if (Alloca->isSwiftError())
4133 return visitLoadFromSwiftError(
I);
4139 Type *Ty =
I.getType();
4143 unsigned NumValues = ValueVTs.
size();
4147 Align Alignment =
I.getAlign();
4149 const MDNode *
Ranges =
I.getMetadata(LLVMContext::MD_range);
4150 bool isVolatile =
I.isVolatile();
4155 bool ConstantMemory =
false;
4168 ConstantMemory =
true;