+AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs,

+ MachineBasicBlock *BB) :

+ NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0) {

+

+ const unsigned BBSize = BB->size();

+ for (unsigned i = 0; i < NumTargetRegs; ++i) {

+ // Initialize all registers to be in their own group. Initially we

+ // assign the register to the same-indexed GroupNode.

+ // Initialize the indices to indicate that no registers are live.

+ KillIndices[i] = ~0u;

+ DefIndices[i] = BBSize;

+ }

+ for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) {

+ State = new AggressiveAntiDepState(TRI->getNumRegs(), BB);

+ for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) {

+ /// NumTargetRegs - Number of non-virtual target registers

+ /// (i.e. TRI->getNumRegs()).

+ const unsigned NumTargetRegs;

+

+ AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB);

+ O << '\n';

+ O << MAI->getCommentString() << ' ';

+ DIScope Scope(DLT.Scope);

+ // Omit the directory, because it's likely to be long and uninteresting.

+ if (!Scope.isNull())

+ O << Scope.getFilename();

+ else

+ O << "<unknown>";

+ O << ':' << DLT.Line;

+ O << ':' << DLT.Col;

+ const MachineMemOperand *MMO;

+ MMO = *MI.memoperands_begin();

+ O << MAI->getCommentString() << ' ' << MMO->getSize() << "-byte Reload";

