SelectionDAGBuild.cpp

Go to the documentation of this file.

//===-- SelectionDAGBuild.cpp - Selection-DAG building --------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This implements routines for translating from LLVM IR into SelectionDAG IR.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "isel"
#include "SelectionDAGBuild.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Constants.h"
#include "llvm/CallingConv.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
#include "llvm/InlineAsm.h"
#include "llvm/Instructions.h"
#include "llvm/Intrinsics.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Module.h"
#include "llvm/CodeGen/FastISel.h"
#include "llvm/CodeGen/GCStrategy.h"
#include "llvm/CodeGen/GCMetadata.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetFrameInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
using namespace llvm;

/// LimitFloatPrecision - Generate low-precision inline sequences for
/// some float libcalls (6, 8 or 12 bits).
static unsigned LimitFloatPrecision;

static cl::opt<unsigned, true>
LimitFPPrecision("limit-float-precision",
                 cl::desc("Generate low-precision inline sequences "
                          "for some float libcalls"),
                 cl::location(LimitFloatPrecision),
                 cl::init(0));

/// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence
/// of insertvalue or extractvalue indices that identify a member, return
/// the linearized index of the start of the member.
///
static unsigned ComputeLinearIndex(const TargetLowering &TLI, const Type *Ty,
                                   const unsigned *Indices,
                                   const unsigned *IndicesEnd,
                                   unsigned CurIndex = 0) {
  // Base case: We're done.
  if (Indices && Indices == IndicesEnd)
    return CurIndex;

  // Given a struct type, recursively traverse the elements.
  if (const StructType *STy = dyn_cast<StructType>(Ty)) {
    for (StructType::element_iterator EB = STy->element_begin(),
                                      EI = EB,
                                      EE = STy->element_end();
        EI != EE; ++EI) {
      if (Indices && *Indices == unsigned(EI - EB))
        return ComputeLinearIndex(TLI, *EI, Indices+1, IndicesEnd, CurIndex);
      CurIndex = ComputeLinearIndex(TLI, *EI, 0, 0, CurIndex);
    }
    return CurIndex;
  }
  // Given an array type, recursively traverse the elements.
  else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
    const Type *EltTy = ATy->getElementType();
    for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
      if (Indices && *Indices == i)
        return ComputeLinearIndex(TLI, EltTy, Indices+1, IndicesEnd, CurIndex);
      CurIndex = ComputeLinearIndex(TLI, EltTy, 0, 0, CurIndex);
    }
    return CurIndex;
  }
  // We haven't found the type we're looking for, so keep searching.
  return CurIndex + 1;
}

/// ComputeValueVTs - Given an LLVM IR type, compute a sequence of
/// MVTs that represent all the individual underlying
/// non-aggregate types that comprise it.
///
/// If Offsets is non-null, it points to a vector to be filled in
/// with the in-memory offsets of each of the individual values.
///
static void ComputeValueVTs(const TargetLowering &TLI, const Type *Ty,
                            SmallVectorImpl<MVT> &ValueVTs,
                            SmallVectorImpl<uint64_t> *Offsets = 0,
                            uint64_t StartingOffset = 0) {
  // Given a struct type, recursively traverse the elements.
  if (const StructType *STy = dyn_cast<StructType>(Ty)) {
    const StructLayout *SL = TLI.getTargetData()->getStructLayout(STy);
    for (StructType::element_iterator EB = STy->element_begin(),
                                      EI = EB,
                                      EE = STy->element_end();
         EI != EE; ++EI)
      ComputeValueVTs(TLI, *EI, ValueVTs, Offsets,
                      StartingOffset + SL->getElementOffset(EI - EB));
    return;
  }
  // Given an array type, recursively traverse the elements.
  if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
    const Type *EltTy = ATy->getElementType();
    uint64_t EltSize = TLI.getTargetData()->getABITypeSize(EltTy);
    for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
      ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets,
                      StartingOffset + i * EltSize);
    return;
  }
  // Base case: we can get an MVT for this LLVM IR type.
  ValueVTs.push_back(TLI.getValueType(Ty));
  if (Offsets)
    Offsets->push_back(StartingOffset);
}

