LegalizeTypes.cpp revision d8742eeb2f7cabc45a1c3736a2780bf87ba684ba
1//===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the SelectionDAG::LegalizeTypes method. It transforms 11// an arbitrary well-formed SelectionDAG to only consist of legal types. This 12// is common code shared among the LegalizeTypes*.cpp files. 13// 14//===----------------------------------------------------------------------===// 15 16#include "LegalizeTypes.h" 17#include "llvm/Constants.h" 18#include "llvm/DerivedTypes.h" 19#include "llvm/Support/CommandLine.h" 20#include "llvm/Support/MathExtras.h" 21using namespace llvm; 22 23#ifndef NDEBUG 24static cl::opt<bool> 25ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden, 26 cl::desc("Pop up a window to show dags before legalize types")); 27#else 28static const bool ViewLegalizeTypesDAGs = 0; 29#endif 30 31 32 33/// run - This is the main entry point for the type legalizer. This does a 34/// top-down traversal of the dag, legalizing types as it goes. 35void DAGTypeLegalizer::run() { 36 // Create a dummy node (which is not added to allnodes), that adds a reference 37 // to the root node, preventing it from being deleted, and tracking any 38 // changes of the root. 39 HandleSDNode Dummy(DAG.getRoot()); 40 41 // The root of the dag may dangle to deleted nodes until the type legalizer is 42 // done. Set it to null to avoid confusion. 43 DAG.setRoot(SDOperand()); 44 45 // Walk all nodes in the graph, assigning them a NodeID of 'ReadyToProcess' 46 // (and remembering them) if they are leaves and assigning 'NewNode' if 47 // non-leaves. 48 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 49 E = DAG.allnodes_end(); I != E; ++I) { 50 if (I->getNumOperands() == 0) { 51 I->setNodeId(ReadyToProcess); 52 Worklist.push_back(I); 53 } else { 54 I->setNodeId(NewNode); 55 } 56 } 57 58 // Now that we have a set of nodes to process, handle them all. 59 while (!Worklist.empty()) { 60 SDNode *N = Worklist.back(); 61 Worklist.pop_back(); 62 assert(N->getNodeId() == ReadyToProcess && 63 "Node should be ready if on worklist!"); 64 65 // Scan the values produced by the node, checking to see if any result 66 // types are illegal. 67 unsigned i = 0; 68 unsigned NumResults = N->getNumValues(); 69 do { 70 MVT::ValueType ResultVT = N->getValueType(i); 71 switch (getTypeAction(ResultVT)) { 72 default: 73 assert(false && "Unknown action!"); 74 case Legal: 75 break; 76 case Promote: 77 PromoteResult(N, i); 78 goto NodeDone; 79 case Expand: 80 ExpandResult(N, i); 81 goto NodeDone; 82 case FloatToInt: 83 FloatToIntResult(N, i); 84 goto NodeDone; 85 case Scalarize: 86 ScalarizeResult(N, i); 87 goto NodeDone; 88 case Split: 89 SplitResult(N, i); 90 goto NodeDone; 91 } 92 } while (++i < NumResults); 93 94 // Scan the operand list for the node, handling any nodes with operands that 95 // are illegal. 96 { 97 unsigned NumOperands = N->getNumOperands(); 98 bool NeedsRevisit = false; 99 for (i = 0; i != NumOperands; ++i) { 100 MVT::ValueType OpVT = N->getOperand(i).getValueType(); 101 switch (getTypeAction(OpVT)) { 102 default: 103 assert(false && "Unknown action!"); 104 case Legal: 105 continue; 106 case Promote: 107 NeedsRevisit = PromoteOperand(N, i); 108 break; 109 case Expand: 110 NeedsRevisit = ExpandOperand(N, i); 111 break; 112 case FloatToInt: 113 NeedsRevisit = FloatToIntOperand(N, i); 114 break; 115 case Scalarize: 116 NeedsRevisit = ScalarizeOperand(N, i); 117 break; 118 case Split: 119 NeedsRevisit = SplitOperand(N, i); 120 break; 121 } 122 break; 123 } 124 125 // If the node needs revisiting, don't add all users to the worklist etc. 126 if (NeedsRevisit) 127 continue; 128 129 if (i == NumOperands) 130 DEBUG(cerr << "Legally typed node: "; N->dump(&DAG); cerr << "\n"); 131 } 132NodeDone: 133 134 // If we reach here, the node was processed, potentially creating new nodes. 135 // Mark it as processed and add its users to the worklist as appropriate. 136 N->setNodeId(Processed); 137 138 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 139 UI != E; ++UI) { 140 SDNode *User = *UI; 141 int NodeID = User->getNodeId(); 142 assert(NodeID != ReadyToProcess && NodeID != Processed && 143 "Invalid node id for user of unprocessed node!"); 144 145 // This node has two options: it can either be a new node or its Node ID 146 // may be a count of the number of operands it has that are not ready. 147 if (NodeID > 0) { 148 User->setNodeId(NodeID-1); 149 150 // If this was the last use it was waiting on, add it to the ready list. 151 if (NodeID-1 == ReadyToProcess) 152 Worklist.push_back(User); 153 continue; 154 } 155 156 // Otherwise, this node is new: this is the first operand of it that 157 // became ready. Its new NodeID is the number of operands it has minus 1 158 // (as this node is now processed). 159 assert(NodeID == NewNode && "Unknown node ID!"); 160 User->setNodeId(User->getNumOperands()-1); 161 162 // If the node only has a single operand, it is now ready. 163 if (User->getNumOperands() == 1) 164 Worklist.push_back(User); 165 } 166 } 167 168 // If the root changed (e.g. it was a dead load, update the root). 169 DAG.setRoot(Dummy.getValue()); 170 171 //DAG.viewGraph(); 172 173 // Remove dead nodes. This is important to do for cleanliness but also before 174 // the checking loop below. Implicit folding by the DAG.getNode operators can 175 // cause unreachable nodes to be around with their flags set to new. 176 DAG.RemoveDeadNodes(); 177 178 // In a debug build, scan all the nodes to make sure we found them all. This 179 // ensures that there are no cycles and that everything got processed. 180#ifndef NDEBUG 181 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 182 E = DAG.allnodes_end(); I != E; ++I) { 183 bool Failed = false; 184 185 // Check that all result types are legal. 186 for (unsigned i = 0, NumVals = I->getNumValues(); i < NumVals; ++i) 187 if (!isTypeLegal(I->getValueType(i))) { 188 cerr << "Result type " << i << " illegal!\n"; 189 Failed = true; 190 } 191 192 // Check that all operand types are legal. 193 for (unsigned i = 0, NumOps = I->getNumOperands(); i < NumOps; ++i) 194 if (!isTypeLegal(I->getOperand(i).getValueType())) { 195 cerr << "Operand type " << i << " illegal!\n"; 196 Failed = true; 197 } 198 199 if (I->getNodeId() != Processed) { 200 if (I->getNodeId() == NewNode) 201 cerr << "New node not 'noticed'?\n"; 202 else if (I->getNodeId() > 0) 203 cerr << "Operand not processed?\n"; 204 else if (I->getNodeId() == ReadyToProcess) 205 cerr << "Not added to worklist?\n"; 206 Failed = true; 207 } 208 209 if (Failed) { 210 I->dump(&DAG); cerr << "\n"; 211 abort(); 212 } 213 } 214#endif 215} 216 217/// AnalyzeNewNode - The specified node is the root of a subtree of potentially 218/// new nodes. Correct any processed operands (this may change the node) and 219/// calculate the NodeId. 220void DAGTypeLegalizer::AnalyzeNewNode(SDNode *&N) { 221 // If this was an existing node that is already done, we're done. 222 if (N->getNodeId() != NewNode) 223 return; 224 225 // Okay, we know that this node is new. Recursively walk all of its operands 226 // to see if they are new also. The depth of this walk is bounded by the size 227 // of the new tree that was constructed (usually 2-3 nodes), so we don't worry 228 // about revisiting of nodes. 229 // 230 // As we walk the operands, keep track of the number of nodes that are 231 // processed. If non-zero, this will become the new nodeid of this node. 232 // Already processed operands may need to be remapped to the node that 233 // replaced them, which can result in our node changing. Since remapping 234 // is rare, the code tries to minimize overhead in the non-remapping case. 235 236 SmallVector<SDOperand, 8> NewOps; 237 unsigned NumProcessed = 0; 238 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 239 SDOperand OrigOp = N->getOperand(i); 240 SDOperand Op = OrigOp; 241 242 if (Op.Val->getNodeId() == Processed) 243 RemapNode(Op); 244 245 if (Op.Val->getNodeId() == NewNode) 246 AnalyzeNewNode(Op.Val); 247 else if (Op.Val->getNodeId() == Processed) 248 ++NumProcessed; 249 250 if (!NewOps.empty()) { 251 // Some previous operand changed. Add this one to the list. 252 NewOps.push_back(Op); 253 } else if (Op != OrigOp) { 254 // This is the first operand to change - add all operands so far. 255 for (unsigned j = 0; j < i; ++j) 256 NewOps.push_back(N->getOperand(j)); 257 NewOps.push_back(Op); 258 } 259 } 260 261 // Some operands changed - update the node. 262 if (!NewOps.empty()) 263 N = DAG.UpdateNodeOperands(SDOperand(N, 0), &NewOps[0], NewOps.size()).Val; 264 265 N->setNodeId(N->getNumOperands()-NumProcessed); 266 if (N->getNodeId() == ReadyToProcess) 267 Worklist.push_back(N); 268} 269 270namespace { 271 /// NodeUpdateListener - This class is a DAGUpdateListener that listens for 272 /// updates to nodes and recomputes their ready state. 273 class VISIBILITY_HIDDEN NodeUpdateListener : 274 public SelectionDAG::DAGUpdateListener { 275 DAGTypeLegalizer &DTL; 276 public: 277 NodeUpdateListener(DAGTypeLegalizer &dtl) : DTL(dtl) {} 278 279 virtual void NodeDeleted(SDNode *N) { 280 // Ignore deletes. 281 assert(N->getNodeId() != DAGTypeLegalizer::Processed && 282 N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 283 "RAUW deleted processed node!"); 284 } 285 286 virtual void NodeUpdated(SDNode *N) { 287 // Node updates can mean pretty much anything. It is possible that an 288 // operand was set to something already processed (f.e.) in which case 289 // this node could become ready. Recompute its flags. 290 assert(N->getNodeId() != DAGTypeLegalizer::Processed && 291 N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 292 "RAUW updated processed node!"); 293 DTL.ReanalyzeNode(N); 294 } 295 }; 296} 297 298 299/// ReplaceValueWith - The specified value was legalized to the specified other 300/// value. If they are different, update the DAG and NodeIDs replacing any uses 301/// of From to use To instead. 302void DAGTypeLegalizer::ReplaceValueWith(SDOperand From, SDOperand To) { 303 if (From == To) return; 304 305 // If expansion produced new nodes, make sure they are properly marked. 306 AnalyzeNewNode(To.Val); 307 308 // Anything that used the old node should now use the new one. Note that this 309 // can potentially cause recursive merging. 310 NodeUpdateListener NUL(*this); 311 DAG.ReplaceAllUsesOfValueWith(From, To, &NUL); 312 313 // The old node may still be present in ExpandedNodes or PromotedNodes. 314 // Inform them about the replacement. 315 ReplacedNodes[From] = To; 316} 317 318/// ReplaceNodeWith - Replace uses of the 'from' node's results with the 'to' 319/// node's results. The from and to node must define identical result types. 320void DAGTypeLegalizer::ReplaceNodeWith(SDNode *From, SDNode *To) { 321 if (From == To) return; 322 323 // If expansion produced new nodes, make sure they are properly marked. 324 AnalyzeNewNode(To); 325 326 assert(From->getNumValues() == To->getNumValues() && 327 "Node results don't match"); 328 329 // Anything that used the old node should now use the new one. Note that this 330 // can potentially cause recursive merging. 331 NodeUpdateListener NUL(*this); 332 DAG.ReplaceAllUsesWith(From, To, &NUL); 333 334 // The old node may still be present in ExpandedNodes or PromotedNodes. 335 // Inform them about the replacement. 336 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i) { 337 assert(From->getValueType(i) == To->getValueType(i) && 338 "Node results don't match"); 339 ReplacedNodes[SDOperand(From, i)] = SDOperand(To, i); 340 } 341} 342 343 344/// RemapNode - If the specified value was already legalized to another value, 345/// replace it by that value. 346void DAGTypeLegalizer::RemapNode(SDOperand &N) { 347 DenseMap<SDOperand, SDOperand>::iterator I = ReplacedNodes.find(N); 348 if (I != ReplacedNodes.end()) { 349 // Use path compression to speed up future lookups if values get multiply 350 // replaced with other values. 351 RemapNode(I->second); 352 N = I->second; 353 } 354} 355 356void DAGTypeLegalizer::SetPromotedOp(SDOperand Op, SDOperand Result) { 357 AnalyzeNewNode(Result.Val); 358 359 SDOperand &OpEntry = PromotedNodes[Op]; 360 assert(OpEntry.Val == 0 && "Node is already promoted!"); 361 OpEntry = Result; 362} 363 364void DAGTypeLegalizer::SetIntegerOp(SDOperand Op, SDOperand Result) { 365 AnalyzeNewNode(Result.Val); 366 367 SDOperand &OpEntry = FloatToIntedNodes[Op]; 368 assert(OpEntry.Val == 0 && "Node is already converted to integer!"); 369 OpEntry = Result; 370} 371 372void DAGTypeLegalizer::SetScalarizedOp(SDOperand Op, SDOperand Result) { 373 AnalyzeNewNode(Result.Val); 374 375 SDOperand &OpEntry = ScalarizedNodes[Op]; 376 assert(OpEntry.Val == 0 && "Node is already scalarized!"); 377 OpEntry = Result; 378} 379 380void DAGTypeLegalizer::GetExpandedOp(SDOperand Op, SDOperand &Lo, 381 SDOperand &Hi) { 382 std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op]; 383 RemapNode(Entry.first); 384 RemapNode(Entry.second); 385 assert(Entry.first.Val && "Operand isn't expanded"); 386 Lo = Entry.first; 387 Hi = Entry.second; 388} 389 390void DAGTypeLegalizer::SetExpandedOp(SDOperand Op, SDOperand Lo, SDOperand Hi) { 391 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 392 AnalyzeNewNode(Lo.Val); 393 AnalyzeNewNode(Hi.Val); 394 395 // Remember that this is the result of the node. 396 std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op]; 397 assert(Entry.first.Val == 0 && "Node already expanded"); 398 Entry.first = Lo; 399 Entry.second = Hi; 400} 401 402void DAGTypeLegalizer::GetSplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi) { 403 std::pair<SDOperand, SDOperand> &Entry = SplitNodes[Op]; 404 RemapNode(Entry.first); 405 RemapNode(Entry.second); 406 assert(Entry.first.Val && "Operand isn't split"); 407 Lo = Entry.first; 408 Hi = Entry.second; 409} 410 411void DAGTypeLegalizer::SetSplitOp(SDOperand Op, SDOperand Lo, SDOperand Hi) { 412 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 413 AnalyzeNewNode(Lo.Val); 414 AnalyzeNewNode(Hi.Val); 415 416 // Remember that this is the result of the node. 417 std::pair<SDOperand, SDOperand> &Entry = SplitNodes[Op]; 418 assert(Entry.first.Val == 0 && "Node already split"); 419 Entry.first = Lo; 420 Entry.second = Hi; 421} 422 423 424/// BitConvertToInteger - Convert to an integer of the same size. 425SDOperand DAGTypeLegalizer::BitConvertToInteger(SDOperand Op) { 426 return DAG.getNode(ISD::BIT_CONVERT, 427 MVT::getIntegerType(MVT::getSizeInBits(Op.getValueType())), 428 Op); 429} 430 431SDOperand DAGTypeLegalizer::CreateStackStoreLoad(SDOperand Op, 432 MVT::ValueType DestVT) { 433 // Create the stack frame object. 434 SDOperand FIPtr = DAG.CreateStackTemporary(DestVT); 435 436 // Emit a store to the stack slot. 437 SDOperand Store = DAG.getStore(DAG.getEntryNode(), Op, FIPtr, NULL, 0); 438 // Result is a load from the stack slot. 439 return DAG.getLoad(DestVT, Store, FIPtr, NULL, 0); 440} 441 442/// HandleMemIntrinsic - This handles memcpy/memset/memmove with invalid 443/// operands. This promotes or expands the operands as required. 444SDOperand DAGTypeLegalizer::HandleMemIntrinsic(SDNode *N) { 445 // The chain and pointer [operands #0 and #1] are always valid types. 446 SDOperand Chain = N->getOperand(0); 447 SDOperand Ptr = N->getOperand(1); 448 SDOperand Op2 = N->getOperand(2); 449 450 // Op #2 is either a value (memset) or a pointer. Promote it if required. 451 switch (getTypeAction(Op2.getValueType())) { 452 default: assert(0 && "Unknown action for pointer/value operand"); 453 case Legal: break; 454 case Promote: Op2 = GetPromotedOp(Op2); break; 455 } 456 457 // The length could have any action required. 458 SDOperand Length = N->getOperand(3); 459 switch (getTypeAction(Length.getValueType())) { 460 default: assert(0 && "Unknown action for memop operand"); 461 case Legal: break; 462 case Promote: Length = GetPromotedZExtOp(Length); break; 463 case Expand: 464 SDOperand Dummy; // discard the high part. 465 GetExpandedOp(Length, Length, Dummy); 466 break; 467 } 468 469 SDOperand Align = N->getOperand(4); 470 switch (getTypeAction(Align.getValueType())) { 471 default: assert(0 && "Unknown action for memop operand"); 472 case Legal: break; 473 case Promote: Align = GetPromotedZExtOp(Align); break; 474 } 475 476 SDOperand AlwaysInline = N->getOperand(5); 477 switch (getTypeAction(AlwaysInline.getValueType())) { 478 default: assert(0 && "Unknown action for memop operand"); 479 case Legal: break; 480 case Promote: AlwaysInline = GetPromotedZExtOp(AlwaysInline); break; 481 } 482 483 SDOperand Ops[] = { Chain, Ptr, Op2, Length, Align, AlwaysInline }; 484 return DAG.UpdateNodeOperands(SDOperand(N, 0), Ops, 6); 485} 486 487/// JoinIntegers - Build an integer with low bits Lo and high bits Hi. 488SDOperand DAGTypeLegalizer::JoinIntegers(SDOperand Lo, SDOperand Hi) { 489 MVT::ValueType LVT = Lo.getValueType(); 490 MVT::ValueType HVT = Hi.getValueType(); 491 MVT::ValueType NVT = MVT::getIntegerType(MVT::getSizeInBits(LVT) + 492 MVT::getSizeInBits(HVT)); 493 494 Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, Lo); 495 Hi = DAG.getNode(ISD::ANY_EXTEND, NVT, Hi); 496 Hi = DAG.getNode(ISD::SHL, NVT, Hi, DAG.getConstant(MVT::getSizeInBits(LVT), 497 TLI.getShiftAmountTy())); 498 return DAG.getNode(ISD::OR, NVT, Lo, Hi); 499} 500 501/// SplitInteger - Return the lower LoVT bits of Op in Lo and the upper HiVT 502/// bits in Hi. 503void DAGTypeLegalizer::SplitInteger(SDOperand Op, 504 MVT::ValueType LoVT, MVT::ValueType HiVT, 505 SDOperand &Lo, SDOperand &Hi) { 506 assert(MVT::getSizeInBits(LoVT) + MVT::getSizeInBits(HiVT) == 507 MVT::getSizeInBits(Op.getValueType()) && "Invalid integer splitting!"); 508 Lo = DAG.getNode(ISD::TRUNCATE, LoVT, Op); 509 Hi = DAG.getNode(ISD::SRL, Op.getValueType(), Op, 510 DAG.getConstant(MVT::getSizeInBits(LoVT), 511 TLI.getShiftAmountTy())); 512 Hi = DAG.getNode(ISD::TRUNCATE, HiVT, Hi); 513} 514 515/// SplitInteger - Return the lower and upper halves of Op's bits in a value type 516/// half the size of Op's. 517void DAGTypeLegalizer::SplitInteger(SDOperand Op, 518 SDOperand &Lo, SDOperand &Hi) { 519 MVT::ValueType HalfVT = 520 MVT::getIntegerType(MVT::getSizeInBits(Op.getValueType())/2); 521 SplitInteger(Op, HalfVT, HalfVT, Lo, Hi); 522} 523 524//===----------------------------------------------------------------------===// 525// Entry Point 526//===----------------------------------------------------------------------===// 527 528/// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 529/// only uses types natively supported by the target. 530/// 531/// Note that this is an involved process that may invalidate pointers into 532/// the graph. 533void SelectionDAG::LegalizeTypes() { 534 if (ViewLegalizeTypesDAGs) viewGraph(); 535 536 DAGTypeLegalizer(*this).run(); 537} 538