diff options
Diffstat (limited to 'lib/CodeGen')
22 files changed, 614 insertions, 282 deletions
diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp index faf4d95..d94729a 100644 --- a/lib/CodeGen/BranchFolding.cpp +++ b/lib/CodeGen/BranchFolding.cpp @@ -334,7 +334,9 @@ static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, unsigned TailLen = 0; while (I1 != MBB1->begin() && I2 != MBB2->begin()) { --I1; --I2; - if (!I1->isIdenticalTo(I2) || + // Don't merge debugging pseudos. + if (I1->isDebugValue() || I2->isDebugValue() || + !I1->isIdenticalTo(I2) || // FIXME: This check is dubious. It's used to get around a problem where // people incorrectly expect inline asm directives to remain in the same // relative order. This is untenable because normal compiler @@ -412,6 +414,8 @@ static unsigned EstimateRuntime(MachineBasicBlock::iterator I, MachineBasicBlock::iterator E) { unsigned Time = 0; for (; I != E; ++I) { + if (I->isDebugValue()) + continue; const TargetInstrDesc &TID = I->getDesc(); if (TID.isCall()) Time += 10; diff --git a/lib/CodeGen/CriticalAntiDepBreaker.cpp b/lib/CodeGen/CriticalAntiDepBreaker.cpp index 056e2d5..7d3de89 100644 --- a/lib/CodeGen/CriticalAntiDepBreaker.cpp +++ b/lib/CodeGen/CriticalAntiDepBreaker.cpp @@ -119,6 +119,8 @@ void CriticalAntiDepBreaker::FinishBlock() { void CriticalAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex) { + if (MI->isDebugValue()) + return; assert(Count < InsertPosIndex && "Instruction index out of expected range!"); // Any register which was defined within the previous scheduling region @@ -409,6 +411,8 @@ BreakAntiDependencies(std::vector<SUnit>& SUnits, for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) { MachineInstr *MI = --I; + if (MI->isDebugValue()) + continue; // Check if this instruction has a dependence on the critical path that // is an anti-dependence that we may be able to break. If it is, set diff --git a/lib/CodeGen/LLVMTargetMachine.cpp b/lib/CodeGen/LLVMTargetMachine.cpp index fd442db..5e88865 100644 --- a/lib/CodeGen/LLVMTargetMachine.cpp +++ b/lib/CodeGen/LLVMTargetMachine.cpp @@ -67,7 +67,7 @@ static cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden, cl::desc("Verify generated machine code"), cl::init(getenv("LLVM_VERIFY_MACHINEINSTRS")!=NULL)); -static cl::opt<bool> EnableMachineCSE("machine-cse", cl::Hidden, +static cl::opt<bool> EnableMachineCSE("enable-machine-cse", cl::Hidden, cl::desc("Enable Machine CSE")); static cl::opt<cl::boolOrDefault> @@ -212,6 +212,12 @@ bool LLVMTargetMachine::addPassesToEmitMachineCode(PassManagerBase &PM, return false; // success! } +static void printNoVerify(PassManagerBase &PM, + const char *Banner) { + if (PrintMachineCode) + PM.add(createMachineFunctionPrinterPass(dbgs(), Banner)); +} + static void printAndVerify(PassManagerBase &PM, const char *Banner, bool allowDoubleDefs = false) { @@ -320,10 +326,10 @@ bool LLVMTargetMachine::addCommonCodeGenPasses(PassManagerBase &PM, if (OptLevel != CodeGenOpt::None) { PM.add(createOptimizeExtsPass()); - if (EnableMachineCSE) - PM.add(createMachineCSEPass()); if (!DisableMachineLICM) PM.add(createMachineLICMPass()); + if (EnableMachineCSE) + PM.add(createMachineCSEPass()); if (!DisableMachineSink) PM.add(createMachineSinkingPass()); printAndVerify(PM, "After MachineLICM and MachineSinking", @@ -378,13 +384,13 @@ bool LLVMTargetMachine::addCommonCodeGenPasses(PassManagerBase &PM, // Branch folding must be run after regalloc and prolog/epilog insertion. if (OptLevel != CodeGenOpt::None && !DisableBranchFold) { PM.add(createBranchFoldingPass(getEnableTailMergeDefault())); - printAndVerify(PM, "After BranchFolding"); + printNoVerify(PM, "After BranchFolding"); } // Tail duplication. if (OptLevel != CodeGenOpt::None && !DisableTailDuplicate) { PM.add(createTailDuplicatePass(false)); - printAndVerify(PM, "After TailDuplicate"); + printNoVerify(PM, "After TailDuplicate"); } PM.add(createGCMachineCodeAnalysisPass()); @@ -394,11 +400,11 @@ bool LLVMTargetMachine::addCommonCodeGenPasses(PassManagerBase &PM, if (OptLevel != CodeGenOpt::None && !DisableCodePlace) { PM.add(createCodePlacementOptPass()); - printAndVerify(PM, "After CodePlacementOpt"); + printNoVerify(PM, "After CodePlacementOpt"); } if (addPreEmitPass(PM, OptLevel)) - printAndVerify(PM, "After PreEmit passes"); + printNoVerify(PM, "After PreEmit passes"); return false; } diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 68c8539..519990e 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -365,27 +365,7 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { } } - if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) { - if (LastPartDef) - // The last partial def kills the register. - LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, - true/*IsImp*/, true/*IsKill*/)); - else { - MachineOperand *MO = - LastRefOrPartRef->findRegisterDefOperand(Reg, false, TRI); - bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg; - // If the last reference is the last def, then it's not used at all. - // That is, unless we are currently processing the last reference itself. - LastRefOrPartRef->addRegisterDead(Reg, TRI, true); - if (NeedEC) { - // If we are adding a subreg def and the superreg def is marked early - // clobber, add an early clobber marker to the subreg def. - MO = LastRefOrPartRef->findRegisterDefOperand(Reg); - if (MO) - MO->setIsEarlyClobber(); - } - } - } else if (!PhysRegUse[Reg]) { + if (!PhysRegUse[Reg]) { // Partial uses. Mark register def dead and add implicit def of // sub-registers which are used. // EAX<dead> = op AL<imp-def> @@ -419,6 +399,26 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) PartUses.erase(*SS); } + } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) { + if (LastPartDef) + // The last partial def kills the register. + LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, + true/*IsImp*/, true/*IsKill*/)); + else { + MachineOperand *MO = + LastRefOrPartRef->findRegisterDefOperand(Reg, false, TRI); + bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg; + // If the last reference is the last def, then it's not used at all. + // That is, unless we are currently processing the last reference itself. + LastRefOrPartRef->addRegisterDead(Reg, TRI, true); + if (NeedEC) { + // If we are adding a subreg def and the superreg def is marked early + // clobber, add an early clobber marker to the subreg def. + MO = LastRefOrPartRef->findRegisterDefOperand(Reg); + if (MO) + MO->setIsEarlyClobber(); + } + } } else LastRefOrPartRef->addRegisterKilled(Reg, TRI, true); return true; diff --git a/lib/CodeGen/MachineCSE.cpp b/lib/CodeGen/MachineCSE.cpp index 023ace2..b376e3d 100644 --- a/lib/CodeGen/MachineCSE.cpp +++ b/lib/CodeGen/MachineCSE.cpp @@ -18,6 +18,7 @@ #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/ADT/ScopedHashTable.h" #include "llvm/ADT/Statistic.h" @@ -25,76 +26,16 @@ using namespace llvm; -namespace llvm { - template<> struct DenseMapInfo<MachineInstr*> { - static inline MachineInstr *getEmptyKey() { - return 0; - } - - static inline MachineInstr *getTombstoneKey() { - return reinterpret_cast<MachineInstr*>(-1); - } - - static unsigned getHashValue(const MachineInstr* const &MI) { - unsigned Hash = MI->getOpcode() * 37; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - uint64_t Key = (uint64_t)MO.getType() << 32; - switch (MO.getType()) { - default: break; - case MachineOperand::MO_Register: - if (MO.isDef() && TargetRegisterInfo::isVirtualRegister(MO.getReg())) - continue; // Skip virtual register defs. - Key |= MO.getReg(); - break; - case MachineOperand::MO_Immediate: - Key |= MO.getImm(); - break; - case MachineOperand::MO_FrameIndex: - case MachineOperand::MO_ConstantPoolIndex: - case MachineOperand::MO_JumpTableIndex: - Key |= MO.getIndex(); - break; - case MachineOperand::MO_MachineBasicBlock: - Key |= DenseMapInfo<void*>::getHashValue(MO.getMBB()); - break; - case MachineOperand::MO_GlobalAddress: - Key |= DenseMapInfo<void*>::getHashValue(MO.getGlobal()); - break; - case MachineOperand::MO_BlockAddress: - Key |= DenseMapInfo<void*>::getHashValue(MO.getBlockAddress()); - break; - } - Key += ~(Key << 32); - Key ^= (Key >> 22); - Key += ~(Key << 13); - Key ^= (Key >> 8); - Key += (Key << 3); - Key ^= (Key >> 15); - Key += ~(Key << 27); - Key ^= (Key >> 31); - Hash = (unsigned)Key + Hash * 37; - } - return Hash; - } - - static bool isEqual(const MachineInstr* const &LHS, - const MachineInstr* const &RHS) { - if (RHS == getEmptyKey() || RHS == getTombstoneKey() || - LHS == getEmptyKey() || LHS == getTombstoneKey()) - return LHS == RHS; - return LHS->isIdenticalTo(RHS, MachineInstr::IgnoreVRegDefs); - } - }; -} // end llvm namespace +STATISTIC(NumCoalesces, "Number of copies coalesced"); +STATISTIC(NumCSEs, "Number of common subexpression eliminated"); namespace { class MachineCSE : public MachineFunctionPass { const TargetInstrInfo *TII; + const TargetRegisterInfo *TRI; MachineRegisterInfo *MRI; MachineDominatorTree *DT; - ScopedHashTable<MachineInstr*, unsigned> VNT; - unsigned CurrVN; + AliasAnalysis *AA; public: static char ID; // Pass identification MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {} @@ -104,12 +45,22 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); MachineFunctionPass::getAnalysisUsage(AU); + AU.addRequired<AliasAnalysis>(); AU.addRequired<MachineDominatorTree>(); AU.addPreserved<MachineDominatorTree>(); } private: + unsigned CurrVN; + ScopedHashTable<MachineInstr*, unsigned, MachineInstrExpressionTrait> VNT; + SmallVector<MachineInstr*, 64> Exps; + bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); + bool isPhysDefTriviallyDead(unsigned Reg, + MachineBasicBlock::const_iterator I, + MachineBasicBlock::const_iterator E); + bool hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB); + bool isCSECandidate(MachineInstr *MI); bool ProcessBlock(MachineDomTreeNode *Node); }; } // end anonymous namespace @@ -125,27 +76,65 @@ bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, bool Changed = false; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isUse()) { - unsigned Reg = MO.getReg(); - if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) - continue; - MachineInstr *DefMI = MRI->getVRegDef(Reg); - if (DefMI->getParent() == MBB) { - unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; - if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && - TargetRegisterInfo::isVirtualRegister(SrcReg) && - !SrcSubIdx && !DstSubIdx) { - MO.setReg(SrcReg); - Changed = true; - } - } + if (!MO.isReg() || !MO.isUse()) + continue; + unsigned Reg = MO.getReg(); + if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) + continue; + if (!MRI->hasOneUse(Reg)) + // Only coalesce single use copies. This ensure the copy will be + // deleted. + continue; + MachineInstr *DefMI = MRI->getVRegDef(Reg); + if (DefMI->getParent() != MBB) + continue; + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && + TargetRegisterInfo::isVirtualRegister(SrcReg) && + !SrcSubIdx && !DstSubIdx) { + MO.setReg(SrcReg); + DefMI->eraseFromParent(); + ++NumCoalesces; + Changed = true; } } return Changed; } -static bool hasLivePhysRegDefUse(MachineInstr *MI) { +bool MachineCSE::isPhysDefTriviallyDead(unsigned Reg, + MachineBasicBlock::const_iterator I, + MachineBasicBlock::const_iterator E) { + unsigned LookAheadLeft = 5; + while (LookAheadLeft--) { + if (I == E) + // Reached end of block, register is obviously dead. + return true; + + if (I->isDebugValue()) + continue; + bool SeenDef = false; + for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = I->getOperand(i); + if (!MO.isReg() || !MO.getReg()) + continue; + if (!TRI->regsOverlap(MO.getReg(), Reg)) + continue; + if (MO.isUse()) + return false; + SeenDef = true; + } + if (SeenDef) + // See a def of Reg (or an alias) before encountering any use, it's + // trivially dead. + return true; + ++I; + } + return false; +} + +bool MachineCSE::hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB){ + unsigned PhysDef = 0; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); if (!MO.isReg()) @@ -153,30 +142,69 @@ static bool hasLivePhysRegDefUse(MachineInstr *MI) { unsigned Reg = MO.getReg(); if (!Reg) continue; - if (TargetRegisterInfo::isPhysicalRegister(Reg) && - !(MO.isDef() && MO.isDead())) + if (TargetRegisterInfo::isPhysicalRegister(Reg)) { + if (MO.isUse()) + // Can't touch anything to read a physical register. + return true; + if (MO.isDead()) + // If the def is dead, it's ok. + continue; + // Ok, this is a physical register def that's not marked "dead". That's + // common since this pass is run before livevariables. We can scan + // forward a few instructions and check if it is obviously dead. + if (PhysDef) + // Multiple physical register defs. These are rare, forget about it. + return true; + PhysDef = Reg; + } + } + + if (PhysDef) { + MachineBasicBlock::iterator I = MI; I = llvm::next(I); + if (!isPhysDefTriviallyDead(PhysDef, I, MBB->end())) return true; } return false; } +bool MachineCSE::isCSECandidate(MachineInstr *MI) { + // Ignore copies or instructions that read / write physical registers + // (except for dead defs of physical registers). + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) || + MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg()) + return false; + + // Ignore stuff that we obviously can't move. + const TargetInstrDesc &TID = MI->getDesc(); + if (TID.mayStore() || TID.isCall() || TID.isTerminator() || + TID.hasUnmodeledSideEffects()) + return false; + + if (TID.mayLoad()) { + // Okay, this instruction does a load. As a refinement, we allow the target + // to decide whether the loaded value is actually a constant. If so, we can + // actually use it as a load. + if (!MI->isInvariantLoad(AA)) + // FIXME: we should be able to hoist loads with no other side effects if + // there are no other instructions which can change memory in this loop. + // This is a trivial form of alias analysis. + return false; + } + return true; +} + bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { bool Changed = false; - ScopedHashTableScope<MachineInstr*, unsigned> VNTS(VNT); + ScopedHashTableScope<MachineInstr*, unsigned, + MachineInstrExpressionTrait> VNTS(VNT); MachineBasicBlock *MBB = Node->getBlock(); - for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; - ++I) { + for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { MachineInstr *MI = &*I; - bool SawStore = false; - if (!MI->isSafeToMove(TII, 0, SawStore)) - continue; - // Ignore copies or instructions that read / write physical registers - // (except for dead defs of physical registers). - unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; - if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) - continue; - if (hasLivePhysRegDefUse(MI)) + ++I; + + if (!isCSECandidate(MI)) continue; bool FoundCSE = VNT.count(MI); @@ -185,11 +213,41 @@ bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { if (PerformTrivialCoalescing(MI, MBB)) FoundCSE = VNT.count(MI); } + // FIXME: commute commutable instructions? + + // If the instruction defines a physical register and the value *may* be + // used, then it's not safe to replace it with a common subexpression. + if (FoundCSE && hasLivePhysRegDefUse(MI, MBB)) + FoundCSE = false; + + if (!FoundCSE) { + VNT.insert(MI, CurrVN++); + Exps.push_back(MI); + continue; + } - if (FoundCSE) - DEBUG(dbgs() << "Found a common subexpression: " << *MI); - else - VNT.insert(MI, ++CurrVN); + // Found a common subexpression, eliminate it. + unsigned CSVN = VNT.lookup(MI); + MachineInstr *CSMI = Exps[CSVN]; + DEBUG(dbgs() << "Examining: " << *MI); + DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); + unsigned NumDefs = MI->getDesc().getNumDefs(); + for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.isDef()) + continue; + unsigned OldReg = MO.getReg(); + unsigned NewReg = CSMI->getOperand(i).getReg(); + if (OldReg == NewReg) + continue; + assert(TargetRegisterInfo::isVirtualRegister(OldReg) && + TargetRegisterInfo::isVirtualRegister(NewReg) && + "Do not CSE physical register defs!"); + MRI->replaceRegWith(OldReg, NewReg); + --NumDefs; + } + MI->eraseFromParent(); + ++NumCSEs; } // Recursively call ProcessBlock with childred. @@ -202,7 +260,9 @@ bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { TII = MF.getTarget().getInstrInfo(); + TRI = MF.getTarget().getRegisterInfo(); MRI = &MF.getRegInfo(); DT = &getAnalysis<MachineDominatorTree>(); + AA = &getAnalysis<AliasAnalysis>(); return ProcessBlock(DT->getRootNode()); } diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp index cba93f1..e23670d 100644 --- a/lib/CodeGen/MachineInstr.cpp +++ b/lib/CodeGen/MachineInstr.cpp @@ -704,24 +704,31 @@ void MachineInstr::addMemOperand(MachineFunction &MF, bool MachineInstr::isIdenticalTo(const MachineInstr *Other, MICheckType Check) const { - if (Other->getOpcode() != getOpcode() || - Other->getNumOperands() != getNumOperands()) + // If opcodes or number of operands are not the same then the two + // instructions are obviously not identical. + if (Other->getOpcode() != getOpcode() || + Other->getNumOperands() != getNumOperands()) + return false; + + // Check operands to make sure they match. + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + const MachineOperand &MO = getOperand(i); + const MachineOperand &OMO = Other->getOperand(i); + // Clients may or may not want to ignore defs when testing for equality. + // For example, machine CSE pass only cares about finding common + // subexpressions, so it's safe to ignore virtual register defs. + if (Check != CheckDefs && MO.isReg() && MO.isDef()) { + if (Check == IgnoreDefs) + continue; + // Check == IgnoreVRegDefs + if (TargetRegisterInfo::isPhysicalRegister(MO.getReg()) || + TargetRegisterInfo::isPhysicalRegister(OMO.getReg())) + if (MO.getReg() != OMO.getReg()) + return false; + } else if (!MO.isIdenticalTo(OMO)) return false; - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { - const MachineOperand &MO = getOperand(i); - const MachineOperand &OMO = Other->getOperand(i); - if (Check != CheckDefs && MO.isReg() && MO.isDef()) { - if (Check == IgnoreDefs) - continue; - // Check == IgnoreVRegDefs - if (TargetRegisterInfo::isPhysicalRegister(MO.getReg()) || - TargetRegisterInfo::isPhysicalRegister(OMO.getReg())) - if (MO.getReg() != OMO.getReg()) - return false; - } else if (!MO.isIdenticalTo(OMO)) - return false; - } - return true; + } + return true; } /// removeFromParent - This method unlinks 'this' from the containing basic @@ -1348,3 +1355,48 @@ void MachineInstr::addRegisterDefined(unsigned IncomingReg, true /*IsDef*/, true /*IsImp*/)); } + +unsigned +MachineInstrExpressionTrait::getHashValue(const MachineInstr* const &MI) { + unsigned Hash = MI->getOpcode() * 37; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + uint64_t Key = (uint64_t)MO.getType() << 32; + switch (MO.getType()) { + default: break; + case MachineOperand::MO_Register: + if (MO.isDef() && MO.getReg() && + TargetRegisterInfo::isVirtualRegister(MO.getReg())) + continue; // Skip virtual register defs. + Key |= MO.getReg(); + break; + case MachineOperand::MO_Immediate: + Key |= MO.getImm(); + break; + case MachineOperand::MO_FrameIndex: + case MachineOperand::MO_ConstantPoolIndex: + case MachineOperand::MO_JumpTableIndex: + Key |= MO.getIndex(); + break; + case MachineOperand::MO_MachineBasicBlock: + Key |= DenseMapInfo<void*>::getHashValue(MO.getMBB()); + break; + case MachineOperand::MO_GlobalAddress: + Key |= DenseMapInfo<void*>::getHashValue(MO.getGlobal()); + break; + case MachineOperand::MO_BlockAddress: + Key |= DenseMapInfo<void*>::getHashValue(MO.getBlockAddress()); + break; + } + Key += ~(Key << 32); + Key ^= (Key >> 22); + Key += ~(Key << 13); + Key ^= (Key >> 8); + Key += (Key << 3); + Key ^= (Key >> 15); + Key += ~(Key << 27); + Key ^= (Key >> 31); + Hash = (unsigned)Key + Hash * 37; + } + return Hash; +} diff --git a/lib/CodeGen/MachineRegisterInfo.cpp b/lib/CodeGen/MachineRegisterInfo.cpp index b31973e..d9ab677 100644 --- a/lib/CodeGen/MachineRegisterInfo.cpp +++ b/lib/CodeGen/MachineRegisterInfo.cpp @@ -116,6 +116,19 @@ MachineInstr *MachineRegisterInfo::getVRegDef(unsigned Reg) const { return 0; } +bool MachineRegisterInfo::hasOneUse(unsigned RegNo) const { + use_iterator UI = use_begin(RegNo); + if (UI == use_end()) + return false; + return ++UI == use_end(); +} + +bool MachineRegisterInfo::hasOneNonDBGUse(unsigned RegNo) const { + use_nodbg_iterator UI = use_nodbg_begin(RegNo); + if (UI == use_nodbg_end()) + return false; + return ++UI == use_nodbg_end(); +} #ifndef NDEBUG void MachineRegisterInfo::dumpUses(unsigned Reg) const { diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 9ba7d14..e47ba7c 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -72,8 +72,13 @@ bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB) const { assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Only makes sense for vregs"); - for (MachineRegisterInfo::use_iterator I = RegInfo->use_begin(Reg), - E = RegInfo->use_end(); I != E; ++I) { + // Ignoring debug uses is necessary so debug info doesn't affect the code. + // This may leave a referencing dbg_value in the original block, before + // the definition of the vreg. Dwarf generator handles this although the + // user might not get the right info at runtime. + for (MachineRegisterInfo::use_nodbg_iterator I = + RegInfo->use_nodbg_begin(Reg), + E = RegInfo->use_nodbg_end(); I != E; ++I) { // Determine the block of the use. MachineInstr *UseInst = &*I; MachineBasicBlock *UseBlock = UseInst->getParent(); @@ -135,7 +140,10 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { ProcessedBegin = I == MBB.begin(); if (!ProcessedBegin) --I; - + + if (MI->isDebugValue()) + continue; + if (SinkInstruction(MI, SawStore)) ++NumSunk, MadeChange = true; diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp index bdfd448..8bbe0a7 100644 --- a/lib/CodeGen/PHIElimination.cpp +++ b/lib/CodeGen/PHIElimination.cpp @@ -443,34 +443,3 @@ MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A, return NMBB; } - -unsigned -PHIElimination::PHINodeTraits::getHashValue(const MachineInstr *MI) { - if (!MI || MI==getEmptyKey() || MI==getTombstoneKey()) - return DenseMapInfo<MachineInstr*>::getHashValue(MI); - unsigned hash = 0; - for (unsigned ni = 1, ne = MI->getNumOperands(); ni != ne; ni += 2) - hash = hash*37 + DenseMapInfo<BBVRegPair>:: - getHashValue(BBVRegPair(MI->getOperand(ni+1).getMBB()->getNumber(), - MI->getOperand(ni).getReg())); - return hash; -} - -bool PHIElimination::PHINodeTraits::isEqual(const MachineInstr *LHS, - const MachineInstr *RHS) { - const MachineInstr *EmptyKey = getEmptyKey(); - const MachineInstr *TombstoneKey = getTombstoneKey(); - if (!LHS || !RHS || LHS==EmptyKey || RHS==EmptyKey || - LHS==TombstoneKey || RHS==TombstoneKey) - return LHS==RHS; - - unsigned ne = LHS->getNumOperands(); - if (ne != RHS->getNumOperands()) - return false; - // Ignore operand 0, the defined register. - for (unsigned ni = 1; ni != ne; ni += 2) - if (LHS->getOperand(ni).getReg() != RHS->getOperand(ni).getReg() || - LHS->getOperand(ni+1).getMBB() != RHS->getOperand(ni+1).getMBB()) - return false; - return true; -} diff --git a/lib/CodeGen/PHIElimination.h b/lib/CodeGen/PHIElimination.h index ff4aa20..7dedf03 100644 --- a/lib/CodeGen/PHIElimination.h +++ b/lib/CodeGen/PHIElimination.h @@ -102,15 +102,9 @@ namespace llvm { // Defs of PHI sources which are implicit_def. SmallPtrSet<MachineInstr*, 4> ImpDefs; - // Lowered PHI nodes may be reused. We provide special DenseMap traits to - // match PHI nodes with identical arguments. - struct PHINodeTraits : public DenseMapInfo<MachineInstr*> { - static unsigned getHashValue(const MachineInstr *PtrVal); - static bool isEqual(const MachineInstr *LHS, const MachineInstr *RHS); - }; - // Map reusable lowered PHI node -> incoming join register. - typedef DenseMap<MachineInstr*, unsigned, PHINodeTraits> LoweredPHIMap; + typedef DenseMap<MachineInstr*, unsigned, + MachineInstrExpressionTrait> LoweredPHIMap; LoweredPHIMap LoweredPHIs; }; diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp index f43395f..424181c 100644 --- a/lib/CodeGen/PostRASchedulerList.cpp +++ b/lib/CodeGen/PostRASchedulerList.cpp @@ -460,6 +460,8 @@ void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin(); I != E; --Count) { MachineInstr *MI = --I; + if (MI->isDebugValue()) + continue; // Update liveness. Registers that are defed but not used in this // instruction are now dead. Mark register and all subregs as they diff --git a/lib/CodeGen/PseudoSourceValue.cpp b/lib/CodeGen/PseudoSourceValue.cpp index 7fb3e6e..5e86e5a 100644 --- a/lib/CodeGen/PseudoSourceValue.cpp +++ b/lib/CodeGen/PseudoSourceValue.cpp @@ -18,19 +18,38 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/ManagedStatic.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/System/Mutex.h" #include <map> using namespace llvm; -static ManagedStatic<PseudoSourceValue[4]> PSVs; +namespace { +struct PSVGlobalsTy { + // PseudoSourceValues are immutable so don't need locking. + const PseudoSourceValue PSVs[4]; + sys::Mutex Lock; // Guards FSValues, but not the values inside it. + std::map<int, const PseudoSourceValue *> FSValues; + + PSVGlobalsTy() : PSVs() {} + ~PSVGlobalsTy() { + for (std::map<int, const PseudoSourceValue *>::iterator + I = FSValues.begin(), E = FSValues.end(); I != E; ++I) { + delete I->second; + } + } +}; + +static ManagedStatic<PSVGlobalsTy> PSVGlobals; + +} // anonymous namespace const PseudoSourceValue *PseudoSourceValue::getStack() -{ return &(*PSVs)[0]; } +{ return &PSVGlobals->PSVs[0]; } const PseudoSourceValue *PseudoSourceValue::getGOT() -{ return &(*PSVs)[1]; } +{ return &PSVGlobals->PSVs[1]; } const PseudoSourceValue *PseudoSourceValue::getJumpTable() -{ return &(*PSVs)[2]; } +{ return &PSVGlobals->PSVs[2]; } const PseudoSourceValue *PseudoSourceValue::getConstantPool() -{ return &(*PSVs)[3]; } +{ return &PSVGlobals->PSVs[3]; } static const char *const PSVNames[] = { "Stack", @@ -48,13 +67,13 @@ PseudoSourceValue::PseudoSourceValue(enum ValueTy Subclass) : Subclass) {} void PseudoSourceValue::printCustom(raw_ostream &O) const { - O << PSVNames[this - *PSVs]; + O << PSVNames[this - PSVGlobals->PSVs]; } -static ManagedStatic<std::map<int, const PseudoSourceValue *> > FSValues; - const PseudoSourceValue *PseudoSourceValue::getFixedStack(int FI) { - const PseudoSourceValue *&V = (*FSValues)[FI]; + PSVGlobalsTy &PG = *PSVGlobals; + sys::ScopedLock locked(PG.Lock); + const PseudoSourceValue *&V = PG.FSValues[FI]; if (!V) V = new FixedStackPseudoSourceValue(FI); return V; diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp index e4ff44d..3be6b43 100644 --- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -1758,7 +1758,7 @@ SDValue DAGCombiner::visitAND(SDNode *N) { ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); EVT VT = N1.getValueType(); - unsigned BitWidth = VT.getSizeInBits(); + unsigned BitWidth = VT.getScalarType().getSizeInBits(); // fold vector ops if (VT.isVector()) { @@ -1872,9 +1872,9 @@ SDValue DAGCombiner::visitAND(SDNode *N) { EVT MemVT = LN0->getMemoryVT(); // If we zero all the possible extended bits, then we can turn this into // a zextload if we are running before legalize or the operation is legal. - unsigned BitWidth = N1.getValueSizeInBits(); + unsigned BitWidth = N1.getValueType().getScalarType().getSizeInBits(); if (DAG.MaskedValueIsZero(N1, APInt::getHighBitsSet(BitWidth, - BitWidth - MemVT.getSizeInBits())) && + BitWidth - MemVT.getScalarType().getSizeInBits())) && ((!LegalOperations && !LN0->isVolatile()) || TLI.isLoadExtLegal(ISD::ZEXTLOAD, MemVT))) { SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, N0.getDebugLoc(), VT, @@ -1895,9 +1895,9 @@ SDValue DAGCombiner::visitAND(SDNode *N) { EVT MemVT = LN0->getMemoryVT(); // If we zero all the possible extended bits, then we can turn this into // a zextload if we are running before legalize or the operation is legal. - unsigned BitWidth = N1.getValueSizeInBits(); + unsigned BitWidth = N1.getValueType().getScalarType().getSizeInBits(); if (DAG.MaskedValueIsZero(N1, APInt::getHighBitsSet(BitWidth, - BitWidth - MemVT.getSizeInBits())) && + BitWidth - MemVT.getScalarType().getSizeInBits())) && ((!LegalOperations && !LN0->isVolatile()) || TLI.isLoadExtLegal(ISD::ZEXTLOAD, MemVT))) { SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, N0.getDebugLoc(), VT, diff --git a/lib/CodeGen/SelectionDAG/InstrEmitter.cpp b/lib/CodeGen/SelectionDAG/InstrEmitter.cpp index 02fe85d..625de11 100644 --- a/lib/CodeGen/SelectionDAG/InstrEmitter.cpp +++ b/lib/CodeGen/SelectionDAG/InstrEmitter.cpp @@ -15,6 +15,7 @@ #define DEBUG_TYPE "instr-emitter" #include "InstrEmitter.h" +#include "SDDbgValue.h" #include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -497,6 +498,56 @@ InstrEmitter::EmitCopyToRegClassNode(SDNode *Node, assert(isNew && "Node emitted out of order - early"); } +/// EmitDbgValue - Generate any debug info that refers to this Node. Constant +/// dbg_value is not handled here. +void +InstrEmitter::EmitDbgValue(SDNode *Node, + DenseMap<SDValue, unsigned> &VRBaseMap, + SDDbgValue *sd) { + if (!Node->getHasDebugValue()) + return; + if (!sd) + return; + unsigned VReg = getVR(SDValue(sd->getSDNode(), sd->getResNo()), VRBaseMap); + const TargetInstrDesc &II = TII->get(TargetOpcode::DBG_VALUE); + DebugLoc DL = sd->getDebugLoc(); + MachineInstr *MI; + if (VReg) { + MI = BuildMI(*MF, DL, II).addReg(VReg, RegState::Debug). + addImm(sd->getOffset()). + addMetadata(sd->getMDPtr()); + } else { + // Insert an Undef so we can see what we dropped. + MI = BuildMI(*MF, DL, II).addReg(0U).addImm(sd->getOffset()). + addMetadata(sd->getMDPtr()); + } + MBB->insert(InsertPos, MI); +} + +/// EmitDbgValue - Generate constant debug info. No SDNode is involved. +void +InstrEmitter::EmitDbgValue(SDDbgValue *sd) { + if (!sd) + return; + const TargetInstrDesc &II = TII->get(TargetOpcode::DBG_VALUE); + DebugLoc DL = sd->getDebugLoc(); + MachineInstr *MI; + Value *V = sd->getConst(); + if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { + MI = BuildMI(*MF, DL, II).addImm(CI->getZExtValue()). + addImm(sd->getOffset()). + addMetadata(sd->getMDPtr()); + } else if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) { + MI = BuildMI(*MF, DL, II).addFPImm(CF).addImm(sd->getOffset()). + addMetadata(sd->getMDPtr()); + } else { + // Insert an Undef so we can see what we dropped. + MI = BuildMI(*MF, DL, II).addReg(0U).addImm(sd->getOffset()). + addMetadata(sd->getMDPtr()); + } + MBB->insert(InsertPos, MI); +} + /// EmitNode - Generate machine code for a node and needed dependencies. /// void InstrEmitter::EmitNode(SDNode *Node, bool IsClone, bool IsCloned, diff --git a/lib/CodeGen/SelectionDAG/InstrEmitter.h b/lib/CodeGen/SelectionDAG/InstrEmitter.h index 91817e4..4fe9f19 100644 --- a/lib/CodeGen/SelectionDAG/InstrEmitter.h +++ b/lib/CodeGen/SelectionDAG/InstrEmitter.h @@ -23,6 +23,7 @@ namespace llvm { class TargetInstrDesc; +class SDDbgValue; class InstrEmitter { MachineFunction *MF; @@ -97,6 +98,16 @@ public: /// MachineInstr. static unsigned CountOperands(SDNode *Node); + /// EmitDbgValue - Generate any debug info that refers to this Node. Constant + /// dbg_value is not handled here. + void EmitDbgValue(SDNode *Node, + DenseMap<SDValue, unsigned> &VRBaseMap, + SDDbgValue* sd); + + + /// EmitDbgValue - Generate a constant DBG_VALUE. No node is involved. + void EmitDbgValue(SDDbgValue* sd); + /// EmitNode - Generate machine code for a node and needed dependencies. /// void EmitNode(SDNode *Node, bool IsClone, bool IsCloned, diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp index c7ab34f..f498263 100644 --- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp +++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp @@ -2008,6 +2008,31 @@ SDValue SelectionDAGLegalize::ExpandLegalINT_TO_FP(bool isSigned, return Result; } assert(!isSigned && "Legalize cannot Expand SINT_TO_FP for i64 yet"); + + // Implementation of unsigned i64 to f64 following the algorithm in + // __floatundidf in compiler_rt. This implementation has the advantage + // of performing rounding correctly, both in the default rounding mode + // and in all alternate rounding modes. + // TODO: Generalize this for use with other types. + if (Op0.getValueType() == MVT::i64 && DestVT == MVT::f64) { + SDValue TwoP52 = + DAG.getConstant(UINT64_C(0x4330000000000000), MVT::i64); + SDValue TwoP84PlusTwoP52 = + DAG.getConstantFP(BitsToDouble(UINT64_C(0x4530000000100000)), MVT::f64); + SDValue TwoP84 = + DAG.getConstant(UINT64_C(0x4530000000000000), MVT::i64); + + SDValue Lo = DAG.getZeroExtendInReg(Op0, dl, MVT::i32); + SDValue Hi = DAG.getNode(ISD::SRL, dl, MVT::i64, Op0, + DAG.getConstant(32, MVT::i64)); + SDValue LoOr = DAG.getNode(ISD::OR, dl, MVT::i64, Lo, TwoP52); + SDValue HiOr = DAG.getNode(ISD::OR, dl, MVT::i64, Hi, TwoP84); + SDValue LoFlt = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::f64, LoOr); + SDValue HiFlt = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::f64, HiOr); + SDValue HiSub = DAG.getNode(ISD::FSUB, dl, MVT::f64, HiFlt, TwoP84PlusTwoP52); + return DAG.getNode(ISD::FADD, dl, MVT::f64, LoFlt, HiSub); + } + SDValue Tmp1 = DAG.getNode(ISD::SINT_TO_FP, dl, DestVT, Op0); SDValue SignSet = DAG.getSetCC(dl, TLI.getSetCCResultType(Op0.getValueType()), diff --git a/lib/CodeGen/SelectionDAG/SDDbgValue.h b/lib/CodeGen/SelectionDAG/SDDbgValue.h new file mode 100644 index 0000000..9e15fc9 --- /dev/null +++ b/lib/CodeGen/SelectionDAG/SDDbgValue.h @@ -0,0 +1,67 @@ +//===-- llvm/CodeGen/SDDbgValue.h - SD dbg_value handling--------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares the SDDbgValue class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_SDDBGVALUE_H +#define LLVM_CODEGEN_SDDBGVALUE_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/DebugLoc.h" + +namespace llvm { + +class MDNode; +class SDNode; +class Value; + +/// SDDbgValue - Holds the information from a dbg_value node through SDISel. +/// Either Const or Node is nonzero, but not both. +/// We do not use SDValue here to avoid including its header. + +class SDDbgValue { + SDNode *Node; // valid for non-constants + unsigned ResNo; // valid for non-constants + Value *Const; // valid for constants + MDNode *mdPtr; + uint64_t Offset; + DebugLoc DL; +public: + // Constructor for non-constants. + SDDbgValue(MDNode *mdP, SDNode *N, unsigned R, uint64_t off, DebugLoc dl) : + Node(N), ResNo(R), Const(0), mdPtr(mdP), Offset(off), DL(dl) {} + + // Constructor for constants. + SDDbgValue(MDNode *mdP, Value *C, uint64_t off, DebugLoc dl) : Node(0), + ResNo(0), Const(C), mdPtr(mdP), Offset(off), DL(dl) {} + + // Returns the MDNode pointer. + MDNode *getMDPtr() { return mdPtr; } + + // Returns the SDNode* (valid for non-constants only). + SDNode *getSDNode() { assert (!Const); return Node; } + + // Returns the ResNo (valid for non-constants only). + unsigned getResNo() { assert (!Const); return ResNo; } + + // Returns the Value* for a constant (invalid for non-constants). + Value *getConst() { assert (!Node); return Const; } + + // Returns the offset. + uint64_t getOffset() { return Offset; } + + // Returns the DebugLoc. + DebugLoc getDebugLoc() { return DL; } +}; + +} // end llvm namespace + +#endif diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index 002bc68..023e486 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -4869,6 +4869,43 @@ SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList, return NULL; } +namespace { + +/// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node +/// pointed to by a use iterator is deleted, increment the use iterator +/// so that it doesn't dangle. +/// +/// This class also manages a "downlink" DAGUpdateListener, to forward +/// messages to ReplaceAllUsesWith's callers. +/// +class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener { + SelectionDAG::DAGUpdateListener *DownLink; + SDNode::use_iterator &UI; + SDNode::use_iterator &UE; + + virtual void NodeDeleted(SDNode *N, SDNode *E) { + // Increment the iterator as needed. + while (UI != UE && N == *UI) + ++UI; + + // Then forward the message. + if (DownLink) DownLink->NodeDeleted(N, E); + } + + virtual void NodeUpdated(SDNode *N) { + // Just forward the message. + if (DownLink) DownLink->NodeUpdated(N); + } + +public: + RAUWUpdateListener(SelectionDAG::DAGUpdateListener *dl, + SDNode::use_iterator &ui, + SDNode::use_iterator &ue) + : DownLink(dl), UI(ui), UE(ue) {} +}; + +} + /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. /// This can cause recursive merging of nodes in the DAG. /// @@ -4889,6 +4926,7 @@ void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To, // is replaced by To, we don't want to replace of all its users with To // too. See PR3018 for more info. SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); + RAUWUpdateListener Listener(UpdateListener, UI, UE); while (UI != UE) { SDNode *User = *UI; @@ -4907,7 +4945,7 @@ void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To, // Now that we have modified User, add it back to the CSE maps. If it // already exists there, recursively merge the results together. - AddModifiedNodeToCSEMaps(User, UpdateListener); + AddModifiedNodeToCSEMaps(User, &Listener); } } @@ -4933,6 +4971,7 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, // Iterate over just the existing users of From. See the comments in // the ReplaceAllUsesWith above. SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); + RAUWUpdateListener Listener(UpdateListener, UI, UE); while (UI != UE) { SDNode *User = *UI; @@ -4951,7 +4990,7 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, // Now that we have modified User, add it back to the CSE maps. If it // already exists there, recursively merge the results together. - AddModifiedNodeToCSEMaps(User, UpdateListener); + AddModifiedNodeToCSEMaps(User, &Listener); } } @@ -4969,6 +5008,7 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, // Iterate over just the existing users of From. See the comments in // the ReplaceAllUsesWith above. SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); + RAUWUpdateListener Listener(UpdateListener, UI, UE); while (UI != UE) { SDNode *User = *UI; @@ -4988,7 +5028,7 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, // Now that we have modified User, add it back to the CSE maps. If it // already exists there, recursively merge the results together. - AddModifiedNodeToCSEMaps(User, UpdateListener); + AddModifiedNodeToCSEMaps(User, &Listener); } } @@ -5010,6 +5050,7 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To, // the ReplaceAllUsesWith above. SDNode::use_iterator UI = From.getNode()->use_begin(), UE = From.getNode()->use_end(); + RAUWUpdateListener Listener(UpdateListener, UI, UE); while (UI != UE) { SDNode *User = *UI; bool UserRemovedFromCSEMaps = false; @@ -5045,7 +5086,7 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To, // Now that we have modified User, add it back to the CSE maps. If it // already exists there, recursively merge the results together. - AddModifiedNodeToCSEMaps(User, UpdateListener); + AddModifiedNodeToCSEMaps(User, &Listener); } } diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 2e2020d..05f9f1f 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -56,9 +56,12 @@ #include "llvm/Support/MathExtras.h" #include "llvm/Support/Timer.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/ADT/Statistic.h" #include <algorithm> using namespace llvm; +STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on"); + static cl::opt<bool> EnableFastISelVerbose("fast-isel-verbose", cl::Hidden, cl::desc("Enable verbose messages in the \"fast\" " @@ -930,6 +933,7 @@ void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, // feed PHI nodes in successor blocks. if (isa<TerminatorInst>(BI)) if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, FastIS)) { + ++NumFastIselFailures; ResetDebugLoc(SDB, FastIS); if (EnableFastISelVerbose || EnableFastISelAbort) { dbgs() << "FastISel miss: "; @@ -954,6 +958,7 @@ void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, // Then handle certain instructions as single-LLVM-Instruction blocks. if (isa<CallInst>(BI)) { + ++NumFastIselFailures; if (EnableFastISelVerbose || EnableFastISelAbort) { dbgs() << "FastISel missed call: "; BI->dump(); @@ -983,6 +988,7 @@ void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, // Otherwise, give up on FastISel for the rest of the block. // For now, be a little lenient about non-branch terminators. if (!isa<TerminatorInst>(BI) || isa<BranchInst>(BI)) { + ++NumFastIselFailures; if (EnableFastISelVerbose || EnableFastISelAbort) { dbgs() << "FastISel miss: "; BI->dump(); @@ -1032,6 +1038,8 @@ SelectionDAGISel::FinishBasicBlock() { MachineInstr *PHI = SDB->PHINodesToUpdate[i].first; assert(PHI->isPHI() && "This is not a machine PHI node that we are updating!"); + if (!BB->isSuccessor(PHI->getParent())) + continue; PHI->addOperand(MachineOperand::CreateReg(SDB->PHINodesToUpdate[i].second, false)); PHI->addOperand(MachineOperand::CreateMBB(BB)); @@ -1414,21 +1422,6 @@ static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse, return false; } -/// isNonImmUse - Start searching from Root up the DAG to check is Def can -/// be reached. Return true if that's the case. However, ignore direct uses -/// by ImmedUse (which would be U in the example illustrated in -/// IsLegalToFold) and by Root (which can happen in the store case). -/// FIXME: to be really generic, we should allow direct use by any node -/// that is being folded. But realisticly since we only fold loads which -/// have one non-chain use, we only need to watch out for load/op/store -/// and load/op/cmp case where the root (store / cmp) may reach the load via -/// its chain operand. -static inline bool isNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse, - bool IgnoreChains) { - SmallPtrSet<SDNode*, 16> Visited; - return findNonImmUse(Root, Def, ImmedUse, Root, Visited, IgnoreChains); -} - /// IsProfitableToFold - Returns true if it's profitable to fold the specific /// operand node N of U during instruction selection that starts at Root. bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U, @@ -1485,6 +1478,8 @@ bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, // Fold. But since Fold and FU are flagged together, this will create // a cycle in the scheduling graph. + // If the node has flags, walk down the graph to the "lowest" node in the + // flagged set. EVT VT = Root->getValueType(Root->getNumValues()-1); while (VT == MVT::Flag) { SDNode *FU = findFlagUse(Root); @@ -1492,9 +1487,17 @@ bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, break; Root = FU; VT = Root->getValueType(Root->getNumValues()-1); + + // If our query node has a flag result with a use, we've walked up it. If + // the user (which has already been selected) has a chain or indirectly uses + // the chain, our WalkChainUsers predicate will not consider it. Because of + // this, we cannot ignore chains in this predicate. + IgnoreChains = false; } + - return !isNonImmUse(Root, N.getNode(), U, IgnoreChains); + SmallPtrSet<SDNode*, 16> Visited; + return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains); } SDNode *SelectionDAGISel::Select_INLINEASM(SDNode *N) { @@ -2249,11 +2252,15 @@ SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, N.getNode())) break; continue; - case OPC_CheckComplexPat: - if (!CheckComplexPattern(NodeToMatch, N, - MatcherTable[MatcherIndex++], RecordedNodes)) + case OPC_CheckComplexPat: { + unsigned CPNum = MatcherTable[MatcherIndex++]; + unsigned RecNo = MatcherTable[MatcherIndex++]; + assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat"); + if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo], CPNum, + RecordedNodes)) break; continue; + } case OPC_CheckOpcode: if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break; continue; @@ -2711,29 +2718,26 @@ SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, void SelectionDAGISel::CannotYetSelect(SDNode *N) { - if (N->getOpcode() == ISD::INTRINSIC_W_CHAIN || - N->getOpcode() == ISD::INTRINSIC_WO_CHAIN || - N->getOpcode() == ISD::INTRINSIC_VOID) - return CannotYetSelectIntrinsic(N); - std::string msg; raw_string_ostream Msg(msg); Msg << "Cannot yet select: "; - N->printrFull(Msg, CurDAG); + + if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN && + N->getOpcode() != ISD::INTRINSIC_WO_CHAIN && + N->getOpcode() != ISD::INTRINSIC_VOID) { + N->printrFull(Msg, CurDAG); + } else { + bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other; + unsigned iid = + cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue(); + if (iid < Intrinsic::num_intrinsics) + Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid); + else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo()) + Msg << "target intrinsic %" << TII->getName(iid); + else + Msg << "unknown intrinsic #" << iid; + } llvm_report_error(Msg.str()); } -void SelectionDAGISel::CannotYetSelectIntrinsic(SDNode *N) { - dbgs() << "Cannot yet select: "; - unsigned iid = - cast<ConstantSDNode>(N->getOperand(N->getOperand(0).getValueType() == - MVT::Other))->getZExtValue(); - if (iid < Intrinsic::num_intrinsics) - llvm_report_error("Cannot yet select: intrinsic %" + - Intrinsic::getName((Intrinsic::ID)iid)); - else if (const TargetIntrinsicInfo *tii = TM.getIntrinsicInfo()) - llvm_report_error(Twine("Cannot yet select: target intrinsic %") + - tii->getName(iid)); -} - char SelectionDAGISel::ID = 0; diff --git a/lib/CodeGen/SjLjEHPrepare.cpp b/lib/CodeGen/SjLjEHPrepare.cpp index 8d4d1b2..059e8d6 100644 --- a/lib/CodeGen/SjLjEHPrepare.cpp +++ b/lib/CodeGen/SjLjEHPrepare.cpp @@ -44,7 +44,6 @@ namespace { const Type *FunctionContextTy; Constant *RegisterFn; Constant *UnregisterFn; - Constant *ResumeFn; Constant *BuiltinSetjmpFn; Constant *FrameAddrFn; Constant *LSDAAddrFn; @@ -67,8 +66,8 @@ namespace { } private: - void markInvokeCallSite(InvokeInst *II, unsigned InvokeNo, - Value *CallSite, + void insertCallSiteStore(Instruction *I, int Number, Value *CallSite); + void markInvokeCallSite(InvokeInst *II, int InvokeNo, Value *CallSite, SwitchInst *CatchSwitch); void splitLiveRangesLiveAcrossInvokes(SmallVector<InvokeInst*,16> &Invokes); bool insertSjLjEHSupport(Function &F); @@ -107,11 +106,6 @@ bool SjLjEHPass::doInitialization(Module &M) { Type::getVoidTy(M.getContext()), PointerType::getUnqual(FunctionContextTy), (Type *)0); - ResumeFn = - M.getOrInsertFunction("_Unwind_SjLj_Resume", - Type::getVoidTy(M.getContext()), - VoidPtrTy, - (Type *)0); FrameAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::frameaddress); BuiltinSetjmpFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_setjmp); LSDAAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_lsda); @@ -123,12 +117,22 @@ bool SjLjEHPass::doInitialization(Module &M) { return true; } +/// insertCallSiteStore - Insert a store of the call-site value to the +/// function context +void SjLjEHPass::insertCallSiteStore(Instruction *I, int Number, + Value *CallSite) { + ConstantInt *CallSiteNoC = ConstantInt::get(Type::getInt32Ty(I->getContext()), + Number); + // Insert a store of the call-site number + new StoreInst(CallSiteNoC, CallSite, true, I); // volatile +} + /// markInvokeCallSite - Insert code to mark the call_site for this invoke -void SjLjEHPass::markInvokeCallSite(InvokeInst *II, unsigned InvokeNo, +void SjLjEHPass::markInvokeCallSite(InvokeInst *II, int InvokeNo, Value *CallSite, SwitchInst *CatchSwitch) { ConstantInt *CallSiteNoC= ConstantInt::get(Type::getInt32Ty(II->getContext()), - InvokeNo); + InvokeNo); // The runtime comes back to the dispatcher with the call_site - 1 in // the context. Odd, but there it is. ConstantInt *SwitchValC = ConstantInt::get(Type::getInt32Ty(II->getContext()), @@ -145,8 +149,11 @@ void SjLjEHPass::markInvokeCallSite(InvokeInst *II, unsigned InvokeNo, } } - // Insert a store of the invoke num before the invoke - new StoreInst(CallSiteNoC, CallSite, true, II); // volatile + // Insert the store of the call site value + insertCallSiteStore(II, InvokeNo, CallSite); + + // Record the call site value for the back end so it stays associated with + // the invoke. CallInst::Create(CallSiteFn, CallSiteNoC, "", II); // Add a switch case to our unwind block. @@ -272,8 +279,8 @@ bool SjLjEHPass::insertSjLjEHSupport(Function &F) { SmallVector<InvokeInst*,16> Invokes; // Look through the terminators of the basic blocks to find invokes, returns - // and unwinds - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) + // and unwinds. + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { // Remember all return instructions in case we insert an invoke into this // function. @@ -283,6 +290,7 @@ bool SjLjEHPass::insertSjLjEHSupport(Function &F) { } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { Unwinds.push_back(UI); } + } // If we don't have any invokes or unwinds, there's nothing to do. if (Unwinds.empty() && Invokes.empty()) return false; @@ -478,24 +486,21 @@ bool SjLjEHPass::insertSjLjEHSupport(Function &F) { for (unsigned i = 0, e = Invokes.size(); i != e; ++i) markInvokeCallSite(Invokes[i], i+1, CallSite, DispatchSwitch); - // The front end has likely added calls to _Unwind_Resume. We need - // to find those calls and mark the call_site as -1 immediately prior. - // resume is a noreturn function, so any block that has a call to it - // should end in an 'unreachable' instruction with the call immediately - // prior. That's how we'll search. - // ??? There's got to be a better way. this is fugly. - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) - if ((dyn_cast<UnreachableInst>(BB->getTerminator()))) { - BasicBlock::iterator I = BB->getTerminator(); - // Check the previous instruction and see if it's a resume call - if (I == BB->begin()) continue; - if (CallInst *CI = dyn_cast<CallInst>(--I)) { - if (CI->getCalledFunction() == ResumeFn) { - Value *NegativeOne = Constant::getAllOnesValue(Int32Ty); - new StoreInst(NegativeOne, CallSite, true, I); // volatile - } + // Mark call instructions that aren't nounwind as no-action + // (call_site == -1). Skip the entry block, as prior to then, no function + // context has been created for this function and any unexpected exceptions + // thrown will go directly to the caller's context, which is what we want + // anyway, so no need to do anything here. + for (Function::iterator BB = F.begin(), E = F.end(); ++BB != E;) { + for (BasicBlock::iterator I = BB->begin(), end = BB->end(); I != end; ++I) + if (CallInst *CI = dyn_cast<CallInst>(I)) { + // Ignore calls to the EH builtins (eh.selector, eh.exception) + Constant *Callee = CI->getCalledFunction(); + if (Callee != SelectorFn && Callee != ExceptionFn + && !CI->doesNotThrow()) + insertCallSiteStore(CI, -1, CallSite); } - } + } // Replace all unwinds with a branch to the unwind handler. // ??? Should this ever happen with sjlj exceptions? diff --git a/lib/CodeGen/TargetLoweringObjectFileImpl.cpp b/lib/CodeGen/TargetLoweringObjectFileImpl.cpp index ef6e129..3b3be5d 100644 --- a/lib/CodeGen/TargetLoweringObjectFileImpl.cpp +++ b/lib/CodeGen/TargetLoweringObjectFileImpl.cpp @@ -550,8 +550,8 @@ void TargetLoweringObjectFileMachO::Initialize(MCContext &Ctx, } // Exception Handling. - LSDASection = getMachOSection("__TEXT", "__gcc_except_tab", 0, - SectionKind::getReadOnlyWithRel()); + LSDASection = getMachOSection("__DATA", "__gcc_except_tab", 0, + SectionKind::getDataRel()); EHFrameSection = getMachOSection("__TEXT", "__eh_frame", MCSectionMachO::S_COALESCED | @@ -652,7 +652,7 @@ SelectSectionForGlobal(const GlobalValue *GV, SectionKind Kind, // FIXME: Alignment check should be handled by section classifier. if (Kind.isMergeable1ByteCString() || - Kind.isMergeable2ByteCString()) { + (Kind.isMergeable2ByteCString() && !GV->hasExternalLinkage())) { if (TM.getTargetData()->getPreferredAlignment( cast<GlobalVariable>(GV)) < 32) { if (Kind.isMergeable1ByteCString()) @@ -779,7 +779,7 @@ unsigned TargetLoweringObjectFileMachO::getFDEEncoding() const { } unsigned TargetLoweringObjectFileMachO::getTTypeEncoding() const { - return DW_EH_PE_indirect | DW_EH_PE_pcrel | DW_EH_PE_sdata4; + return DW_EH_PE_absptr; } //===----------------------------------------------------------------------===// diff --git a/lib/CodeGen/TwoAddressInstructionPass.cpp b/lib/CodeGen/TwoAddressInstructionPass.cpp index 0ba3843..c840b39 100644 --- a/lib/CodeGen/TwoAddressInstructionPass.cpp +++ b/lib/CodeGen/TwoAddressInstructionPass.cpp @@ -454,13 +454,10 @@ MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, const TargetInstrInfo *TII, bool &IsCopy, unsigned &DstReg, bool &IsDstPhys) { - MachineRegisterInfo::use_nodbg_iterator UI = MRI->use_nodbg_begin(Reg); - if (UI == MRI->use_nodbg_end()) - return 0; - MachineInstr &UseMI = *UI; - if (++UI != MRI->use_nodbg_end()) - // More than one use. + if (!MRI->hasOneNonDBGUse(Reg)) + // None or more than one use. return 0; + MachineInstr &UseMI = *MRI->use_nodbg_begin(Reg); if (UseMI.getParent() != MBB) return 0; unsigned SrcReg; |