namespace llvm {
  /// RegsForValue - This struct represents the registers (physical or virtual)
  /// that a particular set of values is assigned, and the type information about
  /// the value. The most common situation is to represent one value at a time,
  /// but struct or array values are handled element-wise as multiple values.
  /// The splitting of aggregates is performed recursively, so that we never
  /// have aggregate-typed registers. The values at this point do not necessarily
  /// have legal types, so each value may require one or more registers of some
  /// legal type.
  /// 
  struct VISIBILITY_HIDDEN RegsForValue {
    /// TLI - The TargetLowering object.
    ///
    const TargetLowering *TLI;

    /// ValueVTs - The value types of the values, which may not be legal, and
    /// may need be promoted or synthesized from one or more registers.
    ///
    SmallVector<MVT, 4> ValueVTs;
    
    /// RegVTs - The value types of the registers. This is the same size as
    /// ValueVTs and it records, for each value, what the type of the assigned
    /// register or registers are. (Individual values are never synthesized
    /// from more than one type of register.)
    ///
    /// With virtual registers, the contents of RegVTs is redundant with TLI's
    /// getRegisterType member function, however when with physical registers
    /// it is necessary to have a separate record of the types.
    ///
    SmallVector<MVT, 4> RegVTs;
    
    /// Regs - This list holds the registers assigned to the values.
    /// Each legal or promoted value requires one register, and each
    /// expanded value requires multiple registers.
    ///
    SmallVector<unsigned, 4> Regs;
    
    RegsForValue() : TLI(0) {}
    
    RegsForValue(const TargetLowering &tli,
                 const SmallVector<unsigned, 4> &regs, 
                 MVT regvt, MVT valuevt)
      : TLI(&tli),  ValueVTs(1, valuevt), RegVTs(1, regvt), Regs(regs) {}
    RegsForValue(const TargetLowering &tli,
                 const SmallVector<unsigned, 4> &regs, 
                 const SmallVector<MVT, 4> &regvts,
                 const SmallVector<MVT, 4> &valuevts)
      : TLI(&tli), ValueVTs(valuevts), RegVTs(regvts), Regs(regs) {}
    RegsForValue(const TargetLowering &tli,
                 unsigned Reg, const Type *Ty) : TLI(&tli) {
      ComputeValueVTs(tli, Ty, ValueVTs);

      for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) {
        MVT ValueVT = ValueVTs[Value];
        unsigned NumRegs = TLI->getNumRegisters(ValueVT);
        MVT RegisterVT = TLI->getRegisterType(ValueVT);
        for (unsigned i = 0; i != NumRegs; ++i)
          Regs.push_back(Reg + i);
        RegVTs.push_back(RegisterVT);
        Reg += NumRegs;
      }
    }
    
    /// append - Add the specified values to this one.
    void append(const RegsForValue &RHS) {
      TLI = RHS.TLI;
      ValueVTs.append(RHS.ValueVTs.begin(), RHS.ValueVTs.end());
      RegVTs.append(RHS.RegVTs.begin(), RHS.RegVTs.end());
      Regs.append(RHS.Regs.begin(), RHS.Regs.end());
    }
    
    
    /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
    /// this value and returns the result as a ValueVTs value.  This uses 
    /// Chain/Flag as the input and updates them for the output Chain/Flag.
    /// If the Flag pointer is NULL, no flag is used.
    SDValue getCopyFromRegs(SelectionDAG &DAG,
                              SDValue &Chain, SDValue *Flag) const;

    /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
    /// specified value into the registers specified by this object.  This uses 
    /// Chain/Flag as the input and updates them for the output Chain/Flag.
    /// If the Flag pointer is NULL, no flag is used.
    void getCopyToRegs(SDValue Val, SelectionDAG &DAG,
                       SDValue &Chain, SDValue *Flag) const;
    
