108d1275cb8137152dbfb13fab361b9b496725124Chris Lattner//===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===// 201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner// 301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner// The LLVM Compiler Infrastructure 401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner// 801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner//===----------------------------------------------------------------------===// 901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner// 1001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner// This file implements the SelectionDAG::LegalizeTypes method. It transforms 1108d1275cb8137152dbfb13fab361b9b496725124Chris Lattner// an arbitrary well-formed SelectionDAG to only consist of legal types. This 1208d1275cb8137152dbfb13fab361b9b496725124Chris Lattner// is common code shared among the LegalizeTypes*.cpp files. 1301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner// 1401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner//===----------------------------------------------------------------------===// 1501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 16dff67f5770ada2942dd8c815323ad2480bfdde44Chris Lattner#include "LegalizeTypes.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SetVector.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/CallingConv.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 20a658baba78e9cb0a9efbc5e4921c63f7b92a920cChris Lattner#include "llvm/Support/CommandLine.h" 217d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 224437ae213d5435390f0750213b53ec807c047f22Chris Lattner#include "llvm/Support/raw_ostream.h" 2301d029b82cb08367d81aa10cdc94d05360466649Chris Lattnerusing namespace llvm; 2401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 2547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sandsstatic cl::opt<bool> 2647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan SandsEnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden); 2747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 2847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands/// PerformExpensiveChecks - Do extensive, expensive, sanity checking. 2947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sandsvoid DAGTypeLegalizer::PerformExpensiveChecks() { 3047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // If a node is not processed, then none of its values should be mapped by any 3147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. 3247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 3347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // If a node is processed, then each value with an illegal type must be mapped 3447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // by exactly one of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. 3547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Values with a legal type may be mapped by ReplacedValues, but not by any of 3647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // the other maps. 3747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 3847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Note that these invariants may not hold momentarily when processing a node: 3947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // the node being processed may be put in a map before being marked Processed. 4047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 4147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Note that it is possible to have nodes marked NewNode in the DAG. This can 4247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // occur in two ways. Firstly, a node may be created during legalization but 4347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // never passed to the legalization core. This is usually due to the implicit 4447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // folding that occurs when using the DAG.getNode operators. Secondly, a new 4547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // node may be passed to the legalization core, but when analyzed may morph 4647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // into a different node, leaving the original node as a NewNode in the DAG. 4747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // A node may morph if one of its operands changes during analysis. Whether 4847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // it actually morphs or not depends on whether, after updating its operands, 4947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // it is equivalent to an existing node: if so, it morphs into that existing 5047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // node (CSE). An operand can change during analysis if the operand is a new 5147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // node that morphs, or it is a processed value that was mapped to some other 5247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // value (as recorded in ReplacedValues) in which case the operand is turned 5347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // into that other value. If a node morphs then the node it morphed into will 5447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // be used instead of it for legalization, however the original node continues 5547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // to live on in the DAG. 5647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // The conclusion is that though there may be nodes marked NewNode in the DAG, 5747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // all uses of such nodes are also marked NewNode: the result is a fungus of 5847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // NewNodes growing on top of the useful nodes, and perhaps using them, but 5947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // not used by them. 6047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 6147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // If a value is mapped by ReplacedValues, then it must have no uses, except 6247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // by nodes marked NewNode (see above). 6347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 6447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // The final node obtained by mapping by ReplacedValues is not marked NewNode. 6547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Note that ReplacedValues should be applied iteratively. 6647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 67c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // Note that the ReplacedValues map may also map deleted nodes (by iterating 68c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // over the DAG we never dereference deleted nodes). This means that it may 69c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // also map nodes marked NewNode if the deallocated memory was reallocated as 70c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // another node, and that new node was not seen by the LegalizeTypes machinery 71c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // (for example because it was created but not used). In general, we cannot 72c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // distinguish between new nodes and deleted nodes. 7347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands SmallVector<SDNode*, 16> NewNodes; 7447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 7547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands E = DAG.allnodes_end(); I != E; ++I) { 7647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Remember nodes marked NewNode - they are subject to extra checking below. 7747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (I->getNodeId() == NewNode) 7847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands NewNodes.push_back(I); 7947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 8047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands for (unsigned i = 0, e = I->getNumValues(); i != e; ++i) { 8147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands SDValue Res(I, i); 8247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands bool Failed = false; 8347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 8447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands unsigned Mapped = 0; 8547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (ReplacedValues.find(Res) != ReplacedValues.end()) { 8647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Mapped |= 1; 8747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Check that remapped values are only used by nodes marked NewNode. 8847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands for (SDNode::use_iterator UI = I->use_begin(), UE = I->use_end(); 8947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands UI != UE; ++UI) 90e7852d014432a06c783de3c350eb96e686f10f92Dan Gohman if (UI.getUse().getResNo() == i) 9147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(UI->getNodeId() == NewNode && 9247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands "Remapped value has non-trivial use!"); 9347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 9447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Check that the final result of applying ReplacedValues is not 9547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // marked NewNode. 9647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands SDValue NewVal = ReplacedValues[Res]; 9747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(NewVal); 9847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands while (I != ReplacedValues.end()) { 9947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands NewVal = I->second; 10047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands I = ReplacedValues.find(NewVal); 10147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 10247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(NewVal.getNode()->getNodeId() != NewNode && 10347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands "ReplacedValues maps to a new node!"); 10447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 10547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (PromotedIntegers.find(Res) != PromotedIntegers.end()) 10647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Mapped |= 2; 10747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (SoftenedFloats.find(Res) != SoftenedFloats.end()) 10847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Mapped |= 4; 10947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (ScalarizedVectors.find(Res) != ScalarizedVectors.end()) 11047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Mapped |= 8; 11147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (ExpandedIntegers.find(Res) != ExpandedIntegers.end()) 11247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Mapped |= 16; 11347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (ExpandedFloats.find(Res) != ExpandedFloats.end()) 11447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Mapped |= 32; 11547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (SplitVectors.find(Res) != SplitVectors.end()) 11647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Mapped |= 64; 11787c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang if (WidenedVectors.find(Res) != WidenedVectors.end()) 11887c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang Mapped |= 128; 11947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 12047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (I->getNodeId() != Processed) { 121c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // Since we allow ReplacedValues to map deleted nodes, it may map nodes 122c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // marked NewNode too, since a deleted node may have been reallocated as 123c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // another node that has not been seen by the LegalizeTypes machinery. 124c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands if ((I->getNodeId() == NewNode && Mapped > 1) || 125c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands (I->getNodeId() != NewNode && Mapped != 0)) { 126bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "Unprocessed value in a map!"; 12747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Failed = true; 12847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 1290394c4fb3d271b3a6736f167b812bbe445ddb5e9Duncan Sands } else if (isTypeLegal(Res.getValueType()) || IgnoreNodeResults(I)) { 1309771b91c2b4ce3baefdb9ba4ddfd9a9dd5077004Duncan Sands if (Mapped > 1) { 131bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "Value with legal type was transformed!"; 13247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Failed = true; 13347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 13447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } else { 13547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (Mapped == 0) { 136bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "Processed value not in any map!"; 13747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Failed = true; 13847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } else if (Mapped & (Mapped - 1)) { 139bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "Value in multiple maps!"; 14047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Failed = true; 14147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 14247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 14347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 14447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (Failed) { 14547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (Mapped & 1) 146bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << " ReplacedValues"; 14747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (Mapped & 2) 148bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << " PromotedIntegers"; 14947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (Mapped & 4) 150bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << " SoftenedFloats"; 15147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (Mapped & 8) 152bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << " ScalarizedVectors"; 15347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (Mapped & 16) 154bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << " ExpandedIntegers"; 15547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (Mapped & 32) 156bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << " ExpandedFloats"; 15747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (Mapped & 64) 158bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << " SplitVectors"; 15987c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang if (Mapped & 128) 160bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << " WidenedVectors"; 161bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "\n"; 162c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable(0); 16347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 16447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 16547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 16647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 16747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Checked that NewNodes are only used by other NewNodes. 16847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands for (unsigned i = 0, e = NewNodes.size(); i != e; ++i) { 16947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands SDNode *N = NewNodes[i]; 17047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 17147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands UI != UE; ++UI) 17247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(UI->getNodeId() == NewNode && "NewNode used by non-NewNode!"); 17347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 17447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands} 17547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 17601d029b82cb08367d81aa10cdc94d05360466649Chris Lattner/// run - This is the main entry point for the type legalizer. This does a 17725cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands/// top-down traversal of the dag, legalizing types as it goes. Returns "true" 17825cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands/// if it made any changes. 17925cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sandsbool DAGTypeLegalizer::run() { 18025cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands bool Changed = false; 18125cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands 18201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // Create a dummy node (which is not added to allnodes), that adds a reference 18301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // to the root node, preventing it from being deleted, and tracking any 18401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // changes of the root. 18501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner HandleSDNode Dummy(DAG.getRoot()); 18647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Dummy.setNodeId(Unanalyzed); 18701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 18801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // The root of the dag may dangle to deleted nodes until the type legalizer is 18901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // done. Set it to null to avoid confusion. 190475871a144eb604ddaf37503397ba0941442e5fbDan Gohman DAG.setRoot(SDValue()); 19169b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 192b99e740d71b68153284669c42ae9421d0f7e1cc2Duncan Sands // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess' 19347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // (and remembering them) if they are leaves and assigning 'Unanalyzed' if 19401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // non-leaves. 19501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 19601d029b82cb08367d81aa10cdc94d05360466649Chris Lattner E = DAG.allnodes_end(); I != E; ++I) { 19701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner if (I->getNumOperands() == 0) { 19801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner I->setNodeId(ReadyToProcess); 19901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner Worklist.push_back(I); 20001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } else { 20147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands I->setNodeId(Unanalyzed); 20201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 20301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 20469b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 20501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // Now that we have a set of nodes to process, handle them all. 20601d029b82cb08367d81aa10cdc94d05360466649Chris Lattner while (!Worklist.empty()) { 20747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands#ifndef XDEBUG 20847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (EnableExpensiveChecks) 20947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands#endif 21047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands PerformExpensiveChecks(); 21147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 21201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner SDNode *N = Worklist.back(); 21301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner Worklist.pop_back(); 21401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner assert(N->getNodeId() == ReadyToProcess && 21501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner "Node should be ready if on worklist!"); 21669b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 217d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands if (IgnoreNodeResults(N)) 218d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands goto ScanOperands; 219d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands 22001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // Scan the values produced by the node, checking to see if any result 22101d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // types are illegal. 222d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) { 223e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT ResultVT = N->getValueType(i); 224077f9b20d0e8659d00a09046a63e28edf0665ffeDuncan Sands switch (getTypeAction(ResultVT)) { 22596e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeLegal: 226077f9b20d0e8659d00a09046a63e28edf0665ffeDuncan Sands break; 22747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // The following calls must take care of *all* of the node's results, 22847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // not just the illegal result they were passed (this includes results 22947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // with a legal type). Results can be remapped using ReplaceValueWith, 23047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // or their promoted/expanded/etc values registered in PromotedIntegers, 23147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // ExpandedIntegers etc. 23296e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypePromoteInteger: 23369b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands PromoteIntegerResult(N, i); 23425cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 23501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner goto NodeDone; 23696e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeExpandInteger: 23769b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands ExpandIntegerResult(N, i); 23825cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 239077f9b20d0e8659d00a09046a63e28edf0665ffeDuncan Sands goto NodeDone; 24096e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeSoftenFloat: 2414fc4fd657d4266059dac3849133a3a351b03d99dDuncan Sands SoftenFloatResult(N, i); 24225cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 24369b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands goto NodeDone; 24496e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeExpandFloat: 24569b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands ExpandFloatResult(N, i); 24625cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 247d8742eeb2f7cabc45a1c3736a2780bf87ba684baDuncan Sands goto NodeDone; 24896e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeScalarizeVector: 249f4e4629ee8c218f892ad8ae3e182fe40bc160895Duncan Sands ScalarizeVectorResult(N, i); 25025cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 251077f9b20d0e8659d00a09046a63e28edf0665ffeDuncan Sands goto NodeDone; 25296e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeSplitVector: 253f4e4629ee8c218f892ad8ae3e182fe40bc160895Duncan Sands SplitVectorResult(N, i); 25425cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 25501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner goto NodeDone; 25696e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeWidenVector: 25787c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang WidenVectorResult(N, i); 25887c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang Changed = true; 25987c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang goto NodeDone; 26001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 261d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands } 262077f9b20d0e8659d00a09046a63e28edf0665ffeDuncan Sands 263d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan SandsScanOperands: 26401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // Scan the operand list for the node, handling any nodes with operands that 26501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // are illegal. 26601d029b82cb08367d81aa10cdc94d05360466649Chris Lattner { 26701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner unsigned NumOperands = N->getNumOperands(); 26847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands bool NeedsReanalyzing = false; 269d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands unsigned i; 27001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner for (i = 0; i != NumOperands; ++i) { 271ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif if (IgnoreNodeResults(N->getOperand(i).getNode())) 272d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands continue; 273d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands 274e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT OpVT = N->getOperand(i).getValueType(); 275077f9b20d0e8659d00a09046a63e28edf0665ffeDuncan Sands switch (getTypeAction(OpVT)) { 27696e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeLegal: 277077f9b20d0e8659d00a09046a63e28edf0665ffeDuncan Sands continue; 27847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // The following calls must either replace all of the node's results 27947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // using ReplaceValueWith, and return "false"; or update the node's 28047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // operands in place, and return "true". 28196e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypePromoteInteger: 28247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands NeedsReanalyzing = PromoteIntegerOperand(N, i); 28325cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 28469b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands break; 28596e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeExpandInteger: 28647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands NeedsReanalyzing = ExpandIntegerOperand(N, i); 28725cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 28801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner break; 28996e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeSoftenFloat: 29047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands NeedsReanalyzing = SoftenFloatOperand(N, i); 29125cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 292077f9b20d0e8659d00a09046a63e28edf0665ffeDuncan Sands break; 29396e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeExpandFloat: 29447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands NeedsReanalyzing = ExpandFloatOperand(N, i); 29525cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 296d8742eeb2f7cabc45a1c3736a2780bf87ba684baDuncan Sands break; 29796e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeScalarizeVector: 29847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands NeedsReanalyzing = ScalarizeVectorOperand(N, i); 29925cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 300077f9b20d0e8659d00a09046a63e28edf0665ffeDuncan Sands break; 30196e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeSplitVector: 30247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands NeedsReanalyzing = SplitVectorOperand(N, i); 30325cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands Changed = true; 30401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner break; 30596e0c5477c41b316263e894bbb5821c7cdeb25efNadav Rotem case TargetLowering::TypeWidenVector: 30687c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang NeedsReanalyzing = WidenVectorOperand(N, i); 30787c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang Changed = true; 30887c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang break; 30901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 310077f9b20d0e8659d00a09046a63e28edf0665ffeDuncan Sands break; 31101d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 31201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 31347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // The sub-method updated N in place. Check to see if any operands are new, 31447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // and if so, mark them. If the node needs revisiting, don't add all users 31547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // to the worklist etc. 31647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (NeedsReanalyzing) { 31747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); 31847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands N->setNodeId(NewNode); 31947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Recompute the NodeId and correct processed operands, adding the node to 32047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // the worklist if ready. 32147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands SDNode *M = AnalyzeNewNode(N); 32247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (M == N) 32347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // The node didn't morph - nothing special to do, it will be revisited. 32447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands continue; 32547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 32647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // The node morphed - this is equivalent to legalizing by replacing every 327c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // value of N with the corresponding value of M. So do that now. 32847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(N->getNumValues() == M->getNumValues() && 32947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands "Node morphing changed the number of results!"); 33047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 331c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands // Replacing the value takes care of remapping the new value. 332c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands ReplaceValueWith(SDValue(N, i), SDValue(M, i)); 3335bb11b89ddbc0f47eee9743b93df5aa872750d13Duncan Sands assert(N->getNodeId() == NewNode && "Unexpected node state!"); 3345bb11b89ddbc0f47eee9743b93df5aa872750d13Duncan Sands // The node continues to live on as part of the NewNode fungus that 3355bb11b89ddbc0f47eee9743b93df5aa872750d13Duncan Sands // grows on top of the useful nodes. Nothing more needs to be done 3365bb11b89ddbc0f47eee9743b93df5aa872750d13Duncan Sands // with it - move on to the next node. 3375bb11b89ddbc0f47eee9743b93df5aa872750d13Duncan Sands continue; 33847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 33969b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 3407a30bc4e7c034ecd0a3bcbfb385ac2a129e6583cDan Gohman if (i == NumOperands) { 341bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene DEBUG(dbgs() << "Legally typed node: "; N->dump(&DAG); dbgs() << "\n"); 34201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 3437a30bc4e7c034ecd0a3bcbfb385ac2a129e6583cDan Gohman } 34401d029b82cb08367d81aa10cdc94d05360466649Chris LattnerNodeDone: 34501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 34601d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // If we reach here, the node was processed, potentially creating new nodes. 34701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // Mark it as processed and add its users to the worklist as appropriate. 34847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); 34901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner N->setNodeId(Processed); 35069b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 35101d029b82cb08367d81aa10cdc94d05360466649Chris Lattner for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 35201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner UI != E; ++UI) { 3538968450305c28444edc3c272d8752a8db0c2f34aDan Gohman SDNode *User = *UI; 354b99e740d71b68153284669c42ae9421d0f7e1cc2Duncan Sands int NodeId = User->getNodeId(); 35569b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 35601d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // This node has two options: it can either be a new node or its Node ID 35701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // may be a count of the number of operands it has that are not ready. 358b99e740d71b68153284669c42ae9421d0f7e1cc2Duncan Sands if (NodeId > 0) { 359b99e740d71b68153284669c42ae9421d0f7e1cc2Duncan Sands User->setNodeId(NodeId-1); 36069b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 36101d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // If this was the last use it was waiting on, add it to the ready list. 362b99e740d71b68153284669c42ae9421d0f7e1cc2Duncan Sands if (NodeId-1 == ReadyToProcess) 36301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner Worklist.push_back(User); 36401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner continue; 36501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 36669b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 36747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // If this is an unreachable new node, then ignore it. If it ever becomes 36847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // reachable by being used by a newly created node then it will be handled 36947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // by AnalyzeNewNode. 37047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (NodeId == NewNode) 37147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands continue; 37247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 37301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // Otherwise, this node is new: this is the first operand of it that 374b99e740d71b68153284669c42ae9421d0f7e1cc2Duncan Sands // became ready. Its new NodeId is the number of operands it has minus 1 37501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // (as this node is now processed). 37647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(NodeId == Unanalyzed && "Unknown node ID!"); 37747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands User->setNodeId(User->getNumOperands() - 1); 37869b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 37901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // If the node only has a single operand, it is now ready. 38001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner if (User->getNumOperands() == 1) 38101d029b82cb08367d81aa10cdc94d05360466649Chris Lattner Worklist.push_back(User); 38201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 38301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 38469b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 38547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands#ifndef XDEBUG 38647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (EnableExpensiveChecks) 38747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands#endif 38847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands PerformExpensiveChecks(); 38901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 39047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // If the root changed (e.g. it was a dead load) update the root. 39147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands DAG.setRoot(Dummy.getValue()); 39201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 39301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // Remove dead nodes. This is important to do for cleanliness but also before 39447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // the checking loop below. Implicit folding by the DAG.getNode operators and 39547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // node morphing can cause unreachable nodes to be around with their flags set 39647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // to new. 39701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner DAG.RemoveDeadNodes(); 39801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 39901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // In a debug build, scan all the nodes to make sure we found them all. This 40001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // ensures that there are no cycles and that everything got processed. 40101d029b82cb08367d81aa10cdc94d05360466649Chris Lattner#ifndef NDEBUG 40201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 40301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner E = DAG.allnodes_end(); I != E; ++I) { 4041a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands bool Failed = false; 4051a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands 4061a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands // Check that all result types are legal. 407d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands if (!IgnoreNodeResults(I)) 408d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands for (unsigned i = 0, NumVals = I->getNumValues(); i < NumVals; ++i) 409d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands if (!isTypeLegal(I->getValueType(i))) { 410bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "Result type " << i << " illegal!\n"; 411d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands Failed = true; 412d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands } 4131a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands 4141a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands // Check that all operand types are legal. 4151a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands for (unsigned i = 0, NumOps = I->getNumOperands(); i < NumOps; ++i) 416ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif if (!IgnoreNodeResults(I->getOperand(i).getNode()) && 417d164ea2fb07ab3540121ffe1c59ad2cdc0a7a0a3Duncan Sands !isTypeLegal(I->getOperand(i).getValueType())) { 418bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "Operand type " << i << " illegal!\n"; 4191a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands Failed = true; 4201a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands } 4211a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands 4221a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands if (I->getNodeId() != Processed) { 4231a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands if (I->getNodeId() == NewNode) 424bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "New node not analyzed?\n"; 42547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands else if (I->getNodeId() == Unanalyzed) 426bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "Unanalyzed node not noticed?\n"; 4271a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands else if (I->getNodeId() > 0) 428bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "Operand not processed?\n"; 4291a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands else if (I->getNodeId() == ReadyToProcess) 430bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene dbgs() << "Not added to worklist?\n"; 4311a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands Failed = true; 4321a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands } 4331a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands 4341a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands if (Failed) { 435bb22223d5b4eb27d238bcc1b67b033975c43db7bDavid Greene I->dump(&DAG); dbgs() << "\n"; 436c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable(0); 4371a9c9df1db4ab3bf39f0395a7086576b4491d50bDuncan Sands } 43801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 43901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner#endif 44025cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands 44125cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands return Changed; 44201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner} 44301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 444212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands/// AnalyzeNewNode - The specified node is the root of a subtree of potentially 445212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands/// new nodes. Correct any processed operands (this may change the node) and 44623b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// calculate the NodeId. If the node itself changes to a processed node, it 44723b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// is not remapped - the caller needs to take care of this. 448ed63214fcbebcaf989dbc6a5bf7c3b6df67732f5Gabor Greif/// Returns the potentially changed node. 44923b10f5b64e594aa7c6b415805b563fed2a75874Duncan SandsSDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) { 45001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // If this was an existing node that is already done, we're done. 45147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed) 45223b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands return N; 45301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 4543a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands // Remove any stale map entries. 4553a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands ExpungeNode(N); 4563a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands 45701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // Okay, we know that this node is new. Recursively walk all of its operands 45801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // to see if they are new also. The depth of this walk is bounded by the size 45901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // of the new tree that was constructed (usually 2-3 nodes), so we don't worry 460cfc24007b13564c6720571a2e809cf84fda67737Chris Lattner // about revisiting of nodes. 46101d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // 46201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // As we walk the operands, keep track of the number of nodes that are 46301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // processed. If non-zero, this will become the new nodeid of this node. 46447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Operands may morph when they are analyzed. If so, the node will be 46547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // updated after all operands have been analyzed. Since this is rare, 46647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // the code tries to minimize overhead in the non-morphing case. 467212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands 468475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SmallVector<SDValue, 8> NewOps; 46901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner unsigned NumProcessed = 0; 47001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 471475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue OrigOp = N->getOperand(i); 472475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue Op = OrigOp; 473212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands 47447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands AnalyzeNewValue(Op); // Op may morph. 4751acb29c8ead8b7a6ac5dd63720711d397ac25ad9Duncan Sands 4761acb29c8ead8b7a6ac5dd63720711d397ac25ad9Duncan Sands if (Op.getNode()->getNodeId() == Processed) 47701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner ++NumProcessed; 478212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands 479212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands if (!NewOps.empty()) { 480212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands // Some previous operand changed. Add this one to the list. 481212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands NewOps.push_back(Op); 482212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands } else if (Op != OrigOp) { 483212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands // This is the first operand to change - add all operands so far. 484403a8cdda5e76ea689693de16474650b4b0df818Dan Gohman NewOps.append(N->op_begin(), N->op_begin() + i); 485212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands NewOps.push_back(Op); 486212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands } 48701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner } 488212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands 489212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands // Some operands changed - update the node. 4901acb29c8ead8b7a6ac5dd63720711d397ac25ad9Duncan Sands if (!NewOps.empty()) { 491027657db7cf60bcbf40403496d7e4a170f9ce1ecDan Gohman SDNode *M = DAG.UpdateNodeOperands(N, &NewOps[0], NewOps.size()); 49223b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands if (M != N) { 49347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // The node morphed into a different node. Normally for this to happen 49447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // the original node would have to be marked NewNode. However this can 49547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // in theory momentarily not be the case while ReplaceValueWith is doing 49647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // its stuff. Mark the original node NewNode to help sanity checking. 49747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands N->setNodeId(NewNode); 49847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (M->getNodeId() != NewNode && M->getNodeId() != Unanalyzed) 49923b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands // It morphed into a previously analyzed node - nothing more to do. 50023b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands return M; 50120f04e9fdd437712b323661e5041fd88431185b3Duncan Sands 5021acb29c8ead8b7a6ac5dd63720711d397ac25ad9Duncan Sands // It morphed into a different new node. Do the equivalent of passing 50347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // it to AnalyzeNewNode: expunge it and calculate the NodeId. No need 50447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // to remap the operands, since they are the same as the operands we 50547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // remapped above. 50623b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands N = M; 5071acb29c8ead8b7a6ac5dd63720711d397ac25ad9Duncan Sands ExpungeNode(N); 5081acb29c8ead8b7a6ac5dd63720711d397ac25ad9Duncan Sands } 5091acb29c8ead8b7a6ac5dd63720711d397ac25ad9Duncan Sands } 51001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 5111acb29c8ead8b7a6ac5dd63720711d397ac25ad9Duncan Sands // Calculate the NodeId. 51247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands N->setNodeId(N->getNumOperands() - NumProcessed); 5131acb29c8ead8b7a6ac5dd63720711d397ac25ad9Duncan Sands if (N->getNodeId() == ReadyToProcess) 5141acb29c8ead8b7a6ac5dd63720711d397ac25ad9Duncan Sands Worklist.push_back(N); 51523b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands 51623b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands return N; 51723b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands} 51823b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands 51923b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// AnalyzeNewValue - Call AnalyzeNewNode, updating the node in Val if needed. 52023b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// If the node changes to a processed node, then remap it. 52123b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sandsvoid DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) { 52247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands Val.setNode(AnalyzeNewNode(Val.getNode())); 52347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (Val.getNode()->getNodeId() == Processed) 52447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // We were passed a processed node, or it morphed into one - remap it. 52523b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(Val); 526ed63214fcbebcaf989dbc6a5bf7c3b6df67732f5Gabor Greif} 527ed63214fcbebcaf989dbc6a5bf7c3b6df67732f5Gabor Greif 52823b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// ExpungeNode - If N has a bogus mapping in ReplacedValues, eliminate it. 5293a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands/// This can occur when a node is deleted then reallocated as a new node - 53023b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// the mapping in ReplacedValues applies to the deleted node, not the new 5313a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands/// one. 53223b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// The only map that can have a deleted node as a source is ReplacedValues. 5333a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands/// Other maps can have deleted nodes as targets, but since their looked-up 53423b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// values are always immediately remapped using RemapValue, resulting in a 53523b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// not-deleted node, this is harmless as long as ReplacedValues/RemapValue 5363a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands/// always performs correct mappings. In order to keep the mapping correct, 5373a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands/// ExpungeNode should be called on any new nodes *before* adding them as 53823b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// either source or target to ReplacedValues (which typically means calling 5393a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands/// Expunge when a new node is first seen, since it may no longer be marked 54023b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands/// NewNode by the time it is added to ReplacedValues). 5413a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sandsvoid DAGTypeLegalizer::ExpungeNode(SDNode *N) { 5423a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands if (N->getNodeId() != NewNode) 5436f7e1cddf63f91af84996d59cdb5809088ac3fe3Duncan Sands return; 5446f7e1cddf63f91af84996d59cdb5809088ac3fe3Duncan Sands 54523b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands // If N is not remapped by ReplacedValues then there is nothing to do. 5463a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands unsigned i, e; 5473a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands for (i = 0, e = N->getNumValues(); i != e; ++i) 54823b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands if (ReplacedValues.find(SDValue(N, i)) != ReplacedValues.end()) 5493a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands break; 550edfcf598faab9ce294712551ecf67093acd1c66eDuncan Sands 5513a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands if (i == e) 5523a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands return; 553edfcf598faab9ce294712551ecf67093acd1c66eDuncan Sands 5543a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands // Remove N from all maps - this is expensive but rare. 555edfcf598faab9ce294712551ecf67093acd1c66eDuncan Sands 556475871a144eb604ddaf37503397ba0941442e5fbDan Gohman for (DenseMap<SDValue, SDValue>::iterator I = PromotedIntegers.begin(), 5573a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands E = PromotedIntegers.end(); I != E; ++I) { 558ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(I->first.getNode() != N); 55923b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(I->second); 5603a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands } 561edfcf598faab9ce294712551ecf67093acd1c66eDuncan Sands 562475871a144eb604ddaf37503397ba0941442e5fbDan Gohman for (DenseMap<SDValue, SDValue>::iterator I = SoftenedFloats.begin(), 5633a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands E = SoftenedFloats.end(); I != E; ++I) { 564ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(I->first.getNode() != N); 56523b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(I->second); 5663a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands } 567edfcf598faab9ce294712551ecf67093acd1c66eDuncan Sands 568475871a144eb604ddaf37503397ba0941442e5fbDan Gohman for (DenseMap<SDValue, SDValue>::iterator I = ScalarizedVectors.begin(), 5693a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands E = ScalarizedVectors.end(); I != E; ++I) { 570ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(I->first.getNode() != N); 57123b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(I->second); 5723a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands } 57369b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 5741bec3dd28a47b7e27e6f30de22a307521ce45b28Duncan Sands for (DenseMap<SDValue, SDValue>::iterator I = WidenedVectors.begin(), 5751bec3dd28a47b7e27e6f30de22a307521ce45b28Duncan Sands E = WidenedVectors.end(); I != E; ++I) { 5761bec3dd28a47b7e27e6f30de22a307521ce45b28Duncan Sands assert(I->first.getNode() != N); 5771bec3dd28a47b7e27e6f30de22a307521ce45b28Duncan Sands RemapValue(I->second); 5781bec3dd28a47b7e27e6f30de22a307521ce45b28Duncan Sands } 5791bec3dd28a47b7e27e6f30de22a307521ce45b28Duncan Sands 580475871a144eb604ddaf37503397ba0941442e5fbDan Gohman for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator 5813a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands I = ExpandedIntegers.begin(), E = ExpandedIntegers.end(); I != E; ++I){ 582ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(I->first.getNode() != N); 58323b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(I->second.first); 58423b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(I->second.second); 5853a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands } 586edfcf598faab9ce294712551ecf67093acd1c66eDuncan Sands 587475871a144eb604ddaf37503397ba0941442e5fbDan Gohman for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator 5883a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands I = ExpandedFloats.begin(), E = ExpandedFloats.end(); I != E; ++I) { 589ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(I->first.getNode() != N); 59023b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(I->second.first); 59123b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(I->second.second); 5923a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands } 5933a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands 594475871a144eb604ddaf37503397ba0941442e5fbDan Gohman for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator 5953a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands I = SplitVectors.begin(), E = SplitVectors.end(); I != E; ++I) { 596ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(I->first.getNode() != N); 59723b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(I->second.first); 59823b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(I->second.second); 599edfcf598faab9ce294712551ecf67093acd1c66eDuncan Sands } 6003a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands 60123b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands for (DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.begin(), 60223b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands E = ReplacedValues.end(); I != E; ++I) 60323b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(I->second); 6043a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands 6053a38e5e3c465c10fe5f859114f9077cb00cc17b9Duncan Sands for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 60623b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands ReplacedValues.erase(SDValue(N, i)); 607edfcf598faab9ce294712551ecf67093acd1c66eDuncan Sands} 608edfcf598faab9ce294712551ecf67093acd1c66eDuncan Sands 60947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands/// RemapValue - If the specified value was already legalized to another value, 61047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands/// replace it by that value. 61147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sandsvoid DAGTypeLegalizer::RemapValue(SDValue &N) { 61247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(N); 61347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (I != ReplacedValues.end()) { 61447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Use path compression to speed up future lookups if values get multiply 61547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // replaced with other values. 61647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands RemapValue(I->second); 61747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands N = I->second; 61847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(N.getNode()->getNodeId() != NewNode && "Mapped to new node!"); 61947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 62047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands} 62147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 62247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sandsnamespace { 62347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands /// NodeUpdateListener - This class is a DAGUpdateListener that listens for 62447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands /// updates to nodes and recomputes their ready state. 6256726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class NodeUpdateListener : public SelectionDAG::DAGUpdateListener { 62647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands DAGTypeLegalizer &DTL; 6272ecf88d1751c847b87a7119bf34fff85a3d272e2Duncan Sands SmallSetVector<SDNode*, 16> &NodesToAnalyze; 62847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands public: 62947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands explicit NodeUpdateListener(DAGTypeLegalizer &dtl, 6302ecf88d1751c847b87a7119bf34fff85a3d272e2Duncan Sands SmallSetVector<SDNode*, 16> &nta) 631bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen : SelectionDAG::DAGUpdateListener(dtl.getDAG()), 632bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen DTL(dtl), NodesToAnalyze(nta) {} 63347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 63447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands virtual void NodeDeleted(SDNode *N, SDNode *E) { 63547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 63647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands N->getNodeId() != DAGTypeLegalizer::Processed && 63747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands "Invalid node ID for RAUW deletion!"); 63847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // It is possible, though rare, for the deleted node N to occur as a 63947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // target in a map, so note the replacement N -> E in ReplacedValues. 64047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(E && "Node not replaced?"); 64147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands DTL.NoteDeletion(N, E); 64247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 64347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // In theory the deleted node could also have been scheduled for analysis. 64495c5f05641e0afdfcbeb430090e1cd0356dddfbcDuncan Sands // So remove it from the set of nodes which will be analyzed. 6452ecf88d1751c847b87a7119bf34fff85a3d272e2Duncan Sands NodesToAnalyze.remove(N); 64647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 64747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // In general nothing needs to be done for E, since it didn't change but 64847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // only gained new uses. However N -> E was just added to ReplacedValues, 64947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // and the result of a ReplacedValues mapping is not allowed to be marked 65047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // NewNode. So if E is marked NewNode, then it needs to be analyzed. 65147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands if (E->getNodeId() == DAGTypeLegalizer::NewNode) 6522ecf88d1751c847b87a7119bf34fff85a3d272e2Duncan Sands NodesToAnalyze.insert(E); 65347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 65447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 65547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands virtual void NodeUpdated(SDNode *N) { 65647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Node updates can mean pretty much anything. It is possible that an 65747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // operand was set to something already processed (f.e.) in which case 65847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // this node could become ready. Recompute its flags. 65947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 66047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands N->getNodeId() != DAGTypeLegalizer::Processed && 66147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands "Invalid node ID for RAUW deletion!"); 66295c5f05641e0afdfcbeb430090e1cd0356dddfbcDuncan Sands N->setNodeId(DAGTypeLegalizer::NewNode); 6632ecf88d1751c847b87a7119bf34fff85a3d272e2Duncan Sands NodesToAnalyze.insert(N); 66447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 66547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands }; 66647d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands} 66747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 66847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 669c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands/// ReplaceValueWith - The specified value was legalized to the specified other 670c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands/// value. Update the DAG and NodeIds replacing any uses of From to use To 671c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands/// instead. 672c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sandsvoid DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) { 67347d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands assert(From.getNode() != To.getNode() && "Potential legalization loop!"); 67447d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 67547d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // If expansion produced new nodes, make sure they are properly marked. 676c088ae8b84bfcdefb57efafb022430312bddf638Duncan Sands ExpungeNode(From.getNode()); 67747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands AnalyzeNewValue(To); // Expunges To. 67847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 67947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // Anything that used the old node should now use the new one. Note that this 68047d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands // can potentially cause recursive merging. 6812ecf88d1751c847b87a7119bf34fff85a3d272e2Duncan Sands SmallSetVector<SDNode*, 16> NodesToAnalyze; 6822ecf88d1751c847b87a7119bf34fff85a3d272e2Duncan Sands NodeUpdateListener NUL(*this, NodesToAnalyze); 683f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang do { 684bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen DAG.ReplaceAllUsesOfValueWith(From, To); 685f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang 686f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // The old node may still be present in a map like ExpandedIntegers or 687f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // PromotedIntegers. Inform maps about the replacement. 688f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang ReplacedValues[From] = To; 689f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang 690f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // Process the list of nodes that need to be reanalyzed. 691f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang while (!NodesToAnalyze.empty()) { 692f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang SDNode *N = NodesToAnalyze.back(); 693f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang NodesToAnalyze.pop_back(); 694f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang if (N->getNodeId() != DAGTypeLegalizer::NewNode) 695f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // The node was analyzed while reanalyzing an earlier node - it is safe 696f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // to skip. Note that this is not a morphing node - otherwise it would 697f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // still be marked NewNode. 698f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang continue; 69947d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 700f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // Analyze the node's operands and recalculate the node ID. 701f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang SDNode *M = AnalyzeNewNode(N); 702f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang if (M != N) { 703f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // The node morphed into a different node. Make everyone use the new 704f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // node instead. 705f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!"); 706f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang assert(N->getNumValues() == M->getNumValues() && 707f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang "Node morphing changed the number of results!"); 708f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 709f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang SDValue OldVal(N, i); 710f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang SDValue NewVal(M, i); 711f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang if (M->getNodeId() == Processed) 712f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang RemapValue(NewVal); 713bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal); 714d9aa80038f630d72883ebe5b524e372a44e6695cDuncan Sands // OldVal may be a target of the ReplacedValues map which was marked 715d9aa80038f630d72883ebe5b524e372a44e6695cDuncan Sands // NewNode to force reanalysis because it was updated. Ensure that 716d9aa80038f630d72883ebe5b524e372a44e6695cDuncan Sands // anything that ReplacedValues mapped to OldVal will now be mapped 717d9aa80038f630d72883ebe5b524e372a44e6695cDuncan Sands // all the way to NewVal. 718d9aa80038f630d72883ebe5b524e372a44e6695cDuncan Sands ReplacedValues[OldVal] = NewVal; 719f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang } 720f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // The original node continues to exist in the DAG, marked NewNode. 72147d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 72247d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands } 723f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // When recursively update nodes with new nodes, it is possible to have 724f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // new uses of From due to CSE. If this happens, replace the new uses of 725f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang // From with To. 726f62546ab046d4bc2f055921f25f127fbb942b806Mon P Wang } while (!From.use_empty()); 72747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands} 72847d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands 729475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanvoid DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) { 73022d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng assert(Result.getValueType() == 73122d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 732f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands "Invalid type for promoted integer"); 73323b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands AnalyzeNewValue(Result); 73401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 735475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue &OpEntry = PromotedIntegers[Op]; 736ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(OpEntry.getNode() == 0 && "Node is already promoted!"); 73701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner OpEntry = Result; 73801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner} 73901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 740475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanvoid DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) { 74122d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng assert(Result.getValueType() == 74222d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 743f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands "Invalid type for softened float"); 74423b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands AnalyzeNewValue(Result); 745d8742eeb2f7cabc45a1c3736a2780bf87ba684baDuncan Sands 746475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue &OpEntry = SoftenedFloats[Op]; 747ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(OpEntry.getNode() == 0 && "Node is already converted to integer!"); 748d8742eeb2f7cabc45a1c3736a2780bf87ba684baDuncan Sands OpEntry = Result; 749d8742eeb2f7cabc45a1c3736a2780bf87ba684baDuncan Sands} 750d8742eeb2f7cabc45a1c3736a2780bf87ba684baDuncan Sands 751475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanvoid DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) { 7528b7c3d0ee42938a9e6ca37239cc327bd9f4c0cd0Nadav Rotem // Note that in some cases vector operation operands may be greater than 7538b7c3d0ee42938a9e6ca37239cc327bd9f4c0cd0Nadav Rotem // the vector element type. For example BUILD_VECTOR of type <1 x i1> with 7548b7c3d0ee42938a9e6ca37239cc327bd9f4c0cd0Nadav Rotem // a constant i8 operand. 7558b7c3d0ee42938a9e6ca37239cc327bd9f4c0cd0Nadav Rotem assert(Result.getValueType().getSizeInBits() >= 7568b7c3d0ee42938a9e6ca37239cc327bd9f4c0cd0Nadav Rotem Op.getValueType().getVectorElementType().getSizeInBits() && 757f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands "Invalid type for scalarized vector"); 75823b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands AnalyzeNewValue(Result); 759212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands 760475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue &OpEntry = ScalarizedVectors[Op]; 761ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(OpEntry.getNode() == 0 && "Node is already scalarized!"); 76213c207b5c84cbac78147fa4472a4e14232cb6febChris Lattner OpEntry = Result; 76313c207b5c84cbac78147fa4472a4e14232cb6febChris Lattner} 76413c207b5c84cbac78147fa4472a4e14232cb6febChris Lattner 765475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanvoid DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo, 766475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue &Hi) { 767475871a144eb604ddaf37503397ba0941442e5fbDan Gohman std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op]; 76823b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(Entry.first); 76923b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(Entry.second); 770ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(Entry.first.getNode() && "Operand isn't expanded"); 77169b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands Lo = Entry.first; 77269b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands Hi = Entry.second; 77369b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands} 77469b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 775475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanvoid DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo, 776475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue Hi) { 77722d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng assert(Lo.getValueType() == 77822d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 779f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands Hi.getValueType() == Lo.getValueType() && 780f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands "Invalid type for expanded integer"); 78169b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 78223b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands AnalyzeNewValue(Lo); 78323b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands AnalyzeNewValue(Hi); 78469b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 78569b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands // Remember that this is the result of the node. 786475871a144eb604ddaf37503397ba0941442e5fbDan Gohman std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op]; 787ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(Entry.first.getNode() == 0 && "Node already expanded"); 78869b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands Entry.first = Lo; 78969b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands Entry.second = Hi; 79069b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands} 79169b01e92a29ce6d7e435171aeea3fbc987b81586Duncan Sands 792475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanvoid DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo, 793475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue &Hi) { 794475871a144eb604ddaf37503397ba0941442e5fbDan Gohman std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op]; 79523b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(Entry.first); 79623b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(Entry.second); 797ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(Entry.first.getNode() && "Operand isn't expanded"); 79801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner Lo = Entry.first; 79901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner Hi = Entry.second; 80001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner} 80101d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 802475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanvoid DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo, 803475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue Hi) { 80422d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng assert(Lo.getValueType() == 80522d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 806f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands Hi.getValueType() == Lo.getValueType() && 807f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands "Invalid type for expanded float"); 808212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 80923b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands AnalyzeNewValue(Lo); 81023b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands AnalyzeNewValue(Hi); 811212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands 81201d029b82cb08367d81aa10cdc94d05360466649Chris Lattner // Remember that this is the result of the node. 813475871a144eb604ddaf37503397ba0941442e5fbDan Gohman std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op]; 814ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(Entry.first.getNode() == 0 && "Node already expanded"); 81501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner Entry.first = Lo; 81601d029b82cb08367d81aa10cdc94d05360466649Chris Lattner Entry.second = Hi; 81701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner} 81801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 819475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanvoid DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo, 820475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue &Hi) { 821475871a144eb604ddaf37503397ba0941442e5fbDan Gohman std::pair<SDValue, SDValue> &Entry = SplitVectors[Op]; 82223b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(Entry.first); 82323b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands RemapValue(Entry.second); 824ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(Entry.first.getNode() && "Operand isn't split"); 825e4af7b5a573593dcf2a37cd4590bf76d1322d6daChris Lattner Lo = Entry.first; 826e4af7b5a573593dcf2a37cd4590bf76d1322d6daChris Lattner Hi = Entry.second; 827e4af7b5a573593dcf2a37cd4590bf76d1322d6daChris Lattner} 828e4af7b5a573593dcf2a37cd4590bf76d1322d6daChris Lattner 829475871a144eb604ddaf37503397ba0941442e5fbDan Gohmanvoid DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo, 830475871a144eb604ddaf37503397ba0941442e5fbDan Gohman SDValue Hi) { 831f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands assert(Lo.getValueType().getVectorElementType() == 832f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands Op.getValueType().getVectorElementType() && 833f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands 2*Lo.getValueType().getVectorNumElements() == 834f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands Op.getValueType().getVectorNumElements() && 835f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands Hi.getValueType() == Lo.getValueType() && 836f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands "Invalid type for split vector"); 837212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 83823b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands AnalyzeNewValue(Lo); 83923b10f5b64e594aa7c6b415805b563fed2a75874Duncan Sands AnalyzeNewValue(Hi); 840212a11c417e272cc8fd12e66cfe5110c47559e17Duncan Sands 841e4af7b5a573593dcf2a37cd4590bf76d1322d6daChris Lattner // Remember that this is the result of the node. 842475871a144eb604ddaf37503397ba0941442e5fbDan Gohman std::pair<SDValue, SDValue> &Entry = SplitVectors[Op]; 843ba36cb5242eb02b12b277f82b9efe497f7da4d7fGabor Greif assert(Entry.first.getNode() == 0 && "Node already split"); 844e4af7b5a573593dcf2a37cd4590bf76d1322d6daChris Lattner Entry.first = Lo; 845e4af7b5a573593dcf2a37cd4590bf76d1322d6daChris Lattner Entry.second = Hi; 846e4af7b5a573593dcf2a37cd4590bf76d1322d6daChris Lattner} 847e4af7b5a573593dcf2a37cd4590bf76d1322d6daChris Lattner 84887c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wangvoid DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) { 84922d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng assert(Result.getValueType() == 85022d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 851f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands "Invalid type for widened vector"); 85287c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang AnalyzeNewValue(Result); 85387c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang 85487c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang SDValue &OpEntry = WidenedVectors[Op]; 8551bec3dd28a47b7e27e6f30de22a307521ce45b28Duncan Sands assert(OpEntry.getNode() == 0 && "Node already widened!"); 85687c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang OpEntry = Result; 85787c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang} 85887c8a8f304d1ee72829086ce2c41a8fa3813ba6aMon P Wang 859e4af7b5a573593dcf2a37cd4590bf76d1322d6daChris Lattner 86078cd649ad326f79a1f8424ca2b63cea3239a9a52Duncan Sands//===----------------------------------------------------------------------===// 86178cd649ad326f79a1f8424ca2b63cea3239a9a52Duncan Sands// Utilities. 86278cd649ad326f79a1f8424ca2b63cea3239a9a52Duncan Sands//===----------------------------------------------------------------------===// 86378cd649ad326f79a1f8424ca2b63cea3239a9a52Duncan Sands 864d8742eeb2f7cabc45a1c3736a2780bf87ba684baDuncan Sands/// BitConvertToInteger - Convert to an integer of the same size. 865475871a144eb604ddaf37503397ba0941442e5fbDan GohmanSDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) { 86683ec4b6711980242ef3c55a4fa36b2d7a39c1bfbDuncan Sands unsigned BitWidth = Op.getValueType().getSizeInBits(); 867bf17cfa3f904e488e898ac2e3af706fd1a892f08Wesley Peck return DAG.getNode(ISD::BITCAST, Op.getDebugLoc(), 86823b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson EVT::getIntegerVT(*DAG.getContext(), BitWidth), Op); 869d8742eeb2f7cabc45a1c3736a2780bf87ba684baDuncan Sands} 870d8742eeb2f7cabc45a1c3736a2780bf87ba684baDuncan Sands 871004e27cc1bba070f013589cc8e434b03589c3c22Duncan Sands/// BitConvertVectorToIntegerVector - Convert to a vector of integers of the 872004e27cc1bba070f013589cc8e434b03589c3c22Duncan Sands/// same size. 873004e27cc1bba070f013589cc8e434b03589c3c22Duncan SandsSDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(SDValue Op) { 874004e27cc1bba070f013589cc8e434b03589c3c22Duncan Sands assert(Op.getValueType().isVector() && "Only applies to vectors!"); 875004e27cc1bba070f013589cc8e434b03589c3c22Duncan Sands unsigned EltWidth = Op.getValueType().getVectorElementType().getSizeInBits(); 87623b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson EVT EltNVT = EVT::getIntegerVT(*DAG.getContext(), EltWidth); 877004e27cc1bba070f013589cc8e434b03589c3c22Duncan Sands unsigned NumElts = Op.getValueType().getVectorNumElements(); 878bf17cfa3f904e488e898ac2e3af706fd1a892f08Wesley Peck return DAG.getNode(ISD::BITCAST, Op.getDebugLoc(), 87923b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson EVT::getVectorVT(*DAG.getContext(), EltNVT, NumElts), Op); 880004e27cc1bba070f013589cc8e434b03589c3c22Duncan Sands} 881004e27cc1bba070f013589cc8e434b03589c3c22Duncan Sands 882475871a144eb604ddaf37503397ba0941442e5fbDan GohmanSDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op, 883e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT DestVT) { 8846f38cb61a94b3abab70f0ee463bdcf55d86d334eDale Johannesen DebugLoc dl = Op.getDebugLoc(); 885c5ffb45934a5f6c19b6279a42622f1b4d9e7ec88Duncan Sands // Create the stack frame object. Make sure it is aligned for both 886c5ffb45934a5f6c19b6279a42622f1b4d9e7ec88Duncan Sands // the source and destination types. 88747d9dcc584cdb7fd645ca1d5c2a0ce363570aeb7Duncan Sands SDValue StackPtr = DAG.CreateStackTemporary(Op.getValueType(), DestVT); 888c224a53d7aa077d36f1495b242d7c8e4f324754dChris Lattner // Emit a store to the stack slot. 889ecf42c4720aba6ee315d0166045c54187ac2de4dChris Lattner SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, 890ecf42c4720aba6ee315d0166045c54187ac2de4dChris Lattner MachinePointerInfo(), false, false, 0); 891c224a53d7aa077d36f1495b242d7c8e4f324754dChris Lattner // Result is a load from the stack slot. 892ecf42c4720aba6ee315d0166045c54187ac2de4dChris Lattner return DAG.getLoad(DestVT, dl, Store, StackPtr, MachinePointerInfo(), 893d752e0f7e64585839cb3a458ef52456eaebbea3cPete Cooper false, false, false, 0); 894c224a53d7aa077d36f1495b242d7c8e4f324754dChris Lattner} 895c224a53d7aa077d36f1495b242d7c8e4f324754dChris Lattner 896f43071beddb7ed5b2fd7d2f06c4130460616a13dDuncan Sands/// CustomLowerNode - Replace the node's results with custom code provided 8971607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands/// by the target and return "true", or do nothing and return "false". 8989fbc7e2e7a765298fb4326885b407e0962f7ab62Duncan Sands/// The last parameter is FALSE if we are dealing with a node with legal 899b169426272b85ce28a9a56d13154e61b158fc47aSanjiv Gupta/// result types and illegal operand. The second parameter denotes the type of 900b169426272b85ce28a9a56d13154e61b158fc47aSanjiv Gupta/// illegal OperandNo in that case. 901bb326bbe88d0b243d5d9d224308eb0c028d4d4afSanjiv Gupta/// The last parameter being TRUE means we are dealing with a 902b169426272b85ce28a9a56d13154e61b158fc47aSanjiv Gupta/// node with illegal result types. The second parameter denotes the type of 903b169426272b85ce28a9a56d13154e61b158fc47aSanjiv Gupta/// illegal ResNo in that case. 904e50ed30282bb5b4a9ed952580523f2dda16215acOwen Andersonbool DAGTypeLegalizer::CustomLowerNode(SDNode *N, EVT VT, bool LegalizeResult) { 9051607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands // See if the target wants to custom lower this node. 9069fbc7e2e7a765298fb4326885b407e0962f7ab62Duncan Sands if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) 9071607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands return false; 9081607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands 9091607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands SmallVector<SDValue, 8> Results; 910bb326bbe88d0b243d5d9d224308eb0c028d4d4afSanjiv Gupta if (LegalizeResult) 911bb326bbe88d0b243d5d9d224308eb0c028d4d4afSanjiv Gupta TLI.ReplaceNodeResults(N, Results, DAG); 912bb326bbe88d0b243d5d9d224308eb0c028d4d4afSanjiv Gupta else 9139fbc7e2e7a765298fb4326885b407e0962f7ab62Duncan Sands TLI.LowerOperationWrapper(N, Results, DAG); 914bb326bbe88d0b243d5d9d224308eb0c028d4d4afSanjiv Gupta 9151607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands if (Results.empty()) 9161607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands // The target didn't want to custom lower it after all. 9171607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands return false; 9181607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands 9191607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands // Make everything that once used N's values now use those in Results instead. 9201607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands assert(Results.size() == N->getNumValues() && 9211607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands "Custom lowering returned the wrong number of results!"); 9221607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands for (unsigned i = 0, e = Results.size(); i != e; ++i) 9231607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands ReplaceValueWith(SDValue(N, i), Results[i]); 924cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang return true; 925cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang} 926cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang 927cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang 928cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang/// CustomWidenLowerNode - Widen the node's results with custom code provided 929cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang/// by the target and return "true", or do nothing and return "false". 930cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wangbool DAGTypeLegalizer::CustomWidenLowerNode(SDNode *N, EVT VT) { 931cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang // See if the target wants to custom lower this node. 932cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) 933cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang return false; 934cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang 935cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang SmallVector<SDValue, 8> Results; 936cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang TLI.ReplaceNodeResults(N, Results, DAG); 937cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang 938cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang if (Results.empty()) 939cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang // The target didn't want to custom widen lower its result after all. 940cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang return false; 941cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang 942cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang // Update the widening map. 943cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang assert(Results.size() == N->getNumValues() && 944cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang "Custom lowering returned the wrong number of results!"); 945cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang for (unsigned i = 0, e = Results.size(); i != e; ++i) 946cd6e725f21852e2f8cdf5fd0e65eb42c224776f8Mon P Wang SetWidenedVector(SDValue(N, i), Results[i]); 9471607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands return true; 9481607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands} 9491607f05cb7d77d01ce521a30232faa389dbed4e2Duncan Sands 9504c19e12d28749c717d3b384962c9ec92796af1c9Duncan SandsSDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(SDNode *N, unsigned ResNo) { 9514c19e12d28749c717d3b384962c9ec92796af1c9Duncan Sands for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 9524c19e12d28749c717d3b384962c9ec92796af1c9Duncan Sands if (i != ResNo) 9534c19e12d28749c717d3b384962c9ec92796af1c9Duncan Sands ReplaceValueWith(SDValue(N, i), SDValue(N->getOperand(i))); 95404b2c5042727b091ad425110d952491a40c88ee3Duncan Sands return SDValue(N->getOperand(ResNo)); 95562bb16cfd10dd271eab6c31d982bca4d79138602Eli Friedman} 95662bb16cfd10dd271eab6c31d982bca4d79138602Eli Friedman 957b6e223a9e806921183da972253c49082a2e07944Duncan Sands/// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type 958b6e223a9e806921183da972253c49082a2e07944Duncan Sands/// which is split into two not necessarily identical pieces. 959e50ed30282bb5b4a9ed952580523f2dda16215acOwen Andersonvoid DAGTypeLegalizer::GetSplitDestVTs(EVT InVT, EVT &LoVT, EVT &HiVT) { 960f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands // Currently all types are split in half. 961b6e223a9e806921183da972253c49082a2e07944Duncan Sands if (!InVT.isVector()) { 96223b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson LoVT = HiVT = TLI.getTypeToTransformTo(*DAG.getContext(), InVT); 963b6e223a9e806921183da972253c49082a2e07944Duncan Sands } else { 964b6e223a9e806921183da972253c49082a2e07944Duncan Sands unsigned NumElements = InVT.getVectorNumElements(); 965f2d754bb382cba0bad2774144ddac84be5354d16Duncan Sands assert(!(NumElements & 1) && "Splitting vector, but not in half!"); 96622d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng LoVT = HiVT = EVT::getVectorVT(*DAG.getContext(), 96722d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng InVT.getVectorElementType(), NumElements/2); 968b6e223a9e806921183da972253c49082a2e07944Duncan Sands } 969b6e223a9e806921183da972253c49082a2e07944Duncan Sands} 970b6e223a9e806921183da972253c49082a2e07944Duncan Sands 9712bee0afb7d023e029975abf7d3157759fa797d37Dan Gohman/// GetPairElements - Use ISD::EXTRACT_ELEMENT nodes to extract the low and 9722bee0afb7d023e029975abf7d3157759fa797d37Dan Gohman/// high parts of the given value. 9732bee0afb7d023e029975abf7d3157759fa797d37Dan Gohmanvoid DAGTypeLegalizer::GetPairElements(SDValue Pair, 9742bee0afb7d023e029975abf7d3157759fa797d37Dan Gohman SDValue &Lo, SDValue &Hi) { 9752bee0afb7d023e029975abf7d3157759fa797d37Dan Gohman DebugLoc dl = Pair.getDebugLoc(); 97623b9b19b1a5a00faa9fce0788155c7dbfd00bfb1Owen Anderson EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.getValueType()); 9772bee0afb7d023e029975abf7d3157759fa797d37Dan Gohman Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair, 9782bee0afb7d023e029975abf7d3157759fa797d37Dan Gohman DAG.getIntPtrConstant(0)); 9792bee0afb7d023e029975abf7d3157759fa797d37Dan Gohman Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair, 9802bee0afb7d023e029975abf7d3157759fa797d37Dan Gohman DAG.getIntPtrConstant(1)); 9812bee0afb7d023e029975abf7d3157759fa797d37Dan Gohman} 9822bee0afb7d023e029975abf7d3157759fa797d37Dan Gohman 983e50ed30282bb5b4a9ed952580523f2dda16215acOwen AndersonSDValue DAGTypeLegalizer::GetVectorElementPointer(SDValue VecPtr, EVT EltVT, 984b6e223a9e806921183da972253c49082a2e07944Duncan Sands SDValue Index) { 9856f38cb61a94b3abab70f0ee463bdcf55d86d334eDale Johannesen DebugLoc dl = Index.getDebugLoc(); 986b6e223a9e806921183da972253c49082a2e07944Duncan Sands // Make sure the index type is big enough to compute in. 987b6e223a9e806921183da972253c49082a2e07944Duncan Sands if (Index.getValueType().bitsGT(TLI.getPointerTy())) 9889c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen Index = DAG.getNode(ISD::TRUNCATE, dl, TLI.getPointerTy(), Index); 989b6e223a9e806921183da972253c49082a2e07944Duncan Sands else 9909c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen Index = DAG.getNode(ISD::ZERO_EXTEND, dl, TLI.getPointerTy(), Index); 991b6e223a9e806921183da972253c49082a2e07944Duncan Sands 992b6e223a9e806921183da972253c49082a2e07944Duncan Sands // Calculate the element offset and add it to the pointer. 993aa9d854b334cab2f29ca6d95413a0946b8a38429Dan Gohman unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size. 994b6e223a9e806921183da972253c49082a2e07944Duncan Sands 9959c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen Index = DAG.getNode(ISD::MUL, dl, Index.getValueType(), Index, 996b6e223a9e806921183da972253c49082a2e07944Duncan Sands DAG.getConstant(EltSize, Index.getValueType())); 9979c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen return DAG.getNode(ISD::ADD, dl, Index.getValueType(), Index, VecPtr); 998b6e223a9e806921183da972253c49082a2e07944Duncan Sands} 999b6e223a9e806921183da972253c49082a2e07944Duncan Sands 1000ac7613a3263caa80d735f3fbf2b9f7b81deabc08Duncan Sands/// JoinIntegers - Build an integer with low bits Lo and high bits Hi. 1001475871a144eb604ddaf37503397ba0941442e5fbDan GohmanSDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) { 10029c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen // Arbitrarily use dlHi for result DebugLoc 10036f38cb61a94b3abab70f0ee463bdcf55d86d334eDale Johannesen DebugLoc dlHi = Hi.getDebugLoc(); 10046f38cb61a94b3abab70f0ee463bdcf55d86d334eDale Johannesen DebugLoc dlLo = Lo.getDebugLoc(); 1005e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT LVT = Lo.getValueType(); 1006e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT HVT = Hi.getValueType(); 100722d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng EVT NVT = EVT::getIntegerVT(*DAG.getContext(), 100822d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng LVT.getSizeInBits() + HVT.getSizeInBits()); 1009ac7613a3263caa80d735f3fbf2b9f7b81deabc08Duncan Sands 10109c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo); 10119c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi); 10129c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi, 101392abc62399881ba9c525be80362c134ad836e2d9Duncan Sands DAG.getConstant(LVT.getSizeInBits(), TLI.getPointerTy())); 10149c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi); 1015ac7613a3263caa80d735f3fbf2b9f7b81deabc08Duncan Sands} 1016ac7613a3263caa80d735f3fbf2b9f7b81deabc08Duncan Sands 1017b6e223a9e806921183da972253c49082a2e07944Duncan Sands/// LibCallify - Convert the node into a libcall with the same prototype. 1018b6e223a9e806921183da972253c49082a2e07944Duncan SandsSDValue DAGTypeLegalizer::LibCallify(RTLIB::Libcall LC, SDNode *N, 1019b6e223a9e806921183da972253c49082a2e07944Duncan Sands bool isSigned) { 1020b6e223a9e806921183da972253c49082a2e07944Duncan Sands unsigned NumOps = N->getNumOperands(); 1021c8fc99d66a03dc603f49d653937ad1d94e833006Dale Johannesen DebugLoc dl = N->getDebugLoc(); 1022b6e223a9e806921183da972253c49082a2e07944Duncan Sands if (NumOps == 0) { 10232c8cf4b404e549482f593f62f9e27e0bab4a8b3fTim Northover return TLI.makeLibCall(DAG, LC, N->getValueType(0), 0, 0, isSigned, dl); 1024b6e223a9e806921183da972253c49082a2e07944Duncan Sands } else if (NumOps == 1) { 1025b6e223a9e806921183da972253c49082a2e07944Duncan Sands SDValue Op = N->getOperand(0); 10262c8cf4b404e549482f593f62f9e27e0bab4a8b3fTim Northover return TLI.makeLibCall(DAG, LC, N->getValueType(0), &Op, 1, isSigned, dl); 1027b6e223a9e806921183da972253c49082a2e07944Duncan Sands } else if (NumOps == 2) { 1028b6e223a9e806921183da972253c49082a2e07944Duncan Sands SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) }; 10292c8cf4b404e549482f593f62f9e27e0bab4a8b3fTim Northover return TLI.makeLibCall(DAG, LC, N->getValueType(0), Ops, 2, isSigned, dl); 1030b6e223a9e806921183da972253c49082a2e07944Duncan Sands } 1031b6e223a9e806921183da972253c49082a2e07944Duncan Sands SmallVector<SDValue, 8> Ops(NumOps); 1032b6e223a9e806921183da972253c49082a2e07944Duncan Sands for (unsigned i = 0; i < NumOps; ++i) 1033b6e223a9e806921183da972253c49082a2e07944Duncan Sands Ops[i] = N->getOperand(i); 1034245741d2a1ccec53a87bb5d02b711244c179f07aDuncan Sands 10352c8cf4b404e549482f593f62f9e27e0bab4a8b3fTim Northover return TLI.makeLibCall(DAG, LC, N->getValueType(0), 10362c8cf4b404e549482f593f62f9e27e0bab4a8b3fTim Northover &Ops[0], NumOps, isSigned, dl); 1037ddc016cc8592fe5c9379feb42a1fb4fb63164a91Duncan Sands} 1038ddc016cc8592fe5c9379feb42a1fb4fb63164a91Duncan Sands 10398d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher// ExpandChainLibCall - Expand a node into a call to a libcall. Similar to 10408d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher// ExpandLibCall except that the first operand is the in-chain. 10418d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopherstd::pair<SDValue, SDValue> 10428d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric ChristopherDAGTypeLegalizer::ExpandChainLibCall(RTLIB::Libcall LC, 10438d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher SDNode *Node, 10448d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher bool isSigned) { 10458d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher SDValue InChain = Node->getOperand(0); 10468d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher 10478d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher TargetLowering::ArgListTy Args; 10488d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher TargetLowering::ArgListEntry Entry; 10498d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) { 10508d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher EVT ArgVT = Node->getOperand(i).getValueType(); 1051db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext()); 10528d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher Entry.Node = Node->getOperand(i); 10538d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher Entry.Ty = ArgTy; 10548d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher Entry.isSExt = isSigned; 10558d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher Entry.isZExt = !isSigned; 10568d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher Args.push_back(Entry); 10578d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher } 10588d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC), 10598d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher TLI.getPointerTy()); 10608d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher 1061db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext()); 1062d2ea0e10cbd158c93fb870cdd03001b9cd1156b8Justin Holewinski TargetLowering:: 1063d2ea0e10cbd158c93fb870cdd03001b9cd1156b8Justin Holewinski CallLoweringInfo CLI(InChain, RetTy, isSigned, !isSigned, false, false, 10648d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher 0, TLI.getLibcallCallingConv(LC), /*isTailCall=*/false, 10654bfcd4acbc7d12aa55f8de9af84a38422f0f6d83Evan Cheng /*doesNotReturn=*/false, /*isReturnValueUsed=*/true, 10668d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher Callee, Args, DAG, Node->getDebugLoc()); 1067d2ea0e10cbd158c93fb870cdd03001b9cd1156b8Justin Holewinski std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI); 10688d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher 10698d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher return CallInfo; 10708d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher} 10718d93d19076fb6a67eeb63cb0ba79d00c3aa8478aEric Christopher 1072b6e223a9e806921183da972253c49082a2e07944Duncan Sands/// PromoteTargetBoolean - Promote the given target boolean to a target boolean 1073b6e223a9e806921183da972253c49082a2e07944Duncan Sands/// of the given type. A target boolean is an integer value, not necessarily of 1074b6e223a9e806921183da972253c49082a2e07944Duncan Sands/// type i1, the bits of which conform to getBooleanContents. 1075e50ed30282bb5b4a9ed952580523f2dda16215acOwen AndersonSDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, EVT VT) { 10766f38cb61a94b3abab70f0ee463bdcf55d86d334eDale Johannesen DebugLoc dl = Bool.getDebugLoc(); 107728b77e968d2b01fc9da724762bd8ddcd80650e32Duncan Sands ISD::NodeType ExtendCode = 107828b77e968d2b01fc9da724762bd8ddcd80650e32Duncan Sands TargetLowering::getExtendForContent(TLI.getBooleanContents(VT.isVector())); 10799c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen return DAG.getNode(ExtendCode, dl, VT, Bool); 108006f0aff69eb0289bdba19a364132bc522f44febaDuncan Sands} 108106f0aff69eb0289bdba19a364132bc522f44febaDuncan Sands 1082b6e223a9e806921183da972253c49082a2e07944Duncan Sands/// SplitInteger - Return the lower LoVT bits of Op in Lo and the upper HiVT 1083b6e223a9e806921183da972253c49082a2e07944Duncan Sands/// bits in Hi. 1084b6e223a9e806921183da972253c49082a2e07944Duncan Sandsvoid DAGTypeLegalizer::SplitInteger(SDValue Op, 1085e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT LoVT, EVT HiVT, 1086b6e223a9e806921183da972253c49082a2e07944Duncan Sands SDValue &Lo, SDValue &Hi) { 10876f38cb61a94b3abab70f0ee463bdcf55d86d334eDale Johannesen DebugLoc dl = Op.getDebugLoc(); 1088b6e223a9e806921183da972253c49082a2e07944Duncan Sands assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() == 1089b6e223a9e806921183da972253c49082a2e07944Duncan Sands Op.getValueType().getSizeInBits() && "Invalid integer splitting!"); 10909c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op); 10919c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op, 109292abc62399881ba9c525be80362c134ad836e2d9Duncan Sands DAG.getConstant(LoVT.getSizeInBits(), TLI.getPointerTy())); 10939c8ac447c464eedefa6acd8d71a3aff8280bb9d1Dale Johannesen Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi); 10947d0d8460646d1a06ff561775d40123a4cf65bf4dDuncan Sands} 10957d0d8460646d1a06ff561775d40123a4cf65bf4dDuncan Sands 1096b6e223a9e806921183da972253c49082a2e07944Duncan Sands/// SplitInteger - Return the lower and upper halves of Op's bits in a value 1097b6e223a9e806921183da972253c49082a2e07944Duncan Sands/// type half the size of Op's. 1098b6e223a9e806921183da972253c49082a2e07944Duncan Sandsvoid DAGTypeLegalizer::SplitInteger(SDValue Op, 1099b6e223a9e806921183da972253c49082a2e07944Duncan Sands SDValue &Lo, SDValue &Hi) { 110022d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), 110122d286b218f3267d57c507678b1af0fccc3a5df0Evan Cheng Op.getValueType().getSizeInBits()/2); 1102b6e223a9e806921183da972253c49082a2e07944Duncan Sands SplitInteger(Op, HalfVT, HalfVT, Lo, Hi); 110378cd649ad326f79a1f8424ca2b63cea3239a9a52Duncan Sands} 110478cd649ad326f79a1f8424ca2b63cea3239a9a52Duncan Sands 11057d0d8460646d1a06ff561775d40123a4cf65bf4dDuncan Sands 110601d029b82cb08367d81aa10cdc94d05360466649Chris Lattner//===----------------------------------------------------------------------===// 110701d029b82cb08367d81aa10cdc94d05360466649Chris Lattner// Entry Point 110801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner//===----------------------------------------------------------------------===// 110901d029b82cb08367d81aa10cdc94d05360466649Chris Lattner 111001d029b82cb08367d81aa10cdc94d05360466649Chris Lattner/// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 111125cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands/// only uses types natively supported by the target. Returns "true" if it made 111225cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands/// any changes. 111301d029b82cb08367d81aa10cdc94d05360466649Chris Lattner/// 111401d029b82cb08367d81aa10cdc94d05360466649Chris Lattner/// Note that this is an involved process that may invalidate pointers into 111501d029b82cb08367d81aa10cdc94d05360466649Chris Lattner/// the graph. 111625cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sandsbool SelectionDAG::LegalizeTypes() { 111725cf2275ff7de3de3bc0e508abaf457413d74725Duncan Sands return DAGTypeLegalizer(*this).run(); 111801d029b82cb08367d81aa10cdc94d05360466649Chris Lattner} 1119