1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements the SelectionDAG::LegalizeTypes method. It transforms 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// an arbitrary well-formed SelectionDAG to only consist of legal types. This 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// is common code shared among the LegalizeTypes*.cpp files. 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "LegalizeTypes.h" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CallingConv.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetData.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SetVector.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/CommandLine.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/ErrorHandling.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/raw_ostream.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic cl::opt<bool> 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanEnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden); 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// PerformExpensiveChecks - Do extensive, expensive, sanity checking. 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::PerformExpensiveChecks() { 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If a node is not processed, then none of its values should be mapped by any 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If a node is processed, then each value with an illegal type must be mapped 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // by exactly one of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Values with a legal type may be mapped by ReplacedValues, but not by any of 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the other maps. 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that these invariants may not hold momentarily when processing a node: 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the node being processed may be put in a map before being marked Processed. 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that it is possible to have nodes marked NewNode in the DAG. This can 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // occur in two ways. Firstly, a node may be created during legalization but 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // never passed to the legalization core. This is usually due to the implicit 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // folding that occurs when using the DAG.getNode operators. Secondly, a new 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // node may be passed to the legalization core, but when analyzed may morph 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // into a different node, leaving the original node as a NewNode in the DAG. 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // A node may morph if one of its operands changes during analysis. Whether 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // it actually morphs or not depends on whether, after updating its operands, 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // it is equivalent to an existing node: if so, it morphs into that existing 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // node (CSE). An operand can change during analysis if the operand is a new 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // node that morphs, or it is a processed value that was mapped to some other 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // value (as recorded in ReplacedValues) in which case the operand is turned 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // into that other value. If a node morphs then the node it morphed into will 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // be used instead of it for legalization, however the original node continues 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to live on in the DAG. 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The conclusion is that though there may be nodes marked NewNode in the DAG, 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // all uses of such nodes are also marked NewNode: the result is a fungus of 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // NewNodes growing on top of the useful nodes, and perhaps using them, but 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // not used by them. 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If a value is mapped by ReplacedValues, then it must have no uses, except 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // by nodes marked NewNode (see above). 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The final node obtained by mapping by ReplacedValues is not marked NewNode. 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that ReplacedValues should be applied iteratively. 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that the ReplacedValues map may also map deleted nodes (by iterating 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // over the DAG we never dereference deleted nodes). This means that it may 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // also map nodes marked NewNode if the deallocated memory was reallocated as 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // another node, and that new node was not seen by the LegalizeTypes machinery 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // (for example because it was created but not used). In general, we cannot 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // distinguish between new nodes and deleted nodes. 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SDNode*, 16> NewNodes; 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = DAG.allnodes_end(); I != E; ++I) { 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember nodes marked NewNode - they are subject to extra checking below. 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getNodeId() == NewNode) 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewNodes.push_back(I); 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = I->getNumValues(); i != e; ++i) { 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue Res(I, i); 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Failed = false; 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Mapped = 0; 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ReplacedValues.find(Res) != ReplacedValues.end()) { 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Mapped |= 1; 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check that remapped values are only used by nodes marked NewNode. 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SDNode::use_iterator UI = I->use_begin(), UE = I->use_end(); 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != UE; ++UI) 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (UI.getUse().getResNo() == i) 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(UI->getNodeId() == NewNode && 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Remapped value has non-trivial use!"); 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check that the final result of applying ReplacedValues is not 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // marked NewNode. 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue NewVal = ReplacedValues[Res]; 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(NewVal); 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (I != ReplacedValues.end()) { 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewVal = I->second; 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I = ReplacedValues.find(NewVal); 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(NewVal.getNode()->getNodeId() != NewNode && 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "ReplacedValues maps to a new node!"); 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PromotedIntegers.find(Res) != PromotedIntegers.end()) 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Mapped |= 2; 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SoftenedFloats.find(Res) != SoftenedFloats.end()) 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Mapped |= 4; 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ScalarizedVectors.find(Res) != ScalarizedVectors.end()) 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Mapped |= 8; 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ExpandedIntegers.find(Res) != ExpandedIntegers.end()) 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Mapped |= 16; 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ExpandedFloats.find(Res) != ExpandedFloats.end()) 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Mapped |= 32; 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SplitVectors.find(Res) != SplitVectors.end()) 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Mapped |= 64; 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (WidenedVectors.find(Res) != WidenedVectors.end()) 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Mapped |= 128; 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getNodeId() != Processed) { 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Since we allow ReplacedValues to map deleted nodes, it may map nodes 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // marked NewNode too, since a deleted node may have been reallocated as 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // another node that has not been seen by the LegalizeTypes machinery. 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((I->getNodeId() == NewNode && Mapped > 1) || 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (I->getNodeId() != NewNode && Mapped != 0)) { 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "Unprocessed value in a map!"; 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Failed = true; 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (isTypeLegal(Res.getValueType()) || IgnoreNodeResults(I)) { 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Mapped > 1) { 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "Value with legal type was transformed!"; 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Failed = true; 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Mapped == 0) { 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "Processed value not in any map!"; 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Failed = true; 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (Mapped & (Mapped - 1)) { 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "Value in multiple maps!"; 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Failed = true; 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Failed) { 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Mapped & 1) 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << " ReplacedValues"; 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Mapped & 2) 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << " PromotedIntegers"; 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Mapped & 4) 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << " SoftenedFloats"; 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Mapped & 8) 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << " ScalarizedVectors"; 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Mapped & 16) 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << " ExpandedIntegers"; 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Mapped & 32) 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << " ExpandedFloats"; 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Mapped & 64) 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << " SplitVectors"; 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Mapped & 128) 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << " WidenedVectors"; 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "\n"; 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman llvm_unreachable(0); 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Checked that NewNodes are only used by other NewNodes. 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = NewNodes.size(); i != e; ++i) { 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *N = NewNodes[i]; 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != UE; ++UI) 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(UI->getNodeId() == NewNode && "NewNode used by non-NewNode!"); 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// run - This is the main entry point for the type legalizer. This does a 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// top-down traversal of the dag, legalizing types as it goes. Returns "true" 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// if it made any changes. 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool DAGTypeLegalizer::run() { 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Changed = false; 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create a dummy node (which is not added to allnodes), that adds a reference 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to the root node, preventing it from being deleted, and tracking any 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // changes of the root. 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman HandleSDNode Dummy(DAG.getRoot()); 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Dummy.setNodeId(Unanalyzed); 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The root of the dag may dangle to deleted nodes until the type legalizer is 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // done. Set it to null to avoid confusion. 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG.setRoot(SDValue()); 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess' 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // (and remembering them) if they are leaves and assigning 'Unanalyzed' if 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // non-leaves. 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = DAG.allnodes_end(); I != E; ++I) { 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getNumOperands() == 0) { 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setNodeId(ReadyToProcess); 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Worklist.push_back(I); 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->setNodeId(Unanalyzed); 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that we have a set of nodes to process, handle them all. 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (!Worklist.empty()) { 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef XDEBUG 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (EnableExpensiveChecks) 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PerformExpensiveChecks(); 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *N = Worklist.back(); 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Worklist.pop_back(); 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNodeId() == ReadyToProcess && 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Node should be ready if on worklist!"); 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (IgnoreNodeResults(N)) 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman goto ScanOperands; 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan the values produced by the node, checking to see if any result 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // types are illegal. 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) { 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT ResultVT = N->getValueType(i); 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (getTypeAction(ResultVT)) { 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman default: 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(false && "Unknown action!"); 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeLegal: 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The following calls must take care of *all* of the node's results, 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // not just the illegal result they were passed (this includes results 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // with a legal type). Results can be remapped using ReplaceValueWith, 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // or their promoted/expanded/etc values registered in PromotedIntegers, 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // ExpandedIntegers etc. 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypePromoteInteger: 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PromoteIntegerResult(N, i); 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman goto NodeDone; 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeExpandInteger: 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExpandIntegerResult(N, i); 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman goto NodeDone; 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeSoftenFloat: 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SoftenFloatResult(N, i); 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman goto NodeDone; 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeExpandFloat: 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExpandFloatResult(N, i); 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman goto NodeDone; 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeScalarizeVector: 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScalarizeVectorResult(N, i); 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman goto NodeDone; 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeSplitVector: 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SplitVectorResult(N, i); 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman goto NodeDone; 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeWidenVector: 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman WidenVectorResult(N, i); 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman goto NodeDone; 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanScanOperands: 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan the operand list for the node, handling any nodes with operands that 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // are illegal. 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman { 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumOperands = N->getNumOperands(); 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool NeedsReanalyzing = false; 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned i; 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (i = 0; i != NumOperands; ++i) { 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (IgnoreNodeResults(N->getOperand(i).getNode())) 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT OpVT = N->getOperand(i).getValueType(); 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (getTypeAction(OpVT)) { 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman default: 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(false && "Unknown action!"); 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeLegal: 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The following calls must either replace all of the node's results 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // using ReplaceValueWith, and return "false"; or update the node's 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // operands in place, and return "true". 28519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypePromoteInteger: 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NeedsReanalyzing = PromoteIntegerOperand(N, i); 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeExpandInteger: 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NeedsReanalyzing = ExpandIntegerOperand(N, i); 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeSoftenFloat: 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NeedsReanalyzing = SoftenFloatOperand(N, i); 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeExpandFloat: 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NeedsReanalyzing = ExpandFloatOperand(N, i); 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeScalarizeVector: 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NeedsReanalyzing = ScalarizeVectorOperand(N, i); 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeSplitVector: 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NeedsReanalyzing = SplitVectorOperand(N, i); 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman case TargetLowering::TypeWidenVector: 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NeedsReanalyzing = WidenVectorOperand(N, i); 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The sub-method updated N in place. Check to see if any operands are new, 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and if so, mark them. If the node needs revisiting, don't add all users 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to the worklist etc. 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NeedsReanalyzing) { 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->setNodeId(NewNode); 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Recompute the NodeId and correct processed operands, adding the node to 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the worklist if ready. 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *M = AnalyzeNewNode(N); 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (M == N) 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The node didn't morph - nothing special to do, it will be revisited. 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The node morphed - this is equivalent to legalizing by replacing every 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // value of N with the corresponding value of M. So do that now. 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNumValues() == M->getNumValues() && 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Node morphing changed the number of results!"); 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Replacing the value takes care of remapping the new value. 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ReplaceValueWith(SDValue(N, i), SDValue(M, i)); 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNodeId() == NewNode && "Unexpected node state!"); 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The node continues to live on as part of the NewNode fungus that 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // grows on top of the useful nodes. Nothing more needs to be done 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // with it - move on to the next node. 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i == NumOperands) { 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Legally typed node: "; N->dump(&DAG); dbgs() << "\n"); 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanNodeDone: 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we reach here, the node was processed, potentially creating new nodes. 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Mark it as processed and add its users to the worklist as appropriate. 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->setNodeId(Processed); 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ++UI) { 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *User = *UI; 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int NodeId = User->getNodeId(); 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This node has two options: it can either be a new node or its Node ID 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // may be a count of the number of operands it has that are not ready. 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NodeId > 0) { 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman User->setNodeId(NodeId-1); 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this was the last use it was waiting on, add it to the ready list. 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NodeId-1 == ReadyToProcess) 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Worklist.push_back(User); 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is an unreachable new node, then ignore it. If it ever becomes 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // reachable by being used by a newly created node then it will be handled 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // by AnalyzeNewNode. 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NodeId == NewNode) 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, this node is new: this is the first operand of it that 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // became ready. Its new NodeId is the number of operands it has minus 1 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // (as this node is now processed). 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(NodeId == Unanalyzed && "Unknown node ID!"); 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman User->setNodeId(User->getNumOperands() - 1); 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the node only has a single operand, it is now ready. 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (User->getNumOperands() == 1) 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Worklist.push_back(User); 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef XDEBUG 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (EnableExpensiveChecks) 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PerformExpensiveChecks(); 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the root changed (e.g. it was a dead load) update the root. 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG.setRoot(Dummy.getValue()); 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove dead nodes. This is important to do for cleanliness but also before 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the checking loop below. Implicit folding by the DAG.getNode operators and 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // node morphing can cause unreachable nodes to be around with their flags set 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to new. 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG.RemoveDeadNodes(); 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // In a debug build, scan all the nodes to make sure we found them all. This 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // ensures that there are no cycles and that everything got processed. 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef NDEBUG 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = DAG.allnodes_end(); I != E; ++I) { 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Failed = false; 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check that all result types are legal. 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!IgnoreNodeResults(I)) 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, NumVals = I->getNumValues(); i < NumVals; ++i) 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isTypeLegal(I->getValueType(i))) { 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "Result type " << i << " illegal!\n"; 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Failed = true; 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check that all operand types are legal. 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, NumOps = I->getNumOperands(); i < NumOps; ++i) 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!IgnoreNodeResults(I->getOperand(i).getNode()) && 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !isTypeLegal(I->getOperand(i).getValueType())) { 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "Operand type " << i << " illegal!\n"; 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Failed = true; 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getNodeId() != Processed) { 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getNodeId() == NewNode) 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "New node not analyzed?\n"; 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else if (I->getNodeId() == Unanalyzed) 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "Unanalyzed node not noticed?\n"; 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else if (I->getNodeId() > 0) 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "Operand not processed?\n"; 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else if (I->getNodeId() == ReadyToProcess) 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "Not added to worklist?\n"; 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Failed = true; 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Failed) { 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->dump(&DAG); dbgs() << "\n"; 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman llvm_unreachable(0); 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Changed; 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// AnalyzeNewNode - The specified node is the root of a subtree of potentially 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// new nodes. Correct any processed operands (this may change the node) and 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// calculate the NodeId. If the node itself changes to a processed node, it 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// is not remapped - the caller needs to take care of this. 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Returns the potentially changed node. 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) { 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this was an existing node that is already done, we're done. 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed) 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return N; 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove any stale map entries. 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExpungeNode(N); 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, we know that this node is new. Recursively walk all of its operands 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to see if they are new also. The depth of this walk is bounded by the size 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // of the new tree that was constructed (usually 2-3 nodes), so we don't worry 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // about revisiting of nodes. 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // As we walk the operands, keep track of the number of nodes that are 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // processed. If non-zero, this will become the new nodeid of this node. 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Operands may morph when they are analyzed. If so, the node will be 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // updated after all operands have been analyzed. Since this is rare, 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the code tries to minimize overhead in the non-morphing case. 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SDValue, 8> NewOps; 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumProcessed = 0; 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue OrigOp = N->getOperand(i); 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue Op = OrigOp; 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Op); // Op may morph. 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Op.getNode()->getNodeId() == Processed) 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumProcessed; 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!NewOps.empty()) { 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Some previous operand changed. Add this one to the list. 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewOps.push_back(Op); 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (Op != OrigOp) { 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This is the first operand to change - add all operands so far. 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewOps.append(N->op_begin(), N->op_begin() + i); 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NewOps.push_back(Op); 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Some operands changed - update the node. 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!NewOps.empty()) { 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *M = DAG.UpdateNodeOperands(N, &NewOps[0], NewOps.size()); 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (M != N) { 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The node morphed into a different node. Normally for this to happen 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the original node would have to be marked NewNode. However this can 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // in theory momentarily not be the case while ReplaceValueWith is doing 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // its stuff. Mark the original node NewNode to help sanity checking. 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->setNodeId(NewNode); 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (M->getNodeId() != NewNode && M->getNodeId() != Unanalyzed) 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // It morphed into a previously analyzed node - nothing more to do. 504894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return M; 505894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // It morphed into a different new node. Do the equivalent of passing 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // it to AnalyzeNewNode: expunge it and calculate the NodeId. No need 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to remap the operands, since they are the same as the operands we 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // remapped above. 510894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N = M; 511894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExpungeNode(N); 512894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 513894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 514894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 515894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Calculate the NodeId. 516894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->setNodeId(N->getNumOperands() - NumProcessed); 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (N->getNodeId() == ReadyToProcess) 518894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Worklist.push_back(N); 519894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return N; 521894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// AnalyzeNewValue - Call AnalyzeNewNode, updating the node in Val if needed. 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// If the node changes to a processed node, then remap it. 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) { 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Val.setNode(AnalyzeNewNode(Val.getNode())); 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Val.getNode()->getNodeId() == Processed) 528894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We were passed a processed node, or it morphed into one - remap it. 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(Val); 530894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ExpungeNode - If N has a bogus mapping in ReplacedValues, eliminate it. 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// This can occur when a node is deleted then reallocated as a new node - 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the mapping in ReplacedValues applies to the deleted node, not the new 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// one. 536894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The only map that can have a deleted node as a source is ReplacedValues. 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Other maps can have deleted nodes as targets, but since their looked-up 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// values are always immediately remapped using RemapValue, resulting in a 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// not-deleted node, this is harmless as long as ReplacedValues/RemapValue 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// always performs correct mappings. In order to keep the mapping correct, 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ExpungeNode should be called on any new nodes *before* adding them as 542894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// either source or target to ReplacedValues (which typically means calling 543894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Expunge when a new node is first seen, since it may no longer be marked 544894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// NewNode by the time it is added to ReplacedValues). 545894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::ExpungeNode(SDNode *N) { 546894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (N->getNodeId() != NewNode) 547894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 548894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 549894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If N is not remapped by ReplacedValues then there is nothing to do. 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned i, e; 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (i = 0, e = N->getNumValues(); i != e; ++i) 552894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ReplacedValues.find(SDValue(N, i)) != ReplacedValues.end()) 553894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 554894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 555894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i == e) 556894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 557894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 558894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove N from all maps - this is expensive but rare. 559894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 560894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (DenseMap<SDValue, SDValue>::iterator I = PromotedIntegers.begin(), 561894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = PromotedIntegers.end(); I != E; ++I) { 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I->first.getNode() != N); 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second); 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 566894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (DenseMap<SDValue, SDValue>::iterator I = SoftenedFloats.begin(), 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = SoftenedFloats.end(); I != E; ++I) { 568894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I->first.getNode() != N); 569894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second); 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 571894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (DenseMap<SDValue, SDValue>::iterator I = ScalarizedVectors.begin(), 573894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = ScalarizedVectors.end(); I != E; ++I) { 574894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I->first.getNode() != N); 575894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second); 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 577894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 578894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (DenseMap<SDValue, SDValue>::iterator I = WidenedVectors.begin(), 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = WidenedVectors.end(); I != E; ++I) { 580894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I->first.getNode() != N); 581894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second); 582894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 583894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 584894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator 585894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I = ExpandedIntegers.begin(), E = ExpandedIntegers.end(); I != E; ++I){ 586894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I->first.getNode() != N); 587894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second.first); 588894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second.second); 589894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 590894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 591894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator 592894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I = ExpandedFloats.begin(), E = ExpandedFloats.end(); I != E; ++I) { 593894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I->first.getNode() != N); 594894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second.first); 595894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second.second); 596894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 597894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 598894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator 599894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I = SplitVectors.begin(), E = SplitVectors.end(); I != E; ++I) { 600894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I->first.getNode() != N); 601894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second.first); 602894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second.second); 603894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 604894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 605894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.begin(), 606894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = ReplacedValues.end(); I != E; ++I) 607894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second); 608894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 609894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 610894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ReplacedValues.erase(SDValue(N, i)); 611894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 612894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 613894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RemapValue - If the specified value was already legalized to another value, 614894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// replace it by that value. 615894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::RemapValue(SDValue &N) { 616894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(N); 617894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I != ReplacedValues.end()) { 618894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Use path compression to speed up future lookups if values get multiply 619894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // replaced with other values. 620894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(I->second); 621894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N = I->second; 622894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N.getNode()->getNodeId() != NewNode && "Mapped to new node!"); 623894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 625894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 626894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 627894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// NodeUpdateListener - This class is a DAGUpdateListener that listens for 628894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// updates to nodes and recomputes their ready state. 629894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class NodeUpdateListener : public SelectionDAG::DAGUpdateListener { 630894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAGTypeLegalizer &DTL; 631894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSetVector<SDNode*, 16> &NodesToAnalyze; 632894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 633894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit NodeUpdateListener(DAGTypeLegalizer &dtl, 634894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSetVector<SDNode*, 16> &nta) 635894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : DTL(dtl), NodesToAnalyze(nta) {} 636894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 637894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void NodeDeleted(SDNode *N, SDNode *E) { 638894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 639894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->getNodeId() != DAGTypeLegalizer::Processed && 640894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Invalid node ID for RAUW deletion!"); 641894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // It is possible, though rare, for the deleted node N to occur as a 642894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // target in a map, so note the replacement N -> E in ReplacedValues. 643894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(E && "Node not replaced?"); 644894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DTL.NoteDeletion(N, E); 645894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 646894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // In theory the deleted node could also have been scheduled for analysis. 647894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // So remove it from the set of nodes which will be analyzed. 648894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodesToAnalyze.remove(N); 649894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 650894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // In general nothing needs to be done for E, since it didn't change but 651894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // only gained new uses. However N -> E was just added to ReplacedValues, 652894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and the result of a ReplacedValues mapping is not allowed to be marked 653894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // NewNode. So if E is marked NewNode, then it needs to be analyzed. 654894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (E->getNodeId() == DAGTypeLegalizer::NewNode) 655894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodesToAnalyze.insert(E); 656894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 657894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 658894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void NodeUpdated(SDNode *N) { 659894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Node updates can mean pretty much anything. It is possible that an 660894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // operand was set to something already processed (f.e.) in which case 661894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this node could become ready. Recompute its flags. 662894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 663894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->getNodeId() != DAGTypeLegalizer::Processed && 664894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Invalid node ID for RAUW deletion!"); 665894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->setNodeId(DAGTypeLegalizer::NewNode); 666894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodesToAnalyze.insert(N); 667894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 668894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 669894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 670894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 671894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 672894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ReplaceValueWith - The specified value was legalized to the specified other 673894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// value. Update the DAG and NodeIds replacing any uses of From to use To 674894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// instead. 675894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) { 676894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(From.getNode() != To.getNode() && "Potential legalization loop!"); 677894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 678894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If expansion produced new nodes, make sure they are properly marked. 679894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExpungeNode(From.getNode()); 680894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(To); // Expunges To. 681894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 682894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Anything that used the old node should now use the new one. Note that this 683894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // can potentially cause recursive merging. 684894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSetVector<SDNode*, 16> NodesToAnalyze; 685894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodeUpdateListener NUL(*this, NodesToAnalyze); 686894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do { 687894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG.ReplaceAllUsesOfValueWith(From, To, &NUL); 688894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 689894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The old node may still be present in a map like ExpandedIntegers or 690894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // PromotedIntegers. Inform maps about the replacement. 691894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ReplacedValues[From] = To; 692894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 693894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Process the list of nodes that need to be reanalyzed. 694894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (!NodesToAnalyze.empty()) { 695894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *N = NodesToAnalyze.back(); 696894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodesToAnalyze.pop_back(); 697894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (N->getNodeId() != DAGTypeLegalizer::NewNode) 698894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The node was analyzed while reanalyzing an earlier node - it is safe 699894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to skip. Note that this is not a morphing node - otherwise it would 700894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // still be marked NewNode. 701894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 702894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 703894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Analyze the node's operands and recalculate the node ID. 704894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *M = AnalyzeNewNode(N); 705894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (M != N) { 706894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The node morphed into a different node. Make everyone use the new 707894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // node instead. 708894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!"); 709894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(N->getNumValues() == M->getNumValues() && 710894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Node morphing changed the number of results!"); 711894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 712894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue OldVal(N, i); 713894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue NewVal(M, i); 714894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (M->getNodeId() == Processed) 715894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(NewVal); 716894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal, &NUL); 71719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // OldVal may be a target of the ReplacedValues map which was marked 71819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // NewNode to force reanalysis because it was updated. Ensure that 71919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // anything that ReplacedValues mapped to OldVal will now be mapped 72019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // all the way to NewVal. 72119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReplacedValues[OldVal] = NewVal; 722894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 723894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The original node continues to exist in the DAG, marked NewNode. 724894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 725894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 726894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // When recursively update nodes with new nodes, it is possible to have 727894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // new uses of From due to CSE. If this happens, replace the new uses of 728894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // From with To. 729894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } while (!From.use_empty()); 730894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 731894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 732894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) { 733894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Result.getValueType() == 734894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 735894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Invalid type for promoted integer"); 736894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Result); 737894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 738894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue &OpEntry = PromotedIntegers[Op]; 739894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(OpEntry.getNode() == 0 && "Node is already promoted!"); 740894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OpEntry = Result; 741894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 742894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 743894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) { 744894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Result.getValueType() == 745894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 746894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Invalid type for softened float"); 747894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Result); 748894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 749894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue &OpEntry = SoftenedFloats[Op]; 750894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(OpEntry.getNode() == 0 && "Node is already converted to integer!"); 751894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OpEntry = Result; 752894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 753894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 754894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) { 755894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Result.getValueType() == Op.getValueType().getVectorElementType() && 756894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Invalid type for scalarized vector"); 757894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Result); 758894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 759894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue &OpEntry = ScalarizedVectors[Op]; 760894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(OpEntry.getNode() == 0 && "Node is already scalarized!"); 761894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OpEntry = Result; 762894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 763894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 764894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo, 765894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue &Hi) { 766894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op]; 767894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(Entry.first); 768894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(Entry.second); 769894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Entry.first.getNode() && "Operand isn't expanded"); 770894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Lo = Entry.first; 771894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi = Entry.second; 772894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 773894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 774894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo, 775894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue Hi) { 776894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Lo.getValueType() == 777894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 778894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi.getValueType() == Lo.getValueType() && 779894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Invalid type for expanded integer"); 780894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 781894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Lo); 782894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Hi); 783894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 784894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember that this is the result of the node. 785894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op]; 786894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Entry.first.getNode() == 0 && "Node already expanded"); 787894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Entry.first = Lo; 788894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Entry.second = Hi; 789894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 790894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 791894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo, 792894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue &Hi) { 793894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op]; 794894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(Entry.first); 795894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(Entry.second); 796894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Entry.first.getNode() && "Operand isn't expanded"); 797894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Lo = Entry.first; 798894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi = Entry.second; 799894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 800894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 801894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo, 802894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue Hi) { 803894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Lo.getValueType() == 804894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 805894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi.getValueType() == Lo.getValueType() && 806894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Invalid type for expanded float"); 807894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 808894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Lo); 809894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Hi); 810894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 811894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember that this is the result of the node. 812894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op]; 813894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Entry.first.getNode() == 0 && "Node already expanded"); 814894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Entry.first = Lo; 815894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Entry.second = Hi; 816894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 817894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 818894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo, 819894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue &Hi) { 820894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::pair<SDValue, SDValue> &Entry = SplitVectors[Op]; 821894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(Entry.first); 822894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RemapValue(Entry.second); 823894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Entry.first.getNode() && "Operand isn't split"); 824894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Lo = Entry.first; 825894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi = Entry.second; 826894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 827894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 828894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo, 829894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue Hi) { 830894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Lo.getValueType().getVectorElementType() == 831894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Op.getValueType().getVectorElementType() && 832894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 2*Lo.getValueType().getVectorNumElements() == 833894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Op.getValueType().getVectorNumElements() && 834894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi.getValueType() == Lo.getValueType() && 835894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Invalid type for split vector"); 836894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 837894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Lo); 838894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Hi); 839894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 840894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember that this is the result of the node. 841894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::pair<SDValue, SDValue> &Entry = SplitVectors[Op]; 842894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Entry.first.getNode() == 0 && "Node already split"); 843894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Entry.first = Lo; 844894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Entry.second = Hi; 845894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 846894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 847894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) { 848894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Result.getValueType() == 849894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 850894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Invalid type for widened vector"); 851894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AnalyzeNewValue(Result); 852894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 853894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue &OpEntry = WidenedVectors[Op]; 854894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(OpEntry.getNode() == 0 && "Node already widened!"); 855894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OpEntry = Result; 856894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 857894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 858894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 859894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 860894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Utilities. 861894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 862894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 863894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// BitConvertToInteger - Convert to an integer of the same size. 864894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) { 865894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned BitWidth = Op.getValueType().getSizeInBits(); 86619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DAG.getNode(ISD::BITCAST, Op.getDebugLoc(), 867894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT::getIntegerVT(*DAG.getContext(), BitWidth), Op); 868894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 869894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 870894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// BitConvertVectorToIntegerVector - Convert to a vector of integers of the 871894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// same size. 872894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(SDValue Op) { 873894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Op.getValueType().isVector() && "Only applies to vectors!"); 874894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned EltWidth = Op.getValueType().getVectorElementType().getSizeInBits(); 875894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT EltNVT = EVT::getIntegerVT(*DAG.getContext(), EltWidth); 876894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumElts = Op.getValueType().getVectorNumElements(); 87719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DAG.getNode(ISD::BITCAST, Op.getDebugLoc(), 878894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT::getVectorVT(*DAG.getContext(), EltNVT, NumElts), Op); 879894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 880894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 881894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op, 882894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT DestVT) { 883894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DebugLoc dl = Op.getDebugLoc(); 884894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create the stack frame object. Make sure it is aligned for both 885894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the source and destination types. 886894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue StackPtr = DAG.CreateStackTemporary(Op.getValueType(), DestVT); 887894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Emit a store to the stack slot. 88819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, 88919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachinePointerInfo(), false, false, 0); 890894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Result is a load from the stack slot. 89119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DAG.getLoad(DestVT, dl, Store, StackPtr, MachinePointerInfo(), 89219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman false, false, 0); 893894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 894894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 895894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// CustomLowerNode - Replace the node's results with custom code provided 896894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// by the target and return "true", or do nothing and return "false". 897894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The last parameter is FALSE if we are dealing with a node with legal 898894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// result types and illegal operand. The second parameter denotes the type of 899894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// illegal OperandNo in that case. 900894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The last parameter being TRUE means we are dealing with a 901894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// node with illegal result types. The second parameter denotes the type of 902894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// illegal ResNo in that case. 903894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool DAGTypeLegalizer::CustomLowerNode(SDNode *N, EVT VT, bool LegalizeResult) { 904894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // See if the target wants to custom lower this node. 905894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) 906894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 907894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 908894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SDValue, 8> Results; 909894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LegalizeResult) 910894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.ReplaceNodeResults(N, Results, DAG); 911894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 912894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.LowerOperationWrapper(N, Results, DAG); 913894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 914894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Results.empty()) 915894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The target didn't want to custom lower it after all. 916894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 917894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 918894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make everything that once used N's values now use those in Results instead. 919894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Results.size() == N->getNumValues() && 920894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Custom lowering returned the wrong number of results!"); 921894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Results.size(); i != e; ++i) 922894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ReplaceValueWith(SDValue(N, i), Results[i]); 923894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 924894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 925894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 926894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 927894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// CustomWidenLowerNode - Widen the node's results with custom code provided 928894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// by the target and return "true", or do nothing and return "false". 929894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool DAGTypeLegalizer::CustomWidenLowerNode(SDNode *N, EVT VT) { 930894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // See if the target wants to custom lower this node. 931894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) 932894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 933894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 934894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SDValue, 8> Results; 935894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.ReplaceNodeResults(N, Results, DAG); 936894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 937894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Results.empty()) 938894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The target didn't want to custom widen lower its result after all. 939894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 940894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 941894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Update the widening map. 942894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Results.size() == N->getNumValues() && 943894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Custom lowering returned the wrong number of results!"); 944894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Results.size(); i != e; ++i) 945894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SetWidenedVector(SDValue(N, i), Results[i]); 946894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 947894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 948894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 94919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(SDNode *N, unsigned ResNo) { 95019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 95119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (i != ResNo) 95219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReplaceValueWith(SDValue(N, i), SDValue(N->getOperand(i))); 95319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return SDValue(N, ResNo); 95419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 95519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 956894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type 957894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// which is split into two not necessarily identical pieces. 958894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::GetSplitDestVTs(EVT InVT, EVT &LoVT, EVT &HiVT) { 959894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Currently all types are split in half. 960894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!InVT.isVector()) { 961894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoVT = HiVT = TLI.getTypeToTransformTo(*DAG.getContext(), InVT); 962894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 963894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumElements = InVT.getVectorNumElements(); 964894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!(NumElements & 1) && "Splitting vector, but not in half!"); 965894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoVT = HiVT = EVT::getVectorVT(*DAG.getContext(), 966894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InVT.getVectorElementType(), NumElements/2); 967894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 968894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 969894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 970894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// GetPairElements - Use ISD::EXTRACT_ELEMENT nodes to extract the low and 971894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// high parts of the given value. 972894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::GetPairElements(SDValue Pair, 973894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue &Lo, SDValue &Hi) { 974894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DebugLoc dl = Pair.getDebugLoc(); 975894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.getValueType()); 976894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair, 977894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG.getIntPtrConstant(0)); 978894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair, 979894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG.getIntPtrConstant(1)); 980894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 981894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 982894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSDValue DAGTypeLegalizer::GetVectorElementPointer(SDValue VecPtr, EVT EltVT, 983894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue Index) { 984894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DebugLoc dl = Index.getDebugLoc(); 985894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make sure the index type is big enough to compute in. 986894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Index.getValueType().bitsGT(TLI.getPointerTy())) 987894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Index = DAG.getNode(ISD::TRUNCATE, dl, TLI.getPointerTy(), Index); 988894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 989894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Index = DAG.getNode(ISD::ZERO_EXTEND, dl, TLI.getPointerTy(), Index); 990894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 991894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Calculate the element offset and add it to the pointer. 992894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size. 993894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 994894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Index = DAG.getNode(ISD::MUL, dl, Index.getValueType(), Index, 995894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG.getConstant(EltSize, Index.getValueType())); 996894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return DAG.getNode(ISD::ADD, dl, Index.getValueType(), Index, VecPtr); 997894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 998894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 999894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// JoinIntegers - Build an integer with low bits Lo and high bits Hi. 1000894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) { 1001894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Arbitrarily use dlHi for result DebugLoc 1002894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DebugLoc dlHi = Hi.getDebugLoc(); 1003894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DebugLoc dlLo = Lo.getDebugLoc(); 1004894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT LVT = Lo.getValueType(); 1005894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT HVT = Hi.getValueType(); 1006894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT NVT = EVT::getIntegerVT(*DAG.getContext(), 1007894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LVT.getSizeInBits() + HVT.getSizeInBits()); 1008894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1009894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo); 1010894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi); 1011894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi, 1012894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG.getConstant(LVT.getSizeInBits(), TLI.getPointerTy())); 1013894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi); 1014894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1015894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1016894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// LibCallify - Convert the node into a libcall with the same prototype. 1017894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSDValue DAGTypeLegalizer::LibCallify(RTLIB::Libcall LC, SDNode *N, 1018894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isSigned) { 1019894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumOps = N->getNumOperands(); 1020894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DebugLoc dl = N->getDebugLoc(); 1021894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumOps == 0) { 1022894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MakeLibCall(LC, N->getValueType(0), 0, 0, isSigned, dl); 1023894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (NumOps == 1) { 1024894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue Op = N->getOperand(0); 1025894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MakeLibCall(LC, N->getValueType(0), &Op, 1, isSigned, dl); 1026894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (NumOps == 2) { 1027894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) }; 1028894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MakeLibCall(LC, N->getValueType(0), Ops, 2, isSigned, dl); 1029894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1030894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SDValue, 8> Ops(NumOps); 1031894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0; i < NumOps; ++i) 1032894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ops[i] = N->getOperand(i); 1033894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1034894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MakeLibCall(LC, N->getValueType(0), &Ops[0], NumOps, isSigned, dl); 1035894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1036894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1037894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// MakeLibCall - Generate a libcall taking the given operands as arguments and 1038894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// returning a result of type RetVT. 1039894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSDValue DAGTypeLegalizer::MakeLibCall(RTLIB::Libcall LC, EVT RetVT, 1040894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SDValue *Ops, unsigned NumOps, 1041894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isSigned, DebugLoc dl) { 1042894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TargetLowering::ArgListTy Args; 1043894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Args.reserve(NumOps); 1044894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1045894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TargetLowering::ArgListEntry Entry; 1046894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0; i != NumOps; ++i) { 1047894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Entry.Node = Ops[i]; 1048894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Entry.Ty = Entry.Node.getValueType().getTypeForEVT(*DAG.getContext()); 1049894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Entry.isSExt = isSigned; 1050894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Entry.isZExt = !isSigned; 1051894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Args.push_back(Entry); 1052894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 1053894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC), 1054894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.getPointerTy()); 1055894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 105619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext()); 1057894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::pair<SDValue,SDValue> CallInfo = 1058894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.LowerCallTo(DAG.getEntryNode(), RetTy, isSigned, !isSigned, false, 1059894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman false, 0, TLI.getLibcallCallingConv(LC), false, 1060894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /*isReturnValueUsed=*/true, 1061894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Callee, Args, DAG, dl); 1062894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return CallInfo.first; 1063894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1064894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 106519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// ExpandChainLibCall - Expand a node into a call to a libcall. Similar to 106619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// ExpandLibCall except that the first operand is the in-chain. 106719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstd::pair<SDValue, SDValue> 106819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanDAGTypeLegalizer::ExpandChainLibCall(RTLIB::Libcall LC, 106919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SDNode *Node, 107019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isSigned) { 107119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SDValue InChain = Node->getOperand(0); 107219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 107319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetLowering::ArgListTy Args; 107419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetLowering::ArgListEntry Entry; 107519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) { 107619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EVT ArgVT = Node->getOperand(i).getValueType(); 107719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext()); 107819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Entry.Node = Node->getOperand(i); 107919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Entry.Ty = ArgTy; 108019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Entry.isSExt = isSigned; 108119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Entry.isZExt = !isSigned; 108219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Args.push_back(Entry); 108319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 108419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC), 108519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TLI.getPointerTy()); 108619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 108719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Splice the libcall in wherever FindInputOutputChains tells us to. 108819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext()); 108919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<SDValue, SDValue> CallInfo = 109019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TLI.LowerCallTo(InChain, RetTy, isSigned, !isSigned, false, false, 109119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 0, TLI.getLibcallCallingConv(LC), /*isTailCall=*/false, 109219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /*isReturnValueUsed=*/true, 109319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Callee, Args, DAG, Node->getDebugLoc()); 109419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 109519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return CallInfo; 109619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 109719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1098894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// PromoteTargetBoolean - Promote the given target boolean to a target boolean 1099894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// of the given type. A target boolean is an integer value, not necessarily of 1100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// type i1, the bits of which conform to getBooleanContents. 1101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, EVT VT) { 1102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DebugLoc dl = Bool.getDebugLoc(); 110319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ISD::NodeType ExtendCode = 110419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetLowering::getExtendForContent(TLI.getBooleanContents(VT.isVector())); 1105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return DAG.getNode(ExtendCode, dl, VT, Bool); 1106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// SplitInteger - Return the lower LoVT bits of Op in Lo and the upper HiVT 1109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// bits in Hi. 1110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::SplitInteger(SDValue Op, 1111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT LoVT, EVT HiVT, 1112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue &Lo, SDValue &Hi) { 1113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DebugLoc dl = Op.getDebugLoc(); 1114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() == 1115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Op.getValueType().getSizeInBits() && "Invalid integer splitting!"); 1116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op); 1117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op, 1118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DAG.getConstant(LoVT.getSizeInBits(), TLI.getPointerTy())); 1119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi); 1120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// SplitInteger - Return the lower and upper halves of Op's bits in a value 1123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// type half the size of Op's. 1124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid DAGTypeLegalizer::SplitInteger(SDValue Op, 1125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDValue &Lo, SDValue &Hi) { 1126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), 1127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Op.getValueType().getSizeInBits()/2); 1128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SplitInteger(Op, HalfVT, HalfVT, Lo, Hi); 1129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 1133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Entry Point 1134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 1135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 1137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// only uses types natively supported by the target. Returns "true" if it made 1138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// any changes. 1139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 1140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Note that this is an involved process that may invalidate pointers into 1141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the graph. 1142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool SelectionDAG::LegalizeTypes() { 1143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return DAGTypeLegalizer(*this).run(); 1144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1145