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