X86ISelDAGToDAG.cpp revision 2584d93acf7cdfabc815a6bbc5597e4dd46d8f2c
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 "X86ISelLowering.h" 19#include "X86RegisterInfo.h" 20#include "X86Subtarget.h" 21#include "X86TargetMachine.h" 22#include "llvm/GlobalValue.h" 23#include "llvm/Instructions.h" 24#include "llvm/Intrinsics.h" 25#include "llvm/Support/CFG.h" 26#include "llvm/CodeGen/MachineConstantPool.h" 27#include "llvm/CodeGen/MachineFunction.h" 28#include "llvm/CodeGen/MachineFrameInfo.h" 29#include "llvm/CodeGen/MachineInstrBuilder.h" 30#include "llvm/CodeGen/SSARegMap.h" 31#include "llvm/CodeGen/SelectionDAGISel.h" 32#include "llvm/Target/TargetMachine.h" 33#include "llvm/Support/Debug.h" 34#include "llvm/Support/Visibility.h" 35#include "llvm/ADT/Statistic.h" 36#include <iostream> 37#include <list> 38#include <set> 39using namespace llvm; 40 41//===----------------------------------------------------------------------===// 42// Pattern Matcher Implementation 43//===----------------------------------------------------------------------===// 44 45namespace { 46 /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses 47 /// SDOperand's instead of register numbers for the leaves of the matched 48 /// tree. 49 struct X86ISelAddressMode { 50 enum { 51 RegBase, 52 FrameIndexBase 53 } BaseType; 54 55 struct { // This is really a union, discriminated by BaseType! 56 SDOperand Reg; 57 int FrameIndex; 58 } Base; 59 60 unsigned Scale; 61 SDOperand IndexReg; 62 unsigned Disp; 63 GlobalValue *GV; 64 Constant *CP; 65 unsigned Align; // CP alignment. 66 67 X86ISelAddressMode() 68 : BaseType(RegBase), Scale(1), IndexReg(), Disp(0), GV(0), 69 CP(0), Align(0) { 70 } 71 }; 72} 73 74namespace { 75 Statistic<> 76 NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added"); 77 78 //===--------------------------------------------------------------------===// 79 /// ISel - X86 specific code to select X86 machine instructions for 80 /// SelectionDAG operations. 81 /// 82 class VISIBILITY_HIDDEN X86DAGToDAGISel : public SelectionDAGISel { 83 /// ContainsFPCode - Every instruction we select that uses or defines a FP 84 /// register should set this to true. 85 bool ContainsFPCode; 86 87 /// X86Lowering - This object fully describes how to lower LLVM code to an 88 /// X86-specific SelectionDAG. 89 X86TargetLowering X86Lowering; 90 91 /// Subtarget - Keep a pointer to the X86Subtarget around so that we can 92 /// make the right decision when generating code for different targets. 93 const X86Subtarget *Subtarget; 94 95 unsigned GlobalBaseReg; 96 97 public: 98 X86DAGToDAGISel(X86TargetMachine &TM) 99 : SelectionDAGISel(X86Lowering), 100 X86Lowering(*TM.getTargetLowering()), 101 Subtarget(&TM.getSubtarget<X86Subtarget>()), 102 DAGSize(0), TopOrder(NULL), IdToOrder(NULL), 103 RMRange(NULL), ReachibilityMatrix(NULL) {} 104 105 virtual bool runOnFunction(Function &Fn) { 106 // Make sure we re-emit a set of the global base reg if necessary 107 GlobalBaseReg = 0; 108 return SelectionDAGISel::runOnFunction(Fn); 109 } 110 111 virtual const char *getPassName() const { 112 return "X86 DAG->DAG Instruction Selection"; 113 } 114 115 /// InstructionSelectBasicBlock - This callback is invoked by 116 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen. 117 virtual void InstructionSelectBasicBlock(SelectionDAG &DAG); 118 119 virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF); 120 121 virtual bool IsFoldableBy(SDNode *N, SDNode *U); 122 123// Include the pieces autogenerated from the target description. 124#include "X86GenDAGISel.inc" 125 126 private: 127 void DetermineTopologicalOrdering(); 128 void DeterminReachibility(SDNode *f, SDNode *t); 129 130 void Select(SDOperand &Result, SDOperand N); 131 132 bool MatchAddress(SDOperand N, X86ISelAddressMode &AM, bool isRoot = true); 133 bool SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 134 SDOperand &Index, SDOperand &Disp); 135 bool SelectLEAAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 136 SDOperand &Index, SDOperand &Disp); 137 bool TryFoldLoad(SDOperand P, SDOperand N, 138 SDOperand &Base, SDOperand &Scale, 139 SDOperand &Index, SDOperand &Disp); 140 /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for 141 /// inline asm expressions. 142 virtual bool SelectInlineAsmMemoryOperand(const SDOperand &Op, 143 char ConstraintCode, 144 std::vector<SDOperand> &OutOps, 145 SelectionDAG &DAG); 146 147 void EmitSpecialCodeForMain(MachineBasicBlock *BB, MachineFrameInfo *MFI); 148 149 inline void getAddressOperands(X86ISelAddressMode &AM, SDOperand &Base, 150 SDOperand &Scale, SDOperand &Index, 151 SDOperand &Disp) { 152 Base = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ? 153 CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, MVT::i32) : AM.Base.Reg; 154 Scale = getI8Imm(AM.Scale); 155 Index = AM.IndexReg; 156 Disp = AM.GV ? CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp) 157 : (AM.CP ? 158 CurDAG->getTargetConstantPool(AM.CP, MVT::i32, AM.Align, AM.Disp) 159 : getI32Imm(AM.Disp)); 160 } 161 162 /// getI8Imm - Return a target constant with the specified value, of type 163 /// i8. 164 inline SDOperand getI8Imm(unsigned Imm) { 165 return CurDAG->getTargetConstant(Imm, MVT::i8); 166 } 167 168 /// getI16Imm - Return a target constant with the specified value, of type 169 /// i16. 170 inline SDOperand getI16Imm(unsigned Imm) { 171 return CurDAG->getTargetConstant(Imm, MVT::i16); 172 } 173 174 /// getI32Imm - Return a target constant with the specified value, of type 175 /// i32. 176 inline SDOperand getI32Imm(unsigned Imm) { 177 return CurDAG->getTargetConstant(Imm, MVT::i32); 178 } 179 180 /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC 181 /// base register. Return the virtual register that holds this value. 182 SDOperand getGlobalBaseReg(); 183 184 /// DAGSize - Number of nodes in the DAG. 185 /// 186 unsigned DAGSize; 187 188 /// TopOrder - Topological ordering of all nodes in the DAG. 189 /// 190 SDNode* *TopOrder; 191 192 /// IdToOrder - Node id to topological order map. 193 /// 194 unsigned *IdToOrder; 195 196 /// RMRange - The range of reachibility information available for the 197 /// particular source node. 198 unsigned *RMRange; 199 200 /// ReachibilityMatrix - A N x N matrix representing all pairs reachibility 201 /// information. One bit per potential edge. 202 unsigned char *ReachibilityMatrix; 203 204 inline void setReachable(SDNode *f, SDNode *t) { 205 unsigned Idx = f->getNodeId() * DAGSize + t->getNodeId(); 206 ReachibilityMatrix[Idx / 8] |= 1 << (Idx % 8); 207 } 208 209 inline bool isReachable(SDNode *f, SDNode *t) { 210 unsigned Idx = f->getNodeId() * DAGSize + t->getNodeId(); 211 return ReachibilityMatrix[Idx / 8] & (1 << (Idx % 8)); 212 } 213 214 /// UnfoldableSet - An boolean array representing nodes which have been 215 /// folded into addressing modes and therefore should not be folded in 216 /// another operation. 217 unsigned char *UnfoldableSet; 218 219 inline void setUnfoldable(SDNode *N) { 220 unsigned Id = N->getNodeId(); 221 UnfoldableSet[Id / 8] |= 1 << (Id % 8); 222 } 223 224 inline bool isUnfoldable(SDNode *N) { 225 unsigned Id = N->getNodeId(); 226 return UnfoldableSet[Id / 8] & (1 << (Id % 8)); 227 } 228 229#ifndef NDEBUG 230 unsigned Indent; 231#endif 232 }; 233} 234 235bool X86DAGToDAGISel::IsFoldableBy(SDNode *N, SDNode *U) { 236 // Is it already folded by SelectAddr / SelectLEAAddr? 237 if (isUnfoldable(N)) 238 return false; 239 240 // If U use can somehow reach N through another path then U can't fold N or 241 // it will create a cycle. e.g. In the following diagram, U can reach N 242 // through X. If N is foled into into U, then X is both a predecessor and 243 // a successor of U. 244 // 245 // [ N ] 246 // ^ ^ 247 // | | 248 // / \--- 249 // / [X] 250 // | ^ 251 // [U]--------| 252 DeterminReachibility(U, N); 253 assert(isReachable(U, N) && "Attempting to fold a non-operand node?"); 254 for (SDNode::op_iterator I = U->op_begin(), E = U->op_end(); I != E; ++I) { 255 SDNode *P = I->Val; 256 if (P != N && isReachable(P, N)) 257 return false; 258 } 259 return true; 260} 261 262/// DetermineTopologicalOrdering - Determine topological ordering of the nodes 263/// in the DAG. 264void X86DAGToDAGISel::DetermineTopologicalOrdering() { 265 TopOrder = new SDNode*[DAGSize]; 266 IdToOrder = new unsigned[DAGSize]; 267 memset(IdToOrder, 0, DAGSize * sizeof(unsigned)); 268 RMRange = new unsigned[DAGSize]; 269 memset(RMRange, 0, DAGSize * sizeof(unsigned)); 270 271 std::vector<unsigned> InDegree(DAGSize); 272 std::list<SDNode*> Sources; 273 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(), 274 E = CurDAG->allnodes_end(); I != E; ++I) { 275 SDNode *N = I; 276 unsigned Degree = N->use_size(); 277 InDegree[N->getNodeId()] = Degree; 278 if (Degree == 0) 279 Sources.push_back(I); 280 } 281 282 unsigned Order = 0; 283 while (!Sources.empty()) { 284 SDNode *N = Sources.front(); 285 Sources.pop_front(); 286 TopOrder[Order] = N; 287 IdToOrder[N->getNodeId()] = Order; 288 Order++; 289 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 290 SDNode *P = I->Val; 291 int PId = P->getNodeId(); 292 unsigned Degree = InDegree[PId] - 1; 293 if (Degree == 0) 294 Sources.push_back(P); 295 InDegree[PId] = Degree; 296 } 297 } 298} 299 300void X86DAGToDAGISel::DeterminReachibility(SDNode *f, SDNode *t) { 301 if (!ReachibilityMatrix) { 302 unsigned RMSize = (DAGSize * DAGSize + 7) / 8; 303 ReachibilityMatrix = new unsigned char[RMSize]; 304 memset(ReachibilityMatrix, 0, RMSize); 305 } 306 307 int Idf = f->getNodeId(); 308 int Idt = t->getNodeId(); 309 unsigned Orderf = IdToOrder[Idf]; 310 unsigned Ordert = IdToOrder[Idt]; 311 unsigned Range = RMRange[Idf]; 312 if (Range >= Ordert) 313 return; 314 if (Range < Orderf) 315 Range = Orderf; 316 317 for (unsigned i = Range; i < Ordert; ++i) { 318 SDNode *N = TopOrder[i]; 319 setReachable(N, N); 320 // If N is a leaf node, there is nothing more to do. 321 if (N->getNumOperands() == 0) 322 continue; 323 324 for (unsigned i2 = Orderf; ; ++i2) { 325 SDNode *M = TopOrder[i2]; 326 if (isReachable(M, N)) { 327 // Update reachibility from M to N's operands. 328 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E;++I) 329 setReachable(M, I->Val); 330 } 331 if (M == N) break; 332 } 333 } 334 335 RMRange[Idf] = Ordert; 336} 337 338/// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel 339/// when it has created a SelectionDAG for us to codegen. 340void X86DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) { 341 DEBUG(BB->dump()); 342 MachineFunction::iterator FirstMBB = BB; 343 344 DAGSize = DAG.AssignNodeIds(); 345 unsigned NumBytes = (DAGSize+7) / 8; 346 UnfoldableSet = new unsigned char[NumBytes]; 347 memset(UnfoldableSet, 0, NumBytes); 348 349 DetermineTopologicalOrdering(); 350 351 // Codegen the basic block. 352#ifndef NDEBUG 353 DEBUG(std::cerr << "===== Instruction selection begins:\n"); 354 Indent = 0; 355#endif 356 DAG.setRoot(SelectRoot(DAG.getRoot())); 357#ifndef NDEBUG 358 DEBUG(std::cerr << "===== Instruction selection ends:\n"); 359#endif 360 361 delete[] ReachibilityMatrix; 362 delete[] TopOrder; 363 delete[] IdToOrder; 364 delete[] RMRange; 365 delete[] UnfoldableSet; 366 ReachibilityMatrix = NULL; 367 TopOrder = NULL; 368 IdToOrder = RMRange = NULL; 369 UnfoldableSet = NULL; 370 CodeGenMap.clear(); 371 HandleMap.clear(); 372 ReplaceMap.clear(); 373 DAG.RemoveDeadNodes(); 374 375 // Emit machine code to BB. 376 ScheduleAndEmitDAG(DAG); 377 378 // If we are emitting FP stack code, scan the basic block to determine if this 379 // block defines any FP values. If so, put an FP_REG_KILL instruction before 380 // the terminator of the block. 381 if (!Subtarget->hasSSE2()) { 382 // Note that FP stack instructions *are* used in SSE code when returning 383 // values, but these are not live out of the basic block, so we don't need 384 // an FP_REG_KILL in this case either. 385 bool ContainsFPCode = false; 386 387 // Scan all of the machine instructions in these MBBs, checking for FP 388 // stores. 389 MachineFunction::iterator MBBI = FirstMBB; 390 do { 391 for (MachineBasicBlock::iterator I = MBBI->begin(), E = MBBI->end(); 392 !ContainsFPCode && I != E; ++I) { 393 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { 394 if (I->getOperand(op).isRegister() && I->getOperand(op).isDef() && 395 MRegisterInfo::isVirtualRegister(I->getOperand(op).getReg()) && 396 RegMap->getRegClass(I->getOperand(0).getReg()) == 397 X86::RFPRegisterClass) { 398 ContainsFPCode = true; 399 break; 400 } 401 } 402 } 403 } while (!ContainsFPCode && &*(MBBI++) != BB); 404 405 // Check PHI nodes in successor blocks. These PHI's will be lowered to have 406 // a copy of the input value in this block. 407 if (!ContainsFPCode) { 408 // Final check, check LLVM BB's that are successors to the LLVM BB 409 // corresponding to BB for FP PHI nodes. 410 const BasicBlock *LLVMBB = BB->getBasicBlock(); 411 const PHINode *PN; 412 for (succ_const_iterator SI = succ_begin(LLVMBB), E = succ_end(LLVMBB); 413 !ContainsFPCode && SI != E; ++SI) { 414 for (BasicBlock::const_iterator II = SI->begin(); 415 (PN = dyn_cast<PHINode>(II)); ++II) { 416 if (PN->getType()->isFloatingPoint()) { 417 ContainsFPCode = true; 418 break; 419 } 420 } 421 } 422 } 423 424 // Finally, if we found any FP code, emit the FP_REG_KILL instruction. 425 if (ContainsFPCode) { 426 BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0); 427 ++NumFPKill; 428 } 429 } 430} 431 432/// EmitSpecialCodeForMain - Emit any code that needs to be executed only in 433/// the main function. 434void X86DAGToDAGISel::EmitSpecialCodeForMain(MachineBasicBlock *BB, 435 MachineFrameInfo *MFI) { 436 if (Subtarget->TargetType == X86Subtarget::isCygwin) 437 BuildMI(BB, X86::CALLpcrel32, 1).addExternalSymbol("__main"); 438 439 // Switch the FPU to 64-bit precision mode for better compatibility and speed. 440 int CWFrameIdx = MFI->CreateStackObject(2, 2); 441 addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx); 442 443 // Set the high part to be 64-bit precision. 444 addFrameReference(BuildMI(BB, X86::MOV8mi, 5), 445 CWFrameIdx, 1).addImm(2); 446 447 // Reload the modified control word now. 448 addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx); 449} 450 451void X86DAGToDAGISel::EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) { 452 // If this is main, emit special code for main. 453 MachineBasicBlock *BB = MF.begin(); 454 if (Fn.hasExternalLinkage() && Fn.getName() == "main") 455 EmitSpecialCodeForMain(BB, MF.getFrameInfo()); 456} 457 458/// MatchAddress - Add the specified node to the specified addressing mode, 459/// returning true if it cannot be done. This just pattern matches for the 460/// addressing mode 461bool X86DAGToDAGISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM, 462 bool isRoot) { 463 bool Available = false; 464 // If N has already been selected, reuse the result unless in some very 465 // specific cases. 466 std::map<SDOperand, SDOperand>::iterator CGMI= CodeGenMap.find(N.getValue(0)); 467 if (CGMI != CodeGenMap.end()) { 468 Available = true; 469 } 470 471 switch (N.getOpcode()) { 472 default: break; 473 case ISD::Constant: 474 AM.Disp += cast<ConstantSDNode>(N)->getValue(); 475 return false; 476 477 case X86ISD::Wrapper: 478 // If both base and index components have been picked, we can't fit 479 // the result available in the register in the addressing mode. Duplicate 480 // GlobalAddress or ConstantPool as displacement. 481 if (!Available || (AM.Base.Reg.Val && AM.IndexReg.Val)) { 482 if (ConstantPoolSDNode *CP = 483 dyn_cast<ConstantPoolSDNode>(N.getOperand(0))) { 484 if (AM.CP == 0) { 485 AM.CP = CP->get(); 486 AM.Align = CP->getAlignment(); 487 AM.Disp += CP->getOffset(); 488 return false; 489 } 490 } else if (GlobalAddressSDNode *G = 491 dyn_cast<GlobalAddressSDNode>(N.getOperand(0))) { 492 if (AM.GV == 0) { 493 AM.GV = G->getGlobal(); 494 AM.Disp += G->getOffset(); 495 return false; 496 } 497 } 498 } 499 break; 500 501 case ISD::FrameIndex: 502 if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) { 503 AM.BaseType = X86ISelAddressMode::FrameIndexBase; 504 AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex(); 505 return false; 506 } 507 break; 508 509 case ISD::SHL: 510 if (!Available && AM.IndexReg.Val == 0 && AM.Scale == 1) 511 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) { 512 unsigned Val = CN->getValue(); 513 if (Val == 1 || Val == 2 || Val == 3) { 514 AM.Scale = 1 << Val; 515 SDOperand ShVal = N.Val->getOperand(0); 516 517 // Okay, we know that we have a scale by now. However, if the scaled 518 // value is an add of something and a constant, we can fold the 519 // constant into the disp field here. 520 if (ShVal.Val->getOpcode() == ISD::ADD && ShVal.hasOneUse() && 521 isa<ConstantSDNode>(ShVal.Val->getOperand(1))) { 522 AM.IndexReg = ShVal.Val->getOperand(0); 523 ConstantSDNode *AddVal = 524 cast<ConstantSDNode>(ShVal.Val->getOperand(1)); 525 AM.Disp += AddVal->getValue() << Val; 526 } else { 527 AM.IndexReg = ShVal; 528 } 529 return false; 530 } 531 } 532 break; 533 534 case ISD::MUL: 535 // X*[3,5,9] -> X+X*[2,4,8] 536 if (!Available && 537 AM.BaseType == X86ISelAddressMode::RegBase && 538 AM.Base.Reg.Val == 0 && 539 AM.IndexReg.Val == 0) 540 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) 541 if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) { 542 AM.Scale = unsigned(CN->getValue())-1; 543 544 SDOperand MulVal = N.Val->getOperand(0); 545 SDOperand Reg; 546 547 // Okay, we know that we have a scale by now. However, if the scaled 548 // value is an add of something and a constant, we can fold the 549 // constant into the disp field here. 550 if (MulVal.Val->getOpcode() == ISD::ADD && MulVal.hasOneUse() && 551 isa<ConstantSDNode>(MulVal.Val->getOperand(1))) { 552 Reg = MulVal.Val->getOperand(0); 553 ConstantSDNode *AddVal = 554 cast<ConstantSDNode>(MulVal.Val->getOperand(1)); 555 AM.Disp += AddVal->getValue() * CN->getValue(); 556 } else { 557 Reg = N.Val->getOperand(0); 558 } 559 560 AM.IndexReg = AM.Base.Reg = Reg; 561 return false; 562 } 563 break; 564 565 case ISD::ADD: { 566 if (!Available) { 567 X86ISelAddressMode Backup = AM; 568 if (!MatchAddress(N.Val->getOperand(0), AM, false) && 569 !MatchAddress(N.Val->getOperand(1), AM, false)) 570 return false; 571 AM = Backup; 572 if (!MatchAddress(N.Val->getOperand(1), AM, false) && 573 !MatchAddress(N.Val->getOperand(0), AM, false)) 574 return false; 575 AM = Backup; 576 } 577 break; 578 } 579 580 case ISD::OR: { 581 if (!Available) { 582 X86ISelAddressMode Backup = AM; 583 // Look for (x << c1) | c2 where (c2 < c1) 584 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(0)); 585 if (CN && !MatchAddress(N.Val->getOperand(1), AM, false)) { 586 if (AM.GV == NULL && AM.Disp == 0 && CN->getValue() < AM.Scale) { 587 AM.Disp = CN->getValue(); 588 return false; 589 } 590 } 591 AM = Backup; 592 CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1)); 593 if (CN && !MatchAddress(N.Val->getOperand(0), AM, false)) { 594 if (AM.GV == NULL && AM.Disp == 0 && CN->getValue() < AM.Scale) { 595 AM.Disp = CN->getValue(); 596 return false; 597 } 598 } 599 AM = Backup; 600 } 601 break; 602 } 603 } 604 605 // Is the base register already occupied? 606 if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.Val) { 607 // If so, check to see if the scale index register is set. 608 if (AM.IndexReg.Val == 0) { 609 AM.IndexReg = N; 610 AM.Scale = 1; 611 return false; 612 } 613 614 // Otherwise, we cannot select it. 615 return true; 616 } 617 618 // Default, generate it as a register. 619 AM.BaseType = X86ISelAddressMode::RegBase; 620 AM.Base.Reg = N; 621 return false; 622} 623 624/// SelectAddr - returns true if it is able pattern match an addressing mode. 625/// It returns the operands which make up the maximal addressing mode it can 626/// match by reference. 627bool X86DAGToDAGISel::SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 628 SDOperand &Index, SDOperand &Disp) { 629 X86ISelAddressMode AM; 630 if (MatchAddress(N, AM)) 631 return false; 632 633 if (AM.BaseType == X86ISelAddressMode::RegBase) { 634 if (!AM.Base.Reg.Val) 635 AM.Base.Reg = CurDAG->getRegister(0, MVT::i32); 636 } 637 638 if (!AM.IndexReg.Val) 639 AM.IndexReg = CurDAG->getRegister(0, MVT::i32); 640 641 getAddressOperands(AM, Base, Scale, Index, Disp); 642 643 int Id = Base.Val ? Base.Val->getNodeId() : -1; 644 if (Id != -1) 645 setUnfoldable(Base.Val); 646 Id = Index.Val ? Index.Val->getNodeId() : -1; 647 if (Id != -1) 648 setUnfoldable(Index.Val); 649 650 return true; 651} 652 653/// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing 654/// mode it matches can be cost effectively emitted as an LEA instruction. 655bool X86DAGToDAGISel::SelectLEAAddr(SDOperand N, SDOperand &Base, 656 SDOperand &Scale, 657 SDOperand &Index, SDOperand &Disp) { 658 X86ISelAddressMode AM; 659 if (MatchAddress(N, AM)) 660 return false; 661 662 unsigned Complexity = 0; 663 if (AM.BaseType == X86ISelAddressMode::RegBase) 664 if (AM.Base.Reg.Val) 665 Complexity = 1; 666 else 667 AM.Base.Reg = CurDAG->getRegister(0, MVT::i32); 668 else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase) 669 Complexity = 4; 670 671 if (AM.IndexReg.Val) 672 Complexity++; 673 else 674 AM.IndexReg = CurDAG->getRegister(0, MVT::i32); 675 676 if (AM.Scale > 2) 677 Complexity += 2; 678 // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg 679 else if (AM.Scale > 1) 680 Complexity++; 681 682 // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA 683 // to a LEA. This is determined with some expermentation but is by no means 684 // optimal (especially for code size consideration). LEA is nice because of 685 // its three-address nature. Tweak the cost function again when we can run 686 // convertToThreeAddress() at register allocation time. 687 if (AM.GV || AM.CP) 688 Complexity += 2; 689 690 if (AM.Disp && (AM.Base.Reg.Val || AM.IndexReg.Val)) 691 Complexity++; 692 693 if (Complexity > 2) { 694 getAddressOperands(AM, Base, Scale, Index, Disp); 695 return true; 696 } 697 698 int Id = Base.Val ? Base.Val->getNodeId() : -1; 699 if (Id != -1) 700 setUnfoldable(Base.Val); 701 Id = Index.Val ? Index.Val->getNodeId() : -1; 702 if (Id != -1) 703 setUnfoldable(Index.Val); 704 705 return false; 706} 707 708bool X86DAGToDAGISel::TryFoldLoad(SDOperand P, SDOperand N, 709 SDOperand &Base, SDOperand &Scale, 710 SDOperand &Index, SDOperand &Disp) { 711 if (N.getOpcode() == ISD::LOAD && 712 N.hasOneUse() && 713 !CodeGenMap.count(N.getValue(0)) && 714 !IsFoldableBy(N.Val, P.Val)) 715 return SelectAddr(N.getOperand(1), Base, Scale, Index, Disp); 716 return false; 717} 718 719static bool isRegister0(SDOperand Op) { 720 if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op)) 721 return (R->getReg() == 0); 722 return false; 723} 724 725/// getGlobalBaseReg - Output the instructions required to put the 726/// base address to use for accessing globals into a register. 727/// 728SDOperand X86DAGToDAGISel::getGlobalBaseReg() { 729 if (!GlobalBaseReg) { 730 // Insert the set of GlobalBaseReg into the first MBB of the function 731 MachineBasicBlock &FirstMBB = BB->getParent()->front(); 732 MachineBasicBlock::iterator MBBI = FirstMBB.begin(); 733 SSARegMap *RegMap = BB->getParent()->getSSARegMap(); 734 // FIXME: when we get to LP64, we will need to create the appropriate 735 // type of register here. 736 GlobalBaseReg = RegMap->createVirtualRegister(X86::GR32RegisterClass); 737 BuildMI(FirstMBB, MBBI, X86::MovePCtoStack, 0); 738 BuildMI(FirstMBB, MBBI, X86::POP32r, 1, GlobalBaseReg); 739 } 740 return CurDAG->getRegister(GlobalBaseReg, MVT::i32); 741} 742 743static SDNode *FindCallStartFromCall(SDNode *Node) { 744 if (Node->getOpcode() == ISD::CALLSEQ_START) return Node; 745 assert(Node->getOperand(0).getValueType() == MVT::Other && 746 "Node doesn't have a token chain argument!"); 747 return FindCallStartFromCall(Node->getOperand(0).Val); 748} 749 750void X86DAGToDAGISel::Select(SDOperand &Result, SDOperand N) { 751 SDNode *Node = N.Val; 752 MVT::ValueType NVT = Node->getValueType(0); 753 unsigned Opc, MOpc; 754 unsigned Opcode = Node->getOpcode(); 755 756#ifndef NDEBUG 757 DEBUG(std::cerr << std::string(Indent, ' ')); 758 DEBUG(std::cerr << "Selecting: "); 759 DEBUG(Node->dump(CurDAG)); 760 DEBUG(std::cerr << "\n"); 761 Indent += 2; 762#endif 763 764 if (Opcode >= ISD::BUILTIN_OP_END && Opcode < X86ISD::FIRST_NUMBER) { 765 Result = N; 766#ifndef NDEBUG 767 DEBUG(std::cerr << std::string(Indent-2, ' ')); 768 DEBUG(std::cerr << "== "); 769 DEBUG(Node->dump(CurDAG)); 770 DEBUG(std::cerr << "\n"); 771 Indent -= 2; 772#endif 773 return; // Already selected. 774 } 775 776 std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(N); 777 if (CGMI != CodeGenMap.end()) { 778 Result = CGMI->second; 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 switch (Opcode) { 790 default: break; 791 case X86ISD::GlobalBaseReg: 792 Result = getGlobalBaseReg(); 793 return; 794 795 case ISD::ADD: { 796 // Turn ADD X, c to MOV32ri X+c. This cannot be done with tblgen'd 797 // code and is matched first so to prevent it from being turned into 798 // LEA32r X+c. 799 SDOperand N0 = N.getOperand(0); 800 SDOperand N1 = N.getOperand(1); 801 if (N.Val->getValueType(0) == MVT::i32 && 802 N0.getOpcode() == X86ISD::Wrapper && 803 N1.getOpcode() == ISD::Constant) { 804 unsigned Offset = (unsigned)cast<ConstantSDNode>(N1)->getValue(); 805 SDOperand C(0, 0); 806 // TODO: handle ExternalSymbolSDNode. 807 if (GlobalAddressSDNode *G = 808 dyn_cast<GlobalAddressSDNode>(N0.getOperand(0))) { 809 C = CurDAG->getTargetGlobalAddress(G->getGlobal(), MVT::i32, 810 G->getOffset() + Offset); 811 } else if (ConstantPoolSDNode *CP = 812 dyn_cast<ConstantPoolSDNode>(N0.getOperand(0))) { 813 C = CurDAG->getTargetConstantPool(CP->get(), MVT::i32, 814 CP->getAlignment(), 815 CP->getOffset()+Offset); 816 } 817 818 if (C.Val) { 819 if (N.Val->hasOneUse()) { 820 Result = CurDAG->SelectNodeTo(N.Val, X86::MOV32ri, MVT::i32, C); 821 } else { 822 SDNode *ResNode = CurDAG->getTargetNode(X86::MOV32ri, MVT::i32, C); 823 Result = CodeGenMap[N] = SDOperand(ResNode, 0); 824 } 825 return; 826 } 827 } 828 829 // Other cases are handled by auto-generated code. 830 break; 831 } 832 833 case ISD::MULHU: 834 case ISD::MULHS: { 835 if (Opcode == ISD::MULHU) 836 switch (NVT) { 837 default: assert(0 && "Unsupported VT!"); 838 case MVT::i8: Opc = X86::MUL8r; MOpc = X86::MUL8m; break; 839 case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break; 840 case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break; 841 } 842 else 843 switch (NVT) { 844 default: assert(0 && "Unsupported VT!"); 845 case MVT::i8: Opc = X86::IMUL8r; MOpc = X86::IMUL8m; break; 846 case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break; 847 case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break; 848 } 849 850 unsigned LoReg, HiReg; 851 switch (NVT) { 852 default: assert(0 && "Unsupported VT!"); 853 case MVT::i8: LoReg = X86::AL; HiReg = X86::AH; break; 854 case MVT::i16: LoReg = X86::AX; HiReg = X86::DX; break; 855 case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break; 856 } 857 858 SDOperand N0 = Node->getOperand(0); 859 SDOperand N1 = Node->getOperand(1); 860 861 bool foldedLoad = false; 862 SDOperand Tmp0, Tmp1, Tmp2, Tmp3; 863 foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3); 864 // MULHU and MULHS are commmutative 865 if (!foldedLoad) { 866 foldedLoad = TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3); 867 if (foldedLoad) { 868 N0 = Node->getOperand(1); 869 N1 = Node->getOperand(0); 870 } 871 } 872 873 SDOperand Chain; 874 if (foldedLoad) 875 Select(Chain, N1.getOperand(0)); 876 else 877 Chain = CurDAG->getEntryNode(); 878 879 SDOperand InFlag(0, 0); 880 Select(N0, N0); 881 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT), 882 N0, InFlag); 883 InFlag = Chain.getValue(1); 884 885 if (foldedLoad) { 886 Select(Tmp0, Tmp0); 887 Select(Tmp1, Tmp1); 888 Select(Tmp2, Tmp2); 889 Select(Tmp3, Tmp3); 890 SDNode *CNode = 891 CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1, 892 Tmp2, Tmp3, Chain, InFlag); 893 Chain = SDOperand(CNode, 0); 894 InFlag = SDOperand(CNode, 1); 895 } else { 896 Select(N1, N1); 897 InFlag = 898 SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0); 899 } 900 901 Result = CurDAG->getCopyFromReg(Chain, HiReg, NVT, InFlag); 902 CodeGenMap[N.getValue(0)] = Result; 903 if (foldedLoad) { 904 CodeGenMap[N1.getValue(1)] = Result.getValue(1); 905 AddHandleReplacement(N1.Val, 1, Result.Val, 1); 906 } 907 908#ifndef NDEBUG 909 DEBUG(std::cerr << std::string(Indent-2, ' ')); 910 DEBUG(std::cerr << "== "); 911 DEBUG(Result.Val->dump(CurDAG)); 912 DEBUG(std::cerr << "\n"); 913 Indent -= 2; 914#endif 915 return; 916 } 917 918 case ISD::SDIV: 919 case ISD::UDIV: 920 case ISD::SREM: 921 case ISD::UREM: { 922 bool isSigned = Opcode == ISD::SDIV || Opcode == ISD::SREM; 923 bool isDiv = Opcode == ISD::SDIV || Opcode == ISD::UDIV; 924 if (!isSigned) 925 switch (NVT) { 926 default: assert(0 && "Unsupported VT!"); 927 case MVT::i8: Opc = X86::DIV8r; MOpc = X86::DIV8m; break; 928 case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break; 929 case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break; 930 } 931 else 932 switch (NVT) { 933 default: assert(0 && "Unsupported VT!"); 934 case MVT::i8: Opc = X86::IDIV8r; MOpc = X86::IDIV8m; break; 935 case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break; 936 case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break; 937 } 938 939 unsigned LoReg, HiReg; 940 unsigned ClrOpcode, SExtOpcode; 941 switch (NVT) { 942 default: assert(0 && "Unsupported VT!"); 943 case MVT::i8: 944 LoReg = X86::AL; HiReg = X86::AH; 945 ClrOpcode = X86::MOV8r0; 946 SExtOpcode = X86::CBW; 947 break; 948 case MVT::i16: 949 LoReg = X86::AX; HiReg = X86::DX; 950 ClrOpcode = X86::MOV16r0; 951 SExtOpcode = X86::CWD; 952 break; 953 case MVT::i32: 954 LoReg = X86::EAX; HiReg = X86::EDX; 955 ClrOpcode = X86::MOV32r0; 956 SExtOpcode = X86::CDQ; 957 break; 958 } 959 960 SDOperand N0 = Node->getOperand(0); 961 SDOperand N1 = Node->getOperand(1); 962 963 bool foldedLoad = false; 964 SDOperand Tmp0, Tmp1, Tmp2, Tmp3; 965 foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3); 966 SDOperand Chain; 967 if (foldedLoad) 968 Select(Chain, N1.getOperand(0)); 969 else 970 Chain = CurDAG->getEntryNode(); 971 972 SDOperand InFlag(0, 0); 973 Select(N0, N0); 974 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT), 975 N0, InFlag); 976 InFlag = Chain.getValue(1); 977 978 if (isSigned) { 979 // Sign extend the low part into the high part. 980 InFlag = 981 SDOperand(CurDAG->getTargetNode(SExtOpcode, MVT::Flag, InFlag), 0); 982 } else { 983 // Zero out the high part, effectively zero extending the input. 984 SDOperand ClrNode = SDOperand(CurDAG->getTargetNode(ClrOpcode, NVT), 0); 985 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(HiReg, NVT), 986 ClrNode, InFlag); 987 InFlag = Chain.getValue(1); 988 } 989 990 if (foldedLoad) { 991 Select(Tmp0, Tmp0); 992 Select(Tmp1, Tmp1); 993 Select(Tmp2, Tmp2); 994 Select(Tmp3, Tmp3); 995 SDNode *CNode = 996 CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1, 997 Tmp2, Tmp3, Chain, InFlag); 998 Chain = SDOperand(CNode, 0); 999 InFlag = SDOperand(CNode, 1); 1000 } else { 1001 Select(N1, N1); 1002 InFlag = 1003 SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0); 1004 } 1005 1006 Result = CurDAG->getCopyFromReg(Chain, isDiv ? LoReg : HiReg, 1007 NVT, InFlag); 1008 CodeGenMap[N.getValue(0)] = Result; 1009 if (foldedLoad) { 1010 CodeGenMap[N1.getValue(1)] = Result.getValue(1); 1011 AddHandleReplacement(N1.Val, 1, Result.Val, 1); 1012 } 1013 1014#ifndef NDEBUG 1015 DEBUG(std::cerr << std::string(Indent-2, ' ')); 1016 DEBUG(std::cerr << "== "); 1017 DEBUG(Result.Val->dump(CurDAG)); 1018 DEBUG(std::cerr << "\n"); 1019 Indent -= 2; 1020#endif 1021 return; 1022 } 1023 1024 case ISD::TRUNCATE: { 1025 if (NVT == MVT::i8) { 1026 unsigned Opc2; 1027 MVT::ValueType VT; 1028 switch (Node->getOperand(0).getValueType()) { 1029 default: assert(0 && "Unknown truncate!"); 1030 case MVT::i16: 1031 Opc = X86::MOV16to16_; 1032 VT = MVT::i16; 1033 Opc2 = X86::TRUNC_GR16_GR8; 1034 break; 1035 case MVT::i32: 1036 Opc = X86::MOV32to32_; 1037 VT = MVT::i32; 1038 Opc2 = X86::TRUNC_GR32_GR8; 1039 break; 1040 } 1041 1042 SDOperand Tmp0, Tmp1; 1043 Select(Tmp0, Node->getOperand(0)); 1044 Tmp1 = SDOperand(CurDAG->getTargetNode(Opc, VT, Tmp0), 0); 1045 Result = CodeGenMap[N] = 1046 SDOperand(CurDAG->getTargetNode(Opc2, NVT, Tmp1), 0); 1047 1048#ifndef NDEBUG 1049 DEBUG(std::cerr << std::string(Indent-2, ' ')); 1050 DEBUG(std::cerr << "== "); 1051 DEBUG(Result.Val->dump(CurDAG)); 1052 DEBUG(std::cerr << "\n"); 1053 Indent -= 2; 1054#endif 1055 return; 1056 } 1057 1058 break; 1059 } 1060 } 1061 1062 SelectCode(Result, N); 1063#ifndef NDEBUG 1064 DEBUG(std::cerr << std::string(Indent-2, ' ')); 1065 DEBUG(std::cerr << "=> "); 1066 DEBUG(Result.Val->dump(CurDAG)); 1067 DEBUG(std::cerr << "\n"); 1068 Indent -= 2; 1069#endif 1070} 1071 1072bool X86DAGToDAGISel:: 1073SelectInlineAsmMemoryOperand(const SDOperand &Op, char ConstraintCode, 1074 std::vector<SDOperand> &OutOps, SelectionDAG &DAG){ 1075 SDOperand Op0, Op1, Op2, Op3; 1076 switch (ConstraintCode) { 1077 case 'o': // offsetable ?? 1078 case 'v': // not offsetable ?? 1079 default: return true; 1080 case 'm': // memory 1081 if (!SelectAddr(Op, Op0, Op1, Op2, Op3)) 1082 return true; 1083 break; 1084 } 1085 1086 OutOps.resize(4); 1087 Select(OutOps[0], Op0); 1088 Select(OutOps[1], Op1); 1089 Select(OutOps[2], Op2); 1090 Select(OutOps[3], Op3); 1091 return false; 1092} 1093 1094/// createX86ISelDag - This pass converts a legalized DAG into a 1095/// X86-specific DAG, ready for instruction scheduling. 1096/// 1097FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM) { 1098 return new X86DAGToDAGISel(TM); 1099} 1100