SelectionDAG.h revision 15e4b01920d6a0ffbe35d3e5aa88a4b42970b6a7
1c3aae25116e66c177579b0b79182b09340b19753Chris Lattner//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===//
2ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman//
36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//                     The LLVM Compiler Infrastructure
46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//
56fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// This file was developed by the LLVM research group and is distributed under
66fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details.
7ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman//
86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===//
9ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman//
10c3aae25116e66c177579b0b79182b09340b19753Chris Lattner// This file declares the SelectionDAG class, and transitively defines the
11c3aae25116e66c177579b0b79182b09340b19753Chris Lattner// SDNode class and subclasses.
12ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman//
13cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner//===----------------------------------------------------------------------===//
14cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
15cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#ifndef LLVM_CODEGEN_SELECTIONDAG_H
16cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#define LLVM_CODEGEN_SELECTIONDAG_H
17cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
18c3aae25116e66c177579b0b79182b09340b19753Chris Lattner#include "llvm/CodeGen/SelectionDAGNodes.h"
19cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#include <map>
20c3aae25116e66c177579b0b79182b09340b19753Chris Lattner#include <string> // FIXME remove eventually, turning map into const char* map.
21d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke
22d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm {
23c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  class TargetLowering;
24c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  class TargetMachine;
25c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  class MachineFunction;
26c3aae25116e66c177579b0b79182b09340b19753Chris Lattner
27c3aae25116e66c177579b0b79182b09340b19753Chris Lattner/// SelectionDAG class - This is used to represent a portion of an LLVM function
28c3aae25116e66c177579b0b79182b09340b19753Chris Lattner/// in a low-level Data Dependence DAG representation suitable for instruction
29c3aae25116e66c177579b0b79182b09340b19753Chris Lattner/// selection.  This DAG is constructed as the first step of instruction
30c3aae25116e66c177579b0b79182b09340b19753Chris Lattner/// selection in order to allow implementation of machine specific optimizations
31c3aae25116e66c177579b0b79182b09340b19753Chris Lattner/// and code simplifications.
32c3aae25116e66c177579b0b79182b09340b19753Chris Lattner///
33c3aae25116e66c177579b0b79182b09340b19753Chris Lattner/// The representation used by the SelectionDAG is a target-independent
34c3aae25116e66c177579b0b79182b09340b19753Chris Lattner/// representation, which has some similarities to the GCC RTL representation,
35c3aae25116e66c177579b0b79182b09340b19753Chris Lattner/// but is significantly more simple, powerful, and is a graph form instead of a
36c3aae25116e66c177579b0b79182b09340b19753Chris Lattner/// linear form.
37cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner///
38cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass SelectionDAG {
39063287a76b5d1486f498fcf674a26d1155471a3fChris Lattner  TargetLowering &TLI;
40c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  MachineFunction &MF;
41cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
42c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  // Root - The root of the entire DAG.  EntryNode - The starting token.
43c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand Root, EntryNode;
44cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
45cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  // AllNodes - All of the nodes in the DAG
46c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  std::vector<SDNode*> AllNodes;
47691ef2ba066dda14ae4ac0ad645054fbc967785aAndrew Lenharth
48691ef2ba066dda14ae4ac0ad645054fbc967785aAndrew Lenharth  // ValueNodes - track SrcValue nodes
49691ef2ba066dda14ae4ac0ad645054fbc967785aAndrew Lenharth  std::map<std::pair<const Value*, int>, SDNode*> ValueNodes;
50691ef2ba066dda14ae4ac0ad645054fbc967785aAndrew Lenharth
51cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerpublic:
52063287a76b5d1486f498fcf674a26d1155471a3fChris Lattner  SelectionDAG(TargetLowering &tli, MachineFunction &mf) : TLI(tli), MF(mf) {
53c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
54c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  }
55cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  ~SelectionDAG();
56cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
57c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  MachineFunction &getMachineFunction() const { return MF; }
58063287a76b5d1486f498fcf674a26d1155471a3fChris Lattner  const TargetMachine &getTarget() const;
59063287a76b5d1486f498fcf674a26d1155471a3fChris Lattner  TargetLowering &getTargetLoweringInfo() const { return TLI; }
60cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
611080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  /// viewGraph - Pop up a ghostview window with the DAG rendered using 'dot'.
621080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  ///
631080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  void viewGraph();
641080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner
651080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner
661080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  typedef std::vector<SDNode*>::const_iterator allnodes_iterator;
671080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  allnodes_iterator allnodes_begin() const { return AllNodes.begin(); }
681080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  allnodes_iterator allnodes_end() const { return AllNodes.end(); }
69ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman
70c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// getRoot - Return the root tag of the SelectionDAG.
71cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  ///
72c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  const SDOperand &getRoot() const { return Root; }
73cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
74c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// getEntryNode - Return the token chain corresponding to the entry of the
75c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// function.
76c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  const SDOperand &getEntryNode() const { return EntryNode; }
77cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
78c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// setRoot - Set the current root tag of the SelectionDAG.
79cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  ///
80c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  const SDOperand &setRoot(SDOperand N) { return Root = N; }
81cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
82c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
83c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// compatible with the target instruction selector, as indicated by the
84c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// TargetLowering object.
85cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  ///
86c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// Note that this is an involved process that may invalidate pointers into
87c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// the graph.
88063287a76b5d1486f498fcf674a26d1155471a3fChris Lattner  void Legalize();
89c3aae25116e66c177579b0b79182b09340b19753Chris Lattner
90d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner  /// RemoveDeadNodes - This method deletes all unreachable nodes in the
91d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner  /// SelectionDAG, including nodes (like loads) that have uses of their token
92d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner  /// chain but no other uses and no side effect.  If a node is passed in as an
93d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner  /// argument, it is used as the seed for node deletion.
94d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner  void RemoveDeadNodes(SDNode *N = 0);
95d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner
96c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getConstant(uint64_t Val, MVT::ValueType VT);
97c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getConstantFP(double Val, MVT::ValueType VT);
98c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT);
99c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getFrameIndex(int FI, MVT::ValueType VT);
100c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getConstantPool(unsigned CPIdx, MVT::ValueType VT);
101c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getBasicBlock(MachineBasicBlock *MBB);
102c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT);
10315e4b01920d6a0ffbe35d3e5aa88a4b42970b6a7Chris Lattner  SDOperand getValueType(MVT::ValueType);
104c3aae25116e66c177579b0b79182b09340b19753Chris Lattner
1059ffdfb6bae9a8befd23e002f71f08aa42caee627Chris Lattner  SDOperand getCopyToReg(SDOperand Chain, SDOperand N, unsigned Reg) {
106c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    // Note: these are auto-CSE'd because the caller doesn't make requests that
107c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    // could cause duplicates to occur.
10860e4878f9414227a92fec423d5fc39f0d00a2478Chris Lattner    SDNode *NN = new RegSDNode(ISD::CopyToReg, Chain, N, Reg);
10960e4878f9414227a92fec423d5fc39f0d00a2478Chris Lattner    NN->setValueTypes(MVT::Other);
110c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    AllNodes.push_back(NN);
111c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    return SDOperand(NN, 0);
112cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  }
113cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
11460e4878f9414227a92fec423d5fc39f0d00a2478Chris Lattner  SDOperand getCopyFromReg(unsigned Reg, MVT::ValueType VT, SDOperand Chain) {
115c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    // Note: These nodes are auto-CSE'd by the caller of this method.
11660e4878f9414227a92fec423d5fc39f0d00a2478Chris Lattner    SDNode *NN = new RegSDNode(ISD::CopyFromReg, Chain, Reg);
11760e4878f9414227a92fec423d5fc39f0d00a2478Chris Lattner    NN->setValueTypes(VT, MVT::Other);
11818c2f13e0f9d0e5d6227cf6d1881e9ee3d1b6109Chris Lattner    AllNodes.push_back(NN);
11918c2f13e0f9d0e5d6227cf6d1881e9ee3d1b6109Chris Lattner    return SDOperand(NN, 0);
12018c2f13e0f9d0e5d6227cf6d1881e9ee3d1b6109Chris Lattner  }
12118c2f13e0f9d0e5d6227cf6d1881e9ee3d1b6109Chris Lattner
1221cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  SDOperand getImplicitDef(SDOperand Chain, unsigned Reg) {
12318c2f13e0f9d0e5d6227cf6d1881e9ee3d1b6109Chris Lattner    // Note: These nodes are auto-CSE'd by the caller of this method.
12460e4878f9414227a92fec423d5fc39f0d00a2478Chris Lattner    SDNode *NN = new RegSDNode(ISD::ImplicitDef, Chain, Reg);
12560e4878f9414227a92fec423d5fc39f0d00a2478Chris Lattner    NN->setValueTypes(MVT::Other);
126c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    AllNodes.push_back(NN);
127c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    return SDOperand(NN, 0);
128cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  }
129cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
130c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// getCall - Note that this destroys the vector of RetVals passed in.
131c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  ///
132c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain,
1334c1eae9fb329e0e371d453957c56426294de24e9Chris Lattner                  SDOperand Callee, bool isTailCall = false) {
1344211e73c4905af413db7524f24414c16a7f69102Chris Lattner    SDNode *NN = new SDNode(isTailCall ? ISD::TAILCALL : ISD::CALL, Chain,
1354211e73c4905af413db7524f24414c16a7f69102Chris Lattner                            Callee);
136c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    NN->setValueTypes(RetVals);
137c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    AllNodes.push_back(NN);
138c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    return NN;
139cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  }
140cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
14102b86f52ed19213ef4911da902145155c03fb136Chris Lattner  /// getCall - This is identical to the one above, and should be used for calls
14202b86f52ed19213ef4911da902145155c03fb136Chris Lattner  /// where arguments are passed in physical registers.  This destroys the
14302b86f52ed19213ef4911da902145155c03fb136Chris Lattner  /// RetVals and ArgsInRegs vectors.
14402b86f52ed19213ef4911da902145155c03fb136Chris Lattner  SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain,
1454211e73c4905af413db7524f24414c16a7f69102Chris Lattner                  SDOperand Callee, std::vector<SDOperand> &ArgsInRegs,
1464211e73c4905af413db7524f24414c16a7f69102Chris Lattner                  bool isTailCall = false) {
14702b86f52ed19213ef4911da902145155c03fb136Chris Lattner    ArgsInRegs.insert(ArgsInRegs.begin(), Callee);
14802b86f52ed19213ef4911da902145155c03fb136Chris Lattner    ArgsInRegs.insert(ArgsInRegs.begin(), Chain);
1494c1eae9fb329e0e371d453957c56426294de24e9Chris Lattner    SDNode *NN = new SDNode(isTailCall ? ISD::TAILCALL : ISD::CALL, ArgsInRegs);
15002b86f52ed19213ef4911da902145155c03fb136Chris Lattner    NN->setValueTypes(RetVals);
15102b86f52ed19213ef4911da902145155c03fb136Chris Lattner    AllNodes.push_back(NN);
15202b86f52ed19213ef4911da902145155c03fb136Chris Lattner    return NN;
15302b86f52ed19213ef4911da902145155c03fb136Chris Lattner  }
15402b86f52ed19213ef4911da902145155c03fb136Chris Lattner
15502b86f52ed19213ef4911da902145155c03fb136Chris Lattner
15630c0fc23c548f75d4e501c39be4be597089d516fChris Lattner  SDOperand getSetCC(ISD::CondCode, MVT::ValueType VT,
15730c0fc23c548f75d4e501c39be4be597089d516fChris Lattner                     SDOperand LHS, SDOperand RHS);
158cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
1591ccae666f596d5aeca5c9942995763600b622062Chris Lattner  /// getZeroExtendInReg - Return the expression required to zero extend the Op
1601ccae666f596d5aeca5c9942995763600b622062Chris Lattner  /// value assuming it was the smaller SrcTy value.
1611ccae666f596d5aeca5c9942995763600b622062Chris Lattner  SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy);
1621ccae666f596d5aeca5c9942995763600b622062Chris Lattner
163c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// getNode - Gets or creates the specified node.
164cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  ///
165c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getNode(unsigned Opcode, MVT::ValueType VT);
166c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N);
167c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
168c3aae25116e66c177579b0b79182b09340b19753Chris Lattner                    SDOperand N1, SDOperand N2);
169c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
170c3aae25116e66c177579b0b79182b09340b19753Chris Lattner                    SDOperand N1, SDOperand N2, SDOperand N3);
171c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
1722d86ea21dd76647cb054fd5d27df9e49efc672b6Andrew Lenharth                    SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4);
1732d86ea21dd76647cb054fd5d27df9e49efc672b6Andrew Lenharth  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
174c3aae25116e66c177579b0b79182b09340b19753Chris Lattner                    std::vector<SDOperand> &Children);
1754211e73c4905af413db7524f24414c16a7f69102Chris Lattner  SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys,
1764211e73c4905af413db7524f24414c16a7f69102Chris Lattner                    std::vector<SDOperand> &Ops);
177c3aae25116e66c177579b0b79182b09340b19753Chris Lattner
1781cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  // getNode - These versions take an extra value type for extending and
179859157daee6a4b49e99921832e1dde065167b317Chris Lattner  // truncating loads, stores, rounds, extends etc.
1801cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N1,
1811cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner                    SDOperand N2, MVT::ValueType EVT);
182859157daee6a4b49e99921832e1dde065167b317Chris Lattner  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
183859157daee6a4b49e99921832e1dde065167b317Chris Lattner                    SDOperand N, MVT::ValueType EVT);
1841cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N1,
1851cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner                    SDOperand N2, SDOperand N3, MVT::ValueType EVT);
1862d86ea21dd76647cb054fd5d27df9e49efc672b6Andrew Lenharth  SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N1,
18721074f43ed5165828717ea3606eb2bd222a39b26Chris Lattner                    SDOperand N2, SDOperand N3, SDOperand N4,
18821074f43ed5165828717ea3606eb2bd222a39b26Chris Lattner                    MVT::ValueType EVT);
1891cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner
1904211e73c4905af413db7524f24414c16a7f69102Chris Lattner
191c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// getLoad - Loads are not normal binary operators: their result type is not
192c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  /// determined by their operands, and they produce a value AND a token chain.
193cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  ///
19421074f43ed5165828717ea3606eb2bd222a39b26Chris Lattner  SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr,
19521074f43ed5165828717ea3606eb2bd222a39b26Chris Lattner                    SDOperand SV);
1962d86ea21dd76647cb054fd5d27df9e49efc672b6Andrew Lenharth
1972d86ea21dd76647cb054fd5d27df9e49efc672b6Andrew Lenharth  // getSrcValue - construct a node to track a Value* through the backend
198691ef2ba066dda14ae4ac0ad645054fbc967785aAndrew Lenharth  SDOperand getSrcValue(const Value* I, int offset = 0);
199cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
200c3aae25116e66c177579b0b79182b09340b19753Chris Lattner  void replaceAllUsesWith(SDOperand Old, SDOperand New) {
201c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    assert(Old != New && "RAUW self!");
202c3aae25116e66c177579b0b79182b09340b19753Chris Lattner    assert(0 && "Unimplemented!");
203cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  }
204cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
205cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner  void dump() const;
206d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner
207d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattnerprivate:
208d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner  void DeleteNodeIfDead(SDNode *N, void *NodeSet);
2091cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner
2101cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  // Maps to auto-CSE operations.
2111cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >,
2121cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner           SDNode *> UnaryOps;
2131cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >,
2141cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner           SDNode *> BinaryOps;
2151cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner
216c7ba0eb5eb170daeb13ed97b23f1283f13bb33ebChris Lattner  std::map<std::pair<std::pair<SDOperand, SDOperand>,
217c7ba0eb5eb170daeb13ed97b23f1283f13bb33ebChris Lattner                     std::pair<ISD::CondCode, MVT::ValueType> >,
2181cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner           SetCCSDNode*> SetCCs;
2191cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner
2201cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >,
2211cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner           SDNode *> Loads;
2221cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner
2231cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  std::map<const GlobalValue*, SDNode*> GlobalValues;
2241cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants;
225b29cb29364d3e22f062c695d2d5740dda42d8e8eChris Lattner  std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> ConstantFPs;
2261cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  std::map<int, SDNode*> FrameIndices;
2271cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  std::map<unsigned, SDNode*> ConstantPoolIndices;
2281cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  std::map<MachineBasicBlock *, SDNode*> BBNodes;
22915e4b01920d6a0ffbe35d3e5aa88a4b42970b6a7Chris Lattner  std::vector<SDNode*> ValueTypeNodes;
2304211e73c4905af413db7524f24414c16a7f69102Chris Lattner  std::map<std::pair<unsigned,
2316765bfed31f06d7ed2f5a87248ffadc9dce10de4Chris Lattner                     std::pair<MVT::ValueType, std::vector<SDOperand> > >,
2326765bfed31f06d7ed2f5a87248ffadc9dce10de4Chris Lattner           SDNode*> OneResultNodes;
2336765bfed31f06d7ed2f5a87248ffadc9dce10de4Chris Lattner  std::map<std::pair<unsigned,
2344211e73c4905af413db7524f24414c16a7f69102Chris Lattner                     std::pair<std::vector<MVT::ValueType>,
2354211e73c4905af413db7524f24414c16a7f69102Chris Lattner                               std::vector<SDOperand> > >,
2364211e73c4905af413db7524f24414c16a7f69102Chris Lattner           SDNode*> ArbitraryNodes;
2374211e73c4905af413db7524f24414c16a7f69102Chris Lattner
2381cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  std::map<std::string, SDNode*> ExternalSymbols;
2391cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  struct EVTStruct {
2401cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner    unsigned Opcode;
2411cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner    MVT::ValueType VT, EVT;
2421cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner    std::vector<SDOperand> Ops;
2431cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner    bool operator<(const EVTStruct &RHS) const {
2441cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner      if (Opcode < RHS.Opcode) return true;
2451cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner      if (Opcode > RHS.Opcode) return false;
2461cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner      if (VT < RHS.VT) return true;
2471cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner      if (VT > RHS.VT) return false;
2481cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner      if (EVT < RHS.EVT) return true;
2491cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner      if (EVT > RHS.EVT) return false;
2501cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner      return Ops < RHS.Ops;
2511cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner    }
2521cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  };
2531cff05c7c216eea0e9173738c2a60b70c2b3c013Chris Lattner  std::map<EVTStruct, SDNode*> MVTSDNodes;
254cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner};
255cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
2561080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattnertemplate <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
2571080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  typedef SelectionDAG::allnodes_iterator nodes_iterator;
2581080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  static nodes_iterator nodes_begin(SelectionDAG *G) {
2591080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner    return G->allnodes_begin();
2601080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  }
2611080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  static nodes_iterator nodes_end(SelectionDAG *G) {
2621080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner    return G->allnodes_end();
2631080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner  }
2641080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner};
2651080b9ee534579c67f7c99364cc6fa11edbcd919Chris Lattner
266cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner}
267cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner
268cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#endif
269