LegalizeTypes.cpp revision 608f7ae5f7a2268b391c372a35d4fe70920dc49b
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 LegalizeAction Action = getTypeAction(ResultVT); 72 if (Action == Promote) { 73 PromoteResult(N, i); 74 goto NodeDone; 75 } else if (Action == Expand) { 76 // Expand can mean 1) split integer in half 2) scalarize single-element 77 // vector 3) split vector in half. 78 if (!MVT::isVector(ResultVT)) 79 ExpandResult(N, i); 80 else if (MVT::getVectorNumElements(ResultVT) == 1) 81 ScalarizeResult(N, i); // Scalarize the single-element vector. 82 else 83 SplitResult(N, i); // Split the vector in half. 84 goto NodeDone; 85 } else { 86 assert(Action == Legal && "Unknown action!"); 87 } 88 } while (++i < NumResults); 89 90 // Scan the operand list for the node, handling any nodes with operands that 91 // are illegal. 92 { 93 unsigned NumOperands = N->getNumOperands(); 94 bool NeedsRevisit = false; 95 for (i = 0; i != NumOperands; ++i) { 96 MVT::ValueType OpVT = N->getOperand(i).getValueType(); 97 LegalizeAction Action = getTypeAction(OpVT); 98 if (Action == Promote) { 99 NeedsRevisit = PromoteOperand(N, i); 100 break; 101 } else if (Action == Expand) { 102 // Expand can mean 1) split integer in half 2) scalarize single-element 103 // vector 3) split vector in half. 104 if (!MVT::isVector(OpVT)) { 105 NeedsRevisit = ExpandOperand(N, i); 106 } else if (MVT::getVectorNumElements(OpVT) == 1) { 107 // Scalarize the single-element vector. 108 NeedsRevisit = ScalarizeOperand(N, i); 109 } else { 110 NeedsRevisit = SplitOperand(N, i); // Split the vector in half. 111 } 112 break; 113 } else { 114 assert(Action == Legal && "Unknown action!"); 115 } 116 } 117 118 // If the node needs revisiting, don't add all users to the worklist etc. 119 if (NeedsRevisit) 120 continue; 121 122 if (i == NumOperands) 123 DEBUG(cerr << "Legally typed node: "; N->dump(&DAG); cerr << "\n"); 124 } 125NodeDone: 126 127 // If we reach here, the node was processed, potentially creating new nodes. 128 // Mark it as processed and add its users to the worklist as appropriate. 129 N->setNodeId(Processed); 130 131 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 132 UI != E; ++UI) { 133 SDNode *User = *UI; 134 int NodeID = User->getNodeId(); 135 assert(NodeID != ReadyToProcess && NodeID != Processed && 136 "Invalid node id for user of unprocessed node!"); 137 138 // This node has two options: it can either be a new node or its Node ID 139 // may be a count of the number of operands it has that are not ready. 140 if (NodeID > 0) { 141 User->setNodeId(NodeID-1); 142 143 // If this was the last use it was waiting on, add it to the ready list. 144 if (NodeID-1 == ReadyToProcess) 145 Worklist.push_back(User); 146 continue; 147 } 148 149 // Otherwise, this node is new: this is the first operand of it that 150 // became ready. Its new NodeID is the number of operands it has minus 1 151 // (as this node is now processed). 152 assert(NodeID == NewNode && "Unknown node ID!"); 153 User->setNodeId(User->getNumOperands()-1); 154 155 // If the node only has a single operand, it is now ready. 156 if (User->getNumOperands() == 1) 157 Worklist.push_back(User); 158 } 159 } 160 161 // If the root changed (e.g. it was a dead load, update the root). 162 DAG.setRoot(Dummy.getValue()); 163 164 //DAG.viewGraph(); 165 166 // Remove dead nodes. This is important to do for cleanliness but also before 167 // the checking loop below. Implicit folding by the DAG.getNode operators can 168 // cause unreachable nodes to be around with their flags set to new. 169 DAG.RemoveDeadNodes(); 170 171 // In a debug build, scan all the nodes to make sure we found them all. This 172 // ensures that there are no cycles and that everything got processed. 173#ifndef NDEBUG 174 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 175 E = DAG.allnodes_end(); I != E; ++I) { 176 if (I->getNodeId() == Processed) 177 continue; 178 cerr << "Unprocessed node: "; 179 I->dump(&DAG); cerr << "\n"; 180 181 if (I->getNodeId() == NewNode) 182 cerr << "New node not 'noticed'?\n"; 183 else if (I->getNodeId() > 0) 184 cerr << "Operand not processed?\n"; 185 else if (I->getNodeId() == ReadyToProcess) 186 cerr << "Not added to worklist?\n"; 187 abort(); 188 } 189#endif 190} 191 192/// MarkNewNodes - The specified node is the root of a subtree of potentially 193/// new nodes. Add the correct NodeId to mark it. 194void DAGTypeLegalizer::MarkNewNodes(SDNode *N) { 195 // If this was an existing node that is already done, we're done. 196 if (N->getNodeId() != NewNode) 197 return; 198 199 // Okay, we know that this node is new. Recursively walk all of its operands 200 // to see if they are new also. The depth of this walk is bounded by the size 201 // of the new tree that was constructed (usually 2-3 nodes), so we don't worry 202 // about revisiting of nodes. 203 // 204 // As we walk the operands, keep track of the number of nodes that are 205 // processed. If non-zero, this will become the new nodeid of this node. 206 unsigned NumProcessed = 0; 207 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 208 int OpId = N->getOperand(i).Val->getNodeId(); 209 if (OpId == NewNode) 210 MarkNewNodes(N->getOperand(i).Val); 211 else if (OpId == Processed) 212 ++NumProcessed; 213 } 214 215 N->setNodeId(N->getNumOperands()-NumProcessed); 216 if (N->getNodeId() == ReadyToProcess) 217 Worklist.push_back(N); 218} 219 220namespace { 221 /// NodeUpdateListener - This class is a DAGUpdateListener that listens for 222 /// updates to nodes and recomputes their ready state. 223 class VISIBILITY_HIDDEN NodeUpdateListener : 224 public SelectionDAG::DAGUpdateListener { 225 DAGTypeLegalizer &DTL; 226 public: 227 NodeUpdateListener(DAGTypeLegalizer &dtl) : DTL(dtl) {} 228 229 virtual void NodeDeleted(SDNode *N) { 230 // Ignore deletes. 231 assert(N->getNodeId() != DAGTypeLegalizer::Processed && 232 N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 233 "RAUW deleted processed node!"); 234 } 235 236 virtual void NodeUpdated(SDNode *N) { 237 // Node updates can mean pretty much anything. It is possible that an 238 // operand was set to something already processed (f.e.) in which case 239 // this node could become ready. Recompute its flags. 240 assert(N->getNodeId() != DAGTypeLegalizer::Processed && 241 N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && 242 "RAUW updated processed node!"); 243 DTL.ReanalyzeNodeFlags(N); 244 } 245 }; 246} 247 248 249/// ReplaceValueWith - The specified value was legalized to the specified other 250/// value. If they are different, update the DAG and NodeIDs replacing any uses 251/// of From to use To instead. 252void DAGTypeLegalizer::ReplaceValueWith(SDOperand From, SDOperand To) { 253 if (From == To) return; 254 255 // If expansion produced new nodes, make sure they are properly marked. 256 if (To.Val->getNodeId() == NewNode) 257 MarkNewNodes(To.Val); 258 259 // Anything that used the old node should now use the new one. Note that this 260 // can potentially cause recursive merging. 261 NodeUpdateListener NUL(*this); 262 DAG.ReplaceAllUsesOfValueWith(From, To, &NUL); 263 264 // The old node may still be present in ExpandedNodes or PromotedNodes. 265 // Inform them about the replacement. 266 ReplacedNodes[From] = To; 267} 268 269/// ReplaceNodeWith - Replace uses of the 'from' node's results with the 'to' 270/// node's results. The from and to node must define identical result types. 271void DAGTypeLegalizer::ReplaceNodeWith(SDNode *From, SDNode *To) { 272 if (From == To) return; 273 assert(From->getNumValues() == To->getNumValues() && 274 "Node results don't match"); 275 276 // If expansion produced new nodes, make sure they are properly marked. 277 if (To->getNodeId() == NewNode) 278 MarkNewNodes(To); 279 280 // Anything that used the old node should now use the new one. Note that this 281 // can potentially cause recursive merging. 282 NodeUpdateListener NUL(*this); 283 DAG.ReplaceAllUsesWith(From, To, &NUL); 284 285 // The old node may still be present in ExpandedNodes or PromotedNodes. 286 // Inform them about the replacement. 287 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i) { 288 assert(From->getValueType(i) == To->getValueType(i) && 289 "Node results don't match"); 290 ReplacedNodes[SDOperand(From, i)] = SDOperand(To, i); 291 } 292} 293 294 295/// RemapNode - If the specified value was already legalized to another value, 296/// replace it by that value. 297void DAGTypeLegalizer::RemapNode(SDOperand &N) { 298 DenseMap<SDOperand, SDOperand>::iterator I = ReplacedNodes.find(N); 299 if (I != ReplacedNodes.end()) { 300 // Use path compression to speed up future lookups if values get multiply 301 // replaced with other values. 302 RemapNode(I->second); 303 N = I->second; 304 } 305} 306 307void DAGTypeLegalizer::SetPromotedOp(SDOperand Op, SDOperand Result) { 308 if (Result.Val->getNodeId() == NewNode) 309 MarkNewNodes(Result.Val); 310 311 SDOperand &OpEntry = PromotedNodes[Op]; 312 assert(OpEntry.Val == 0 && "Node is already promoted!"); 313 OpEntry = Result; 314} 315 316void DAGTypeLegalizer::SetScalarizedOp(SDOperand Op, SDOperand Result) { 317 if (Result.Val->getNodeId() == NewNode) 318 MarkNewNodes(Result.Val); 319 320 SDOperand &OpEntry = ScalarizedNodes[Op]; 321 assert(OpEntry.Val == 0 && "Node is already scalarized!"); 322 OpEntry = Result; 323} 324 325 326void DAGTypeLegalizer::GetExpandedOp(SDOperand Op, SDOperand &Lo, 327 SDOperand &Hi) { 328 std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op]; 329 RemapNode(Entry.first); 330 RemapNode(Entry.second); 331 assert(Entry.first.Val && "Operand isn't expanded"); 332 Lo = Entry.first; 333 Hi = Entry.second; 334} 335 336void DAGTypeLegalizer::SetExpandedOp(SDOperand Op, SDOperand Lo, SDOperand Hi) { 337 // Remember that this is the result of the node. 338 std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op]; 339 assert(Entry.first.Val == 0 && "Node already expanded"); 340 Entry.first = Lo; 341 Entry.second = Hi; 342 343 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 344 if (Lo.Val->getNodeId() == NewNode) 345 MarkNewNodes(Lo.Val); 346 if (Hi.Val->getNodeId() == NewNode) 347 MarkNewNodes(Hi.Val); 348} 349 350void DAGTypeLegalizer::GetSplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi) { 351 std::pair<SDOperand, SDOperand> &Entry = SplitNodes[Op]; 352 RemapNode(Entry.first); 353 RemapNode(Entry.second); 354 assert(Entry.first.Val && "Operand isn't split"); 355 Lo = Entry.first; 356 Hi = Entry.second; 357} 358 359void DAGTypeLegalizer::SetSplitOp(SDOperand Op, SDOperand Lo, SDOperand Hi) { 360 // Remember that this is the result of the node. 361 std::pair<SDOperand, SDOperand> &Entry = SplitNodes[Op]; 362 assert(Entry.first.Val == 0 && "Node already split"); 363 Entry.first = Lo; 364 Entry.second = Hi; 365 366 // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant. 367 if (Lo.Val->getNodeId() == NewNode) 368 MarkNewNodes(Lo.Val); 369 if (Hi.Val->getNodeId() == NewNode) 370 MarkNewNodes(Hi.Val); 371} 372 373 374SDOperand DAGTypeLegalizer::CreateStackStoreLoad(SDOperand Op, 375 MVT::ValueType DestVT) { 376 // Create the stack frame object. 377 SDOperand FIPtr = DAG.CreateStackTemporary(DestVT); 378 379 // Emit a store to the stack slot. 380 SDOperand Store = DAG.getStore(DAG.getEntryNode(), Op, FIPtr, NULL, 0); 381 // Result is a load from the stack slot. 382 return DAG.getLoad(DestVT, Store, FIPtr, NULL, 0); 383} 384 385/// HandleMemIntrinsic - This handles memcpy/memset/memmove with invalid 386/// operands. This promotes or expands the operands as required. 387SDOperand DAGTypeLegalizer::HandleMemIntrinsic(SDNode *N) { 388 // The chain and pointer [operands #0 and #1] are always valid types. 389 SDOperand Chain = N->getOperand(0); 390 SDOperand Ptr = N->getOperand(1); 391 SDOperand Op2 = N->getOperand(2); 392 393 // Op #2 is either a value (memset) or a pointer. Promote it if required. 394 switch (getTypeAction(Op2.getValueType())) { 395 default: assert(0 && "Unknown action for pointer/value operand"); 396 case Legal: break; 397 case Promote: Op2 = GetPromotedOp(Op2); break; 398 } 399 400 // The length could have any action required. 401 SDOperand Length = N->getOperand(3); 402 switch (getTypeAction(Length.getValueType())) { 403 default: assert(0 && "Unknown action for memop operand"); 404 case Legal: break; 405 case Promote: Length = GetPromotedZExtOp(Length); break; 406 case Expand: 407 SDOperand Dummy; // discard the high part. 408 GetExpandedOp(Length, Length, Dummy); 409 break; 410 } 411 412 SDOperand Align = N->getOperand(4); 413 switch (getTypeAction(Align.getValueType())) { 414 default: assert(0 && "Unknown action for memop operand"); 415 case Legal: break; 416 case Promote: Align = GetPromotedZExtOp(Align); break; 417 } 418 419 SDOperand AlwaysInline = N->getOperand(5); 420 switch (getTypeAction(AlwaysInline.getValueType())) { 421 default: assert(0 && "Unknown action for memop operand"); 422 case Legal: break; 423 case Promote: AlwaysInline = GetPromotedZExtOp(AlwaysInline); break; 424 } 425 426 SDOperand Ops[] = { Chain, Ptr, Op2, Length, Align, AlwaysInline }; 427 return DAG.UpdateNodeOperands(SDOperand(N, 0), Ops, 6); 428} 429 430/// SplitOp - Return the lower and upper halves of Op's bits in a value type 431/// half the size of Op's. 432void DAGTypeLegalizer::SplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi) { 433 unsigned NVTBits = MVT::getSizeInBits(Op.getValueType())/2; 434 assert(MVT::getSizeInBits(Op.getValueType()) == 2*NVTBits && 435 "Cannot split odd sized integer type"); 436 MVT::ValueType NVT = MVT::getIntegerType(NVTBits); 437 Lo = DAG.getNode(ISD::TRUNCATE, NVT, Op); 438 Hi = DAG.getNode(ISD::SRL, Op.getValueType(), Op, 439 DAG.getConstant(NVTBits, TLI.getShiftAmountTy())); 440 Hi = DAG.getNode(ISD::TRUNCATE, NVT, Hi); 441} 442 443 444//===----------------------------------------------------------------------===// 445// Entry Point 446//===----------------------------------------------------------------------===// 447 448/// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that 449/// only uses types natively supported by the target. 450/// 451/// Note that this is an involved process that may invalidate pointers into 452/// the graph. 453void SelectionDAG::LegalizeTypes() { 454 if (ViewLegalizeTypesDAGs) viewGraph(); 455 456 DAGTypeLegalizer(*this).run(); 457} 458