SelectionDAG.h revision 6fbcc26f1460eaee4e0eb8b426fc1ff0c7af11be
1cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG Rep. ----*- 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// 10cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// This file declares the SelectionDAG class, which is used to represent an LLVM 11cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// function in a low-level representation suitable for instruction selection. 12cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// This DAG is constructed as the first step of instruction selection in order 13cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// to allow implementation of machine specific optimizations and code 14cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// simplifications. 15cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// 16cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// The representation used by the SelectionDAG is a target-independent 17cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// representation, which is loosly modeled after the GCC RTL representation, but 18cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// is significantly simpler. 19cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner// 20cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner//===----------------------------------------------------------------------===// 21cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 22cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#ifndef LLVM_CODEGEN_SELECTIONDAG_H 23cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#define LLVM_CODEGEN_SELECTIONDAG_H 24cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 25cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#include "llvm/CodeGen/ValueTypes.h" 26cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#include "Support/DataTypes.h" 27cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#include <map> 28cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#include <vector> 29b274d4a38bbec0c222cade044d160028a01e9326Chris Lattner#include <cassert> 30cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass Value; 31cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass Type; 32cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass Instruction; 33f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattnerclass CallInst; 34cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass BasicBlock; 35cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass MachineBasicBlock; 36cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass MachineFunction; 37cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass TargetMachine; 38cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass SelectionDAGNode; 39cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass SelectionDAGBlock; 40cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass SelectionDAGBuilder; 41cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass SelectionDAGTargetBuilder; 42cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 43cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// ISD namespace - This namespace contains an enum which represents all of the 44cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// SelectionDAG node types and value types. 45cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// 46cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnernamespace ISD { 47cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner enum NodeType { 48cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // ChainNode nodes are used to sequence operations within a basic block 49cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // which cannot be reordered (such as loads, stores, calls, etc). 50cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // BlockChainNodes are used to connect the DAG's for different basic blocks 51cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // into one big DAG. 52cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner ChainNode, BlockChainNode, 53cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 54cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // ProtoNodes are nodes that are only half way constructed. 55cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner ProtoNode, 56cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 57f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner // Leaf nodes 58f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner Constant, FrameIndex, BasicBlock, 59cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 60cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // Simple binary arithmetic operators 61cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Plus, Minus, Times, SDiv, UDiv, SRem, URem, 62cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 63cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // Bitwise operators 64cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner And, Or, Xor, 65cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 66f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner // Comparisons 67f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner SetEQ, SetNE, SetLT, SetLE, SetGT, SetGE, 68f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner 69cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // Control flow instructions 70f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner Br, BrCond, Switch, Ret, RetVoid, 71cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 72cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // Other operators 73cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Load, Store, PHI, Call, 74f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner 75f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner // Unknown operators, of a specified arity 76f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner Unspec1, Unspec2 77cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner }; 78cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner} 79cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 80cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass SelectionDAG { 81cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner friend class SelectionDAGBuilder; 82cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner MachineFunction &F; 83cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner const TargetMachine &TM; 84cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner MVT::ValueType PointerType; // The ValueType the target uses for pointers 85cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 86cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // ValueMap - The SelectionDAGNode for each LLVM value in the function. 87cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner std::map<const Value*, SelectionDAGNode*> ValueMap; 88cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 89cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // BlockMap - The MachineBasicBlock created for each LLVM BasicBlock 90cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner std::map<const BasicBlock*, MachineBasicBlock*> BlockMap; 91cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 92cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // Root - The root of the entire DAG 93cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode *Root; 94cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 95cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // AllNodes - All of the nodes in the DAG 96cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner std::vector<SelectionDAGNode*> AllNodes; 97cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerpublic: 98cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// SelectionDAG constructor - Build a SelectionDAG for the specified 99cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// function. Implemented in DAGBuilder.cpp 100cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 101cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAG(MachineFunction &F, const TargetMachine &TM, 102cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGTargetBuilder &SDTB); 103cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner ~SelectionDAG(); 104cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 105cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// getValueType - Return the ValueType for the specified LLVM type. This 106cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// method works on all scalar LLVM types. 107cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 108cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner MVT::ValueType getValueType(const Type *Ty) const; 109cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 110cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// getRoot - Return the root of the current SelectionDAG. 111cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 112cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode *getRoot() const { return Root; } 113cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 114cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// getMachineFunction - Return the MachineFunction object that this 115cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// SelectionDAG corresponds to. 116cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 117cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner MachineFunction &getMachineFunction() const { return F; } 118cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 119cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner //===--------------------------------------------------------------------===// 120cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // Addition and updating methods 121cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // 122cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 123cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// addNode - Add the specified node to the SelectionDAG so that it will be 124cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// deleted when the DAG is... 125cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 126cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode *addNode(SelectionDAGNode *N) { 127cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner AllNodes.push_back(N); 128cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner return N; 129cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 130cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 131cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// addNodeForValue - Add the specified node to the SelectionDAG so that it 132cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// will be deleted when the DAG is... and update the value map to indicate 133cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// that the specified DAG node computes the value. Note that it is an error 134cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// to specify multiple DAG nodes that compute the same value. 135cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 136cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode *addNodeForValue(SelectionDAGNode *N, const Value *V) { 137cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner assert(ValueMap.count(V) == 0 && "Value already has a DAG node!"); 138cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner return addNode(ValueMap[V] = N); 139cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 140cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 141cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void dump() const; 142cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerprivate: 143cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void addInstructionToDAG(const Instruction &I, const BasicBlock &BB); 144cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner}; 145cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 146cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 147cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// SelectionDAGReducedValue - During the reducer pass we need the ability to 148cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// add an arbitrary (but usually 1 or 0) number of arbitrarily sized values to 149cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// the selection DAG. Because of this, we represent these values as a singly 150cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// linked list of values attached to the DAGNode. We end up putting the 151cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// arbitrary state for the value in subclasses of this node. 152cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// 153cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// Note that this class does not have a virtual dtor, this is because we know 154cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// that the subclasses will not hold state that needs to be destroyed. 155cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// 156cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass SelectionDAGReducedValue { 157cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner unsigned Code; 158cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGReducedValue *Next; 159cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerpublic: 160cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGReducedValue(unsigned C) : Code(C), Next(0) {} 161cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 162cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// getValueCode - Return the code for this reducer value... 163cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 164cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner unsigned getValueCode() const { return Code; } 165cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 166cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// getNext - Return the next value in the list 167cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 168cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner const SelectionDAGReducedValue *getNext() const { return Next; } 169cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void setNext(SelectionDAGReducedValue *N) { Next = N; } 170cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 171cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGReducedValue *getNext() { return Next; } 172cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner}; 173cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 174cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 175cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 176cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// SelectionDAGNode - Represents one node in the selection DAG. 177cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// 178cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerclass SelectionDAGNode { 179cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner std::vector<SelectionDAGNode*> Uses; 180cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner ISD::NodeType NodeType; 181cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner MVT::ValueType ValueType; 182cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner MachineBasicBlock *BB; 183cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGReducedValue *ValList; 184cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 185cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// Costs - Each pair of elements of 'Costs' contains the cost of producing 186cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// the value with the target specific slot number and the production number 187cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// to use to produce it. A zero value for the production number indicates 188cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// that the cost has not yet been computed. 189cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner unsigned *Costs; 190cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerpublic: 191cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, 192cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner MachineBasicBlock *bb = 0) 193cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) {} 194cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 195cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb, 196cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode *N) 197cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) { 198cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!"); 199cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Uses.reserve(1); Uses.push_back(N); 200cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 201cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb, 202cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode *N1, SelectionDAGNode *N2) 203cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) { 204cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!"); 205cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Uses.reserve(2); Uses.push_back(N1); Uses.push_back(N2); 206cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 207f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner SelectionDAGNode(ISD::NodeType NT, MVT::ValueType VT, MachineBasicBlock *bb, 208f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner SelectionDAGNode *N1, SelectionDAGNode *N2, 209f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner SelectionDAGNode *N3) 210f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner : NodeType(NT), ValueType(VT), BB(bb), ValList(0), Costs(0) { 211f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner assert(NT != ISD::ProtoNode && "Cannot specify uses for a protonode!"); 212f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner Uses.reserve(3); Uses.push_back(N1); Uses.push_back(N2); Uses.push_back(N3); 213f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner } 214cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 215cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner ~SelectionDAGNode() { delete [] Costs; delete ValList; } 216cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 217cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void setNode(ISD::NodeType NT, MachineBasicBlock *bb) { 218cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode); 219cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner NodeType = NT; BB = bb; 220cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 221cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void setNode(ISD::NodeType NT, MachineBasicBlock *bb, SelectionDAGNode *N) { 222cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode); 223cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner NodeType = NT; BB = bb; Uses.reserve(1); Uses.push_back(N); 224cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 225cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void setNode(ISD::NodeType NT, MachineBasicBlock *bb, 226cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode *N1, SelectionDAGNode *N2) { 227cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner assert(NodeType == ISD::ProtoNode && NT != ISD::ProtoNode); 228cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner NodeType = NT; BB = bb; 229cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Uses.reserve(1); Uses.push_back(N1); Uses.push_back(N2); 230cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 231cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 232cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner //===--------------------------------------------------------------------===// 233cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // Accessors 234cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // 235cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner ISD::NodeType getNodeType() const { return NodeType; } 236cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner MVT::ValueType getValueType() const { return ValueType; } 237cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner MachineBasicBlock *getBB() const { return BB; } 238cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 239cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGNode *getUse(unsigned Num) { 240cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner assert(Num < Uses.size() && "Invalid child # of SelectionDAGNode!"); 241cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner return Uses[Num]; 242cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 243cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 244cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner template<class Type> 245cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Type *getValue(unsigned Code) const { 246cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGReducedValue *Vals = ValList; 247cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner while (1) { 248cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner assert(Vals && "Code does not exist in this list!"); 249cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner if (Vals->getValueCode() == Code) 250cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner return (Type*)Vals; 251cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Vals = Vals->getNext(); 252cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 253cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 254cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 255cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner template<class Type> 256cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Type *hasValue(unsigned Code) const { 257cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner SelectionDAGReducedValue *Vals = ValList; 258cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner while (Vals) { 259cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner if (Vals->getValueCode() == Code) 260cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner return (Type*)Vals; 261cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Vals = Vals->getNext(); 262cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 263cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner return false; 264cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 265cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 266cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void addValue(SelectionDAGReducedValue *New) { 267cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner assert(New->getNext() == 0); 268cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner New->setNext(ValList); 269cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner ValList = New; 270cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 271cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 272cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner //===--------------------------------------------------------------------===// 273cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // Utility methods used by the pattern matching instruction selector 274cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner // 275cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 276cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// getPatternFor - Return the pattern selected to compute the specified slot, 277cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// or zero if there is no pattern yet. 278cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 279cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner unsigned getPatternFor(unsigned Slot) const { 280cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner return Costs ? Costs[Slot*2] : 0; 281cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 282cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 283cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// getCostFor - Return the cost to compute the value corresponding to Slot. 284cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 285cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner unsigned getCostFor(unsigned Slot) const { 286cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner return Costs ? Costs[Slot*2+1] : 0; 287cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 288cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 289cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// setPatternCostFor - Sets the pattern and the cost for the specified slot 290cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// to the specified values. This allocates the Costs vector if necessary, so 291cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// you must specify the maximum number of slots that may be used. 292cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// 293cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void setPatternCostFor(unsigned Slot, unsigned Pattern, unsigned Cost, 294cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner unsigned NumSlots) { 295cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner if (Costs == 0) { 296cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Costs = new unsigned[NumSlots*2]; 297cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner for (unsigned i = 0; i != NumSlots*2; ++i) Costs[i] = 0; 298cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 299cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Costs[Slot*2] = Pattern; 300cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Costs[Slot*2+1] = Cost; 301cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner } 302cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 303cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void dump() const; 304cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerprivate: 305cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner void printit(unsigned Offset, unsigned &LastID, 306cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner std::map<const SelectionDAGNode*, unsigned> &NodeIDs) const; 307cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner}; 308cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 309cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 310cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// SelectionDAGTargetBuilder - This class must be implemented by the target, to 311cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// indicate how to perform the extremely target-specific tasks of building DAG 312cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// nodes to represent the calling convention used by the target. 313cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner/// 314cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerstruct SelectionDAGTargetBuilder { 315cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// expandArguments - This method is called once by the SelectionDAG 316cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// construction mechanisms to add DAG nodes for each formal argument to the 317cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// current function. If any of the incoming arguments lives on the stack, 318cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// this method should also create the stack slots for the arguments as 319cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// necessary. 320f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner virtual void expandArguments(SelectionDAG &SD) = 0; 321f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner 322f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner /// expandCall - This method is called once per function call by the 323f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner /// SelectionDAG construction algorithm. It must add DAG nodes to the 324f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner /// SelectionDAG specified to perform that call. 325f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner virtual void expandCall(SelectionDAG &SD, CallInst &CI) = 0; 326cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner}; 327cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 328cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnernamespace ISD { 329cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner enum { // Builtin Slot numbers 330cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Constant_i1_Slot, 331cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Constant_i8_Slot, 332cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Constant_i16_Slot, 333cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Constant_i32_Slot, 334cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Constant_i64_Slot, 335cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Constant_f32_Slot, 336cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Constant_f64_Slot, 337cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 338cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner FrameIndex_i32_Slot, 339cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner FrameIndex_i64_Slot, 340f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner BasicBlock_i32_Slot, 341f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattner BasicBlock_i64_Slot, 342cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner NumBuiltinSlots 343cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner }; 344cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner} 345cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 346cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnertemplate<typename ValType, unsigned NodeCode> 347cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnerstruct ReducedValue : public SelectionDAGReducedValue { 348cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner ReducedValue(const ValType &V) : SelectionDAGReducedValue(NodeCode), Val(V) {} 349cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner ValType Val; 350cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner}; 351cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 352cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnertypedef ReducedValue<int, ISD::FrameIndex_i32_Slot > ReducedValue_FrameIndex_i32; 353cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnertypedef ReducedValue<int, ISD::FrameIndex_i64_Slot > ReducedValue_FrameIndex_i64; 354f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattnertypedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i32_Slot > ReducedValue_BasicBlock_i32; 355f4f5f8bcaa388f663bdbd49b8ee4914f39a3a20aChris Lattnertypedef ReducedValue<MachineBasicBlock*, ISD::BasicBlock_i64_Slot > ReducedValue_BasicBlock_i64; 356cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 357cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnertypedef ReducedValue<bool , ISD::Constant_i1_Slot > ReducedValue_Constant_i1; 358cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnertypedef ReducedValue<unsigned char , ISD::Constant_i8_Slot > ReducedValue_Constant_i8; 359cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnertypedef ReducedValue<unsigned short, ISD::Constant_i16_Slot> ReducedValue_Constant_i16; 360cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnertypedef ReducedValue<unsigned , ISD::Constant_i32_Slot> ReducedValue_Constant_i32; 361cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnertypedef ReducedValue<uint64_t , ISD::Constant_i64_Slot> ReducedValue_Constant_i64; 362cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnertypedef ReducedValue<float , ISD::Constant_f32_Slot> ReducedValue_Constant_f32; 363cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattnertypedef ReducedValue<double , ISD::Constant_f64_Slot> ReducedValue_Constant_f64; 364cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 365cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#endif 366