SelectionDAG.h revision d1fc96499b7619356c7542200d32da898b79f7c1
1c3aae25116e66c177579b0b79182b09340b19753Chris Lattner//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===// 2cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// 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. 76fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 96fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 10c3aae25116e66c177579b0b79182b09340b19753Chris Lattner// This file declares the SelectionDAG class, and transitively defines the 11c3aae25116e66c177579b0b79182b09340b19753Chris Lattner// SDNode class and subclasses. 12cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// 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 { 39cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner const TargetMachine &TM; 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; 47c3aae25116e66c177579b0b79182b09340b19753Chris Lattner 48c3aae25116e66c177579b0b79182b09340b19753Chris Lattner // Maps to auto-CSE operations. 49c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >, 50c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDNode *> UnaryOps; 51c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >, 52c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDNode *> BinaryOps; 53c3aae25116e66c177579b0b79182b09340b19753Chris Lattner 54c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<std::pair<std::pair<SDOperand, SDOperand>, ISD::CondCode>, 55c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SetCCSDNode*> SetCCs; 56c3aae25116e66c177579b0b79182b09340b19753Chris Lattner 57c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >, 58c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDNode *> Loads; 59c3aae25116e66c177579b0b79182b09340b19753Chris Lattner 60c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<const GlobalValue*, SDNode*> GlobalValues; 61c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants; 62c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<std::pair<double, MVT::ValueType>, SDNode*> ConstantFPs; 63c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<int, SDNode*> FrameIndices; 64c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<unsigned, SDNode*> ConstantPoolIndices; 65c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<MachineBasicBlock *, SDNode*> BBNodes; 66c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::map<std::string, SDNode*> ExternalSymbols; 67cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerpublic: 68c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SelectionDAG(const TargetMachine &tm, MachineFunction &mf) : TM(tm), MF(mf) { 69c3aae25116e66c177579b0b79182b09340b19753Chris Lattner EntryNode = Root = getNode(ISD::EntryToken, MVT::Other); 70c3aae25116e66c177579b0b79182b09340b19753Chris Lattner } 71cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner ~SelectionDAG(); 72cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 73c3aae25116e66c177579b0b79182b09340b19753Chris Lattner MachineFunction &getMachineFunction() const { return MF; } 74c3aae25116e66c177579b0b79182b09340b19753Chris Lattner const TargetMachine &getTarget() { return TM; } 75cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 76c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// getRoot - Return the root tag of the SelectionDAG. 77cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 78c3aae25116e66c177579b0b79182b09340b19753Chris Lattner const SDOperand &getRoot() const { return Root; } 79cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 80c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// getEntryNode - Return the token chain corresponding to the entry of the 81c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// function. 82c3aae25116e66c177579b0b79182b09340b19753Chris Lattner const SDOperand &getEntryNode() const { return EntryNode; } 83cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 84c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// setRoot - Set the current root tag of the SelectionDAG. 85cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 86c3aae25116e66c177579b0b79182b09340b19753Chris Lattner const SDOperand &setRoot(SDOperand N) { return Root = N; } 87cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 88c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 89c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// compatible with the target instruction selector, as indicated by the 90c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// TargetLowering object. 91cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 92c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// Note that this is an involved process that may invalidate pointers into 93c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// the graph. 94c3aae25116e66c177579b0b79182b09340b19753Chris Lattner void Legalize(TargetLowering &TLI); 95c3aae25116e66c177579b0b79182b09340b19753Chris Lattner 96d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner /// RemoveDeadNodes - This method deletes all unreachable nodes in the 97d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner /// SelectionDAG, including nodes (like loads) that have uses of their token 98d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner /// chain but no other uses and no side effect. If a node is passed in as an 99d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner /// argument, it is used as the seed for node deletion. 100d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner void RemoveDeadNodes(SDNode *N = 0); 101d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner 102c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getConstant(uint64_t Val, MVT::ValueType VT); 103c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getConstantFP(double Val, MVT::ValueType VT); 104c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT); 105c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getFrameIndex(int FI, MVT::ValueType VT); 106c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getConstantPool(unsigned CPIdx, MVT::ValueType VT); 107c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getBasicBlock(MachineBasicBlock *MBB); 108c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT); 109c3aae25116e66c177579b0b79182b09340b19753Chris Lattner 110c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getCopyToReg(SDOperand Chain, SDOperand N, unsigned VReg) { 111c3aae25116e66c177579b0b79182b09340b19753Chris Lattner // Note: these are auto-CSE'd because the caller doesn't make requests that 112c3aae25116e66c177579b0b79182b09340b19753Chris Lattner // could cause duplicates to occur. 113c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDNode *NN = new CopyRegSDNode(Chain, N, VReg); 114c3aae25116e66c177579b0b79182b09340b19753Chris Lattner AllNodes.push_back(NN); 115c3aae25116e66c177579b0b79182b09340b19753Chris Lattner return SDOperand(NN, 0); 116cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 117cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 118c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getCopyFromReg(unsigned VReg, MVT::ValueType VT) { 119c3aae25116e66c177579b0b79182b09340b19753Chris Lattner // Note: These nodes are auto-CSE'd by the caller of this method. 120c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDNode *NN = new CopyRegSDNode(VReg, VT); 121c3aae25116e66c177579b0b79182b09340b19753Chris Lattner AllNodes.push_back(NN); 122c3aae25116e66c177579b0b79182b09340b19753Chris Lattner return SDOperand(NN, 0); 123cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 124cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 125c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// getCall - Note that this destroys the vector of RetVals passed in. 126c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// 127c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain, 128c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand Callee) { 129c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDNode *NN = new SDNode(ISD::CALL, Chain, Callee); 130c3aae25116e66c177579b0b79182b09340b19753Chris Lattner NN->setValueTypes(RetVals); 131c3aae25116e66c177579b0b79182b09340b19753Chris Lattner AllNodes.push_back(NN); 132c3aae25116e66c177579b0b79182b09340b19753Chris Lattner return NN; 133cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 134cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 135c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getSetCC(ISD::CondCode, SDOperand LHS, SDOperand RHS); 136cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 137c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// getNode - Gets or creates the specified node. 138cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 139c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getNode(unsigned Opcode, MVT::ValueType VT); 140c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N); 141c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 142c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand N1, SDOperand N2); 143c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 144c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand N1, SDOperand N2, SDOperand N3); 145c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 146c3aae25116e66c177579b0b79182b09340b19753Chris Lattner std::vector<SDOperand> &Children); 147c3aae25116e66c177579b0b79182b09340b19753Chris Lattner 148c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// getLoad - Loads are not normal binary operators: their result type is not 149c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// determined by their operands, and they produce a value AND a token chain. 150cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 151c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr); 152cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 153c3aae25116e66c177579b0b79182b09340b19753Chris Lattner void replaceAllUsesWith(SDOperand Old, SDOperand New) { 154c3aae25116e66c177579b0b79182b09340b19753Chris Lattner assert(Old != New && "RAUW self!"); 155c3aae25116e66c177579b0b79182b09340b19753Chris Lattner assert(0 && "Unimplemented!"); 156cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 157cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 158cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void dump() const; 159d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner 160d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattnerprivate: 161d1fc96499b7619356c7542200d32da898b79f7c1Chris Lattner void DeleteNodeIfDead(SDNode *N, void *NodeSet); 162cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner}; 163cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 164cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner} 165cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 166cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#endif 167