1193323Sed//===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the SelectionDAG::LegalizeTypes method. It transforms 11193323Sed// an arbitrary well-formed SelectionDAG to only consist of legal types. This 12193323Sed// is common code shared among the LegalizeTypes*.cpp files. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16193323Sed#include "LegalizeTypes.h" 17193323Sed#include "llvm/ADT/SetVector.h" 18249423Sdim#include "llvm/IR/CallingConv.h" 19249423Sdim#include "llvm/IR/DataLayout.h" 20193323Sed#include "llvm/Support/CommandLine.h" 21198090Srdivacky#include "llvm/Support/ErrorHandling.h" 22198090Srdivacky#include "llvm/Support/raw_ostream.h" 23193323Sedusing namespace llvm; 24193323Sed 25193323Sedstatic cl::opt<bool> 26193323SedEnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden); 27193323Sed 28193323Sed/// PerformExpensiveChecks - Do extensive, expensive, sanity checking. 29193323Sedvoid DAGTypeLegalizer::PerformExpensiveChecks() { 30193323Sed // If a node is not processed, then none of its values should be mapped by any 31193323Sed // of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. 32193323Sed 33193323Sed // If a node is processed, then each value with an illegal type must be mapped 34193323Sed // by exactly one of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. 35193323Sed // Values with a legal type may be mapped by ReplacedValues, but not by any of 36193323Sed // the other maps. 37193323Sed 38193323Sed // Note that these invariants may not hold momentarily when processing a node: 39193323Sed // the node being processed may be put in a map before being marked Processed. 40193323Sed 41193323Sed // Note that it is possible to have nodes marked NewNode in the DAG. This can 42193323Sed // occur in two ways. Firstly, a node may be created during legalization but 43193323Sed // never passed to the legalization core. This is usually due to the implicit 44193323Sed // folding that occurs when using the DAG.getNode operators. Secondly, a new 45193323Sed // node may be passed to the legalization core, but when analyzed may morph 46193323Sed // into a different node, leaving the original node as a NewNode in the DAG. 47193323Sed // A node may morph if one of its operands changes during analysis. Whether 48193323Sed // it actually morphs or not depends on whether, after updating its operands, 49193323Sed // it is equivalent to an existing node: if so, it morphs into that existing 50193323Sed // node (CSE). An operand can change during analysis if the operand is a new 51193323Sed // node that morphs, or it is a processed value that was mapped to some other 52193323Sed // value (as recorded in ReplacedValues) in which case the operand is turned 53193323Sed // into that other value. If a node morphs then the node it morphed into will 54193323Sed // be used instead of it for legalization, however the original node continues 55193323Sed // to live on in the DAG. 56193323Sed // The conclusion is that though there may be nodes marked NewNode in the DAG, 57193323Sed // all uses of such nodes are also marked NewNode: the result is a fungus of 58193323Sed // NewNodes growing on top of the useful nodes, and perhaps using them, but 59193323Sed // not used by them. 60193323Sed 61193323Sed // If a value is mapped by ReplacedValues, then it must have no uses, except 62193323Sed // by nodes marked NewNode (see above). 63193323Sed 64193323Sed // The final node obtained by mapping by ReplacedValues is not marked NewNode. 65193323Sed // Note that ReplacedValues should be applied iteratively. 66193323Sed 67199989Srdivacky // Note that the ReplacedValues map may also map deleted nodes (by iterating 68199989Srdivacky // over the DAG we never dereference deleted nodes). This means that it may 69199989Srdivacky // also map nodes marked NewNode if the deallocated memory was reallocated as 70199989Srdivacky // another node, and that new node was not seen by the LegalizeTypes machinery 71199989Srdivacky // (for example because it was created but not used). In general, we cannot 72199989Srdivacky // distinguish between new nodes and deleted nodes. 73193323Sed SmallVector<SDNode*, 16> NewNodes; 74193323Sed for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 75193323Sed E = DAG.allnodes_end(); I != E; ++I) { 76193323Sed // Remember nodes marked NewNode - they are subject to extra checking below. 77193323Sed if (I->getNodeId() == NewNode) 78193323Sed NewNodes.push_back(I); 79193323Sed 80193323Sed for (unsigned i = 0, e = I->getNumValues(); i != e; ++i) { 81193323Sed SDValue Res(I, i); 82193323Sed bool Failed = false; 83193323Sed 84193323Sed unsigned Mapped = 0; 85193323Sed if (ReplacedValues.find(Res) != ReplacedValues.end()) { 86193323Sed Mapped |= 1; 87193323Sed // Check that remapped values are only used by nodes marked NewNode. 88193323Sed for (SDNode::use_iterator UI = I->use_begin(), UE = I->use_end(); 89193323Sed UI != UE; ++UI) 90193323Sed if (UI.getUse().getResNo() == i) 91193323Sed assert(UI->getNodeId() == NewNode && 92193323Sed "Remapped value has non-trivial use!"); 93193323Sed 94193323Sed // Check that the final result of applying ReplacedValues is not 95193323Sed // marked NewNode. 96193323Sed SDValue NewVal = ReplacedValues[Res]; 97193323Sed DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(NewVal); 98193323Sed while (I != ReplacedValues.end()) { 99193323Sed NewVal = I->second; 100193323Sed I = ReplacedValues.find(NewVal); 101193323Sed } 102193323Sed assert(NewVal.getNode()->getNodeId() != NewNode && 103193323Sed "ReplacedValues maps to a new node!"); 104193323Sed } 105193323Sed if (PromotedIntegers.find(Res) != PromotedIntegers.end()) 106193323Sed Mapped |= 2; 107193323Sed if (SoftenedFloats.find(Res) != SoftenedFloats.end()) 108193323Sed Mapped |= 4; 109193323Sed if (ScalarizedVectors.find(Res) != ScalarizedVectors.end()) 110193323Sed Mapped |= 8; 111193323Sed if (ExpandedIntegers.find(Res) != ExpandedIntegers.end()) 112193323Sed Mapped |= 16; 113193323Sed if (ExpandedFloats.find(Res) != ExpandedFloats.end()) 114193323Sed Mapped |= 32; 115193323Sed if (SplitVectors.find(Res) != SplitVectors.end()) 116193323Sed Mapped |= 64; 117193323Sed if (WidenedVectors.find(Res) != WidenedVectors.end()) 118193323Sed Mapped |= 128; 119193323Sed 120193323Sed if (I->getNodeId() != Processed) { 121199989Srdivacky // Since we allow ReplacedValues to map deleted nodes, it may map nodes 122199989Srdivacky // marked NewNode too, since a deleted node may have been reallocated as 123199989Srdivacky // another node that has not been seen by the LegalizeTypes machinery. 124199989Srdivacky if ((I->getNodeId() == NewNode && Mapped > 1) || 125199989Srdivacky (I->getNodeId() != NewNode && Mapped != 0)) { 126202375Srdivacky dbgs() << "Unprocessed value in a map!"; 127193323Sed Failed = true; 128193323Sed } 129193323Sed } else if (isTypeLegal(Res.getValueType()) || IgnoreNodeResults(I)) { 130193323Sed if (Mapped > 1) { 131202375Srdivacky dbgs() << "Value with legal type was transformed!"; 132193323Sed Failed = true; 133193323Sed } 134193323Sed } else { 135193323Sed if (Mapped == 0) { 136202375Srdivacky dbgs() << "Processed value not in any map!"; 137193323Sed Failed = true; 138193323Sed } else if (Mapped & (Mapped - 1)) { 139202375Srdivacky dbgs() << "Value in multiple maps!"; 140193323Sed Failed = true; 141193323Sed } 142193323Sed } 143193323Sed 144193323Sed if (Failed) { 145193323Sed if (Mapped & 1) 146202375Srdivacky dbgs() << " ReplacedValues"; 147193323Sed if (Mapped & 2) 148202375Srdivacky dbgs() << " PromotedIntegers"; 149193323Sed if (Mapped & 4) 150202375Srdivacky dbgs() << " SoftenedFloats"; 151193323Sed if (Mapped & 8) 152202375Srdivacky dbgs() << " ScalarizedVectors"; 153193323Sed if (Mapped & 16) 154202375Srdivacky dbgs() << " ExpandedIntegers"; 155193323Sed if (Mapped & 32) 156202375Srdivacky dbgs() << " ExpandedFloats"; 157193323Sed if (Mapped & 64) 158202375Srdivacky dbgs() << " SplitVectors"; 159193323Sed if (Mapped & 128) 160202375Srdivacky dbgs() << " WidenedVectors"; 161202375Srdivacky dbgs() << "\n"; 162198090Srdivacky llvm_unreachable(0); 163193323Sed } 164193323Sed } 165193323Sed } 166193323Sed 167193323Sed // Checked that NewNodes are only used by other NewNodes. 168193323Sed for (unsigned i = 0, e = NewNodes.size(); i != e; ++i) { 169193323Sed SDNode *N = NewNodes[i]; 170193323Sed for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 171193323Sed UI != UE; ++UI) 172193323Sed assert(UI->getNodeId() == NewNode && "NewNode used by non-NewNode!"); 173193323Sed } 174193323Sed} 175193323Sed 176193323Sed/// run - This is the main entry point for the type legalizer. This does a 177193323Sed/// top-down traversal of the dag, legalizing types as it goes. Returns "true" 178193323Sed/// if it made any changes. 179193323Sedbool DAGTypeLegalizer::run() { 180193323Sed bool Changed = false; 181193323Sed 182193323Sed // Create a dummy node (which is not added to allnodes), that adds a reference 183193323Sed // to the root node, preventing it from being deleted, and tracking any 184193323Sed // changes of the root. 185193323Sed HandleSDNode Dummy(DAG.getRoot()); 186193323Sed Dummy.setNodeId(Unanalyzed); 187193323Sed 188193323Sed // The root of the dag may dangle to deleted nodes until the type legalizer is 189193323Sed // done. Set it to null to avoid confusion. 190193323Sed DAG.setRoot(SDValue()); 191193323Sed 192193323Sed // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess' 193193323Sed // (and remembering them) if they are leaves and assigning 'Unanalyzed' if 194193323Sed // non-leaves. 195193323Sed for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 196193323Sed E = DAG.allnodes_end(); I != E; ++I) { 197193323Sed if (I->getNumOperands() == 0) { 198193323Sed I->setNodeId(ReadyToProcess); 199193323Sed Worklist.push_back(I); 200193323Sed } else { 201193323Sed I->setNodeId(Unanalyzed); 202193323Sed } 203193323Sed } 204193323Sed 205193323Sed // Now that we have a set of nodes to process, handle them all. 206193323Sed while (!Worklist.empty()) { 207193323Sed#ifndef XDEBUG 208193323Sed if (EnableExpensiveChecks) 209193323Sed#endif 210193323Sed PerformExpensiveChecks(); 211193323Sed 212193323Sed SDNode *N = Worklist.back(); 213193323Sed Worklist.pop_back(); 214193323Sed assert(N->getNodeId() == ReadyToProcess && 215193323Sed "Node should be ready if on worklist!"); 216193323Sed 217193323Sed if (IgnoreNodeResults(N)) 218193323Sed goto ScanOperands; 219193323Sed 220193323Sed // Scan the values produced by the node, checking to see if any result 221193323Sed // types are illegal. 222193323Sed for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) { 223198090Srdivacky EVT ResultVT = N->getValueType(i); 224193323Sed switch (getTypeAction(ResultVT)) { 225223017Sdim case TargetLowering::TypeLegal: 226193323Sed break; 227193323Sed // The following calls must take care of *all* of the node's results, 228193323Sed // not just the illegal result they were passed (this includes results 229193323Sed // with a legal type). Results can be remapped using ReplaceValueWith, 230193323Sed // or their promoted/expanded/etc values registered in PromotedIntegers, 231193323Sed // ExpandedIntegers etc. 232223017Sdim case TargetLowering::TypePromoteInteger: 233193323Sed PromoteIntegerResult(N, i); 234193323Sed Changed = true; 235193323Sed goto NodeDone; 236223017Sdim case TargetLowering::TypeExpandInteger: 237193323Sed ExpandIntegerResult(N, i); 238193323Sed Changed = true; 239193323Sed goto NodeDone; 240223017Sdim case TargetLowering::TypeSoftenFloat: 241193323Sed SoftenFloatResult(N, i); 242193323Sed Changed = true; 243193323Sed goto NodeDone; 244223017Sdim case TargetLowering::TypeExpandFloat: 245193323Sed ExpandFloatResult(N, i); 246193323Sed Changed = true; 247193323Sed goto NodeDone; 248223017Sdim case TargetLowering::TypeScalarizeVector: 249193323Sed ScalarizeVectorResult(N, i); 250193323Sed Changed = true; 251193323Sed goto NodeDone; 252223017Sdim case TargetLowering::TypeSplitVector: 253193323Sed SplitVectorResult(N, i); 254193323Sed Changed = true; 255193323Sed goto NodeDone; 256223017Sdim case TargetLowering::TypeWidenVector: 257193323Sed WidenVectorResult(N, i); 258193323Sed Changed = true; 259193323Sed goto NodeDone; 260193323Sed } 261193323Sed } 262193323Sed 263193323SedScanOperands: 264193323Sed // Scan the operand list for the node, handling any nodes with operands that 265193323Sed // are illegal. 266193323Sed { 267193323Sed unsigned NumOperands = N->getNumOperands(); 268193323Sed bool NeedsReanalyzing = false; 269193323Sed unsigned i; 270193323Sed for (i = 0; i != NumOperands; ++i) { 271193323Sed if (IgnoreNodeResults(N->getOperand(i).getNode())) 272193323Sed continue; 273193323Sed 274198090Srdivacky EVT OpVT = N->getOperand(i).getValueType(); 275193323Sed switch (getTypeAction(OpVT)) { 276223017Sdim case TargetLowering::TypeLegal: 277193323Sed continue; 278193323Sed // The following calls must either replace all of the node's results 279193323Sed // using ReplaceValueWith, and return "false"; or update the node's 280193323Sed // operands in place, and return "true". 281223017Sdim case TargetLowering::TypePromoteInteger: 282193323Sed NeedsReanalyzing = PromoteIntegerOperand(N, i); 283193323Sed Changed = true; 284193323Sed break; 285223017Sdim case TargetLowering::TypeExpandInteger: 286193323Sed NeedsReanalyzing = ExpandIntegerOperand(N, i); 287193323Sed Changed = true; 288193323Sed break; 289223017Sdim case TargetLowering::TypeSoftenFloat: 290193323Sed NeedsReanalyzing = SoftenFloatOperand(N, i); 291193323Sed Changed = true; 292193323Sed break; 293223017Sdim case TargetLowering::TypeExpandFloat: 294193323Sed NeedsReanalyzing = ExpandFloatOperand(N, i); 295193323Sed Changed = true; 296193323Sed break; 297223017Sdim case TargetLowering::TypeScalarizeVector: 298193323Sed NeedsReanalyzing = ScalarizeVectorOperand(N, i); 299193323Sed Changed = true; 300193323Sed break; 301223017Sdim case TargetLowering::TypeSplitVector: 302193323Sed NeedsReanalyzing = SplitVectorOperand(N, i); 303193323Sed Changed = true; 304193323Sed break; 305223017Sdim case TargetLowering::TypeWidenVector: 306193323Sed NeedsReanalyzing = WidenVectorOperand(N, i); 307193323Sed Changed = true; 308193323Sed break; 309193323Sed } 310193323Sed break; 311193323Sed } 312193323Sed 313193323Sed // The sub-method updated N in place. Check to see if any operands are new, 314193323Sed // and if so, mark them. If the node needs revisiting, don't add all users 315193323Sed // to the worklist etc. 316193323Sed if (NeedsReanalyzing) { 317193323Sed assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); 318193323Sed N->setNodeId(NewNode); 319193323Sed // Recompute the NodeId and correct processed operands, adding the node to 320193323Sed // the worklist if ready. 321193323Sed SDNode *M = AnalyzeNewNode(N); 322193323Sed if (M == N) 323193323Sed // The node didn't morph - nothing special to do, it will be revisited. 324193323Sed continue; 325193323Sed 326193323Sed // The node morphed - this is equivalent to legalizing by replacing every 327199989Srdivacky // value of N with the corresponding value of M. So do that now. 328193323Sed assert(N->getNumValues() == M->getNumValues() && 329193323Sed "Node morphing changed the number of results!"); 330193323Sed for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 331199989Srdivacky // Replacing the value takes care of remapping the new value. 332199989Srdivacky ReplaceValueWith(SDValue(N, i), SDValue(M, i)); 333193323Sed assert(N->getNodeId() == NewNode && "Unexpected node state!"); 334193323Sed // The node continues to live on as part of the NewNode fungus that 335193323Sed // grows on top of the useful nodes. Nothing more needs to be done 336193323Sed // with it - move on to the next node. 337193323Sed continue; 338193323Sed } 339193323Sed 340193323Sed if (i == NumOperands) { 341202375Srdivacky DEBUG(dbgs() << "Legally typed node: "; N->dump(&DAG); dbgs() << "\n"); 342193323Sed } 343193323Sed } 344193323SedNodeDone: 345193323Sed 346193323Sed // If we reach here, the node was processed, potentially creating new nodes. 347193323Sed // Mark it as processed and add its users to the worklist as appropriate. 348193323Sed assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); 349193323Sed N->setNodeId(Processed); 350193323Sed 351193323Sed for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 352193323Sed UI != E; ++UI) { 353193323Sed SDNode *User = *UI; 354193323Sed int NodeId = User->getNodeId(); 355193323Sed 356193323Sed // This node has two options: it can either be a new node or its Node ID 357193323Sed // may be a count of the number of operands it has that are not ready. 358193323Sed if (NodeId > 0) { 359193323Sed User->setNodeId(NodeId-1); 360193323Sed 361193323Sed // If this was the last use it was waiting on, add it to the ready list. 362193323Sed if (NodeId-1 == ReadyToProcess) 363193323Sed Worklist.push_back(User); 364193323Sed continue; 365193323Sed } 366193323Sed 367193323Sed // If this is an unreachable new node, then ignore it. If it ever becomes 368193323Sed // reachable by being used by a newly created node then it will be handled 369193323Sed // by AnalyzeNewNode. 370193323Sed if (NodeId == NewNode) 371193323Sed continue; 372193323Sed 373193323Sed // Otherwise, this node is new: this is the first operand of it that 374193323Sed // became ready. Its new NodeId is the number of operands it has minus 1 375193323Sed // (as this node is now processed). 376193323Sed assert(NodeId == Unanalyzed && "Unknown node ID!"); 377193323Sed User->setNodeId(User->getNumOperands() - 1); 378193323Sed 379193323Sed // If the node only has a single operand, it is now ready. 380193323Sed if (User->getNumOperands() == 1) 381193323Sed Worklist.push_back(User); 382193323Sed } 383193323Sed } 384193323Sed 385193323Sed#ifndef XDEBUG 386193323Sed if (EnableExpensiveChecks) 387193323Sed#endif 388193323Sed PerformExpensiveChecks(); 389193323Sed 390193323Sed // If the root changed (e.g. it was a dead load) update the root. 391193323Sed DAG.setRoot(Dummy.getValue()); 392193323Sed 393193323Sed // Remove dead nodes. This is important to do for cleanliness but also before 394193323Sed // the checking loop below. Implicit folding by the DAG.getNode operators and 395193323Sed // node morphing can cause unreachable nodes to be around with their flags set 396193323Sed // to new. 397193323Sed DAG.RemoveDeadNodes(); 398193323Sed 399193323Sed // In a debug build, scan all the nodes to make sure we found them all. This 400193323Sed // ensures that there are no cycles and that everything got processed. 401193323Sed#ifndef NDEBUG 402193323Sed for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 403193323Sed E = DAG.allnodes_end(); I != E; ++I) { 404193323Sed bool Failed = false; 405193323Sed 406193323Sed // Check that all result types are legal. 407193323Sed if (!IgnoreNodeResults(I)) 408193323Sed for (unsigned i = 0, NumVals = I->getNumValues(); i < NumVals; ++i) 409193323Sed if (!isTypeLegal(I->getValueType(i))) { 410202375Srdivacky dbgs() << "Result type " << i << " illegal!\n"; 411193323Sed Failed = true; 412193323Sed } 413193323Sed 414193323Sed // Check that all operand types are legal. 415193323Sed for (unsigned i = 0, NumOps = I->getNumOperands(); i < NumOps; ++i) 416193323Sed if (!IgnoreNodeResults(I->getOperand(i).getNode()) && 417193323Sed !isTypeLegal(I->getOperand(i).getValueType())) { 418202375Srdivacky dbgs() << "Operand type " << i << " illegal!\n"; 419193323Sed Failed = true; 420193323Sed } 421193323Sed 422193323Sed if (I->getNodeId() != Processed) { 423193323Sed if (I->getNodeId() == NewNode) 424202375Srdivacky dbgs() << "New node not analyzed?\n"; 425193323Sed else if (I->getNodeId() == Unanalyzed) 426202375Srdivacky dbgs() << "Unanalyzed node not noticed?\n"; 427193323Sed else if (I->getNodeId() > 0) 428202375Srdivacky dbgs() << "Operand not processed?\n"; 429193323Sed else if (I->getNodeId() == ReadyToProcess) 430202375Srdivacky dbgs() << "Not added to worklist?\n"; 431193323Sed Failed = true; 432193323Sed } 433193323Sed 434193323Sed if (Failed) { 435202375Srdivacky I->dump(&DAG); dbgs() << "\n"; 436198090Srdivacky llvm_unreachable(0); 437193323Sed } 438193323Sed } 439193323Sed#endif 440193323Sed 441193323Sed return Changed; 442193323Sed} 443193323Sed 444193323Sed/// AnalyzeNewNode - The specified node is the root of a subtree of potentially 445193323Sed/// new nodes. Correct any processed operands (this may change the node) and 446193323Sed/// calculate the NodeId. If the node itself changes to a processed node, it 447193323Sed/// is not remapped - the caller needs to take care of this. 448193323Sed/// Returns the potentially changed node. 449193323SedSDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) { 450193323Sed // If this was an existing node that is already done, we're done. 451193323Sed if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed) 452193323Sed return N; 453193323Sed 454193323Sed // Remove any stale map entries. 455193323Sed ExpungeNode(N); 456193323Sed 457193323Sed // Okay, we know that this node is new. Recursively walk all of its operands 458193323Sed // to see if they are new also. The depth of this walk is bounded by the size 459193323Sed // of the new tree that was constructed (usually 2-3 nodes), so we don't worry 460193323Sed // about revisiting of nodes. 461193323Sed // 462193323Sed // As we walk the operands, keep track of the number of nodes that are 463193323Sed // processed. If non-zero, this will become the new nodeid of this node. 464193323Sed // Operands may morph when they are analyzed. If so, the node will be 465193323Sed // updated after all operands have been analyzed. Since this is rare, 466193323Sed // the code tries to minimize overhead in the non-morphing case. 467193323Sed 468193323Sed SmallVector<SDValue, 8> NewOps; 469193323Sed unsigned NumProcessed = 0; 470193323Sed for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 471193323Sed SDValue OrigOp = N->getOperand(i); 472193323Sed SDValue Op = OrigOp; 473193323Sed 474193323Sed AnalyzeNewValue(Op); // Op may morph. 475193323Sed 476193323Sed if (Op.getNode()->getNodeId() == Processed) 477193323Sed ++NumProcessed; 478193323Sed 479193323Sed if (!NewOps.empty()) { 480193323Sed // Some previous operand changed. Add this one to the list. 481193323Sed NewOps.push_back(Op); 482193323Sed } else if (Op != OrigOp) { 483193323Sed // This is the first operand to change - add all operands so far. 484210299Sed NewOps.append(N->op_begin(), N->op_begin() + i); 485193323Sed NewOps.push_back(Op); 486193323Sed } 487193323Sed } 488193323Sed 489193323Sed // Some operands changed - update the node. 490193323Sed if (!NewOps.empty()) { 491210299Sed SDNode *M = DAG.UpdateNodeOperands(N, &NewOps[0], NewOps.size()); 492193323Sed if (M != N) { 493193323Sed // The node morphed into a different node. Normally for this to happen 494193323Sed // the original node would have to be marked NewNode. However this can 495193323Sed // in theory momentarily not be the case while ReplaceValueWith is doing 496193323Sed // its stuff. Mark the original node NewNode to help sanity checking. 497193323Sed N->setNodeId(NewNode); 498193323Sed if (M->getNodeId() != NewNode && M->getNodeId() != Unanalyzed) 499193323Sed // It morphed into a previously analyzed node - nothing more to do. 500193323Sed return M; 501193323Sed 502193323Sed // It morphed into a different new node. Do the equivalent of passing 503193323Sed // it to AnalyzeNewNode: expunge it and calculate the NodeId. No need 504193323Sed // to remap the operands, since they are the same as the operands we 505193323Sed // remapped above. 506193323Sed N = M; 507193323Sed ExpungeNode(N); 508193323Sed } 509193323Sed } 510193323Sed 511193323Sed // Calculate the NodeId. 512193323Sed N->setNodeId(N->getNumOperands() - NumProcessed); 513193323Sed if (N->getNodeId() == ReadyToProcess) 514193323Sed Worklist.push_back(N); 515193323Sed 516193323Sed return N; 517193323Sed} 518193323Sed 519193323Sed/// AnalyzeNewValue - Call AnalyzeNewNode, updating the node in Val if needed. 520193323Sed/// If the node changes to a processed node, then remap it. 521193323Sedvoid DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) { 522193323Sed Val.setNode(AnalyzeNewNode(Val.getNode())); 523193323Sed if (Val.getNode()->getNodeId() == Processed) 524193323Sed // We were passed a processed node, or it morphed into one - remap it. 525193323Sed RemapValue(Val); 526193323Sed} 527193323Sed 528193323Sed/// ExpungeNode - If N has a bogus mapping in ReplacedValues, eliminate it. 529193323Sed/// This can occur when a node is deleted then reallocated as a new node - 530193323Sed/// the mapping in ReplacedValues applies to the deleted node, not the new 531193323Sed/// one. 532193323Sed/// The only map that can have a deleted node as a source is ReplacedValues. 533193323Sed/// Other maps can have deleted nodes as targets, but since their looked-up 534193323Sed/// values are always immediately remapped using RemapValue, resulting in a 535193323Sed/// not-deleted node, this is harmless as long as ReplacedValues/RemapValue 536193323Sed/// always performs correct mappings. In order to keep the mapping correct, 537193323Sed/// ExpungeNode should be called on any new nodes *before* adding them as 538193323Sed/// either source or target to ReplacedValues (which typically means calling 539193323Sed/// Expunge when a new node is first seen, since it may no longer be marked 540193323Sed/// NewNode by the time it is added to ReplacedValues). 541193323Sedvoid DAGTypeLegalizer::ExpungeNode(SDNode *N) { 542193323Sed if (N->getNodeId() != NewNode) 543193323Sed return; 544193323Sed 545193323Sed // If N is not remapped by ReplacedValues then there is nothing to do. 546193323Sed unsigned i, e; 547193323Sed for (i = 0, e = N->getNumValues(); i != e; ++i) 548193323Sed if (ReplacedValues.find(SDValue(N, i)) != ReplacedValues.end()) 549193323Sed break; 550193323Sed 551193323Sed if (i == e) 552193323Sed return; 553193323Sed 554193323Sed // Remove N from all maps - this is expensive but rare. 555193323Sed 556193323Sed for (DenseMap<SDValue, SDValue>::iterator I = PromotedIntegers.begin(), 557193323Sed E = PromotedIntegers.end(); I != E; ++I) { 558193323Sed assert(I->first.getNode() != N); 559193323Sed RemapValue(I->second); 560193323Sed } 561193323Sed 562193323Sed for (DenseMap<SDValue, SDValue>::iterator I = SoftenedFloats.begin(), 563193323Sed E = SoftenedFloats.end(); I != E; ++I) { 564193323Sed assert(I->first.getNode() != N); 565193323Sed RemapValue(I->second); 566193323Sed } 567193323Sed 568193323Sed for (DenseMap<SDValue, SDValue>::iterator I = ScalarizedVectors.begin(), 569193323Sed E = ScalarizedVectors.end(); I != E; ++I) { 570193323Sed assert(I->first.getNode() != N); 571193323Sed RemapValue(I->second); 572193323Sed } 573193323Sed 574193323Sed for (DenseMap<SDValue, SDValue>::iterator I = WidenedVectors.begin(), 575193323Sed E = WidenedVectors.end(); I != E; ++I) { 576193323Sed assert(I->first.getNode() != N); 577193323Sed RemapValue(I->second); 578193323Sed } 579193323Sed 580193323Sed for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator 581193323Sed I = ExpandedIntegers.begin(), E = ExpandedIntegers.end(); I != E; ++I){ 582193323Sed assert(I->first.getNode() != N); 583193323Sed RemapValue(I->second.first); 584193323Sed RemapValue(I->second.second); 585193323Sed } 586193323Sed 587193323Sed for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator 588193323Sed I = ExpandedFloats.begin(), E = ExpandedFloats.end(); I != E; ++I) { 589193323Sed assert(I->first.getNode() != N); 590193323Sed RemapValue(I->second.first); 591193323Sed RemapValue(I->second.second); 592193323Sed } 593193323Sed 594193323Sed for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator 595193323Sed I = SplitVectors.begin(), E = SplitVectors.end(); I != E; ++I) { 596193323Sed assert(I->first.getNode() != N); 597193323Sed RemapValue(I->second.first); 598193323Sed RemapValue(I->second.second); 599193323Sed } 600193323Sed 601193323Sed for (DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.begin(), 602193323Sed E = ReplacedValues.end(); I != E; ++I) 603193323Sed RemapValue(I->second); 604193323Sed 605193323Sed for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 606193323Sed ReplacedValues.erase(SDValue(N, i)); 607193323Sed} 608193323Sed 609193323Sed/// RemapValue - If the specified value was already legalized to another value, 610193323Sed/// replace it by that value. 611193323Sedvoid DAGTypeLegalizer::RemapValue(SDValue &N) { 612193323Sed DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(N); 613193323Sed if (I != ReplacedValues.end()) { 614193323Sed // Use path compression to speed up future lookups if values get multiply 615193323Sed // replaced with other values. 616193323Sed RemapValue(I->second); 617193323Sed N = I->second; 618256024Sdim 619256024Sdim // Note that it is possible to have N.getNode()->getNodeId() == NewNode at 620256024Sdim // this point because it is possible for a node to be put in the map before 621256024Sdim // being processed. 622193323Sed } 623193323Sed} 624193323Sed 625193323Sednamespace { 626193323Sed /// NodeUpdateListener - This class is a DAGUpdateListener that listens for 627193323Sed /// updates to nodes and recomputes their ready state. 628198892Srdivacky class NodeUpdateListener : public SelectionDAG::DAGUpdateListener { 629193323Sed DAGTypeLegalizer &DTL; 630193323Sed SmallSetVector<SDNode*, 16> &NodesToAnalyze; 631193323Sed public: 632193323Sed explicit NodeUpdateListener(DAGTypeLegalizer &dtl, 633193323Sed SmallSetVector<SDNode*, 16> &nta) 634239462Sdim : SelectionDAG::DAGUpdateListener(dtl.getDAG()), 635239462Sdim DTL(dtl), NodesToAnalyze(nta) {} 636193323Sed 637193323Sed virtual void NodeDeleted(SDNode *N, SDNode *E) { 638193323Sed assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 639193323Sed N->getNodeId() != DAGTypeLegalizer::Processed && 640193323Sed "Invalid node ID for RAUW deletion!"); 641193323Sed // It is possible, though rare, for the deleted node N to occur as a 642193323Sed // target in a map, so note the replacement N -> E in ReplacedValues. 643193323Sed assert(E && "Node not replaced?"); 644193323Sed DTL.NoteDeletion(N, E); 645193323Sed 646193323Sed // In theory the deleted node could also have been scheduled for analysis. 647193323Sed // So remove it from the set of nodes which will be analyzed. 648193323Sed NodesToAnalyze.remove(N); 649193323Sed 650193323Sed // In general nothing needs to be done for E, since it didn't change but 651193323Sed // only gained new uses. However N -> E was just added to ReplacedValues, 652193323Sed // and the result of a ReplacedValues mapping is not allowed to be marked 653193323Sed // NewNode. So if E is marked NewNode, then it needs to be analyzed. 654193323Sed if (E->getNodeId() == DAGTypeLegalizer::NewNode) 655193323Sed NodesToAnalyze.insert(E); 656193323Sed } 657193323Sed 658193323Sed virtual void NodeUpdated(SDNode *N) { 659193323Sed // Node updates can mean pretty much anything. It is possible that an 660193323Sed // operand was set to something already processed (f.e.) in which case 661193323Sed // this node could become ready. Recompute its flags. 662193323Sed assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 663193323Sed N->getNodeId() != DAGTypeLegalizer::Processed && 664193323Sed "Invalid node ID for RAUW deletion!"); 665193323Sed N->setNodeId(DAGTypeLegalizer::NewNode); 666193323Sed NodesToAnalyze.insert(N); 667193323Sed } 668193323Sed }; 669193323Sed} 670193323Sed 671193323Sed 672199989Srdivacky/// ReplaceValueWith - The specified value was legalized to the specified other 673199989Srdivacky/// value. Update the DAG and NodeIds replacing any uses of From to use To 674199989Srdivacky/// instead. 675199989Srdivackyvoid DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) { 676193323Sed assert(From.getNode() != To.getNode() && "Potential legalization loop!"); 677193323Sed 678193323Sed // If expansion produced new nodes, make sure they are properly marked. 679199989Srdivacky ExpungeNode(From.getNode()); 680193323Sed AnalyzeNewValue(To); // Expunges To. 681193323Sed 682193323Sed // Anything that used the old node should now use the new one. Note that this 683193323Sed // can potentially cause recursive merging. 684193323Sed SmallSetVector<SDNode*, 16> NodesToAnalyze; 685193323Sed NodeUpdateListener NUL(*this, NodesToAnalyze); 686210299Sed do { 687239462Sdim DAG.ReplaceAllUsesOfValueWith(From, To); 688193323Sed 689210299Sed // The old node may still be present in a map like ExpandedIntegers or 690210299Sed // PromotedIntegers. Inform maps about the replacement. 691210299Sed ReplacedValues[From] = To; 692199989Srdivacky 693210299Sed // Process the list of nodes that need to be reanalyzed. 694210299Sed while (!NodesToAnalyze.empty()) { 695210299Sed SDNode *N = NodesToAnalyze.back(); 696210299Sed NodesToAnalyze.pop_back(); 697210299Sed if (N->getNodeId() != DAGTypeLegalizer::NewNode) 698210299Sed // The node was analyzed while reanalyzing an earlier node - it is safe 699210299Sed // to skip. Note that this is not a morphing node - otherwise it would 700210299Sed // still be marked NewNode. 701210299Sed continue; 702193323Sed 703210299Sed // Analyze the node's operands and recalculate the node ID. 704210299Sed SDNode *M = AnalyzeNewNode(N); 705210299Sed if (M != N) { 706210299Sed // The node morphed into a different node. Make everyone use the new 707210299Sed // node instead. 708210299Sed assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!"); 709210299Sed assert(N->getNumValues() == M->getNumValues() && 710210299Sed "Node morphing changed the number of results!"); 711210299Sed for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 712210299Sed SDValue OldVal(N, i); 713210299Sed SDValue NewVal(M, i); 714210299Sed if (M->getNodeId() == Processed) 715210299Sed RemapValue(NewVal); 716239462Sdim DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal); 717218893Sdim // OldVal may be a target of the ReplacedValues map which was marked 718218893Sdim // NewNode to force reanalysis because it was updated. Ensure that 719218893Sdim // anything that ReplacedValues mapped to OldVal will now be mapped 720218893Sdim // all the way to NewVal. 721218893Sdim ReplacedValues[OldVal] = NewVal; 722210299Sed } 723210299Sed // The original node continues to exist in the DAG, marked NewNode. 724193323Sed } 725193323Sed } 726210299Sed // When recursively update nodes with new nodes, it is possible to have 727210299Sed // new uses of From due to CSE. If this happens, replace the new uses of 728210299Sed // From with To. 729210299Sed } while (!From.use_empty()); 730193323Sed} 731193323Sed 732193323Sedvoid DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) { 733207618Srdivacky assert(Result.getValueType() == 734207618Srdivacky TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 735198090Srdivacky "Invalid type for promoted integer"); 736193323Sed AnalyzeNewValue(Result); 737193323Sed 738193323Sed SDValue &OpEntry = PromotedIntegers[Op]; 739193323Sed assert(OpEntry.getNode() == 0 && "Node is already promoted!"); 740193323Sed OpEntry = Result; 741193323Sed} 742193323Sed 743193323Sedvoid DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) { 744207618Srdivacky assert(Result.getValueType() == 745207618Srdivacky TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 746198090Srdivacky "Invalid type for softened float"); 747193323Sed AnalyzeNewValue(Result); 748193323Sed 749193323Sed SDValue &OpEntry = SoftenedFloats[Op]; 750193323Sed assert(OpEntry.getNode() == 0 && "Node is already converted to integer!"); 751193323Sed OpEntry = Result; 752193323Sed} 753193323Sed 754193323Sedvoid DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) { 755234353Sdim // Note that in some cases vector operation operands may be greater than 756234353Sdim // the vector element type. For example BUILD_VECTOR of type <1 x i1> with 757234353Sdim // a constant i8 operand. 758234353Sdim assert(Result.getValueType().getSizeInBits() >= 759234353Sdim Op.getValueType().getVectorElementType().getSizeInBits() && 760198090Srdivacky "Invalid type for scalarized vector"); 761193323Sed AnalyzeNewValue(Result); 762193323Sed 763193323Sed SDValue &OpEntry = ScalarizedVectors[Op]; 764193323Sed assert(OpEntry.getNode() == 0 && "Node is already scalarized!"); 765193323Sed OpEntry = Result; 766193323Sed} 767193323Sed 768193323Sedvoid DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo, 769193323Sed SDValue &Hi) { 770193323Sed std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op]; 771193323Sed RemapValue(Entry.first); 772193323Sed RemapValue(Entry.second); 773193323Sed assert(Entry.first.getNode() && "Operand isn't expanded"); 774193323Sed Lo = Entry.first; 775193323Sed Hi = Entry.second; 776193323Sed} 777193323Sed 778193323Sedvoid DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo, 779193323Sed SDValue Hi) { 780207618Srdivacky assert(Lo.getValueType() == 781207618Srdivacky TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 782198090Srdivacky Hi.getValueType() == Lo.getValueType() && 783198090Srdivacky "Invalid type for expanded integer"); 784193323Sed // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 785193323Sed AnalyzeNewValue(Lo); 786193323Sed AnalyzeNewValue(Hi); 787193323Sed 788193323Sed // Remember that this is the result of the node. 789193323Sed std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op]; 790193323Sed assert(Entry.first.getNode() == 0 && "Node already expanded"); 791193323Sed Entry.first = Lo; 792193323Sed Entry.second = Hi; 793193323Sed} 794193323Sed 795193323Sedvoid DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo, 796193323Sed SDValue &Hi) { 797193323Sed std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op]; 798193323Sed RemapValue(Entry.first); 799193323Sed RemapValue(Entry.second); 800193323Sed assert(Entry.first.getNode() && "Operand isn't expanded"); 801193323Sed Lo = Entry.first; 802193323Sed Hi = Entry.second; 803193323Sed} 804193323Sed 805193323Sedvoid DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo, 806193323Sed SDValue Hi) { 807207618Srdivacky assert(Lo.getValueType() == 808207618Srdivacky TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 809198090Srdivacky Hi.getValueType() == Lo.getValueType() && 810198090Srdivacky "Invalid type for expanded float"); 811193323Sed // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 812193323Sed AnalyzeNewValue(Lo); 813193323Sed AnalyzeNewValue(Hi); 814193323Sed 815193323Sed // Remember that this is the result of the node. 816193323Sed std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op]; 817193323Sed assert(Entry.first.getNode() == 0 && "Node already expanded"); 818193323Sed Entry.first = Lo; 819193323Sed Entry.second = Hi; 820193323Sed} 821193323Sed 822193323Sedvoid DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo, 823193323Sed SDValue &Hi) { 824193323Sed std::pair<SDValue, SDValue> &Entry = SplitVectors[Op]; 825193323Sed RemapValue(Entry.first); 826193323Sed RemapValue(Entry.second); 827193323Sed assert(Entry.first.getNode() && "Operand isn't split"); 828193323Sed Lo = Entry.first; 829193323Sed Hi = Entry.second; 830193323Sed} 831193323Sed 832193323Sedvoid DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo, 833193323Sed SDValue Hi) { 834198090Srdivacky assert(Lo.getValueType().getVectorElementType() == 835198090Srdivacky Op.getValueType().getVectorElementType() && 836198090Srdivacky 2*Lo.getValueType().getVectorNumElements() == 837198090Srdivacky Op.getValueType().getVectorNumElements() && 838198090Srdivacky Hi.getValueType() == Lo.getValueType() && 839198090Srdivacky "Invalid type for split vector"); 840193323Sed // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 841193323Sed AnalyzeNewValue(Lo); 842193323Sed AnalyzeNewValue(Hi); 843193323Sed 844193323Sed // Remember that this is the result of the node. 845193323Sed std::pair<SDValue, SDValue> &Entry = SplitVectors[Op]; 846193323Sed assert(Entry.first.getNode() == 0 && "Node already split"); 847193323Sed Entry.first = Lo; 848193323Sed Entry.second = Hi; 849193323Sed} 850193323Sed 851193323Sedvoid DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) { 852207618Srdivacky assert(Result.getValueType() == 853207618Srdivacky TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 854198090Srdivacky "Invalid type for widened vector"); 855193323Sed AnalyzeNewValue(Result); 856193323Sed 857193323Sed SDValue &OpEntry = WidenedVectors[Op]; 858193323Sed assert(OpEntry.getNode() == 0 && "Node already widened!"); 859193323Sed OpEntry = Result; 860193323Sed} 861193323Sed 862193323Sed 863193323Sed//===----------------------------------------------------------------------===// 864193323Sed// Utilities. 865193323Sed//===----------------------------------------------------------------------===// 866193323Sed 867193323Sed/// BitConvertToInteger - Convert to an integer of the same size. 868193323SedSDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) { 869193323Sed unsigned BitWidth = Op.getValueType().getSizeInBits(); 870263508Sdim return DAG.getNode(ISD::BITCAST, SDLoc(Op), 871198090Srdivacky EVT::getIntegerVT(*DAG.getContext(), BitWidth), Op); 872193323Sed} 873193323Sed 874193323Sed/// BitConvertVectorToIntegerVector - Convert to a vector of integers of the 875193323Sed/// same size. 876193323SedSDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(SDValue Op) { 877193323Sed assert(Op.getValueType().isVector() && "Only applies to vectors!"); 878193323Sed unsigned EltWidth = Op.getValueType().getVectorElementType().getSizeInBits(); 879198090Srdivacky EVT EltNVT = EVT::getIntegerVT(*DAG.getContext(), EltWidth); 880193323Sed unsigned NumElts = Op.getValueType().getVectorNumElements(); 881263508Sdim return DAG.getNode(ISD::BITCAST, SDLoc(Op), 882198090Srdivacky EVT::getVectorVT(*DAG.getContext(), EltNVT, NumElts), Op); 883193323Sed} 884193323Sed 885193323SedSDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op, 886198090Srdivacky EVT DestVT) { 887263508Sdim SDLoc dl(Op); 888193323Sed // Create the stack frame object. Make sure it is aligned for both 889193323Sed // the source and destination types. 890193323Sed SDValue StackPtr = DAG.CreateStackTemporary(Op.getValueType(), DestVT); 891193323Sed // Emit a store to the stack slot. 892218893Sdim SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, 893218893Sdim MachinePointerInfo(), false, false, 0); 894193323Sed // Result is a load from the stack slot. 895218893Sdim return DAG.getLoad(DestVT, dl, Store, StackPtr, MachinePointerInfo(), 896234353Sdim false, false, false, 0); 897193323Sed} 898193323Sed 899193323Sed/// CustomLowerNode - Replace the node's results with custom code provided 900193323Sed/// by the target and return "true", or do nothing and return "false". 901193323Sed/// The last parameter is FALSE if we are dealing with a node with legal 902193323Sed/// result types and illegal operand. The second parameter denotes the type of 903193323Sed/// illegal OperandNo in that case. 904193323Sed/// The last parameter being TRUE means we are dealing with a 905193323Sed/// node with illegal result types. The second parameter denotes the type of 906193323Sed/// illegal ResNo in that case. 907198090Srdivackybool DAGTypeLegalizer::CustomLowerNode(SDNode *N, EVT VT, bool LegalizeResult) { 908193323Sed // See if the target wants to custom lower this node. 909193323Sed if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) 910193323Sed return false; 911193323Sed 912193323Sed SmallVector<SDValue, 8> Results; 913193323Sed if (LegalizeResult) 914193323Sed TLI.ReplaceNodeResults(N, Results, DAG); 915193323Sed else 916193323Sed TLI.LowerOperationWrapper(N, Results, DAG); 917193323Sed 918193323Sed if (Results.empty()) 919193323Sed // The target didn't want to custom lower it after all. 920193323Sed return false; 921193323Sed 922193323Sed // Make everything that once used N's values now use those in Results instead. 923193323Sed assert(Results.size() == N->getNumValues() && 924193323Sed "Custom lowering returned the wrong number of results!"); 925249423Sdim for (unsigned i = 0, e = Results.size(); i != e; ++i) { 926193323Sed ReplaceValueWith(SDValue(N, i), Results[i]); 927249423Sdim } 928193323Sed return true; 929193323Sed} 930193323Sed 931199989Srdivacky 932199989Srdivacky/// CustomWidenLowerNode - Widen the node's results with custom code provided 933199989Srdivacky/// by the target and return "true", or do nothing and return "false". 934199989Srdivackybool DAGTypeLegalizer::CustomWidenLowerNode(SDNode *N, EVT VT) { 935199989Srdivacky // See if the target wants to custom lower this node. 936199989Srdivacky if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) 937199989Srdivacky return false; 938199989Srdivacky 939199989Srdivacky SmallVector<SDValue, 8> Results; 940199989Srdivacky TLI.ReplaceNodeResults(N, Results, DAG); 941199989Srdivacky 942199989Srdivacky if (Results.empty()) 943199989Srdivacky // The target didn't want to custom widen lower its result after all. 944199989Srdivacky return false; 945199989Srdivacky 946199989Srdivacky // Update the widening map. 947199989Srdivacky assert(Results.size() == N->getNumValues() && 948199989Srdivacky "Custom lowering returned the wrong number of results!"); 949199989Srdivacky for (unsigned i = 0, e = Results.size(); i != e; ++i) 950199989Srdivacky SetWidenedVector(SDValue(N, i), Results[i]); 951199989Srdivacky return true; 952199989Srdivacky} 953199989Srdivacky 954226633SdimSDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(SDNode *N, unsigned ResNo) { 955226633Sdim for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 956226633Sdim if (i != ResNo) 957226633Sdim ReplaceValueWith(SDValue(N, i), SDValue(N->getOperand(i))); 958239462Sdim return SDValue(N->getOperand(ResNo)); 959226633Sdim} 960226633Sdim 961193323Sed/// GetPairElements - Use ISD::EXTRACT_ELEMENT nodes to extract the low and 962193323Sed/// high parts of the given value. 963193323Sedvoid DAGTypeLegalizer::GetPairElements(SDValue Pair, 964193323Sed SDValue &Lo, SDValue &Hi) { 965263508Sdim SDLoc dl(Pair); 966198090Srdivacky EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.getValueType()); 967193323Sed Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair, 968193323Sed DAG.getIntPtrConstant(0)); 969193323Sed Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair, 970193323Sed DAG.getIntPtrConstant(1)); 971193323Sed} 972193323Sed 973198090SrdivackySDValue DAGTypeLegalizer::GetVectorElementPointer(SDValue VecPtr, EVT EltVT, 974193323Sed SDValue Index) { 975263508Sdim SDLoc dl(Index); 976193323Sed // Make sure the index type is big enough to compute in. 977263508Sdim Index = DAG.getZExtOrTrunc(Index, dl, TLI.getPointerTy()); 978193323Sed 979193323Sed // Calculate the element offset and add it to the pointer. 980193323Sed unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size. 981193323Sed 982193323Sed Index = DAG.getNode(ISD::MUL, dl, Index.getValueType(), Index, 983193323Sed DAG.getConstant(EltSize, Index.getValueType())); 984193323Sed return DAG.getNode(ISD::ADD, dl, Index.getValueType(), Index, VecPtr); 985193323Sed} 986193323Sed 987193323Sed/// JoinIntegers - Build an integer with low bits Lo and high bits Hi. 988193323SedSDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) { 989263508Sdim // Arbitrarily use dlHi for result SDLoc 990263508Sdim SDLoc dlHi(Hi); 991263508Sdim SDLoc dlLo(Lo); 992198090Srdivacky EVT LVT = Lo.getValueType(); 993198090Srdivacky EVT HVT = Hi.getValueType(); 994207618Srdivacky EVT NVT = EVT::getIntegerVT(*DAG.getContext(), 995207618Srdivacky LVT.getSizeInBits() + HVT.getSizeInBits()); 996193323Sed 997193323Sed Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo); 998193323Sed Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi); 999193323Sed Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi, 1000193323Sed DAG.getConstant(LVT.getSizeInBits(), TLI.getPointerTy())); 1001193323Sed return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi); 1002193323Sed} 1003193323Sed 1004193323Sed/// LibCallify - Convert the node into a libcall with the same prototype. 1005193323SedSDValue DAGTypeLegalizer::LibCallify(RTLIB::Libcall LC, SDNode *N, 1006193323Sed bool isSigned) { 1007193323Sed unsigned NumOps = N->getNumOperands(); 1008263508Sdim SDLoc dl(N); 1009193323Sed if (NumOps == 0) { 1010263508Sdim return TLI.makeLibCall(DAG, LC, N->getValueType(0), 0, 0, isSigned, 1011263508Sdim dl).first; 1012193323Sed } else if (NumOps == 1) { 1013193323Sed SDValue Op = N->getOperand(0); 1014263508Sdim return TLI.makeLibCall(DAG, LC, N->getValueType(0), &Op, 1, isSigned, 1015263508Sdim dl).first; 1016193323Sed } else if (NumOps == 2) { 1017193323Sed SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) }; 1018263508Sdim return TLI.makeLibCall(DAG, LC, N->getValueType(0), Ops, 2, isSigned, 1019263508Sdim dl).first; 1020193323Sed } 1021193323Sed SmallVector<SDValue, 8> Ops(NumOps); 1022193323Sed for (unsigned i = 0; i < NumOps; ++i) 1023193323Sed Ops[i] = N->getOperand(i); 1024193323Sed 1025249423Sdim return TLI.makeLibCall(DAG, LC, N->getValueType(0), 1026263508Sdim &Ops[0], NumOps, isSigned, dl).first; 1027193323Sed} 1028193323Sed 1029218893Sdim// ExpandChainLibCall - Expand a node into a call to a libcall. Similar to 1030218893Sdim// ExpandLibCall except that the first operand is the in-chain. 1031218893Sdimstd::pair<SDValue, SDValue> 1032218893SdimDAGTypeLegalizer::ExpandChainLibCall(RTLIB::Libcall LC, 1033218893Sdim SDNode *Node, 1034218893Sdim bool isSigned) { 1035218893Sdim SDValue InChain = Node->getOperand(0); 1036218893Sdim 1037218893Sdim TargetLowering::ArgListTy Args; 1038218893Sdim TargetLowering::ArgListEntry Entry; 1039218893Sdim for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i) { 1040218893Sdim EVT ArgVT = Node->getOperand(i).getValueType(); 1041226633Sdim Type *ArgTy = ArgVT.getTypeForEVT(*DAG.getContext()); 1042218893Sdim Entry.Node = Node->getOperand(i); 1043218893Sdim Entry.Ty = ArgTy; 1044218893Sdim Entry.isSExt = isSigned; 1045218893Sdim Entry.isZExt = !isSigned; 1046218893Sdim Args.push_back(Entry); 1047218893Sdim } 1048218893Sdim SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC), 1049218893Sdim TLI.getPointerTy()); 1050218893Sdim 1051226633Sdim Type *RetTy = Node->getValueType(0).getTypeForEVT(*DAG.getContext()); 1052239462Sdim TargetLowering:: 1053239462Sdim CallLoweringInfo CLI(InChain, RetTy, isSigned, !isSigned, false, false, 1054218893Sdim 0, TLI.getLibcallCallingConv(LC), /*isTailCall=*/false, 1055234353Sdim /*doesNotReturn=*/false, /*isReturnValueUsed=*/true, 1056263508Sdim Callee, Args, DAG, SDLoc(Node)); 1057239462Sdim std::pair<SDValue, SDValue> CallInfo = TLI.LowerCallTo(CLI); 1058218893Sdim 1059218893Sdim return CallInfo; 1060218893Sdim} 1061218893Sdim 1062193323Sed/// PromoteTargetBoolean - Promote the given target boolean to a target boolean 1063193323Sed/// of the given type. A target boolean is an integer value, not necessarily of 1064193323Sed/// type i1, the bits of which conform to getBooleanContents. 1065198090SrdivackySDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, EVT VT) { 1066263508Sdim SDLoc dl(Bool); 1067226633Sdim ISD::NodeType ExtendCode = 1068226633Sdim TargetLowering::getExtendForContent(TLI.getBooleanContents(VT.isVector())); 1069193323Sed return DAG.getNode(ExtendCode, dl, VT, Bool); 1070193323Sed} 1071193323Sed 1072193323Sed/// SplitInteger - Return the lower LoVT bits of Op in Lo and the upper HiVT 1073193323Sed/// bits in Hi. 1074193323Sedvoid DAGTypeLegalizer::SplitInteger(SDValue Op, 1075198090Srdivacky EVT LoVT, EVT HiVT, 1076193323Sed SDValue &Lo, SDValue &Hi) { 1077263508Sdim SDLoc dl(Op); 1078193323Sed assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() == 1079193323Sed Op.getValueType().getSizeInBits() && "Invalid integer splitting!"); 1080193323Sed Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op); 1081193323Sed Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op, 1082193323Sed DAG.getConstant(LoVT.getSizeInBits(), TLI.getPointerTy())); 1083193323Sed Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi); 1084193323Sed} 1085193323Sed 1086193323Sed/// SplitInteger - Return the lower and upper halves of Op's bits in a value 1087193323Sed/// type half the size of Op's. 1088193323Sedvoid DAGTypeLegalizer::SplitInteger(SDValue Op, 1089193323Sed SDValue &Lo, SDValue &Hi) { 1090207618Srdivacky EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), 1091207618Srdivacky Op.getValueType().getSizeInBits()/2); 1092193323Sed SplitInteger(Op, HalfVT, HalfVT, Lo, Hi); 1093193323Sed} 1094193323Sed 1095193323Sed 1096193323Sed//===----------------------------------------------------------------------===// 1097193323Sed// Entry Point 1098193323Sed//===----------------------------------------------------------------------===// 1099193323Sed 1100193323Sed/// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 1101193323Sed/// only uses types natively supported by the target. Returns "true" if it made 1102193323Sed/// any changes. 1103193323Sed/// 1104193323Sed/// Note that this is an involved process that may invalidate pointers into 1105193323Sed/// the graph. 1106193323Sedbool SelectionDAG::LegalizeTypes() { 1107193323Sed return DAGTypeLegalizer(*this).run(); 1108193323Sed} 1109