1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
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"
25 static bool isCommutativeBinOp(unsigned Opcode) {
31 case ISD::XOR: return true;
32 default: return false; // FIXME: Need commutative info for user ops!
36 static bool isAssociativeBinOp(unsigned Opcode) {
42 case ISD::XOR: return true;
43 default: return false; // FIXME: Need associative info for user ops!
47 static unsigned ExactLog2(uint64_t Val) {
56 // isInvertibleForFree - Return true if there is no cost to emitting the logical
57 // inverse of this node.
58 static bool isInvertibleForFree(SDOperand N) {
59 if (isa<ConstantSDNode>(N.Val)) return true;
60 if (isa<SetCCSDNode>(N.Val) && N.Val->hasOneUse())
66 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
67 /// when given the operation for (X op Y).
68 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
69 // To perform this operation, we just need to swap the L and G bits of the
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.
78 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
79 /// 'op' is a valid SetCC operation.
80 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
81 unsigned Operation = Op;
83 Operation ^= 7; // Flip L, G, E bits, but not U.
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);
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).
95 static int isSignedOp(ISD::CondCode Opcode) {
97 default: assert(0 && "Illegal integer setcc operation!");
99 case ISD::SETNE: return 0;
103 case ISD::SETGE: return 1;
107 case ISD::SETUGE: return 2;
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
115 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
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;
121 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
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);
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
134 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
136 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
137 // Cannot fold a signed setcc with an unsigned setcc.
138 return ISD::SETCC_INVALID;
140 // Combine all of the condition bits.
141 return ISD::CondCode(Op1 & Op2);
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.
148 void SelectionDAG::RemoveDeadNodes(SDNode *N) {
149 std::set<SDNode*> AllNodeSet(AllNodes.begin(), AllNodes.end());
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());
155 DeleteNodeIfDead(N, &AllNodeSet);
158 unsigned NumNodes = AllNodeSet.size();
159 for (std::set<SDNode*>::iterator I = AllNodeSet.begin(), E = AllNodeSet.end();
161 // Try to delete this node.
162 DeleteNodeIfDead(*I, &AllNodeSet);
164 // If we actually deleted any nodes, do not use invalid iterators in
166 if (AllNodeSet.size() != NumNodes)
171 if (AllNodes.size() != NumNodes)
172 AllNodes.assign(AllNodeSet.begin(), AllNodeSet.end());
174 // If the root changed (e.g. it was a dead load, update the root).
175 setRoot(DummyNode->getOperand(0));
177 // Now that we are done with the dummy node, delete it.
178 DummyNode->getOperand(0).Val->removeUser(DummyNode);
182 void SelectionDAG::DeleteNodeIfDead(SDNode *N, void *NodeSet) {
186 // Okay, we really are going to delete this node. First take this out of the
187 // appropriate CSE map.
188 switch (N->getOpcode()) {
190 Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(),
191 N->getValueType(0)));
193 case ISD::ConstantFP:
194 ConstantFPs.erase(std::make_pair(cast<ConstantFPSDNode>(N)->getValue(),
195 N->getValueType(0)));
197 case ISD::GlobalAddress:
198 GlobalValues.erase(cast<GlobalAddressSDNode>(N)->getGlobal());
200 case ISD::FrameIndex:
201 FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
203 case ISD::ConstantPool:
204 ConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->getIndex());
206 case ISD::BasicBlock:
207 BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock());
209 case ISD::ExternalSymbol:
210 ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
214 Loads.erase(std::make_pair(N->getOperand(1),
215 std::make_pair(N->getOperand(0),
216 N->getValueType(0))));
219 SetCCs.erase(std::make_pair(std::make_pair(N->getOperand(0),
221 cast<SetCCSDNode>(N)->getCondition()));
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),
235 // Next, brutally remove the operand list.
236 while (!N->Operands.empty()) {
237 SDNode *O = N->Operands.back().Val;
238 N->Operands.pop_back();
241 // Now that we removed this operand, see if there are no uses of it left.
242 DeleteNodeIfDead(O, NodeSet);
245 // Remove the node from the nodes set and delete it.
246 std::set<SDNode*> &AllNodeSet = *(std::set<SDNode*>*)NodeSet;
249 // Now that the node is gone, check to see if any of the operands of this node
255 SelectionDAG::~SelectionDAG() {
256 for (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
260 SDOperand 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.
264 Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
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);
273 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) {
274 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
276 Val = (float)Val; // Mask out extra precision.
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);
287 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
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);
296 SDOperand 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);
304 SDOperand 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);
312 SDOperand 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);
320 SDOperand 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);
328 SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, SDOperand N1,
330 // These setcc operations always fold.
334 case ISD::SETFALSE2: return getConstant(0, MVT::i1);
336 case ISD::SETTRUE2: return getConstant(1, MVT::i1);
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();
343 // Sign extend the operands if required
344 if (ISD::isSignedIntSetCC(Cond)) {
345 C1 = N1C->getSignExtended();
346 C2 = N2C->getSignExtended();
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);
363 // Ensure that the constant occurs on the RHS.
364 Cond = ISD::getSetCCSwappedOperands(Cond);
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();
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);
382 // Ensure that the constant occurs on the RHS.
383 Cond = ISD::getSetCCSwappedOperands(Cond);
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;
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));
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()));
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)));
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()));
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);
459 /// getNode - Gets or creates the specified node.
461 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
462 SDNode *N = new SDNode(Opcode, VT);
463 AllNodes.push_back(N);
464 return SDOperand(N, 0);
467 static const Type *getTypeFor(MVT::ValueType 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;
480 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
482 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
483 uint64_t Val = C->getValue();
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);
494 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
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);
505 unsigned OpOpcode = Operand.Val->getOpcode();
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));
512 case ISD::ZERO_EXTEND:
513 if (Operand.getValueType() == VT) return Operand; // noop extension
514 if (OpOpcode == ISD::ZERO_EXTEND)
515 return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
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));
528 return Operand.Val->getOperand(0);
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);
541 SDOperand 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);
547 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
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);
553 if (C2) return getConstant(C1 / C2, VT);
556 if (C2) return getConstant(C1 % C2, VT);
559 if (C2) return getConstant(N1C->getSignExtended() /
560 N2C->getSignExtended(), VT);
563 if (C2) return getConstant(N1C->getSignExtended() %
564 N2C->getSignExtended(), VT);
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);
575 } else { // Cannonicalize constant to RHS if commutative
576 if (isCommutativeBinOp(Opcode)) {
584 uint64_t C2 = N2C->getValue();
588 if (!C2) return N1; // add X, 0 -> X
591 if (!C2) return N1; // sub X, 0 -> X
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);
598 // FIXME: This should only be done if the target supports shift
600 if ((C2 & C2-1) == 0) {
601 SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
602 return getNode(ISD::SHL, VT, N1, ShAmt);
607 // FIXME: This should only be done if the target supports shift
609 if ((C2 & C2-1) == 0 && C2) {
610 SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
611 return getNode(ISD::SRL, VT, N1, ShAmt);
618 if (C2 == 0) return N1;
622 if (!C2) return N2; // X and 0 -> 0
623 if (N2C->isAllOnesValue())
624 return N1; // X and -1 -> X
627 if (!C2)return N1; // X or 0 -> X
628 if (N2C->isAllOnesValue())
629 return N2; // X or -1 -> -1
632 if (!C2) return N1; // X xor 0 -> X
633 if (N2C->isAllOnesValue()) {
634 if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N1.Val)){
635 // !(X op Y) -> (X !op Y)
636 bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
637 return getSetCC(ISD::getSetCCInverse(SetCC->getCondition(),isInteger),
638 SetCC->getOperand(0), SetCC->getOperand(1));
639 } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) {
641 // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible
642 // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible
643 SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1);
644 if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) {
645 LHS = getNode(ISD::XOR, VT, LHS, N2); // RHS = ~LHS
646 RHS = getNode(ISD::XOR, VT, RHS, N2); // RHS = ~RHS
647 if (Op->getOpcode() == ISD::AND)
648 return getNode(ISD::OR, VT, LHS, RHS);
649 return getNode(ISD::AND, VT, LHS, RHS);
652 // X xor -1 -> not(x) ?
657 // Reassociate ((X op C1) op C2) if possible.
658 if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode))
659 if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1)))
660 return getNode(Opcode, VT, N1.Val->getOperand(0),
661 getNode(Opcode, VT, N2, N1.Val->getOperand(1)));
664 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
665 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
668 double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
670 case ISD::ADD: return getConstantFP(C1 + C2, VT);
671 case ISD::SUB: return getConstantFP(C1 - C2, VT);
672 case ISD::MUL: return getConstantFP(C1 * C2, VT);
674 if (C2) return getConstantFP(C1 / C2, VT);
677 if (C2) return getConstantFP(fmod(C1, C2), VT);
682 } else { // Cannonicalize constant to RHS if commutative
683 if (isCommutativeBinOp(Opcode)) {
684 std::swap(N1CFP, N2CFP);
689 // Finally, fold operations that do not require constants.
693 if (SetCCSDNode *LHS = dyn_cast<SetCCSDNode>(N1.Val))
694 if (SetCCSDNode *RHS = dyn_cast<SetCCSDNode>(N2.Val)) {
695 SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0);
696 SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1);
697 ISD::CondCode Op2 = RHS->getCondition();
699 // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y)
700 if (LL == RR && LR == RL) {
701 Op2 = ISD::getSetCCSwappedOperands(Op2);
702 goto MatchedBackwards;
705 if (LL == RL && LR == RR) {
707 ISD::CondCode Result;
708 bool isInteger = MVT::isInteger(LL.getValueType());
709 if (Opcode == ISD::OR)
710 Result = ISD::getSetCCOrOperation(LHS->getCondition(), Op2,
713 Result = ISD::getSetCCAndOperation(LHS->getCondition(), Op2,
715 if (Result != ISD::SETCC_INVALID)
716 return getSetCC(Result, LL, LR);
721 if (N1 == N2) return getConstant(0, VT); // xor X, Y -> 0
724 if (N1.getOpcode() == ISD::ADD) {
725 if (N1.Val->getOperand(0) == N2)
726 return N1.Val->getOperand(1); // (A+B)-A == B
727 if (N1.Val->getOperand(1) == N2)
728 return N1.Val->getOperand(0); // (A+B)-B == A
733 SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))];
734 if (N) return SDOperand(N, 0);
735 N = new SDNode(Opcode, N1, N2);
736 N->setValueTypes(VT);
738 AllNodes.push_back(N);
739 return SDOperand(N, 0);
742 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
743 SDOperand Chain, SDOperand Ptr) {
744 SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))];
745 if (N) return SDOperand(N, 0);
746 N = new SDNode(ISD::LOAD, Chain, Ptr);
748 // Loads have a token chain.
749 N->setValueTypes(VT, MVT::Other);
750 AllNodes.push_back(N);
751 return SDOperand(N, 0);
755 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
756 SDOperand N1, SDOperand N2, SDOperand N3) {
757 // Perform various simplifications.
758 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
759 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
760 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
765 return N2; // select true, X, Y -> X
767 return N3; // select false, X, Y -> Y
769 if (N2 == N3) return N2; // select C, X, X -> X
771 if (VT == MVT::i1) { // Boolean SELECT
774 if (N2C->getValue()) // select C, 1, 0 -> C
776 return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C
779 if (N2C->getValue()) // select C, 1, X -> C | X
780 return getNode(ISD::OR, VT, N1, N3);
781 else // select C, 0, X -> ~C & X
782 return getNode(ISD::AND, VT,
783 getNode(ISD::XOR, N1.getValueType(), N1,
784 getConstant(1, N1.getValueType())), N3);
786 if (N3C->getValue()) // select C, X, 1 -> ~C | X
787 return getNode(ISD::OR, VT,
788 getNode(ISD::XOR, N1.getValueType(), N1,
789 getConstant(1, N1.getValueType())), N2);
790 else // select C, X, 0 -> C & X
791 return getNode(ISD::AND, VT, N1, N2);
798 if (N2C->getValue()) // Unconditional branch
799 return getNode(ISD::BR, MVT::Other, N1, N3);
801 return N1; // Never-taken branch
805 SDNode *N = new SDNode(Opcode, N1, N2, N3);
808 N->setValueTypes(VT);
810 case ISD::DYNAMIC_STACKALLOC: // DYNAMIC_STACKALLOC produces pointer and chain
811 N->setValueTypes(VT, MVT::Other);
815 // FIXME: memoize NODES
816 AllNodes.push_back(N);
817 return SDOperand(N, 0);
820 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
821 std::vector<SDOperand> &Children) {
822 switch (Children.size()) {
823 case 0: return getNode(Opcode, VT);
824 case 1: return getNode(Opcode, VT, Children[0]);
825 case 2: return getNode(Opcode, VT, Children[0], Children[1]);
826 case 3: return getNode(Opcode, VT, Children[0], Children[1], Children[2]);
829 SDNode *N = new SDNode(Opcode, Children);
830 N->setValueTypes(VT);
831 AllNodes.push_back(N);
832 return SDOperand(N, 0);
836 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
837 /// indicated value. This method ignores uses of other values defined by this
839 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) {
840 assert(Value < getNumValues() && "Bad value!");
842 // If there is only one value, this is easy.
843 if (getNumValues() == 1)
844 return use_size() == NUses;
845 if (Uses.size() < NUses) return false;
847 SDOperand TheValue(this, Value);
849 std::set<SDNode*> UsersHandled;
851 for (std::vector<SDNode*>::iterator UI = Uses.begin(), E = Uses.end();
854 if (User->getNumOperands() == 1 ||
855 UsersHandled.insert(User).second) // First time we've seen this?
856 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
857 if (User->getOperand(i) == TheValue) {
859 return false; // too many uses
864 // Found exactly the right number of uses?
869 const char *SDNode::getOperationName() const {
870 switch (getOpcode()) {
871 default: return "<<Unknown>>";
872 case ISD::EntryToken: return "EntryToken";
873 case ISD::TokenFactor: return "TokenFactor";
874 case ISD::Constant: return "Constant";
875 case ISD::ConstantFP: return "ConstantFP";
876 case ISD::GlobalAddress: return "GlobalAddress";
877 case ISD::FrameIndex: return "FrameIndex";
878 case ISD::BasicBlock: return "BasicBlock";
879 case ISD::ExternalSymbol: return "ExternalSymbol";
880 case ISD::ConstantPool: return "ConstantPoolIndex";
881 case ISD::CopyToReg: return "CopyToReg";
882 case ISD::CopyFromReg: return "CopyFromReg";
883 case ISD::ImplicitDef: return "ImplicitDef";
885 case ISD::ADD: return "add";
886 case ISD::SUB: return "sub";
887 case ISD::MUL: return "mul";
888 case ISD::SDIV: return "sdiv";
889 case ISD::UDIV: return "udiv";
890 case ISD::SREM: return "srem";
891 case ISD::UREM: return "urem";
892 case ISD::AND: return "and";
893 case ISD::OR: return "or";
894 case ISD::XOR: return "xor";
895 case ISD::SHL: return "shl";
896 case ISD::SRA: return "sra";
897 case ISD::SRL: return "srl";
899 case ISD::SELECT: return "select";
900 case ISD::ADDC: return "addc";
901 case ISD::SUBB: return "subb";
903 // Conversion operators.
904 case ISD::SIGN_EXTEND: return "sign_extend";
905 case ISD::ZERO_EXTEND: return "zero_extend";
906 case ISD::TRUNCATE: return "truncate";
907 case ISD::FP_ROUND: return "fp_round";
908 case ISD::FP_EXTEND: return "fp_extend";
910 case ISD::SINT_TO_FP: return "sint_to_fp";
911 case ISD::UINT_TO_FP: return "uint_to_fp";
912 case ISD::FP_TO_SINT: return "fp_to_sint";
913 case ISD::FP_TO_UINT: return "fp_to_uint";
915 // Control flow instructions
916 case ISD::BR: return "br";
917 case ISD::BRCOND: return "brcond";
918 case ISD::RET: return "ret";
919 case ISD::CALL: return "call";
920 case ISD::ADJCALLSTACKDOWN: return "adjcallstackdown";
921 case ISD::ADJCALLSTACKUP: return "adjcallstackup";
924 case ISD::LOAD: return "load";
925 case ISD::STORE: return "store";
926 case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
927 case ISD::EXTRACT_ELEMENT: return "extract_element";
928 case ISD::BUILD_PAIR: return "build_pair";
929 case ISD::MEMSET: return "memset";
930 case ISD::MEMCPY: return "memcpy";
931 case ISD::MEMMOVE: return "memmove";
934 const SetCCSDNode *SetCC = cast<SetCCSDNode>(this);
935 switch (SetCC->getCondition()) {
936 default: assert(0 && "Unknown setcc condition!");
937 case ISD::SETOEQ: return "setcc:setoeq";
938 case ISD::SETOGT: return "setcc:setogt";
939 case ISD::SETOGE: return "setcc:setoge";
940 case ISD::SETOLT: return "setcc:setolt";
941 case ISD::SETOLE: return "setcc:setole";
942 case ISD::SETONE: return "setcc:setone";
944 case ISD::SETO: return "setcc:seto";
945 case ISD::SETUO: return "setcc:setuo";
946 case ISD::SETUEQ: return "setcc:setue";
947 case ISD::SETUGT: return "setcc:setugt";
948 case ISD::SETUGE: return "setcc:setuge";
949 case ISD::SETULT: return "setcc:setult";
950 case ISD::SETULE: return "setcc:setule";
951 case ISD::SETUNE: return "setcc:setune";
953 case ISD::SETEQ: return "setcc:seteq";
954 case ISD::SETGT: return "setcc:setgt";
955 case ISD::SETGE: return "setcc:setge";
956 case ISD::SETLT: return "setcc:setlt";
957 case ISD::SETLE: return "setcc:setle";
958 case ISD::SETNE: return "setcc:setne";
963 void SDNode::dump() const {
964 std::cerr << (void*)this << ": ";
966 for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
967 if (i) std::cerr << ",";
968 switch (getValueType(i)) {
969 default: assert(0 && "Unknown value type!");
970 case MVT::i1: std::cerr << "i1"; break;
971 case MVT::i8: std::cerr << "i8"; break;
972 case MVT::i16: std::cerr << "i16"; break;
973 case MVT::i32: std::cerr << "i32"; break;
974 case MVT::i64: std::cerr << "i64"; break;
975 case MVT::f32: std::cerr << "f32"; break;
976 case MVT::f64: std::cerr << "f64"; break;
977 case MVT::Other: std::cerr << "ch"; break;
980 std::cerr << " = " << getOperationName();
983 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
984 if (i) std::cerr << ", ";
985 std::cerr << (void*)getOperand(i).Val;
986 if (unsigned RN = getOperand(i).ResNo)
987 std::cerr << ":" << RN;
990 if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
991 std::cerr << "<" << CSDN->getValue() << ">";
992 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
993 std::cerr << "<" << CSDN->getValue() << ">";
994 } else if (const GlobalAddressSDNode *GADN =
995 dyn_cast<GlobalAddressSDNode>(this)) {
997 WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
998 } else if (const FrameIndexSDNode *FIDN =
999 dyn_cast<FrameIndexSDNode>(this)) {
1000 std::cerr << "<" << FIDN->getIndex() << ">";
1001 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
1002 std::cerr << "<" << CP->getIndex() << ">";
1003 } else if (const BasicBlockSDNode *BBDN =
1004 dyn_cast<BasicBlockSDNode>(this)) {
1006 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
1008 std::cerr << LBB->getName() << " ";
1009 std::cerr << (const void*)BBDN->getBasicBlock() << ">";
1010 } else if (const RegSDNode *C2V = dyn_cast<RegSDNode>(this)) {
1011 std::cerr << "<reg #" << C2V->getReg() << ">";
1012 } else if (const ExternalSymbolSDNode *ES =
1013 dyn_cast<ExternalSymbolSDNode>(this)) {
1014 std::cerr << "'" << ES->getSymbol() << "'";
1018 static void DumpNodes(SDNode *N, unsigned indent) {
1019 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
1020 if (N->getOperand(i).Val->hasOneUse())
1021 DumpNodes(N->getOperand(i).Val, indent+2);
1023 std::cerr << "\n" << std::string(indent+2, ' ')
1024 << (void*)N->getOperand(i).Val << ": <multiple use>";
1027 std::cerr << "\n" << std::string(indent, ' ');
1031 void SelectionDAG::dump() const {
1032 std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
1033 std::vector<SDNode*> Nodes(AllNodes);
1034 std::sort(Nodes.begin(), Nodes.end());
1036 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
1037 if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
1038 DumpNodes(Nodes[i], 2);
1041 DumpNodes(getRoot().Val, 2);
1043 std::cerr << "\n\n";