diff options
Diffstat (limited to 'llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 864 |
1 files changed, 758 insertions, 106 deletions
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index acf3daa32f5..f02bdcd95b1 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -1,4 +1,4 @@ -//===-- SelectionDAG.cpp - Implement the SelectionDAG* classes ------------===// +//===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===// // // The LLVM Compiler Infrastructure // @@ -7,125 +7,777 @@ // //===----------------------------------------------------------------------===// // -// This file implements the SelectionDAG* classes, which are used to perform -// DAG-based instruction selection in a target-specific manner. +// This implements the SelectionDAG class. // //===----------------------------------------------------------------------===// #include "llvm/CodeGen/SelectionDAG.h" -#include "llvm/Type.h" +#include "llvm/Constants.h" +#include "llvm/GlobalValue.h" +#include "llvm/Assembly/Writer.h" +#include "llvm/CodeGen/MachineBasicBlock.h" #include <iostream> - +#include <cmath> using namespace llvm; +/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) +/// when given the operation for (X op Y). +ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { + // To perform this operation, we just need to swap the L and G bits of the + // operation. + unsigned OldL = (Operation >> 2) & 1; + unsigned OldG = (Operation >> 1) & 1; + return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits + (OldL << 1) | // New G bit + (OldG << 2)); // New L bit. +} + +/// getSetCCInverse - Return the operation corresponding to !(X op Y), where +/// 'op' is a valid SetCC operation. +ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { + unsigned Operation = Op; + if (isInteger) + Operation ^= 7; // Flip L, G, E bits, but not U. + else + Operation ^= 15; // Flip all of the condition bits. + if (Operation > ISD::SETTRUE2) + Operation &= ~8; // Don't let N and U bits get set. + return ISD::CondCode(Operation); +} + + +/// isSignedOp - For an integer comparison, return 1 if the comparison is a +/// signed operation and 2 if the result is an unsigned comparison. Return zero +/// if the operation does not depend on the sign of the input (setne and seteq). +static int isSignedOp(ISD::CondCode Opcode) { + switch (Opcode) { + default: assert(0 && "Illegal integer setcc operation!"); + case ISD::SETEQ: + case ISD::SETNE: return 0; + case ISD::SETLT: + case ISD::SETLE: + case ISD::SETGT: + case ISD::SETGE: return 1; + case ISD::SETULT: + case ISD::SETULE: + case ISD::SETUGT: + case ISD::SETUGE: return 2; + } +} + +/// getSetCCOrOperation - Return the result of a logical OR between different +/// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function +/// returns SETCC_INVALID if it is not possible to represent the resultant +/// comparison. +ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, + bool isInteger) { + if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) + // Cannot fold a signed integer setcc with an unsigned integer setcc. + return ISD::SETCC_INVALID; + + unsigned Op = Op1 | Op2; // Combine all of the condition bits. + + // If the N and U bits get set then the resultant comparison DOES suddenly + // care about orderedness, and is true when ordered. + if (Op > ISD::SETTRUE2) + Op &= ~16; // Clear the N bit. + return ISD::CondCode(Op); +} + +/// getSetCCAndOperation - Return the result of a logical AND between different +/// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This +/// function returns zero if it is not possible to represent the resultant +/// comparison. +ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, + bool isInteger) { + if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) + // Cannot fold a signed setcc with an unsigned setcc. + return ISD::SETCC_INVALID; + + // Combine all of the condition bits. + return ISD::CondCode(Op1 & Op2); +} + SelectionDAG::~SelectionDAG() { for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) delete AllNodes[i]; } +SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) { + assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); + // Mask out any bits that are not valid for this constant. + Val &= (1ULL << MVT::getSizeInBits(VT)) - 1; -/// dump - Print out the current Selection DAG... -void SelectionDAG::dump() const { - Root->dump(); // Print from the root... + SDNode *&N = Constants[std::make_pair(Val, VT)]; + if (N) return SDOperand(N, 0); + N = new ConstantSDNode(Val, VT); + AllNodes.push_back(N); + return SDOperand(N, 0); } -/// getValueType - Return the ValueType for the specified LLVM type. This -/// method works on all scalar LLVM types. +SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) { + assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); + if (VT == MVT::f32) + Val = (float)Val; // Mask out extra precision. + + SDNode *&N = ConstantFPs[std::make_pair(Val, VT)]; + if (N) return SDOperand(N, 0); + N = new ConstantFPSDNode(Val, VT); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + + + +SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, + MVT::ValueType VT) { + SDNode *&N = GlobalValues[GV]; + if (N) return SDOperand(N, 0); + N = new GlobalAddressSDNode(GV,VT); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) { + SDNode *&N = FrameIndices[FI]; + if (N) return SDOperand(N, 0); + N = new FrameIndexSDNode(FI, VT); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +SDOperand SelectionDAG::getConstantPool(unsigned CPIdx, MVT::ValueType VT) { + SDNode *N = ConstantPoolIndices[CPIdx]; + if (N) return SDOperand(N, 0); + N = new ConstantPoolSDNode(CPIdx, VT); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { + SDNode *&N = BBNodes[MBB]; + if (N) return SDOperand(N, 0); + N = new BasicBlockSDNode(MBB); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) { + SDNode *&N = ExternalSymbols[Sym]; + if (N) return SDOperand(N, 0); + N = new ExternalSymbolSDNode(Sym, VT); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, SDOperand N1, + SDOperand N2) { + // These setcc operations always fold. + switch (Cond) { + default: break; + case ISD::SETFALSE: + case ISD::SETFALSE2: return getConstant(0, MVT::i1); + case ISD::SETTRUE: + case ISD::SETTRUE2: return getConstant(1, MVT::i1); + } + + if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) + if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) { + uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); + + // Sign extend the operands if required + if (ISD::isSignedIntSetCC(Cond)) { + C1 = N1C->getSignExtended(); + C2 = N2C->getSignExtended(); + } + + switch (Cond) { + default: assert(0 && "Unknown integer setcc!"); + case ISD::SETEQ: return getConstant(C1 == C2, MVT::i1); + case ISD::SETNE: return getConstant(C1 != C2, MVT::i1); + case ISD::SETULT: return getConstant(C1 < C2, MVT::i1); + case ISD::SETUGT: return getConstant(C1 > C2, MVT::i1); + case ISD::SETULE: return getConstant(C1 <= C2, MVT::i1); + case ISD::SETUGE: return getConstant(C1 >= C2, MVT::i1); + case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); + case ISD::SETGT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); + case ISD::SETLE: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); + case ISD::SETGE: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); + } + } else { + // Ensure that the constant occurs on the RHS. + Cond = ISD::getSetCCSwappedOperands(Cond); + std::swap(N1, N2); + } + + if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) + if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) { + double C1 = N1C->getValue(), C2 = N2C->getValue(); + + switch (Cond) { + default: break; // FIXME: Implement the rest of these! + case ISD::SETEQ: return getConstant(C1 == C2, MVT::i1); + case ISD::SETNE: return getConstant(C1 != C2, MVT::i1); + case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); + case ISD::SETGT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); + case ISD::SETLE: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); + case ISD::SETGE: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); + } + } else { + // Ensure that the constant occurs on the RHS. + Cond = ISD::getSetCCSwappedOperands(Cond); + std::swap(N1, N2); + } + + if (N1 == N2) { + // We can always fold X == Y for integer setcc's. + if (MVT::isInteger(N1.getValueType())) + return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1); + unsigned UOF = ISD::getUnorderedFlavor(Cond); + if (UOF == 2) // FP operators that are undefined on NaNs. + return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1); + if (UOF == ISD::isTrueWhenEqual(Cond)) + return getConstant(UOF, MVT::i1); + // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO + // if it is not already. + Cond = UOF == 0 ? ISD::SETUO : ISD::SETO; + } + + + SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2), Cond)]; + if (N) return SDOperand(N, 0); + N = new SetCCSDNode(Cond, N1, N2); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + + + +/// getNode - Gets or creates the specified node. /// -MVT::ValueType SelectionDAG::getValueType(const Type *Ty) const { - switch (Ty->getTypeID()) { - case Type::VoidTyID: assert(0 && "Void type object in getValueType!"); - default: assert(0 && "Unknown type in DAGBuilder!\n"); - case Type::BoolTyID: return MVT::i1; - case Type::SByteTyID: - case Type::UByteTyID: return MVT::i8; - case Type::ShortTyID: - case Type::UShortTyID: return MVT::i16; - case Type::IntTyID: - case Type::UIntTyID: return MVT::i32; - case Type::LongTyID: - case Type::ULongTyID: return MVT::i64; - case Type::FloatTyID: return MVT::f32; - case Type::DoubleTyID: return MVT::f64; - case Type::LabelTyID: - case Type::PointerTyID: return PointerType; - } -} - -void SelectionDAGNode::dump() const { - // Print out the DAG in post-order - std::map<const SelectionDAGNode*, unsigned> NodeIDs; - unsigned ID = 0; - printit(0, ID, NodeIDs); -} - -void SelectionDAGNode::printit(unsigned Offset, unsigned &LastID, - std::map<const SelectionDAGNode*, - unsigned> &NodeIDs) const { - if (!NodeIDs.count(this)) { - // Emit all of the uses first... - for (unsigned i = 0, e = Uses.size(); i != e; ++i) - Uses[i]->printit(Offset+1, LastID, NodeIDs); - - NodeIDs[this] = LastID++; - - std::cerr << std::string(Offset, ' ') << "#" << LastID-1 << " "; - } else { - // Node has already been emitted... - std::cerr << std::string(Offset, ' ') << "#" << NodeIDs[this] << " "; - } - - switch (ValueType) { - case MVT::isVoid: std::cerr << "V:"; break; - case MVT::i1: std::cerr << "i1:"; break; - case MVT::i8: std::cerr << "i8:"; break; - case MVT::i16: std::cerr << "i16:"; break; - case MVT::i32: std::cerr << "i32:"; break; - case MVT::i64: std::cerr << "i64:"; break; - case MVT::f32: std::cerr << "f32:"; break; - case MVT::f64: std::cerr << "f64:"; break; - default: assert(0 && "Invalid node ValueType!"); - } - switch (NodeType) { - case ISD::ChainNode: std::cerr << "ChainNode"; break; - case ISD::BlockChainNode: std::cerr << "BlockChainNode"; break; - case ISD::ProtoNode: std::cerr << "ProtoNode"; break; - - case ISD::Constant: std::cerr << "Constant"; break; - case ISD::FrameIndex: std::cerr << "FrameIndex"; break; - case ISD::BasicBlock: std::cerr << "BasicBlock"; break; - - case ISD::Plus: std::cerr << "Plus"; break; - case ISD::Minus: std::cerr << "Minus"; break; - case ISD::Times: std::cerr << "Times"; break; - case ISD::SDiv: std::cerr << "SDiv"; break; - case ISD::UDiv: std::cerr << "UDiv"; break; - case ISD::SRem: std::cerr << "SRem"; break; - case ISD::URem: std::cerr << "URem"; break; - case ISD::And: std::cerr << "And"; break; - case ISD::Or: std::cerr << "Or"; break; - case ISD::Xor: std::cerr << "Xor"; break; - - case ISD::SetEQ: std::cerr << "SetEQ"; break; - case ISD::SetNE: std::cerr << "SetNE"; break; - case ISD::SetLT: std::cerr << "SetLT"; break; - case ISD::SetLE: std::cerr << "SetLE"; break; - case ISD::SetGT: std::cerr << "SetGT"; break; - case ISD::SetGE: std::cerr << "SetGE"; break; - - case ISD::Br: std::cerr << "Br"; break; - case ISD::BrCond: std::cerr << "BrCond"; break; - case ISD::Switch: std::cerr << "Switch"; break; - case ISD::Ret: std::cerr << "Ret"; break; - case ISD::RetVoid: std::cerr << "RetVoid"; break; - case ISD::Load: std::cerr << "Load"; break; - case ISD::Store: std::cerr << "Store"; break; - case ISD::PHI: std::cerr << "PHI"; break; - case ISD::Call: std::cerr << "Call"; break; - - case ISD::Unspec1: std::cerr << "Unspec1"; break; - case ISD::Unspec2: std::cerr << "Unspec2"; break; - } - - std::cerr << "\n"; +SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) { + SDNode *N = new SDNode(Opcode, VT); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +static const Type *getTypeFor(MVT::ValueType VT) { + switch (VT) { + default: assert(0 && "Unknown MVT!"); + case MVT::i1: return Type::BoolTy; + case MVT::i8: return Type::UByteTy; + case MVT::i16: return Type::UShortTy; + case MVT::i32: return Type::UIntTy; + case MVT::i64: return Type::ULongTy; + case MVT::f32: return Type::FloatTy; + case MVT::f64: return Type::DoubleTy; + } +} + +SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, + SDOperand Operand) { + if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) { + uint64_t Val = C->getValue(); + switch (Opcode) { + default: break; + case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT); + case ISD::ZERO_EXTEND: return getConstant(Val, VT); + case ISD::TRUNCATE: return getConstant(Val, VT); + } + } + + if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) + switch (Opcode) { + case ISD::FP_ROUND: + case ISD::FP_EXTEND: + return getConstantFP(C->getValue(), VT); + } + + unsigned OpOpcode = Operand.Val->getOpcode(); + switch (Opcode) { + case ISD::SIGN_EXTEND: + if (Operand.getValueType() == VT) return Operand; // noop extension + if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) + return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); + break; + case ISD::ZERO_EXTEND: + if (Operand.getValueType() == VT) return Operand; // noop extension + if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) + return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); + break; + case ISD::TRUNCATE: + if (Operand.getValueType() == VT) return Operand; // noop truncate + if (OpOpcode == ISD::TRUNCATE) + return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); + break; + } + + SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))]; + if (N) return SDOperand(N, 0); + N = new SDNode(Opcode, Operand); + N->setValueTypes(VT); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +static bool isCommutativeBinOp(unsigned Opcode) { + switch (Opcode) { + case ISD::ADD: + case ISD::MUL: + case ISD::AND: + case ISD::OR: + case ISD::XOR: return true; + default: return false; // FIXME: Need commutative info for user ops! + } +} + +static bool isAssociativeBinOp(unsigned Opcode) { + switch (Opcode) { + case ISD::ADD: + case ISD::MUL: + case ISD::AND: + case ISD::OR: + case ISD::XOR: return true; + default: return false; // FIXME: Need associative info for user ops! + } +} + +static unsigned ExactLog2(uint64_t Val) { + unsigned Count = 0; + while (Val != 1) { + Val >>= 1; + ++Count; + } + return Count; } + +// isInvertibleForFree - Return true if there is no cost to emitting the logical +// inverse of this node. +static bool isInvertibleForFree(SDOperand N) { + if (isa<ConstantSDNode>(N.Val)) return true; + if (isa<SetCCSDNode>(N.Val) && N.Val->hasOneUse()) + return true; + return false; +} + + +SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, + SDOperand N1, SDOperand N2) { + ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); + ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); + if (N1C) { + if (N2C) { + uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); + switch (Opcode) { + case ISD::ADD: return getConstant(C1 + C2, VT); + case ISD::SUB: return getConstant(C1 - C2, VT); + case ISD::MUL: return getConstant(C1 * C2, VT); + case ISD::UDIV: + if (C2) return getConstant(C1 / C2, VT); + break; + case ISD::UREM : + if (C2) return getConstant(C1 % C2, VT); + break; + case ISD::SDIV : + if (C2) return getConstant(N1C->getSignExtended() / + N2C->getSignExtended(), VT); + break; + case ISD::SREM : + if (C2) return getConstant(N1C->getSignExtended() % + N2C->getSignExtended(), VT); + break; + case ISD::AND : return getConstant(C1 & C2, VT); + case ISD::OR : return getConstant(C1 | C2, VT); + case ISD::XOR : return getConstant(C1 ^ C2, VT); + default: break; + } + + } else { // Cannonicalize constant to RHS if commutative + if (isCommutativeBinOp(Opcode)) { + std::swap(N1C, N2C); + std::swap(N1, N2); + } + } + } + + if (N2C) { + uint64_t C2 = N2C->getValue(); + + switch (Opcode) { + case ISD::ADD: + if (!C2) return N1; // add X, 0 -> X + break; + case ISD::SUB: + if (!C2) return N1; // sub X, 0 -> X + break; + case ISD::MUL: + if (!C2) return N2; // mul X, 0 -> 0 + if (N2C->isAllOnesValue()) // mul X, -1 -> 0-X + return getNode(ISD::SUB, VT, getConstant(0, VT), N1); + + // FIXME: This should only be done if the target supports shift + // operations. + if ((C2 & C2-1) == 0) { + SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8); + return getNode(ISD::SHL, VT, N1, ShAmt); + } + break; + + case ISD::UDIV: + // FIXME: This should only be done if the target supports shift + // operations. + if ((C2 & C2-1) == 0 && C2) { + SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8); + return getNode(ISD::SRL, VT, N1, ShAmt); + } + break; + + case ISD::AND: + if (!C2) return N2; // X and 0 -> 0 + if (N2C->isAllOnesValue()) + return N1; // X and -1 -> X + break; + case ISD::OR: + if (!C2)return N1; // X or 0 -> X + if (N2C->isAllOnesValue()) + return N2; // X or -1 -> -1 + break; + case ISD::XOR: + if (!C2) return N1; // X xor 0 -> X + if (N2C->isAllOnesValue()) { + if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N1.Val)){ + // !(X op Y) -> (X !op Y) + bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType()); + return getSetCC(ISD::getSetCCInverse(SetCC->getCondition(),isInteger), + SetCC->getOperand(0), SetCC->getOperand(1)); + } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) { + SDNode *Op = N1.Val; + // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible + // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible + SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1); + if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) { + LHS = getNode(ISD::XOR, VT, LHS, N2); // RHS = ~LHS + RHS = getNode(ISD::XOR, VT, RHS, N2); // RHS = ~RHS + if (Op->getOpcode() == ISD::AND) + return getNode(ISD::OR, VT, LHS, RHS); + return getNode(ISD::AND, VT, LHS, RHS); + } + } + // X xor -1 -> not(x) ? + } + break; + } + + // Reassociate ((X op C1) op C2) if possible. + if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode)) + if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1))) + return getNode(Opcode, VT, N3C->getOperand(0), + getNode(Opcode, VT, N2, N1.Val->getOperand(1))); + } + + ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val); + ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val); + if (N1CFP) + if (N2CFP) { + double C1 = N1CFP->getValue(), C2 = N2CFP->getValue(); + switch (Opcode) { + case ISD::ADD: return getConstantFP(C1 + C2, VT); + case ISD::SUB: return getConstantFP(C1 - C2, VT); + case ISD::MUL: return getConstantFP(C1 * C2, VT); + case ISD::SDIV: + if (C2) return getConstantFP(C1 / C2, VT); + break; + case ISD::SREM : + if (C2) return getConstantFP(fmod(C1, C2), VT); + break; + default: break; + } + + } else { // Cannonicalize constant to RHS if commutative + if (isCommutativeBinOp(Opcode)) { + std::swap(N1CFP, N2CFP); + std::swap(N1, N2); + } + } + + // Finally, fold operations that do not require constants. + switch (Opcode) { + case ISD::AND: + case ISD::OR: + if (SetCCSDNode *LHS = dyn_cast<SetCCSDNode>(N1.Val)) + if (SetCCSDNode *RHS = dyn_cast<SetCCSDNode>(N2.Val)) { + SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0); + SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1); + ISD::CondCode Op2 = RHS->getCondition(); + + // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y) + if (LL == RR && LR == RL) { + Op2 = ISD::getSetCCSwappedOperands(Op2); + goto MatchedBackwards; + } + + if (LL == RL && LR == RR) { + MatchedBackwards: + ISD::CondCode Result; + bool isInteger = MVT::isInteger(LL.getValueType()); + if (Opcode == ISD::OR) + Result = ISD::getSetCCOrOperation(LHS->getCondition(), Op2, + isInteger); + else + Result = ISD::getSetCCAndOperation(LHS->getCondition(), Op2, + isInteger); + if (Result != ISD::SETCC_INVALID) + return getSetCC(Result, LL, LR); + } + } + break; + case ISD::XOR: + if (N1 == N2) return getConstant(0, VT); // xor X, Y -> 0 + break; + } + + SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))]; + if (N) return SDOperand(N, 0); + N = new SDNode(Opcode, N1, N2); + N->setValueTypes(VT); + + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +SDOperand SelectionDAG::getLoad(MVT::ValueType VT, + SDOperand Chain, SDOperand Ptr) { + SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))]; + if (N) return SDOperand(N, 0); + N = new SDNode(ISD::LOAD, Chain, Ptr); + + // Loads have a token chain. + N->setValueTypes(VT, MVT::Other); + AllNodes.push_back(N); + return SDOperand(N, 0); +} + + +SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, + SDOperand N1, SDOperand N2, SDOperand N3) { + // Perform various simplifications. + ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); + ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); + ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); + switch (Opcode) { + case ISD::SELECT: + if (N1C) + if (N1C->getValue()) + return N2; // select true, X, Y -> X + else + return N3; // select false, X, Y -> Y + + if (N2 == N3) return N2; // select C, X, X -> X + + if (VT == MVT::i1) { // Boolean SELECT + if (N2C) { + if (N3C) { + if (N2C->getValue()) // select C, 1, 0 -> C + return N1; + return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C + } + + if (N2C->getValue()) // select C, 1, X -> C | X + return getNode(ISD::OR, VT, N1, N3); + else // select C, 0, X -> ~C & X + return getNode(ISD::AND, VT, + getNode(ISD::XOR, N1.getValueType(), N1, + getConstant(1, N1.getValueType())), N3); + } else if (N3C) { + if (N3C->getValue()) // select C, X, 1 -> ~C | X + return getNode(ISD::OR, VT, + getNode(ISD::XOR, N1.getValueType(), N1, + getConstant(1, N1.getValueType())), N2); + else // select C, X, 0 -> C & X + return getNode(ISD::AND, VT, N1, N2); + } + } + + break; + } + + SDNode *N = new SDNode(Opcode, N1, N2, N3); + switch (Opcode) { + default: + N->setValueTypes(VT); + break; + case ISD::DYNAMIC_STACKALLOC: // DYNAMIC_STACKALLOC produces pointer and chain + N->setValueTypes(VT, MVT::Other); + break; + } + + // FIXME: memoize NODES + AllNodes.push_back(N); + return SDOperand(N, 0); +} + +SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, + std::vector<SDOperand> &Children) { + switch (Children.size()) { + case 0: return getNode(Opcode, VT); + case 1: return getNode(Opcode, VT, Children[0]); + case 2: return getNode(Opcode, VT, Children[0], Children[1]); + case 3: return getNode(Opcode, VT, Children[0], Children[1], Children[2]); + default: + // FIXME: MEMOIZE!! + SDNode *N = new SDNode(Opcode, Children); + N->setValueTypes(VT); + AllNodes.push_back(N); + return SDOperand(N, 0); + } +} + + + +void SDNode::dump() const { + std::cerr << (void*)this << ": "; + + for (unsigned i = 0, e = getNumValues(); i != e; ++i) { + if (i) std::cerr << ","; + switch (getValueType(i)) { + default: assert(0 && "Unknown value type!"); + case MVT::i1: std::cerr << "i1"; break; + case MVT::i8: std::cerr << "i8"; break; + case MVT::i16: std::cerr << "i16"; break; + case MVT::i32: std::cerr << "i32"; break; + case MVT::i64: std::cerr << "i64"; break; + case MVT::f32: std::cerr << "f32"; break; + case MVT::f64: std::cerr << "f64"; break; + case MVT::Other: std::cerr << "ch"; break; + } + } + std::cerr << " = "; + + switch (getOpcode()) { + default: std::cerr << "<<Unknown>>"; break; + case ISD::EntryToken: std::cerr << "EntryToken"; break; + case ISD::Constant: std::cerr << "Constant"; break; + case ISD::ConstantFP: std::cerr << "ConstantFP"; break; + case ISD::GlobalAddress: std::cerr << "GlobalAddress"; break; + case ISD::FrameIndex: std::cerr << "FrameIndex"; break; + case ISD::BasicBlock: std::cerr << "BasicBlock"; break; + case ISD::ExternalSymbol: std::cerr << "ExternalSymbol"; break; + case ISD::ConstantPool: std::cerr << "ConstantPoolIndex"; break; + case ISD::CopyToReg: std::cerr << "CopyToReg"; break; + case ISD::CopyFromReg: std::cerr << "CopyFromReg"; break; + + case ISD::ADD: std::cerr << "add"; break; + case ISD::SUB: std::cerr << "sub"; break; + case ISD::MUL: std::cerr << "mul"; break; + case ISD::SDIV: std::cerr << "sdiv"; break; + case ISD::UDIV: std::cerr << "udiv"; break; + case ISD::SREM: std::cerr << "srem"; break; + case ISD::UREM: std::cerr << "urem"; break; + case ISD::AND: std::cerr << "and"; break; + case ISD::OR: std::cerr << "or"; break; + case ISD::XOR: std::cerr << "xor"; break; + case ISD::SHL: std::cerr << "shl"; break; + case ISD::SRA: std::cerr << "sra"; break; + case ISD::SRL: std::cerr << "srl"; break; + + case ISD::SETCC: std::cerr << "setcc"; break; + case ISD::SELECT: std::cerr << "select"; break; + case ISD::ADDC: std::cerr << "addc"; break; + case ISD::SUBB: std::cerr << "subb"; break; + + // Conversion operators. + case ISD::SIGN_EXTEND: std::cerr << "sign_extend"; break; + case ISD::ZERO_EXTEND: std::cerr << "zero_extend"; break; + case ISD::TRUNCATE: std::cerr << "truncate"; break; + case ISD::FP_ROUND: std::cerr << "fp_round"; break; + case ISD::FP_EXTEND: std::cerr << "fp_extend"; break; + + // Control flow instructions + case ISD::BR: std::cerr << "br"; break; + case ISD::BRCOND: std::cerr << "brcond"; break; + case ISD::RET: std::cerr << "ret"; break; + case ISD::CALL: std::cerr << "call"; break; + case ISD::ADJCALLSTACKDOWN: std::cerr << "adjcallstackdown"; break; + case ISD::ADJCALLSTACKUP: std::cerr << "adjcallstackup"; break; + + // Other operators + case ISD::LOAD: std::cerr << "load"; break; + case ISD::STORE: std::cerr << "store"; break; + case ISD::DYNAMIC_STACKALLOC: std::cerr << "dynamic_stackalloc"; break; + case ISD::EXTRACT_ELEMENT: std::cerr << "extract_element"; break; + case ISD::BUILD_PAIR: std::cerr << "build_pair"; break; + } + + std::cerr << " "; + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + if (i) std::cerr << ", "; + std::cerr << (void*)getOperand(i).Val; + if (unsigned RN = getOperand(i).ResNo) + std::cerr << ":" << RN; + } + + if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) { + std::cerr << "<" << CSDN->getValue() << ">"; + } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) { + std::cerr << "<" << CSDN->getValue() << ">"; + } else if (const GlobalAddressSDNode *GADN = + dyn_cast<GlobalAddressSDNode>(this)) { + std::cerr << "<"; + WriteAsOperand(std::cerr, GADN->getGlobal()) << ">"; + } else if (const FrameIndexSDNode *FIDN = + dyn_cast<FrameIndexSDNode>(this)) { + std::cerr << "<" << FIDN->getIndex() << ">"; + } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){ + std::cerr << "<" << CP->getIndex() << ">"; + } else if (const BasicBlockSDNode *BBDN = + dyn_cast<BasicBlockSDNode>(this)) { + std::cerr << "<"; + const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); + if (LBB) + std::cerr << LBB->getName() << " "; + std::cerr << (const void*)BBDN->getBasicBlock() << ">"; + } else if (const CopyRegSDNode *C2V = dyn_cast<CopyRegSDNode>(this)) { + std::cerr << "<reg #" << C2V->getReg() << ">"; + } else if (const ExternalSymbolSDNode *ES = + dyn_cast<ExternalSymbolSDNode>(this)) { + std::cerr << "'" << ES->getSymbol() << "'"; + } else if (const SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(this)) { + std::cerr << " - condition = "; + switch (SetCC->getCondition()) { + default: assert(0 && "Unknown setcc condition!"); + case ISD::SETOEQ: std::cerr << "setoeq"; break; + case ISD::SETOGT: std::cerr << "setogt"; break; + case ISD::SETOGE: std::cerr << "setoge"; break; + case ISD::SETOLT: std::cerr << "setolt"; break; + case ISD::SETOLE: std::cerr << "setole"; break; + case ISD::SETONE: std::cerr << "setone"; break; + + case ISD::SETO: std::cerr << "seto"; break; + case ISD::SETUO: std::cerr << "setuo"; break; + case ISD::SETUEQ: std::cerr << "setue"; break; + case ISD::SETUGT: std::cerr << "setugt"; break; + case ISD::SETUGE: std::cerr << "setuge"; break; + case ISD::SETULT: std::cerr << "setult"; break; + case ISD::SETULE: std::cerr << "setule"; break; + case ISD::SETUNE: std::cerr << "setune"; break; + + case ISD::SETEQ: std::cerr << "seteq"; break; + case ISD::SETGT: std::cerr << "setgt"; break; + case ISD::SETGE: std::cerr << "setge"; break; + case ISD::SETLT: std::cerr << "setlt"; break; + case ISD::SETLE: std::cerr << "setle"; break; + case ISD::SETNE: std::cerr << "setne"; break; + } + } + +} + +void SelectionDAG::dump() const { + std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; + for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) { + std::cerr << "\n "; + AllNodes[i]->dump(); + } + std::cerr << "\n\n"; +} + |
