diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 813 |
1 files changed, 441 insertions, 372 deletions
diff --git a/contrib/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/contrib/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 64e6c22..bdf57e8 100644 --- a/contrib/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/contrib/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -1,4 +1,4 @@ -//===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===// +//===- SelectionDAGISel.cpp - Implement the SelectionDAGISel class --------===// // // The LLVM Compiler Infrastructure // @@ -11,43 +11,73 @@ // //===----------------------------------------------------------------------===// -#include "llvm/CodeGen/SelectionDAG.h" #include "ScheduleDAGSDNodes.h" #include "SelectionDAGBuilder.h" +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/None.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/CFG.h" -#include "llvm/Analysis/EHPersonalities.h" +#include "llvm/Analysis/OptimizationDiagnosticInfo.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/CodeGen/FastISel.h" #include "llvm/CodeGen/FunctionLoweringInfo.h" #include "llvm/CodeGen/GCMetadata.h" -#include "llvm/CodeGen/GCStrategy.h" +#include "llvm/CodeGen/ISDOpcodes.h" +#include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBuilder.h" -#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/MachineMemOperand.h" +#include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/MachinePassRegistry.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/ScheduleHazardRecognizer.h" +#include "llvm/CodeGen/MachineValueType.h" #include "llvm/CodeGen/SchedulerRegistry.h" +#include "llvm/CodeGen/SelectionDAG.h" #include "llvm/CodeGen/SelectionDAGISel.h" +#include "llvm/CodeGen/SelectionDAGNodes.h" #include "llvm/CodeGen/StackProtector.h" -#include "llvm/CodeGen/WinEHFuncInfo.h" +#include "llvm/CodeGen/ValueTypes.h" +#include "llvm/IR/BasicBlock.h" #include "llvm/IR/Constants.h" -#include "llvm/IR/DebugInfo.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/DebugInfoMetadata.h" +#include "llvm/IR/DebugLoc.h" +#include "llvm/IR/DiagnosticInfo.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InlineAsm.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/MC/MCAsmInfo.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/Pass.h" +#include "llvm/Support/BranchProbability.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CodeGen.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/KnownBits.h" #include "llvm/Support/Timer.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" @@ -59,6 +89,14 @@ #include "llvm/Target/TargetSubtargetInfo.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include <algorithm> +#include <cassert> +#include <cstdint> +#include <iterator> +#include <limits> +#include <memory> +#include <string> +#include <utility> +#include <vector> using namespace llvm; @@ -73,104 +111,6 @@ STATISTIC(NumEntryBlocks, "Number of entry blocks encountered"); STATISTIC(NumFastIselFailLowerArguments, "Number of entry blocks where fast isel failed to lower arguments"); -#ifndef NDEBUG -static cl::opt<bool> -EnableFastISelVerbose2("fast-isel-verbose2", cl::Hidden, - cl::desc("Enable extra verbose messages in the \"fast\" " - "instruction selector")); - - // Terminators -STATISTIC(NumFastIselFailRet,"Fast isel fails on Ret"); -STATISTIC(NumFastIselFailBr,"Fast isel fails on Br"); -STATISTIC(NumFastIselFailSwitch,"Fast isel fails on Switch"); -STATISTIC(NumFastIselFailIndirectBr,"Fast isel fails on IndirectBr"); -STATISTIC(NumFastIselFailInvoke,"Fast isel fails on Invoke"); -STATISTIC(NumFastIselFailResume,"Fast isel fails on Resume"); -STATISTIC(NumFastIselFailUnreachable,"Fast isel fails on Unreachable"); - - // Standard binary operators... -STATISTIC(NumFastIselFailAdd,"Fast isel fails on Add"); -STATISTIC(NumFastIselFailFAdd,"Fast isel fails on FAdd"); -STATISTIC(NumFastIselFailSub,"Fast isel fails on Sub"); -STATISTIC(NumFastIselFailFSub,"Fast isel fails on FSub"); -STATISTIC(NumFastIselFailMul,"Fast isel fails on Mul"); -STATISTIC(NumFastIselFailFMul,"Fast isel fails on FMul"); -STATISTIC(NumFastIselFailUDiv,"Fast isel fails on UDiv"); -STATISTIC(NumFastIselFailSDiv,"Fast isel fails on SDiv"); -STATISTIC(NumFastIselFailFDiv,"Fast isel fails on FDiv"); -STATISTIC(NumFastIselFailURem,"Fast isel fails on URem"); -STATISTIC(NumFastIselFailSRem,"Fast isel fails on SRem"); -STATISTIC(NumFastIselFailFRem,"Fast isel fails on FRem"); - - // Logical operators... -STATISTIC(NumFastIselFailAnd,"Fast isel fails on And"); -STATISTIC(NumFastIselFailOr,"Fast isel fails on Or"); -STATISTIC(NumFastIselFailXor,"Fast isel fails on Xor"); - - // Memory instructions... -STATISTIC(NumFastIselFailAlloca,"Fast isel fails on Alloca"); -STATISTIC(NumFastIselFailLoad,"Fast isel fails on Load"); -STATISTIC(NumFastIselFailStore,"Fast isel fails on Store"); -STATISTIC(NumFastIselFailAtomicCmpXchg,"Fast isel fails on AtomicCmpXchg"); -STATISTIC(NumFastIselFailAtomicRMW,"Fast isel fails on AtomicRWM"); -STATISTIC(NumFastIselFailFence,"Fast isel fails on Frence"); -STATISTIC(NumFastIselFailGetElementPtr,"Fast isel fails on GetElementPtr"); - - // Convert instructions... -STATISTIC(NumFastIselFailTrunc,"Fast isel fails on Trunc"); -STATISTIC(NumFastIselFailZExt,"Fast isel fails on ZExt"); -STATISTIC(NumFastIselFailSExt,"Fast isel fails on SExt"); -STATISTIC(NumFastIselFailFPTrunc,"Fast isel fails on FPTrunc"); -STATISTIC(NumFastIselFailFPExt,"Fast isel fails on FPExt"); -STATISTIC(NumFastIselFailFPToUI,"Fast isel fails on FPToUI"); -STATISTIC(NumFastIselFailFPToSI,"Fast isel fails on FPToSI"); -STATISTIC(NumFastIselFailUIToFP,"Fast isel fails on UIToFP"); -STATISTIC(NumFastIselFailSIToFP,"Fast isel fails on SIToFP"); -STATISTIC(NumFastIselFailIntToPtr,"Fast isel fails on IntToPtr"); -STATISTIC(NumFastIselFailPtrToInt,"Fast isel fails on PtrToInt"); -STATISTIC(NumFastIselFailBitCast,"Fast isel fails on BitCast"); - - // Other instructions... -STATISTIC(NumFastIselFailICmp,"Fast isel fails on ICmp"); -STATISTIC(NumFastIselFailFCmp,"Fast isel fails on FCmp"); -STATISTIC(NumFastIselFailPHI,"Fast isel fails on PHI"); -STATISTIC(NumFastIselFailSelect,"Fast isel fails on Select"); -STATISTIC(NumFastIselFailCall,"Fast isel fails on Call"); -STATISTIC(NumFastIselFailShl,"Fast isel fails on Shl"); -STATISTIC(NumFastIselFailLShr,"Fast isel fails on LShr"); -STATISTIC(NumFastIselFailAShr,"Fast isel fails on AShr"); -STATISTIC(NumFastIselFailVAArg,"Fast isel fails on VAArg"); -STATISTIC(NumFastIselFailExtractElement,"Fast isel fails on ExtractElement"); -STATISTIC(NumFastIselFailInsertElement,"Fast isel fails on InsertElement"); -STATISTIC(NumFastIselFailShuffleVector,"Fast isel fails on ShuffleVector"); -STATISTIC(NumFastIselFailExtractValue,"Fast isel fails on ExtractValue"); -STATISTIC(NumFastIselFailInsertValue,"Fast isel fails on InsertValue"); -STATISTIC(NumFastIselFailLandingPad,"Fast isel fails on LandingPad"); - -// Intrinsic instructions... -STATISTIC(NumFastIselFailIntrinsicCall, "Fast isel fails on Intrinsic call"); -STATISTIC(NumFastIselFailSAddWithOverflow, - "Fast isel fails on sadd.with.overflow"); -STATISTIC(NumFastIselFailUAddWithOverflow, - "Fast isel fails on uadd.with.overflow"); -STATISTIC(NumFastIselFailSSubWithOverflow, - "Fast isel fails on ssub.with.overflow"); -STATISTIC(NumFastIselFailUSubWithOverflow, - "Fast isel fails on usub.with.overflow"); -STATISTIC(NumFastIselFailSMulWithOverflow, - "Fast isel fails on smul.with.overflow"); -STATISTIC(NumFastIselFailUMulWithOverflow, - "Fast isel fails on umul.with.overflow"); -STATISTIC(NumFastIselFailFrameaddress, "Fast isel fails on Frameaddress"); -STATISTIC(NumFastIselFailSqrt, "Fast isel fails on sqrt call"); -STATISTIC(NumFastIselFailStackMap, "Fast isel fails on StackMap call"); -STATISTIC(NumFastIselFailPatchPoint, "Fast isel fails on PatchPoint call"); -#endif - -static cl::opt<bool> -EnableFastISelVerbose("fast-isel-verbose", cl::Hidden, - cl::desc("Enable verbose messages in the \"fast\" " - "instruction selector")); static cl::opt<int> EnableFastISelAbort( "fast-isel-abort", cl::Hidden, cl::desc("Enable abort calls when \"fast\" instruction selection " @@ -179,6 +119,11 @@ static cl::opt<int> EnableFastISelAbort( "abort for argument lowering, and 3 will never fallback " "to SelectionDAG.")); +static cl::opt<bool> EnableFastISelFallbackReport( + "fast-isel-report-on-fallback", cl::Hidden, + cl::desc("Emit a diagnostic when \"fast\" instruction selection " + "falls back to SelectionDAG.")); + static cl::opt<bool> UseMBPI("use-mbpi", cl::desc("use Machine Branch Probability Info"), @@ -238,7 +183,7 @@ MachinePassRegistry RegisterScheduler::Registry; /// //===---------------------------------------------------------------------===// static cl::opt<RegisterScheduler::FunctionPassCtor, false, - RegisterPassParser<RegisterScheduler> > + RegisterPassParser<RegisterScheduler>> ISHeuristic("pre-RA-sched", cl::init(&createDefaultScheduler), cl::Hidden, cl::desc("Instruction schedulers available (before register" @@ -249,6 +194,7 @@ defaultListDAGScheduler("default", "Best scheduler for the target", createDefaultScheduler); namespace llvm { + //===--------------------------------------------------------------------===// /// \brief This class is used by SelectionDAGISel to temporarily override /// the optimization level on a per-function basis. @@ -318,6 +264,7 @@ namespace llvm { "Unknown sched type!"); return createILPListDAGScheduler(IS, OptLevel); } + } // end namespace llvm // EmitInstrWithCustomInserter - This method should be implemented by targets @@ -357,7 +304,7 @@ SelectionDAGISel::SelectionDAGISel(TargetMachine &tm, FuncInfo(new FunctionLoweringInfo()), CurDAG(new SelectionDAG(tm, OL)), SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)), - GFI(), + AA(), GFI(), OptLevel(OL), DAGSize(0) { initializeGCModuleInfoPass(*PassRegistry::getPassRegistry()); @@ -375,7 +322,8 @@ SelectionDAGISel::~SelectionDAGISel() { } void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<AAResultsWrapperPass>(); + if (OptLevel != CodeGenOpt::None) + AU.addRequired<AAResultsWrapperPass>(); AU.addRequired<GCModuleInfo>(); AU.addRequired<StackProtector>(); AU.addPreserved<StackProtector>(); @@ -389,11 +337,13 @@ void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { /// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that /// may trap on it. In this case we have to split the edge so that the path /// through the predecessor block that doesn't go to the phi block doesn't -/// execute the possibly trapping instruction. -/// +/// execute the possibly trapping instruction. If available, we pass domtree +/// and loop info to be updated when we split critical edges. This is because +/// SelectionDAGISel preserves these analyses. /// This is required for correctness, so it must be done at -O0. /// -static void SplitCriticalSideEffectEdges(Function &Fn) { +static void SplitCriticalSideEffectEdges(Function &Fn, DominatorTree *DT, + LoopInfo *LI) { // Loop for blocks with phi nodes. for (BasicBlock &BB : Fn) { PHINode *PN = dyn_cast<PHINode>(BB.begin()); @@ -419,7 +369,7 @@ static void SplitCriticalSideEffectEdges(Function &Fn) { // Okay, we have to split this edge. SplitCriticalEdge( Pred->getTerminator(), GetSuccessorNumber(Pred, &BB), - CriticalEdgeSplittingOptions().setMergeIdenticalEdges()); + CriticalEdgeSplittingOptions(DT, LI).setMergeIdenticalEdges()); goto ReprocessBlock; } } @@ -431,8 +381,6 @@ bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { MachineFunctionProperties::Property::Selected)) return false; // Do some sanity-checking on the command-line options. - assert((!EnableFastISelVerbose || TM.Options.EnableFastISel) && - "-fast-isel-verbose requires -fast-isel"); assert((!EnableFastISelAbort || TM.Options.EnableFastISel) && "-fast-isel-abort > 0 requires -fast-isel"); @@ -454,23 +402,37 @@ bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { TII = MF->getSubtarget().getInstrInfo(); TLI = MF->getSubtarget().getTargetLowering(); RegInfo = &MF->getRegInfo(); - AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : nullptr; + ORE = make_unique<OptimizationRemarkEmitter>(&Fn); + auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); + DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr; + auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); + LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n"); - SplitCriticalSideEffectEdges(const_cast<Function &>(Fn)); + SplitCriticalSideEffectEdges(const_cast<Function &>(Fn), DT, LI); - CurDAG->init(*MF); + CurDAG->init(*MF, *ORE); FuncInfo->set(Fn, *MF, CurDAG); + // Now get the optional analyzes if we want to. + // This is based on the possibly changed OptLevel (after optnone is taken + // into account). That's unfortunate but OK because it just means we won't + // ask for passes that have been required anyway. + if (UseMBPI && OptLevel != CodeGenOpt::None) FuncInfo->BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI(); else FuncInfo->BPI = nullptr; - SDB->init(GFI, *AA, LibInfo); + if (OptLevel != CodeGenOpt::None) + AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); + else + AA = nullptr; + + SDB->init(GFI, AA, LibInfo); MF->setHasInlineAsm(false); @@ -502,6 +464,10 @@ bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { TLI->initializeSplitCSR(EntryMBB); SelectAllBasicBlocks(Fn); + if (FastISelFailed && EnableFastISelFallbackReport) { + DiagnosticInfoISelFallback DiagFallback(Fn); + Fn.getContext().diagnose(DiagFallback); + } // If the first basic block in the function has live ins that need to be // copied into vregs, emit the copies into the top of the block before @@ -628,7 +594,7 @@ bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { unsigned To = I->second; // If To is also scheduled to be replaced, find what its ultimate // replacement is. - for (;;) { + while (true) { DenseMap<unsigned, unsigned>::iterator J = FuncInfo->RegFixups.find(To); if (J == E) break; To = J->second; @@ -648,13 +614,7 @@ bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { MRI.replaceRegWith(From, To); } - if (TLI->hasCopyImplyingStackAdjustment(MF)) - MFI.setHasCopyImplyingStackAdjustment(true); - - // Freeze the set of reserved registers now that MachineFrameInfo has been - // set up. All the information required by getReservedRegs() should be - // available now. - MRI.freezeReservedRegs(*MF); + TLI->finalizeLowering(*MF); // Release function-specific state. SDB and CurDAG are already cleared // at this point. @@ -666,13 +626,30 @@ bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { return true; } +static void reportFastISelFailure(MachineFunction &MF, + OptimizationRemarkEmitter &ORE, + OptimizationRemarkMissed &R, + bool ShouldAbort) { + // Print the function name explicitly if we don't have a debug location (which + // makes the diagnostic less useful) or if we're going to emit a raw error. + if (!R.getLocation().isValid() || ShouldAbort) + R << (" (in function: " + MF.getName() + ")").str(); + + if (ShouldAbort) + report_fatal_error(R.getMsg()); + + ORE.emit(R); +} + void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin, BasicBlock::const_iterator End, bool &HadTailCall) { // Lower the instructions. If a call is emitted as a tail call, cease emitting // nodes for this block. - for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) - SDB->visit(*I); + for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) { + if (!ElidedArgCopyInstrs.count(&*I)) + SDB->visit(*I); + } // Make sure the root of the DAG is up-to-date. CurDAG->setRoot(SDB->getControlRoot()); @@ -689,8 +666,7 @@ void SelectionDAGISel::ComputeLiveOutVRegInfo() { Worklist.push_back(CurDAG->getRoot().getNode()); - APInt KnownZero; - APInt KnownOne; + KnownBits Known; do { SDNode *N = Worklist.pop_back_val(); @@ -719,8 +695,8 @@ void SelectionDAGISel::ComputeLiveOutVRegInfo() { continue; unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src); - CurDAG->computeKnownBits(Src, KnownZero, KnownOne); - FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, KnownZero, KnownOne); + CurDAG->computeKnownBits(Src, Known); + FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known); } while (!Worklist.empty()); } @@ -731,6 +707,10 @@ void SelectionDAGISel::CodeGenAndEmitDAG() { int BlockNumber = -1; (void)BlockNumber; bool MatchFilterBB = false; (void)MatchFilterBB; + + // Pre-type legalization allow creation of any node types. + CurDAG->NewNodesMustHaveLegalTypes = false; + #ifndef NDEBUG MatchFilterBB = (FilterDAGBasicBlockName.empty() || FilterDAGBasicBlockName == @@ -756,7 +736,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() { { NamedRegionTimer T("combine1", "DAG Combining 1", GroupName, GroupDescription, TimePassesIsEnabled); - CurDAG->Combine(BeforeLegalizeTypes, *AA, OptLevel); + CurDAG->Combine(BeforeLegalizeTypes, AA, OptLevel); } DEBUG(dbgs() << "Optimized lowered selection DAG: BB#" << BlockNumber @@ -777,6 +757,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() { DEBUG(dbgs() << "Type-legalized selection DAG: BB#" << BlockNumber << " '" << BlockName << "'\n"; CurDAG->dump()); + // Only allow creation of legal node types. CurDAG->NewNodesMustHaveLegalTypes = true; if (Changed) { @@ -787,12 +768,11 @@ void SelectionDAGISel::CodeGenAndEmitDAG() { { NamedRegionTimer T("combine_lt", "DAG Combining after legalize types", GroupName, GroupDescription, TimePassesIsEnabled); - CurDAG->Combine(AfterLegalizeTypes, *AA, OptLevel); + CurDAG->Combine(AfterLegalizeTypes, AA, OptLevel); } DEBUG(dbgs() << "Optimized type-legalized selection DAG: BB#" << BlockNumber << " '" << BlockName << "'\n"; CurDAG->dump()); - } { @@ -802,12 +782,18 @@ void SelectionDAGISel::CodeGenAndEmitDAG() { } if (Changed) { + DEBUG(dbgs() << "Vector-legalized selection DAG: BB#" << BlockNumber + << " '" << BlockName << "'\n"; CurDAG->dump()); + { NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName, GroupDescription, TimePassesIsEnabled); CurDAG->LegalizeTypes(); } + DEBUG(dbgs() << "Vector/type-legalized selection DAG: BB#" << BlockNumber + << " '" << BlockName << "'\n"; CurDAG->dump()); + if (ViewDAGCombineLT && MatchFilterBB) CurDAG->viewGraph("dag-combine-lv input for " + BlockName); @@ -815,7 +801,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() { { NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors", GroupName, GroupDescription, TimePassesIsEnabled); - CurDAG->Combine(AfterLegalizeVectorOps, *AA, OptLevel); + CurDAG->Combine(AfterLegalizeVectorOps, AA, OptLevel); } DEBUG(dbgs() << "Optimized vector-legalized selection DAG: BB#" @@ -841,7 +827,7 @@ void SelectionDAGISel::CodeGenAndEmitDAG() { { NamedRegionTimer T("combine2", "DAG Combining 2", GroupName, GroupDescription, TimePassesIsEnabled); - CurDAG->Combine(AfterLegalizeDAG, *AA, OptLevel); + CurDAG->Combine(AfterLegalizeDAG, AA, OptLevel); } DEBUG(dbgs() << "Optimized legalized selection DAG: BB#" << BlockNumber @@ -907,10 +893,12 @@ void SelectionDAGISel::CodeGenAndEmitDAG() { } namespace { + /// ISelUpdater - helper class to handle updates of the instruction selection /// graph. class ISelUpdater : public SelectionDAG::DAGUpdateListener { SelectionDAG::allnodes_iterator &ISelPosition; + public: ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp) : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {} @@ -923,6 +911,7 @@ public: ++ISelPosition; } }; + } // end anonymous namespace void SelectionDAGISel::DoInstructionSelection() { @@ -960,6 +949,19 @@ void SelectionDAGISel::DoInstructionSelection() { if (Node->use_empty()) continue; + // When we are using non-default rounding modes or FP exception behavior + // FP operations are represented by StrictFP pseudo-operations. They + // need to be simplified here so that the target-specific instruction + // selectors know how to handle them. + // + // If the current node is a strict FP pseudo-op, the isStrictFPOp() + // function will provide the corresponding normal FP opcode to which the + // node should be mutated. + // + // FIXME: The backends need a way to handle FP constraints. + if (Node->isStrictFPOpcode()) + Node = CurDAG->mutateStrictFPToFP(Node); + Select(Node); } @@ -1046,116 +1048,6 @@ static bool isFoldedOrDeadInstruction(const Instruction *I, !FuncInfo->isExportedInst(I); // Exported instrs must be computed. } -#ifndef NDEBUG -// Collect per Instruction statistics for fast-isel misses. Only those -// instructions that cause the bail are accounted for. It does not account for -// instructions higher in the block. Thus, summing the per instructions stats -// will not add up to what is reported by NumFastIselFailures. -static void collectFailStats(const Instruction *I) { - switch (I->getOpcode()) { - default: assert (0 && "<Invalid operator> "); - - // Terminators - case Instruction::Ret: NumFastIselFailRet++; return; - case Instruction::Br: NumFastIselFailBr++; return; - case Instruction::Switch: NumFastIselFailSwitch++; return; - case Instruction::IndirectBr: NumFastIselFailIndirectBr++; return; - case Instruction::Invoke: NumFastIselFailInvoke++; return; - case Instruction::Resume: NumFastIselFailResume++; return; - case Instruction::Unreachable: NumFastIselFailUnreachable++; return; - - // Standard binary operators... - case Instruction::Add: NumFastIselFailAdd++; return; - case Instruction::FAdd: NumFastIselFailFAdd++; return; - case Instruction::Sub: NumFastIselFailSub++; return; - case Instruction::FSub: NumFastIselFailFSub++; return; - case Instruction::Mul: NumFastIselFailMul++; return; - case Instruction::FMul: NumFastIselFailFMul++; return; - case Instruction::UDiv: NumFastIselFailUDiv++; return; - case Instruction::SDiv: NumFastIselFailSDiv++; return; - case Instruction::FDiv: NumFastIselFailFDiv++; return; - case Instruction::URem: NumFastIselFailURem++; return; - case Instruction::SRem: NumFastIselFailSRem++; return; - case Instruction::FRem: NumFastIselFailFRem++; return; - - // Logical operators... - case Instruction::And: NumFastIselFailAnd++; return; - case Instruction::Or: NumFastIselFailOr++; return; - case Instruction::Xor: NumFastIselFailXor++; return; - - // Memory instructions... - case Instruction::Alloca: NumFastIselFailAlloca++; return; - case Instruction::Load: NumFastIselFailLoad++; return; - case Instruction::Store: NumFastIselFailStore++; return; - case Instruction::AtomicCmpXchg: NumFastIselFailAtomicCmpXchg++; return; - case Instruction::AtomicRMW: NumFastIselFailAtomicRMW++; return; - case Instruction::Fence: NumFastIselFailFence++; return; - case Instruction::GetElementPtr: NumFastIselFailGetElementPtr++; return; - - // Convert instructions... - case Instruction::Trunc: NumFastIselFailTrunc++; return; - case Instruction::ZExt: NumFastIselFailZExt++; return; - case Instruction::SExt: NumFastIselFailSExt++; return; - case Instruction::FPTrunc: NumFastIselFailFPTrunc++; return; - case Instruction::FPExt: NumFastIselFailFPExt++; return; - case Instruction::FPToUI: NumFastIselFailFPToUI++; return; - case Instruction::FPToSI: NumFastIselFailFPToSI++; return; - case Instruction::UIToFP: NumFastIselFailUIToFP++; return; - case Instruction::SIToFP: NumFastIselFailSIToFP++; return; - case Instruction::IntToPtr: NumFastIselFailIntToPtr++; return; - case Instruction::PtrToInt: NumFastIselFailPtrToInt++; return; - case Instruction::BitCast: NumFastIselFailBitCast++; return; - - // Other instructions... - case Instruction::ICmp: NumFastIselFailICmp++; return; - case Instruction::FCmp: NumFastIselFailFCmp++; return; - case Instruction::PHI: NumFastIselFailPHI++; return; - case Instruction::Select: NumFastIselFailSelect++; return; - case Instruction::Call: { - if (auto const *Intrinsic = dyn_cast<IntrinsicInst>(I)) { - switch (Intrinsic->getIntrinsicID()) { - default: - NumFastIselFailIntrinsicCall++; return; - case Intrinsic::sadd_with_overflow: - NumFastIselFailSAddWithOverflow++; return; - case Intrinsic::uadd_with_overflow: - NumFastIselFailUAddWithOverflow++; return; - case Intrinsic::ssub_with_overflow: - NumFastIselFailSSubWithOverflow++; return; - case Intrinsic::usub_with_overflow: - NumFastIselFailUSubWithOverflow++; return; - case Intrinsic::smul_with_overflow: - NumFastIselFailSMulWithOverflow++; return; - case Intrinsic::umul_with_overflow: - NumFastIselFailUMulWithOverflow++; return; - case Intrinsic::frameaddress: - NumFastIselFailFrameaddress++; return; - case Intrinsic::sqrt: - NumFastIselFailSqrt++; return; - case Intrinsic::experimental_stackmap: - NumFastIselFailStackMap++; return; - case Intrinsic::experimental_patchpoint_void: // fall-through - case Intrinsic::experimental_patchpoint_i64: - NumFastIselFailPatchPoint++; return; - } - } - NumFastIselFailCall++; - return; - } - case Instruction::Shl: NumFastIselFailShl++; return; - case Instruction::LShr: NumFastIselFailLShr++; return; - case Instruction::AShr: NumFastIselFailAShr++; return; - case Instruction::VAArg: NumFastIselFailVAArg++; return; - case Instruction::ExtractElement: NumFastIselFailExtractElement++; return; - case Instruction::InsertElement: NumFastIselFailInsertElement++; return; - case Instruction::ShuffleVector: NumFastIselFailShuffleVector++; return; - case Instruction::ExtractValue: NumFastIselFailExtractValue++; return; - case Instruction::InsertValue: NumFastIselFailInsertValue++; return; - case Instruction::LandingPad: NumFastIselFailLandingPad++; return; - } -} -#endif // NDEBUG - /// Set up SwiftErrorVals by going through the function. If the function has /// swifterror argument, it will be the first entry. static void setupSwiftErrorVals(const Function &Fn, const TargetLowering *TLI, @@ -1166,6 +1058,7 @@ static void setupSwiftErrorVals(const Function &Fn, const TargetLowering *TLI, FuncInfo->SwiftErrorVals.clear(); FuncInfo->SwiftErrorVRegDefMap.clear(); FuncInfo->SwiftErrorVRegUpwardsUse.clear(); + FuncInfo->SwiftErrorVRegDefUses.clear(); FuncInfo->SwiftErrorArg = nullptr; // Check if function has a swifterror argument. @@ -1190,9 +1083,9 @@ static void setupSwiftErrorVals(const Function &Fn, const TargetLowering *TLI, } static void createSwiftErrorEntriesInEntryBlock(FunctionLoweringInfo *FuncInfo, + FastISel *FastIS, const TargetLowering *TLI, const TargetInstrInfo *TII, - const BasicBlock *LLVMBB, SelectionDAGBuilder *SDB) { if (!TLI->supportSwiftError()) return; @@ -1202,21 +1095,71 @@ static void createSwiftErrorEntriesInEntryBlock(FunctionLoweringInfo *FuncInfo, if (FuncInfo->SwiftErrorVals.empty()) return; - if (pred_begin(LLVMBB) == pred_end(LLVMBB)) { - auto &DL = FuncInfo->MF->getDataLayout(); - auto const *RC = TLI->getRegClassFor(TLI->getPointerTy(DL)); - for (const auto *SwiftErrorVal : FuncInfo->SwiftErrorVals) { - // We will always generate a copy from the argument. It is always used at - // least by the 'return' of the swifterror. - if (FuncInfo->SwiftErrorArg && FuncInfo->SwiftErrorArg == SwiftErrorVal) + assert(FuncInfo->MBB == &*FuncInfo->MF->begin() && + "expected to insert into entry block"); + auto &DL = FuncInfo->MF->getDataLayout(); + auto const *RC = TLI->getRegClassFor(TLI->getPointerTy(DL)); + for (const auto *SwiftErrorVal : FuncInfo->SwiftErrorVals) { + // We will always generate a copy from the argument. It is always used at + // least by the 'return' of the swifterror. + if (FuncInfo->SwiftErrorArg && FuncInfo->SwiftErrorArg == SwiftErrorVal) + continue; + unsigned VReg = FuncInfo->MF->getRegInfo().createVirtualRegister(RC); + // Assign Undef to Vreg. We construct MI directly to make sure it works + // with FastISel. + BuildMI(*FuncInfo->MBB, FuncInfo->MBB->getFirstNonPHI(), + SDB->getCurDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF), + VReg); + + // Keep FastIS informed about the value we just inserted. + if (FastIS) + FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt)); + + FuncInfo->setCurrentSwiftErrorVReg(FuncInfo->MBB, SwiftErrorVal, VReg); + } +} + +/// Collect llvm.dbg.declare information. This is done after argument lowering +/// in case the declarations refer to arguments. +static void processDbgDeclares(FunctionLoweringInfo *FuncInfo) { + MachineFunction *MF = FuncInfo->MF; + const DataLayout &DL = MF->getDataLayout(); + for (const BasicBlock &BB : *FuncInfo->Fn) { + for (const Instruction &I : BB) { + const DbgDeclareInst *DI = dyn_cast<DbgDeclareInst>(&I); + if (!DI) + continue; + + assert(DI->getVariable() && "Missing variable"); + assert(DI->getDebugLoc() && "Missing location"); + const Value *Address = DI->getAddress(); + if (!Address) + continue; + + // Look through casts and constant offset GEPs. These mostly come from + // inalloca. + APInt Offset(DL.getPointerSizeInBits(0), 0); + Address = Address->stripAndAccumulateInBoundsConstantOffsets(DL, Offset); + + // Check if the variable is a static alloca or a byval or inalloca + // argument passed in memory. If it is not, then we will ignore this + // intrinsic and handle this during isel like dbg.value. + int FI = std::numeric_limits<int>::max(); + if (const auto *AI = dyn_cast<AllocaInst>(Address)) { + auto SI = FuncInfo->StaticAllocaMap.find(AI); + if (SI != FuncInfo->StaticAllocaMap.end()) + FI = SI->second; + } else if (const auto *Arg = dyn_cast<Argument>(Address)) + FI = FuncInfo->getArgumentFrameIndex(Arg); + + if (FI == std::numeric_limits<int>::max()) continue; - unsigned VReg = FuncInfo->MF->getRegInfo().createVirtualRegister(RC); - // Assign Undef to Vreg. We construct MI directly to make sure it works - // with FastISel. - BuildMI(*FuncInfo->MBB, FuncInfo->MBB->getFirstNonPHI(), - SDB->getCurDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF), - VReg); - FuncInfo->setCurrentSwiftErrorVReg(FuncInfo->MBB, SwiftErrorVal, VReg); + + DIExpression *Expr = DI->getExpression(); + if (Offset.getBoolValue()) + Expr = DIExpression::prepend(Expr, DIExpression::NoDeref, + Offset.getZExtValue()); + MF->setVariableDbgInfo(DI->getVariable(), Expr, FI, DI->getDebugLoc()); } } } @@ -1339,7 +1282,82 @@ static void propagateSwiftErrorVRegs(FunctionLoweringInfo *FuncInfo) { } } +void preassignSwiftErrorRegs(const TargetLowering *TLI, + FunctionLoweringInfo *FuncInfo, + BasicBlock::const_iterator Begin, + BasicBlock::const_iterator End) { + if (!TLI->supportSwiftError() || FuncInfo->SwiftErrorVals.empty()) + return; + + // Iterator over instructions and assign vregs to swifterror defs and uses. + for (auto It = Begin; It != End; ++It) { + ImmutableCallSite CS(&*It); + if (CS) { + // A call-site with a swifterror argument is both use and def. + const Value *SwiftErrorAddr = nullptr; + for (auto &Arg : CS.args()) { + if (!Arg->isSwiftError()) + continue; + // Use of swifterror. + assert(!SwiftErrorAddr && "Cannot have multiple swifterror arguments"); + SwiftErrorAddr = &*Arg; + assert(SwiftErrorAddr->isSwiftError() && + "Must have a swifterror value argument"); + unsigned VReg; bool CreatedReg; + std::tie(VReg, CreatedReg) = FuncInfo->getOrCreateSwiftErrorVRegUseAt( + &*It, FuncInfo->MBB, SwiftErrorAddr); + assert(CreatedReg); + } + if (!SwiftErrorAddr) + continue; + + // Def of swifterror. + unsigned VReg; bool CreatedReg; + std::tie(VReg, CreatedReg) = + FuncInfo->getOrCreateSwiftErrorVRegDefAt(&*It); + assert(CreatedReg); + FuncInfo->setCurrentSwiftErrorVReg(FuncInfo->MBB, SwiftErrorAddr, VReg); + + // A load is a use. + } else if (const LoadInst *LI = dyn_cast<const LoadInst>(&*It)) { + const Value *V = LI->getOperand(0); + if (!V->isSwiftError()) + continue; + + unsigned VReg; bool CreatedReg; + std::tie(VReg, CreatedReg) = + FuncInfo->getOrCreateSwiftErrorVRegUseAt(LI, FuncInfo->MBB, V); + assert(CreatedReg); + + // A store is a def. + } else if (const StoreInst *SI = dyn_cast<const StoreInst>(&*It)) { + const Value *SwiftErrorAddr = SI->getOperand(1); + if (!SwiftErrorAddr->isSwiftError()) + continue; + + // Def of swifterror. + unsigned VReg; bool CreatedReg; + std::tie(VReg, CreatedReg) = + FuncInfo->getOrCreateSwiftErrorVRegDefAt(&*It); + assert(CreatedReg); + FuncInfo->setCurrentSwiftErrorVReg(FuncInfo->MBB, SwiftErrorAddr, VReg); + + // A return in a swiferror returning function is a use. + } else if (const ReturnInst *R = dyn_cast<const ReturnInst>(&*It)) { + const Function *F = R->getParent()->getParent(); + if(!F->getAttributes().hasAttrSomewhere(Attribute::SwiftError)) + continue; + + unsigned VReg; bool CreatedReg; + std::tie(VReg, CreatedReg) = FuncInfo->getOrCreateSwiftErrorVRegUseAt( + R, FuncInfo->MBB, FuncInfo->SwiftErrorArg); + assert(CreatedReg); + } + } +} + void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { + FastISelFailed = false; // Initialize the Fast-ISel state, if needed. FastISel *FastIS = nullptr; if (TM.Options.EnableFastISel) @@ -1347,12 +1365,55 @@ void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { setupSwiftErrorVals(Fn, TLI, FuncInfo); - // Iterate over all basic blocks in the function. ReversePostOrderTraversal<const Function*> RPOT(&Fn); - for (ReversePostOrderTraversal<const Function*>::rpo_iterator - I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { - const BasicBlock *LLVMBB = *I; + // Lower arguments up front. An RPO iteration always visits the entry block + // first. + assert(*RPOT.begin() == &Fn.getEntryBlock()); + ++NumEntryBlocks; + + // Set up FuncInfo for ISel. Entry blocks never have PHIs. + FuncInfo->MBB = FuncInfo->MBBMap[&Fn.getEntryBlock()]; + FuncInfo->InsertPt = FuncInfo->MBB->begin(); + + if (!FastIS) { + LowerArguments(Fn); + } else { + // See if fast isel can lower the arguments. + FastIS->startNewBlock(); + if (!FastIS->lowerArguments()) { + FastISelFailed = true; + // Fast isel failed to lower these arguments + ++NumFastIselFailLowerArguments; + + OptimizationRemarkMissed R("sdagisel", "FastISelFailure", + Fn.getSubprogram(), + &Fn.getEntryBlock()); + R << "FastISel didn't lower all arguments: " + << ore::NV("Prototype", Fn.getType()); + reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 1); + + // Use SelectionDAG argument lowering + LowerArguments(Fn); + CurDAG->setRoot(SDB->getControlRoot()); + SDB->clear(); + CodeGenAndEmitDAG(); + } + + // If we inserted any instructions at the beginning, make a note of + // where they are, so we can be sure to emit subsequent instructions + // after them. + if (FuncInfo->InsertPt != FuncInfo->MBB->begin()) + FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt)); + else + FastIS->setLastLocalValue(nullptr); + } + createSwiftErrorEntriesInEntryBlock(FuncInfo, FastIS, TLI, TII, SDB); + + processDbgDeclares(FuncInfo); + + // Iterate over all basic blocks in the function. + for (const BasicBlock *LLVMBB : RPOT) { if (OptLevel != CodeGenOpt::None) { bool AllPredsVisited = true; for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB); @@ -1384,8 +1445,9 @@ void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB]; if (!FuncInfo->MBB) continue; // Some blocks like catchpads have no code or MBB. - FuncInfo->InsertPt = FuncInfo->MBB->getFirstNonPHI(); - createSwiftErrorEntriesInEntryBlock(FuncInfo, TLI, TII, LLVMBB, SDB); + + // Insert new instructions after any phi or argument setup code. + FuncInfo->InsertPt = FuncInfo->MBB->end(); // Setup an EH landing-pad block. FuncInfo->ExceptionPointerVirtReg = 0; @@ -1396,43 +1458,21 @@ void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { // Before doing SelectionDAG ISel, see if FastISel has been requested. if (FastIS) { - FastIS->startNewBlock(); - - // Emit code for any incoming arguments. This must happen before - // beginning FastISel on the entry block. - if (LLVMBB == &Fn.getEntryBlock()) { - ++NumEntryBlocks; - - // Lower any arguments needed in this block if this is the entry block. - if (!FastIS->lowerArguments()) { - // Fast isel failed to lower these arguments - ++NumFastIselFailLowerArguments; - if (EnableFastISelAbort > 1) - report_fatal_error("FastISel didn't lower all arguments"); - - // Use SelectionDAG argument lowering - LowerArguments(Fn); - CurDAG->setRoot(SDB->getControlRoot()); - SDB->clear(); - CodeGenAndEmitDAG(); - } - - // If we inserted any instructions at the beginning, make a note of - // where they are, so we can be sure to emit subsequent instructions - // after them. - if (FuncInfo->InsertPt != FuncInfo->MBB->begin()) - FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt)); - else - FastIS->setLastLocalValue(nullptr); - } + if (LLVMBB != &Fn.getEntryBlock()) + FastIS->startNewBlock(); unsigned NumFastIselRemaining = std::distance(Begin, End); + + // Pre-assign swifterror vregs. + preassignSwiftErrorRegs(TLI, FuncInfo, Begin, End); + // Do FastISel on as many instructions as possible. for (; BI != Begin; --BI) { const Instruction *Inst = &*std::prev(BI); // If we no longer require this instruction, skip it. - if (isFoldedOrDeadInstruction(Inst, FuncInfo)) { + if (isFoldedOrDeadInstruction(Inst, FuncInfo) || + ElidedArgCopyInstrs.count(Inst)) { --NumFastIselRemaining; continue; } @@ -1465,22 +1505,28 @@ void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { continue; } -#ifndef NDEBUG - if (EnableFastISelVerbose2) - collectFailStats(Inst); -#endif + FastISelFailed = true; // Then handle certain instructions as single-LLVM-Instruction blocks. - if (isa<CallInst>(Inst)) { - - if (EnableFastISelVerbose || EnableFastISelAbort) { - dbgs() << "FastISel missed call: "; - Inst->dump(); + // We cannot separate out GCrelocates to their own blocks since we need + // to keep track of gc-relocates for a particular gc-statepoint. This is + // done by SelectionDAGBuilder::LowerAsSTATEPOINT, called before + // visitGCRelocate. + if (isa<CallInst>(Inst) && !isStatepoint(Inst) && !isGCRelocate(Inst)) { + OptimizationRemarkMissed R("sdagisel", "FastISelFailure", + Inst->getDebugLoc(), LLVMBB); + + R << "FastISel missed call"; + + if (R.isEnabled() || EnableFastISelAbort) { + std::string InstStrStorage; + raw_string_ostream InstStr(InstStrStorage); + InstStr << *Inst; + + R << ": " << InstStr.str(); } - if (EnableFastISelAbort > 2) - // FastISel selector couldn't handle something and bailed. - // For the purpose of debugging, just abort. - report_fatal_error("FastISel didn't select the entire block"); + + reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 2); if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy() && !Inst->use_empty()) { @@ -1509,35 +1555,35 @@ void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { continue; } + OptimizationRemarkMissed R("sdagisel", "FastISelFailure", + Inst->getDebugLoc(), LLVMBB); + bool ShouldAbort = EnableFastISelAbort; - if (EnableFastISelVerbose || EnableFastISelAbort) { - if (isa<TerminatorInst>(Inst)) { - // Use a different message for terminator misses. - dbgs() << "FastISel missed terminator: "; - // Don't abort unless for terminator unless the level is really high - ShouldAbort = (EnableFastISelAbort > 2); - } else { - dbgs() << "FastISel miss: "; - } - Inst->dump(); + if (isa<TerminatorInst>(Inst)) { + // Use a different message for terminator misses. + R << "FastISel missed terminator"; + // Don't abort for terminator unless the level is really high + ShouldAbort = (EnableFastISelAbort > 2); + } else { + R << "FastISel missed"; } - if (ShouldAbort) - // FastISel selector couldn't handle something and bailed. - // For the purpose of debugging, just abort. - report_fatal_error("FastISel didn't select the entire block"); + + if (R.isEnabled() || EnableFastISelAbort) { + std::string InstStrStorage; + raw_string_ostream InstStr(InstStrStorage); + InstStr << *Inst; + R << ": " << InstStr.str(); + } + + reportFastISelFailure(*MF, *ORE, R, ShouldAbort); NumFastIselFailures += NumFastIselRemaining; break; } FastIS->recomputeInsertPt(); - } else { - // Lower any arguments needed in this block if this is the entry block. - if (LLVMBB == &Fn.getEntryBlock()) { - ++NumEntryBlocks; - LowerArguments(Fn); - } } + if (getAnalysis<StackProtector>().shouldEmitSDCheck(*LLVMBB)) { bool FunctionBasedInstrumentation = TLI->getSSPStackGuardCheck(*Fn.getParent()); @@ -1556,10 +1602,17 @@ void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { // block. bool HadTailCall; SelectBasicBlock(Begin, BI, HadTailCall); + + // But if FastISel was run, we already selected some of the block. + // If we emitted a tail-call, we need to delete any previously emitted + // instruction that follows it. + if (HadTailCall && FuncInfo->InsertPt != FuncInfo->MBB->end()) + FastIS->removeDeadCode(FuncInfo->InsertPt, FuncInfo->MBB->end()); } FinishBasicBlock(); FuncInfo->PHINodesToUpdate.clear(); + ElidedArgCopyInstrs.clear(); } propagateSwiftErrorVRegs(FuncInfo); @@ -1975,11 +2028,11 @@ bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS, // either already zero or is not demanded. Check for known zero input bits. APInt NeededMask = DesiredMask & ~ActualMask; - APInt KnownZero, KnownOne; - CurDAG->computeKnownBits(LHS, KnownZero, KnownOne); + KnownBits Known; + CurDAG->computeKnownBits(LHS, Known); // If all the missing bits in the or are already known to be set, match! - if ((NeededMask & KnownOne) == NeededMask) + if (NeededMask.isSubsetOf(Known.One)) return true; // TODO: check to see if missing bits are just not demanded. @@ -2062,7 +2115,7 @@ static SDNode *findGlueUse(SDNode *N) { } /// findNonImmUse - Return true if "Use" is a non-immediate use of "Def". -/// This function recursively traverses up the operand chain, ignoring +/// This function iteratively traverses up the operand chain, ignoring /// certain nodes. static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse, SDNode *Root, SmallPtrSetImpl<SDNode*> &Visited, @@ -2075,30 +2128,36 @@ static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse, // The Use may be -1 (unassigned) if it is a newly allocated node. This can // happen because we scan down to newly selected nodes in the case of glue // uses. - if ((Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1)) - return false; + std::vector<SDNode *> WorkList; + WorkList.push_back(Use); - // Don't revisit nodes if we already scanned it and didn't fail, we know we - // won't fail if we scan it again. - if (!Visited.insert(Use).second) - return false; + while (!WorkList.empty()) { + Use = WorkList.back(); + WorkList.pop_back(); + if (Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1) + continue; - for (const SDValue &Op : Use->op_values()) { - // Ignore chain uses, they are validated by HandleMergeInputChains. - if (Op.getValueType() == MVT::Other && IgnoreChains) + // Don't revisit nodes if we already scanned it and didn't fail, we know we + // won't fail if we scan it again. + if (!Visited.insert(Use).second) continue; - SDNode *N = Op.getNode(); - if (N == Def) { - if (Use == ImmedUse || Use == Root) - continue; // We are not looking for immediate use. - assert(N != Root); - return true; - } + for (const SDValue &Op : Use->op_values()) { + // Ignore chain uses, they are validated by HandleMergeInputChains. + if (Op.getValueType() == MVT::Other && IgnoreChains) + continue; - // Traverse up the operand chain. - if (findNonImmUse(N, Def, ImmedUse, Root, Visited, IgnoreChains)) - return true; + SDNode *N = Op.getNode(); + if (N == Def) { + if (Use == ImmedUse || Use == Root) + continue; // We are not looking for immediate use. + assert(N != Root); + return true; + } + + // Traverse up the operand chain. + WorkList.push_back(N); + } } return false; } @@ -2177,7 +2236,6 @@ bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, IgnoreChains = false; } - SmallPtrSet<SDNode*, 16> Visited; return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains); } @@ -2554,7 +2612,7 @@ MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList, LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, - const SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) { + const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) { // Accept if it is exactly the same as a previously recorded node. unsigned RecNo = MatcherTable[MatcherIndex++]; assert(RecNo < RecordedNodes.size() && "Invalid CheckSame"); @@ -2564,9 +2622,9 @@ CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, /// CheckChildSame - Implements OP_CheckChildXSame. LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool CheckChildSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, - SDValue N, - const SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes, - unsigned ChildNo) { + SDValue N, + const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes, + unsigned ChildNo) { if (ChildNo >= N.getNumOperands()) return false; // Match fails if out of range child #. return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo), @@ -2688,7 +2746,7 @@ static unsigned IsPredicateKnownToFail(const unsigned char *Table, unsigned Index, SDValue N, bool &Result, const SelectionDAGISel &SDISel, - SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) { + SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) { switch (Table[Index++]) { default: Result = false; @@ -2756,6 +2814,7 @@ static unsigned IsPredicateKnownToFail(const unsigned char *Table, } namespace { + struct MatchScope { /// FailIndex - If this match fails, this is the index to continue with. unsigned FailIndex; @@ -2785,6 +2844,7 @@ class MatchStateUpdater : public SelectionDAG::DAGUpdateListener SDNode **NodeToMatch; SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes; SmallVectorImpl<MatchScope> &MatchScopes; + public: MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch, SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN, @@ -2816,6 +2876,7 @@ public: J.setNode(E); } }; + } // end anonymous namespace void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, @@ -2921,7 +2982,7 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, // with an OPC_SwitchOpcode instruction. Populate the table now, since this // is the first time we're selecting an instruction. unsigned Idx = 1; - while (1) { + while (true) { // Get the size of this case. unsigned CaseSize = MatcherTable[Idx++]; if (CaseSize & 128) @@ -2942,7 +3003,7 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, MatcherIndex = OpcodeOffset[N.getOpcode()]; } - while (1) { + while (true) { assert(MatcherIndex < TableSize && "Invalid index"); #ifndef NDEBUG unsigned CurrentOpcodeIndex = MatcherIndex; @@ -2957,7 +3018,7 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, // immediately fail, don't even bother pushing a scope for them. unsigned FailIndex; - while (1) { + while (true) { unsigned NumToSkip = MatcherTable[MatcherIndex++]; if (NumToSkip & 128) NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex); @@ -3118,7 +3179,7 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, unsigned CurNodeOpcode = N.getOpcode(); unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart; unsigned CaseSize; - while (1) { + while (true) { // Get the size of this case. CaseSize = MatcherTable[MatcherIndex++]; if (CaseSize & 128) @@ -3149,7 +3210,7 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, MVT CurNodeVT = N.getSimpleValueType(); unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart; unsigned CaseSize; - while (1) { + while (true) { // Get the size of this case. CaseSize = MatcherTable[MatcherIndex++]; if (CaseSize & 128) @@ -3215,7 +3276,7 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, // a single use. bool HasMultipleUses = false; for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i) - if (!NodeStack[i].hasOneUse()) { + if (!NodeStack[i].getNode()->hasOneUse()) { HasMultipleUses = true; break; } @@ -3381,6 +3442,15 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr)); continue; } + case OPC_Coverage: { + // This is emitted right before MorphNode/EmitNode. + // So it should be safe to assume that this node has been selected + unsigned index = MatcherTable[MatcherIndex++]; + index |= (MatcherTable[MatcherIndex++] << 8); + dbgs() << "COVERED: " << getPatternForIndex(index) << "\n"; + dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n"; + continue; + } case OPC_EmitNode: case OPC_MorphNodeTo: case OPC_EmitNode0: case OPC_EmitNode1: case OPC_EmitNode2: @@ -3473,7 +3543,6 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i), nullptr)); } - } else { assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE && "NodeToMatch was removed partway through selection"); @@ -3610,7 +3679,7 @@ void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, // find a case to check. DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex << "\n"); ++NumDAGIselRetries; - while (1) { + while (true) { if (MatchScopes.empty()) { CannotYetSelect(NodeToMatch); return; |
