SelectionDAG.cpp revision 68dc3109420f38d639fb2e9fed6f1a29df60795b
1//===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This implements the SelectionDAG class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/CodeGen/SelectionDAG.h" 15#include "llvm/Constants.h" 16#include "llvm/GlobalValue.h" 17#include "llvm/Assembly/Writer.h" 18#include "llvm/CodeGen/MachineBasicBlock.h" 19#include <iostream> 20#include <set> 21#include <cmath> 22#include <algorithm> 23using namespace llvm; 24 25static bool isCommutativeBinOp(unsigned Opcode) { 26 switch (Opcode) { 27 case ISD::ADD: 28 case ISD::MUL: 29 case ISD::AND: 30 case ISD::OR: 31 case ISD::XOR: return true; 32 default: return false; // FIXME: Need commutative info for user ops! 33 } 34} 35 36static bool isAssociativeBinOp(unsigned Opcode) { 37 switch (Opcode) { 38 case ISD::ADD: 39 case ISD::MUL: 40 case ISD::AND: 41 case ISD::OR: 42 case ISD::XOR: return true; 43 default: return false; // FIXME: Need associative info for user ops! 44 } 45} 46 47static unsigned ExactLog2(uint64_t Val) { 48 unsigned Count = 0; 49 while (Val != 1) { 50 Val >>= 1; 51 ++Count; 52 } 53 return Count; 54} 55 56// isInvertibleForFree - Return true if there is no cost to emitting the logical 57// inverse of this node. 58static bool isInvertibleForFree(SDOperand N) { 59 if (isa<ConstantSDNode>(N.Val)) return true; 60 if (isa<SetCCSDNode>(N.Val) && N.Val->hasOneUse()) 61 return true; 62 return false; 63} 64 65 66/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 67/// when given the operation for (X op Y). 68ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { 69 // To perform this operation, we just need to swap the L and G bits of the 70 // operation. 71 unsigned OldL = (Operation >> 2) & 1; 72 unsigned OldG = (Operation >> 1) & 1; 73 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits 74 (OldL << 1) | // New G bit 75 (OldG << 2)); // New L bit. 76} 77 78/// getSetCCInverse - Return the operation corresponding to !(X op Y), where 79/// 'op' is a valid SetCC operation. 80ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { 81 unsigned Operation = Op; 82 if (isInteger) 83 Operation ^= 7; // Flip L, G, E bits, but not U. 84 else 85 Operation ^= 15; // Flip all of the condition bits. 86 if (Operation > ISD::SETTRUE2) 87 Operation &= ~8; // Don't let N and U bits get set. 88 return ISD::CondCode(Operation); 89} 90 91 92/// isSignedOp - For an integer comparison, return 1 if the comparison is a 93/// signed operation and 2 if the result is an unsigned comparison. Return zero 94/// if the operation does not depend on the sign of the input (setne and seteq). 95static int isSignedOp(ISD::CondCode Opcode) { 96 switch (Opcode) { 97 default: assert(0 && "Illegal integer setcc operation!"); 98 case ISD::SETEQ: 99 case ISD::SETNE: return 0; 100 case ISD::SETLT: 101 case ISD::SETLE: 102 case ISD::SETGT: 103 case ISD::SETGE: return 1; 104 case ISD::SETULT: 105 case ISD::SETULE: 106 case ISD::SETUGT: 107 case ISD::SETUGE: return 2; 108 } 109} 110 111/// getSetCCOrOperation - Return the result of a logical OR between different 112/// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function 113/// returns SETCC_INVALID if it is not possible to represent the resultant 114/// comparison. 115ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, 116 bool isInteger) { 117 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 118 // Cannot fold a signed integer setcc with an unsigned integer setcc. 119 return ISD::SETCC_INVALID; 120 121 unsigned Op = Op1 | Op2; // Combine all of the condition bits. 122 123 // If the N and U bits get set then the resultant comparison DOES suddenly 124 // care about orderedness, and is true when ordered. 125 if (Op > ISD::SETTRUE2) 126 Op &= ~16; // Clear the N bit. 127 return ISD::CondCode(Op); 128} 129 130/// getSetCCAndOperation - Return the result of a logical AND between different 131/// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 132/// function returns zero if it is not possible to represent the resultant 133/// comparison. 134ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, 135 bool isInteger) { 136 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 137 // Cannot fold a signed setcc with an unsigned setcc. 138 return ISD::SETCC_INVALID; 139 140 // Combine all of the condition bits. 141 return ISD::CondCode(Op1 & Op2); 142} 143 144/// RemoveDeadNodes - This method deletes all unreachable nodes in the 145/// SelectionDAG, including nodes (like loads) that have uses of their token 146/// chain but no other uses and no side effect. If a node is passed in as an 147/// argument, it is used as the seed for node deletion. 148void SelectionDAG::RemoveDeadNodes(SDNode *N) { 149 std::set<SDNode*> AllNodeSet(AllNodes.begin(), AllNodes.end()); 150 151 // Create a dummy node (which is not added to allnodes), that adds a reference 152 // to the root node, preventing it from being deleted. 153 SDNode *DummyNode = new SDNode(ISD::EntryToken, getRoot()); 154 155 DeleteNodeIfDead(N, &AllNodeSet); 156 157 Restart: 158 unsigned NumNodes = AllNodeSet.size(); 159 for (std::set<SDNode*>::iterator I = AllNodeSet.begin(), E = AllNodeSet.end(); 160 I != E; ++I) { 161 // Try to delete this node. 162 DeleteNodeIfDead(*I, &AllNodeSet); 163 164 // If we actually deleted any nodes, do not use invalid iterators in 165 // AllNodeSet. 166 if (AllNodeSet.size() != NumNodes) 167 goto Restart; 168 } 169 170 // Restore AllNodes. 171 if (AllNodes.size() != NumNodes) 172 AllNodes.assign(AllNodeSet.begin(), AllNodeSet.end()); 173 174 // If the root changed (e.g. it was a dead load, update the root). 175 setRoot(DummyNode->getOperand(0)); 176 177 // Now that we are done with the dummy node, delete it. 178 DummyNode->getOperand(0).Val->removeUser(DummyNode); 179 delete DummyNode; 180} 181 182void SelectionDAG::DeleteNodeIfDead(SDNode *N, void *NodeSet) { 183 if (!N->use_empty()) 184 return; 185 186 // Okay, we really are going to delete this node. First take this out of the 187 // appropriate CSE map. 188 switch (N->getOpcode()) { 189 case ISD::Constant: 190 Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(), 191 N->getValueType(0))); 192 break; 193 case ISD::ConstantFP: 194 ConstantFPs.erase(std::make_pair(cast<ConstantFPSDNode>(N)->getValue(), 195 N->getValueType(0))); 196 break; 197 case ISD::GlobalAddress: 198 GlobalValues.erase(cast<GlobalAddressSDNode>(N)->getGlobal()); 199 break; 200 case ISD::FrameIndex: 201 FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex()); 202 break; 203 case ISD::ConstantPool: 204 ConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->getIndex()); 205 break; 206 case ISD::BasicBlock: 207 BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock()); 208 break; 209 case ISD::ExternalSymbol: 210 ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 211 break; 212 213 case ISD::LOAD: 214 Loads.erase(std::make_pair(N->getOperand(1), 215 std::make_pair(N->getOperand(0), 216 N->getValueType(0)))); 217 break; 218 case ISD::SETCC: 219 SetCCs.erase(std::make_pair(std::make_pair(N->getOperand(0), 220 N->getOperand(1)), 221 cast<SetCCSDNode>(N)->getCondition())); 222 break; 223 default: 224 if (N->getNumOperands() == 1) 225 UnaryOps.erase(std::make_pair(N->getOpcode(), 226 std::make_pair(N->getOperand(0), 227 N->getValueType(0)))); 228 else if (N->getNumOperands() == 2) 229 BinaryOps.erase(std::make_pair(N->getOpcode(), 230 std::make_pair(N->getOperand(0), 231 N->getOperand(1)))); 232 break; 233 } 234 235 // Next, brutally remove the operand list. 236 while (!N->Operands.empty()) { 237 SDNode *O = N->Operands.back().Val; 238 N->Operands.pop_back(); 239 O->removeUser(N); 240 241 // Now that we removed this operand, see if there are no uses of it left. 242 DeleteNodeIfDead(O, NodeSet); 243 } 244 245 // Remove the node from the nodes set and delete it. 246 std::set<SDNode*> &AllNodeSet = *(std::set<SDNode*>*)NodeSet; 247 AllNodeSet.erase(N); 248 249 // Now that the node is gone, check to see if any of the operands of this node 250 // are dead now. 251 delete N; 252} 253 254 255SelectionDAG::~SelectionDAG() { 256 for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) 257 delete AllNodes[i]; 258} 259 260SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) { 261 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 262 // Mask out any bits that are not valid for this constant. 263 if (VT != MVT::i64) 264 Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1; 265 266 SDNode *&N = Constants[std::make_pair(Val, VT)]; 267 if (N) return SDOperand(N, 0); 268 N = new ConstantSDNode(Val, VT); 269 AllNodes.push_back(N); 270 return SDOperand(N, 0); 271} 272 273SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) { 274 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); 275 if (VT == MVT::f32) 276 Val = (float)Val; // Mask out extra precision. 277 278 SDNode *&N = ConstantFPs[std::make_pair(Val, VT)]; 279 if (N) return SDOperand(N, 0); 280 N = new ConstantFPSDNode(Val, VT); 281 AllNodes.push_back(N); 282 return SDOperand(N, 0); 283} 284 285 286 287SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, 288 MVT::ValueType VT) { 289 SDNode *&N = GlobalValues[GV]; 290 if (N) return SDOperand(N, 0); 291 N = new GlobalAddressSDNode(GV,VT); 292 AllNodes.push_back(N); 293 return SDOperand(N, 0); 294} 295 296SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) { 297 SDNode *&N = FrameIndices[FI]; 298 if (N) return SDOperand(N, 0); 299 N = new FrameIndexSDNode(FI, VT); 300 AllNodes.push_back(N); 301 return SDOperand(N, 0); 302} 303 304SDOperand SelectionDAG::getConstantPool(unsigned CPIdx, MVT::ValueType VT) { 305 SDNode *N = ConstantPoolIndices[CPIdx]; 306 if (N) return SDOperand(N, 0); 307 N = new ConstantPoolSDNode(CPIdx, VT); 308 AllNodes.push_back(N); 309 return SDOperand(N, 0); 310} 311 312SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 313 SDNode *&N = BBNodes[MBB]; 314 if (N) return SDOperand(N, 0); 315 N = new BasicBlockSDNode(MBB); 316 AllNodes.push_back(N); 317 return SDOperand(N, 0); 318} 319 320SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) { 321 SDNode *&N = ExternalSymbols[Sym]; 322 if (N) return SDOperand(N, 0); 323 N = new ExternalSymbolSDNode(Sym, VT); 324 AllNodes.push_back(N); 325 return SDOperand(N, 0); 326} 327 328SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, SDOperand N1, 329 SDOperand N2) { 330 // These setcc operations always fold. 331 switch (Cond) { 332 default: break; 333 case ISD::SETFALSE: 334 case ISD::SETFALSE2: return getConstant(0, MVT::i1); 335 case ISD::SETTRUE: 336 case ISD::SETTRUE2: return getConstant(1, MVT::i1); 337 } 338 339 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) 340 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) { 341 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); 342 343 // Sign extend the operands if required 344 if (ISD::isSignedIntSetCC(Cond)) { 345 C1 = N1C->getSignExtended(); 346 C2 = N2C->getSignExtended(); 347 } 348 349 switch (Cond) { 350 default: assert(0 && "Unknown integer setcc!"); 351 case ISD::SETEQ: return getConstant(C1 == C2, MVT::i1); 352 case ISD::SETNE: return getConstant(C1 != C2, MVT::i1); 353 case ISD::SETULT: return getConstant(C1 < C2, MVT::i1); 354 case ISD::SETUGT: return getConstant(C1 > C2, MVT::i1); 355 case ISD::SETULE: return getConstant(C1 <= C2, MVT::i1); 356 case ISD::SETUGE: return getConstant(C1 >= C2, MVT::i1); 357 case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 358 case ISD::SETGT: return getConstant((int64_t)C1 > (int64_t)C2, MVT::i1); 359 case ISD::SETLE: return getConstant((int64_t)C1 <= (int64_t)C2, MVT::i1); 360 case ISD::SETGE: return getConstant((int64_t)C1 >= (int64_t)C2, MVT::i1); 361 } 362 } else { 363 // Ensure that the constant occurs on the RHS. 364 Cond = ISD::getSetCCSwappedOperands(Cond); 365 std::swap(N1, N2); 366 } 367 368 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) 369 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) { 370 double C1 = N1C->getValue(), C2 = N2C->getValue(); 371 372 switch (Cond) { 373 default: break; // FIXME: Implement the rest of these! 374 case ISD::SETEQ: return getConstant(C1 == C2, MVT::i1); 375 case ISD::SETNE: return getConstant(C1 != C2, MVT::i1); 376 case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 377 case ISD::SETGT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 378 case ISD::SETLE: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 379 case ISD::SETGE: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 380 } 381 } else { 382 // Ensure that the constant occurs on the RHS. 383 Cond = ISD::getSetCCSwappedOperands(Cond); 384 std::swap(N1, N2); 385 } 386 387 if (N1 == N2) { 388 // We can always fold X == Y for integer setcc's. 389 if (MVT::isInteger(N1.getValueType())) 390 return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1); 391 unsigned UOF = ISD::getUnorderedFlavor(Cond); 392 if (UOF == 2) // FP operators that are undefined on NaNs. 393 return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1); 394 if (UOF == ISD::isTrueWhenEqual(Cond)) 395 return getConstant(UOF, MVT::i1); 396 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO 397 // if it is not already. 398 Cond = UOF == 0 ? ISD::SETUO : ISD::SETO; 399 } 400 401 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 402 MVT::isInteger(N1.getValueType())) { 403 if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB || 404 N1.getOpcode() == ISD::XOR) { 405 // Simplify (X+Y) == (X+Z) --> Y == Z 406 if (N1.getOpcode() == N2.getOpcode()) { 407 if (N1.getOperand(0) == N2.getOperand(0)) 408 return getSetCC(Cond, N1.getOperand(1), N2.getOperand(1)); 409 if (N1.getOperand(1) == N2.getOperand(1)) 410 return getSetCC(Cond, N1.getOperand(0), N2.getOperand(0)); 411 if (isCommutativeBinOp(N1.getOpcode())) { 412 // If X op Y == Y op X, try other combinations. 413 if (N1.getOperand(0) == N2.getOperand(1)) 414 return getSetCC(Cond, N1.getOperand(1), N2.getOperand(0)); 415 if (N1.getOperand(1) == N2.getOperand(0)) 416 return getSetCC(Cond, N1.getOperand(1), N2.getOperand(1)); 417 } 418 } 419 420 // Simplify (X+Z) == X --> Z == 0 421 if (N1.getOperand(0) == N2) 422 return getSetCC(Cond, N1.getOperand(1), 423 getConstant(0, N1.getValueType())); 424 if (N1.getOperand(1) == N2) { 425 if (isCommutativeBinOp(N1.getOpcode())) 426 return getSetCC(Cond, N1.getOperand(0), 427 getConstant(0, N1.getValueType())); 428 else { 429 assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!"); 430 // (Z-X) == X --> Z == X<<1 431 return getSetCC(Cond, N1.getOperand(0), 432 getNode(ISD::SHL, N2.getValueType(), 433 N2, getConstant(1, MVT::i8))); 434 } 435 } 436 } 437 438 if (N2.getOpcode() == ISD::ADD || N2.getOpcode() == ISD::SUB || 439 N2.getOpcode() == ISD::XOR) { 440 // Simplify X == (X+Z) --> Z == 0 441 if (N2.getOperand(0) == N1) 442 return getSetCC(Cond, N2.getOperand(1), 443 getConstant(0, N2.getValueType())); 444 else if (N2.getOperand(1) == N1) 445 return getSetCC(Cond, N2.getOperand(0), 446 getConstant(0, N2.getValueType())); 447 } 448 } 449 450 SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2), Cond)]; 451 if (N) return SDOperand(N, 0); 452 N = new SetCCSDNode(Cond, N1, N2); 453 AllNodes.push_back(N); 454 return SDOperand(N, 0); 455} 456 457 458 459/// getNode - Gets or creates the specified node. 460/// 461SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) { 462 SDNode *N = new SDNode(Opcode, VT); 463 AllNodes.push_back(N); 464 return SDOperand(N, 0); 465} 466 467static const Type *getTypeFor(MVT::ValueType VT) { 468 switch (VT) { 469 default: assert(0 && "Unknown MVT!"); 470 case MVT::i1: return Type::BoolTy; 471 case MVT::i8: return Type::UByteTy; 472 case MVT::i16: return Type::UShortTy; 473 case MVT::i32: return Type::UIntTy; 474 case MVT::i64: return Type::ULongTy; 475 case MVT::f32: return Type::FloatTy; 476 case MVT::f64: return Type::DoubleTy; 477 } 478} 479 480SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 481 SDOperand Operand) { 482 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) { 483 uint64_t Val = C->getValue(); 484 switch (Opcode) { 485 default: break; 486 case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT); 487 case ISD::ZERO_EXTEND: return getConstant(Val, VT); 488 case ISD::TRUNCATE: return getConstant(Val, VT); 489 case ISD::SINT_TO_FP: return getConstantFP(C->getSignExtended(), VT); 490 case ISD::UINT_TO_FP: return getConstantFP(C->getValue(), VT); 491 } 492 } 493 494 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) 495 switch (Opcode) { 496 case ISD::FP_ROUND: 497 case ISD::FP_EXTEND: 498 return getConstantFP(C->getValue(), VT); 499 case ISD::FP_TO_SINT: 500 return getConstant((int64_t)C->getValue(), VT); 501 case ISD::FP_TO_UINT: 502 return getConstant((uint64_t)C->getValue(), VT); 503 } 504 505 unsigned OpOpcode = Operand.Val->getOpcode(); 506 switch (Opcode) { 507 case ISD::SIGN_EXTEND: 508 if (Operand.getValueType() == VT) return Operand; // noop extension 509 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 510 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 511 break; 512 case ISD::ZERO_EXTEND: 513 if (Operand.getValueType() == VT) return Operand; // noop extension 514 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 515 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 516 break; 517 case ISD::TRUNCATE: 518 if (Operand.getValueType() == VT) return Operand; // noop truncate 519 if (OpOpcode == ISD::TRUNCATE) 520 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 521 else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) { 522 // If the source is smaller than the dest, we still need an extend. 523 if (Operand.Val->getOperand(0).getValueType() < VT) 524 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 525 else if (Operand.Val->getOperand(0).getValueType() > VT) 526 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 527 else 528 return Operand.Val->getOperand(0); 529 } 530 break; 531 } 532 533 SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))]; 534 if (N) return SDOperand(N, 0); 535 N = new SDNode(Opcode, Operand); 536 N->setValueTypes(VT); 537 AllNodes.push_back(N); 538 return SDOperand(N, 0); 539} 540 541SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 542 SDOperand N1, SDOperand N2) { 543 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 544 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 545 if (N1C) { 546 if (N2C) { 547 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); 548 switch (Opcode) { 549 case ISD::ADD: return getConstant(C1 + C2, VT); 550 case ISD::SUB: return getConstant(C1 - C2, VT); 551 case ISD::MUL: return getConstant(C1 * C2, VT); 552 case ISD::UDIV: 553 if (C2) return getConstant(C1 / C2, VT); 554 break; 555 case ISD::UREM : 556 if (C2) return getConstant(C1 % C2, VT); 557 break; 558 case ISD::SDIV : 559 if (C2) return getConstant(N1C->getSignExtended() / 560 N2C->getSignExtended(), VT); 561 break; 562 case ISD::SREM : 563 if (C2) return getConstant(N1C->getSignExtended() % 564 N2C->getSignExtended(), VT); 565 break; 566 case ISD::AND : return getConstant(C1 & C2, VT); 567 case ISD::OR : return getConstant(C1 | C2, VT); 568 case ISD::XOR : return getConstant(C1 ^ C2, VT); 569 case ISD::SHL : return getConstant(C1 << (int)C2, VT); 570 case ISD::SRL : return getConstant(C1 >> (unsigned)C2, VT); 571 case ISD::SRA : return getConstant(N1C->getSignExtended() >>(int)C2, VT); 572 default: break; 573 } 574 575 } else { // Cannonicalize constant to RHS if commutative 576 if (isCommutativeBinOp(Opcode)) { 577 std::swap(N1C, N2C); 578 std::swap(N1, N2); 579 } 580 } 581 } 582 583 if (N2C) { 584 uint64_t C2 = N2C->getValue(); 585 586 switch (Opcode) { 587 case ISD::ADD: 588 if (!C2) return N1; // add X, 0 -> X 589 break; 590 case ISD::SUB: 591 if (!C2) return N1; // sub X, 0 -> X 592 break; 593 case ISD::MUL: 594 if (!C2) return N2; // mul X, 0 -> 0 595 if (N2C->isAllOnesValue()) // mul X, -1 -> 0-X 596 return getNode(ISD::SUB, VT, getConstant(0, VT), N1); 597 598 // FIXME: This should only be done if the target supports shift 599 // operations. 600 if ((C2 & C2-1) == 0) { 601 SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8); 602 return getNode(ISD::SHL, VT, N1, ShAmt); 603 } 604 break; 605 606 case ISD::UDIV: 607 // FIXME: This should only be done if the target supports shift 608 // operations. 609 if ((C2 & C2-1) == 0 && C2) { 610 SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8); 611 return getNode(ISD::SRL, VT, N1, ShAmt); 612 } 613 break; 614 615 case ISD::AND: 616 if (!C2) return N2; // X and 0 -> 0 617 if (N2C->isAllOnesValue()) 618 return N1; // X and -1 -> X 619 break; 620 case ISD::OR: 621 if (!C2)return N1; // X or 0 -> X 622 if (N2C->isAllOnesValue()) 623 return N2; // X or -1 -> -1 624 break; 625 case ISD::XOR: 626 if (!C2) return N1; // X xor 0 -> X 627 if (N2C->isAllOnesValue()) { 628 if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N1.Val)){ 629 // !(X op Y) -> (X !op Y) 630 bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType()); 631 return getSetCC(ISD::getSetCCInverse(SetCC->getCondition(),isInteger), 632 SetCC->getOperand(0), SetCC->getOperand(1)); 633 } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) { 634 SDNode *Op = N1.Val; 635 // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible 636 // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible 637 SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1); 638 if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) { 639 LHS = getNode(ISD::XOR, VT, LHS, N2); // RHS = ~LHS 640 RHS = getNode(ISD::XOR, VT, RHS, N2); // RHS = ~RHS 641 if (Op->getOpcode() == ISD::AND) 642 return getNode(ISD::OR, VT, LHS, RHS); 643 return getNode(ISD::AND, VT, LHS, RHS); 644 } 645 } 646 // X xor -1 -> not(x) ? 647 } 648 break; 649 } 650 651 // Reassociate ((X op C1) op C2) if possible. 652 if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode)) 653 if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1))) 654 return getNode(Opcode, VT, N1.Val->getOperand(0), 655 getNode(Opcode, VT, N2, N1.Val->getOperand(1))); 656 } 657 658 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val); 659 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val); 660 if (N1CFP) 661 if (N2CFP) { 662 double C1 = N1CFP->getValue(), C2 = N2CFP->getValue(); 663 switch (Opcode) { 664 case ISD::ADD: return getConstantFP(C1 + C2, VT); 665 case ISD::SUB: return getConstantFP(C1 - C2, VT); 666 case ISD::MUL: return getConstantFP(C1 * C2, VT); 667 case ISD::SDIV: 668 if (C2) return getConstantFP(C1 / C2, VT); 669 break; 670 case ISD::SREM : 671 if (C2) return getConstantFP(fmod(C1, C2), VT); 672 break; 673 default: break; 674 } 675 676 } else { // Cannonicalize constant to RHS if commutative 677 if (isCommutativeBinOp(Opcode)) { 678 std::swap(N1CFP, N2CFP); 679 std::swap(N1, N2); 680 } 681 } 682 683 // Finally, fold operations that do not require constants. 684 switch (Opcode) { 685 case ISD::AND: 686 case ISD::OR: 687 if (SetCCSDNode *LHS = dyn_cast<SetCCSDNode>(N1.Val)) 688 if (SetCCSDNode *RHS = dyn_cast<SetCCSDNode>(N2.Val)) { 689 SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0); 690 SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1); 691 ISD::CondCode Op2 = RHS->getCondition(); 692 693 // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y) 694 if (LL == RR && LR == RL) { 695 Op2 = ISD::getSetCCSwappedOperands(Op2); 696 goto MatchedBackwards; 697 } 698 699 if (LL == RL && LR == RR) { 700 MatchedBackwards: 701 ISD::CondCode Result; 702 bool isInteger = MVT::isInteger(LL.getValueType()); 703 if (Opcode == ISD::OR) 704 Result = ISD::getSetCCOrOperation(LHS->getCondition(), Op2, 705 isInteger); 706 else 707 Result = ISD::getSetCCAndOperation(LHS->getCondition(), Op2, 708 isInteger); 709 if (Result != ISD::SETCC_INVALID) 710 return getSetCC(Result, LL, LR); 711 } 712 } 713 break; 714 case ISD::XOR: 715 if (N1 == N2) return getConstant(0, VT); // xor X, Y -> 0 716 break; 717 case ISD::SUB: 718 if (N1.getOpcode() == ISD::ADD) { 719 if (N1.Val->getOperand(0) == N2) 720 return N1.Val->getOperand(1); // (A+B)-A == B 721 if (N1.Val->getOperand(1) == N2) 722 return N1.Val->getOperand(0); // (A+B)-B == A 723 } 724 break; 725 } 726 727 SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))]; 728 if (N) return SDOperand(N, 0); 729 N = new SDNode(Opcode, N1, N2); 730 N->setValueTypes(VT); 731 732 AllNodes.push_back(N); 733 return SDOperand(N, 0); 734} 735 736SDOperand SelectionDAG::getLoad(MVT::ValueType VT, 737 SDOperand Chain, SDOperand Ptr) { 738 SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))]; 739 if (N) return SDOperand(N, 0); 740 N = new SDNode(ISD::LOAD, Chain, Ptr); 741 742 // Loads have a token chain. 743 N->setValueTypes(VT, MVT::Other); 744 AllNodes.push_back(N); 745 return SDOperand(N, 0); 746} 747 748 749SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 750 SDOperand N1, SDOperand N2, SDOperand N3) { 751 // Perform various simplifications. 752 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 753 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 754 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 755 switch (Opcode) { 756 case ISD::SELECT: 757 if (N1C) 758 if (N1C->getValue()) 759 return N2; // select true, X, Y -> X 760 else 761 return N3; // select false, X, Y -> Y 762 763 if (N2 == N3) return N2; // select C, X, X -> X 764 765 if (VT == MVT::i1) { // Boolean SELECT 766 if (N2C) { 767 if (N3C) { 768 if (N2C->getValue()) // select C, 1, 0 -> C 769 return N1; 770 return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C 771 } 772 773 if (N2C->getValue()) // select C, 1, X -> C | X 774 return getNode(ISD::OR, VT, N1, N3); 775 else // select C, 0, X -> ~C & X 776 return getNode(ISD::AND, VT, 777 getNode(ISD::XOR, N1.getValueType(), N1, 778 getConstant(1, N1.getValueType())), N3); 779 } else if (N3C) { 780 if (N3C->getValue()) // select C, X, 1 -> ~C | X 781 return getNode(ISD::OR, VT, 782 getNode(ISD::XOR, N1.getValueType(), N1, 783 getConstant(1, N1.getValueType())), N2); 784 else // select C, X, 0 -> C & X 785 return getNode(ISD::AND, VT, N1, N2); 786 } 787 } 788 789 break; 790 case ISD::BRCOND: 791 if (N2C) 792 if (N2C->getValue()) // Unconditional branch 793 return getNode(ISD::BR, MVT::Other, N1, N3); 794 else 795 return N1; // Never-taken branch 796 break; 797 } 798 799 SDNode *N = new SDNode(Opcode, N1, N2, N3); 800 switch (Opcode) { 801 default: 802 N->setValueTypes(VT); 803 break; 804 case ISD::DYNAMIC_STACKALLOC: // DYNAMIC_STACKALLOC produces pointer and chain 805 N->setValueTypes(VT, MVT::Other); 806 break; 807 } 808 809 // FIXME: memoize NODES 810 AllNodes.push_back(N); 811 return SDOperand(N, 0); 812} 813 814SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 815 std::vector<SDOperand> &Children) { 816 switch (Children.size()) { 817 case 0: return getNode(Opcode, VT); 818 case 1: return getNode(Opcode, VT, Children[0]); 819 case 2: return getNode(Opcode, VT, Children[0], Children[1]); 820 case 3: return getNode(Opcode, VT, Children[0], Children[1], Children[2]); 821 default: 822 // FIXME: MEMOIZE!! 823 SDNode *N = new SDNode(Opcode, Children); 824 N->setValueTypes(VT); 825 AllNodes.push_back(N); 826 return SDOperand(N, 0); 827 } 828} 829 830 831 832void SDNode::dump() const { 833 std::cerr << (void*)this << ": "; 834 835 for (unsigned i = 0, e = getNumValues(); i != e; ++i) { 836 if (i) std::cerr << ","; 837 switch (getValueType(i)) { 838 default: assert(0 && "Unknown value type!"); 839 case MVT::i1: std::cerr << "i1"; break; 840 case MVT::i8: std::cerr << "i8"; break; 841 case MVT::i16: std::cerr << "i16"; break; 842 case MVT::i32: std::cerr << "i32"; break; 843 case MVT::i64: std::cerr << "i64"; break; 844 case MVT::f32: std::cerr << "f32"; break; 845 case MVT::f64: std::cerr << "f64"; break; 846 case MVT::Other: std::cerr << "ch"; break; 847 } 848 } 849 std::cerr << " = "; 850 851 switch (getOpcode()) { 852 default: std::cerr << "<<Unknown>>"; break; 853 case ISD::EntryToken: std::cerr << "EntryToken"; break; 854 case ISD::Constant: std::cerr << "Constant"; break; 855 case ISD::ConstantFP: std::cerr << "ConstantFP"; break; 856 case ISD::GlobalAddress: std::cerr << "GlobalAddress"; break; 857 case ISD::FrameIndex: std::cerr << "FrameIndex"; break; 858 case ISD::BasicBlock: std::cerr << "BasicBlock"; break; 859 case ISD::ExternalSymbol: std::cerr << "ExternalSymbol"; break; 860 case ISD::ConstantPool: std::cerr << "ConstantPoolIndex"; break; 861 case ISD::CopyToReg: std::cerr << "CopyToReg"; break; 862 case ISD::CopyFromReg: std::cerr << "CopyFromReg"; break; 863 864 case ISD::ADD: std::cerr << "add"; break; 865 case ISD::SUB: std::cerr << "sub"; break; 866 case ISD::MUL: std::cerr << "mul"; break; 867 case ISD::SDIV: std::cerr << "sdiv"; break; 868 case ISD::UDIV: std::cerr << "udiv"; break; 869 case ISD::SREM: std::cerr << "srem"; break; 870 case ISD::UREM: std::cerr << "urem"; break; 871 case ISD::AND: std::cerr << "and"; break; 872 case ISD::OR: std::cerr << "or"; break; 873 case ISD::XOR: std::cerr << "xor"; break; 874 case ISD::SHL: std::cerr << "shl"; break; 875 case ISD::SRA: std::cerr << "sra"; break; 876 case ISD::SRL: std::cerr << "srl"; break; 877 878 case ISD::SETCC: std::cerr << "setcc"; break; 879 case ISD::SELECT: std::cerr << "select"; break; 880 case ISD::ADDC: std::cerr << "addc"; break; 881 case ISD::SUBB: std::cerr << "subb"; break; 882 883 // Conversion operators. 884 case ISD::SIGN_EXTEND: std::cerr << "sign_extend"; break; 885 case ISD::ZERO_EXTEND: std::cerr << "zero_extend"; break; 886 case ISD::TRUNCATE: std::cerr << "truncate"; break; 887 case ISD::FP_ROUND: std::cerr << "fp_round"; break; 888 case ISD::FP_EXTEND: std::cerr << "fp_extend"; break; 889 890 case ISD::SINT_TO_FP: std::cerr << "sint_to_fp"; break; 891 case ISD::UINT_TO_FP: std::cerr << "uint_to_fp"; break; 892 case ISD::FP_TO_SINT: std::cerr << "fp_to_sint"; break; 893 case ISD::FP_TO_UINT: std::cerr << "fp_to_uint"; break; 894 895 // Control flow instructions 896 case ISD::BR: std::cerr << "br"; break; 897 case ISD::BRCOND: std::cerr << "brcond"; break; 898 case ISD::RET: std::cerr << "ret"; break; 899 case ISD::CALL: std::cerr << "call"; break; 900 case ISD::ADJCALLSTACKDOWN: std::cerr << "adjcallstackdown"; break; 901 case ISD::ADJCALLSTACKUP: std::cerr << "adjcallstackup"; break; 902 903 // Other operators 904 case ISD::LOAD: std::cerr << "load"; break; 905 case ISD::STORE: std::cerr << "store"; break; 906 case ISD::DYNAMIC_STACKALLOC: std::cerr << "dynamic_stackalloc"; break; 907 case ISD::EXTRACT_ELEMENT: std::cerr << "extract_element"; break; 908 case ISD::BUILD_PAIR: std::cerr << "build_pair"; break; 909 } 910 911 std::cerr << " "; 912 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 913 if (i) std::cerr << ", "; 914 std::cerr << (void*)getOperand(i).Val; 915 if (unsigned RN = getOperand(i).ResNo) 916 std::cerr << ":" << RN; 917 } 918 919 if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) { 920 std::cerr << "<" << CSDN->getValue() << ">"; 921 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) { 922 std::cerr << "<" << CSDN->getValue() << ">"; 923 } else if (const GlobalAddressSDNode *GADN = 924 dyn_cast<GlobalAddressSDNode>(this)) { 925 std::cerr << "<"; 926 WriteAsOperand(std::cerr, GADN->getGlobal()) << ">"; 927 } else if (const FrameIndexSDNode *FIDN = 928 dyn_cast<FrameIndexSDNode>(this)) { 929 std::cerr << "<" << FIDN->getIndex() << ">"; 930 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){ 931 std::cerr << "<" << CP->getIndex() << ">"; 932 } else if (const BasicBlockSDNode *BBDN = 933 dyn_cast<BasicBlockSDNode>(this)) { 934 std::cerr << "<"; 935 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); 936 if (LBB) 937 std::cerr << LBB->getName() << " "; 938 std::cerr << (const void*)BBDN->getBasicBlock() << ">"; 939 } else if (const CopyRegSDNode *C2V = dyn_cast<CopyRegSDNode>(this)) { 940 std::cerr << "<reg #" << C2V->getReg() << ">"; 941 } else if (const ExternalSymbolSDNode *ES = 942 dyn_cast<ExternalSymbolSDNode>(this)) { 943 std::cerr << "'" << ES->getSymbol() << "'"; 944 } else if (const SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(this)) { 945 std::cerr << " - condition = "; 946 switch (SetCC->getCondition()) { 947 default: assert(0 && "Unknown setcc condition!"); 948 case ISD::SETOEQ: std::cerr << "setoeq"; break; 949 case ISD::SETOGT: std::cerr << "setogt"; break; 950 case ISD::SETOGE: std::cerr << "setoge"; break; 951 case ISD::SETOLT: std::cerr << "setolt"; break; 952 case ISD::SETOLE: std::cerr << "setole"; break; 953 case ISD::SETONE: std::cerr << "setone"; break; 954 955 case ISD::SETO: std::cerr << "seto"; break; 956 case ISD::SETUO: std::cerr << "setuo"; break; 957 case ISD::SETUEQ: std::cerr << "setue"; break; 958 case ISD::SETUGT: std::cerr << "setugt"; break; 959 case ISD::SETUGE: std::cerr << "setuge"; break; 960 case ISD::SETULT: std::cerr << "setult"; break; 961 case ISD::SETULE: std::cerr << "setule"; break; 962 case ISD::SETUNE: std::cerr << "setune"; break; 963 964 case ISD::SETEQ: std::cerr << "seteq"; break; 965 case ISD::SETGT: std::cerr << "setgt"; break; 966 case ISD::SETGE: std::cerr << "setge"; break; 967 case ISD::SETLT: std::cerr << "setlt"; break; 968 case ISD::SETLE: std::cerr << "setle"; break; 969 case ISD::SETNE: std::cerr << "setne"; break; 970 } 971 } 972 973} 974 975static void DumpNodes(SDNode *N, unsigned indent) { 976 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 977 if (N->getOperand(i).Val->hasOneUse()) 978 DumpNodes(N->getOperand(i).Val, indent+2); 979 else 980 std::cerr << "\n" << std::string(indent+2, ' ') 981 << (void*)N->getOperand(i).Val << ": <multiple use>"; 982 983 984 std::cerr << "\n" << std::string(indent, ' '); 985 N->dump(); 986} 987 988void SelectionDAG::dump() const { 989 std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; 990 std::vector<SDNode*> Nodes(AllNodes); 991 std::sort(Nodes.begin(), Nodes.end()); 992 993 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 994 if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val) 995 DumpNodes(Nodes[i], 2); 996 } 997 998 DumpNodes(getRoot().Val, 2); 999 1000 std::cerr << "\n\n"; 1001} 1002 1003