+ else if (TM.getInstrInfo()->hasLoadFromStackSlot(&MI, MMO, FI)) {

+ O << MAI->getCommentString() << ' '

+ << MMO->getSize() << "-byte Folded Reload";

+ MMO = *MI.memoperands_begin();

+ O << MAI->getCommentString() << ' ' << MMO->getSize() << "-byte Spill";

+ else if (TM.getInstrInfo()->hasStoreToStackSlot(&MI, MMO, FI)) {

+ O << MAI->getCommentString() << ' '

+ << MMO->getSize() << "-byte Folded Spill";

+ /// DIEString - A string value DIE. This DIE keeps string reference only.

+/// addString - Add a string attribute data and value. DIEString only

+/// keeps string reference.

+ unsigned FileID = findCompileUnit(V->getCompileUnit())->getID();

+ unsigned FileID = findCompileUnit(G->getCompileUnit())->getID();

+ unsigned FileID = findCompileUnit(SP->getCompileUnit())->getID();

+ unsigned FileID = findCompileUnit(CU)->getID();

+/// addToContextOwner - Add Die into the list of its context owner's children.

+void DwarfDebug::addToContextOwner(DIE *Die, DIDescriptor Context) {

+ if (Context.isNull())

+ ModuleCU->addDie(Die);

+ else if (Context.isType()) {

+ DIE *ContextDIE = getOrCreateTypeDIE(DIType(Context.getNode()));

+ ContextDIE->addChild(Die);

+ } else if (DIE *ContextDIE = ModuleCU->getDIE(Context.getNode()))

+ ContextDIE->addChild(Die);

+ else

+ ModuleCU->addDie(Die);

+}

+

+/// getOrCreateTypeDIE - Find existing DIE or create new DIE for the

+/// given DIType.

+DIE *DwarfDebug::getOrCreateTypeDIE(DIType Ty) {

+ DIE *TyDIE = ModuleCU->getDIE(Ty.getNode());

+ if (TyDIE)

+ return TyDIE;

+

+ // Create new type.

+ TyDIE = new DIE(dwarf::DW_TAG_base_type);

+ ModuleCU->insertDIE(Ty.getNode(), TyDIE);

+ if (Ty.isBasicType())

+ constructTypeDIE(*TyDIE, DIBasicType(Ty.getNode()));

+ else if (Ty.isCompositeType())

+ constructTypeDIE(*TyDIE, DICompositeType(Ty.getNode()));

+ else {

+ assert(Ty.isDerivedType() && "Unknown kind of DIType");

+ constructTypeDIE(*TyDIE, DIDerivedType(Ty.getNode()));

+ }

+

+ addToContextOwner(TyDIE, Ty.getContext());

+ return TyDIE;

+}

+

+void DwarfDebug::addType(DIE *Entity, DIType Ty) {

+ DIEEntry *Entry = ModuleCU->getDIEEntry(Ty.getNode());

+ ModuleCU->insertDIEEntry(Ty.getNode(), Entry);

+ DIE *Buffer = getOrCreateTypeDIE(Ty);

+void DwarfDebug::constructTypeDIE(DIE &Buffer, DIBasicType BTy) {

+void DwarfDebug::constructTypeDIE(DIE &Buffer, DIDerivedType DTy) {

+ addType(&Buffer, FromTy);

+void DwarfDebug::constructTypeDIE(DIE &Buffer, DICompositeType CTy) {

+ constructArrayTypeDIE(Buffer, &CTy);

+ ElemDie = constructEnumTypeDIE(&Enum);

+ addType(&Buffer, DIType(RTy.getNode()));

+ addType(Arg, DIType(Ty.getNode()));

+ ElemDie = createSubprogramDIE(DISubprogram(Element.getNode()));

+ ElemDie = createMemberDIE(DIDerivedType(Element.getNode()));

+ addSInt(DW_Subrange, dwarf::DW_AT_upper_bound, 0, H);

+void DwarfDebug::constructArrayTypeDIE(DIE &Buffer,

+ addType(&Buffer, CTy->getTypeDerivedFrom());

+ DIE *IdxTy = ModuleCU->getIndexTyDie();

+ ModuleCU->addDie(IdxTy);

+ ModuleCU->setIndexTyDie(IdxTy);

+DIE *DwarfDebug::constructEnumTypeDIE(DIEnumerator *ETy) {

+DIE *DwarfDebug::createGlobalVariableDIE(const DIGlobalVariable &GV) {

+ addType(GVDie, GV.getType());

+DIE *DwarfDebug::createMemberDIE(const DIDerivedType &DT) {

+ addType(MemberDie, DT.getTypeDerivedFrom());

+ addUInt(MemberDie, dwarf::DW_AT_accessibility, dwarf::DW_FORM_flag,

+ addUInt(MemberDie, dwarf::DW_AT_accessibility, dwarf::DW_FORM_flag,

+ else if (DT.getTag() == dwarf::DW_TAG_inheritance)

+ addUInt(MemberDie, dwarf::DW_AT_accessibility, dwarf::DW_FORM_flag,

+ dwarf::DW_ACCESS_public);

+ if (DT.isVirtual())

+ addUInt(MemberDie, dwarf::DW_AT_virtuality, dwarf::DW_FORM_flag,

+ dwarf::DW_VIRTUALITY_virtual);

+DIE *DwarfDebug::createSubprogramDIE(const DISubprogram &SP, bool MakeDecl) {

+ DIE *SPDie = ModuleCU->getDIE(SP.getNode());

+ if (SPDie)

+ return SPDie;

+

+ SPDie = new DIE(dwarf::DW_TAG_subprogram);

+ DICompositeType SPTy = SP.getType();

+ DIArray Args = SPTy.getTypeArray();

+

+ if (Args.isNull() || SPTag != dwarf::DW_TAG_subroutine_type)

+ addType(SPDie, SPTy);

+ else

+ addType(SPDie, DIType(Args.getElement(0).getNode()));

+

+ unsigned VK = SP.getVirtuality();

+ if (VK) {

+ addUInt(SPDie, dwarf::DW_AT_virtuality, dwarf::DW_FORM_flag, VK);

+ DIEBlock *Block = new DIEBlock();

+ addUInt(Block, 0, dwarf::DW_FORM_data1, dwarf::DW_OP_constu);

+ addUInt(Block, 0, dwarf::DW_FORM_data1, SP.getVirtualIndex());

+ addBlock(SPDie, dwarf::DW_AT_vtable_elem_location, 0, Block);

+ ContainingTypeMap.insert(std::make_pair(SPDie, WeakVH(SP.getContainingType().getNode())));

+ if (MakeDecl || !SP.isDefinition()) {

+ // be handled while processing variables.

+ DICompositeType SPTy = SP.getType();

+ DIArray Args = SPTy.getTypeArray();

+ unsigned SPTag = SPTy.getTag();

+

+ addType(Arg, DIType(Args.getElement(i).getNode()));

+ ModuleCU->insertDIE(SP.getNode(), SPDie);

+CompileUnit *DwarfDebug::findCompileUnit(DICompileUnit Unit) {

+ if (I == CompileUnitMap.end())

+ return constructCompileUnit(Unit.getNode());

+ return I->second;

+ DISubprogram SP(SPNode);

+ if (SP.isDefinition() && !SP.getContext().isCompileUnit()) {

+ addUInt(SPDie, dwarf::DW_AT_declaration, dwarf::DW_FORM_flag, 1);

+ // Add arguments.

+ DICompositeType SPTy = SP.getType();

+ DIArray Args = SPTy.getTypeArray();

+ unsigned SPTag = SPTy.getTag();

+ if (SPTag == dwarf::DW_TAG_subroutine_type)

+ for (unsigned i = 1, N = Args.getNumElements(); i < N; ++i) {

+ DIE *Arg = new DIE(dwarf::DW_TAG_formal_parameter);

+ addType(Arg, DIType(Args.getElement(i).getNode()));

+ addUInt(Arg, dwarf::DW_AT_artificial, dwarf::DW_FORM_flag, 1); // ??

+ SPDie->addChild(Arg);

+ }

+ DIE *SPDeclDie = SPDie;

+ SPDie = new DIE(dwarf::DW_TAG_subprogram);

+ addDIEEntry(SPDie, dwarf::DW_AT_specification, dwarf::DW_FORM_ref4,

+ SPDeclDie);

+

+ ModuleCU->addDie(SPDie);

+ }

+

+DIE *DwarfDebug::constructVariableDIE(DbgVariable *DV, DbgScope *Scope) {

+ addType(VariableDie, getBlockByrefType(VD.getType(), Name));

+ addType(VariableDie, VD.getType());

+ DIE *VariableDIE = constructVariableDIE(Variables[i], Scope);

+CompileUnit *DwarfDebug::constructCompileUnit(MDNode *N) {

+ return Unit;

+ DIE *VariableDie = createGlobalVariableDIE(DI_GV);

+ if (!VariableDie)

+ return;

+ addToContextOwner(VariableDie, DI_GV.getContext());

+

+ DIE *SubprogramDie = createSubprogramDIE(SP);

+ if (SP.getContext().getNode() == SP.getCompileUnit().getNode())

+ if (TopLevelDIEs.insert(SubprogramDie))

+ TopLevelDIEsVector.push_back(SubprogramDie);

+ // Create DIEs for each global variable.

+ for (DebugInfoFinder::iterator I = DbgFinder.global_variable_begin(),

+ E = DbgFinder.global_variable_end(); I != E; ++I)

+ constructGlobalVariableDIE(*I);

+

+ // Insert top level DIEs.

+ for (SmallVector<DIE *, 4>::iterator TI = TopLevelDIEsVector.begin(),

+ TE = TopLevelDIEsVector.end(); TI != TE; ++TI)

+ ModuleCU->getCUDie()->addChild(*TI);

+

+ for (DenseMap<DIE *, WeakVH>::iterator CI = ContainingTypeMap.begin(),

+ CE = ContainingTypeMap.end(); CI != CE; ++CI) {

+ DIE *SPDie = CI->first;

+ MDNode *N = dyn_cast_or_null<MDNode>(CI->second);

+ if (!N) continue;

+ DIE *NDie = ModuleCU->getDIE(N);

+ if (!NDie) continue;

+ addDIEEntry(SPDie, dwarf::DW_AT_containing_type, dwarf::DW_FORM_ref4, NDie);

+ addDIEEntry(NDie, dwarf::DW_AT_containing_type, dwarf::DW_FORM_ref4, NDie);

+ }

+

+ O << '\n';

+ CurrentFnDbgScope = NULL;

+ DbgScopeMap.clear();

+ DbgScopeBeginMap.clear();

+ DbgScopeEndMap.clear();

+ ConcreteScopes.clear();

+ AbstractScopesList.clear();

+

+/// emitDebugInfo - Emit the debug info section.

+void DwarfDebug::emitDebugInfo() {

+ // Start debug info section.

+ Asm->OutStreamer.SwitchSection(

+ Asm->getObjFileLowering().getDwarfInfoSection());

+ DIE *Die = ModuleCU->getCUDie();

+ EmitLabel("info_begin", ModuleCU->getID());

+ EmitLabel("info_end", ModuleCU->getID());

+ << getSourceDirectoryName(SourceID.first) << '/'

+ << ':' << utostr_32(LineInfo.getLine()) << '\n';

+/// emitDebugPubNames - Emit visible names into a debug pubnames section.

+///

+void DwarfDebug::emitDebugPubNames() {

+ // Start the dwarf pubnames section.

+ Asm->OutStreamer.SwitchSection(

+ Asm->getObjFileLowering().getDwarfPubNamesSection());

+

+ EmitDifference("pubnames_end", ModuleCU->getID(),

+ "pubnames_begin", ModuleCU->getID(), true);

+ EmitLabel("pubnames_begin", ModuleCU->getID());

+ ModuleCU->getID(), 0, true, false);

+ EmitDifference("info_end", ModuleCU->getID(), "info_begin", ModuleCU->getID(),

+ const StringMap<DIE*> &Globals = ModuleCU->getGlobals();

+ EmitLabel("pubnames_end", ModuleCU->getID());

+ DenseMap<DIE *, WeakVH> ContainingTypeMap;

+

+ /// TopLevelDIEs - Collection of top level DIEs.

+ SmallPtrSet<DIE *, 4> TopLevelDIEs;

+ SmallVector<DIE *, 4> TopLevelDIEsVector;

+ /// addToContextOwner - Add Die into the list of its context owner's children.

+ void addToContextOwner(DIE *Die, DIDescriptor Context);

+

+ void addType(DIE *Entity, DIType Ty);

+

+ /// getOrCreateTypeDIE - Find existing DIE or create new DIE for the

+ /// given DIType.

+ DIE *getOrCreateTypeDIE(DIType Ty);

+ void constructTypeDIE(DIE &Buffer,

+ void constructTypeDIE(DIE &Buffer,

+ void constructTypeDIE(DIE &Buffer,

+ void constructArrayTypeDIE(DIE &Buffer,

+ DIE *constructEnumTypeDIE(DIEnumerator *ETy);

+ DIE *createGlobalVariableDIE(const DIGlobalVariable &GV);

+ DIE *createMemberDIE(const DIDerivedType &DT);

+ DIE *createSubprogramDIE(const DISubprogram &SP, bool MakeDecl = false);

+ CompileUnit *findCompileUnit(DICompileUnit Unit);

+ DIE *constructVariableDIE(DbgVariable *DV, DbgScope *S);

+ /// EmitDebugInfo - Emit the debug info section.

+ CompileUnit *constructCompileUnit(MDNode *N);

+ // We force 32-bits here because we've encoded our LSDA in the CIE with

+ // `dwarf::DW_EH_PE_sdata4'. And the CIE and FDE should agree.

+ EmitReference("exception", EHFrameInfo.Number, true, true);

+ else

+ Asm->EmitInt32((int)0);

+

+ MachineFunction::iterator I = llvm::next(MachineFunction::iterator(CurMBB));

+ for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end();

+ FBB = llvm::next(MachineFunction::iterator(PBB));

+ bool PredHasNoFallThrough = !PrevBB.canFallThrough();

+ MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB));

+ CalcSpillWeights.cpp

+ MachineSSAUpdater.cpp

+ MaxStackAlignment.cpp

+//===------------------------ CalcSpillWeights.cpp ------------------------===//

+//

+// The LLVM Compiler Infrastructure

+//

+// This file is distributed under the University of Illinois Open Source

+// License. See LICENSE.TXT for details.

+//

+//===----------------------------------------------------------------------===//

+

+#define DEBUG_TYPE "calcspillweights"

+

+#include "llvm/Function.h"

+#include "llvm/ADT/SmallSet.h"

+#include "llvm/CodeGen/CalcSpillWeights.h"

+#include "llvm/CodeGen/LiveIntervalAnalysis.h"

+#include "llvm/CodeGen/MachineFunction.h"

+#include "llvm/CodeGen/MachineLoopInfo.h"

+#include "llvm/CodeGen/MachineRegisterInfo.h"

+#include "llvm/CodeGen/SlotIndexes.h"

+#include "llvm/Support/Debug.h"

+#include "llvm/Support/raw_ostream.h"

+#include "llvm/Target/TargetInstrInfo.h"

+#include "llvm/Target/TargetRegisterInfo.h"

+

+using namespace llvm;

+

+char CalculateSpillWeights::ID = 0;

+static RegisterPass<CalculateSpillWeights> X("calcspillweights",

+ "Calculate spill weights");

+

+void CalculateSpillWeights::getAnalysisUsage(AnalysisUsage &au) const {

+ au.addRequired<LiveIntervals>();

+ au.addRequired<MachineLoopInfo>();

+ au.setPreservesAll();

+ MachineFunctionPass::getAnalysisUsage(au);

+}

+

+bool CalculateSpillWeights::runOnMachineFunction(MachineFunction &fn) {

+

+ DEBUG(errs() << "********** Compute Spill Weights **********\n"

+ << "********** Function: "

+ << fn.getFunction()->getName() << '\n');

+

+ LiveIntervals *lis = &getAnalysis<LiveIntervals>();

+ MachineLoopInfo *loopInfo = &getAnalysis<MachineLoopInfo>();

+ const TargetInstrInfo *tii = fn.getTarget().getInstrInfo();

+ MachineRegisterInfo *mri = &fn.getRegInfo();

+

+ SmallSet<unsigned, 4> processed;

+ for (MachineFunction::iterator mbbi = fn.begin(), mbbe = fn.end();

+ mbbi != mbbe; ++mbbi) {

+ MachineBasicBlock* mbb = mbbi;

+ SlotIndex mbbEnd = lis->getMBBEndIdx(mbb);

+ MachineLoop* loop = loopInfo->getLoopFor(mbb);

+ unsigned loopDepth = loop ? loop->getLoopDepth() : 0;

+ bool isExiting = loop ? loop->isLoopExiting(mbb) : false;

+

+ for (MachineBasicBlock::const_iterator mii = mbb->begin(), mie = mbb->end();

+ mii != mie; ++mii) {

+ const MachineInstr *mi = mii;

+ if (tii->isIdentityCopy(*mi))

+ continue;

+

+ if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)

+ continue;

+

+ for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {

+ const MachineOperand &mopi = mi->getOperand(i);

+ if (!mopi.isReg() || mopi.getReg() == 0)

+ continue;

+ unsigned reg = mopi.getReg();

+ if (!TargetRegisterInfo::isVirtualRegister(mopi.getReg()))

+ continue;

+ // Multiple uses of reg by the same instruction. It should not

+ // contribute to spill weight again.

+ if (!processed.insert(reg))

+ continue;

+

+ bool hasDef = mopi.isDef();

+ bool hasUse = !hasDef;

+ for (unsigned j = i+1; j != e; ++j) {

+ const MachineOperand &mopj = mi->getOperand(j);

+ if (!mopj.isReg() || mopj.getReg() != reg)

+ continue;

+ hasDef |= mopj.isDef();

+ hasUse |= mopj.isUse();

+ if (hasDef && hasUse)

+ break;

+ }

+

+ LiveInterval &regInt = lis->getInterval(reg);

+ float weight = lis->getSpillWeight(hasDef, hasUse, loopDepth);

+ if (hasDef && isExiting) {

+ // Looks like this is a loop count variable update.

+ SlotIndex defIdx = lis->getInstructionIndex(mi).getDefIndex();

+ const LiveRange *dlr =

+ lis->getInterval(reg).getLiveRangeContaining(defIdx);

+ if (dlr->end > mbbEnd)

+ weight *= 3.0F;

+ }

+ regInt.weight += weight;

+ }

+ processed.clear();

+ }

+ }

+

+ for (LiveIntervals::iterator I = lis->begin(), E = lis->end(); I != E; ++I) {

+ LiveInterval &li = *I->second;

+ if (TargetRegisterInfo::isVirtualRegister(li.reg)) {

+ // If the live interval length is essentially zero, i.e. in every live

+ // range the use follows def immediately, it doesn't make sense to spill

+ // it and hope it will be easier to allocate for this li.

+ if (isZeroLengthInterval(&li)) {

+ li.weight = HUGE_VALF;

+ continue;

+ }

+

+ bool isLoad = false;

+ SmallVector<LiveInterval*, 4> spillIs;

+ if (lis->isReMaterializable(li, spillIs, isLoad)) {

+ // If all of the definitions of the interval are re-materializable,

+ // it is a preferred candidate for spilling. If non of the defs are

+ // loads, then it's potentially very cheap to re-materialize.

+ // FIXME: this gets much more complicated once we support non-trivial

+ // re-materialization.

+ if (isLoad)

+ li.weight *= 0.9F;

+ else

+ li.weight *= 0.5F;

+ }

+

+ // Slightly prefer live interval that has been assigned a preferred reg.

+ std::pair<unsigned, unsigned> Hint = mri->getRegAllocationHint(li.reg);

+ if (Hint.first || Hint.second)

+ li.weight *= 1.01F;

+

+ // Divide the weight of the interval by its size. This encourages

+ // spilling of intervals that are large and have few uses, and

+ // discourages spilling of small intervals with many uses.

+ li.weight /= lis->getApproximateInstructionCount(li) * SlotIndex::NUM;

+ }

+ }

+

+ return false;

+}

+

+/// Returns true if the given live interval is zero length.

+bool CalculateSpillWeights::isZeroLengthInterval(LiveInterval *li) const {

+ for (LiveInterval::Ranges::const_iterator

+ i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i)

+ if (i->end.getPrevIndex() > i->start)

+ return false;

+ return true;

+}

+ MachineFunction::iterator End = llvm::next(Begin);

+ MachineFunction::iterator InsertPt =

+ llvm::next(MachineFunction::iterator(BotMBB));

+ E = llvm::next(MachineFunction::iterator(BotMBB)); I != E; ++I)

+ MachineFunction::iterator End = llvm::next(MachineFunction::iterator(BB));

+ const unsigned BBSize = BB->size();

+ for (unsigned i = 0; i < TRI->getNumRegs(); ++i) {

+ KillIndices[i] = ~0u;

+ DefIndices[i] = BBSize;

+ }

+ for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg)

+static cl::opt<bool> PreAllocTailDup("pre-regalloc-taildup", cl::Hidden,

+ cl::desc("Pre-register allocation tail duplication"));

+

+ // Pre-ra tail duplication.

+ if (OptLevel != CodeGenOpt::None &&

+ !DisableTailDuplicate && PreAllocTailDup) {

+ PM.add(createTailDuplicatePass(true));

+ printAndVerify(PM, "After Pre-RegAlloc TailDuplicate");

+ }

+

+ PM.add(createTailDuplicatePass(false));

+ if (!vni->isDefAccurate() && !vni->isPHIDef())

+bool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li,

+ VirtRegMap &vrm, unsigned reg) {

+ // We don't handle fancy stuff crossing basic block boundaries

+ if (li.ranges.size() != 1)

+ return true;

+ const LiveRange &range = li.ranges.front();

+ SlotIndex idx = range.start.getBaseIndex();

+ SlotIndex end = range.end.getPrevSlot().getBaseIndex().getNextIndex();

+

+ // Skip deleted instructions

+ MachineInstr *firstMI = getInstructionFromIndex(idx);

+ while (!firstMI && idx != end) {

+ idx = idx.getNextIndex();

+ firstMI = getInstructionFromIndex(idx);

+ }

+ if (!firstMI)

+ return false;

+ // Find last instruction in range

+ SlotIndex lastIdx = end.getPrevIndex();

+ MachineInstr *lastMI = getInstructionFromIndex(lastIdx);

+ while (!lastMI && lastIdx != idx) {

+ lastIdx = lastIdx.getPrevIndex();

+ lastMI = getInstructionFromIndex(lastIdx);

+ }

+ if (!lastMI)

+ return false;

+

+ // Range cannot cross basic block boundaries or terminators

+ MachineBasicBlock *MBB = firstMI->getParent();

+ if (MBB != lastMI->getParent() || lastMI->getDesc().isTerminator())

+ return true;

+

+ MachineBasicBlock::const_iterator E = lastMI;

+ ++E;

+ for (MachineBasicBlock::const_iterator I = firstMI; I != E; ++I) {

+ const MachineInstr &MI = *I;

+

+ // Allow copies to and from li.reg

+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;

+ if (tii_->isMoveInstr(MI, SrcReg, DstReg, SrcSubReg, DstSubReg))

+ if (SrcReg == li.reg || DstReg == li.reg)

+ continue;

+

+ // Check for operands using reg

+ for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {

+ const MachineOperand& mop = MI.getOperand(i);

+ if (!mop.isReg())

+ continue;

+ unsigned PhysReg = mop.getReg();

+ if (PhysReg == 0 || PhysReg == li.reg)

+ continue;

+ if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {

+ if (!vrm.hasPhys(PhysReg))

+ PhysReg = vrm.getPhys(PhysReg);

+ if (PhysReg && tri_->regsOverlap(PhysReg, reg))

+ return true;

+ // No conflicts found.

+ MachineInstr *MI = getInstructionFromIndex(index);

+ if (!MI)

+ continue; // skip deleted instructions

+ MachineBasicBlock *killMBB = getMBBFromIndex(VNI->def);

+ interval.getNextValue(SlotIndex(getMBBStartIdx(Killer->getParent()), true),

+ if (TargetRegisterInfo::isPhysicalRegister(Reg)) {

+ unsigned SrcSubReg = VNI->getCopy()->getOperand(2).getImm();

+ unsigned DstSubReg = VNI->getCopy()->getOperand(0).getSubReg();

+ if (SrcSubReg == DstSubReg)

+ // %reg1034:3<def> = EXTRACT_SUBREG %EDX, 3

+ // reg1034 can still be coalesced to EDX.

+ return Reg;

+ assert(DstSubReg == 0);

+ }

+bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) {

+ LiveVariables::VarInfo &VI = getVarInfo(Reg);

+

+ // Loop over all of the successors of the basic block, checking to see if

+ // the value is either live in the block, or if it is killed in the block.

+ std::vector<MachineBasicBlock*> OpSuccBlocks;

+ for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),

+ E = MBB.succ_end(); SI != E; ++SI) {

+ MachineBasicBlock *SuccMBB = *SI;

+

+ // Is it alive in this successor?

+ unsigned SuccIdx = SuccMBB->getNumber();

+ if (VI.AliveBlocks.test(SuccIdx))

+ return true;

+ OpSuccBlocks.push_back(SuccMBB);

+ }

+

+ // Check to see if this value is live because there is a use in a successor

+ // that kills it.

+ switch (OpSuccBlocks.size()) {

+ case 1: {

+ MachineBasicBlock *SuccMBB = OpSuccBlocks[0];

+ for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)

+ if (VI.Kills[i]->getParent() == SuccMBB)

+ return true;

+ break;

+ }

+ case 2: {

+ MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1];

+ for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)

+ if (VI.Kills[i]->getParent() == SuccMBB1 ||

+ VI.Kills[i]->getParent() == SuccMBB2)

+ return true;

+ break;

+ }

+ default:

+ std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end());

+ for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)

+ if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(),

+ VI.Kills[i]->getParent()))

+ return true;

+ }

+ return false;

+}

+

+ MachineBasicBlock::iterator nmi = llvm::next(mi);

+ MachineBasicBlock *MBBB = *llvm::next(succ_begin());

+ return llvm::next(I) == MachineFunction::const_iterator(MBB);

+ // Analyze the branches, if any, at the end of the block.

+ MachineBasicBlock *TBB = 0, *FBB = 0;

+ SmallVector<MachineOperand, 4> Cond;

+ const TargetInstrInfo *TII = getParent()->getTarget().getInstrInfo();

+ if (TII->AnalyzeBranch(*this, TBB, FBB, Cond, true)) {

+ // If we couldn't analyze the branch, examine the last instruction.

+ // If the block doesn't end in a known control barrier, assume fallthrough

+ // is possible. The isPredicable check is needed because this code can be

+ // called during IfConversion, where an instruction which is normally a

+ // Barrier is predicated and thus no longer an actual control barrier. This

+ // is over-conservative though, because if an instruction isn't actually

+ // predicated we could still treat it like a barrier.

+ }

+ MachineFunction::iterator FallThru =

+ llvm::next(MachineFunction::iterator(this));

+ // If this block ends with a conditional branch that falls through to its

+ // successor, set DestB as the successor.

+ // a fallthrough into DestA.

+ if (llvm::next(I) != E)

+ if (llvm::next(I) != E)

+/// isConstantValuePHI - If the specified instruction is a PHI that always

+/// merges together the same virtual register, return the register, otherwise

+/// return 0.

+unsigned MachineInstr::isConstantValuePHI() const {

+ if (getOpcode() != TargetInstrInfo::PHI)

+ return 0;

+ assert(getNumOperands() >= 3 &&

+ "It's illegal to have a PHI without source operands");

+

+ unsigned Reg = getOperand(1).getReg();

+ for (unsigned i = 3, e = getNumOperands(); i < e; i += 2)

+ if (getOperand(i).getReg() != Reg)

+ return 0;

+ return Reg;

+}

+

+ // Omit the directory, since it's usually long and uninteresting.

+ OS << Scope.getFilename();

+ else

+ OS << "<unknown>";

+ OS << ':' << DLT.Line;

+ if (DLT.Col != 0)

+ OS << ':' << DLT.Col;

+ MachineBasicBlock *NextMBB = llvm::next(MachineFunction::iterator(BotMBB));

+ if (BotMBB == llvm::next(MachineFunction::iterator(BotMBB))) break;

+ NextMBB = llvm::next(MachineFunction::iterator(BotMBB));

+//===- MachineSSAUpdater.cpp - Unstructured SSA Update Tool ---------------===//

+//

+// The LLVM Compiler Infrastructure

+//

+// This file is distributed under the University of Illinois Open Source

+// License. See LICENSE.TXT for details.

+//

+//===----------------------------------------------------------------------===//

+//

+// This file implements the MachineSSAUpdater class. It's based on SSAUpdater

+// class in lib/Transforms/Utils.

+//

+//===----------------------------------------------------------------------===//

+

+#include "llvm/CodeGen/MachineSSAUpdater.h"

+#include "llvm/CodeGen/MachineInstr.h"

+#include "llvm/CodeGen/MachineInstrBuilder.h"

+#include "llvm/CodeGen/MachineRegisterInfo.h"

+#include "llvm/Target/TargetInstrInfo.h"

+#include "llvm/Target/TargetMachine.h"

+#include "llvm/Target/TargetRegisterInfo.h"

+#include "llvm/ADT/DenseMap.h"

+#include "llvm/Support/Debug.h"

+#include "llvm/Support/ErrorHandling.h"

+#include "llvm/Support/raw_ostream.h"

+using namespace llvm;

+

+typedef DenseMap<MachineBasicBlock*, unsigned> AvailableValsTy;

+typedef std::vector<std::pair<MachineBasicBlock*, unsigned> >

+ IncomingPredInfoTy;

+

+static AvailableValsTy &getAvailableVals(void *AV) {

+ return *static_cast<AvailableValsTy*>(AV);

+}

+

+static IncomingPredInfoTy &getIncomingPredInfo(void *IPI) {

+ return *static_cast<IncomingPredInfoTy*>(IPI);

+}

+

+

+MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF,

+ SmallVectorImpl<MachineInstr*> *NewPHI)

+ : AV(0), IPI(0), InsertedPHIs(NewPHI) {

+ TII = MF.getTarget().getInstrInfo();

+ MRI = &MF.getRegInfo();

+}

+

+MachineSSAUpdater::~MachineSSAUpdater() {

+ delete &getAvailableVals(AV);

+ delete &getIncomingPredInfo(IPI);

+}

+

+/// Initialize - Reset this object to get ready for a new set of SSA

+/// updates. ProtoValue is the value used to name PHI nodes.

+void MachineSSAUpdater::Initialize(unsigned V) {

+ if (AV == 0)

+ AV = new AvailableValsTy();

+ else

+ getAvailableVals(AV).clear();

+

+ if (IPI == 0)

+ IPI = new IncomingPredInfoTy();

+ else

+ getIncomingPredInfo(IPI).clear();

+

+ VR = V;

+ VRC = MRI->getRegClass(VR);

+}

+

+/// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for

+/// the specified block.

+bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const {

+ return getAvailableVals(AV).count(BB);

+}

+

+/// AddAvailableValue - Indicate that a rewritten value is available in the

+/// specified block with the specified value.

+void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) {

+ getAvailableVals(AV)[BB] = V;

+}

+

+/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is

+/// live at the end of the specified block.

+unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) {

+ return GetValueAtEndOfBlockInternal(BB);

+}

+

+static

+unsigned LookForIdenticalPHI(MachineBasicBlock *BB,

+ SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> &PredValues) {

+ if (BB->empty())

+ return 0;

+

+ MachineBasicBlock::iterator I = BB->front();

+ if (I->getOpcode() != TargetInstrInfo::PHI)

+ return 0;

+

+ AvailableValsTy AVals;

+ for (unsigned i = 0, e = PredValues.size(); i != e; ++i)

+ AVals[PredValues[i].first] = PredValues[i].second;

+ while (I != BB->end() && I->getOpcode() == TargetInstrInfo::PHI) {

+ bool Same = true;

+ for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) {

+ unsigned SrcReg = I->getOperand(i).getReg();

+ MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB();

+ if (AVals[SrcBB] != SrcReg) {

+ Same = false;

+ break;

+ }

+ }

+ if (Same)

+ return I->getOperand(0).getReg();

+ ++I;

+ }

+ return 0;

+}

+

+/// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define

+/// a value of the given register class at the start of the specified basic

+/// block. It returns the virtual register defined by the instruction.

+static

+MachineInstr *InsertNewDef(unsigned Opcode,

+ MachineBasicBlock *BB, MachineBasicBlock::iterator I,

+ const TargetRegisterClass *RC,

+ MachineRegisterInfo *MRI, const TargetInstrInfo *TII) {

+ unsigned NewVR = MRI->createVirtualRegister(RC);

+ return BuildMI(*BB, I, DebugLoc::getUnknownLoc(), TII->get(Opcode), NewVR);

+}

+

+/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that

+/// is live in the middle of the specified block.

+///

+/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one

+/// important case: if there is a definition of the rewritten value after the

+/// 'use' in BB. Consider code like this:

+///

+/// X1 = ...

+/// SomeBB:

+/// use(X)

+/// X2 = ...

+/// br Cond, SomeBB, OutBB

+///

+/// In this case, there are two values (X1 and X2) added to the AvailableVals

+/// set by the client of the rewriter, and those values are both live out of

+/// their respective blocks. However, the use of X happens in the *middle* of

+/// a block. Because of this, we need to insert a new PHI node in SomeBB to

+/// merge the appropriate values, and this value isn't live out of the block.

+///

+unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) {

+ // If there is no definition of the renamed variable in this block, just use

+ // GetValueAtEndOfBlock to do our work.

+ if (!getAvailableVals(AV).count(BB))

+ return GetValueAtEndOfBlockInternal(BB);

+

+ // If there are no predecessors, just return undef.

+ if (BB->pred_empty()) {

+ // Insert an implicit_def to represent an undef value.

+ MachineInstr *NewDef = InsertNewDef(TargetInstrInfo::IMPLICIT_DEF,

+ BB, BB->getFirstTerminator(),

+ VRC, MRI, TII);

+ return NewDef->getOperand(0).getReg();

+ }

+

+ // Otherwise, we have the hard case. Get the live-in values for each

+ // predecessor.

+ SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues;

+ unsigned SingularValue = 0;

+

+ bool isFirstPred = true;

+ for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),

+ E = BB->pred_end(); PI != E; ++PI) {

+ MachineBasicBlock *PredBB = *PI;

+ unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB);

+ PredValues.push_back(std::make_pair(PredBB, PredVal));

+

+ // Compute SingularValue.

+ if (isFirstPred) {

+ SingularValue = PredVal;

+ isFirstPred = false;

+ } else if (PredVal != SingularValue)

+ SingularValue = 0;

+ }

+

+ // Otherwise, if all the merged values are the same, just use it.

+ if (SingularValue != 0)

+ return SingularValue;

+

+ // If an identical PHI is already in BB, just reuse it.

+ unsigned DupPHI = LookForIdenticalPHI(BB, PredValues);

+ if (DupPHI)

+ return DupPHI;

+

+ // Otherwise, we do need a PHI: insert one now.

+ MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();

+ MachineInstr *InsertedPHI = InsertNewDef(TargetInstrInfo::PHI, BB,

+ Loc, VRC, MRI, TII);

+

+ // Fill in all the predecessors of the PHI.

+ MachineInstrBuilder MIB(InsertedPHI);

+ for (unsigned i = 0, e = PredValues.size(); i != e; ++i)

+ MIB.addReg(PredValues[i].second).addMBB(PredValues[i].first);

+

+ // See if the PHI node can be merged to a single value. This can happen in

+ // loop cases when we get a PHI of itself and one other value.

+ if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {

+ InsertedPHI->eraseFromParent();

+ return ConstVal;

+ }

+

+ // If the client wants to know about all new instructions, tell it.

+ if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);

+

+ DEBUG(errs() << " Inserted PHI: " << *InsertedPHI << "\n");

+ return InsertedPHI->getOperand(0).getReg();

+}

+

+static

+MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI,

+ MachineOperand *U) {

+ for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {

+ if (&MI->getOperand(i) == U)

+ return MI->getOperand(i+1).getMBB();

+ }

+

+ llvm_unreachable("MachineOperand::getParent() failure?");

+ return 0;

+}

+

+/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes,

+/// which use their value in the corresponding predecessor.

+void MachineSSAUpdater::RewriteUse(MachineOperand &U) {

+ MachineInstr *UseMI = U.getParent();

+ unsigned NewVR = 0;

+ if (UseMI->getOpcode() == TargetInstrInfo::PHI) {

+ MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U);

+ NewVR = GetValueAtEndOfBlockInternal(SourceBB);

+ } else {

+ NewVR = GetValueInMiddleOfBlock(UseMI->getParent());

+ }

+

+ U.setReg(NewVR);

+}

+

+void MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) {

+ MRI->replaceRegWith(OldReg, NewReg);

+

+ AvailableValsTy &AvailableVals = getAvailableVals(AV);

+ for (DenseMap<MachineBasicBlock*, unsigned>::iterator

+ I = AvailableVals.begin(), E = AvailableVals.end(); I != E; ++I)

+ if (I->second == OldReg)

+ I->second = NewReg;

+}

+

+/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry

+/// for the specified BB and if so, return it. If not, construct SSA form by

+/// walking predecessors inserting PHI nodes as needed until we get to a block

+/// where the value is available.

+///

+unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){

+ AvailableValsTy &AvailableVals = getAvailableVals(AV);

+

+ // Query AvailableVals by doing an insertion of null.

+ std::pair<AvailableValsTy::iterator, bool> InsertRes =

+ AvailableVals.insert(std::make_pair(BB, 0));

+

+ // Handle the case when the insertion fails because we have already seen BB.

+ if (!InsertRes.second) {

+ // If the insertion failed, there are two cases. The first case is that the

+ // value is already available for the specified block. If we get this, just

+ // return the value.

+ if (InsertRes.first->second != 0)

+ return InsertRes.first->second;

+

+ // Otherwise, if the value we find is null, then this is the value is not

+ // known but it is being computed elsewhere in our recursion. This means

+ // that we have a cycle. Handle this by inserting a PHI node and returning

+ // it. When we get back to the first instance of the recursion we will fill

+ // in the PHI node.

+ MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();

+ MachineInstr *NewPHI = InsertNewDef(TargetInstrInfo::PHI, BB, Loc,

+ VRC, MRI,TII);

+ unsigned NewVR = NewPHI->getOperand(0).getReg();

+ InsertRes.first->second = NewVR;

+ return NewVR;

+ }

+

+ // If there are no predecessors, then we must have found an unreachable block

+ // just return 'undef'. Since there are no predecessors, InsertRes must not

+ // be invalidated.

+ if (BB->pred_empty()) {

+ // Insert an implicit_def to represent an undef value.

+ MachineInstr *NewDef = InsertNewDef(TargetInstrInfo::IMPLICIT_DEF,

+ BB, BB->getFirstTerminator(),

+ VRC, MRI, TII);

+ return InsertRes.first->second = NewDef->getOperand(0).getReg();

+ }

+

+ // Okay, the value isn't in the map and we just inserted a null in the entry

+ // to indicate that we're processing the block. Since we have no idea what

+ // value is in this block, we have to recurse through our predecessors.

+ //

+ // While we're walking our predecessors, we keep track of them in a vector,

+ // then insert a PHI node in the end if we actually need one. We could use a

+ // smallvector here, but that would take a lot of stack space for every level

+ // of the recursion, just use IncomingPredInfo as an explicit stack.

+ IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI);

