aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp')
-rw-r--r--lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp5821
1 files changed, 0 insertions, 5821 deletions
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
deleted file mode 100644
index cb6be3fc52..0000000000
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
+++ /dev/null
@@ -1,5821 +0,0 @@
-//===-- 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 "FunctionLoweringInfo.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/LLVMContext.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/CodeGen/DwarfWriter.h"
-#include "llvm/Analysis/DebugInfo.h"
-#include "llvm/Target/TargetRegisterInfo.h"
-#include "llvm/Target/TargetData.h"
-#include "llvm/Target/TargetFrameInfo.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetIntrinsicInfo.h"
-#include "llvm/Target/TargetLowering.h"
-#include "llvm/Target/TargetOptions.h"
-#include "llvm/Support/Compiler.h"
-#include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/ErrorHandling.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));
-
-namespace {
- /// 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 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<EVT, 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<EVT, 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,
- EVT regvt, EVT valuevt)
- : TLI(&tli), ValueVTs(1, valuevt), RegVTs(1, regvt), Regs(regs) {}
- RegsForValue(const TargetLowering &tli,
- const SmallVector<unsigned, 4> &regs,
- const SmallVector<EVT, 4> &regvts,
- const SmallVector<EVT, 4> &valuevts)
- : TLI(&tli), ValueVTs(valuevts), RegVTs(regvts), Regs(regs) {}
- RegsForValue(LLVMContext &Context, const TargetLowering &tli,
- unsigned Reg, const Type *Ty) : TLI(&tli) {
- ComputeValueVTs(tli, Ty, ValueVTs);
-
- for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) {
- EVT ValueVT = ValueVTs[Value];
- unsigned NumRegs = TLI->getNumRegisters(Context, ValueVT);
- EVT RegisterVT = TLI->getRegisterType(Context, 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, DebugLoc dl,
- 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, DebugLoc dl,
- SDValue &Chain, SDValue *Flag) const;
-
- /// AddInlineAsmOperands - Add this value to the specified inlineasm node
- /// operand list. This adds the code marker, matching input operand index
- /// (if applicable), and includes the number of values added into it.
- void AddInlineAsmOperands(unsigned Code,
- bool HasMatching, unsigned MatchingIdx,
- SelectionDAG &DAG, std::vector<SDValue> &Ops) const;
- };
-}
-
-/// 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, DebugLoc dl,
- const SDValue *Parts,
- unsigned NumParts, EVT PartVT, EVT ValueVT,
- ISD::NodeType AssertOp = ISD::DELETED_NODE) {
- assert(NumParts > 0 && "No parts to assemble!");
- const TargetLowering &TLI = DAG.getTargetLoweringInfo();
- SDValue Val = Parts[0];
-
- if (NumParts > 1) {
- // Assemble the value from multiple parts.
- if (!ValueVT.isVector() && ValueVT.isInteger()) {
- 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;
- EVT RoundVT = RoundBits == ValueBits ?
- ValueVT : EVT::getIntegerVT(*DAG.getContext(), RoundBits);
- SDValue Lo, Hi;
-
- EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), RoundBits/2);
-
- if (RoundParts > 2) {
- Lo = getCopyFromParts(DAG, dl, Parts, RoundParts/2, PartVT, HalfVT);
- Hi = getCopyFromParts(DAG, dl, Parts+RoundParts/2, RoundParts/2,
- PartVT, HalfVT);
- } else {
- Lo = DAG.getNode(ISD::BIT_CONVERT, dl, HalfVT, Parts[0]);
- Hi = DAG.getNode(ISD::BIT_CONVERT, dl, HalfVT, Parts[1]);
- }
- if (TLI.isBigEndian())
- std::swap(Lo, Hi);
- Val = DAG.getNode(ISD::BUILD_PAIR, dl, RoundVT, Lo, Hi);
-
- if (RoundParts < NumParts) {
- // Assemble the trailing non-power-of-2 part.
- unsigned OddParts = NumParts - RoundParts;
- EVT OddVT = EVT::getIntegerVT(*DAG.getContext(), OddParts * PartBits);
- Hi = getCopyFromParts(DAG, dl,
- Parts+RoundParts, OddParts, PartVT, OddVT);
-
- // Combine the round and odd parts.
- Lo = Val;
- if (TLI.isBigEndian())
- std::swap(Lo, Hi);
- EVT TotalVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
- Hi = DAG.getNode(ISD::ANY_EXTEND, dl, TotalVT, Hi);
- Hi = DAG.getNode(ISD::SHL, dl, TotalVT, Hi,
- DAG.getConstant(Lo.getValueType().getSizeInBits(),
- TLI.getPointerTy()));
- Lo = DAG.getNode(ISD::ZERO_EXTEND, dl, TotalVT, Lo);
- Val = DAG.getNode(ISD::OR, dl, TotalVT, Lo, Hi);
- }
- } else if (ValueVT.isVector()) {
- // Handle a multi-element vector.
- EVT IntermediateVT, RegisterVT;
- unsigned NumIntermediates;
- unsigned NumRegs =
- TLI.getVectorTypeBreakdown(*DAG.getContext(), 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, dl, &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, dl, &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, dl,
- ValueVT, &Ops[0], NumIntermediates);
- } else if (PartVT.isFloatingPoint()) {
- // FP split into multiple FP parts (for ppcf128)
- assert(ValueVT == EVT(MVT::ppcf128) && PartVT == EVT(MVT::f64) &&
- "Unexpected split");
- SDValue Lo, Hi;
- Lo = DAG.getNode(ISD::BIT_CONVERT, dl, EVT(MVT::f64), Parts[0]);
- Hi = DAG.getNode(ISD::BIT_CONVERT, dl, EVT(MVT::f64), Parts[1]);
- if (TLI.isBigEndian())
- std::swap(Lo, Hi);
- Val = DAG.getNode(ISD::BUILD_PAIR, dl, ValueVT, Lo, Hi);
- } else {
- // FP split into integer parts (soft fp)
- assert(ValueVT.isFloatingPoint() && PartVT.isInteger() &&
- !PartVT.isVector() && "Unexpected split");
- EVT IntVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits());
- Val = getCopyFromParts(DAG, dl, Parts, NumParts, PartVT, IntVT);
- }
- }
-
- // 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, dl, 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, dl, 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, dl, PartVT, Val,
- DAG.getValueType(ValueVT));
- return DAG.getNode(ISD::TRUNCATE, dl, ValueVT, Val);
- } else {
- return DAG.getNode(ISD::ANY_EXTEND, dl, 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, dl, ValueVT, Val,
- DAG.getIntPtrConstant(1));
- return DAG.getNode(ISD::FP_EXTEND, dl, ValueVT, Val);
- }
-
- if (PartVT.getSizeInBits() == ValueVT.getSizeInBits())
- return DAG.getNode(ISD::BIT_CONVERT, dl, ValueVT, Val);
-
- llvm_unreachable("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, DebugLoc dl, SDValue Val,
- SDValue *Parts, unsigned NumParts, EVT PartVT,
- ISD::NodeType ExtendKind = ISD::ANY_EXTEND) {
- const TargetLowering &TLI = DAG.getTargetLoweringInfo();
- EVT PtrVT = TLI.getPointerTy();
- EVT ValueVT = Val.getValueType();
- unsigned PartBits = PartVT.getSizeInBits();
- unsigned OrigNumParts = NumParts;
- 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, dl, PartVT, Val);
- } else if (PartVT.isInteger() && ValueVT.isInteger()) {
- ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
- Val = DAG.getNode(ExtendKind, dl, ValueVT, Val);
- } else {
- llvm_unreachable("Unknown mismatch!");
- }
- } else if (PartBits == ValueVT.getSizeInBits()) {
- // Different types of the same size.
- assert(NumParts == 1 && PartVT != ValueVT);
- Val = DAG.getNode(ISD::BIT_CONVERT, dl, 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 = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
- Val = DAG.getNode(ISD::TRUNCATE, dl, ValueVT, Val);
- } else {
- llvm_unreachable("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, dl, ValueVT, Val,
- DAG.getConstant(RoundBits,
- TLI.getPointerTy()));
- getCopyToParts(DAG, dl, 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 = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits);
- Val = DAG.getNode(ISD::TRUNCATE, dl, 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, dl,
- EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits()),
- Val);
- for (unsigned StepSize = NumParts; StepSize > 1; StepSize /= 2) {
- for (unsigned i = 0; i < NumParts; i += StepSize) {
- unsigned ThisBits = StepSize * PartBits / 2;
- EVT ThisVT = EVT::getIntegerVT(*DAG.getContext(), ThisBits);
- SDValue &Part0 = Parts[i];
- SDValue &Part1 = Parts[i+StepSize/2];
-
- Part1 = DAG.getNode(ISD::EXTRACT_ELEMENT, dl,
- ThisVT, Part0,
- DAG.getConstant(1, PtrVT));
- Part0 = DAG.getNode(ISD::EXTRACT_ELEMENT, dl,
- ThisVT, Part0,
- DAG.getConstant(0, PtrVT));
-
- if (ThisBits == PartBits && ThisVT != PartVT) {
- Part0 = DAG.getNode(ISD::BIT_CONVERT, dl,
- PartVT, Part0);
- Part1 = DAG.getNode(ISD::BIT_CONVERT, dl,
- PartVT, Part1);
- }
- }
- }
-
- if (TLI.isBigEndian())
- std::reverse(Parts, Parts + OrigNumParts);
-
- return;
- }
-
- // Vector ValueVT.
- if (NumParts == 1) {
- if (PartVT != ValueVT) {
- if (PartVT.isVector()) {
- Val = DAG.getNode(ISD::BIT_CONVERT, dl, 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, dl,
- PartVT, Val,
- DAG.getConstant(0, PtrVT));
- }
- }
-
- Parts[0] = Val;
- return;
- }
-
- // Handle a multi-element vector.
- EVT IntermediateVT, RegisterVT;
- unsigned NumIntermediates;
- unsigned NumRegs = TLI.getVectorTypeBreakdown(*DAG.getContext(), 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, dl,
- IntermediateVT, Val,
- DAG.getConstant(i * (NumElements / NumIntermediates),
- PtrVT));
- else
- Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl,
- 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, dl, 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, dl, 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();
- EdgeMapping.clear();
- DAG.clear();
- CurDebugLoc = DebugLoc::getUnknownLoc();
- HasTailCall = false;
-}
-
-/// 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, getCurDebugLoc(), 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, getCurDebugLoc(), 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: llvm_unreachable("Unknown instruction type encountered!");
- // 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"
- }
-}
-
-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))) {
- EVT 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) && !V->getType()->isAggregateType())
- return N = DAG.getUNDEF(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)) {
- SmallVector<SDValue, 4> Constants;
- for (User::const_op_iterator OI = C->op_begin(), OE = C->op_end();
- OI != OE; ++OI) {
- SDNode *Val = getValue(*OI).getNode();
- // If the operand is an empty aggregate, there are no values.
- if (!Val) continue;
- // Add each leaf value from the operand to the Constants list
- // to form a flattened list of all the values.
- for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i)
- Constants.push_back(SDValue(Val, i));
- }
- return DAG.getMergeValues(&Constants[0], Constants.size(),
- getCurDebugLoc());
- }
-
- if (isa<StructType>(C->getType()) || isa<ArrayType>(C->getType())) {
- assert((isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) &&
- "Unknown struct or array constant!");
-
- SmallVector<EVT, 4> ValueVTs;
- ComputeValueVTs(TLI, C->getType(), ValueVTs);
- unsigned NumElts = ValueVTs.size();
- if (NumElts == 0)
- return SDValue(); // empty struct
- SmallVector<SDValue, 4> Constants(NumElts);
- for (unsigned i = 0; i != NumElts; ++i) {
- EVT EltVT = ValueVTs[i];
- if (isa<UndefValue>(C))
- Constants[i] = DAG.getUNDEF(EltVT);
- else if (EltVT.isFloatingPoint())
- Constants[i] = DAG.getConstantFP(0, EltVT);
- else
- Constants[i] = DAG.getConstant(0, EltVT);
- }
- return DAG.getMergeValues(&Constants[0], NumElts, getCurDebugLoc());
- }
-
- if (BlockAddress *BA = dyn_cast<BlockAddress>(C))
- return DAG.getBlockAddress(BA, VT);
-
- const VectorType *VecTy = cast<VectorType>(V->getType());
- unsigned NumElements = VecTy->getNumElements();
-
- // Now that we know the number and type of the elements, get that number of
- // elements into the Ops array based on what kind of constant it is.
- SmallVector<SDValue, 16> Ops;
- if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) {
- for (unsigned i = 0; i != NumElements; ++i)
- Ops.push_back(getValue(CP->getOperand(i)));
- } else {
- assert(isa<ConstantAggregateZero>(C) && "Unknown vector constant!");
- EVT EltVT = TLI.getValueType(VecTy->getElementType());
-
- SDValue Op;
- if (EltVT.isFloatingPoint())
- Op = DAG.getConstantFP(0, EltVT);
- else
- Op = DAG.getConstant(0, EltVT);
- Ops.assign(NumElements, Op);
- }
-
- // Create a BUILD_VECTOR node.
- return NodeMap[V] = DAG.getNode(ISD::BUILD_VECTOR, getCurDebugLoc(),
- VT, &Ops[0], Ops.size());
- }
-
- // If this is a static alloca, generate it as the frameindex instead of
- // computation.
- if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
- DenseMap<const AllocaInst*, int>::iterator SI =
- FuncInfo.StaticAllocaMap.find(AI);
- if (SI != FuncInfo.StaticAllocaMap.end())
- return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
- }
-
- unsigned InReg = FuncInfo.ValueMap[V];
- assert(InReg && "Value not in map!");
-
- RegsForValue RFV(*DAG.getContext(), TLI, InReg, V->getType());
- SDValue Chain = DAG.getEntryNode();
- return RFV.getCopyFromRegs(DAG, getCurDebugLoc(), Chain, NULL);
-}
-
-/// Get the EVTs and ArgFlags collections that represent the return type
-/// of the given function. This does not require a DAG or a return value, and
-/// is suitable for use before any DAGs for the function are constructed.
-static void getReturnInfo(const Type* ReturnType,
- Attributes attr, SmallVectorImpl<EVT> &OutVTs,
- SmallVectorImpl<ISD::ArgFlagsTy> &OutFlags,
- TargetLowering &TLI,
- SmallVectorImpl<uint64_t> *Offsets = 0) {
- SmallVector<EVT, 4> ValueVTs;
- ComputeValueVTs(TLI, ReturnType, ValueVTs, Offsets);
- unsigned NumValues = ValueVTs.size();
- if ( NumValues == 0 ) return;
-
- for (unsigned j = 0, f = NumValues; j != f; ++j) {
- EVT VT = ValueVTs[j];
- ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
-
- if (attr & Attribute::SExt)
- ExtendKind = ISD::SIGN_EXTEND;
- else if (attr & Attribute::ZExt)
- ExtendKind = ISD::ZERO_EXTEND;
-
- // FIXME: C calling convention requires the return type to be promoted to
- // at least 32-bit. But this is not necessary for non-C calling
- // conventions. The frontend should mark functions whose return values
- // require promoting with signext or zeroext attributes.
- if (ExtendKind != ISD::ANY_EXTEND && VT.isInteger()) {
- EVT MinVT = TLI.getRegisterType(ReturnType->getContext(), MVT::i32);
- if (VT.bitsLT(MinVT))
- VT = MinVT;
- }
-
- unsigned NumParts = TLI.getNumRegisters(ReturnType->getContext(), VT);
- EVT PartVT = TLI.getRegisterType(ReturnType->getContext(), VT);
- // 'inreg' on function refers to return value
- ISD::ArgFlagsTy Flags = ISD::ArgFlagsTy();
- if (attr & Attribute::InReg)
- Flags.setInReg();
-
- // Propagate extension type if any
- if (attr & Attribute::SExt)
- Flags.setSExt();
- else if (attr & Attribute::ZExt)
- Flags.setZExt();
-
- for (unsigned i = 0; i < NumParts; ++i) {
- OutVTs.push_back(PartVT);
- OutFlags.push_back(Flags);
- }
- }
-}
-
-void SelectionDAGLowering::visitRet(ReturnInst &I) {
- SDValue Chain = getControlRoot();
- SmallVector<ISD::OutputArg, 8> Outs;
- FunctionLoweringInfo &FLI = DAG.getFunctionLoweringInfo();
-
- if (!FLI.CanLowerReturn) {
- unsigned DemoteReg = FLI.DemoteRegister;
- const Function *F = I.getParent()->getParent();
-
- // Emit a store of the return value through the virtual register.
- // Leave Outs empty so that LowerReturn won't try to load return
- // registers the usual way.
- SmallVector<EVT, 1> PtrValueVTs;
- ComputeValueVTs(TLI, PointerType::getUnqual(F->getReturnType()),
- PtrValueVTs);
-
- SDValue RetPtr = DAG.getRegister(DemoteReg, PtrValueVTs[0]);
- SDValue RetOp = getValue(I.getOperand(0));
-
- SmallVector<EVT, 4> ValueVTs;
- SmallVector<uint64_t, 4> Offsets;
- ComputeValueVTs(TLI, I.getOperand(0)->getType(), ValueVTs, &Offsets);
- unsigned NumValues = ValueVTs.size();
-
- SmallVector<SDValue, 4> Chains(NumValues);
- EVT PtrVT = PtrValueVTs[0];
- for (unsigned i = 0; i != NumValues; ++i)
- Chains[i] = DAG.getStore(Chain, getCurDebugLoc(),
- SDValue(RetOp.getNode(), RetOp.getResNo() + i),
- DAG.getNode(ISD::ADD, getCurDebugLoc(), PtrVT, RetPtr,
- DAG.getConstant(Offsets[i], PtrVT)),
- NULL, Offsets[i], false, 0);
- Chain = DAG.getNode(ISD::TokenFactor, getCurDebugLoc(),
- MVT::Other, &Chains[0], NumValues);
- }
- else {
- for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
- SmallVector<EVT, 4> ValueVTs;
- ComputeValueVTs(TLI, I.getOperand(i)->getType(), ValueVTs);
- unsigned NumValues = ValueVTs.size();
- if (NumValues == 0) continue;
-
- SDValue RetOp = getValue(I.getOperand(i));
- for (unsigned j = 0, f = NumValues; j != f; ++j) {
- EVT VT = ValueVTs[j];
-
- ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
-
- const Function *F = I.getParent()->getParent();
- if (F->paramHasAttr(0, Attribute::SExt))
- ExtendKind = ISD::SIGN_EXTEND;
- else if (F->paramHasAttr(0, Attribute::ZExt))
- ExtendKind = ISD::ZERO_EXTEND;
-
- // FIXME: C calling convention requires the return type to be promoted to
- // at least 32-bit. But this is not necessary for non-C calling
- // conventions. The frontend should mark functions whose return values
- // require promoting with signext or zeroext attributes.
- if (ExtendKind != ISD::ANY_EXTEND && VT.isInteger()) {
- EVT MinVT = TLI.getRegisterType(*DAG.getContext(), MVT::i32);
- if (VT.bitsLT(MinVT))
- VT = MinVT;
- }
-
- unsigned NumParts = TLI.getNumRegisters(*DAG.getContext(), VT);
- EVT PartVT = TLI.getRegisterType(*DAG.getContext(), VT);
- SmallVector<SDValue, 4> Parts(NumParts);
- getCopyToParts(DAG, getCurDebugLoc(),
- SDValue(RetOp.getNode(), RetOp.getResNo() + j),
- &Parts[0], NumParts, PartVT, ExtendKind);
-
- // 'inreg' on function refers to return value
- ISD::ArgFlagsTy Flags = ISD::ArgFlagsTy();
- if (F->paramHasAttr(0, Attribute::InReg))
- Flags.setInReg();
-
- // Propagate extension type if any
- if (F->paramHasAttr(0, Attribute::SExt))
- Flags.setSExt();
- else if (F->paramHasAttr(0, Attribute::ZExt))
- Flags.setZExt();
-
- for (unsigned i = 0; i < NumParts; ++i)
- Outs.push_back(ISD::OutputArg(Flags, Parts[i], /*isfixed=*/true));
- }
- }
- }
-
- bool isVarArg = DAG.getMachineFunction().getFunction()->isVarArg();
- CallingConv::ID CallConv =
- DAG.getMachineFunction().getFunction()->getCallingConv();
- Chain = TLI.LowerReturn(Chain, CallConv, isVarArg,
- Outs, getCurDebugLoc(), DAG);
-
- // Verify that the target's LowerReturn behaved as expected.
- assert(Chain.getNode() && Chain.getValueType() == MVT::Other &&
- "LowerReturn didn't return a valid chain!");
-
- // Update the DAG with the new chain value resulting from return lowering.
- DAG.setRoot(Chain);
-}
-
-/// CopyToExportRegsIfNeeded - If the given value has virtual registers
-/// created for it, emit nodes to copy the value into the virtual
-/// registers.
-void SelectionDAGLowering::CopyToExportRegsIfNeeded(Value *V) {
- if (!V->use_empty()) {
- DenseMap<const Value *, unsigned>::iterator VMI = FuncInfo.ValueMap.find(V);
- if (VMI != FuncInfo.ValueMap.end())
- CopyValueToVirtualRegister(V, VMI->second);
- }
-}
-
-/// ExportFromCurrentBlock - If this condition isn't known to be exported from
-/// the current basic block, add it to ValueMap now so that we'll get a
-/// CopyTo/FromReg.
-void SelectionDAGLowering::ExportFromCurrentBlock(Value *V) {
- // No need to export constants.
- if (!isa<Instruction>(V) && !isa<Argument>(V)) return;
-
- // Already exported?
- if (FuncInfo.isExportedInst(V)) return;
-
- unsigned Reg = FuncInfo.InitializeRegForValue(V);
- CopyValueToVirtualRegister(V, Reg);
-}
-
-bool SelectionDAGLowering::isExportableFromCurrentBlock(Value *V,
- const BasicBlock *FromBB) {
- // The operands of the setcc have to be in this block. We don't know
- // how to export them from some other block.
- if (Instruction *VI = dyn_cast<Instruction>(V)) {
- // Can export from current BB.
- if (VI->getParent() == FromBB)
- return true;
-
- // Is already exported, noop.
- return FuncInfo.isExportedInst(V);
- }
-
- // If this is an argument, we can export it if the BB is the entry block or
- // if it is already exported.
- if (isa<Argument>(V)) {
- if (FromBB == &FromBB->getParent()->getEntryBlock())
- return true;
-
- // Otherwise, can only export this if it is already exported.
- return FuncInfo.isExportedInst(V);
- }
-
- // Otherwise, constants can always be exported.
- return true;
-}
-
-static bool InBlock(const Value *V, const BasicBlock *BB) {
- if (const Instruction *I = dyn_cast<Instruction>(V))
- return I->getParent() == BB;
- return true;
-}
-
-/// getFCmpCondCode - Return the ISD condition code corresponding to
-/// the given LLVM IR floating-point condition code. This includes
-/// consideration of global floating-point math flags.
-///
-static ISD::CondCode getFCmpCondCode(FCmpInst::Predicate Pred) {
- ISD::CondCode FPC, FOC;
- switch (Pred) {
- case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break;
- case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break;
- case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break;
- case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break;
- case FCmpInst::FCMP_OLT: FOC = ISD::SETLT;