LLVM API Documentation
00001 //===- X86ISelDAGToDAG.cpp - A DAG pattern matching inst selector for X86 -===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the Evan Cheng and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines a DAG pattern matching instruction selector for X86, 00011 // converting from a legalized dag to a X86 dag. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #define DEBUG_TYPE "isel" 00016 #include "X86.h" 00017 #include "X86InstrBuilder.h" 00018 #include "X86ISelLowering.h" 00019 #include "X86RegisterInfo.h" 00020 #include "X86Subtarget.h" 00021 #include "X86TargetMachine.h" 00022 #include "llvm/GlobalValue.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/Intrinsics.h" 00025 #include "llvm/Support/CFG.h" 00026 #include "llvm/CodeGen/MachineConstantPool.h" 00027 #include "llvm/CodeGen/MachineFunction.h" 00028 #include "llvm/CodeGen/MachineFrameInfo.h" 00029 #include "llvm/CodeGen/MachineInstrBuilder.h" 00030 #include "llvm/CodeGen/SSARegMap.h" 00031 #include "llvm/CodeGen/SelectionDAGISel.h" 00032 #include "llvm/Target/TargetMachine.h" 00033 #include "llvm/Support/Debug.h" 00034 #include "llvm/ADT/Statistic.h" 00035 #include <iostream> 00036 #include <set> 00037 using namespace llvm; 00038 00039 //===----------------------------------------------------------------------===// 00040 // Pattern Matcher Implementation 00041 //===----------------------------------------------------------------------===// 00042 00043 namespace { 00044 /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses 00045 /// SDOperand's instead of register numbers for the leaves of the matched 00046 /// tree. 00047 struct X86ISelAddressMode { 00048 enum { 00049 RegBase, 00050 FrameIndexBase, 00051 } BaseType; 00052 00053 struct { // This is really a union, discriminated by BaseType! 00054 SDOperand Reg; 00055 int FrameIndex; 00056 } Base; 00057 00058 unsigned Scale; 00059 SDOperand IndexReg; 00060 unsigned Disp; 00061 GlobalValue *GV; 00062 Constant *CP; 00063 unsigned Align; // CP alignment. 00064 00065 X86ISelAddressMode() 00066 : BaseType(RegBase), Scale(1), IndexReg(), Disp(0), GV(0), 00067 CP(0), Align(0) { 00068 } 00069 }; 00070 } 00071 00072 namespace { 00073 Statistic<> 00074 NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added"); 00075 00076 //===--------------------------------------------------------------------===// 00077 /// ISel - X86 specific code to select X86 machine instructions for 00078 /// SelectionDAG operations. 00079 /// 00080 class X86DAGToDAGISel : public SelectionDAGISel { 00081 /// ContainsFPCode - Every instruction we select that uses or defines a FP 00082 /// register should set this to true. 00083 bool ContainsFPCode; 00084 00085 /// X86Lowering - This object fully describes how to lower LLVM code to an 00086 /// X86-specific SelectionDAG. 00087 X86TargetLowering X86Lowering; 00088 00089 /// Subtarget - Keep a pointer to the X86Subtarget around so that we can 00090 /// make the right decision when generating code for different targets. 00091 const X86Subtarget *Subtarget; 00092 00093 unsigned GlobalBaseReg; 00094 public: 00095 X86DAGToDAGISel(X86TargetMachine &TM) 00096 : SelectionDAGISel(X86Lowering), 00097 X86Lowering(*TM.getTargetLowering()) { 00098 Subtarget = &TM.getSubtarget<X86Subtarget>(); 00099 } 00100 00101 virtual bool runOnFunction(Function &Fn) { 00102 // Make sure we re-emit a set of the global base reg if necessary 00103 GlobalBaseReg = 0; 00104 return SelectionDAGISel::runOnFunction(Fn); 00105 } 00106 00107 virtual const char *getPassName() const { 00108 return "X86 DAG->DAG Instruction Selection"; 00109 } 00110 00111 /// InstructionSelectBasicBlock - This callback is invoked by 00112 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen. 00113 virtual void InstructionSelectBasicBlock(SelectionDAG &DAG); 00114 00115 virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF); 00116 00117 // Include the pieces autogenerated from the target description. 00118 #include "X86GenDAGISel.inc" 00119 00120 private: 00121 void Select(SDOperand &Result, SDOperand N); 00122 00123 bool MatchAddress(SDOperand N, X86ISelAddressMode &AM, bool isRoot = true); 00124 bool SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 00125 SDOperand &Index, SDOperand &Disp); 00126 bool SelectLEAAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 00127 SDOperand &Index, SDOperand &Disp); 00128 bool TryFoldLoad(SDOperand P, SDOperand N, 00129 SDOperand &Base, SDOperand &Scale, 00130 SDOperand &Index, SDOperand &Disp); 00131 00132 inline void getAddressOperands(X86ISelAddressMode &AM, SDOperand &Base, 00133 SDOperand &Scale, SDOperand &Index, 00134 SDOperand &Disp) { 00135 Base = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ? 00136 CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, MVT::i32) : AM.Base.Reg; 00137 Scale = getI8Imm(AM.Scale); 00138 Index = AM.IndexReg; 00139 Disp = AM.GV ? CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp) 00140 : (AM.CP ? 00141 CurDAG->getTargetConstantPool(AM.CP, MVT::i32, AM.Align, AM.Disp) 00142 : getI32Imm(AM.Disp)); 00143 } 00144 00145 /// getI8Imm - Return a target constant with the specified value, of type 00146 /// i8. 00147 inline SDOperand getI8Imm(unsigned Imm) { 00148 return CurDAG->getTargetConstant(Imm, MVT::i8); 00149 } 00150 00151 /// getI16Imm - Return a target constant with the specified value, of type 00152 /// i16. 00153 inline SDOperand getI16Imm(unsigned Imm) { 00154 return CurDAG->getTargetConstant(Imm, MVT::i16); 00155 } 00156 00157 /// getI32Imm - Return a target constant with the specified value, of type 00158 /// i32. 00159 inline SDOperand getI32Imm(unsigned Imm) { 00160 return CurDAG->getTargetConstant(Imm, MVT::i32); 00161 } 00162 00163 /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC 00164 /// base register. Return the virtual register that holds this value. 00165 SDOperand getGlobalBaseReg(); 00166 00167 #ifndef NDEBUG 00168 unsigned Indent; 00169 #endif 00170 }; 00171 } 00172 00173 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel 00174 /// when it has created a SelectionDAG for us to codegen. 00175 void X86DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) { 00176 DEBUG(BB->dump()); 00177 MachineFunction::iterator FirstMBB = BB; 00178 00179 // Codegen the basic block. 00180 #ifndef NDEBUG 00181 DEBUG(std::cerr << "===== Instruction selection begins:\n"); 00182 Indent = 0; 00183 #endif 00184 DAG.setRoot(SelectRoot(DAG.getRoot())); 00185 #ifndef NDEBUG 00186 DEBUG(std::cerr << "===== Instruction selection ends:\n"); 00187 #endif 00188 CodeGenMap.clear(); 00189 DAG.RemoveDeadNodes(); 00190 00191 // Emit machine code to BB. 00192 ScheduleAndEmitDAG(DAG); 00193 00194 // If we are emitting FP stack code, scan the basic block to determine if this 00195 // block defines any FP values. If so, put an FP_REG_KILL instruction before 00196 // the terminator of the block. 00197 if (!Subtarget->hasSSE2()) { 00198 // Note that FP stack instructions *are* used in SSE code when returning 00199 // values, but these are not live out of the basic block, so we don't need 00200 // an FP_REG_KILL in this case either. 00201 bool ContainsFPCode = false; 00202 00203 // Scan all of the machine instructions in these MBBs, checking for FP 00204 // stores. 00205 MachineFunction::iterator MBBI = FirstMBB; 00206 do { 00207 for (MachineBasicBlock::iterator I = MBBI->begin(), E = MBBI->end(); 00208 !ContainsFPCode && I != E; ++I) { 00209 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) { 00210 if (I->getOperand(op).isRegister() && I->getOperand(op).isDef() && 00211 MRegisterInfo::isVirtualRegister(I->getOperand(op).getReg()) && 00212 RegMap->getRegClass(I->getOperand(0).getReg()) == 00213 X86::RFPRegisterClass) { 00214 ContainsFPCode = true; 00215 break; 00216 } 00217 } 00218 } 00219 } while (!ContainsFPCode && &*(MBBI++) != BB); 00220 00221 // Check PHI nodes in successor blocks. These PHI's will be lowered to have 00222 // a copy of the input value in this block. 00223 if (!ContainsFPCode) { 00224 // Final check, check LLVM BB's that are successors to the LLVM BB 00225 // corresponding to BB for FP PHI nodes. 00226 const BasicBlock *LLVMBB = BB->getBasicBlock(); 00227 const PHINode *PN; 00228 for (succ_const_iterator SI = succ_begin(LLVMBB), E = succ_end(LLVMBB); 00229 !ContainsFPCode && SI != E; ++SI) { 00230 for (BasicBlock::const_iterator II = SI->begin(); 00231 (PN = dyn_cast<PHINode>(II)); ++II) { 00232 if (PN->getType()->isFloatingPoint()) { 00233 ContainsFPCode = true; 00234 break; 00235 } 00236 } 00237 } 00238 } 00239 00240 // Finally, if we found any FP code, emit the FP_REG_KILL instruction. 00241 if (ContainsFPCode) { 00242 BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0); 00243 ++NumFPKill; 00244 } 00245 } 00246 } 00247 00248 /// EmitSpecialCodeForMain - Emit any code that needs to be executed only in 00249 /// the main function. 00250 static void EmitSpecialCodeForMain(MachineBasicBlock *BB, 00251 MachineFrameInfo *MFI) { 00252 // Switch the FPU to 64-bit precision mode for better compatibility and speed. 00253 int CWFrameIdx = MFI->CreateStackObject(2, 2); 00254 addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx); 00255 00256 // Set the high part to be 64-bit precision. 00257 addFrameReference(BuildMI(BB, X86::MOV8mi, 5), 00258 CWFrameIdx, 1).addImm(2); 00259 00260 // Reload the modified control word now. 00261 addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx); 00262 } 00263 00264 void X86DAGToDAGISel::EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) { 00265 // If this is main, emit special code for main. 00266 MachineBasicBlock *BB = MF.begin(); 00267 if (Fn.hasExternalLinkage() && Fn.getName() == "main") 00268 EmitSpecialCodeForMain(BB, MF.getFrameInfo()); 00269 } 00270 00271 /// MatchAddress - Add the specified node to the specified addressing mode, 00272 /// returning true if it cannot be done. This just pattern matches for the 00273 /// addressing mode 00274 bool X86DAGToDAGISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM, 00275 bool isRoot) { 00276 bool Available = false; 00277 // If N has already been selected, reuse the result unless in some very 00278 // specific cases. 00279 std::map<SDOperand, SDOperand>::iterator CGMI= CodeGenMap.find(N.getValue(0)); 00280 if (CGMI != CodeGenMap.end()) { 00281 Available = true; 00282 } 00283 00284 switch (N.getOpcode()) { 00285 default: break; 00286 case ISD::Constant: 00287 AM.Disp += cast<ConstantSDNode>(N)->getValue(); 00288 return false; 00289 00290 case X86ISD::Wrapper: 00291 // If both base and index components have been picked, we can't fit 00292 // the result available in the register in the addressing mode. Duplicate 00293 // GlobalAddress or ConstantPool as displacement. 00294 if (!Available || (AM.Base.Reg.Val && AM.IndexReg.Val)) { 00295 if (ConstantPoolSDNode *CP = 00296 dyn_cast<ConstantPoolSDNode>(N.getOperand(0))) { 00297 if (AM.CP == 0) { 00298 AM.CP = CP->get(); 00299 AM.Align = CP->getAlignment(); 00300 AM.Disp += CP->getOffset(); 00301 return false; 00302 } 00303 } else if (GlobalAddressSDNode *G = 00304 dyn_cast<GlobalAddressSDNode>(N.getOperand(0))) { 00305 if (AM.GV == 0) { 00306 AM.GV = G->getGlobal(); 00307 AM.Disp += G->getOffset(); 00308 return false; 00309 } 00310 } 00311 } 00312 break; 00313 00314 case ISD::FrameIndex: 00315 if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) { 00316 AM.BaseType = X86ISelAddressMode::FrameIndexBase; 00317 AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex(); 00318 return false; 00319 } 00320 break; 00321 00322 case ISD::SHL: 00323 if (!Available && AM.IndexReg.Val == 0 && AM.Scale == 1) 00324 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) { 00325 unsigned Val = CN->getValue(); 00326 if (Val == 1 || Val == 2 || Val == 3) { 00327 AM.Scale = 1 << Val; 00328 SDOperand ShVal = N.Val->getOperand(0); 00329 00330 // Okay, we know that we have a scale by now. However, if the scaled 00331 // value is an add of something and a constant, we can fold the 00332 // constant into the disp field here. 00333 if (ShVal.Val->getOpcode() == ISD::ADD && ShVal.hasOneUse() && 00334 isa<ConstantSDNode>(ShVal.Val->getOperand(1))) { 00335 AM.IndexReg = ShVal.Val->getOperand(0); 00336 ConstantSDNode *AddVal = 00337 cast<ConstantSDNode>(ShVal.Val->getOperand(1)); 00338 AM.Disp += AddVal->getValue() << Val; 00339 } else { 00340 AM.IndexReg = ShVal; 00341 } 00342 return false; 00343 } 00344 } 00345 break; 00346 00347 case ISD::MUL: 00348 // X*[3,5,9] -> X+X*[2,4,8] 00349 if (!Available && 00350 AM.BaseType == X86ISelAddressMode::RegBase && 00351 AM.Base.Reg.Val == 0 && 00352 AM.IndexReg.Val == 0) 00353 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) 00354 if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) { 00355 AM.Scale = unsigned(CN->getValue())-1; 00356 00357 SDOperand MulVal = N.Val->getOperand(0); 00358 SDOperand Reg; 00359 00360 // Okay, we know that we have a scale by now. However, if the scaled 00361 // value is an add of something and a constant, we can fold the 00362 // constant into the disp field here. 00363 if (MulVal.Val->getOpcode() == ISD::ADD && MulVal.hasOneUse() && 00364 isa<ConstantSDNode>(MulVal.Val->getOperand(1))) { 00365 Reg = MulVal.Val->getOperand(0); 00366 ConstantSDNode *AddVal = 00367 cast<ConstantSDNode>(MulVal.Val->getOperand(1)); 00368 AM.Disp += AddVal->getValue() * CN->getValue(); 00369 } else { 00370 Reg = N.Val->getOperand(0); 00371 } 00372 00373 AM.IndexReg = AM.Base.Reg = Reg; 00374 return false; 00375 } 00376 break; 00377 00378 case ISD::ADD: { 00379 if (!Available) { 00380 X86ISelAddressMode Backup = AM; 00381 if (!MatchAddress(N.Val->getOperand(0), AM, false) && 00382 !MatchAddress(N.Val->getOperand(1), AM, false)) 00383 return false; 00384 AM = Backup; 00385 if (!MatchAddress(N.Val->getOperand(1), AM, false) && 00386 !MatchAddress(N.Val->getOperand(0), AM, false)) 00387 return false; 00388 AM = Backup; 00389 } 00390 break; 00391 } 00392 } 00393 00394 // Is the base register already occupied? 00395 if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.Val) { 00396 // If so, check to see if the scale index register is set. 00397 if (AM.IndexReg.Val == 0) { 00398 AM.IndexReg = N; 00399 AM.Scale = 1; 00400 return false; 00401 } 00402 00403 // Otherwise, we cannot select it. 00404 return true; 00405 } 00406 00407 // Default, generate it as a register. 00408 AM.BaseType = X86ISelAddressMode::RegBase; 00409 AM.Base.Reg = N; 00410 return false; 00411 } 00412 00413 /// SelectAddr - returns true if it is able pattern match an addressing mode. 00414 /// It returns the operands which make up the maximal addressing mode it can 00415 /// match by reference. 00416 bool X86DAGToDAGISel::SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale, 00417 SDOperand &Index, SDOperand &Disp) { 00418 X86ISelAddressMode AM; 00419 if (MatchAddress(N, AM)) 00420 return false; 00421 00422 if (AM.BaseType == X86ISelAddressMode::RegBase) { 00423 if (!AM.Base.Reg.Val) 00424 AM.Base.Reg = CurDAG->getRegister(0, MVT::i32); 00425 } 00426 00427 if (!AM.IndexReg.Val) 00428 AM.IndexReg = CurDAG->getRegister(0, MVT::i32); 00429 00430 getAddressOperands(AM, Base, Scale, Index, Disp); 00431 00432 return true; 00433 } 00434 00435 /// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing 00436 /// mode it matches can be cost effectively emitted as an LEA instruction. 00437 /// For X86, it always is unless it's just a (Reg + const). 00438 bool X86DAGToDAGISel::SelectLEAAddr(SDOperand N, SDOperand &Base, 00439 SDOperand &Scale, 00440 SDOperand &Index, SDOperand &Disp) { 00441 X86ISelAddressMode AM; 00442 if (MatchAddress(N, AM)) 00443 return false; 00444 00445 unsigned Complexity = 0; 00446 if (AM.BaseType == X86ISelAddressMode::RegBase) 00447 if (AM.Base.Reg.Val) 00448 Complexity = 1; 00449 else 00450 AM.Base.Reg = CurDAG->getRegister(0, MVT::i32); 00451 else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase) 00452 Complexity = 4; 00453 00454 if (AM.IndexReg.Val) 00455 Complexity++; 00456 else 00457 AM.IndexReg = CurDAG->getRegister(0, MVT::i32); 00458 00459 if (AM.Scale > 2) 00460 Complexity += 2; 00461 // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg 00462 else if (AM.Scale > 1) 00463 Complexity++; 00464 00465 // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA 00466 // to a LEA. This is determined with some expermentation but is by no means 00467 // optimal (especially for code size consideration). LEA is nice because of 00468 // its three-address nature. Tweak the cost function again when we can run 00469 // convertToThreeAddress() at register allocation time. 00470 if (AM.GV || AM.CP) 00471 Complexity += 2; 00472 00473 if (AM.Disp && (AM.Base.Reg.Val || AM.IndexReg.Val)) 00474 Complexity++; 00475 00476 if (Complexity > 2) { 00477 getAddressOperands(AM, Base, Scale, Index, Disp); 00478 return true; 00479 } 00480 00481 return false; 00482 } 00483 00484 bool X86DAGToDAGISel::TryFoldLoad(SDOperand P, SDOperand N, 00485 SDOperand &Base, SDOperand &Scale, 00486 SDOperand &Index, SDOperand &Disp) { 00487 if (N.getOpcode() == ISD::LOAD && 00488 N.hasOneUse() && 00489 !CodeGenMap.count(N.getValue(0)) && 00490 (P.getNumOperands() == 1 || !isNonImmUse(P.Val, N.Val))) 00491 return SelectAddr(N.getOperand(1), Base, Scale, Index, Disp); 00492 return false; 00493 } 00494 00495 static bool isRegister0(SDOperand Op) { 00496 if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op)) 00497 return (R->getReg() == 0); 00498 return false; 00499 } 00500 00501 /// getGlobalBaseReg - Output the instructions required to put the 00502 /// base address to use for accessing globals into a register. 00503 /// 00504 SDOperand X86DAGToDAGISel::getGlobalBaseReg() { 00505 if (!GlobalBaseReg) { 00506 // Insert the set of GlobalBaseReg into the first MBB of the function 00507 MachineBasicBlock &FirstMBB = BB->getParent()->front(); 00508 MachineBasicBlock::iterator MBBI = FirstMBB.begin(); 00509 SSARegMap *RegMap = BB->getParent()->getSSARegMap(); 00510 // FIXME: when we get to LP64, we will need to create the appropriate 00511 // type of register here. 00512 GlobalBaseReg = RegMap->createVirtualRegister(X86::R32RegisterClass); 00513 BuildMI(FirstMBB, MBBI, X86::MovePCtoStack, 0); 00514 BuildMI(FirstMBB, MBBI, X86::POP32r, 1, GlobalBaseReg); 00515 } 00516 return CurDAG->getRegister(GlobalBaseReg, MVT::i32); 00517 } 00518 00519 void X86DAGToDAGISel::Select(SDOperand &Result, SDOperand N) { 00520 SDNode *Node = N.Val; 00521 MVT::ValueType NVT = Node->getValueType(0); 00522 unsigned Opc, MOpc; 00523 unsigned Opcode = Node->getOpcode(); 00524 00525 #ifndef NDEBUG 00526 DEBUG(std::cerr << std::string(Indent, ' ')); 00527 DEBUG(std::cerr << "Selecting: "); 00528 DEBUG(Node->dump(CurDAG)); 00529 DEBUG(std::cerr << "\n"); 00530 Indent += 2; 00531 #endif 00532 00533 if (Opcode >= ISD::BUILTIN_OP_END && Opcode < X86ISD::FIRST_NUMBER) { 00534 Result = N; 00535 #ifndef NDEBUG 00536 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00537 DEBUG(std::cerr << "== "); 00538 DEBUG(Node->dump(CurDAG)); 00539 DEBUG(std::cerr << "\n"); 00540 Indent -= 2; 00541 #endif 00542 return; // Already selected. 00543 } 00544 00545 std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(N); 00546 if (CGMI != CodeGenMap.end()) { 00547 Result = CGMI->second; 00548 #ifndef NDEBUG 00549 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00550 DEBUG(std::cerr << "== "); 00551 DEBUG(Result.Val->dump(CurDAG)); 00552 DEBUG(std::cerr << "\n"); 00553 Indent -= 2; 00554 #endif 00555 return; 00556 } 00557 00558 switch (Opcode) { 00559 default: break; 00560 case X86ISD::GlobalBaseReg: 00561 Result = getGlobalBaseReg(); 00562 return; 00563 00564 case ISD::ADD: { 00565 // Turn ADD X, c to MOV32ri X+c. This cannot be done with tblgen'd 00566 // code and is matched first so to prevent it from being turned into 00567 // LEA32r X+c. 00568 SDOperand N0 = N.getOperand(0); 00569 SDOperand N1 = N.getOperand(1); 00570 if (N.Val->getValueType(0) == MVT::i32 && 00571 N0.getOpcode() == X86ISD::Wrapper && 00572 N1.getOpcode() == ISD::Constant) { 00573 unsigned Offset = (unsigned)cast<ConstantSDNode>(N1)->getValue(); 00574 SDOperand C(0, 0); 00575 // TODO: handle ExternalSymbolSDNode. 00576 if (GlobalAddressSDNode *G = 00577 dyn_cast<GlobalAddressSDNode>(N0.getOperand(0))) { 00578 C = CurDAG->getTargetGlobalAddress(G->getGlobal(), MVT::i32, 00579 G->getOffset() + Offset); 00580 } else if (ConstantPoolSDNode *CP = 00581 dyn_cast<ConstantPoolSDNode>(N0.getOperand(0))) { 00582 C = CurDAG->getTargetConstantPool(CP->get(), MVT::i32, 00583 CP->getAlignment(), 00584 CP->getOffset()+Offset); 00585 } 00586 00587 if (C.Val) { 00588 if (N.Val->hasOneUse()) { 00589 Result = CurDAG->SelectNodeTo(N.Val, X86::MOV32ri, MVT::i32, C); 00590 } else { 00591 SDNode *ResNode = CurDAG->getTargetNode(X86::MOV32ri, MVT::i32, C); 00592 Result = CodeGenMap[N] = SDOperand(ResNode, 0); 00593 } 00594 return; 00595 } 00596 } 00597 00598 // Other cases are handled by auto-generated code. 00599 break; 00600 } 00601 00602 case ISD::MULHU: 00603 case ISD::MULHS: { 00604 if (Opcode == ISD::MULHU) 00605 switch (NVT) { 00606 default: assert(0 && "Unsupported VT!"); 00607 case MVT::i8: Opc = X86::MUL8r; MOpc = X86::MUL8m; break; 00608 case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break; 00609 case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break; 00610 } 00611 else 00612 switch (NVT) { 00613 default: assert(0 && "Unsupported VT!"); 00614 case MVT::i8: Opc = X86::IMUL8r; MOpc = X86::IMUL8m; break; 00615 case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break; 00616 case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break; 00617 } 00618 00619 unsigned LoReg, HiReg; 00620 switch (NVT) { 00621 default: assert(0 && "Unsupported VT!"); 00622 case MVT::i8: LoReg = X86::AL; HiReg = X86::AH; break; 00623 case MVT::i16: LoReg = X86::AX; HiReg = X86::DX; break; 00624 case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break; 00625 } 00626 00627 SDOperand N0 = Node->getOperand(0); 00628 SDOperand N1 = Node->getOperand(1); 00629 00630 bool foldedLoad = false; 00631 SDOperand Tmp0, Tmp1, Tmp2, Tmp3; 00632 foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3); 00633 // MULHU and MULHS are commmutative 00634 if (!foldedLoad) { 00635 foldedLoad = TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3); 00636 if (foldedLoad) { 00637 N0 = Node->getOperand(1); 00638 N1 = Node->getOperand(0); 00639 } 00640 } 00641 00642 SDOperand Chain; 00643 if (foldedLoad) 00644 Select(Chain, N1.getOperand(0)); 00645 else 00646 Chain = CurDAG->getEntryNode(); 00647 00648 SDOperand InFlag(0, 0); 00649 Select(N0, N0); 00650 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT), 00651 N0, InFlag); 00652 InFlag = Chain.getValue(1); 00653 00654 if (foldedLoad) { 00655 Select(Tmp0, Tmp0); 00656 Select(Tmp1, Tmp1); 00657 Select(Tmp2, Tmp2); 00658 Select(Tmp3, Tmp3); 00659 SDNode *CNode = 00660 CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1, 00661 Tmp2, Tmp3, Chain, InFlag); 00662 Chain = SDOperand(CNode, 0); 00663 InFlag = SDOperand(CNode, 1); 00664 } else { 00665 Select(N1, N1); 00666 InFlag = 00667 SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0); 00668 } 00669 00670 Result = CurDAG->getCopyFromReg(Chain, HiReg, NVT, InFlag); 00671 CodeGenMap[N.getValue(0)] = Result; 00672 if (foldedLoad) { 00673 CodeGenMap[N1.getValue(1)] = Result.getValue(1); 00674 AddHandleReplacement(N1.Val, 1, Result.Val, 1); 00675 } 00676 00677 #ifndef NDEBUG 00678 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00679 DEBUG(std::cerr << "== "); 00680 DEBUG(Result.Val->dump(CurDAG)); 00681 DEBUG(std::cerr << "\n"); 00682 Indent -= 2; 00683 #endif 00684 return; 00685 } 00686 00687 case ISD::SDIV: 00688 case ISD::UDIV: 00689 case ISD::SREM: 00690 case ISD::UREM: { 00691 bool isSigned = Opcode == ISD::SDIV || Opcode == ISD::SREM; 00692 bool isDiv = Opcode == ISD::SDIV || Opcode == ISD::UDIV; 00693 if (!isSigned) 00694 switch (NVT) { 00695 default: assert(0 && "Unsupported VT!"); 00696 case MVT::i8: Opc = X86::DIV8r; MOpc = X86::DIV8m; break; 00697 case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break; 00698 case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break; 00699 } 00700 else 00701 switch (NVT) { 00702 default: assert(0 && "Unsupported VT!"); 00703 case MVT::i8: Opc = X86::IDIV8r; MOpc = X86::IDIV8m; break; 00704 case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break; 00705 case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break; 00706 } 00707 00708 unsigned LoReg, HiReg; 00709 unsigned ClrOpcode, SExtOpcode; 00710 switch (NVT) { 00711 default: assert(0 && "Unsupported VT!"); 00712 case MVT::i8: 00713 LoReg = X86::AL; HiReg = X86::AH; 00714 ClrOpcode = X86::MOV8ri; 00715 SExtOpcode = X86::CBW; 00716 break; 00717 case MVT::i16: 00718 LoReg = X86::AX; HiReg = X86::DX; 00719 ClrOpcode = X86::MOV16ri; 00720 SExtOpcode = X86::CWD; 00721 break; 00722 case MVT::i32: 00723 LoReg = X86::EAX; HiReg = X86::EDX; 00724 ClrOpcode = X86::MOV32ri; 00725 SExtOpcode = X86::CDQ; 00726 break; 00727 } 00728 00729 SDOperand N0 = Node->getOperand(0); 00730 SDOperand N1 = Node->getOperand(1); 00731 00732 bool foldedLoad = false; 00733 SDOperand Tmp0, Tmp1, Tmp2, Tmp3; 00734 foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3); 00735 SDOperand Chain; 00736 if (foldedLoad) 00737 Select(Chain, N1.getOperand(0)); 00738 else 00739 Chain = CurDAG->getEntryNode(); 00740 00741 SDOperand InFlag(0, 0); 00742 Select(N0, N0); 00743 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT), 00744 N0, InFlag); 00745 InFlag = Chain.getValue(1); 00746 00747 if (isSigned) { 00748 // Sign extend the low part into the high part. 00749 InFlag = 00750 SDOperand(CurDAG->getTargetNode(SExtOpcode, MVT::Flag, InFlag), 0); 00751 } else { 00752 // Zero out the high part, effectively zero extending the input. 00753 SDOperand ClrNode = 00754 SDOperand(CurDAG->getTargetNode(ClrOpcode, NVT, 00755 CurDAG->getTargetConstant(0, NVT)), 0); 00756 Chain = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(HiReg, NVT), 00757 ClrNode, InFlag); 00758 InFlag = Chain.getValue(1); 00759 } 00760 00761 if (foldedLoad) { 00762 Select(Tmp0, Tmp0); 00763 Select(Tmp1, Tmp1); 00764 Select(Tmp2, Tmp2); 00765 Select(Tmp3, Tmp3); 00766 SDNode *CNode = 00767 CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1, 00768 Tmp2, Tmp3, Chain, InFlag); 00769 Chain = SDOperand(CNode, 0); 00770 InFlag = SDOperand(CNode, 1); 00771 } else { 00772 Select(N1, N1); 00773 InFlag = 00774 SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0); 00775 } 00776 00777 Result = CurDAG->getCopyFromReg(Chain, isDiv ? LoReg : HiReg, 00778 NVT, InFlag); 00779 CodeGenMap[N.getValue(0)] = Result; 00780 if (foldedLoad) { 00781 CodeGenMap[N1.getValue(1)] = Result.getValue(1); 00782 AddHandleReplacement(N1.Val, 1, Result.Val, 1); 00783 } 00784 00785 #ifndef NDEBUG 00786 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00787 DEBUG(std::cerr << "== "); 00788 DEBUG(Result.Val->dump(CurDAG)); 00789 DEBUG(std::cerr << "\n"); 00790 Indent -= 2; 00791 #endif 00792 return; 00793 } 00794 00795 case ISD::TRUNCATE: { 00796 unsigned Reg; 00797 MVT::ValueType VT; 00798 switch (Node->getOperand(0).getValueType()) { 00799 default: assert(0 && "Unknown truncate!"); 00800 case MVT::i16: Reg = X86::AX; Opc = X86::MOV16rr; VT = MVT::i16; break; 00801 case MVT::i32: Reg = X86::EAX; Opc = X86::MOV32rr; VT = MVT::i32; break; 00802 } 00803 SDOperand Tmp0, Tmp1; 00804 Select(Tmp0, Node->getOperand(0)); 00805 Select(Tmp1, SDOperand(CurDAG->getTargetNode(Opc, VT, Tmp0), 0)); 00806 SDOperand InFlag = SDOperand(0,0); 00807 Result = CurDAG->getCopyToReg(CurDAG->getEntryNode(), Reg, Tmp1, InFlag); 00808 SDOperand Chain = Result.getValue(0); 00809 InFlag = Result.getValue(1); 00810 00811 switch (NVT) { 00812 default: assert(0 && "Unknown truncate!"); 00813 case MVT::i8: Reg = X86::AL; Opc = X86::MOV8rr; VT = MVT::i8; break; 00814 case MVT::i16: Reg = X86::AX; Opc = X86::MOV16rr; VT = MVT::i16; break; 00815 } 00816 00817 Result = CurDAG->getCopyFromReg(Chain, Reg, VT, InFlag); 00818 if (N.Val->hasOneUse()) 00819 Result = CurDAG->SelectNodeTo(N.Val, Opc, VT, Result); 00820 else 00821 Result = CodeGenMap[N] = 00822 SDOperand(CurDAG->getTargetNode(Opc, VT, Result), 0); 00823 00824 #ifndef NDEBUG 00825 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00826 DEBUG(std::cerr << "== "); 00827 DEBUG(Result.Val->dump(CurDAG)); 00828 DEBUG(std::cerr << "\n"); 00829 Indent -= 2; 00830 #endif 00831 return; 00832 } 00833 } 00834 00835 SelectCode(Result, N); 00836 #ifndef NDEBUG 00837 DEBUG(std::cerr << std::string(Indent-2, ' ')); 00838 DEBUG(std::cerr << "=> "); 00839 DEBUG(Result.Val->dump(CurDAG)); 00840 DEBUG(std::cerr << "\n"); 00841 Indent -= 2; 00842 #endif 00843 } 00844 00845 /// createX86ISelDag - This pass converts a legalized DAG into a 00846 /// X86-specific DAG, ready for instruction scheduling. 00847 /// 00848 FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM) { 00849 return new X86DAGToDAGISel(TM); 00850 }