+ unsigned FirstPredInfoEntry = IncomingPredInfo.size();

+

+ // As we're walking the predecessors, keep track of whether they are all

+ // producing the same value. If so, this value will capture it, if not, it

+ // will get reset to null. We distinguish the no-predecessor case explicitly

+ // below.

+ unsigned SingularValue = 0;

+ bool isFirstPred = true;

+ for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),

+ E = BB->pred_end(); PI != E; ++PI) {

+ MachineBasicBlock *PredBB = *PI;

+ unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB);

+ IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal));

+

+ // Compute SingularValue.

+ if (isFirstPred) {

+ SingularValue = PredVal;

+ isFirstPred = false;

+ } else if (PredVal != SingularValue)

+ SingularValue = 0;

+ }

+

+ /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If

+ /// this block is involved in a loop, a no-entry PHI node will have been

+ /// inserted as InsertedVal. Otherwise, we'll still have the null we inserted

+ /// above.

+ unsigned &InsertedVal = AvailableVals[BB];

+

+ // If all the predecessor values are the same then we don't need to insert a

+ // PHI. This is the simple and common case.

+ if (SingularValue) {

+ // If a PHI node got inserted, replace it with the singlar value and delete

+ // it.

+ if (InsertedVal) {

+ MachineInstr *OldVal = MRI->getVRegDef(InsertedVal);

+ // Be careful about dead loops. These RAUW's also update InsertedVal.

+ assert(InsertedVal != SingularValue && "Dead loop?");

+ ReplaceRegWith(InsertedVal, SingularValue);

+ OldVal->eraseFromParent();

+ }

+

+ InsertedVal = SingularValue;

+

+ // Drop the entries we added in IncomingPredInfo to restore the stack.

+ IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry,

+ IncomingPredInfo.end());

+ return InsertedVal;

+ }

+

+