    /// AddInlineAsmOperands - Add this value to the specified inlineasm node
    /// operand list.  This adds the code marker and includes the number of 
    /// values added into it.
    void AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
                              std::vector<SDValue> &Ops) const;
  };
}

/// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
/// PHI nodes or outside of the basic block that defines it, or used by a 
/// switch or atomic instruction, which may expand to multiple basic blocks.
static bool isUsedOutsideOfDefiningBlock(Instruction *I) {
  if (isa<PHINode>(I)) return true;
  BasicBlock *BB = I->getParent();
  for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
    if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI) ||
        // FIXME: Remove switchinst special case.
        isa<SwitchInst>(*UI))
      return true;
  return false;
}

/// isOnlyUsedInEntryBlock - If the specified argument is only used in the
/// entry block, return true.  This includes arguments used by switches, since
/// the switch may expand into multiple basic blocks.
static bool isOnlyUsedInEntryBlock(Argument *A, bool EnableFastISel) {
  // With FastISel active, we may be splitting blocks, so force creation
  // of virtual registers for all non-dead arguments.
  // Don't force virtual registers for byval arguments though, because
  // fast-isel can't handle those in all cases.
  if (EnableFastISel && !A->hasByValAttr())
    return A->use_empty();

  BasicBlock *Entry = A->getParent()->begin();
  for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI)
    if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI))
      return false;  // Use not in entry block.
  return true;
}

FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli)
  : TLI(tli) {
}

void FunctionLoweringInfo::set(Function &fn, MachineFunction &mf,
                               bool EnableFastISel) {
  Fn = &fn;
  MF = &mf;
  RegInfo = &MF->getRegInfo();

  // Create a vreg for each argument register that is not dead and is used
  // outside of the entry block for the function.
  for (Function::arg_iterator AI = Fn->arg_begin(), E = Fn->arg_end();
       AI != E; ++AI)
    if (!isOnlyUsedInEntryBlock(AI, EnableFastISel))
      InitializeRegForValue(AI);

  // Initialize the mapping of values to registers.  This is only set up for
  // instruction values that are used outside of the block that defines
  // them.
  Function::iterator BB = Fn->begin(), EB = Fn->end();
  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
    if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
      if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
        const Type *Ty = AI->getAllocatedType();
        uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty);
        unsigned Align = 
          std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
                   AI->getAlignment());

        TySize *= CUI->getZExtValue();   // Get total allocated size.
        if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
        StaticAllocaMap[AI] =
          MF->getFrameInfo()->CreateStackObject(TySize, Align);
      }

  for (; BB != EB; ++BB)
    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
      if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I))
        if (!isa<AllocaInst>(I) ||
            !StaticAllocaMap.count(cast<AllocaInst>(I)))
          InitializeRegForValue(I);

  // Create an initial MachineBasicBlock for each LLVM BasicBlock in F.  This
  // also creates the initial PHI MachineInstrs, though none of the input
  // operands are populated.
  for (BB = Fn->begin(), EB = Fn->end(); BB != EB; ++BB) {
    MachineBasicBlock *MBB = mf.CreateMachineBasicBlock(BB);
    MBBMap[BB] = MBB;
    MF->push_back(MBB);

    // Create Machine PHI nodes for LLVM PHI nodes, lowering them as
    // appropriate.
    PHINode *PN;
    for (BasicBlock::iterator I = BB->begin();(PN = dyn_cast<PHINode>(I)); ++I){
      if (PN->use_empty()) continue;
      
      unsigned PHIReg = ValueMap[PN];
      assert(PHIReg && "PHI node does not have an assigned virtual register!");

      SmallVector<MVT, 4> ValueVTs;
      ComputeValueVTs(TLI, PN->getType(), ValueVTs);
      for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) {
        MVT VT = ValueVTs[vti];
        unsigned NumRegisters = TLI.getNumRegisters(VT);
        const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
        for (unsigned i = 0; i != NumRegisters; ++i)
          BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i);
        PHIReg += NumRegisters;
      }
    }
  }
}

