diff options
| -rw-r--r-- | include/llvm/CodeGen/SelectionDAG.h | 9 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/DAGCombiner.cpp | 33 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/LegalizeDAGTypes.cpp | 1522 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp | 6 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 88 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 4 | ||||
| -rw-r--r-- | utils/TableGen/DAGISelEmitter.cpp | 4 |
7 files changed, 1605 insertions, 61 deletions
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index 731846d760..0120e99c8b 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -120,6 +120,13 @@ public: /// generate any nodes that will be illegal on the target. void Combine(bool AfterLegalize, AliasAnalysis &AA); + /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that + /// only uses types natively supported by the target. + /// + /// Note that this is an involved process that may invalidate pointers into + /// the graph. + void LegalizeTypes(); + /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is /// compatible with the target instruction selector, as indicated by the /// TargetLowering object. @@ -451,7 +458,7 @@ public: /// handled the same was as for ReplaceAllUsesWith, but it is required for /// this method. void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, - std::vector<SDNode*> &Deleted); + std::vector<SDNode*> *Deleted = 0); /// AssignNodeIds - Assign a unique node id for each node in the DAG based on /// their allnodes order. It returns the maximum id. diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp index 4d813a0cb4..3614cb6939 100644 --- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -173,7 +173,7 @@ namespace { DOUT << '\n'; std::vector<SDNode*> NowDead; - DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, NowDead); + DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, &NowDead); // Push the new node and any (possibly new) users onto the worklist. AddToWorkList(TLO.New.Val); @@ -1414,8 +1414,6 @@ SDOperand DAGCombiner::visitMULHU(SDNode *N) { /// bool DAGCombiner::SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp, unsigned HiOp) { - std::vector<SDNode*> NowDead; - // If the high half is not needed, just compute the low half. if (!N->hasAnyUseOfValue(1) && (!AfterLegalize || @@ -1423,8 +1421,7 @@ bool DAGCombiner::SimplifyNodeWithTwoResults(SDNode *N, DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), DAG.getNode(LoOp, N->getValueType(0), N->op_begin(), - N->getNumOperands()), - NowDead); + N->getNumOperands())); return true; } @@ -1435,8 +1432,7 @@ bool DAGCombiner::SimplifyNodeWithTwoResults(SDNode *N, DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), DAG.getNode(HiOp, N->getValueType(1), N->op_begin(), - N->getNumOperands()), - NowDead); + N->getNumOperands())); return true; } @@ -1464,8 +1460,8 @@ bool DAGCombiner::SimplifyNodeWithTwoResults(SDNode *N, (HiExists || HiOpt != Hi) && TLI.isOperationLegal(LoOpt.getOpcode(), LoOpt.getValueType()) && TLI.isOperationLegal(HiOpt.getOpcode(), HiOpt.getValueType())) { - DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), LoOpt, NowDead); - DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), HiOpt, NowDead); + DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), LoOpt); + DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), HiOpt); return true; } @@ -2891,8 +2887,7 @@ SDOperand DAGCombiner::ReduceLoadWidth(SDNode *N) { LN0->isVolatile(), LN0->getAlignment()); AddToWorkList(N); if (CombineSRL) { - std::vector<SDNode*> NowDead; - DAG.ReplaceAllUsesOfValueWith(N0.getValue(1), Load.getValue(1), NowDead); + DAG.ReplaceAllUsesOfValueWith(N0.getValue(1), Load.getValue(1)); CombineTo(N->getOperand(0).Val, Load); } else CombineTo(N0.Val, Load, Load.getValue(1)); @@ -3694,12 +3689,12 @@ bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) { std::vector<SDNode*> NowDead; if (isLoad) { DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0), - NowDead); + &NowDead); DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2), - NowDead); + &NowDead); } else { DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(1), - NowDead); + &NowDead); } // Nodes can end up on the worklist more than once. Make sure we do @@ -3711,7 +3706,7 @@ bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) { // Replace the uses of Ptr with uses of the updated base value. DAG.ReplaceAllUsesOfValueWith(Ptr, Result.getValue(isLoad ? 1 : 0), - NowDead); + &NowDead); removeFromWorkList(Ptr.Val); for (unsigned i = 0, e = NowDead.size(); i != e; ++i) removeFromWorkList(NowDead[i]); @@ -3825,12 +3820,12 @@ bool DAGCombiner::CombineToPostIndexedLoadStore(SDNode *N) { std::vector<SDNode*> NowDead; if (isLoad) { DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0), - NowDead); + &NowDead); DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2), - NowDead); + &NowDead); } else { DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(1), - NowDead); + &NowDead); } // Nodes can end up on the worklist more than once. Make sure we do @@ -3843,7 +3838,7 @@ bool DAGCombiner::CombineToPostIndexedLoadStore(SDNode *N) { // Replace the uses of Use with uses of the updated base value. DAG.ReplaceAllUsesOfValueWith(SDOperand(Op, 0), Result.getValue(isLoad ? 1 : 0), - NowDead); + &NowDead); removeFromWorkList(Op); for (unsigned i = 0, e = NowDead.size(); i != e; ++i) removeFromWorkList(NowDead[i]); diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAGTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAGTypes.cpp new file mode 100644 index 0000000000..e46f1bd2bb --- /dev/null +++ b/lib/CodeGen/SelectionDAG/LegalizeDAGTypes.cpp @@ -0,0 +1,1522 @@ +//===-- LegalizeDAGTypes.cpp - Implement SelectionDAG::LegalizeTypes ------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by Chris Lattner and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the SelectionDAG::LegalizeTypes method. It transforms +// an arbitrary well-formed SelectionDAG to only consist of legal types. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "legalize-types" +#include "llvm/CodeGen/SelectionDAG.h" +#include "llvm/Target/TargetLowering.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +using namespace llvm; + +//===----------------------------------------------------------------------===// +/// DAGTypeLegalizer - This takes an arbitrary SelectionDAG as input and +/// hacks on it until the target machine can handle it. This involves +/// eliminating value sizes the machine cannot handle (promoting small sizes to +/// large sizes or splitting up large values into small values) as well as +/// eliminating operations the machine cannot handle. +/// +/// This code also does a small amount of optimization and recognition of idioms +/// as part of its processing. For example, if a target does not support a +/// 'setcc' instruction efficiently, but does support 'brcc' instruction, this +/// will attempt merge setcc and brc instructions into brcc's. +/// +namespace { +class VISIBILITY_HIDDEN DAGTypeLegalizer { + TargetLowering &TLI; + SelectionDAG &DAG; + + // NodeIDFlags - This pass uses the NodeID on the SDNodes to hold information + // about the state of the node. The enum has all the values. + enum NodeIDFlags { + /// ReadyToProcess - All operands have been processed, so this node is ready + /// to be handled. + ReadyToProcess = 0, + + /// NewNode - This is a new node that was created in the process of + /// legalizing some other node. + NewNode = -1, + + /// Processed - This is a node that has already been processed. + Processed = -2 + + // 1+ - This is a node which has this many unlegalized operands. + }; + + enum LegalizeAction { + Legal, // The target natively supports this operation. + Promote, // This operation should be executed in a larger type. + Expand // Try to expand this to other ops, otherwise use a libcall. + }; + + /// ValueTypeActions - This is a bitvector that contains two bits for each + /// value type, where the two bits correspond to the LegalizeAction enum. + /// This can be queried with "getTypeAction(VT)". + TargetLowering::ValueTypeActionImpl ValueTypeActions; + + /// getTypeAction - Return how we should legalize values of this type, either + /// it is already legal or we need to expand it into multiple registers of + /// smaller integer type, or we need to promote it to a larger type. + LegalizeAction getTypeAction(MVT::ValueType VT) const { + return (LegalizeAction)ValueTypeActions.getTypeAction(VT); + } + + /// isTypeLegal - Return true if this type is legal on this target. + /// + bool isTypeLegal(MVT::ValueType VT) const { + return getTypeAction(VT) == Legal; + } + + SDOperand getIntPtrConstant(uint64_t Val) { + return DAG.getConstant(Val, TLI.getPointerTy()); + } + + /// PromotedNodes - For nodes that are below legal width, and that have more + /// than one use, this map indicates what promoted value to use. + DenseMap<SDOperand, SDOperand> PromotedNodes; + + /// ExpandedNodes - For nodes that need to be expanded this map indicates + /// which which operands are the expanded version of the input. + DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes; + + /// Worklist - This defines a worklist of nodes to process. In order to be + /// pushed onto this worklist, all operands of a node must have already been + /// processed. + SmallVector<SDNode*, 128> Worklist; + +public: + DAGTypeLegalizer(SelectionDAG &dag) + : TLI(dag.getTargetLoweringInfo()), DAG(dag), + ValueTypeActions(TLI.getValueTypeActions()) { + assert(MVT::LAST_VALUETYPE <= 32 && + "Too many value types for ValueTypeActions to hold!"); + } + + void run(); + +private: + void MarkNewNodes(SDNode *N); + + void ReplaceLegalValueWith(SDOperand From, SDOperand To); + + SDOperand GetPromotedOp(SDOperand Op) { + Op = PromotedNodes[Op]; + assert(Op.Val && "Operand wasn't promoted?"); + return Op; + } + void SetPromotedOp(SDOperand Op, SDOperand Result); + + void GetExpandedOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi); + void SetExpandedOp(SDOperand Op, SDOperand Lo, SDOperand Hi); + + // Result Promotion. + void PromoteResult(SDNode *N, unsigned ResNo); + SDOperand PromoteResult_UNDEF(SDNode *N); + SDOperand PromoteResult_Constant(SDNode *N); + SDOperand PromoteResult_TRUNCATE(SDNode *N); + SDOperand PromoteResult_INT_EXTEND(SDNode *N); + SDOperand PromoteResult_FP_ROUND(SDNode *N); + SDOperand PromoteResult_SETCC(SDNode *N); + SDOperand PromoteResult_LOAD(LoadSDNode *N); + SDOperand PromoteResult_SimpleIntBinOp(SDNode *N); + + // Result Expansion. + void ExpandResult(SDNode *N, unsigned ResNo); + void ExpandResult_UNDEF (SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_Constant (SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_BUILD_PAIR (SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_ANY_EXTEND (SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_ZERO_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_SIGN_EXTEND(SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_LOAD (LoadSDNode *N, SDOperand &Lo, SDOperand &Hi); + + void ExpandResult_Logical (SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_ADDSUB (SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_SELECT (SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_SELECT_CC (SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_MUL (SDNode *N, SDOperand &Lo, SDOperand &Hi); + void ExpandResult_Shift (SDNode *N, SDOperand &Lo, SDOperand &Hi); + + void ExpandShiftByConstant(SDNode *N, unsigned Amt, + SDOperand &Lo, SDOperand &Hi); + bool ExpandShiftWithKnownAmountBit(SDNode *N, SDOperand &Lo, SDOperand &Hi); + + // Operand Promotion. + bool PromoteOperand(SDNode *N, unsigned OperandNo); + SDOperand PromoteOperand_ANY_EXTEND(SDNode *N); + SDOperand PromoteOperand_ZERO_EXTEND(SDNode *N); + SDOperand PromoteOperand_SIGN_EXTEND(SDNode *N); + SDOperand PromoteOperand_FP_EXTEND(SDNode *N); + SDOperand PromoteOperand_FP_ROUND(SDNode *N); + SDOperand PromoteOperand_SELECT(SDNode *N, unsigned OpNo); + SDOperand PromoteOperand_BRCOND(SDNode *N, unsigned OpNo); + SDOperand PromoteOperand_STORE(StoreSDNode *N, unsigned OpNo); + + // Operand Expansion. + bool ExpandOperand(SDNode *N, unsigned OperandNo); + SDOperand ExpandOperand_TRUNCATE(SDNode *N); + SDOperand ExpandOperand_EXTRACT_ELEMENT(SDNode *N); + SDOperand ExpandOperand_SETCC(SDNode *N); + SDOperand ExpandOperand_STORE(StoreSDNode *N, unsigned OpNo); + + void ExpandSetCCOperands(SDOperand &NewLHS, SDOperand &NewRHS, + ISD::CondCode &CCCode); +}; +} // end anonymous namespace + + + +/// run - This is the main entry point for the type legalizer. This does a +/// top-down traversal of the dag, legalizing types as it goes. +void DAGTypeLegalizer::run() { + // Create a dummy node (which is not added to allnodes), that adds a reference + // to the root node, preventing it from being deleted, and tracking any + // changes of the root. + HandleSDNode Dummy(DAG.getRoot()); + + // The root of the dag may dangle to deleted nodes until the type legalizer is + // done. Set it to null to avoid confusion. + DAG.setRoot(SDOperand()); + + // Walk all nodes in the graph, assigning them a NodeID of 'ReadyToProcess' + // (and remembering them) if they are leafs and assigning 'NewNode' if + // non-leaves. + for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), + E = DAG.allnodes_end(); I != E; ++I) { + if (I->getNumOperands() == 0) { + I->setNodeId(ReadyToProcess); + Worklist.push_back(I); + } else { + I->setNodeId(NewNode); + } + } + + // Now that we have a set of nodes to process, handle them all. + while (!Worklist.empty()) { + SDNode *N = Worklist.back(); + Worklist.pop_back(); + assert(N->getNodeId() == ReadyToProcess && + "Node should be ready if on worklist!"); + + // Scan the values produced by the node, checking to see if any result + // types are illegal. + unsigned i = 0; + unsigned NumResults = N->getNumValues(); + do { + LegalizeAction Action = getTypeAction(N->getValueType(i)); + if (Action == Promote) { + PromoteResult(N, i); + goto NodeDone; + } else if (Action == Expand) { + ExpandResult(N, i); + goto NodeDone; + } else { + assert(Action == Legal && "Unknown action!"); + } + } while (++i < NumResults); + + // Scan the operand list for the node, handling any nodes with operands that + // are illegal. + { + unsigned NumOperands = N->getNumOperands(); + bool NeedsRevisit = false; + for (i = 0; i != NumOperands; ++i) { + LegalizeAction Action = getTypeAction(N->getOperand(i).getValueType()); + if (Action == Promote) { + NeedsRevisit = PromoteOperand(N, i); + break; + } else if (Action == Expand) { + NeedsRevisit = ExpandOperand(N, i); + break; + } else { + assert(Action == Legal && "Unknown action!"); + } + } + + // If the node needs revisitation, don't add all users to the worklist etc. + if (NeedsRevisit) + continue; + + if (i == NumOperands) + DEBUG(cerr << "Legally typed node: "; N->dump(&DAG); cerr << "\n"); + } +NodeDone: + + // If we reach here, the node was processed, potentially creating new nodes. + // Mark it as processed and add its users to the worklist as appropriate. + N->setNodeId(Processed); + + for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); + UI != E; ++UI) { + SDNode *User = *UI; + int NodeID = User->getNodeId(); + assert(NodeID != ReadyToProcess && NodeID != Processed && + "Invalid node id for user of unprocessed node!"); + + // This node has two options: it can either be a new node or its Node ID + // may be a count of the number of operands it has that are not ready. + if (NodeID > 0) { + User->setNodeId(NodeID-1); + + // If this was the last use it was waiting on, add it to the ready list. + if (NodeID-1 == ReadyToProcess) + Worklist.push_back(User); + continue; + } + + // Otherwise, this node is new: this is the first operand of it that + // became ready. Its new NodeID is the number of operands it has minus 1 + // (as this node is now processed). + assert(NodeID == NewNode && "Unknown node ID!"); + User->setNodeId(User->getNumOperands()-1); + + // If the node only has a single operand, it is now ready. + if (User->getNumOperands() == 1) + Worklist.push_back(User); + } + } + + // If the root changed (e.g. it was a dead load, update the root). + DAG.setRoot(Dummy.getValue()); + + //DAG.viewGraph(); + + // Remove dead nodes. This is important to do for cleanliness but also before + // the checking loop below. Implicit folding by the DAG.getNode operators can + // cause unreachable nodes to be around with their flags set to new. + DAG.RemoveDeadNodes(); + + // In a debug build, scan all the nodes to make sure we found them all. This + // ensures that there are no cycles and that everything got processed. +#ifndef NDEBUG + for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), + E = DAG.allnodes_end(); I != E; ++I) { + if (I->getNodeId() == Processed) + continue; + cerr << "Unprocessed node: "; + I->dump(&DAG); cerr << "\n"; + + if (I->getNodeId() == NewNode) + cerr << "New node not 'noticed'?\n"; + else if (I->getNodeId() > 0) + cerr << "Operand not processed?\n"; + else if (I->getNodeId() == ReadyToProcess) + cerr << "Not added to worklist?\n"; + abort(); + } +#endif +} + +/// MarkNewNodes - The specified node is the root of a subtree of potentially +/// new nodes. Add the correct NodeId to mark it. +void DAGTypeLegalizer::MarkNewNodes(SDNode *N) { + // If this was an existing node that is already done, we're done. + if (N->getNodeId() != NewNode) + return; + + // Okay, we know that this node is new. Recursively walk all of its operands + // to see if they are new also. The depth of this walk is bounded by the size + // of the new tree that was constructed (usually 2-3 nodes), so we don't worry + // about revisitation of nodes. + // + // As we walk the operands, keep track of the number of nodes that are + // processed. If non-zero, this will become the new nodeid of this node. + unsigned NumProcessed = 0; + for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { + int OpId = N->getOperand(i).Val->getNodeId(); + if (OpId == NewNode) + MarkNewNodes(N->getOperand(i).Val); + else if (OpId == Processed) + ++NumProcessed; + } + + N->setNodeId(N->getNumOperands()-NumProcessed); + if (N->getNodeId() == ReadyToProcess) + Worklist.push_back(N); +} + +/// ReplaceLegalValueWith - The specified value with a legal type was legalized +/// to the specified other value. If they are different, update the DAG and +/// NodeIDs replacing any uses of From to use To instead. +void DAGTypeLegalizer::ReplaceLegalValueWith(SDOperand From, SDOperand To) { + if (From == To) return; + + // If expansion produced new nodes, make sure they are properly marked. + if (To.Val->getNodeId() == NewNode) + MarkNewNodes(To.Val); + + // Anything that used the old node should now use the new one. Note that this + // can potentially cause recursive merging. + DAG.ReplaceAllUsesOfValueWith(From, To); + + // Since we just made an unstructured update to the DAG, which could wreak + // general havoc on anything that once used N and now uses Res, walk all users + // of the result, updating their flags. + for (SDNode::use_iterator I = To.Val->use_begin(), E = To.Val->use_end(); + I != E; ++I) { + SDNode *User = *I; + // If the node isn't already processed or in the worklist, mark it as new, + // then use MarkNewNodes to recompute its ID. + int NodeId = User->getNodeId(); + if (NodeId != ReadyToProcess && NodeId != Processed) { + User->setNodeId(NewNode); + MarkNewNodes(User); + } + } +} + +void DAGTypeLegalizer::SetPromotedOp(SDOperand Op, SDOperand Result) { + if (Result.Val->getNodeId() == NewNode) + MarkNewNodes(Result.Val); + + SDOperand &OpEntry = PromotedNodes[Op]; + assert(OpEntry.Val == 0 && "Node is already promoted!"); + OpEntry = Result; +} + + +void DAGTypeLegalizer::GetExpandedOp(SDOperand Op, SDOperand &Lo, + SDOperand &Hi) { + std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op]; + assert(Entry.first.Val && "Operand isn't expanded"); + Lo = Entry.first; + Hi = Entry.second; +} + +void DAGTypeLegalizer::SetExpandedOp(SDOperand Op, SDOperand Lo, + SDOperand Hi) { + // Remember that this is the result of the node. + std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op]; + assert(Entry.first.Val == 0 && "Node already expanded"); + Entry.first = Lo; + Entry.second = Hi; + + // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. + if (Lo.Val->getNodeId() == NewNode) + MarkNewNodes(Lo.Val); + if (Hi.Val->getNodeId() == NewNode) + MarkNewNodes(Hi.Val); +} + +//===----------------------------------------------------------------------===// +// Result Promotion +//===----------------------------------------------------------------------===// + +/// PromoteResult - This method is called when a result of a node is found to be +/// in need of promotion to a larger type. At this point, the node may also +/// have invalid operands or may have other results that need expansion, we just +/// know that (at least) the one result needs promotion. +void DAGTypeLegalizer::PromoteResult(SDNode *N, unsigned ResNo) { + DEBUG(cerr << "Promote node result: "; N->dump(&DAG); cerr << "\n"); + SDOperand Result = SDOperand(); + + switch (N->getOpcode()) { + default: +#ifndef NDEBUG + cerr << "PromoteResult #" << ResNo << ": "; + N->dump(&DAG); cerr << "\n"; +#endif + assert(0 && "Do not know how to promote this operator!"); + abort(); + case ISD::UNDEF: Result = PromoteResult_UNDEF(N); break; + case ISD::Constant: Result = PromoteResult_Constant(N); break; + + case ISD::TRUNCATE: Result = PromoteResult_TRUNCATE(N); break; + case ISD::SIGN_EXTEND: + case ISD::ZERO_EXTEND: + case ISD::ANY_EXTEND: Result = PromoteResult_INT_EXTEND(N); break; + case ISD::FP_ROUND: Result = PromoteResult_FP_ROUND(N); break; + + case ISD::SETCC: Result = PromoteResult_SETCC(N); break; + case ISD::LOAD: Result = PromoteResult_LOAD(cast<LoadSDNode>(N)); break; + + case ISD::AND: + case ISD::OR: + case ISD::XOR: + case ISD::ADD: + case ISD::SUB: + case ISD::MUL: Result = PromoteResult_SimpleIntBinOp(N); break; + } + + // If Result is null, the sub-method took care of registering the result. + if (Result.Val) + SetPromotedOp(SDOperand(N, ResNo), Result); +} + +SDOperand DAGTypeLegalizer::PromoteResult_UNDEF(SDNode *N) { + return DAG.getNode(ISD::UNDEF, TLI.getTypeToTransformTo(N->getValueType(0))); +} + +SDOperand DAGTypeLegalizer::PromoteResult_Constant(SDNode *N) { + MVT::ValueType VT = N->getValueType(0); + // Zero extend things like i1, sign extend everything else. It shouldn't + // matter in theory which one we pick, but this tends to give better code? + unsigned Opc = VT != MVT::i1 ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND; + SDOperand Result = DAG.getNode(Opc, TLI.getTypeToTransformTo(VT), + SDOperand(N, 0)); + assert(isa<ConstantSDNode>(Result) && "Didn't constant fold ext?"); + return Result; +} + +SDOperand DAGTypeLegalizer::PromoteResult_TRUNCATE(SDNode *N) { + MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); + switch (getTypeAction(N->getOperand(0).getValueType())) { + default: assert(0 && "Unknown type action!"); + case Legal: { + SDOperand Res = N->getOperand(0); + assert(Res.getValueType() >= NVT && "Truncation doesn't make sense!"); + if (Res.getValueType() > NVT) // Truncate to NVT instead of VT + return DAG.getNode(ISD::TRUNCATE, NVT, Res); + return Res; + } + case Promote: + // The truncation is not required, because we don't guarantee anything + // about high bits anyway. + return GetPromotedOp(N->getOperand(0)); + case Expand: + // Truncate the low part of the expanded value to the result type + SDOperand Lo, Hi; + GetExpandedOp(N->getOperand(0), Lo, Hi); + return DAG.getNode(ISD::TRUNCATE, NVT, Lo); + } +} +SDOperand DAGTypeLegalizer::PromoteResult_INT_EXTEND(SDNode *N) { + MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); + switch (getTypeAction(N->getOperand(0).getValueType())) { + default: assert(0 && "BUG: Smaller reg should have been promoted!"); + case Legal: + // Input is legal? Just do extend all the way to the larger type. + return DAG.getNode(N->getOpcode(), NVT, N->getOperand(0)); + case Promote: + // Get promoted operand if it is smaller. + SDOperand Res = GetPromotedOp(N->getOperand(0)); + // The high bits are not guaranteed to be anything. Insert an extend. + if (N->getOpcode() == ISD::SIGN_EXTEND) + return DAG.getNode(ISD::SIGN_EXTEND_INREG, NVT, Res, + DAG.getValueType(N->getOperand(0).getValueType())); + if (N->getOpcode() == ISD::ZERO_EXTEND) + return DAG.getZeroExtendInReg(Res, N->getOperand(0).getValueType()); + assert(N->getOpcode() == ISD::ANY_EXTEND && "Unknown integer extension!"); + return Res; + } +} + +SDOperand DAGTypeLegalizer::PromoteResult_FP_ROUND(SDNode *N) { + // NOTE: Assumes input is legal. + return DAG.getNode(ISD::FP_ROUND_INREG, N->getOperand(0).getValueType(), + N->getOperand(0), DAG.getValueType(N->getValueType(0))); +} + + +SDOperand DAGTypeLegalizer::PromoteResult_SETCC(SDNode *N) { + assert(isTypeLegal(TLI.getSetCCResultTy()) && "SetCC type is not legal??"); + return DAG.getNode(ISD::SETCC, TLI.getSetCCResultTy(), N->getOperand(0), + N->getOperand(1), N->getOperand(2)); +} + +SDOperand DAGTypeLegalizer::PromoteResult_LOAD(LoadSDNode *N) { + MVT::ValueType NVT = TLI.getTypeToTransformTo(N->getValueType(0)); + ISD::LoadExtType ExtType = + ISD::isNON_EXTLoad(N) ? ISD::EXTLOAD : N->getExtensionType(); + SDOperand Res = DAG.getExtLoad(ExtType, NVT, N->getChain(), N->getBasePtr(), + N->getSrcValue(), N->getSrcValueOffset(), + N->getLoadedVT(), N->isVolatile(), + N->getAlignment()); + + // Legalized the chain result, switching anything that used the old chain to + // use the new one. + ReplaceLegalValueWith(SDOperand(N, 1), Res.getValue(1)); + return Res; +} + +SDOperand DAGTypeLegalizer::PromoteResult_SimpleIntBinOp(SDNode *N) { + // The input may have strange things in the top bits of the registers, but + // these operations don't care. They may have weird bits going out, but + // that too is okay if they are integer operations. + SDOperand LHS = GetPromotedOp(N->getOperand(0)); + SDOperand RHS = GetPromotedOp(N->getOperand(1)); + return DAG.getNode(N->getOpcode(), LHS.getValueType(), LHS, RHS); +} + +//===----------------------------------------------------------------------===// +// Result Expansion +//===----------------------------------------------------------------------===// + +/// ExpandResult - This method is called when the specified result of the +/// specified node is found to need expansion. At this point, the node may also +/// have invalid operands or may have other results that need promotion, we just +/// know that (at least) the one result needs expansion. +void DAGTypeLegalizer::ExpandResult(SDNode *N, unsigned ResNo) { + DEBUG(cerr << "Expand node result: "; N->dump(&DAG); cerr << "\n"); + SDOperand Lo, Hi; + Lo = Hi = SDOperand(); + switch (N->getOpcode()) { + default: +#ifndef NDEBUG + cerr << "ExpandResult #" << ResNo << ": "; + N->dump(&DAG); cerr << "\n"; +#endif + assert(0 && "Do not know how to expand this operator!"); + abort(); + + case ISD::UNDEF: ExpandResult_UNDEF(N, Lo, Hi); break; + case ISD::Constant: ExpandResult_Constant(N, Lo, Hi); break; + case ISD::BUILD_PAIR: ExpandResult_BUILD_PAIR(N, Lo, Hi); break; + case ISD::ANY_EXTEND: ExpandResult_ANY_EXTEND(N, Lo, Hi); break; + case ISD::ZERO_EXTEND: ExpandResult_ZERO_EXTEND(N, Lo, Hi); break; + case ISD::SIGN_EXTEND: ExpandResult_SIGN_EXTEND(N, Lo, Hi); break; + case ISD::LOAD: ExpandResult_LOAD(cast<LoadSDNode>(N), Lo, Hi); break; + + case ISD::AND: + case ISD::OR: + case ISD::XOR: ExpandResult_Logical(N, Lo, Hi); break; + case ISD::ADD: + case ISD::SUB: ExpandResult_ADDSUB(N, Lo, Hi); break; + case ISD::SELECT: ExpandResult_SELECT(N, Lo, Hi); break; + case ISD::SELECT_CC: ExpandResult_SELECT_CC(N, Lo, Hi); break; + case ISD::MUL: ExpandResult_MUL(N, Lo, Hi); break; + case ISD::SHL: + case ISD::SRA: + case ISD::SRL: ExpandResult_Shift(N, Lo, Hi); break; + + } + + // If Lo/Hi is null, the sub-method took care of registering results etc. + if (Lo.Val) + SetExpandedOp(SDOperand(N, ResNo), Lo, Hi); +} + +void DAGTypeLegalizer::ExpandResult_UNDEF(SDNode *N, + SDOperand &Lo, SDOperand &Hi) { + MVT::ValueType NVT = TLI.getTypeToExpandTo(N->getValueType(0)); + Lo = Hi = DAG.getNode(ISD::UNDEF, NVT); +} + +void DAGTypeLegalizer::ExpandResult_Constant(SDNode *N, + SDOperand &Lo, SDOperand &Hi) { + MVT::ValueType NVT = TLI.getTypeToExpandTo(N->getValueType(0)); + uint64_t Cst = cast<ConstantSDNode>(N)->getValue(); + Lo = DAG.getConstant(Cst, NVT); + Hi = DAG.getConstant(Cst >> MVT::getSizeInBits(NVT), NVT); +} + +void DAGTypeLegalizer::ExpandResult_BUILD_PAIR(SDNode *N, + SDOperand &Lo, SDOperand &Hi) { + // Return the operands. + Lo = N->getOperand(0); + Hi = N->getOperand(1); +} + +void DAGTypeLegalizer::ExpandResult_ANY_EXTEND(SDNode *N, + SDOperand &Lo, SDOperand &Hi) { + + MVT::ValueType NVT = TLI.getTypeToExpandTo(N->getValueType(0)); + // The low part is any extension of the input (which degenerates to a copy). + Lo = DAG.getNode(ISD::ANY_EXTEND, NVT, N->getOperand(0)); + Hi = DAG.getNode(ISD::UNDEF, NVT); // The high part is undefined. +} + +void DAGTypeLegalizer::ExpandResult_ZERO_EXTEND(SDNode *N, + SDOperand &Lo, SDOperand &Hi) { + MVT::ValueType NVT = TLI.getTypeToExpandTo(N->getValueType(0)); + // The low part is zero extension of the input (which degenerates to a copy). + Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, N->getOperand(0)); + Hi = DAG.getConstant(0, NVT); // The high part is just a zero. +} + +void DAGTypeLegalizer::ExpandResult_SIGN_EXTEND(SDNode *N, + SDOperand &Lo, SDOperand &Hi) { + MVT::ValueType NVT = TLI.getTypeToExpandTo(N->getValueType(0)); + // The low part is sign extension of the input (which degenerates to a copy). + Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, N->getOperand(0)); + + // The high part is obtained by SRA'ing all but one of the bits of low part. + unsigned LoSize = MVT::getSizeInBits(NVT); + Hi = DAG.getNode(ISD::SRA, NVT, Lo, + DAG.getConstant(LoSize-1, TLI.getShiftAmountTy())); +} + + +void DAGTypeLegalizer::ExpandResult_LOAD(LoadSDNode *N, + SDOperand &Lo, SDOperand &Hi) { + MVT::ValueType VT = N->getValueType(0); + MVT::ValueType NVT = TLI.getTypeToExpandTo(VT); + SDOperand Ch = N->getChain(); // Legalize the chain. + SDOperand Ptr = N->getBasePtr(); // Legalize the pointer. + ISD::LoadExtType ExtType = N->getExtensionType(); + int SVOffset = N->getSrcValueOffset(); + unsigned Alignment = N->getAlignment(); + bool isVolatile = N->isVolatile(); + + if (ExtType == ISD::NON_EXTLOAD) { + Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset, + isVolatile, Alignment); + if (VT == MVT::f32 || VT == MVT::f64) { + assert(0 && "FIXME: softfp should use promotion!"); +#if 0 + // f32->i32 or f64->i64 one to one expansion. + // Remember that we legalized the chain. + AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Lo.getValue(1))); + // Recursively expand the new load. + if (getTypeAction(NVT) == Expand) + ExpandOp(Lo, Lo, Hi); + break; +#endif + } + + // Increment the pointer to the other half. + unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; + Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, + getIntPtrConstant(IncrementSize)); + Hi = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), SVOffset+IncrementSize, + isVolatile, std::max(Alignment, IncrementSize)); + + // Build a factor node to remember that this load is independent of the + // other one. + Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1), + Hi.getValue(1)); + + // Handle endianness of the load. + if (!TLI.isLittleEndian()) + std::swap(Lo, Hi); + } else { + MVT::ValueType EVT = N->getLoadedVT(); + + if (VT == MVT::f64 && EVT == MVT::f32) { + assert(0 && "FIXME: softfp should use promotion!"); +#if 0 + // f64 = EXTLOAD f32 should expand to LOAD, FP_EXTEND + SDOperand Load = DAG.getLoad(EVT, Ch, Ptr, N->getSrcValue(), + SVOffset, isVolatile, Alignment); + // Remember that we legalized the chain. + AddLegalizedOperand(SDOperand(Node, 1), LegalizeOp(Load.getValue(1))); + ExpandOp(DAG.getNode(ISD::FP_EXTEND, VT, Load), Lo, Hi); + break; +#endif + } + + if (EVT == NVT) + Lo = DAG.getLoad(NVT, Ch, Ptr, N->getSrcValue(), + SVOffset, isVolatile, Alignment); + else + Lo = DAG.getExtLoad(ExtType, NVT, Ch, Ptr, N->getSrcValue(), + SVOffset, EVT, isVolatile, + Alignment); + // Remember the chain. + Ch = Lo.getValue(1); + + if (ExtType == ISD::SEXTLOAD) { + // The high part is obtained by SRA'ing all but one of the bits of the + // lo part. + unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); + Hi = DAG.getNode(ISD::SRA, NVT, Lo, + DAG.getConstant(LoSize-1, TLI.getShiftAmountTy())); + } else if (ExtType == ISD::ZEXTLOAD) { + // The high part is just a zero. + Hi = DAG.getConstant(0, NVT); + } else { + assert(ExtType == ISD::EXTLOAD && "Unknown extload!"); + // The high part is undefined. + Hi = DAG.getNode(ISD::UNDEF, NVT); + } + } + + // Legalized the chain re |