+ // Otherwise, we do need a PHI: insert one now if we don't already have one.

+ MachineInstr *InsertedPHI;

+ if (InsertedVal == 0) {

+ MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();

+ InsertedPHI = InsertNewDef(TargetInstrInfo::PHI, BB, Loc,

+ VRC, MRI, TII);

+ InsertedVal = InsertedPHI->getOperand(0).getReg();

+ } else {

+ InsertedPHI = MRI->getVRegDef(InsertedVal);

+ }

+

+ // Fill in all the predecessors of the PHI.

+ MachineInstrBuilder MIB(InsertedPHI);

+ for (IncomingPredInfoTy::iterator I =

+ IncomingPredInfo.begin()+FirstPredInfoEntry,

+ E = IncomingPredInfo.end(); I != E; ++I)

+ MIB.addReg(I->second).addMBB(I->first);

+

+ // Drop the entries we added in IncomingPredInfo to restore the stack.

+ IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry,

+ IncomingPredInfo.end());

+

+ // See if the PHI node can be merged to a single value. This can happen in

+ // loop cases when we get a PHI of itself and one other value.

+ if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {

+ MRI->replaceRegWith(InsertedVal, ConstVal);

+ InsertedPHI->eraseFromParent();

+ InsertedVal = ConstVal;

+ } else {

+ DEBUG(errs() << " Inserted PHI: " << *InsertedPHI << "\n");

+

+ // If the client wants to know about all new instructions, tell it.

+ if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);

+ }

+

+ return InsertedVal;

+}

+//===-- MaxStackAlignment.cpp - Compute the required stack alignment -- ---===//

+//

+// The LLVM Compiler Infrastructure

+//

+// This file is distributed under the University of Illinois Open Source

+// License. See LICENSE.TXT for details.

+//

+//===----------------------------------------------------------------------===//

+//

+// This pass looks for vector register usage and aligned local objects to

+// calculate the maximum required alignment for a function. This is used by

+// targets which support it to determine if dynamic stack realignment is

+// necessary.

+//

+//===----------------------------------------------------------------------===//

+

+#include "llvm/CodeGen/MachineFunction.h"

+#include "llvm/CodeGen/MachineFrameInfo.h"

+#include "llvm/CodeGen/MachineRegisterInfo.h"

+#include "llvm/CodeGen/Passes.h"

+

+using namespace llvm;

+

+namespace {

+ struct MaximalStackAlignmentCalculator : public MachineFunctionPass {

+ static char ID;

+ MaximalStackAlignmentCalculator() : MachineFunctionPass(&ID) {}

+

+ virtual bool runOnMachineFunction(MachineFunction &MF) {

+ MachineFrameInfo *FFI = MF.getFrameInfo();

+ MachineRegisterInfo &RI = MF.getRegInfo();

+

+ // Calculate max stack alignment of all already allocated stack objects.

+ FFI->calculateMaxStackAlignment();

+ unsigned MaxAlign = FFI->getMaxAlignment();

+

+ // Be over-conservative: scan over all vreg defs and find whether vector

+ // registers are used. If yes, there is probability that vector registers

+ // will be spilled and thus the stack needs to be aligned properly.

+ // FIXME: It would be better to only do this if a spill actually

+ // happens rather than conseratively aligning the stack regardless.

+ for (unsigned RegNum = TargetRegisterInfo::FirstVirtualRegister;

+ RegNum < RI.getLastVirtReg(); ++RegNum)

+ MaxAlign = std::max(MaxAlign, RI.getRegClass(RegNum)->getAlignment());

+

+ if (FFI->getMaxAlignment() == MaxAlign)

+ return false;

+

+ FFI->setMaxAlignment(MaxAlign);

+ return true;

+ }

+

+ virtual const char *getPassName() const {

+ return "Stack Alignment Requirements Auto-Detector";

+ }

+

+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {

+ AU.setPreservesCFG();

+ MachineFunctionPass::getAnalysisUsage(AU);

+ }

+ };

+

+ char MaximalStackAlignmentCalculator::ID = 0;

+}

+

+FunctionPass*

+llvm::createMaxStackAlignmentCalculatorPass() {

+ return new MaximalStackAlignmentCalculator();

+}

+

+ if (!ValueIsUsed && !LV->isLiveOut(SrcReg, opBlock)) {

+ for (MachineBasicBlock::iterator TI = llvm::next(Term);

+ TI != opBlock.end(); ++TI) {

+ if (!LV.isLiveIn(Reg, MBB) && LV.isLiveOut(Reg, *PreMBB))

+ MF->insert(llvm::next(MachineFunction::iterator(A)), NMBB);

+ for (unsigned i = 0; i < TRI->getNumRegs(); ++i)

+ KillIndices[i] = ~0u;

+ DEBUG(errs() << "Fixing " << MO << " in ");

+ // Warning: ToggleKillFlag may invalidate MO.

+ ToggleKillFlag(MI, MO);

+#include "llvm/CodeGen/CalcSpillWeights.h"

+ AU.addPreserved<CalculateSpillWeights>();

+ KillPt = llvm::next(MachineBasicBlock::iterator(DefMI));

+ SpillPt = llvm::next(MachineBasicBlock::iterator(DefMI));

+ MachineFrameInfo *FFI = Fn.getFrameInfo();

+ bool HasCalls = FFI->hasCalls();

+ I = llvm::next(PrevI);

+#include "llvm/CodeGen/CalcSpillWeights.h"

+static cl::opt<bool>

+TrivCoalesceEnds("trivial-coalesce-ends",

+ cl::desc("Attempt trivial coalescing of interval ends"),

+ cl::init(false), cl::Hidden);

+

+ AU.addRequired<CalculateSpillWeights>();

+/// attemptTrivialCoalescing - If a simple interval is defined by a copy, try

+/// allocate the definition the same register as the source register if the

+/// register is not defined during live time of the interval. If the interval is

+/// killed by a copy, try to use the destination register. This eliminates a

+/// copy. This is used to coalesce copies which were not coalesced away before

+/// allocation either due to dest and src being in different register classes or

+/// because the coalescer was overly conservative.

+ // We cannot handle complicated live ranges. Simple linear stuff only.

+ if (cur.ranges.size() != 1)

+

+ const LiveRange &range = cur.ranges.front();

+

+ VNInfo *vni = range.valno;

+ if (vni->isUnused())

+

+ unsigned CandReg;

+ {

+ MachineInstr *CopyMI;

+ unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;

+ if (vni->def != SlotIndex() && vni->isDefAccurate() &&

+ (CopyMI = li_->getInstructionFromIndex(vni->def)) &&

+ tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg))

+ // Defined by a copy, try to extend SrcReg forward

+ CandReg = SrcReg;

+ else if (TrivCoalesceEnds &&

+ (CopyMI =

+ li_->getInstructionFromIndex(range.end.getBaseIndex())) &&

+ tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&

+ cur.reg == SrcReg)

+ // Only used by a copy, try to extend DstReg backwards

+ CandReg = DstReg;

+ else

+ return Reg;

+ }

+

+ if (TargetRegisterInfo::isVirtualRegister(CandReg)) {

+ if (!vrm_->isAssignedReg(CandReg))

+ CandReg = vrm_->getPhys(CandReg);

+ if (Reg == CandReg)

+ if (!RC->contains(CandReg))

+ if (li_->conflictsWithPhysReg(cur, *vrm_, CandReg))

+ return Reg;

+ // Try to coalesce.

+ DEBUG(errs() << "Coalescing: " << cur << " -> " << tri_->getName(CandReg)

+ << '\n');

+ vrm_->clearVirt(cur.reg);

+ vrm_->assignVirt2Phys(cur.reg, CandReg);

+ ++NumCoalesce;

+ return CandReg;

+ assert(!spillIs.empty() && "No spill intervals?");

+ SlotIndex earliestStart = spillIs[0]->beginIndex();

+ if (sli->beginIndex() < earliestStart)

+ earliestStart = sli->beginIndex();

+ newIs = spiller_->spill(sli, spillIs, &earliestStart);

+ if (!i->empty() && i->beginIndex() < earliestStart)

+#include "llvm/CodeGen/CalcSpillWeights.h"

+ au.addRequired<CalculateSpillWeights>();

+ MBBI = llvm::next(MBBI);

+ unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();

+ APInt Demanded = APInt::getAllOnesValue(BitWidth);

+ assert((!To[i].getNode() ||

+ N->getValueType(i) == To[i].getValueType()) &&

+ //

+ // do not sink logical op inside of a vector extend, since it may combine

+ // into a vsetcc.

+ !VT.isVector() &&

+ if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF) {

+ EVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT;

+ return DAG.getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);

+ }

+ unsigned OpSizeInBits = VT.getScalarType().getSizeInBits();

+ APInt::getAllOnesValue(OpSizeInBits)))

+ unsigned OpSizeInBits = VT.getScalarType().getSizeInBits();

+ if (N1C && N1C->getZExtValue() >= OpSizeInBits)

+ unsigned LowBits = OpSizeInBits - (unsigned)N1C->getZExtValue();

+ if (Sum >= OpSizeInBits) Sum = OpSizeInBits-1;

+ EVT::getIntegerVT(*DAG.getContext(), OpSizeInBits - N1C->getZExtValue());

+ TruncC.trunc(TruncVT.getScalarType().getSizeInBits());

+ unsigned OpSizeInBits = VT.getScalarType().getSizeInBits();

+ DAG.getValueType(N0.getValueType().getScalarType()));

+ return DAG.getZeroExtendInReg(Op, N->getDebugLoc(),

+ N0.getValueType().getScalarType());

+ // Fold (zext (and x, cst)) -> (and (zext x), cst)

+ if (N0.getOpcode() == ISD::AND &&

+ N0.getOperand(1).getOpcode() == ISD::Constant &&

+ N0.getOperand(0).getOpcode() != ISD::TRUNCATE &&

+ N0.getOperand(0).hasOneUse()) {

+ APInt Mask = cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue();

+ Mask.zext(VT.getSizeInBits());

+ return DAG.getNode(ISD::AND, N->getDebugLoc(), VT,

+ DAG.getNode(ISD::ZERO_EXTEND, N->getDebugLoc(), VT,

+ N0.getOperand(0)),

+ DAG.getConstant(Mask, VT));

+ }

+

+ // (zext (shl (zext x), cst)) -> (shl (zext x), cst)

+ if ((N0.getOpcode() == ISD::SHL || N0.getOpcode() == ISD::SRL) &&

+ isa<ConstantSDNode>(N0.getOperand(1)) &&

+ N0.getOperand(0).getOpcode() == ISD::ZERO_EXTEND &&

+ N0.hasOneUse()) {

+ if (N0.getOpcode() == ISD::SHL) {

+ // If the original shl may be shifting out bits, do not perform this

+ // transformation.

+ unsigned ShAmt = cast<ConstantSDNode>(N0.getOperand(1))->getZExtValue();

+ unsigned KnownZeroBits = N0.getOperand(0).getValueType().getSizeInBits() -

+ N0.getOperand(0).getOperand(0).getValueType().getSizeInBits();

+ if (ShAmt > KnownZeroBits)

+ return SDValue();

+ }

+ DebugLoc dl = N->getDebugLoc();

+ return DAG.getNode(N0.getOpcode(), dl, VT,

+ DAG.getNode(ISD::ZERO_EXTEND, dl, VT, N0.getOperand(0)),

+ DAG.getNode(ISD::ZERO_EXTEND, dl, VT, N0.getOperand(1)));

+ }

+

+ unsigned VTBits = VT.getScalarType().getSizeInBits();

+ if (DAG.ComputeNumSignBits(N0) >= VTBits-EVTBits+1)

+ if (N00.getValueType().getScalarType().getSizeInBits() < EVTBits)

