1 //===-- LegalizeTypes.cpp - Common code for DAG type legalizer ------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the SelectionDAG::LegalizeTypes method. It transforms 10 // an arbitrary well-formed SelectionDAG to only consist of legal types. This 11 // is common code shared among the LegalizeTypes*.cpp files. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "LegalizeTypes.h" 16 #include "llvm/ADT/SetVector.h" 17 #include "llvm/IR/DataLayout.h" 18 #include "llvm/Support/CommandLine.h" 19 #include "llvm/Support/ErrorHandling.h" 20 #include "llvm/Support/raw_ostream.h" 21 using namespace llvm; 22 23 #define DEBUG_TYPE "legalize-types" 24 25 static cl::opt<bool> 26 EnableExpensiveChecks("enable-legalize-types-checking", cl::Hidden); 27 28 /// Do extensive, expensive, basic correctness checking. 29 void DAGTypeLegalizer::PerformExpensiveChecks() { 30 // If a node is not processed, then none of its values should be mapped by any 31 // of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. 32 33 // If a node is processed, then each value with an illegal type must be mapped 34 // by exactly one of PromotedIntegers, ExpandedIntegers, ..., ReplacedValues. 35 // Values with a legal type may be mapped by ReplacedValues, but not by any of 36 // the other maps. 37 38 // Note that these invariants may not hold momentarily when processing a node: 39 // the node being processed may be put in a map before being marked Processed. 40 41 // Note that it is possible to have nodes marked NewNode in the DAG. This can 42 // occur in two ways. Firstly, a node may be created during legalization but 43 // never passed to the legalization core. This is usually due to the implicit 44 // folding that occurs when using the DAG.getNode operators. Secondly, a new 45 // node may be passed to the legalization core, but when analyzed may morph 46 // into a different node, leaving the original node as a NewNode in the DAG. 47 // A node may morph if one of its operands changes during analysis. Whether 48 // it actually morphs or not depends on whether, after updating its operands, 49 // it is equivalent to an existing node: if so, it morphs into that existing 50 // node (CSE). An operand can change during analysis if the operand is a new 51 // node that morphs, or it is a processed value that was mapped to some other 52 // value (as recorded in ReplacedValues) in which case the operand is turned 53 // into that other value. If a node morphs then the node it morphed into will 54 // be used instead of it for legalization, however the original node continues 55 // to live on in the DAG. 56 // The conclusion is that though there may be nodes marked NewNode in the DAG, 57 // all uses of such nodes are also marked NewNode: the result is a fungus of 58 // NewNodes growing on top of the useful nodes, and perhaps using them, but 59 // not used by them. 60 61 // If a value is mapped by ReplacedValues, then it must have no uses, except 62 // by nodes marked NewNode (see above). 63 64 // The final node obtained by mapping by ReplacedValues is not marked NewNode. 65 // Note that ReplacedValues should be applied iteratively. 66 67 // Note that the ReplacedValues map may also map deleted nodes (by iterating 68 // over the DAG we never dereference deleted nodes). This means that it may 69 // also map nodes marked NewNode if the deallocated memory was reallocated as 70 // another node, and that new node was not seen by the LegalizeTypes machinery 71 // (for example because it was created but not used). In general, we cannot 72 // distinguish between new nodes and deleted nodes. 73 SmallVector<SDNode*, 16> NewNodes; 74 for (SDNode &Node : DAG.allnodes()) { 75 // Remember nodes marked NewNode - they are subject to extra checking below. 76 if (Node.getNodeId() == NewNode) 77 NewNodes.push_back(&Node); 78 79 for (unsigned i = 0, e = Node.getNumValues(); i != e; ++i) { 80 SDValue Res(&Node, i); 81 bool Failed = false; 82 // Don't create a value in map. 83 auto ResId = ValueToIdMap.lookup(Res); 84 85 unsigned Mapped = 0; 86 if (ResId) { 87 auto I = ReplacedValues.find(ResId); 88 if (I != ReplacedValues.end()) { 89 Mapped |= 1; 90 // Check that remapped values are only used by nodes marked NewNode. 91 for (SDNode::use_iterator UI = Node.use_begin(), UE = Node.use_end(); 92 UI != UE; ++UI) 93 if (UI.getUse().getResNo() == i) 94 assert(UI->getNodeId() == NewNode && 95 "Remapped value has non-trivial use!"); 96 97 // Check that the final result of applying ReplacedValues is not 98 // marked NewNode. 99 auto NewValId = I->second; 100 I = ReplacedValues.find(NewValId); 101 while (I != ReplacedValues.end()) { 102 NewValId = I->second; 103 I = ReplacedValues.find(NewValId); 104 } 105 SDValue NewVal = getSDValue(NewValId); 106 (void)NewVal; 107 assert(NewVal.getNode()->getNodeId() != NewNode && 108 "ReplacedValues maps to a new node!"); 109 } 110 if (PromotedIntegers.count(ResId)) 111 Mapped |= 2; 112 if (SoftenedFloats.count(ResId)) 113 Mapped |= 4; 114 if (ScalarizedVectors.count(ResId)) 115 Mapped |= 8; 116 if (ExpandedIntegers.count(ResId)) 117 Mapped |= 16; 118 if (ExpandedFloats.count(ResId)) 119 Mapped |= 32; 120 if (SplitVectors.count(ResId)) 121 Mapped |= 64; 122 if (WidenedVectors.count(ResId)) 123 Mapped |= 128; 124 if (PromotedFloats.count(ResId)) 125 Mapped |= 256; 126 if (SoftPromotedHalfs.count(ResId)) 127 Mapped |= 512; 128 } 129 130 if (Node.getNodeId() != Processed) { 131 // Since we allow ReplacedValues to map deleted nodes, it may map nodes 132 // marked NewNode too, since a deleted node may have been reallocated as 133 // another node that has not been seen by the LegalizeTypes machinery. 134 if ((Node.getNodeId() == NewNode && Mapped > 1) || 135 (Node.getNodeId() != NewNode && Mapped != 0)) { 136 dbgs() << "Unprocessed value in a map!"; 137 Failed = true; 138 } 139 } else if (isTypeLegal(Res.getValueType()) || IgnoreNodeResults(&Node)) { 140 if (Mapped > 1) { 141 dbgs() << "Value with legal type was transformed!"; 142 Failed = true; 143 } 144 } else { 145 if (Mapped == 0) { 146 SDValue NodeById = IdToValueMap.lookup(ResId); 147 // It is possible the node has been remapped to another node and had 148 // its Id updated in the Value to Id table. The node it remapped to 149 // may not have been processed yet. Look up the Id in the Id to Value 150 // table and re-check the Processed state. If the node hasn't been 151 // remapped we'll get the same state as we got earlier. 152 if (NodeById->getNodeId() == Processed) { 153 dbgs() << "Processed value not in any map!"; 154 Failed = true; 155 } 156 } else if (Mapped & (Mapped - 1)) { 157 dbgs() << "Value in multiple maps!"; 158 Failed = true; 159 } 160 } 161 162 if (Failed) { 163 if (Mapped & 1) 164 dbgs() << " ReplacedValues"; 165 if (Mapped & 2) 166 dbgs() << " PromotedIntegers"; 167 if (Mapped & 4) 168 dbgs() << " SoftenedFloats"; 169 if (Mapped & 8) 170 dbgs() << " ScalarizedVectors"; 171 if (Mapped & 16) 172 dbgs() << " ExpandedIntegers"; 173 if (Mapped & 32) 174 dbgs() << " ExpandedFloats"; 175 if (Mapped & 64) 176 dbgs() << " SplitVectors"; 177 if (Mapped & 128) 178 dbgs() << " WidenedVectors"; 179 if (Mapped & 256) 180 dbgs() << " PromotedFloats"; 181 if (Mapped & 512) 182 dbgs() << " SoftPromoteHalfs"; 183 dbgs() << "\n"; 184 llvm_unreachable(nullptr); 185 } 186 } 187 } 188 189 #ifndef NDEBUG 190 // Checked that NewNodes are only used by other NewNodes. 191 for (unsigned i = 0, e = NewNodes.size(); i != e; ++i) { 192 SDNode *N = NewNodes[i]; 193 for (SDNode *U : N->uses()) 194 assert(U->getNodeId() == NewNode && "NewNode used by non-NewNode!"); 195 } 196 #endif 197 } 198 199 /// This is the main entry point for the type legalizer. This does a top-down 200 /// traversal of the dag, legalizing types as it goes. Returns "true" if it made 201 /// any changes. 202 bool DAGTypeLegalizer::run() { 203 bool Changed = false; 204 205 // Create a dummy node (which is not added to allnodes), that adds a reference 206 // to the root node, preventing it from being deleted, and tracking any 207 // changes of the root. 208 HandleSDNode Dummy(DAG.getRoot()); 209 Dummy.setNodeId(Unanalyzed); 210 211 // The root of the dag may dangle to deleted nodes until the type legalizer is 212 // done. Set it to null to avoid confusion. 213 DAG.setRoot(SDValue()); 214 215 // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess' 216 // (and remembering them) if they are leaves and assigning 'Unanalyzed' if 217 // non-leaves. 218 for (SDNode &Node : DAG.allnodes()) { 219 if (Node.getNumOperands() == 0) { 220 Node.setNodeId(ReadyToProcess); 221 Worklist.push_back(&Node); 222 } else { 223 Node.setNodeId(Unanalyzed); 224 } 225 } 226 227 // Now that we have a set of nodes to process, handle them all. 228 while (!Worklist.empty()) { 229 #ifndef EXPENSIVE_CHECKS 230 if (EnableExpensiveChecks) 231 #endif 232 PerformExpensiveChecks(); 233 234 SDNode *N = Worklist.pop_back_val(); 235 assert(N->getNodeId() == ReadyToProcess && 236 "Node should be ready if on worklist!"); 237 238 LLVM_DEBUG(dbgs() << "Legalizing node: "; N->dump(&DAG)); 239 if (IgnoreNodeResults(N)) { 240 LLVM_DEBUG(dbgs() << "Ignoring node results\n"); 241 goto ScanOperands; 242 } 243 244 // Scan the values produced by the node, checking to see if any result 245 // types are illegal. 246 for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) { 247 EVT ResultVT = N->getValueType(i); 248 LLVM_DEBUG(dbgs() << "Analyzing result type: " << ResultVT.getEVTString() 249 << "\n"); 250 switch (getTypeAction(ResultVT)) { 251 case TargetLowering::TypeLegal: 252 LLVM_DEBUG(dbgs() << "Legal result type\n"); 253 break; 254 case TargetLowering::TypeScalarizeScalableVector: 255 report_fatal_error( 256 "Scalarization of scalable vectors is not supported."); 257 // The following calls must take care of *all* of the node's results, 258 // not just the illegal result they were passed (this includes results 259 // with a legal type). Results can be remapped using ReplaceValueWith, 260 // or their promoted/expanded/etc values registered in PromotedIntegers, 261 // ExpandedIntegers etc. 262 case TargetLowering::TypePromoteInteger: 263 PromoteIntegerResult(N, i); 264 Changed = true; 265 goto NodeDone; 266 case TargetLowering::TypeExpandInteger: 267 ExpandIntegerResult(N, i); 268 Changed = true; 269 goto NodeDone; 270 case TargetLowering::TypeSoftenFloat: 271 SoftenFloatResult(N, i); 272 Changed = true; 273 goto NodeDone; 274 case TargetLowering::TypeExpandFloat: 275 ExpandFloatResult(N, i); 276 Changed = true; 277 goto NodeDone; 278 case TargetLowering::TypeScalarizeVector: 279 ScalarizeVectorResult(N, i); 280 Changed = true; 281 goto NodeDone; 282 case TargetLowering::TypeSplitVector: 283 SplitVectorResult(N, i); 284 Changed = true; 285 goto NodeDone; 286 case TargetLowering::TypeWidenVector: 287 WidenVectorResult(N, i); 288 Changed = true; 289 goto NodeDone; 290 case TargetLowering::TypePromoteFloat: 291 PromoteFloatResult(N, i); 292 Changed = true; 293 goto NodeDone; 294 case TargetLowering::TypeSoftPromoteHalf: 295 SoftPromoteHalfResult(N, i); 296 Changed = true; 297 goto NodeDone; 298 } 299 } 300 301 ScanOperands: 302 // Scan the operand list for the node, handling any nodes with operands that 303 // are illegal. 304 { 305 unsigned NumOperands = N->getNumOperands(); 306 bool NeedsReanalyzing = false; 307 unsigned i; 308 for (i = 0; i != NumOperands; ++i) { 309 if (IgnoreNodeResults(N->getOperand(i).getNode())) 310 continue; 311 312 const auto &Op = N->getOperand(i); 313 LLVM_DEBUG(dbgs() << "Analyzing operand: "; Op.dump(&DAG)); 314 EVT OpVT = Op.getValueType(); 315 switch (getTypeAction(OpVT)) { 316 case TargetLowering::TypeLegal: 317 LLVM_DEBUG(dbgs() << "Legal operand\n"); 318 continue; 319 case TargetLowering::TypeScalarizeScalableVector: 320 report_fatal_error( 321 "Scalarization of scalable vectors is not supported."); 322 // The following calls must either replace all of the node's results 323 // using ReplaceValueWith, and return "false"; or update the node's 324 // operands in place, and return "true". 325 case TargetLowering::TypePromoteInteger: 326 NeedsReanalyzing = PromoteIntegerOperand(N, i); 327 Changed = true; 328 break; 329 case TargetLowering::TypeExpandInteger: 330 NeedsReanalyzing = ExpandIntegerOperand(N, i); 331 Changed = true; 332 break; 333 case TargetLowering::TypeSoftenFloat: 334 NeedsReanalyzing = SoftenFloatOperand(N, i); 335 Changed = true; 336 break; 337 case TargetLowering::TypeExpandFloat: 338 NeedsReanalyzing = ExpandFloatOperand(N, i); 339 Changed = true; 340 break; 341 case TargetLowering::TypeScalarizeVector: 342 NeedsReanalyzing = ScalarizeVectorOperand(N, i); 343 Changed = true; 344 break; 345 case TargetLowering::TypeSplitVector: 346 NeedsReanalyzing = SplitVectorOperand(N, i); 347 Changed = true; 348 break; 349 case TargetLowering::TypeWidenVector: 350 NeedsReanalyzing = WidenVectorOperand(N, i); 351 Changed = true; 352 break; 353 case TargetLowering::TypePromoteFloat: 354 NeedsReanalyzing = PromoteFloatOperand(N, i); 355 Changed = true; 356 break; 357 case TargetLowering::TypeSoftPromoteHalf: 358 NeedsReanalyzing = SoftPromoteHalfOperand(N, i); 359 Changed = true; 360 break; 361 } 362 break; 363 } 364 365 // The sub-method updated N in place. Check to see if any operands are new, 366 // and if so, mark them. If the node needs revisiting, don't add all users 367 // to the worklist etc. 368 if (NeedsReanalyzing) { 369 assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); 370 371 N->setNodeId(NewNode); 372 // Recompute the NodeId and correct processed operands, adding the node to 373 // the worklist if ready. 374 SDNode *M = AnalyzeNewNode(N); 375 if (M == N) 376 // The node didn't morph - nothing special to do, it will be revisited. 377 continue; 378 379 // The node morphed - this is equivalent to legalizing by replacing every 380 // value of N with the corresponding value of M. So do that now. 381 assert(N->getNumValues() == M->getNumValues() && 382 "Node morphing changed the number of results!"); 383 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 384 // Replacing the value takes care of remapping the new value. 385 ReplaceValueWith(SDValue(N, i), SDValue(M, i)); 386 assert(N->getNodeId() == NewNode && "Unexpected node state!"); 387 // The node continues to live on as part of the NewNode fungus that 388 // grows on top of the useful nodes. Nothing more needs to be done 389 // with it - move on to the next node. 390 continue; 391 } 392 393 if (i == NumOperands) { 394 LLVM_DEBUG(dbgs() << "Legally typed node: "; N->dump(&DAG); 395 dbgs() << "\n"); 396 } 397 } 398 NodeDone: 399 400 // If we reach here, the node was processed, potentially creating new nodes. 401 // Mark it as processed and add its users to the worklist as appropriate. 402 assert(N->getNodeId() == ReadyToProcess && "Node ID recalculated?"); 403 N->setNodeId(Processed); 404 405 for (SDNode *User : N->uses()) { 406 int NodeId = User->getNodeId(); 407 408 // This node has two options: it can either be a new node or its Node ID 409 // may be a count of the number of operands it has that are not ready. 410 if (NodeId > 0) { 411 User->setNodeId(NodeId-1); 412 413 // If this was the last use it was waiting on, add it to the ready list. 414 if (NodeId-1 == ReadyToProcess) 415 Worklist.push_back(User); 416 continue; 417 } 418 419 // If this is an unreachable new node, then ignore it. If it ever becomes 420 // reachable by being used by a newly created node then it will be handled 421 // by AnalyzeNewNode. 422 if (NodeId == NewNode) 423 continue; 424 425 // Otherwise, this node is new: this is the first operand of it that 426 // became ready. Its new NodeId is the number of operands it has minus 1 427 // (as this node is now processed). 428 assert(NodeId == Unanalyzed && "Unknown node ID!"); 429 User->setNodeId(User->getNumOperands() - 1); 430 431 // If the node only has a single operand, it is now ready. 432 if (User->getNumOperands() == 1) 433 Worklist.push_back(User); 434 } 435 } 436 437 #ifndef EXPENSIVE_CHECKS 438 if (EnableExpensiveChecks) 439 #endif 440 PerformExpensiveChecks(); 441 442 // If the root changed (e.g. it was a dead load) update the root. 443 DAG.setRoot(Dummy.getValue()); 444 445 // Remove dead nodes. This is important to do for cleanliness but also before 446 // the checking loop below. Implicit folding by the DAG.getNode operators and 447 // node morphing can cause unreachable nodes to be around with their flags set 448 // to new. 449 DAG.RemoveDeadNodes(); 450 451 // In a debug build, scan all the nodes to make sure we found them all. This 452 // ensures that there are no cycles and that everything got processed. 453 #ifndef NDEBUG 454 for (SDNode &Node : DAG.allnodes()) { 455 bool Failed = false; 456 457 // Check that all result types are legal. 458 if (!IgnoreNodeResults(&Node)) 459 for (unsigned i = 0, NumVals = Node.getNumValues(); i < NumVals; ++i) 460 if (!isTypeLegal(Node.getValueType(i))) { 461 dbgs() << "Result type " << i << " illegal: "; 462 Node.dump(&DAG); 463 Failed = true; 464 } 465 466 // Check that all operand types are legal. 467 for (unsigned i = 0, NumOps = Node.getNumOperands(); i < NumOps; ++i) 468 if (!IgnoreNodeResults(Node.getOperand(i).getNode()) && 469 !isTypeLegal(Node.getOperand(i).getValueType())) { 470 dbgs() << "Operand type " << i << " illegal: "; 471 Node.getOperand(i).dump(&DAG); 472 Failed = true; 473 } 474 475 if (Node.getNodeId() != Processed) { 476 if (Node.getNodeId() == NewNode) 477 dbgs() << "New node not analyzed?\n"; 478 else if (Node.getNodeId() == Unanalyzed) 479 dbgs() << "Unanalyzed node not noticed?\n"; 480 else if (Node.getNodeId() > 0) 481 dbgs() << "Operand not processed?\n"; 482 else if (Node.getNodeId() == ReadyToProcess) 483 dbgs() << "Not added to worklist?\n"; 484 Failed = true; 485 } 486 487 if (Failed) { 488 Node.dump(&DAG); dbgs() << "\n"; 489 llvm_unreachable(nullptr); 490 } 491 } 492 #endif 493 494 return Changed; 495 } 496 497 /// The specified node is the root of a subtree of potentially new nodes. 498 /// Correct any processed operands (this may change the node) and calculate the 499 /// NodeId. If the node itself changes to a processed node, it is not remapped - 500 /// the caller needs to take care of this. Returns the potentially changed node. 501 SDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) { 502 // If this was an existing node that is already done, we're done. 503 if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed) 504 return N; 505 506 // Okay, we know that this node is new. Recursively walk all of its operands 507 // to see if they are new also. The depth of this walk is bounded by the size 508 // of the new tree that was constructed (usually 2-3 nodes), so we don't worry 509 // about revisiting of nodes. 510 // 511 // As we walk the operands, keep track of the number of nodes that are 512 // processed. If non-zero, this will become the new nodeid of this node. 513 // Operands may morph when they are analyzed. If so, the node will be 514 // updated after all operands have been analyzed. Since this is rare, 515 // the code tries to minimize overhead in the non-morphing case. 516 517 std::vector<SDValue> NewOps; 518 unsigned NumProcessed = 0; 519 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 520 SDValue OrigOp = N->getOperand(i); 521 SDValue Op = OrigOp; 522 523 AnalyzeNewValue(Op); // Op may morph. 524 525 if (Op.getNode()->getNodeId() == Processed) 526 ++NumProcessed; 527 528 if (!NewOps.empty()) { 529 // Some previous operand changed. Add this one to the list. 530 NewOps.push_back(Op); 531 } else if (Op != OrigOp) { 532 // This is the first operand to change - add all operands so far. 533 NewOps.insert(NewOps.end(), N->op_begin(), N->op_begin() + i); 534 NewOps.push_back(Op); 535 } 536 } 537 538 // Some operands changed - update the node. 539 if (!NewOps.empty()) { 540 SDNode *M = DAG.UpdateNodeOperands(N, NewOps); 541 if (M != N) { 542 // The node morphed into a different node. Normally for this to happen 543 // the original node would have to be marked NewNode. However this can 544 // in theory momentarily not be the case while ReplaceValueWith is doing 545 // its stuff. Mark the original node NewNode to help basic correctness 546 // checking. 547 N->setNodeId(NewNode); 548 if (M->getNodeId() != NewNode && M->getNodeId() != Unanalyzed) 549 // It morphed into a previously analyzed node - nothing more to do. 550 return M; 551 552 // It morphed into a different new node. Do the equivalent of passing 553 // it to AnalyzeNewNode: expunge it and calculate the NodeId. No need 554 // to remap the operands, since they are the same as the operands we 555 // remapped above. 556 N = M; 557 } 558 } 559 560 // Calculate the NodeId. 561 N->setNodeId(N->getNumOperands() - NumProcessed); 562 if (N->getNodeId() == ReadyToProcess) 563 Worklist.push_back(N); 564 565 return N; 566 } 567 568 /// Call AnalyzeNewNode, updating the node in Val if needed. 569 /// If the node changes to a processed node, then remap it. 570 void DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) { 571 Val.setNode(AnalyzeNewNode(Val.getNode())); 572 if (Val.getNode()->getNodeId() == Processed) 573 // We were passed a processed node, or it morphed into one - remap it. 574 RemapValue(Val); 575 } 576 577 /// If the specified value was already legalized to another value, 578 /// replace it by that value. 579 void DAGTypeLegalizer::RemapValue(SDValue &V) { 580 auto Id = getTableId(V); 581 V = getSDValue(Id); 582 } 583 584 void DAGTypeLegalizer::RemapId(TableId &Id) { 585 auto I = ReplacedValues.find(Id); 586 if (I != ReplacedValues.end()) { 587 assert(Id != I->second && "Id is mapped to itself."); 588 // Use path compression to speed up future lookups if values get multiply 589 // replaced with other values. 590 RemapId(I->second); 591 Id = I->second; 592 593 // Note that N = IdToValueMap[Id] it is possible to have 594 // N.getNode()->getNodeId() == NewNode at this point because it is possible 595 // for a node to be put in the map before being processed. 596 } 597 } 598 599 namespace { 600 /// This class is a DAGUpdateListener that listens for updates to nodes and 601 /// recomputes their ready state. 602 class NodeUpdateListener : public SelectionDAG::DAGUpdateListener { 603 DAGTypeLegalizer &DTL; 604 SmallSetVector<SDNode*, 16> &NodesToAnalyze; 605 public: 606 explicit NodeUpdateListener(DAGTypeLegalizer &dtl, 607 SmallSetVector<SDNode*, 16> &nta) 608 : SelectionDAG::DAGUpdateListener(dtl.getDAG()), 609 DTL(dtl), NodesToAnalyze(nta) {} 610 611 void NodeDeleted(SDNode *N, SDNode *E) override { 612 assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 613 N->getNodeId() != DAGTypeLegalizer::Processed && 614 "Invalid node ID for RAUW deletion!"); 615 // It is possible, though rare, for the deleted node N to occur as a 616 // target in a map, so note the replacement N -> E in ReplacedValues. 617 assert(E && "Node not replaced?"); 618 DTL.NoteDeletion(N, E); 619 620 // In theory the deleted node could also have been scheduled for analysis. 621 // So remove it from the set of nodes which will be analyzed. 622 NodesToAnalyze.remove(N); 623 624 // In general nothing needs to be done for E, since it didn't change but 625 // only gained new uses. However N -> E was just added to ReplacedValues, 626 // and the result of a ReplacedValues mapping is not allowed to be marked 627 // NewNode. So if E is marked NewNode, then it needs to be analyzed. 628 if (E->getNodeId() == DAGTypeLegalizer::NewNode) 629 NodesToAnalyze.insert(E); 630 } 631 632 void NodeUpdated(SDNode *N) override { 633 // Node updates can mean pretty much anything. It is possible that an 634 // operand was set to something already processed (f.e.) in which case 635 // this node could become ready. Recompute its flags. 636 assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 637 N->getNodeId() != DAGTypeLegalizer::Processed && 638 "Invalid node ID for RAUW deletion!"); 639 N->setNodeId(DAGTypeLegalizer::NewNode); 640 NodesToAnalyze.insert(N); 641 } 642 }; 643 } 644 645 646 /// The specified value was legalized to the specified other value. 647 /// Update the DAG and NodeIds replacing any uses of From to use To instead. 648 void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) { 649 assert(From.getNode() != To.getNode() && "Potential legalization loop!"); 650 651 // If expansion produced new nodes, make sure they are properly marked. 652 AnalyzeNewValue(To); 653 654 // Anything that used the old node should now use the new one. Note that this 655 // can potentially cause recursive merging. 656 SmallSetVector<SDNode*, 16> NodesToAnalyze; 657 NodeUpdateListener NUL(*this, NodesToAnalyze); 658 do { 659 660 // The old node may be present in a map like ExpandedIntegers or 661 // PromotedIntegers. Inform maps about the replacement. 662 auto FromId = getTableId(From); 663 auto ToId = getTableId(To); 664 665 if (FromId != ToId) 666 ReplacedValues[FromId] = ToId; 667 DAG.ReplaceAllUsesOfValueWith(From, To); 668 669 // Process the list of nodes that need to be reanalyzed. 670 while (!NodesToAnalyze.empty()) { 671 SDNode *N = NodesToAnalyze.pop_back_val(); 672 if (N->getNodeId() != DAGTypeLegalizer::NewNode) 673 // The node was analyzed while reanalyzing an earlier node - it is safe 674 // to skip. Note that this is not a morphing node - otherwise it would 675 // still be marked NewNode. 676 continue; 677 678 // Analyze the node's operands and recalculate the node ID. 679 SDNode *M = AnalyzeNewNode(N); 680 if (M != N) { 681 // The node morphed into a different node. Make everyone use the new 682 // node instead. 683 assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!"); 684 assert(N->getNumValues() == M->getNumValues() && 685 "Node morphing changed the number of results!"); 686 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 687 SDValue OldVal(N, i); 688 SDValue NewVal(M, i); 689 if (M->getNodeId() == Processed) 690 RemapValue(NewVal); 691 // OldVal may be a target of the ReplacedValues map which was marked 692 // NewNode to force reanalysis because it was updated. Ensure that 693 // anything that ReplacedValues mapped to OldVal will now be mapped 694 // all the way to NewVal. 695 auto OldValId = getTableId(OldVal); 696 auto NewValId = getTableId(NewVal); 697 DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal); 698 if (OldValId != NewValId) 699 ReplacedValues[OldValId] = NewValId; 700 } 701 // The original node continues to exist in the DAG, marked NewNode. 702 } 703 } 704 // When recursively update nodes with new nodes, it is possible to have 705 // new uses of From due to CSE. If this happens, replace the new uses of 706 // From with To. 707 } while (!From.use_empty()); 708 } 709 710 void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) { 711 assert(Result.getValueType() == 712 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 713 "Invalid type for promoted integer"); 714 AnalyzeNewValue(Result); 715 716 auto &OpIdEntry = PromotedIntegers[getTableId(Op)]; 717 assert((OpIdEntry == 0) && "Node is already promoted!"); 718 OpIdEntry = getTableId(Result); 719 Result->setFlags(Op->getFlags()); 720 721 DAG.transferDbgValues(Op, Result); 722 } 723 724 void DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) { 725 assert(Result.getValueType() == 726 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 727 "Invalid type for softened float"); 728 AnalyzeNewValue(Result); 729 730 auto &OpIdEntry = SoftenedFloats[getTableId(Op)]; 731 assert((OpIdEntry == 0) && "Node is already converted to integer!"); 732 OpIdEntry = getTableId(Result); 733 } 734 735 void DAGTypeLegalizer::SetPromotedFloat(SDValue Op, SDValue Result) { 736 assert(Result.getValueType() == 737 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 738 "Invalid type for promoted float"); 739 AnalyzeNewValue(Result); 740 741 auto &OpIdEntry = PromotedFloats[getTableId(Op)]; 742 assert((OpIdEntry == 0) && "Node is already promoted!"); 743 OpIdEntry = getTableId(Result); 744 } 745 746 void DAGTypeLegalizer::SetSoftPromotedHalf(SDValue Op, SDValue Result) { 747 assert(Result.getValueType() == MVT::i16 && 748 "Invalid type for soft-promoted half"); 749 AnalyzeNewValue(Result); 750 751 auto &OpIdEntry = SoftPromotedHalfs[getTableId(Op)]; 752 assert((OpIdEntry == 0) && "Node is already promoted!"); 753 OpIdEntry = getTableId(Result); 754 } 755 756 void DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) { 757 // Note that in some cases vector operation operands may be greater than 758 // the vector element type. For example BUILD_VECTOR of type <1 x i1> with 759 // a constant i8 operand. 760 761 // We don't currently support the scalarization of scalable vector types. 762 assert(Result.getValueSizeInBits().getFixedSize() >= 763 Op.getScalarValueSizeInBits() && 764 "Invalid type for scalarized vector"); 765 AnalyzeNewValue(Result); 766 767 auto &OpIdEntry = ScalarizedVectors[getTableId(Op)]; 768 assert((OpIdEntry == 0) && "Node is already scalarized!"); 769 OpIdEntry = getTableId(Result); 770 } 771 772 void DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo, 773 SDValue &Hi) { 774 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)]; 775 assert((Entry.first != 0) && "Operand isn't expanded"); 776 Lo = getSDValue(Entry.first); 777 Hi = getSDValue(Entry.second); 778 } 779 780 void DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo, 781 SDValue Hi) { 782 assert(Lo.getValueType() == 783 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 784 Hi.getValueType() == Lo.getValueType() && 785 "Invalid type for expanded integer"); 786 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 787 AnalyzeNewValue(Lo); 788 AnalyzeNewValue(Hi); 789 790 // Transfer debug values. Don't invalidate the source debug value until it's 791 // been transferred to the high and low bits. 792 if (DAG.getDataLayout().isBigEndian()) { 793 DAG.transferDbgValues(Op, Hi, 0, Hi.getValueSizeInBits(), false); 794 DAG.transferDbgValues(Op, Lo, Hi.getValueSizeInBits(), 795 Lo.getValueSizeInBits()); 796 } else { 797 DAG.transferDbgValues(Op, Lo, 0, Lo.getValueSizeInBits(), false); 798 DAG.transferDbgValues(Op, Hi, Lo.getValueSizeInBits(), 799 Hi.getValueSizeInBits()); 800 } 801 802 // Remember that this is the result of the node. 803 std::pair<TableId, TableId> &Entry = ExpandedIntegers[getTableId(Op)]; 804 assert((Entry.first == 0) && "Node already expanded"); 805 Entry.first = getTableId(Lo); 806 Entry.second = getTableId(Hi); 807 } 808 809 void DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo, 810 SDValue &Hi) { 811 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)]; 812 assert((Entry.first != 0) && "Operand isn't expanded"); 813 Lo = getSDValue(Entry.first); 814 Hi = getSDValue(Entry.second); 815 } 816 817 void DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo, 818 SDValue Hi) { 819 assert(Lo.getValueType() == 820 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 821 Hi.getValueType() == Lo.getValueType() && 822 "Invalid type for expanded float"); 823 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 824 AnalyzeNewValue(Lo); 825 AnalyzeNewValue(Hi); 826 827 std::pair<TableId, TableId> &Entry = ExpandedFloats[getTableId(Op)]; 828 assert((Entry.first == 0) && "Node already expanded"); 829 Entry.first = getTableId(Lo); 830 Entry.second = getTableId(Hi); 831 } 832 833 void DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo, 834 SDValue &Hi) { 835 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)]; 836 Lo = getSDValue(Entry.first); 837 Hi = getSDValue(Entry.second); 838 assert(Lo.getNode() && "Operand isn't split"); 839 ; 840 } 841 842 void DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo, 843 SDValue Hi) { 844 assert(Lo.getValueType().getVectorElementType() == 845 Op.getValueType().getVectorElementType() && 846 Lo.getValueType().getVectorElementCount() * 2 == 847 Op.getValueType().getVectorElementCount() && 848 Hi.getValueType() == Lo.getValueType() && 849 "Invalid type for split vector"); 850 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 851 AnalyzeNewValue(Lo); 852 AnalyzeNewValue(Hi); 853 854 // Remember that this is the result of the node. 855 std::pair<TableId, TableId> &Entry = SplitVectors[getTableId(Op)]; 856 assert((Entry.first == 0) && "Node already split"); 857 Entry.first = getTableId(Lo); 858 Entry.second = getTableId(Hi); 859 } 860 861 void DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) { 862 assert(Result.getValueType() == 863 TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType()) && 864 "Invalid type for widened vector"); 865 AnalyzeNewValue(Result); 866 867 auto &OpIdEntry = WidenedVectors[getTableId(Op)]; 868 assert((OpIdEntry == 0) && "Node already widened!"); 869 OpIdEntry = getTableId(Result); 870 } 871 872 873 //===----------------------------------------------------------------------===// 874 // Utilities. 875 //===----------------------------------------------------------------------===// 876 877 /// Convert to an integer of the same size. 878 SDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) { 879 unsigned BitWidth = Op.getValueSizeInBits(); 880 return DAG.getNode(ISD::BITCAST, SDLoc(Op), 881 EVT::getIntegerVT(*DAG.getContext(), BitWidth), Op); 882 } 883 884 /// Convert to a vector of integers of the same size. 885 SDValue DAGTypeLegalizer::BitConvertVectorToIntegerVector(SDValue Op) { 886 assert(Op.getValueType().isVector() && "Only applies to vectors!"); 887 unsigned EltWidth = Op.getScalarValueSizeInBits(); 888 EVT EltNVT = EVT::getIntegerVT(*DAG.getContext(), EltWidth); 889 auto EltCnt = Op.getValueType().getVectorElementCount(); 890 return DAG.getNode(ISD::BITCAST, SDLoc(Op), 891 EVT::getVectorVT(*DAG.getContext(), EltNVT, EltCnt), Op); 892 } 893 894 SDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op, 895 EVT DestVT) { 896 SDLoc dl(Op); 897 // Create the stack frame object. Make sure it is aligned for both 898 // the source and destination types. 899 900 // In cases where the vector is illegal it will be broken down into parts 901 // and stored in parts - we should use the alignment for the smallest part. 902 Align DestAlign = DAG.getReducedAlign(DestVT, /*UseABI=*/false); 903 Align OpAlign = DAG.getReducedAlign(Op.getValueType(), /*UseABI=*/false); 904 Align Align = std::max(DestAlign, OpAlign); 905 SDValue StackPtr = 906 DAG.CreateStackTemporary(Op.getValueType().getStoreSize(), Align); 907 // Emit a store to the stack slot. 908 SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, 909 MachinePointerInfo(), Align); 910 // Result is a load from the stack slot. 911 return DAG.getLoad(DestVT, dl, Store, StackPtr, MachinePointerInfo(), Align); 912 } 913 914 /// Replace the node's results with custom code provided by the target and 915 /// return "true", or do nothing and return "false". 916 /// The last parameter is FALSE if we are dealing with a node with legal 917 /// result types and illegal operand. The second parameter denotes the type of 918 /// illegal OperandNo in that case. 919 /// The last parameter being TRUE means we are dealing with a 920 /// node with illegal result types. The second parameter denotes the type of 921 /// illegal ResNo in that case. 922 bool DAGTypeLegalizer::CustomLowerNode(SDNode *N, EVT VT, bool LegalizeResult) { 923 // See if the target wants to custom lower this node. 924 if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) 925 return false; 926 927 SmallVector<SDValue, 8> Results; 928 if (LegalizeResult) 929 TLI.ReplaceNodeResults(N, Results, DAG); 930 else 931 TLI.LowerOperationWrapper(N, Results, DAG); 932 933 if (Results.empty()) 934 // The target didn't want to custom lower it after all. 935 return false; 936 937 // Make everything that once used N's values now use those in Results instead. 938 assert(Results.size() == N->getNumValues() && 939 "Custom lowering returned the wrong number of results!"); 940 for (unsigned i = 0, e = Results.size(); i != e; ++i) { 941 ReplaceValueWith(SDValue(N, i), Results[i]); 942 } 943 return true; 944 } 945 946 947 /// Widen the node's results with custom code provided by the target and return 948 /// "true", or do nothing and return "false". 949 bool DAGTypeLegalizer::CustomWidenLowerNode(SDNode *N, EVT VT) { 950 // See if the target wants to custom lower this node. 951 if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) 952 return false; 953 954 SmallVector<SDValue, 8> Results; 955 TLI.ReplaceNodeResults(N, Results, DAG); 956 957 if (Results.empty()) 958 // The target didn't want to custom widen lower its result after all. 959 return false; 960 961 // Update the widening map. 962 assert(Results.size() == N->getNumValues() && 963 "Custom lowering returned the wrong number of results!"); 964 for (unsigned i = 0, e = Results.size(); i != e; ++i) { 965 // If this is a chain output or already widened just replace it. 966 bool WasWidened = SDValue(N, i).getValueType() != Results[i].getValueType(); 967 if (WasWidened) 968 SetWidenedVector(SDValue(N, i), Results[i]); 969 else 970 ReplaceValueWith(SDValue(N, i), Results[i]); 971 } 972 return true; 973 } 974 975 SDValue DAGTypeLegalizer::DisintegrateMERGE_VALUES(SDNode *N, unsigned ResNo) { 976 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 977 if (i != ResNo) 978 ReplaceValueWith(SDValue(N, i), SDValue(N->getOperand(i))); 979 return SDValue(N->getOperand(ResNo)); 980 } 981 982 /// Use ISD::EXTRACT_ELEMENT nodes to extract the low and high parts of the 983 /// given value. 984 void DAGTypeLegalizer::GetPairElements(SDValue Pair, 985 SDValue &Lo, SDValue &Hi) { 986 SDLoc dl(Pair); 987 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), Pair.getValueType()); 988 Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair, 989 DAG.getIntPtrConstant(0, dl)); 990 Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, NVT, Pair, 991 DAG.getIntPtrConstant(1, dl)); 992 } 993 994 /// Build an integer with low bits Lo and high bits Hi. 995 SDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) { 996 // Arbitrarily use dlHi for result SDLoc 997 SDLoc dlHi(Hi); 998 SDLoc dlLo(Lo); 999 EVT LVT = Lo.getValueType(); 1000 EVT HVT = Hi.getValueType(); 1001 EVT NVT = EVT::getIntegerVT(*DAG.getContext(), 1002 LVT.getSizeInBits() + HVT.getSizeInBits()); 1003 1004 EVT ShiftAmtVT = TLI.getShiftAmountTy(NVT, DAG.getDataLayout(), false); 1005 Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo); 1006 Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi); 1007 Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi, 1008 DAG.getConstant(LVT.getSizeInBits(), dlHi, ShiftAmtVT)); 1009 return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi); 1010 } 1011 1012 /// Promote the given target boolean to a target boolean of the given type. 1013 /// A target boolean is an integer value, not necessarily of type i1, the bits 1014 /// of which conform to getBooleanContents. 1015 /// 1016 /// ValVT is the type of values that produced the boolean. 1017 SDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, EVT ValVT) { 1018 return TLI.promoteTargetBoolean(DAG, Bool, ValVT); 1019 } 1020 1021 /// Return the lower LoVT bits of Op in Lo and the upper HiVT bits in Hi. 1022 void DAGTypeLegalizer::SplitInteger(SDValue Op, 1023 EVT LoVT, EVT HiVT, 1024 SDValue &Lo, SDValue &Hi) { 1025 SDLoc dl(Op); 1026 assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() == 1027 Op.getValueSizeInBits() && "Invalid integer splitting!"); 1028 Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op); 1029 unsigned ReqShiftAmountInBits = 1030 Log2_32_Ceil(Op.getValueType().getSizeInBits()); 1031 MVT ShiftAmountTy = 1032 TLI.getScalarShiftAmountTy(DAG.getDataLayout(), Op.getValueType()); 1033 if (ReqShiftAmountInBits > ShiftAmountTy.getSizeInBits()) 1034 ShiftAmountTy = MVT::getIntegerVT(NextPowerOf2(ReqShiftAmountInBits)); 1035 Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op, 1036 DAG.getConstant(LoVT.getSizeInBits(), dl, ShiftAmountTy)); 1037 Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi); 1038 } 1039 1040 /// Return the lower and upper halves of Op's bits in a value type half the 1041 /// size of Op's. 1042 void DAGTypeLegalizer::SplitInteger(SDValue Op, 1043 SDValue &Lo, SDValue &Hi) { 1044 EVT HalfVT = 1045 EVT::getIntegerVT(*DAG.getContext(), Op.getValueSizeInBits() / 2); 1046 SplitInteger(Op, HalfVT, HalfVT, Lo, Hi); 1047 } 1048 1049 1050 //===----------------------------------------------------------------------===// 1051 // Entry Point 1052 //===----------------------------------------------------------------------===// 1053 1054 /// This transforms the SelectionDAG into a SelectionDAG that only uses types 1055 /// natively supported by the target. Returns "true" if it made any changes. 1056 /// 1057 /// Note that this is an involved process that may invalidate pointers into 1058 /// the graph. 1059 bool SelectionDAG::LegalizeTypes() { 1060 return DAGTypeLegalizer(*this).run(); 1061 } 1062