X86ISelDAGToDAG.cpp revision 51a9ed9b41c881bd485ce76834352eb82c38ee5b
1//===- X86ISelDAGToDAG.cpp - A DAG pattern matching inst selector for X86 -===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the Evan Cheng and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines a DAG pattern matching instruction selector for X86, 11// converting from a legalized dag to a X86 dag. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "isel" 16#include "X86.h" 17#include "X86InstrBuilder.h" 18#include "X86RegisterInfo.h" 19#include "X86Subtarget.h" 20#include "X86ISelLowering.h" 21#include "llvm/GlobalValue.h" 22#include "llvm/Instructions.h" 23#include "llvm/Support/CFG.h" 24#include "llvm/CodeGen/MachineConstantPool.h" 25#include "llvm/CodeGen/MachineFunction.h" 26#include "llvm/CodeGen/MachineFrameInfo.h" 27#include "llvm/CodeGen/MachineInstrBuilder.h" 28#include "llvm/CodeGen/SSARegMap.h" 29#include "llvm/CodeGen/SelectionDAGISel.h" 30#include "llvm/Target/TargetMachine.h" 31#include "llvm/Support/Debug.h" 32#include "llvm/ADT/Statistic.h" 33#include <iostream> 34#include <set> 35using namespace llvm; 36 37//===----------------------------------------------------------------------===// 38// Pattern Matcher Implementation 39//===----------------------------------------------------------------------===// 40 41namespace { 42 /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses 43 /// SDOperand's instead of register numbers for the leaves of the matched 44 /// tree. 45 struct X86ISelAddressMode { 46 enum { 47 RegBase, 48 FrameIndexBase, 49 } BaseType; 50 51 struct { // This is really a union, discriminated by BaseType! 52 SDOperand Reg; 53 int FrameIndex; 54 } Base; 55 56 unsigned Scale; 57 SDOperand IndexReg; 58 unsigned Disp; 59 GlobalValue *GV; 60 Constant *CP; 61 unsigned Align; // CP alignment. 62 63 X86ISelAddressMode() 64 : BaseType(RegBase), Scale(1), IndexReg(), Disp(0), GV(0), 65 CP(0), Align(0) { 66 } 67 }; 68} 69 70namespace { 71 Statistic<> 72 NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added"); 73 74 //===--------------------------------------------------------------------===// 75 /// ISel - X86 specific code to select X86 machine instructions for 76 /// SelectionDAG operations. 77 /// 78 class X86DAGToDAGISel : public SelectionDAGISel { 79 /// ContainsFPCode - Every instruction we select that uses or defines a FP 80 /// register should set this to true. 81 bool ContainsFPCode; 82 83 /// X86Lowering - This object fully describes how to lower LLVM code to an 84 /// X86-specific SelectionDAG. 85 X86TargetLowering X86Lowering; 86 87 /// Subtarget - Keep a pointer to the X86Subtarget around so that we can 88 /// make the right decision when generating code for different targets. 89 const X86Subtarget *Subtarget; 90 91 unsigned GlobalBaseReg; 92 public: 93 X86DAGToDAGISel(TargetMachine &TM) 94 : SelectionDAGISel(X86Lowering), X86Lowering(TM) { 95 Subtarget = &TM.getSubtarget<X86Subtarget>(); 96 } 97 98 virtual bool runOnFunction(Function &Fn) { 99 // Make sure we re-emit a set of the global base reg if necessary 100 GlobalBaseReg = 0; 101 return SelectionDAGISel::runOnFunction(Fn); 102 } 103 104 virtual const char *getPassName() const { 105 return "X86 DAG->DAG Instruction Selection"; 106 } 107 108 /// InstructionSelectBasicBlock - This callback is invoked by 109 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen. 110 virtual void InstructionSelectBasicBlock(SelectionDAG &DAG); 111 112 virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF); 113 114// Include the pieces autogenerated from the target description. 115#include "X86GenDAGISel.inc" 116 117 private: 118 void Select(SDOperand &Result, SDOperand N); 119 120 bool MatchAddress(SDOperand N, X86ISelAddressMode &AM, bool isRoot = true); 121 bool SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 122 SDOperand &Index, SDOperand &Disp); 123 bool SelectLEAAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 124 SDOperand &Index, SDOperand &Disp); 125 bool TryFoldLoad(SDOperand P, SDOperand N, 126 SDOperand &Base, SDOperand &Scale, 127 SDOperand &Index, SDOperand &Disp); 128 129 inline void getAddressOperands(X86ISelAddressMode &AM, SDOperand &Base, 130 SDOperand &Scale, SDOperand &Index, 131 SDOperand &Disp) { 132 Base = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ? 133 CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, MVT::i32) : AM.Base.Reg; 134 Scale = getI8Imm(AM.Scale); 135 Index = AM.IndexReg; 136 Disp = AM.GV ? CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp) 137 : (AM.CP ? 138 CurDAG->getTargetConstantPool(AM.CP, MVT::i32, AM.Align, AM.Disp) 139 : getI32Imm(AM.Disp)); 140 } 141 142 /// getI8Imm - Return a target constant with the specified value, of type 143 /// i8. 144 inline SDOperand getI8Imm(unsigned Imm) { 145 return CurDAG->getTargetConstant(Imm, MVT::i8); 146 } 147 148 /// getI16Imm - Return a target constant with the specified value, of type 149 /// i16. 150 inline SDOperand getI16Imm(unsigned Imm) { 151 return CurDAG->getTargetConstant(Imm, MVT::i16); 152 } 153 154 /// getI32Imm - Return a target constant with the specified value, of type 155 /// i32. 156 inline SDOperand getI32Imm(unsigned Imm) { 157 return CurDAG->getTargetConstant(Imm, MVT::i32); 158 } 159 160 /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC 161 /// base register. Return the virtual register that holds this value. 162 SDOperand getGlobalBaseReg(); 163 164#ifndef NDEBUG 165 unsigned Indent; 166#endif 167 }; 168} 169 170/// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel 171/// when it has created a SelectionDAG for us to codegen. 172void X86DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) { 173 DEBUG(BB->dump()); 174 MachineFunction::iterator FirstMBB = BB; 175 176 // Codegen the basic block. 177#ifndef NDEBUG 178 DEBUG(std::cerr << "===== Instruction selection begins:\n"); 179 Indent = 0; 180#endif 181 DAG.setRoot(SelectRoot(DAG.getRoot())); 182#ifndef NDEBUG 183 DEBUG(std::cerr << "===== Instruction selection ends:\n"); 184#endif 185 CodeGenMap.clear(); 186 DAG.RemoveDeadNodes(); 187 188 // Emit machine code to BB. 189 ScheduleAndEmitDAG(DAG); 190 191 // If we are emitting FP stack code, scan the basic block to determine if this 192 // block defines any FP values. If so, put an FP_REG_KILL instruction before 193 // the terminator of the block. 194 if (!Subtarget->hasSSE2()) { 195 // Note that FP stack instructions *are* used in SSE code when returning 196 // values, but these are not live out of the basic block, so we don't need 197 // an FP_REG_KILL in this case either. 198 bool ContainsFPCode = false; 199 200 // Scan all of the machine instructions in these MBBs, checking for FP 201 // stores. 202 MachineFunction::iterator MBBI = FirstMBB; 203 do { 204 for (MachineBasicBlock::iterator I = MBBI->begin(), E = MBBI->end(); 205 !ContainsFPCode && I != E; ++I) { 206 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { 207 if (I->getOperand(op).isRegister() && I->getOperand(op).isDef() && 208 MRegisterInfo::isVirtualRegister(I->getOperand(op).getReg()) && 209 RegMap->getRegClass(I->getOperand(0).getReg()) == 210 X86::RFPRegisterClass) { 211 ContainsFPCode = true; 212 break; 213 } 214 } 215 } 216 } while (!ContainsFPCode && &*(MBBI++) != BB); 217 218 // Check PHI nodes in successor blocks. These PHI's will be lowered to have 219 // a copy of the input value in this block. 220 if (!ContainsFPCode) { 221 // Final check, check LLVM BB's that are successors to the LLVM BB 222 // corresponding to BB for FP PHI nodes. 223 const BasicBlock *LLVMBB = BB->getBasicBlock(); 224 const PHINode *PN; 225 for (succ_const_iterator SI = succ_begin(LLVMBB), E = succ_end(LLVMBB); 226 !ContainsFPCode && SI != E; ++SI) { 227 for (BasicBlock::const_iterator II = SI->begin(); 228 (PN = dyn_cast<PHINode>(II)); ++II) { 229 if (PN->getType()->isFloatingPoint()) { 230 ContainsFPCode = true; 231 break; 232 } 233 } 234 } 235 } 236 237 // Finally, if we found any FP code, emit the FP_REG_KILL instruction. 238 if (ContainsFPCode) { 239 BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0); 240 ++NumFPKill; 241 } 242 } 243} 244 245/// EmitSpecialCodeForMain - Emit any code that needs to be executed only in 246/// the main function. 247static void EmitSpecialCodeForMain(MachineBasicBlock *BB, 248 MachineFrameInfo *MFI) { 249 // Switch the FPU to 64-bit precision mode for better compatibility and speed. 250 int CWFrameIdx = MFI->CreateStackObject(2, 2); 251 addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx); 252 253 // Set the high part to be 64-bit precision. 254 addFrameReference(BuildMI(BB, X86::MOV8mi, 5), 255 CWFrameIdx, 1).addImm(2); 256 257 // Reload the modified control word now. 258 addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx); 259} 260 261void X86DAGToDAGISel::EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) { 262 // If this is main, emit special code for main. 263 MachineBasicBlock *BB = MF.begin(); 264 if (Fn.hasExternalLinkage() && Fn.getName() == "main") 265 EmitSpecialCodeForMain(BB, MF.getFrameInfo()); 266} 267 268/// MatchAddress - Add the specified node to the specified addressing mode, 269/// returning true if it cannot be done. This just pattern matches for the 270/// addressing mode 271bool X86DAGToDAGISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM, 272 bool isRoot) { 273 bool Available = false; 274 // If N has already been selected, reuse the result unless in some very 275 // specific cases. 276 std::map<SDOperand, SDOperand>::iterator CGMI= CodeGenMap.find(N.getValue(0)); 277 if (CGMI != CodeGenMap.end()) { 278 Available = true; 279 } 280 281 switch (N.getOpcode()) { 282 default: break; 283 case ISD::Constant: 284 AM.Disp += cast<ConstantSDNode>(N)->getValue(); 285 return false; 286 287 case X86ISD::Wrapper: 288 // If both base and index components have been picked, we can't fit 289 // the result available in the register in the addressing mode. Duplicate 290 // GlobalAddress or ConstantPool as displacement. 291 if (!Available || (AM.Base.Reg.Val && AM.IndexReg.Val)) { 292 if (ConstantPoolSDNode *CP = 293 dyn_cast<ConstantPoolSDNode>(N.getOperand(0))) { 294 if (AM.CP == 0) { 295 AM.CP = CP->get(); 296 AM.Align = CP->getAlignment(); 297 AM.Disp += CP->getOffset(); 298 return false; 299 } 300 } else if (GlobalAddressSDNode *G = 301 dyn_cast<GlobalAddressSDNode>(N.getOperand(0))) { 302 if (AM.GV == 0) { 303 AM.GV = G->getGlobal(); 304 AM.Disp += G->getOffset(); 305 return false; 306 } 307 } 308 } 309 break; 310 311 case ISD::FrameIndex: 312 if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) { 313 AM.BaseType = X86ISelAddressMode::FrameIndexBase; 314 AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex(); 315 return false; 316 } 317 break; 318 319 case ISD::SHL: 320 if (!Available && AM.IndexReg.Val == 0 && AM.Scale == 1) 321 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) { 322 unsigned Val = CN->getValue(); 323 if (Val == 1 || Val == 2 || Val == 3) { 324 AM.Scale = 1 << Val; 325 SDOperand ShVal = N.Val->getOperand(0); 326 327 // Okay, we know that we have a scale by now. However, if the scaled 328 // value is an add of something and a constant, we can fold the 329 // constant into the disp field here. 330 if (ShVal.Val->getOpcode() == ISD::ADD && ShVal.hasOneUse() && 331 isa<ConstantSDNode>(ShVal.Val->getOperand(1))) { 332 AM.IndexReg = ShVal.Val->getOperand(0); 333 ConstantSDNode *AddVal = 334 cast<ConstantSDNode>(ShVal.Val->getOperand(1)); 335 AM.Disp += AddVal->getValue() << Val; 336 } else { 337 AM.IndexReg = ShVal; 338 } 339 return false; 340 } 341 } 342 break; 343 344 case ISD::MUL: 345 // X*[3,5,9] -> X+X*[2,4,8] 346 if (!Available && 347 AM.BaseType == X86ISelAddressMode::RegBase && 348 AM.Base.Reg.Val == 0 && 349 AM.IndexReg.Val == 0) 350 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) 351 if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) { 352 AM.Scale = unsigned(CN->getValue())-1; 353 354 SDOperand MulVal = N.Val->getOperand(0); 355 SDOperand Reg; 356 357 // Okay, we know that we have a scale by now. However, if the scaled 358 // value is an add of something and a constant, we can fold the 359 // constant into the disp field here. 360 if (MulVal.Val->getOpcode() == ISD::ADD && MulVal.hasOneUse() && 361 isa<ConstantSDNode>(MulVal.Val->getOperand(1))) { 362 Reg = MulVal.Val->getOperand(0); 363 ConstantSDNode *AddVal = 364 cast<ConstantSDNode>(MulVal.Val->getOperand(1)); 365 AM.Disp += AddVal->getValue() * CN->getValue(); 366 } else { 367 Reg = N.Val->getOperand(0); 368 } 369 370 AM.IndexReg = AM.Base.Reg = Reg; 371 return false; 372 } 373 break; 374 375 case ISD::ADD: { 376 if (!Available) { 377 X86ISelAddressMode Backup = AM; 378 if (!MatchAddress(N.Val->getOperand(0), AM, false) && 379 !MatchAddress(N.Val->getOperand(1), AM, false)) 380 return false; 381 AM = Backup; 382 if (!MatchAddress(N.Val->getOperand(1), AM, false) && 383 !MatchAddress(N.Val->getOperand(0), AM, false)) 384 return false; 385 AM = Backup; 386 } 387 break; 388 } 389 } 390 391 // Is the base register already occupied? 392 if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.Val) { 393 // If so, check to see if the scale index register is set. 394 if (AM.IndexReg.Val == 0) { 395 AM.IndexReg = N; 396 AM.Scale = 1; 397 return false; 398 } 399 400 // Otherwise, we cannot select it. 401 return true; 402 } 403 404 // Default, generate it as a register. 405 AM.BaseType = X86ISelAddressMode::RegBase; 406 AM.Base.Reg = N; 407 return false; 408} 409 410/// SelectAddr - returns true if it is able pattern match an addressing mode. 411/// It returns the operands which make up the maximal addressing mode it can 412/// match by reference. 413bool X86DAGToDAGISel::SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 414 SDOperand &Index, SDOperand &Disp) { 415 X86ISelAddressMode AM; 416 if (MatchAddress(N, AM)) 417 return false; 418 419 if (AM.BaseType == X86ISelAddressMode::RegBase) { 420 if (!AM.Base.Reg.Val) 421 AM.Base.Reg = CurDAG->getRegister(0, MVT::i32); 422 } 423 424 if (!AM.IndexReg.Val) 425 AM.IndexReg = CurDAG->getRegister(0, MVT::i32); 426 427 getAddressOperands(AM, Base, Scale, Index, Disp); 428 429 return true; 430} 431 432/// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing 433/// mode it matches can be cost effectively emitted as an LEA instruction. 434/// For X86, it always is unless it's just a (Reg + const). 435bool X86DAGToDAGISel::SelectLEAAddr(SDOperand N, SDOperand &Base, 436 SDOperand &Scale, 437 SDOperand &Index, SDOperand &Disp) { 438 X86ISelAddressMode AM; 439 if (MatchAddress(N, AM)) 440 return false; 441 442 unsigned Complexity = 0; 443 if (AM.BaseType == X86ISelAddressMode::RegBase) 444 if (AM.Base.Reg.Val) 445 Complexity = 1; 446 else 447 AM.Base.Reg = CurDAG->getRegister(0, MVT::i32); 448 else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase) 449 Complexity = 4; 450 451 if (AM.IndexReg.Val) 452 Complexity++; 453 else 454 AM.IndexReg = CurDAG->getRegister(0, MVT::i32); 455 456 if (AM.Scale > 1) 457 Complexity += 2; 458 459 // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA 460 // to a LEA. This is determined with some expermentation but is by no means 461 // optimal (especially for code size consideration). LEA is nice because of 462 // its three-address nature. Tweak the cost function again when we can run 463 // convertToThreeAddress() at register allocation time. 464 if (AM.GV || AM.CP) 465 Complexity += 2; 466 467 if (AM.Disp && (AM.Base.Reg.Val || AM.IndexReg.Val)) 468 Complexity++; 469 470 if (Complexity > 2) { 471 getAddressOperands(AM, Base, Scale, Index, Disp); 472 return true; 473 } 474 475 return false; 476} 477 478bool X86DAGToDAGISel::TryFoldLoad(SDOperand P, SDOperand N, 479 SDOperand &Base, SDOperand &Scale, 480 SDOperand &Index, SDOperand &Disp) { 481 if (N.getOpcode() == ISD::LOAD && 482 N.hasOneUse() && 483 !CodeGenMap.count(N.getValue(0)) && 484 (P.getNumOperands() == 1 || !isNonImmUse(P.Val, N.Val))) 485 return SelectAddr(N.getOperand(1), Base, Scale, Index, Disp); 486 return false; 487} 488 489static bool isRegister0(SDOperand Op) { 490 if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op)) 491 return (R->getReg() == 0); 492 return false; 493} 494 495/// getGlobalBaseReg - Output the instructions required to put the 496/// base address to use for accessing globals into a register. 497/// 498SDOperand X86DAGToDAGISel::getGlobalBaseReg() { 499 if (!GlobalBaseReg) { 500 // Insert the set of GlobalBaseReg into the first MBB of the function 501 MachineBasicBlock &FirstMBB = BB->getParent()->front(); 502 MachineBasicBlock::iterator MBBI = FirstMBB.begin(); 503 SSARegMap *RegMap = BB->getParent()->getSSARegMap(); 504 // FIXME: when we get to LP64, we will need to create the appropriate 505 // type of register here. 506 GlobalBaseReg = RegMap->createVirtualRegister(X86::R32RegisterClass); 507 BuildMI(FirstMBB, MBBI, X86::MovePCtoStack, 0); 508 BuildMI(FirstMBB, MBBI, X86::POP32r, 1, GlobalBaseReg); 509 } 510 return CurDAG->getRegister(GlobalBaseReg, MVT::i32); 511} 512 513void X86DAGToDAGISel::Select(SDOperand &Result, SDOperand N) { 514 SDNode *Node = N.Val; 515 MVT::ValueType NVT = Node->getValueType(0); 516 unsigned Opc, MOpc; 517 unsigned Opcode = Node->getOpcode(); 518 519#ifndef NDEBUG 520 DEBUG(std::cerr << std::string(Indent, ' ')); 521 DEBUG(std::cerr << "Selecting: "); 522 DEBUG(Node->dump(CurDAG)); 523 DEBUG(std::cerr << "\n"); 524 Indent += 2; 525#endif 526 527 if (Opcode >= ISD::BUILTIN_OP_END && Opcode < X86ISD::FIRST_NUMBER) { 528 Result = N; 529#ifndef NDEBUG 530 DEBUG(std::cerr << std::string(Indent-2, ' ')); 531 DEBUG(std::cerr << "== "); 532 DEBUG(Node->dump(CurDAG)); 533 DEBUG(std::cerr << "\n"); 534 Indent -= 2; 535#endif 536 return; // Already selected. 537 } 538 539 std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(N); 540 if (CGMI != CodeGenMap.end()) { 541 Result = CGMI->second; 542#ifndef NDEBUG 543 DEBUG(std::cerr << std::string(Indent-2, ' ')); 544 DEBUG(std::cerr << "== "); 545 DEBUG(Result.Val->dump(CurDAG)); 546 DEBUG(std::cerr << "\n"); 547 Indent -= 2; 548#endif 549 return; 550 } 551 552 switch (Opcode) { 553 default: break; 554 case X86ISD::GlobalBaseReg: 555 Result = getGlobalBaseReg(); 556 return; 557 558 case ISD::ADD: { 559 // Turn ADD X, c to MOV32ri X+c. This cannot be done with tblgen'd 560 // code and is matched first so to prevent it from being turned into 561 // LEA32r X+c. 562 SDOperand N0 = N.getOperand(0); 563 SDOperand N1 = N.getOperand(1); 564 if (N.Val->getValueType(0) == MVT::i32 && 565 N0.getOpcode() == X86ISD::Wrapper && 566 N1.getOpcode() == ISD::Constant) { 567 unsigned Offset = (unsigned)cast<ConstantSDNode>(N1)->getValue(); 568 SDOperand C(0, 0); 569 // TODO: handle ExternalSymbolSDNode. 570 if (GlobalAddressSDNode *G = 571 dyn_cast<GlobalAddressSDNode>(N0.getOperand(0))) { 572 C = CurDAG->getTargetGlobalAddress(G->getGlobal(), MVT::i32, 573 G->getOffset() + Offset); 574 } else if (ConstantPoolSDNode *CP = 575 dyn_cast<ConstantPoolSDNode>(N0.getOperand(0))) { 576 C = CurDAG->getTargetConstantPool(CP->get(), MVT::i32, 577 CP->getAlignment(), 578 CP->getOffset()+Offset); 579 } 580 581 if (C.Val) { 582 if (N.Val->hasOneUse()) { 583 Result = CurDAG->SelectNodeTo(N.Val, X86::MOV32ri, MVT::i32, C); 584 } else { 585 SDNode *ResNode = CurDAG->getTargetNode(X86::MOV32ri, MVT::i32, C); 586 Result = CodeGenMap[N] = SDOperand(ResNode, 0); 587 } 588 return; 589 } 590 } 591 592 // Other cases are handled by auto-generated code. 593 break; 594 } 595 596 case ISD::MULHU: 597 case ISD::MULHS: { 598 if (Opcode == ISD::MULHU) 599 switch (NVT) { 600 default: assert(0 && "Unsupported VT!"); 601 case MVT::i8: Opc = X86::MUL8r; MOpc = X86::MUL8m; break; 602 case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break; 603 case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break; 604 } 605 else 606 switch (NVT) { 607 default: assert(0 && "Unsupported VT!"); 608 case MVT::i8: Opc = X86::IMUL8r; MOpc = X86::IMUL8m; break; 609 case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break; 610 case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break; 611 } 612 613 unsigned LoReg, HiReg; 614 switch (NVT) { 615 default: assert(0 && "Unsupported VT!"); 616 case MVT::i8: LoReg = X86::AL; HiReg = X86::AH; break; 617 case MVT::i16: LoReg = X86::AX; HiReg = X86::DX; break; 618 case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break; 619 } 620 621 SDOperand N0 = Node->getOperand(0); 622 SDOperand N1 = Node->getOperand(1); 623 624 bool foldedLoad = false; 625 SDOperand Tmp0, Tmp1, Tmp2, Tmp3; 626 foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3); 627 // MULHU and MULHS are commmutative 628 if (!foldedLoad) { 629 foldedLoad = TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3); 630 if (foldedLoad) { 631 N0 = Node->getOperand(1); 632 N1 = Node->getOperand(0); 633 } 634 } 635 636 SDOperand Chain; 637 if (foldedLoad) 638 Select(Chain, N1.getOperand(0)); 639 else 640 Chain = CurDAG->getEntryNode(); 641 642 SDOperand InFlag(0, 0); 643 Select(N0, N0); 644 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT), 645 N0, InFlag); 646 InFlag = Chain.getValue(1); 647 648 if (foldedLoad) { 649 Select(Tmp0, Tmp0); 650 Select(Tmp1, Tmp1); 651 Select(Tmp2, Tmp2); 652 Select(Tmp3, Tmp3); 653 SDNode *CNode = 654 CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1, 655 Tmp2, Tmp3, Chain, InFlag); 656 Chain = SDOperand(CNode, 0); 657 InFlag = SDOperand(CNode, 1); 658 } else { 659 Select(N1, N1); 660 InFlag = 661 SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0); 662 } 663 664 Result = CurDAG->getCopyFromReg(Chain, HiReg, NVT, InFlag); 665 CodeGenMap[N.getValue(0)] = Result; 666 if (foldedLoad) { 667 CodeGenMap[N1.getValue(1)] = Result.getValue(1); 668 AddHandleReplacement(N1.Val, 1, Result.Val, 1); 669 } 670 671#ifndef NDEBUG 672 DEBUG(std::cerr << std::string(Indent-2, ' ')); 673 DEBUG(std::cerr << "== "); 674 DEBUG(Result.Val->dump(CurDAG)); 675 DEBUG(std::cerr << "\n"); 676 Indent -= 2; 677#endif 678 return; 679 } 680 681 case ISD::SDIV: 682 case ISD::UDIV: 683 case ISD::SREM: 684 case ISD::UREM: { 685 bool isSigned = Opcode == ISD::SDIV || Opcode == ISD::SREM; 686 bool isDiv = Opcode == ISD::SDIV || Opcode == ISD::UDIV; 687 if (!isSigned) 688 switch (NVT) { 689 default: assert(0 && "Unsupported VT!"); 690 case MVT::i8: Opc = X86::DIV8r; MOpc = X86::DIV8m; break; 691 case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break; 692 case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break; 693 } 694 else 695 switch (NVT) { 696 default: assert(0 && "Unsupported VT!"); 697 case MVT::i8: Opc = X86::IDIV8r; MOpc = X86::IDIV8m; break; 698 case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break; 699 case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break; 700 } 701 702 unsigned LoReg, HiReg; 703 unsigned ClrOpcode, SExtOpcode; 704 switch (NVT) { 705 default: assert(0 && "Unsupported VT!"); 706 case MVT::i8: 707 LoReg = X86::AL; HiReg = X86::AH; 708 ClrOpcode = X86::MOV8ri; 709 SExtOpcode = X86::CBW; 710 break; 711 case MVT::i16: 712 LoReg = X86::AX; HiReg = X86::DX; 713 ClrOpcode = X86::MOV16ri; 714 SExtOpcode = X86::CWD; 715 break; 716 case MVT::i32: 717 LoReg = X86::EAX; HiReg = X86::EDX; 718 ClrOpcode = X86::MOV32ri; 719 SExtOpcode = X86::CDQ; 720 break; 721 } 722 723 SDOperand N0 = Node->getOperand(0); 724 SDOperand N1 = Node->getOperand(1); 725 726 bool foldedLoad = false; 727 SDOperand Tmp0, Tmp1, Tmp2, Tmp3; 728 foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3); 729 SDOperand Chain; 730 if (foldedLoad) 731 Select(Chain, N1.getOperand(0)); 732 else 733 Chain = CurDAG->getEntryNode(); 734 735 SDOperand InFlag(0, 0); 736 Select(N0, N0); 737 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT), 738 N0, InFlag); 739 InFlag = Chain.getValue(1); 740 741 if (isSigned) { 742 // Sign extend the low part into the high part. 743 InFlag = 744 SDOperand(CurDAG->getTargetNode(SExtOpcode, MVT::Flag, InFlag), 0); 745 } else { 746 // Zero out the high part, effectively zero extending the input. 747 SDOperand ClrNode = 748 SDOperand(CurDAG->getTargetNode(ClrOpcode, NVT, 749 CurDAG->getTargetConstant(0, NVT)), 0); 750 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(HiReg, NVT), 751 ClrNode, InFlag); 752 InFlag = Chain.getValue(1); 753 } 754 755 if (foldedLoad) { 756 Select(Tmp0, Tmp0); 757 Select(Tmp1, Tmp1); 758 Select(Tmp2, Tmp2); 759 Select(Tmp3, Tmp3); 760 SDNode *CNode = 761 CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1, 762 Tmp2, Tmp3, Chain, InFlag); 763 Chain = SDOperand(CNode, 0); 764 InFlag = SDOperand(CNode, 1); 765 } else { 766 Select(N1, N1); 767 InFlag = 768 SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0); 769 } 770 771 Result = CurDAG->getCopyFromReg(Chain, isDiv ? LoReg : HiReg, 772 NVT, InFlag); 773 CodeGenMap[N.getValue(0)] = Result; 774 if (foldedLoad) { 775 CodeGenMap[N1.getValue(1)] = Result.getValue(1); 776 AddHandleReplacement(N1.Val, 1, Result.Val, 1); 777 } 778 779#ifndef NDEBUG 780 DEBUG(std::cerr << std::string(Indent-2, ' ')); 781 DEBUG(std::cerr << "== "); 782 DEBUG(Result.Val->dump(CurDAG)); 783 DEBUG(std::cerr << "\n"); 784 Indent -= 2; 785#endif 786 return; 787 } 788 789 case ISD::TRUNCATE: { 790 unsigned Reg; 791 MVT::ValueType VT; 792 switch (Node->getOperand(0).getValueType()) { 793 default: assert(0 && "Unknown truncate!"); 794 case MVT::i16: Reg = X86::AX; Opc = X86::MOV16rr; VT = MVT::i16; break; 795 case MVT::i32: Reg = X86::EAX; Opc = X86::MOV32rr; VT = MVT::i32; break; 796 } 797 SDOperand Tmp0, Tmp1; 798 Select(Tmp0, Node->getOperand(0)); 799 Select(Tmp1, SDOperand(CurDAG->getTargetNode(Opc, VT, Tmp0), 0)); 800 SDOperand InFlag = SDOperand(0,0); 801 Result = CurDAG->getCopyToReg(CurDAG->getEntryNode(), Reg, Tmp1, InFlag); 802 SDOperand Chain = Result.getValue(0); 803 InFlag = Result.getValue(1); 804 805 switch (NVT) { 806 default: assert(0 && "Unknown truncate!"); 807 case MVT::i8: Reg = X86::AL; Opc = X86::MOV8rr; VT = MVT::i8; break; 808 case MVT::i16: Reg = X86::AX; Opc = X86::MOV16rr; VT = MVT::i16; break; 809 } 810 811 Result = CurDAG->getCopyFromReg(Chain, Reg, VT, InFlag); 812 if (N.Val->hasOneUse()) 813 Result = CurDAG->SelectNodeTo(N.Val, Opc, VT, Result); 814 else 815 Result = CodeGenMap[N] = 816 SDOperand(CurDAG->getTargetNode(Opc, VT, Result), 0); 817 818#ifndef NDEBUG 819 DEBUG(std::cerr << std::string(Indent-2, ' ')); 820 DEBUG(std::cerr << "== "); 821 DEBUG(Result.Val->dump(CurDAG)); 822 DEBUG(std::cerr << "\n"); 823 Indent -= 2; 824#endif 825 return; 826 } 827 } 828 829 SelectCode(Result, N); 830#ifndef NDEBUG 831 DEBUG(std::cerr << std::string(Indent-2, ' ')); 832 DEBUG(std::cerr << "=> "); 833 DEBUG(Result.Val->dump(CurDAG)); 834 DEBUG(std::cerr << "\n"); 835 Indent -= 2; 836#endif 837} 838 839/// createX86ISelDag - This pass converts a legalized DAG into a 840/// X86-specific DAG, ready for instruction scheduling. 841/// 842FunctionPass *llvm::createX86ISelDag(TargetMachine &TM) { 843 return new X86DAGToDAGISel(TM); 844} 845