+ if (ShAmt->getZExtValue()+EVTBits <= VTBits) {

+ if (VTBits-(ShAmt->getZExtValue()+EVTBits) < InSignBits)

+ DAG.isConsecutiveLoad(LD2, LD1, LD1VT.getSizeInBits()/8, 1)) {

+ if (unsigned Align = DAG.InferPtrAlignment(Ptr)) {

+ if (unsigned Align = DAG.InferPtrAlignment(Ptr)) {

+ Value.getValueType().getScalarType().getSizeInBits(),

+ // First, try doing target-independent selection.

+ if (SelectOperator(I, I->getOpcode()))

+ return true;

+

+ // Next, try calling the target to attempt to handle the instruction.

+ if (TargetSelectInstruction(I))

+ return true;

+

+ return false;

+ llvm::next(MachineFunction::iterator(MBB));

+ E = prior(DAG.allnodes_end()); I != llvm::next(E); ++I)

+ EVT VT = Node->getValueType(0);

+ EVT ShiftAmountTy = TLI.getShiftAmountTy();

+ if (VT.isVector()) {

+ ShiftAmountTy = VT;

+ VT = VT.getVectorElementType();

+ }

+ unsigned BitsDiff = VT.getSizeInBits() -

+ SDValue ShiftCst = DAG.getConstant(BitsDiff, ShiftAmountTy);

+void SelectionDAG::Legalize(CodeGenOpt::Level OptLevel) {

+ SDValue AmtExcess = DAG.getNode(ISD::SUB, dl, ShTy, Amt, NVBitsNode);

+ SDValue AmtLack = DAG.getNode(ISD::SUB, dl, ShTy, NVBitsNode, Amt);

+ SDValue isShort = DAG.getSetCC(dl, TLI.getSetCCResultType(ShTy),

+ Amt, NVBitsNode, ISD::SETULT);

+ SDValue LoS, HiS, LoL, HiL;

+ // Short: ShAmt < NVTBits

+ LoS = DAG.getNode(ISD::SHL, dl, NVT, InL, Amt);

+ HiS = DAG.getNode(ISD::OR, dl, NVT,

+ // FIXME: If Amt is zero, the following shift generates an undefined result

+ // on some architectures.

+ DAG.getNode(ISD::SRL, dl, NVT, InL, AmtLack));

+

+ // Long: ShAmt >= NVTBits

+ LoL = DAG.getConstant(0, NVT); // Lo part is zero.

+ HiL = DAG.getNode(ISD::SHL, dl, NVT, InL, AmtExcess); // Hi from Lo part.

+ Lo = DAG.getNode(ISD::SELECT, dl, NVT, isShort, LoS, LoL);

+ Hi = DAG.getNode(ISD::SELECT, dl, NVT, isShort, HiS, HiL);

+ // Short: ShAmt < NVTBits

+ HiS = DAG.getNode(ISD::SRL, dl, NVT, InH, Amt);

+ LoS = DAG.getNode(ISD::OR, dl, NVT,

+ DAG.getNode(ISD::SRL, dl, NVT, InL, Amt),

+ // FIXME: If Amt is zero, the following shift generates an undefined result

+ // on some architectures.

+ DAG.getNode(ISD::SHL, dl, NVT, InH, AmtLack));

+

+ // Long: ShAmt >= NVTBits

+ HiL = DAG.getConstant(0, NVT); // Hi part is zero.

+ LoL = DAG.getNode(ISD::SRL, dl, NVT, InH, AmtExcess); // Lo from Hi part.

+

+ Lo = DAG.getNode(ISD::SELECT, dl, NVT, isShort, LoS, LoL);

+ Hi = DAG.getNode(ISD::SELECT, dl, NVT, isShort, HiS, HiL);

+ // Short: ShAmt < NVTBits

+ HiS = DAG.getNode(ISD::SRA, dl, NVT, InH, Amt);

+ LoS = DAG.getNode(ISD::OR, dl, NVT,

+ // FIXME: If Amt is zero, the following shift generates an undefined result

+ // on some architectures.

+ DAG.getNode(ISD::SHL, dl, NVT, InH, AmtLack));

+

+ // Long: ShAmt >= NVTBits

+ HiL = DAG.getNode(ISD::SRA, dl, NVT, InH, // Sign of Hi part.

+ DAG.getConstant(NVTBits-1, ShTy));

+ LoL = DAG.getNode(ISD::SRA, dl, NVT, InH, AmtExcess); // Lo from Hi part.

+ Lo = DAG.getNode(ISD::SELECT, dl, NVT, isShort, LoS, LoL);

+ Hi = DAG.getNode(ISD::SELECT, dl, NVT, isShort, HiS, HiL);

+ case ISD::ROTR: Res = ExpandIntOp_Shift(N); break;

+ case ISD::RETURNADDR:

+ case ISD::FRAMEADDR: Res = ExpandIntOp_RETURNADDR(N); break;

+SDValue DAGTypeLegalizer::ExpandIntOp_RETURNADDR(SDNode *N) {

+ // The argument of RETURNADDR / FRAMEADDR builtin is 32 bit contant. This

+ // surely makes pretty nice problems on 8/16 bit targets. Just truncate this

+ // constant to valid type.

+ SDValue Lo, Hi;

+ GetExpandedInteger(N->getOperand(0), Lo, Hi);

+ return DAG.UpdateNodeOperands(SDValue(N, 0), Lo);

+}

+

+ SDValue ExpandIntOp_RETURNADDR(SDNode *N);

+ SDValue ScalarizeVecRes_SIGN_EXTEND_INREG(SDNode *N);

+ void SplitVecRes_SIGN_EXTEND_INREG(SDNode *N, SDValue &Lo, SDValue &Hi);

+ SDValue WidenVecRes_SIGN_EXTEND_INREG(SDNode* N);

+ E = prior(DAG.allnodes_end()); I != llvm::next(E); ++I)

+ case ISD::SIGN_EXTEND_INREG:

+ case ISD::SIGN_EXTEND_INREG: R = ScalarizeVecRes_SIGN_EXTEND_INREG(N); break;

+SDValue DAGTypeLegalizer::ScalarizeVecRes_SIGN_EXTEND_INREG(SDNode *N) {

+ EVT EltVT = N->getValueType(0).getVectorElementType();

+ SDValue LHS = GetScalarizedVector(N->getOperand(0));

+ return DAG.getNode(ISD::SIGN_EXTEND_INREG, N->getDebugLoc(), EltVT,

+ LHS, N->getOperand(1));

+}

+

+ case ISD::SIGN_EXTEND_INREG: SplitVecRes_SIGN_EXTEND_INREG(N, Lo, Hi); break;

+void DAGTypeLegalizer::SplitVecRes_SIGN_EXTEND_INREG(SDNode *N, SDValue &Lo,

+ SDValue &Hi) {

+ SDValue LHSLo, LHSHi;

+ GetSplitVector(N->getOperand(0), LHSLo, LHSHi);

+ DebugLoc dl = N->getDebugLoc();

+

+ Lo = DAG.getNode(N->getOpcode(), dl, LHSLo.getValueType(), LHSLo,

+ N->getOperand(1));

+ Hi = DAG.getNode(N->getOpcode(), dl, LHSHi.getValueType(), LHSHi,

+ N->getOperand(1));

+}

+

+ case ISD::SIGN_EXTEND_INREG: Res = WidenVecRes_SIGN_EXTEND_INREG(N); break;

+SDValue DAGTypeLegalizer::WidenVecRes_SIGN_EXTEND_INREG(SDNode *N) {

+ EVT WidenVT = TLI.getTypeToTransformTo(*DAG.getContext(), N->getValueType(0));

+ SDValue WidenLHS = GetWidenedVector(N->getOperand(0));

+ return DAG.getNode(ISD::SIGN_EXTEND_INREG, N->getDebugLoc(),

+ WidenVT, WidenLHS, N->getOperand(1));

+}

+

+#include "llvm/Support/CommandLine.h"

+cl::opt<bool>

+DisableInstScheduling("disable-inst-scheduling",

+ cl::init(false),

+ cl::desc("Disable instruction scheduling"));

+

+#include "llvm/Target/TargetFrameInfo.h"

+extern cl::opt<bool> DisableInstScheduling;

+

+

+ // Remove the ordering of this node.

+ if (Ordering) Ordering->remove(N);

+

+ // Remove the ordering of this node.

+ if (Ordering) Ordering->remove(N);

+

+ // Remove the ordering of this node.

+ if (Ordering) Ordering->remove(N);

+ SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);

+ if (Ordering) Ordering->remove(Node);

+ return Node;

+ SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);

+ if (Ordering) Ordering->remove(Node);

+ return Node;

+ SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);

+ if (Ordering) Ordering->remove(Node);

+ return Node;

+ getVTList(MVT::Other)),

+ Root(getEntryNode()), Ordering(0) {

+ if (DisableInstScheduling) {

+ Ordering = new NodeOrdering();

+ Ordering->add(&EntryNode);

+ }

+ delete Ordering;

+ if (DisableInstScheduling) {

+ Ordering = new NodeOrdering();

+ Ordering->add(&EntryNode);

+ }

+ assert(!VT.isVector() &&

+ "getZeroExtendInReg should use the vector element type instead of "

+ "the vector type!");

+ unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();

+ APInt Imm = APInt::getLowBitsSet(BitWidth,

+ if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) {

+ if (Ordering) Ordering->add(N);

+ }

+ if (Ordering) Ordering->add(N);

+ if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) {

+ if (Ordering) Ordering->add(N);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (Ordering) Ordering->add(N);

+ if (Ordering) Ordering->add(N);

+ if (Ordering) Ordering->add(N);

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();

+ assert(BitWidth == Op.getValueType().getScalarType().getSizeInBits() &&

+ unsigned InBits = InVT.getScalarType().getSizeInBits();

+ unsigned InBits = InVT.getScalarType().getSizeInBits();

+ unsigned InBits = InVT.getScalarType().getSizeInBits();

+ unsigned InBits = InVT.getScalarType().getSizeInBits();

+ unsigned VTBits = VT.getScalarType().getSizeInBits();

+ Tmp = VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ assert((!VT.isVector() ||

+ VT.getVectorNumElements() ==

+ Operand.getValueType().getVectorNumElements()) &&

+ "Vector element count mismatch!");

+ assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&

+ "Invalid sext node, dst < src!");

+ assert((!VT.isVector() ||

+ VT.getVectorNumElements() ==

+ Operand.getValueType().getVectorNumElements()) &&

+ "Vector element count mismatch!");

+ assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&

+ "Invalid zext node, dst < src!");

+ assert((!VT.isVector() ||

+ VT.getVectorNumElements() ==

+ Operand.getValueType().getVectorNumElements()) &&

+ "Vector element count mismatch!");

+ assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&

+ "Invalid anyext node, dst < src!");

+ assert((!VT.isVector() ||

+ VT.getVectorNumElements() ==

+ Operand.getValueType().getVectorNumElements()) &&

+ "Vector element count mismatch!");

+ assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&

+ "Invalid truncate node, src < dst!");

+ assert((!VT.isVector() ||

+ VT.getVectorNumElements() ==

+ Operand.getValueType().getVectorNumElements()) &&

+ "Vector element count mismatch!");

+ if (Operand.getNode()->getOperand(0).getValueType().getScalarType()

+ .bitsLT(VT.getScalarType()))

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ assert(!EVT.isVector() &&

+ "AssertSExt/AssertZExt type should be the vector element type "

+ "rather than the vector type!");

+ assert(!EVT.isVector() &&

+ "SIGN_EXTEND_INREG type should be the vector element type rather "

+ "than the vector type!");

+ assert(EVT.bitsLE(VT.getScalarType()) && "Not extending!");

+ unsigned FromBits = EVT.getSizeInBits();

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+

+ if (Ordering) Ordering->add(N);

+ if (Ordering) Ordering->add(E);

+ if (Ordering) Ordering->add(N);

+ if (Ordering) Ordering->add(E);

+ if (Ordering) Ordering->add(N);

+ if (Ordering) Ordering->add(E);

+ if (Ordering) Ordering->add(N);

+ assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&

+ "Should only be an extending load, not truncating!");

+ assert(VT.isVector() == MemVT.isVector() &&

+ "Cannot use trunc store to convert to or from a vector!");

+ assert((!VT.isVector() ||

+ VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&

+ "Cannot use trunc store to change the number of vector elements!");

+ if (Ordering) Ordering->add(E);

+ if (Ordering) Ordering->add(N);

+ if (Ordering) Ordering->add(E);

+ if (Ordering) Ordering->add(N);

+ assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&

+ "Should only be a truncating store, not extending!");

+ assert(VT.isVector() == SVT.isVector() &&

+ "Cannot use trunc store to convert to or from a vector!");

+ assert((!VT.isVector() ||

+ VT.getVectorNumElements() == SVT.getVectorNumElements()) &&

+ "Cannot use trunc store to change the number of vector elements!");

+ if (Ordering) Ordering->add(E);

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ EVT *Array = Allocator.Allocate<EVT>(4);

+ if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(ON);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+ if (Ordering) Ordering->add(N);

+ if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {

+ if (Ordering) Ordering->add(E);

+ }

+

+/// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a

+/// location that is 'Dist' units away from the location that the 'Base' load

+/// is loading from.

+bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,

+ unsigned Bytes, int Dist) const {

+ if (LD->getChain() != Base->getChain())

+ return false;

+ EVT VT = LD->getValueType(0);

+ if (VT.getSizeInBits() / 8 != Bytes)

+ return false;

+

+ SDValue Loc = LD->getOperand(1);

+ SDValue BaseLoc = Base->getOperand(1);

+ if (Loc.getOpcode() == ISD::FrameIndex) {

+ if (BaseLoc.getOpcode() != ISD::FrameIndex)

+ return false;

+ const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();

+ int FI = cast<FrameIndexSDNode>(Loc)->getIndex();

+ int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();

+ int FS = MFI->getObjectSize(FI);

+ int BFS = MFI->getObjectSize(BFI);

+ if (FS != BFS || FS != (int)Bytes) return false;

+ return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);

+ }

+ if (Loc.getOpcode() == ISD::ADD && Loc.getOperand(0) == BaseLoc) {

+ ConstantSDNode *V = dyn_cast<ConstantSDNode>(Loc.getOperand(1));

+ if (V && (V->getSExtValue() == Dist*Bytes))

+ return true;

+ }

+

+ GlobalValue *GV1 = NULL;

+ GlobalValue *GV2 = NULL;

+ int64_t Offset1 = 0;

+ int64_t Offset2 = 0;

+ bool isGA1 = TLI.isGAPlusOffset(Loc.getNode(), GV1, Offset1);

+ bool isGA2 = TLI.isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);

+ if (isGA1 && isGA2 && GV1 == GV2)

+ return Offset1 == (Offset2 + Dist*Bytes);

+ return false;

+}

+

+

+/// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if

+/// it cannot be inferred.

+unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {

+ // If this is a GlobalAddress + cst, return the alignment.

+ GlobalValue *GV;

+ int64_t GVOffset = 0;

+ if (TLI.isGAPlusOffset(Ptr.getNode(), GV, GVOffset))

+ return MinAlign(GV->getAlignment(), GVOffset);

+

+ // If this is a direct reference to a stack slot, use information about the

+ // stack slot's alignment.

+ int FrameIdx = 1 << 31;

+ int64_t FrameOffset = 0;

+ if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {

+ FrameIdx = FI->getIndex();

+ } else if (Ptr.getOpcode() == ISD::ADD &&

+ isa<ConstantSDNode>(Ptr.getOperand(1)) &&

+ isa<FrameIndexSDNode>(Ptr.getOperand(0))) {

+ FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();

+ FrameOffset = Ptr.getConstantOperandVal(1);

+ }

+

+ if (FrameIdx != (1 << 31)) {

+ // FIXME: Handle FI+CST.

+ const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();

+ unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),

+ FrameOffset);

+ if (MFI.isFixedObjectIndex(FrameIdx)) {

+ int64_t ObjectOffset = MFI.getObjectOffset(FrameIdx) + FrameOffset;

+

+ // The alignment of the frame index can be determined from its offset from

+ // the incoming frame position. If the frame object is at offset 32 and

+ // the stack is guaranteed to be 16-byte aligned, then we know that the

+ // object is 16-byte aligned.

+ unsigned StackAlign = getTarget().getFrameInfo()->getStackAlignment();

+ unsigned Align = MinAlign(ObjectOffset, StackAlign);

+

+ // Finally, the frame object itself may have a known alignment. Factor

+ // the alignment + offset into a new alignment. For example, if we know

+ // the FI is 8 byte aligned, but the pointer is 4 off, we really have a

+ // 4-byte alignment of the resultant pointer. Likewise align 4 + 4-byte

+ // offset = 4-byte alignment, align 4 + 1-byte offset = align 1, etc.

+ return std::max(Align, FIInfoAlign);

+ }

+ return FIInfoAlign;

+ }

+

+ return 0;

+}

+

+void SelectionDAG::NodeOrdering::dump() const {

+}

+