unsigned FunctionLoweringInfo::MakeReg(MVT VT) {
  return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
}

/// CreateRegForValue - Allocate the appropriate number of virtual registers of
/// the correctly promoted or expanded types.  Assign these registers
/// consecutive vreg numbers and return the first assigned number.
///
/// In the case that the given value has struct or array type, this function
/// will assign registers for each member or element.
///
unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) {
  SmallVector<MVT, 4> ValueVTs;
  ComputeValueVTs(TLI, V->getType(), ValueVTs);

  unsigned FirstReg = 0;
  for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) {
    MVT ValueVT = ValueVTs[Value];
    MVT RegisterVT = TLI.getRegisterType(ValueVT);

    unsigned NumRegs = TLI.getNumRegisters(ValueVT);
    for (unsigned i = 0; i != NumRegs; ++i) {
      unsigned R = MakeReg(RegisterVT);
      if (!FirstReg) FirstReg = R;
    }
  }
  return FirstReg;
}

/// getCopyFromParts - Create a value that contains the specified legal parts
/// combined into the value they represent.  If the parts combine to a type
/// larger then ValueVT then AssertOp can be used to specify whether the extra
/// bits are known to be zero (ISD::AssertZext) or sign extended from ValueVT
/// (ISD::AssertSext).
static SDValue getCopyFromParts(SelectionDAG &DAG,
                                  const SDValue *Parts,
                                  unsigned NumParts,
                                  MVT PartVT,
                                  MVT ValueVT,
                                  ISD::NodeType AssertOp = ISD::DELETED_NODE) {
  assert(NumParts > 0 && "No parts to assemble!");
  TargetLowering &TLI = DAG.getTargetLoweringInfo();
  SDValue Val = Parts[0];

  if (NumParts > 1) {
    // Assemble the value from multiple parts.
    if (!ValueVT.isVector()) {
      unsigned PartBits = PartVT.getSizeInBits();
      unsigned ValueBits = ValueVT.getSizeInBits();

      // Assemble the power of 2 part.
      unsigned RoundParts = NumParts & (NumParts - 1) ?
        1 << Log2_32(NumParts) : NumParts;
      unsigned RoundBits = PartBits * RoundParts;
      MVT RoundVT = RoundBits == ValueBits ?
        ValueVT : MVT::getIntegerVT(RoundBits);
      SDValue Lo, Hi;

      MVT HalfVT = ValueVT.isInteger() ?
        MVT::getIntegerVT(RoundBits/2) :
        MVT::getFloatingPointVT(RoundBits/2);

      if (RoundParts > 2) {
        Lo = getCopyFromParts(DAG, Parts, RoundParts/2, PartVT, HalfVT);
        Hi = getCopyFromParts(DAG, Parts+RoundParts/2, RoundParts/2,
                              PartVT, HalfVT);
      } else {
        Lo = DAG.getNode(ISD::BIT_CONVERT, HalfVT, Parts[0]);
        Hi = DAG.getNode(ISD::BIT_CONVERT, HalfVT, Parts[1]);
      }
      if (TLI.isBigEndian())
        std::swap(Lo, Hi);
      Val = DAG.getNode(ISD::BUILD_PAIR, RoundVT, Lo, Hi);

      if (RoundParts < NumParts) {
        // Assemble the trailing non-power-of-2 part.
        unsigned OddParts = NumParts - RoundParts;
        MVT OddVT = MVT::getIntegerVT(OddParts * PartBits);
        Hi = getCopyFromParts(DAG, Parts+RoundParts, OddParts, PartVT, OddVT);

        // Combine the round and odd parts.
        Lo = Val;
        if (TLI.isBigEndian())
          std::swap(Lo, Hi);
        MVT TotalVT = MVT::getIntegerVT(NumParts * PartBits);
        Hi = DAG.getNode(ISD::ANY_EXTEND, TotalVT, Hi);
        Hi = DAG.getNode(ISD::SHL, TotalVT, Hi,
                         DAG.getConstant(Lo.getValueType().getSizeInBits(),
                                         TLI.getShiftAmountTy()));
        Lo = DAG.getNode(ISD::ZERO_EXTEND, TotalVT, Lo);
        Val = DAG.getNode(ISD::OR, TotalVT, Lo, Hi);
      }
    } else {
      // Handle a multi-element vector.
      MVT IntermediateVT, RegisterVT;
      unsigned NumIntermediates;
      unsigned NumRegs =
        TLI.getVectorTypeBreakdown(ValueVT, IntermediateVT, NumIntermediates,
                                   RegisterVT);
      assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
      NumParts = NumRegs; // Silence a compiler warning.
      assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
      assert(RegisterVT == Parts[0].getValueType() &&
             "Part type doesn't match part!");

      // Assemble the parts into intermediate operands.
      SmallVector<SDValue, 8> Ops(NumIntermediates);
      if (NumIntermediates == NumParts) {
        // If the register was not expanded, truncate or copy the value,
        // as appropriate.
        for (unsigned i = 0; i != NumParts; ++i)
          Ops[i] = getCopyFromParts(DAG, &Parts[i], 1,
                                    PartVT, IntermediateVT);
      } else if (NumParts > 0) {
        // If the intermediate type was expanded, build the intermediate operands
        // from the parts.
        assert(NumParts % NumIntermediates == 0 &&
               "Must expand into a divisible number of parts!");
        unsigned Factor = NumParts / NumIntermediates;
        for (unsigned i = 0; i != NumIntermediates; ++i)
          Ops[i] = getCopyFromParts(DAG, &Parts[i * Factor], Factor,
                                    PartVT, IntermediateVT);
      }

      // Build a vector with BUILD_VECTOR or CONCAT_VECTORS from the intermediate
      // operands.
      Val = DAG.getNode(IntermediateVT.isVector() ?
                        ISD::CONCAT_VECTORS : ISD::BUILD_VECTOR,
                        ValueVT, &Ops[0], NumIntermediates);
    }
  }

  // There is now one part, held in Val.  Correct it to match ValueVT.
  PartVT = Val.getValueType();

  if (PartVT == ValueVT)
    return Val;

  if (PartVT.isVector()) {
    assert(ValueVT.isVector() && "Unknown vector conversion!");
    return DAG.getNode(ISD::BIT_CONVERT, ValueVT, Val);
  }

  if (ValueVT.isVector()) {
    assert(ValueVT.getVectorElementType() == PartVT &&
           ValueVT.getVectorNumElements() == 1 &&
           "Only trivial scalar-to-vector conversions should get here!");
    return DAG.getNode(ISD::BUILD_VECTOR, ValueVT, Val);
  }

  if (PartVT.isInteger() &&
      ValueVT.isInteger()) {
    if (ValueVT.bitsLT(PartVT)) {
      // For a truncate, see if we have any information to
      // indicate whether the truncated bits will always be
      // zero or sign-extension.
      if (AssertOp != ISD::DELETED_NODE)
        Val = DAG.getNode(AssertOp, PartVT, Val,
                          DAG.getValueType(ValueVT));
      return DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
    } else {
      return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val);
    }
  }

  if (PartVT.isFloatingPoint() && ValueVT.isFloatingPoint()) {
    if (ValueVT.bitsLT(Val.getValueType()))
      // FP_ROUND's are always exact here.
      return DAG.getNode(ISD::FP_ROUND, ValueVT, Val,
                         DAG.getIntPtrConstant(1));
    return DAG.getNode(ISD::FP_EXTEND, ValueVT, Val);
  }

  if (PartVT.getSizeInBits() == ValueVT.getSizeInBits())
    return DAG.getNode(ISD::BIT_CONVERT, ValueVT, Val);

  assert(0 && "Unknown mismatch!");
  return SDValue();
}