+ // Tell the DAG that we're processing a new instruction.

+ DAG.NewInst();

+

+ TrueVal.getNode()->getValueType(i), Cond,

+/// SetDebugLoc - Update MF's and SDB's DebugLocs if debug information is

+/// attached with this instruction.

+static void SetDebugLoc(unsigned MDDbgKind,

+ MetadataContext &TheMetadata,

+ Instruction *I,

+ SelectionDAGBuilder *SDB,

+ FastISel *FastIS,

+ MachineFunction *MF) {

+ if (!isa<DbgInfoIntrinsic>(I))

+ if (MDNode *Dbg = TheMetadata.getMD(MDDbgKind, I)) {

+ DILocation DILoc(Dbg);

+ DebugLoc Loc = ExtractDebugLocation(DILoc, MF->getDebugLocInfo());

+

+ SDB->setCurDebugLoc(Loc);

+

+ if (FastIS)

+ FastIS->setCurDebugLoc(Loc);

+

+ // If the function doesn't have a default debug location yet, set

+ // it. This is kind of a hack.

+ if (MF->getDefaultDebugLoc().isUnknown())

+ MF->setDefaultDebugLoc(Loc);

+ }

+}

+

+/// ResetDebugLoc - Set MF's and SDB's DebugLocs to Unknown.

+static void ResetDebugLoc(SelectionDAGBuilder *SDB,

+ FastISel *FastIS) {

+ SDB->setCurDebugLoc(DebugLoc::getUnknownLoc());

+ if (FastIS)

+ FastIS->setCurDebugLoc(DebugLoc::getUnknownLoc());

+}

+

+ if (MDDbgKind)

+ SetDebugLoc(MDDbgKind, TheMetadata, I, SDB, 0, MF);

+

+ if (!isa<TerminatorInst>(I)) {

+

+ // Set the current debug location back to "unknown" so that it doesn't

+ // spuriously apply to subsequent instructions.

+ ResetDebugLoc(SDB, 0);

+ }

+ SetDebugLoc(MDDbgKind, TheMetadata, LLVMBB->getTerminator(), SDB, 0, MF);

+ ResetDebugLoc(SDB, 0);

+ if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " +

+ BlockName);

+

+ bool Changed;

+ if (TimePassesIsEnabled) {

+ NamedRegionTimer T("Type Legalization", GroupName);

+ Changed = CurDAG->LegalizeTypes();

+ } else {

+ Changed = CurDAG->LegalizeTypes();

+ }

+

+ DEBUG(errs() << "Type-legalized selection DAG:\n");

+ DEBUG(CurDAG->dump());

+ if (Changed) {

+ if (ViewDAGCombineLT)

+ CurDAG->viewGraph("dag-combine-lt input for " + BlockName);

+

+ // Run the DAG combiner in post-type-legalize mode.

+ NamedRegionTimer T("DAG Combining after legalize types", GroupName);

+ CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);

+ CurDAG->Combine(NoIllegalTypes, *AA, OptLevel);

+ DEBUG(errs() << "Optimized type-legalized selection DAG:\n");

+ }

+ if (TimePassesIsEnabled) {

+ NamedRegionTimer T("Vector Legalization", GroupName);

+ Changed = CurDAG->LegalizeVectors();

+ } else {

+ Changed = CurDAG->LegalizeVectors();

+ }

+ if (Changed) {

+ NamedRegionTimer T("Type Legalization 2", GroupName);

+ Changed = CurDAG->LegalizeTypes();

+ Changed = CurDAG->LegalizeTypes();

+ if (ViewDAGCombineLT)

+ CurDAG->viewGraph("dag-combine-lv input for " + BlockName);

+ // Run the DAG combiner in post-type-legalize mode.

+ if (TimePassesIsEnabled) {

+ NamedRegionTimer T("DAG Combining after legalize vectors", GroupName);

+ CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);

+ } else {

+ CurDAG->Combine(NoIllegalOperations, *AA, OptLevel);

+

+ DEBUG(errs() << "Optimized vector-legalized selection DAG:\n");

+ DEBUG(CurDAG->dump());

+ CurDAG->Legalize(OptLevel);

+ CurDAG->Legalize(OptLevel);

+ ResetDebugLoc(SDB, FastIS);

+ if (MDDbgKind)

+ SetDebugLoc(MDDbgKind, TheMetadata, BI, SDB, FastIS, &MF);

+

+ if (FastIS->SelectInstruction(BI)) {

+ ResetDebugLoc(SDB, FastIS);

+ }

+ // Clear out the debug location so that it doesn't carry over to

+ // unrelated instructions.

+ ResetDebugLoc(SDB, FastIS);

+ SelectBasicBlock(LLVMBB, BI, llvm::next(BI), HadTailCall);

+ explicit DOTGraphTraits(bool isSimple=false) :

+ DefaultDOTGraphTraits(isSimple) {}

+ template<typename EdgeIter>

+ static std::string getEdgeSourceLabel(const void *Node, EdgeIter I) {

+ return itostr(I - SDNodeIterator::begin((SDNode *) Node));

+ }

+

+

+

+

+ return DOTGraphTraits<SelectionDAG*>::getSimpleNodeLabel(Node, G);

+ ViewGraph(this, "dag." + getMachineFunction().getFunction()->getNameStr(),

+

+ } else if (strcmp(Color, "yellow") == 0) {

+ assert(Op.getValueType().getScalarType().getSizeInBits() == BitWidth &&

+ InDemandedMask |= APInt::getSignBit(VT.getScalarType().getSizeInBits());

+ // sbbl $3,$0>, 10, %EAX<def>, 14, %ECX<earlyclobber,def>, 9,

+ // %EAX<kill>,

+/// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with

+/// IntA being the source and IntB being the dest, thus this defines a value

+/// number in IntB. If the source value number (in IntA) is defined by a

+/// commutable instruction and its other operand is coalesced to the copy dest

+/// register, see if we can transform the copy into a noop by commuting the

+/// definition. For example,

+ SRLI.MergeInClobberRange(*li_, AI->start, End,

+ li_->getVNInfoAllocator());

+ MachineBasicBlock::iterator MII =

+ llvm::next(MachineBasicBlock::iterator(CopyMI));

+ } else if (tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) {

+ if (SrcSubIdx && DstSubIdx && SrcSubIdx != DstSubIdx) {

+ // e.g. %reg16404:1<def> = MOV8rr %reg16412:2<kill>

+ Again = true;

+ return false; // Not coalescable.

+ }

+ } else {

+ // If the virtual register live interval is long but it has low use

+ // density, do not join them, instead mark the physical register as its

+ // allocation preference.

+ // If it's re-defined by an early clobber somewhere in the live range,

+ // then conservatively abort coalescing.

+ if (LHSIt->valno->hasRedefByEC())

+ return false;

+ // If it's re-defined by an early clobber somewhere in the live range,

+ // then conservatively abort coalescing.

+ if (LHSIt->valno->hasRedefByEC())

+ return false;

+ // If it's re-defined by an early clobber somewhere in the live range,

+ // then conservatively abort coalescing.

+ if (NewVNInfo[LHSValNoAssignments[I->valno->id]]->hasRedefByEC())

+ return false;

+ bool isInsUndef = false;

+ } else if (Inst->getOpcode() == TargetInstrInfo::INSERT_SUBREG) {

+ DstReg = Inst->getOperand(0).getReg();

+ SrcReg = Inst->getOperand(2).getReg();

+ if (Inst->getOperand(1).isUndef())

+ isInsUndef = true;

+ if (isInsUndef ||

+ (li_->hasInterval(SrcReg) && li_->getInterval(SrcReg).empty()))

+ // Try coalescing implicit copies and insert_subreg <undef> first,

+ // followed by copies to / from physical registers, then finally copies

+ // from virtual registers to virtual registers.

+ for (LiveIntervals::iterator I = li_->begin(), E = li_->end();

+ I != E; ++I){

+ mii = llvm::next(mii);

+#include <set>

+ enum SpillerName { trivial, standard, splitting };

+ cl::values(clEnumVal(trivial, "trivial spiller"),

+ clEnumVal(standard, "default spiller"),

+ clEnumVal(splitting, "splitting spiller"),

+// Spiller virtual destructor implementation.

+ tii->storeRegToStackSlot(*mi->getParent(), llvm::next(miItr), newVReg, true,

+ MachineInstr *storeInstr(llvm::next(miItr));

+ SmallVectorImpl<LiveInterval*> &spillIs,

+ SlotIndex*) {

+protected:

+ StandardSpiller(LiveIntervals *lis, const MachineLoopInfo *loopInfo,

+ VirtRegMap *vrm)

+ SmallVectorImpl<LiveInterval*> &spillIs,

+ SlotIndex*) {

+/// When a call to spill is placed this spiller will first try to break the

+/// interval up into its component values (one new interval per value).

+/// If this fails, or if a call is placed to spill a previously split interval

+/// then the spiller falls back on the standard spilling mechanism.

+class SplittingSpiller : public StandardSpiller {

+public:

+ SplittingSpiller(MachineFunction *mf, LiveIntervals *lis,

+ const MachineLoopInfo *loopInfo, VirtRegMap *vrm)

+ : StandardSpiller(lis, loopInfo, vrm) {

+

+ mri = &mf->getRegInfo();

+ tii = mf->getTarget().getInstrInfo();

+ tri = mf->getTarget().getRegisterInfo();

+ }

+

+ std::vector<LiveInterval*> spill(LiveInterval *li,

+ SmallVectorImpl<LiveInterval*> &spillIs,

+ SlotIndex *earliestStart) {

+

+ if (worthTryingToSplit(li)) {

+ return tryVNISplit(li, earliestStart);

+ }

+ // else

+ return StandardSpiller::spill(li, spillIs, earliestStart);

+ }

+

+private:

+

+ MachineRegisterInfo *mri;

+ const TargetInstrInfo *tii;

+ const TargetRegisterInfo *tri;

+ DenseSet<LiveInterval*> alreadySplit;

+

+ bool worthTryingToSplit(LiveInterval *li) const {

+ return (!alreadySplit.count(li) && li->getNumValNums() > 1);

+ }

+

+ /// Try to break a LiveInterval into its component values.

+ std::vector<LiveInterval*> tryVNISplit(LiveInterval *li,

+ SlotIndex *earliestStart) {

+

+ DEBUG(errs() << "Trying VNI split of %reg" << *li << "\n");

+

+ std::vector<LiveInterval*> added;

+ SmallVector<VNInfo*, 4> vnis;

+

+ std::copy(li->vni_begin(), li->vni_end(), std::back_inserter(vnis));

+

+ for (SmallVectorImpl<VNInfo*>::iterator vniItr = vnis.begin(),

+ vniEnd = vnis.end(); vniItr != vniEnd; ++vniItr) {

+ VNInfo *vni = *vniItr;

+

+ // Skip unused VNIs, or VNIs with no kills.

+ if (vni->isUnused() || vni->kills.empty())

+ continue;

+

+ DEBUG(errs() << " Extracted Val #" << vni->id << " as ");

+ LiveInterval *splitInterval = extractVNI(li, vni);

+

+ if (splitInterval != 0) {

+ DEBUG(errs() << *splitInterval << "\n");

+ added.push_back(splitInterval);

+ alreadySplit.insert(splitInterval);

+ if (earliestStart != 0) {

+ if (splitInterval->beginIndex() < *earliestStart)

+ *earliestStart = splitInterval->beginIndex();

+ }

+ } else {

+ DEBUG(errs() << "0\n");

+ }

+ }

+

+ DEBUG(errs() << "Original LI: " << *li << "\n");

+

+ // If there original interval still contains some live ranges

+ // add it to added and alreadySplit.

+ if (!li->empty()) {

+ added.push_back(li);

+ alreadySplit.insert(li);

+ if (earliestStart != 0) {

+ if (li->beginIndex() < *earliestStart)

+ *earliestStart = li->beginIndex();

+ }

+ }

+

+ return added;

+ }

+

+ /// Extract the given value number from the interval.

+ LiveInterval* extractVNI(LiveInterval *li, VNInfo *vni) const {

+ assert(vni->isDefAccurate() || vni->isPHIDef());

+ assert(!vni->kills.empty());

+

+ // Create a new vreg and live interval, copy VNI kills & ranges over.

+ const TargetRegisterClass *trc = mri->getRegClass(li->reg);

+ unsigned newVReg = mri->createVirtualRegister(trc);

+ vrm->grow();

+ LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);

+ VNInfo *newVNI = newLI->createValueCopy(vni, lis->getVNInfoAllocator());

+

+ // Start by copying all live ranges in the VN to the new interval.

+ for (LiveInterval::iterator rItr = li->begin(), rEnd = li->end();

+ rItr != rEnd; ++rItr) {

+ if (rItr->valno == vni) {

+ newLI->addRange(LiveRange(rItr->start, rItr->end, newVNI));

+ }

+ }

+

+ // Erase the old VNI & ranges.

+ li->removeValNo(vni);

+

+ // Collect all current uses of the register belonging to the given VNI.

+ // We'll use this to rename the register after we've dealt with the def.

+ std::set<MachineInstr*> uses;

+ for (MachineRegisterInfo::use_iterator

+ useItr = mri->use_begin(li->reg), useEnd = mri->use_end();

+ useItr != useEnd; ++useItr) {

+ uses.insert(&*useItr);

+ }

+

+ // Process the def instruction for this VNI.

+ if (newVNI->isPHIDef()) {

+ // Insert a copy at the start of the MBB. The range proceeding the

+ // copy will be attached to the original LiveInterval.

+ MachineBasicBlock *defMBB = lis->getMBBFromIndex(newVNI->def);

+ tii->copyRegToReg(*defMBB, defMBB->begin(), newVReg, li->reg, trc, trc);

+ MachineInstr *copyMI = defMBB->begin();

+ copyMI->addRegisterKilled(li->reg, tri);

+ SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);

+ VNInfo *phiDefVNI = li->getNextValue(lis->getMBBStartIdx(defMBB),

+ 0, false, lis->getVNInfoAllocator());

+ phiDefVNI->setIsPHIDef(true);

+ phiDefVNI->addKill(copyIdx.getDefIndex());

+ li->addRange(LiveRange(phiDefVNI->def, copyIdx.getDefIndex(), phiDefVNI));

+ LiveRange *oldPHIDefRange =

+ newLI->getLiveRangeContaining(lis->getMBBStartIdx(defMBB));

+

+ // If the old phi def starts in the middle of the range chop it up.

+ if (oldPHIDefRange->start < lis->getMBBStartIdx(defMBB)) {

+ LiveRange oldPHIDefRange2(copyIdx.getDefIndex(), oldPHIDefRange->end,

+ oldPHIDefRange->valno);

+ oldPHIDefRange->end = lis->getMBBStartIdx(defMBB);

+ newLI->addRange(oldPHIDefRange2);

+ } else if (oldPHIDefRange->start == lis->getMBBStartIdx(defMBB)) {

+ // Otherwise if it's at the start of the range just trim it.

+ oldPHIDefRange->start = copyIdx.getDefIndex();

+ } else {

+ assert(false && "PHI def range doesn't cover PHI def?");

+ }

+

+ newVNI->def = copyIdx.getDefIndex();

+ newVNI->setCopy(copyMI);

+ newVNI->setIsPHIDef(false); // not a PHI def anymore.

+ newVNI->setIsDefAccurate(true);

+ } else {

+ // non-PHI def. Rename the def. If it's two-addr that means renaming the use

+ // and inserting a new copy too.

+ MachineInstr *defInst = lis->getInstructionFromIndex(newVNI->def);

+ // We'll rename this now, so we can remove it from uses.

+ uses.erase(defInst);

+ unsigned defOpIdx = defInst->findRegisterDefOperandIdx(li->reg);

+ bool isTwoAddr = defInst->isRegTiedToUseOperand(defOpIdx),

+ twoAddrUseIsUndef = false;

+

+ for (unsigned i = 0; i < defInst->getNumOperands(); ++i) {

+ MachineOperand &mo = defInst->getOperand(i);

+ if (mo.isReg() && (mo.isDef() || isTwoAddr) && (mo.getReg()==li->reg)) {

+ mo.setReg(newVReg);

+ if (isTwoAddr && mo.isUse() && mo.isUndef())

+ twoAddrUseIsUndef = true;

+ }

+ }

+

+ SlotIndex defIdx = lis->getInstructionIndex(defInst);

+ newVNI->def = defIdx.getDefIndex();

+

+ if (isTwoAddr && !twoAddrUseIsUndef) {

+ MachineBasicBlock *defMBB = defInst->getParent();

+ tii->copyRegToReg(*defMBB, defInst, newVReg, li->reg, trc, trc);

+ MachineInstr *copyMI = prior(MachineBasicBlock::iterator(defInst));

+ SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);

+ copyMI->addRegisterKilled(li->reg, tri);

+ LiveRange *origUseRange =

+ li->getLiveRangeContaining(newVNI->def.getUseIndex());

+ VNInfo *origUseVNI = origUseRange->valno;

+ origUseRange->end = copyIdx.getDefIndex();

+ bool updatedKills = false;

+ for (unsigned k = 0; k < origUseVNI->kills.size(); ++k) {

+ if (origUseVNI->kills[k] == defIdx.getDefIndex()) {

+ origUseVNI->kills[k] = copyIdx.getDefIndex();

+ updatedKills = true;

+ break;

+ }

+ }

+ assert(updatedKills && "Failed to update VNI kill list.");

+ VNInfo *copyVNI = newLI->getNextValue(copyIdx.getDefIndex(), copyMI,

+ true, lis->getVNInfoAllocator());

+ copyVNI->addKill(defIdx.getDefIndex());

+ LiveRange copyRange(copyIdx.getDefIndex(),defIdx.getDefIndex(),copyVNI);

+ newLI->addRange(copyRange);

+ }

+ }

+

+ for (std::set<MachineInstr*>::iterator

+ usesItr = uses.begin(), usesEnd = uses.end();

+ usesItr != usesEnd; ++usesItr) {

+ MachineInstr *useInst = *usesItr;

+ SlotIndex useIdx = lis->getInstructionIndex(useInst);

+ LiveRange *useRange =

+ newLI->getLiveRangeContaining(useIdx.getUseIndex());

+

+ // If this use doesn't belong to the new interval skip it.

+ if (useRange == 0)

+ continue;

+

+ // This use doesn't belong to the VNI, skip it.

+ if (useRange->valno != newVNI)

+ continue;

+

+ // Check if this instr is two address.

+ unsigned useOpIdx = useInst->findRegisterUseOperandIdx(li->reg);

+ bool isTwoAddress = useInst->isRegTiedToDefOperand(useOpIdx);

+

+ // Rename uses (and defs for two-address instrs).

+ for (unsigned i = 0; i < useInst->getNumOperands(); ++i) {

+ MachineOperand &mo = useInst->getOperand(i);

+ if (mo.isReg() && (mo.isUse() || isTwoAddress) &&

+ (mo.getReg() == li->reg)) {

+ mo.setReg(newVReg);

+ }

+ }

+

+ // If this is a two address instruction we've got some extra work to do.

+ if (isTwoAddress) {

+ // We modified the def operand, so we need to copy back to the original

+ // reg.

+ MachineBasicBlock *useMBB = useInst->getParent();

+ MachineBasicBlock::iterator useItr(useInst);

+ tii->copyRegToReg(*useMBB, next(useItr), li->reg, newVReg, trc, trc);

+ MachineInstr *copyMI = next(useItr);

+ copyMI->addRegisterKilled(newVReg, tri);

+ SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);

+

+ // Change the old two-address defined range & vni to start at

+ // (and be defined by) the copy.

+ LiveRange *origDefRange =

+ li->getLiveRangeContaining(useIdx.getDefIndex());

+ origDefRange->start = copyIdx.getDefIndex();

+ origDefRange->valno->def = copyIdx.getDefIndex();

+ origDefRange->valno->setCopy(copyMI);

+

+ // Insert a new range & vni for the two-address-to-copy value. This

+ // will be attached to the new live interval.

+ VNInfo *copyVNI =

+ newLI->getNextValue(useIdx.getDefIndex(), 0, true,

+ lis->getVNInfoAllocator());

+ copyVNI->addKill(copyIdx.getDefIndex());

+ LiveRange copyRange(useIdx.getDefIndex(),copyIdx.getDefIndex(),copyVNI);

+ newLI->addRange(copyRange);

+ }

+ }

+

+ // Iterate over any PHI kills - we'll need to insert new copies for them.

+ for (VNInfo::KillSet::iterator

+ killItr = newVNI->kills.begin(), killEnd = newVNI->kills.end();

+ killItr != killEnd; ++killItr) {

+ SlotIndex killIdx(*killItr);

+ if (killItr->isPHI()) {

+ MachineBasicBlock *killMBB = lis->getMBBFromIndex(killIdx);

+ LiveRange *oldKillRange =

+ newLI->getLiveRangeContaining(killIdx);

+

+ assert(oldKillRange != 0 && "No kill range?");

+

+ tii->copyRegToReg(*killMBB, killMBB->getFirstTerminator(),

+ li->reg, newVReg, trc, trc);

+ MachineInstr *copyMI = prior(killMBB->getFirstTerminator());

+ copyMI->addRegisterKilled(newVReg, tri);

+ SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);

+

+ // Save the current end. We may need it to add a new range if the

+ // current range runs of the end of the MBB.

+ SlotIndex newKillRangeEnd = oldKillRange->end;

+ oldKillRange->end = copyIdx.getDefIndex();

+

+ if (newKillRangeEnd != lis->getMBBEndIdx(killMBB).getNextSlot()) {

+ assert(newKillRangeEnd > lis->getMBBEndIdx(killMBB).getNextSlot() &&

+ "PHI kill range doesn't reach kill-block end. Not sane.");

+ newLI->addRange(LiveRange(lis->getMBBEndIdx(killMBB).getNextSlot(),

+ newKillRangeEnd, newVNI));

+ }

+

+ *killItr = oldKillRange->end;

+ VNInfo *newKillVNI = li->getNextValue(copyIdx.getDefIndex(),

+ copyMI, true,

+ lis->getVNInfoAllocator());

+ newKillVNI->addKill(lis->getMBBTerminatorGap(killMBB));

+ newKillVNI->setHasPHIKill(true);

+ li->addRange(LiveRange(copyIdx.getDefIndex(),

+ lis->getMBBEndIdx(killMBB).getNextSlot(),

+ newKillVNI));

+ }

+

+ }

+

+ newVNI->setHasPHIKill(false);

+

+ return newLI;

+ }

+

+};

+

+ case standard: return new StandardSpiller(lis, loopInfo, vrm); break;

+ case splitting: return new SplittingSpiller(mf, lis, loopInfo, vrm); break;

+ class SlotIndex;

+ SmallVectorImpl<LiveInterval*> &spillIs,

+ SlotIndex *earliestIndex = 0) = 0;

+ MachineBasicBlock::iterator NextMI = llvm::next(I);

+#include "llvm/CodeGen/MachineRegisterInfo.h"

+#include "llvm/CodeGen/MachineSSAUpdater.h"

+#include "llvm/Support/ErrorHandling.h"

+STATISTIC(NumTails , "Number of tails duplicated");

+static cl::opt<bool>

+TailDupVerify("tail-dup-verify",

+ cl::desc("Verify sanity of PHI instructions during taildup"),

+ cl::init(false), cl::Hidden);

+

+static cl::opt<unsigned>

+TailDupLimit("tail-dup-limit", cl::init(~0U), cl::Hidden);

+

+typedef std::vector<std::pair<MachineBasicBlock*,unsigned> > AvailableValsTy;

+

+ bool PreRegAlloc;

+ MachineRegisterInfo *MRI;

+

+ // SSAUpdateVRs - A list of virtual registers for which to update SSA form.

+ SmallVector<unsigned, 16> SSAUpdateVRs;

+

+ // SSAUpdateVals - For each virtual register in SSAUpdateVals keep a list of

+ // source virtual registers.

+ DenseMap<unsigned, AvailableValsTy> SSAUpdateVals;

+ explicit TailDuplicatePass(bool PreRA) :

+ MachineFunctionPass(&ID), PreRegAlloc(PreRA) {}

+ void AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,

+ MachineBasicBlock *BB);

+ void ProcessPHI(MachineInstr *MI, MachineBasicBlock *TailBB,

+ MachineBasicBlock *PredBB,

+ DenseMap<unsigned, unsigned> &LocalVRMap,

+ SmallVector<std::pair<unsigned,unsigned>, 4> &Copies);

+ void DuplicateInstruction(MachineInstr *MI,

+ MachineBasicBlock *TailBB,

+ MachineBasicBlock *PredBB,

+ MachineFunction &MF,

+ DenseMap<unsigned, unsigned> &LocalVRMap);

+ void UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,

+ SmallVector<MachineBasicBlock*, 8> &TDBBs,

+ SmallSetVector<MachineBasicBlock*, 8> &Succs);

+ bool TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF,

+ SmallVector<MachineBasicBlock*, 8> &TDBBs,

+ SmallVector<MachineInstr*, 16> &Copies);

+FunctionPass *llvm::createTailDuplicatePass(bool PreRegAlloc) {

+ return new TailDuplicatePass(PreRegAlloc);

+ MRI = &MF.getRegInfo();

+static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) {

+ for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ++I) {

+ MachineBasicBlock *MBB = I;

+ SmallSetVector<MachineBasicBlock*, 8> Preds(MBB->pred_begin(),

+ MBB->pred_end());

+ MachineBasicBlock::iterator MI = MBB->begin();

+ while (MI != MBB->end()) {

+ if (MI->getOpcode() != TargetInstrInfo::PHI)

+ break;

+ for (SmallSetVector<MachineBasicBlock *, 8>::iterator PI = Preds.begin(),

+ PE = Preds.end(); PI != PE; ++PI) {

+ MachineBasicBlock *PredBB = *PI;

+ bool Found = false;

+ for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {

+ MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB();

+ if (PHIBB == PredBB) {

+ Found = true;

+ break;

+ }

+ }

+ if (!Found) {

+ errs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI;

+ errs() << " missing input from predecessor BB#"

+ << PredBB->getNumber() << '\n';

+ llvm_unreachable(0);

+ }

+ }

+

+ for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {

+ MachineBasicBlock *PHIBB = MI->getOperand(i+1).getMBB();

+ if (CheckExtra && !Preds.count(PHIBB)) {

+ // This is not a hard error.

+ errs() << "Warning: malformed PHI in BB#" << MBB->getNumber()

+ << ": " << *MI;

+ errs() << " extra input from predecessor BB#"

+ << PHIBB->getNumber() << '\n';

+ }

+ if (PHIBB->getNumber() < 0) {

+ errs() << "Malformed PHI in BB#" << MBB->getNumber() << ": " << *MI;

+ errs() << " non-existing BB#" << PHIBB->getNumber() << '\n';

+ llvm_unreachable(0);

+ }

+ }

+ ++MI;

+ }

+ }

+}

+

+ if (PreRegAlloc && TailDupVerify) {

+ DEBUG(errs() << "\n*** Before tail-duplicating\n");

+ VerifyPHIs(MF, true);

+ }

+

+ SmallVector<MachineInstr*, 8> NewPHIs;

+ MachineSSAUpdater SSAUpdate(MF, &NewPHIs);

+

+ if (NumTails == TailDupLimit)

+ break;

+

+ // Save the successors list.

+ SmallSetVector<MachineBasicBlock*, 8> Succs(MBB->succ_begin(),

+ MBB->succ_end());

+

+ SmallVector<MachineBasicBlock*, 8> TDBBs;

+ SmallVector<MachineInstr*, 16> Copies;