/// getCopyToParts - Create a series of nodes that contain the specified value
/// split into legal parts.  If the parts contain more bits than Val, then, for
/// integers, ExtendKind can be used to specify how to generate the extra bits.
static void getCopyToParts(SelectionDAG &DAG, SDValue Val,
                           SDValue *Parts, unsigned NumParts, MVT PartVT,
                           ISD::NodeType ExtendKind = ISD::ANY_EXTEND) {
  TargetLowering &TLI = DAG.getTargetLoweringInfo();
  MVT PtrVT = TLI.getPointerTy();
  MVT ValueVT = Val.getValueType();
  unsigned PartBits = PartVT.getSizeInBits();
  assert(TLI.isTypeLegal(PartVT) && "Copying to an illegal type!");

  if (!NumParts)
    return;

  if (!ValueVT.isVector()) {
    if (PartVT == ValueVT) {
      assert(NumParts == 1 && "No-op copy with multiple parts!");
      Parts[0] = Val;
      return;
    }

    if (NumParts * PartBits > ValueVT.getSizeInBits()) {
      // If the parts cover more bits than the value has, promote the value.
      if (PartVT.isFloatingPoint() && ValueVT.isFloatingPoint()) {
        assert(NumParts == 1 && "Do not know what to promote to!");
        Val = DAG.getNode(ISD::FP_EXTEND, PartVT, Val);
      } else if (PartVT.isInteger() && ValueVT.isInteger()) {
        ValueVT = MVT::getIntegerVT(NumParts * PartBits);
        Val = DAG.getNode(ExtendKind, ValueVT, Val);
      } else {
        assert(0 && "Unknown mismatch!");
      }
    } else if (PartBits == ValueVT.getSizeInBits()) {
      // Different types of the same size.
      assert(NumParts == 1 && PartVT != ValueVT);
      Val = DAG.getNode(ISD::BIT_CONVERT, PartVT, Val);
    } else if (NumParts * PartBits < ValueVT.getSizeInBits()) {
      // If the parts cover less bits than value has, truncate the value.
      if (PartVT.isInteger() && ValueVT.isInteger()) {
        ValueVT = MVT::getIntegerVT(NumParts * PartBits);
        Val = DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
      } else {
        assert(0 && "Unknown mismatch!");
      }
    }

    // The value may have changed - recompute ValueVT.
    ValueVT = Val.getValueType();
    assert(NumParts * PartBits == ValueVT.getSizeInBits() &&
           "Failed to tile the value with PartVT!");

    if (NumParts == 1) {
      assert(PartVT == ValueVT && "Type conversion failed!");
      Parts[0] = Val;
      return;
    }

    // Expand the value into multiple parts.
    if (NumParts & (NumParts - 1)) {
      // The number of parts is not a power of 2.  Split off and copy the tail.
      assert(PartVT.isInteger() && ValueVT.isInteger() &&
             "Do not know what to expand to!");
      unsigned RoundParts = 1 << Log2_32(NumParts);
      unsigned RoundBits = RoundParts * PartBits;
      unsigned OddParts = NumParts - RoundParts;
      SDValue OddVal = DAG.getNode(ISD::SRL, ValueVT, Val,
                                     DAG.getConstant(RoundBits,
                                                     TLI.getShiftAmountTy()));
      getCopyToParts(DAG, OddVal, Parts + RoundParts, OddParts, PartVT);
      if (TLI.isBigEndian())
        // The odd parts were reversed by getCopyToParts - unreverse them.
        std::reverse(Parts + RoundParts, Parts + NumParts);
      NumParts = RoundParts;
      ValueVT = MVT::getIntegerVT(NumParts * PartBits);
      Val = DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
    }

    // The number of parts is a power of 2.  Repeatedly bisect the value using
    // EXTRACT_ELEMENT.
    Parts[0] = DAG.getNode(ISD::BIT_CONVERT,
                           MVT::getIntegerVT(ValueVT.getSizeInBits()),
                           Val);
    for (unsigned StepSize = NumParts; StepSize > 1; StepSize /= 2) {
      for (unsigned i = 0; i < NumParts; i += StepSize) {
        unsigned ThisBits = StepSize * PartBits / 2;
        MVT ThisVT = MVT::getIntegerVT (ThisBits);
        SDValue &Part0 = Parts[i];
        SDValue &Part1 = Parts[i+StepSize/2];

        Part1 = DAG.getNode(ISD::EXTRACT_ELEMENT, ThisVT, Part0,
                            DAG.getConstant(1, PtrVT));
        Part0 = DAG.getNode(ISD::EXTRACT_ELEMENT, ThisVT, Part0,
                            DAG.getConstant(0, PtrVT));

        if (ThisBits == PartBits && ThisVT != PartVT) {
          Part0 = DAG.getNode(ISD::BIT_CONVERT, PartVT, Part0);
          Part1 = DAG.getNode(ISD::BIT_CONVERT, PartVT, Part1);
        }
      }
    }

    if (TLI.isBigEndian())
      std::reverse(Parts, Parts + NumParts);

    return;
  }

  // Vector ValueVT.
  if (NumParts == 1) {
    if (PartVT != ValueVT) {
      if (PartVT.isVector()) {
        Val = DAG.getNode(ISD::BIT_CONVERT, PartVT, Val);
      } else {
        assert(ValueVT.getVectorElementType() == PartVT &&
               ValueVT.getVectorNumElements() == 1 &&
               "Only trivial vector-to-scalar conversions should get here!");
        Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, PartVT, Val,
                          DAG.getConstant(0, PtrVT));
      }
    }

    Parts[0] = Val;
    return;
  }

  // Handle a multi-element vector.
  MVT IntermediateVT, RegisterVT;
  unsigned NumIntermediates;
  unsigned NumRegs =
    DAG.getTargetLoweringInfo()
      .getVectorTypeBreakdown(ValueVT, IntermediateVT, NumIntermediates,
                              RegisterVT);
  unsigned NumElements = ValueVT.getVectorNumElements();

  assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
  NumParts = NumRegs; // Silence a compiler warning.
  assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");

  // Split the vector into intermediate operands.
  SmallVector<SDValue, 8> Ops(NumIntermediates);
  for (unsigned i = 0; i != NumIntermediates; ++i)
    if (IntermediateVT.isVector())
      Ops[i] = DAG.getNode(ISD::EXTRACT_SUBVECTOR,
                           IntermediateVT, Val,
                           DAG.getConstant(i * (NumElements / NumIntermediates),
                                           PtrVT));
    else
      Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT,
                           IntermediateVT, Val, 
                           DAG.getConstant(i, PtrVT));

  // Split the intermediate operands into legal parts.
  if (NumParts == NumIntermediates) {
    // If the register was not expanded, promote or copy the value,
    // as appropriate.
    for (unsigned i = 0; i != NumParts; ++i)
      getCopyToParts(DAG, Ops[i], &Parts[i], 1, PartVT);
  } else if (NumParts > 0) {
    // If the intermediate type was expanded, split each the value into
    // legal parts.
    assert(NumParts % NumIntermediates == 0 &&
           "Must expand into a divisible number of parts!");
    unsigned Factor = NumParts / NumIntermediates;
    for (unsigned i = 0; i != NumIntermediates; ++i)
      getCopyToParts(DAG, Ops[i], &Parts[i * Factor], Factor, PartVT);
  }
}


void SelectionDAGLowering::init(GCFunctionInfo *gfi, AliasAnalysis &aa) {
  AA = &aa;
  GFI = gfi;
  TD = DAG.getTarget().getTargetData();
}

/// clear - Clear out the curret SelectionDAG and the associated
/// state and prepare this SelectionDAGLowering object to be used
/// for a new block. This doesn't clear out information about
/// additional blocks that are needed to complete switch lowering
/// or PHI node updating; that information is cleared out as it is
/// consumed.
void SelectionDAGLowering::clear() {
  NodeMap.clear();
  PendingLoads.clear();
  PendingExports.clear();
  DAG.clear();
}

/// getRoot - Return the current virtual root of the Selection DAG,
/// flushing any PendingLoad items. This must be done before emitting
/// a store or any other node that may need to be ordered after any
/// prior load instructions.
///
SDValue SelectionDAGLowering::getRoot() {
  if (PendingLoads.empty())
    return DAG.getRoot();

  if (PendingLoads.size() == 1) {
    SDValue Root = PendingLoads[0];
    DAG.setRoot(Root);
    PendingLoads.clear();
    return Root;
  }

  // Otherwise, we have to make a token factor node.
  SDValue Root = DAG.getNode(ISD::TokenFactor, MVT::Other,
                               &PendingLoads[0], PendingLoads.size());
  PendingLoads.clear();
  DAG.setRoot(Root);
  return Root;
}