+ if (TailDuplicate(MBB, MF, TDBBs, Copies)) {

+ ++NumTails;

+

+ // TailBB's immediate successors are now successors of those predecessors

+ // which duplicated TailBB. Add the predecessors as sources to the PHI

+ // instructions.

+ bool isDead = MBB->pred_empty();

+ if (PreRegAlloc)

+ UpdateSuccessorsPHIs(MBB, isDead, TDBBs, Succs);

+

+ // If it is dead, remove it.

+ if (isDead) {

+ NumInstrDups -= MBB->size();

+ RemoveDeadBlock(MBB);

+ ++NumDeadBlocks;

+ }

+

+ // Update SSA form.

+ if (!SSAUpdateVRs.empty()) {

+ for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) {

+ unsigned VReg = SSAUpdateVRs[i];

+ SSAUpdate.Initialize(VReg);

+

+ // If the original definition is still around, add it as an available

+ // value.

+ MachineInstr *DefMI = MRI->getVRegDef(VReg);

+ MachineBasicBlock *DefBB = 0;

+ if (DefMI) {

+ DefBB = DefMI->getParent();

+ SSAUpdate.AddAvailableValue(DefBB, VReg);

+ }

+

+ // Add the new vregs as available values.

+ DenseMap<unsigned, AvailableValsTy>::iterator LI =

+ SSAUpdateVals.find(VReg);

+ for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {

+ MachineBasicBlock *SrcBB = LI->second[j].first;

+ unsigned SrcReg = LI->second[j].second;

+ SSAUpdate.AddAvailableValue(SrcBB, SrcReg);

+ }

+

+ // Rewrite uses that are outside of the original def's block.

+ MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg);

+ while (UI != MRI->use_end()) {

+ MachineOperand &UseMO = UI.getOperand();

+ MachineInstr *UseMI = &*UI;

+ ++UI;

+ if (UseMI->getParent() == DefBB)

+ continue;

+ SSAUpdate.RewriteUse(UseMO);

+ }

+ }

+

+ SSAUpdateVRs.clear();

+ SSAUpdateVals.clear();

+ }

+

+ // Eliminate some of the copies inserted tail duplication to maintain

+ // SSA form.

+ for (unsigned i = 0, e = Copies.size(); i != e; ++i) {

+ MachineInstr *Copy = Copies[i];

+ unsigned Src, Dst, SrcSR, DstSR;

+ if (TII->isMoveInstr(*Copy, Src, Dst, SrcSR, DstSR)) {

+ MachineRegisterInfo::use_iterator UI = MRI->use_begin(Src);

+ if (++UI == MRI->use_end()) {

+ // Copy is the only use. Do trivial copy propagation here.

+ MRI->replaceRegWith(Dst, Src);

+ Copy->eraseFromParent();

+ }

+ }

+ }

+

+ if (PreRegAlloc && TailDupVerify)

+ VerifyPHIs(MF, false);

+

+static bool isDefLiveOut(unsigned Reg, MachineBasicBlock *BB,

+ const MachineRegisterInfo *MRI) {

+ for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),

+ UE = MRI->use_end(); UI != UE; ++UI) {

+ MachineInstr *UseMI = &*UI;

+ if (UseMI->getParent() != BB)

+ return true;

+ }

+ return false;

+}

+

+static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) {

+ for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2)

+ if (MI->getOperand(i+1).getMBB() == SrcBB)

+ return i;

+ return 0;

+}

+

+/// AddSSAUpdateEntry - Add a definition and source virtual registers pair for

+/// SSA update.

+void TailDuplicatePass::AddSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,

+ MachineBasicBlock *BB) {

+ DenseMap<unsigned, AvailableValsTy>::iterator LI= SSAUpdateVals.find(OrigReg);

+ if (LI != SSAUpdateVals.end())

+ LI->second.push_back(std::make_pair(BB, NewReg));

+ else {

+ AvailableValsTy Vals;

+ Vals.push_back(std::make_pair(BB, NewReg));

+ SSAUpdateVals.insert(std::make_pair(OrigReg, Vals));

+ SSAUpdateVRs.push_back(OrigReg);

+ }

+}

+

+/// ProcessPHI - Process PHI node in TailBB by turning it into a copy in PredBB.

+/// Remember the source register that's contributed by PredBB and update SSA

+/// update map.

+void TailDuplicatePass::ProcessPHI(MachineInstr *MI,

+ MachineBasicBlock *TailBB,

+ MachineBasicBlock *PredBB,

+ DenseMap<unsigned, unsigned> &LocalVRMap,

+ SmallVector<std::pair<unsigned,unsigned>, 4> &Copies) {

+ unsigned DefReg = MI->getOperand(0).getReg();

+ unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, PredBB);

+ assert(SrcOpIdx && "Unable to find matching PHI source?");

+ unsigned SrcReg = MI->getOperand(SrcOpIdx).getReg();

+ const TargetRegisterClass *RC = MRI->getRegClass(DefReg);

+ LocalVRMap.insert(std::make_pair(DefReg, SrcReg));

+

+ // Insert a copy from source to the end of the block. The def register is the

+ // available value liveout of the block.

+ unsigned NewDef = MRI->createVirtualRegister(RC);

+ Copies.push_back(std::make_pair(NewDef, SrcReg));

+ if (isDefLiveOut(DefReg, TailBB, MRI))

+ AddSSAUpdateEntry(DefReg, NewDef, PredBB);

+

+ // Remove PredBB from the PHI node.

+ MI->RemoveOperand(SrcOpIdx+1);

+ MI->RemoveOperand(SrcOpIdx);

+ if (MI->getNumOperands() == 1)

+ MI->eraseFromParent();

+}

+

+/// DuplicateInstruction - Duplicate a TailBB instruction to PredBB and update

+/// the source operands due to earlier PHI translation.

+void TailDuplicatePass::DuplicateInstruction(MachineInstr *MI,

+ MachineBasicBlock *TailBB,

+ MachineBasicBlock *PredBB,

+ MachineFunction &MF,

+ DenseMap<unsigned, unsigned> &LocalVRMap) {

+ MachineInstr *NewMI = MF.CloneMachineInstr(MI);

+ for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {

+ MachineOperand &MO = NewMI->getOperand(i);

+ if (!MO.isReg())

+ continue;

+ unsigned Reg = MO.getReg();

+ if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg))

+ continue;

+ if (MO.isDef()) {

+ const TargetRegisterClass *RC = MRI->getRegClass(Reg);

+ unsigned NewReg = MRI->createVirtualRegister(RC);

+ MO.setReg(NewReg);

+ LocalVRMap.insert(std::make_pair(Reg, NewReg));

+ if (isDefLiveOut(Reg, TailBB, MRI))

+ AddSSAUpdateEntry(Reg, NewReg, PredBB);

+ } else {

+ DenseMap<unsigned, unsigned>::iterator VI = LocalVRMap.find(Reg);

+ if (VI != LocalVRMap.end())

+ MO.setReg(VI->second);

+ }

+ }

+ PredBB->insert(PredBB->end(), NewMI);

+}

+

+/// UpdateSuccessorsPHIs - After FromBB is tail duplicated into its predecessor

+/// blocks, the successors have gained new predecessors. Update the PHI

+/// instructions in them accordingly.

+void

+TailDuplicatePass::UpdateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,

+ SmallVector<MachineBasicBlock*, 8> &TDBBs,

+ SmallSetVector<MachineBasicBlock*,8> &Succs) {

+ for (SmallSetVector<MachineBasicBlock*, 8>::iterator SI = Succs.begin(),

+ SE = Succs.end(); SI != SE; ++SI) {

+ MachineBasicBlock *SuccBB = *SI;

+ for (MachineBasicBlock::iterator II = SuccBB->begin(), EE = SuccBB->end();

+ II != EE; ++II) {

+ if (II->getOpcode() != TargetInstrInfo::PHI)

+ break;

+ unsigned Idx = 0;

+ for (unsigned i = 1, e = II->getNumOperands(); i != e; i += 2) {

+ MachineOperand &MO = II->getOperand(i+1);

+ if (MO.getMBB() == FromBB) {

+ Idx = i;

+ break;

+ }

+ }

+

+ assert(Idx != 0);

+ MachineOperand &MO0 = II->getOperand(Idx);

+ unsigned Reg = MO0.getReg();

+ if (isDead) {

+ // Folded into the previous BB.

+ // There could be duplicate phi source entries. FIXME: Should sdisel

+ // or earlier pass fixed this?

+ for (unsigned i = II->getNumOperands()-2; i != Idx; i -= 2) {

+ MachineOperand &MO = II->getOperand(i+1);

+ if (MO.getMBB() == FromBB) {

+ II->RemoveOperand(i+1);

+ II->RemoveOperand(i);

+ }

+ }

+ II->RemoveOperand(Idx+1);

+ II->RemoveOperand(Idx);

+ }

+ DenseMap<unsigned,AvailableValsTy>::iterator LI=SSAUpdateVals.find(Reg);

+ if (LI != SSAUpdateVals.end()) {

+ // This register is defined in the tail block.

+ for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {

+ MachineBasicBlock *SrcBB = LI->second[j].first;

+ unsigned SrcReg = LI->second[j].second;

+ II->addOperand(MachineOperand::CreateReg(SrcReg, false));

+ II->addOperand(MachineOperand::CreateMBB(SrcBB));

+ }

+ } else {

+ // Live in tail block, must also be live in predecessors.

+ for (unsigned j = 0, ee = TDBBs.size(); j != ee; ++j) {

+ MachineBasicBlock *SrcBB = TDBBs[j];

+ II->addOperand(MachineOperand::CreateReg(Reg, false));

+ II->addOperand(MachineOperand::CreateMBB(SrcBB));

+ }

+ }

+ }

+ }

+}

+

+bool

+TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB, MachineFunction &MF,

+ SmallVector<MachineBasicBlock*, 8> &TDBBs,

+ SmallVector<MachineInstr*, 16> &Copies) {

+ unsigned InstrCount = 0;

+ I != TailBB->end(); ++I) {

+ // Do not duplicate 'return' instructions if this is a pre-regalloc run.

+ // A return may expand into a lot more instructions (e.g. reload of callee

+ // saved registers) after PEI.

+ if (PreRegAlloc && I->getDesc().isReturn()) return false;

+ if (InstrCount == MaxDuplicateCount) return false;

+ if (I->getOpcode() != TargetInstrInfo::PHI)

+ InstrCount += 1;

+ if (InstrCount > 1 && HasCall)

+ DEBUG(errs() << "\n*** Tail-duplicating BB#" << TailBB->getNumber() << '\n');

+

+ SmallSetVector<MachineBasicBlock*, 8> Preds(TailBB->pred_begin(),

+ TailBB->pred_end());

+ TDBBs.push_back(PredBB);

+

+

+ DenseMap<unsigned, unsigned> LocalVRMap;

+ SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos;

+ MachineBasicBlock::iterator I = TailBB->begin();

+ while (I != TailBB->end()) {

+ MachineInstr *MI = &*I;

+ ++I;

+ if (MI->getOpcode() == TargetInstrInfo::PHI) {

+ // Replace the uses of the def of the PHI with the register coming

+ // from PredBB.

+ ProcessPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos);

+ } else {

+ // Replace def of virtual registers with new registers, and update

+ // uses with PHI source register or the new registers.

+ DuplicateInstruction(MI, TailBB, PredBB, MF, LocalVRMap);

+ }

+ }

+ MachineBasicBlock::iterator Loc = PredBB->getFirstTerminator();

+ for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) {

+ const TargetRegisterClass *RC = MRI->getRegClass(CopyInfos[i].first);

+ TII->copyRegToReg(*PredBB, Loc, CopyInfos[i].first,

+ CopyInfos[i].second, RC,RC);

+ MachineInstr *CopyMI = prior(Loc);

+ Copies.push_back(CopyMI);

+ E = TailBB->succ_end(); I != E; ++I)

+ PredBB->addSuccessor(*I);

+ MachineBasicBlock *PrevBB = prior(MachineFunction::iterator(TailBB));

+ TII->AnalyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond, true);

+ TailBB->pred_size() == 1 && PrevBB->succ_size() == 1 &&

+ DEBUG(errs() << "\nMerging into block: " << *PrevBB

+ if (PreRegAlloc) {

+ DenseMap<unsigned, unsigned> LocalVRMap;

+ SmallVector<std::pair<unsigned,unsigned>, 4> CopyInfos;

+ MachineBasicBlock::iterator I = TailBB->begin();

+ // Process PHI instructions first.

+ while (I != TailBB->end() && I->getOpcode() == TargetInstrInfo::PHI) {

+ // Replace the uses of the def of the PHI with the register coming

+ // from PredBB.

+ MachineInstr *MI = &*I++;

+ ProcessPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos);

+ if (MI->getParent())

+ MI->eraseFromParent();

+ }

+

+ // Now copy the non-PHI instructions.

+ while (I != TailBB->end()) {

+ // Replace def of virtual registers with new registers, and update

+ // uses with PHI source register or the new registers.

+ MachineInstr *MI = &*I++;

+ DuplicateInstruction(MI, TailBB, PrevBB, MF, LocalVRMap);

+ MI->eraseFromParent();

+ }

+ MachineBasicBlock::iterator Loc = PrevBB->getFirstTerminator();

+ for (unsigned i = 0, e = CopyInfos.size(); i != e; ++i) {

+ const TargetRegisterClass *RC = MRI->getRegClass(CopyInfos[i].first);

+ TII->copyRegToReg(*PrevBB, Loc, CopyInfos[i].first,

+ CopyInfos[i].second, RC, RC);

+ MachineInstr *CopyMI = prior(Loc);

+ Copies.push_back(CopyMI);

+ }

+ } else {

+ // No PHIs to worry about, just splice the instructions over.

+ PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());

+ }

+ PrevBB->removeSuccessor(PrevBB->succ_begin());

+ assert(PrevBB->succ_empty());

+ PrevBB->transferSuccessors(TailBB);

+ TDBBs.push_back(PrevBB);

+ if (MO.isDef() && (llvm::next(MRI.def_begin(Reg)) != MRI.def_end() ||

+ for (MachineBasicBlock::iterator I = llvm::next(OldPos); I != KillPos; ++I) {

+ if (llvm::next(Begin) != MRI->def_end())

+ nmi = llvm::next(mi);

+ MachineBasicBlock::iterator nmi = llvm::next(mi);

+ std::multimap<unsigned, int>::iterator NI = llvm::next(I);

+ MachineBasicBlock::iterator NextMII = llvm::next(MII);

+ NextMII = llvm::next(NextMII);

+ MachineBasicBlock::iterator oldNextMII = llvm::next(MII);

+ TII->storeRegToStackSlot(MBB, llvm::next(MII), PhysReg, true, StackSlot, RC);

+ MachineBasicBlock::iterator NextMII = llvm::next(MII);

+ NextMII = llvm::next(MII);

+ ComputeReloadLoc(llvm::next(MII), MBB.begin(), PhysReg, TRI, false,

+ NextMII = llvm::next(MII);

+ MachineBasicBlock::iterator oldNextMII = llvm::next(MII);

+ TII->storeRegToStackSlot(MBB, llvm::next(MII), Phys, isKill, StackSlot, RC);

+ NextMII = llvm::next(MII);

+ NextMII = llvm::next(MII);

+ NextMII = llvm::next(MII);