/// getControlRoot - Similar to getRoot, but instead of flushing all the
/// PendingLoad items, flush all the PendingExports items. It is necessary
/// to do this before emitting a terminator instruction.
///
SDValue SelectionDAGLowering::getControlRoot() {
  SDValue Root = DAG.getRoot();

  if (PendingExports.empty())
    return Root;

  // Turn all of the CopyToReg chains into one factored node.
  if (Root.getOpcode() != ISD::EntryToken) {
    unsigned i = 0, e = PendingExports.size();
    for (; i != e; ++i) {
      assert(PendingExports[i].getNode()->getNumOperands() > 1);
      if (PendingExports[i].getNode()->getOperand(0) == Root)
        break;  // Don't add the root if we already indirectly depend on it.
    }

    if (i == e)
      PendingExports.push_back(Root);
  }

  Root = DAG.getNode(ISD::TokenFactor, MVT::Other,
                     &PendingExports[0],
                     PendingExports.size());
  PendingExports.clear();
  DAG.setRoot(Root);
  return Root;
}

void SelectionDAGLowering::visit(Instruction &I) {
  visit(I.getOpcode(), I);
}

void SelectionDAGLowering::visit(unsigned Opcode, User &I) {
  // Note: this doesn't use InstVisitor, because it has to work with
  // ConstantExpr's in addition to instructions.
  switch (Opcode) {
  default: assert(0 && "Unknown instruction type encountered!");
           abort();
    // Build the switch statement using the Instruction.def file.
#define HANDLE_INST(NUM, OPCODE, CLASS) \
  case Instruction::OPCODE:return visit##OPCODE((CLASS&)I);
#include "llvm/Instruction.def"
  }
} 

void SelectionDAGLowering::visitAdd(User &I) {
  if (I.getType()->isFPOrFPVector())
    visitBinary(I, ISD::FADD);
  else
    visitBinary(I, ISD::ADD);
}

void SelectionDAGLowering::visitMul(User &I) {
  if (I.getType()->isFPOrFPVector())
    visitBinary(I, ISD::FMUL);
  else
    visitBinary(I, ISD::MUL);
}

SDValue SelectionDAGLowering::getValue(const Value *V) {
  SDValue &N = NodeMap[V];
  if (N.getNode()) return N;
  
  if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) {
    MVT VT = TLI.getValueType(V->getType(), true);
    
    if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
      return N = DAG.getConstant(*CI, VT);

    if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
      return N = DAG.getGlobalAddress(GV, VT);
    
    if (isa<ConstantPointerNull>(C))
      return N = DAG.getConstant(0, TLI.getPointerTy());
    
    if (ConstantFP *CFP = dyn_cast<ConstantFP>(C))
      return N = DAG.getConstantFP(*CFP, VT);
    
    if (isa<UndefValue>(C) && !isa<VectorType>(V->getType()) &&
        !V->getType()->isAggregateType())
      return N = DAG.getNode(ISD::UNDEF, VT);

    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
      visit(CE->getOpcode(), *CE);
      SDValue N1 = NodeMap[V];
      assert(N1.getNode() && "visit didn't populate the ValueMap!");
      return N1;
    }
    
    if (isa<ConstantStruct>(C) || isa<ConstantArray>(C)) {