lib/Target/Sparc/SparcV8ISelSimple.cpp

   1 //===-- InstSelectSimple.cpp - A simple instruction selector for SparcV8 --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a simple peephole instruction selector for the V8 target
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "SparcV8.h"
  15 #include "SparcV8InstrInfo.h"
  16 #include "Support/Debug.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/IntrinsicLowering.h"
  19 #include "llvm/Pass.h"
  20 #include "llvm/Constants.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineConstantPool.h"
  24 #include "llvm/CodeGen/MachineFunction.h"
  25 #include "llvm/CodeGen/SSARegMap.h"
  26 #include "llvm/Target/TargetMachine.h"
  27 #include "llvm/Support/GetElementPtrTypeIterator.h"
  28 #include "llvm/Support/InstVisitor.h"
  29 #include "llvm/Support/CFG.h"
  30 using namespace llvm;
  31
  32 namespace {
  33   struct V8ISel : public FunctionPass, public InstVisitor<V8ISel> {
  34     TargetMachine &TM;
  35     MachineFunction *F;                 // The function we are compiling into
  36     MachineBasicBlock *BB;              // The current MBB we are compiling
  37
  38     std::map<Value*, unsigned> RegMap;  // Mapping between Val's and SSA Regs
  39
  40     // MBBMap - Mapping between LLVM BB -> Machine BB
  41     std::map<const BasicBlock*, MachineBasicBlock*> MBBMap;
  42
  43     V8ISel(TargetMachine &tm) : TM(tm), F(0), BB(0) {}
  44
  45     /// runOnFunction - Top level implementation of instruction selection for
  46     /// the entire function.
  47     ///
  48     bool runOnFunction(Function &Fn);
  49
  50     virtual const char *getPassName() const {
  51       return "SparcV8 Simple Instruction Selection";
  52     }
  53
  54     /// emitGEPOperation - Common code shared between visitGetElementPtrInst and
  55     /// constant expression GEP support.
  56     ///
  57     void emitGEPOperation(MachineBasicBlock *BB, MachineBasicBlock::iterator IP,
  58                           Value *Src, User::op_iterator IdxBegin,
  59                           User::op_iterator IdxEnd, unsigned TargetReg);
  60
  61     /// visitBasicBlock - This method is called when we are visiting a new basic
  62     /// block.  This simply creates a new MachineBasicBlock to emit code into
  63     /// and adds it to the current MachineFunction.  Subsequent visit* for
  64     /// instructions will be invoked for all instructions in the basic block.
  65     ///
  66     void visitBasicBlock(BasicBlock &LLVM_BB) {
  67       BB = MBBMap[&LLVM_BB];
  68     }
  69
  70     void visitBinaryOperator(Instruction &I);
  71     void visitShiftInst (ShiftInst &SI) { visitBinaryOperator (SI); }
  72     void visitSetCondInst(Instruction &I);
  73     void visitCallInst(CallInst &I);
  74     void visitReturnInst(ReturnInst &I);
  75     void visitBranchInst(BranchInst &I);
  76     void visitCastInst(CastInst &I);
  77     void visitLoadInst(LoadInst &I);
  78     void visitStoreInst(StoreInst &I);
  79     void visitPHINode(PHINode &I) {}      // PHI nodes handled by second pass
  80     void visitGetElementPtrInst(GetElementPtrInst &I);
  81     void visitAllocaInst(AllocaInst &I);
  82
  83
  84
  85     void visitInstruction(Instruction &I) {
  86       std::cerr << "Unhandled instruction: " << I;
  87       abort();
  88     }
  89
  90     /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
  91     /// function, lowering any calls to unknown intrinsic functions into the
  92     /// equivalent LLVM code.
  93     void LowerUnknownIntrinsicFunctionCalls(Function &F);
  94     void visitIntrinsicCall(Intrinsic::ID ID, CallInst &CI);
  95
  96     void LoadArgumentsToVirtualRegs(Function *F);
  97
  98     /// SelectPHINodes - Insert machine code to generate phis.  This is tricky
  99     /// because we have to generate our sources into the source basic blocks,
 100     /// not the current one.
 101     ///
 102     void SelectPHINodes();
 103
 104     /// copyConstantToRegister - Output the instructions required to put the
 105     /// specified constant into the specified register.
 106     ///
 107     void copyConstantToRegister(MachineBasicBlock *MBB,
 108                                 MachineBasicBlock::iterator IP,
 109                                 Constant *C, unsigned R);
 110
 111     /// makeAnotherReg - This method returns the next register number we haven't
 112     /// yet used.
 113     ///
 114     /// Long values are handled somewhat specially.  They are always allocated
 115     /// as pairs of 32 bit integer values.  The register number returned is the
 116     /// lower 32 bits of the long value, and the regNum+1 is the upper 32 bits
 117     /// of the long value.
 118     ///
 119     unsigned makeAnotherReg(const Type *Ty) {
 120       assert(dynamic_cast<const SparcV8RegisterInfo*>(TM.getRegisterInfo()) &&
 121              "Current target doesn't have SparcV8 reg info??");
 122       const SparcV8RegisterInfo *MRI =
 123         static_cast<const SparcV8RegisterInfo*>(TM.getRegisterInfo());
 124       if (Ty == Type::LongTy || Ty == Type::ULongTy) {
 125         const TargetRegisterClass *RC = MRI->getRegClassForType(Type::IntTy);
 126         // Create the lower part
 127         F->getSSARegMap()->createVirtualRegister(RC);
 128         // Create the upper part.
 129         return F->getSSARegMap()->createVirtualRegister(RC)-1;
 130       }
 131
 132       // Add the mapping of regnumber => reg class to MachineFunction
 133       const TargetRegisterClass *RC = MRI->getRegClassForType(Ty);
 134       return F->getSSARegMap()->createVirtualRegister(RC);
 135     }
 136
 137     unsigned getReg(Value &V) { return getReg (&V); } // allow refs.
 138     unsigned getReg(Value *V) {
 139       // Just append to the end of the current bb.
 140       MachineBasicBlock::iterator It = BB->end();
 141       return getReg(V, BB, It);
 142     }
 143     unsigned getReg(Value *V, MachineBasicBlock *MBB,
 144                     MachineBasicBlock::iterator IPt) {
 145       unsigned &Reg = RegMap[V];
 146       if (Reg == 0) {
 147         Reg = makeAnotherReg(V->getType());
 148         RegMap[V] = Reg;
 149       }
 150       // If this operand is a constant, emit the code to copy the constant into
 151       // the register here...
 152       //
 153       if (Constant *C = dyn_cast<Constant>(V)) {
 154         copyConstantToRegister(MBB, IPt, C, Reg);
 155         RegMap.erase(V);  // Assign a new name to this constant if ref'd again
 156       } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 157         // Move the address of the global into the register
 158         unsigned TmpReg = makeAnotherReg(V->getType());
 159         BuildMI (*MBB, IPt, V8::SETHIi, 1, TmpReg).addGlobalAddress (GV);
 160         BuildMI (*MBB, IPt, V8::ORri, 2, Reg).addReg (TmpReg)
 161           .addGlobalAddress (GV);
 162         RegMap.erase(V);  // Assign a new name to this address if ref'd again
 163       }
 164
 165       return Reg;
 166     }
 167
 168   };
 169 }
 170
 171 FunctionPass *llvm::createSparcV8SimpleInstructionSelector(TargetMachine &TM) {
 172   return new V8ISel(TM);
 173 }
 174
 175 enum TypeClass {
 176   cByte, cShort, cInt, cLong, cFloat, cDouble
 177 };
 178
 179 static TypeClass getClass (const Type *T) {
 180   switch (T->getTypeID()) {
 181     case Type::UByteTyID:  case Type::SByteTyID:  return cByte;
 182     case Type::UShortTyID: case Type::ShortTyID:  return cShort;
 183     case Type::PointerTyID:
 184     case Type::UIntTyID:   case Type::IntTyID:    return cInt;
 185     case Type::ULongTyID:  case Type::LongTyID:   return cLong;
 186     case Type::FloatTyID:                         return cFloat;
 187     case Type::DoubleTyID:                        return cDouble;
 188     default:
 189       assert (0 && "Type of unknown class passed to getClass?");
 190       return cByte;
 191   }
 192 }
 193 static TypeClass getClassB(const Type *T) {
 194   if (T == Type::BoolTy) return cByte;
 195   return getClass(T);
 196 }
 197
 198
 199
 200 /// copyConstantToRegister - Output the instructions required to put the
 201 /// specified constant into the specified register.
 202 ///
 203 void V8ISel::copyConstantToRegister(MachineBasicBlock *MBB,
 204                                     MachineBasicBlock::iterator IP,
 205                                     Constant *C, unsigned R) {
 206   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 207     switch (CE->getOpcode()) {
 208     case Instruction::GetElementPtr:
 209       emitGEPOperation(MBB, IP, CE->getOperand(0),
 210                        CE->op_begin()+1, CE->op_end(), R);
 211       return;
 212     default:
 213       std::cerr << "Copying this constant expr not yet handled: " << *CE;
 214       abort();
 215     }
 216   }
 217
 218   if (C->getType()->isIntegral ()) {
 219     uint64_t Val;
 220     unsigned Class = getClassB (C->getType ());
 221     if (Class == cLong) {
 222       unsigned TmpReg = makeAnotherReg (Type::IntTy);
 223       unsigned TmpReg2 = makeAnotherReg (Type::IntTy);
 224       // Copy the value into the register pair.
 225       // R = top(more-significant) half, R+1 = bottom(less-significant) half
 226       uint64_t Val = cast<ConstantInt>(C)->getRawValue();
 227       unsigned topHalf = Val & 0xffffffffU;
 228       unsigned bottomHalf = Val >> 32;
 229       unsigned HH = topHalf >> 10;
 230       unsigned HM = topHalf & 0x03ff;
 231       unsigned LM = bottomHalf >> 10;
 232       unsigned LO = bottomHalf & 0x03ff;
 233       BuildMI (*MBB, IP, V8::SETHIi, 1, TmpReg).addImm(HH);
 234       BuildMI (*MBB, IP, V8::ORri, 2, R).addReg (TmpReg)
 235         .addImm (HM);
 236       BuildMI (*MBB, IP, V8::SETHIi, 1, TmpReg2).addImm(LM);
 237       BuildMI (*MBB, IP, V8::ORri, 2, R+1).addReg (TmpReg2)
 238         .addImm (LO);
 239       return;
 240     }
 241
 242     assert(Class <= cInt && "Type not handled yet!");
 243
 244     if (C->getType() == Type::BoolTy) {
 245       Val = (C == ConstantBool::True);
 246     } else {
 247       ConstantInt *CI = dyn_cast<ConstantInt> (C);
 248       Val = CI->getRawValue ();
 249     }
 250     switch (Class) {
 251       case cByte:
 252         BuildMI (*MBB, IP, V8::ORri, 2, R).addReg (V8::G0).addImm((uint8_t)Val);
 253         return;
 254       case cShort: {
 255         unsigned TmpReg = makeAnotherReg (C->getType ());
 256         BuildMI (*MBB, IP, V8::SETHIi, 1, TmpReg)
 257           .addImm (((uint16_t) Val) >> 10);
 258         BuildMI (*MBB, IP, V8::ORri, 2, R).addReg (TmpReg)
 259           .addImm (((uint16_t) Val) & 0x03ff);
 260         return;
 261       }
 262       case cInt: {
 263         unsigned TmpReg = makeAnotherReg (C->getType ());
 264         BuildMI (*MBB, IP, V8::SETHIi, 1, TmpReg).addImm(((uint32_t)Val) >> 10);
 265         BuildMI (*MBB, IP, V8::ORri, 2, R).addReg (TmpReg)
 266           .addImm (((uint32_t) Val) & 0x03ff);
 267         return;
 268       }
 269       default:
 270         std::cerr << "Offending constant: " << *C << "\n";
 271         assert (0 && "Can't copy this kind of constant into register yet");
 272         return;
 273     }
 274   } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 275     // We need to spill the constant to memory...
 276     MachineConstantPool *CP = F->getConstantPool();
 277     unsigned CPI = CP->getConstantPoolIndex(CFP);
 278     const Type *Ty = CFP->getType();
 279
 280     assert(Ty == Type::FloatTy || Ty == Type::DoubleTy && "Unknown FP type!");
 281     unsigned LoadOpcode = Ty == Type::FloatTy ? V8::LDFmr : V8::LDDFmr;
 282     BuildMI (*MBB, IP, LoadOpcode, 2, R).addConstantPoolIndex (CPI).addSImm (0);
 283   } else if (isa<ConstantPointerNull>(C)) {
 284     // Copy zero (null pointer) to the register.
 285     BuildMI (*MBB, IP, V8::ORri, 2, R).addReg (V8::G0).addImm (0);
 286   } else if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C)) {
 287     // Copy it with a SETHI/OR pair; the JIT + asmwriter should recognize
 288     // that SETHI %reg,global == SETHI %reg,%hi(global) and
 289     // OR %reg,global,%reg == OR %reg,%lo(global),%reg.
 290     unsigned TmpReg = makeAnotherReg (C->getType ());
 291     BuildMI (*MBB, IP, V8::SETHIi, 1, TmpReg).addGlobalAddress (CPR->getValue());
 292     BuildMI (*MBB, IP, V8::ORri, 2, R).addReg (TmpReg)
 293       .addGlobalAddress (CPR->getValue ());
 294   } else {
 295     std::cerr << "Offending constant: " << *C << "\n";
 296     assert (0 && "Can't copy this kind of constant into register yet");
 297   }
 298 }
 299
 300 void V8ISel::LoadArgumentsToVirtualRegs (Function *F) {
 301   unsigned ArgOffset = 0;
 302   static const unsigned IncomingArgRegs[] = { V8::I0, V8::I1, V8::I2,
 303     V8::I3, V8::I4, V8::I5 };
 304   assert (F->asize () < 7
 305           && "Can't handle loading excess call args off the stack yet");
 306
 307   for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) {
 308     unsigned Reg = getReg(*I);
 309     switch (getClassB(I->getType())) {
 310     case cByte:
 311     case cShort:
 312     case cInt:
 313       BuildMI(BB, V8::ORrr, 2, Reg).addReg (V8::G0)
 314         .addReg (IncomingArgRegs[ArgOffset]);
 315       break;
 316     default:
 317       assert (0 && "Only <=32-bit, integral arguments currently handled");
 318       return;
 319     }
 320     ++ArgOffset;
 321   }
 322 }
 323
 324 void V8ISel::SelectPHINodes() {
 325   const TargetInstrInfo &TII = *TM.getInstrInfo();
 326   const Function &LF = *F->getFunction();  // The LLVM function...
 327   for (Function::const_iterator I = LF.begin(), E = LF.end(); I != E; ++I) {
 328     const BasicBlock *BB = I;
 329     MachineBasicBlock &MBB = *MBBMap[I];
 330
 331     // Loop over all of the PHI nodes in the LLVM basic block...
 332     MachineBasicBlock::iterator PHIInsertPoint = MBB.begin();
 333     for (BasicBlock::const_iterator I = BB->begin();
 334          PHINode *PN = const_cast<PHINode*>(dyn_cast<PHINode>(I)); ++I) {
 335
 336       // Create a new machine instr PHI node, and insert it.
 337       unsigned PHIReg = getReg(*PN);
 338       MachineInstr *PhiMI = BuildMI(MBB, PHIInsertPoint,
 339                                     V8::PHI, PN->getNumOperands(), PHIReg);
 340
 341       MachineInstr *LongPhiMI = 0;
 342       if (PN->getType() == Type::LongTy || PN->getType() == Type::ULongTy)
 343         LongPhiMI = BuildMI(MBB, PHIInsertPoint,
 344                             V8::PHI, PN->getNumOperands(), PHIReg+1);
 345
 346       // PHIValues - Map of blocks to incoming virtual registers.  We use this
 347       // so that we only initialize one incoming value for a particular block,
 348       // even if the block has multiple entries in the PHI node.
 349       //
 350       std::map<MachineBasicBlock*, unsigned> PHIValues;
 351
 352       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 353         MachineBasicBlock *PredMBB = 0;
 354         for (MachineBasicBlock::pred_iterator PI = MBB.pred_begin (),
 355              PE = MBB.pred_end (); PI != PE; ++PI)
 356           if (PN->getIncomingBlock(i) == (*PI)->getBasicBlock()) {
 357             PredMBB = *PI;
 358             break;
 359           }
 360         assert (PredMBB && "Couldn't find incoming machine-cfg edge for phi");
 361
 362         unsigned ValReg;
 363         std::map<MachineBasicBlock*, unsigned>::iterator EntryIt =
 364           PHIValues.lower_bound(PredMBB);
 365
 366         if (EntryIt != PHIValues.end() && EntryIt->first == PredMBB) {
 367           // We already inserted an initialization of the register for this
 368           // predecessor.  Recycle it.
 369           ValReg = EntryIt->second;
 370
 371         } else {
 372           // Get the incoming value into a virtual register.
 373           //
 374           Value *Val = PN->getIncomingValue(i);
 375
 376           // If this is a constant or GlobalValue, we may have to insert code
 377           // into the basic block to compute it into a virtual register.
 378           if ((isa<Constant>(Val) && !isa<ConstantExpr>(Val)) ||
 379               isa<GlobalValue>(Val)) {
 380             // Simple constants get emitted at the end of the basic block,
 381             // before any terminator instructions.  We "know" that the code to
 382             // move a constant into a register will never clobber any flags.
 383             ValReg = getReg(Val, PredMBB, PredMBB->getFirstTerminator());
 384           } else {
 385             // Because we don't want to clobber any values which might be in
 386             // physical registers with the computation of this constant (which
 387             // might be arbitrarily complex if it is a constant expression),
 388             // just insert the computation at the top of the basic block.
 389             MachineBasicBlock::iterator PI = PredMBB->begin();
 390
 391             // Skip over any PHI nodes though!
 392             while (PI != PredMBB->end() && PI->getOpcode() == V8::PHI)
 393               ++PI;
 394
 395             ValReg = getReg(Val, PredMBB, PI);
 396           }
 397
 398           // Remember that we inserted a value for this PHI for this predecessor
 399           PHIValues.insert(EntryIt, std::make_pair(PredMBB, ValReg));
 400         }
 401
 402         PhiMI->addRegOperand(ValReg);
 403         PhiMI->addMachineBasicBlockOperand(PredMBB);
 404         if (LongPhiMI) {
 405           LongPhiMI->addRegOperand(ValReg+1);
 406           LongPhiMI->addMachineBasicBlockOperand(PredMBB);
 407         }
 408       }
 409
 410       // Now that we emitted all of the incoming values for the PHI node, make
 411       // sure to reposition the InsertPoint after the PHI that we just added.
 412       // This is needed because we might have inserted a constant into this
 413       // block, right after the PHI's which is before the old insert point!
 414       PHIInsertPoint = LongPhiMI ? LongPhiMI : PhiMI;
 415       ++PHIInsertPoint;
 416     }
 417   }
 418 }
 419
 420 bool V8ISel::runOnFunction(Function &Fn) {
 421   // First pass over the function, lower any unknown intrinsic functions
 422   // with the IntrinsicLowering class.
 423   LowerUnknownIntrinsicFunctionCalls(Fn);
 424
 425   F = &MachineFunction::construct(&Fn, TM);
 426
 427   // Create all of the machine basic blocks for the function...
 428   for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
 429     F->getBasicBlockList().push_back(MBBMap[I] = new MachineBasicBlock(I));
 430
 431   BB = &F->front();
 432
 433   // Set up a frame object for the return address.  This is used by the
 434   // llvm.returnaddress & llvm.frameaddress intrinisics.
 435   //ReturnAddressIndex = F->getFrameInfo()->CreateFixedObject(4, -4);
 436
 437   // Copy incoming arguments off of the stack and out of fixed registers.
 438   LoadArgumentsToVirtualRegs(&Fn);
 439
 440   // Instruction select everything except PHI nodes
 441   visit(Fn);
 442
 443   // Select the PHI nodes
 444   SelectPHINodes();
 445
 446   RegMap.clear();
 447   MBBMap.clear();
 448   F = 0;
 449   // We always build a machine code representation for the function
 450   return true;
 451 }
 452
 453 void V8ISel::visitCastInst(CastInst &I) {
 454   unsigned SrcReg = getReg (I.getOperand (0));
 455   unsigned DestReg = getReg (I);
 456   const Type *oldTy = I.getOperand (0)->getType ();
 457   const Type *newTy = I.getType ();
 458   unsigned oldTyClass = getClassB (oldTy);
 459   unsigned newTyClass = getClassB (newTy);
 460
 461   if (oldTyClass < cLong && newTyClass < cLong) {
 462     if (oldTyClass >= newTyClass) {
 463       // Emit a reg->reg copy to do a equal-size or narrowing cast,
 464       // and do sign/zero extension (necessary if we change signedness).
 465       unsigned TmpReg1 = makeAnotherReg (newTy);
 466       unsigned TmpReg2 = makeAnotherReg (newTy);
 467       BuildMI (BB, V8::ORrr, 2, TmpReg1).addReg (V8::G0).addReg (SrcReg);
 468       unsigned shiftWidth = 32 - (8 * TM.getTargetData ().getTypeSize (newTy));
 469       BuildMI (BB, V8::SLLri, 2, TmpReg2).addZImm (shiftWidth).addReg(TmpReg1);
 470       if (newTy->isSigned ()) { // sign-extend with SRA
 471         BuildMI(BB, V8::SRAri, 2, DestReg).addZImm (shiftWidth).addReg(TmpReg2);
 472       } else { // zero-extend with SRL
 473         BuildMI(BB, V8::SRLri, 2, DestReg).addZImm (shiftWidth).addReg(TmpReg2);
 474       }
 475     } else {
 476       unsigned TmpReg1 = makeAnotherReg (oldTy);
 477       unsigned TmpReg2 = makeAnotherReg (newTy);
 478       unsigned TmpReg3 = makeAnotherReg (newTy);
 479       // Widening integer cast. Make sure it's fully sign/zero-extended
 480       // wrt the input type, then make sure it's fully sign/zero-extended wrt
 481       // the output type. Kind of stupid, but simple...
 482       unsigned shiftWidth = 32 - (8 * TM.getTargetData ().getTypeSize (oldTy));
 483       BuildMI (BB, V8::SLLri, 2, TmpReg1).addZImm (shiftWidth).addReg(SrcReg);
 484       if (oldTy->isSigned ()) { // sign-extend with SRA
 485         BuildMI(BB, V8::SRAri, 2, TmpReg2).addZImm (shiftWidth).addReg(TmpReg1);
 486       } else { // zero-extend with SRL
 487         BuildMI(BB, V8::SRLri, 2, TmpReg2).addZImm (shiftWidth).addReg(TmpReg1);
 488       }
 489       shiftWidth = 32 - (8 * TM.getTargetData ().getTypeSize (newTy));
 490       BuildMI (BB, V8::SLLri, 2, TmpReg3).addZImm (shiftWidth).addReg(TmpReg2);
 491       if (newTy->isSigned ()) { // sign-extend with SRA
 492         BuildMI(BB, V8::SRAri, 2, DestReg).addZImm (shiftWidth).addReg(TmpReg3);
 493       } else { // zero-extend with SRL
 494         BuildMI(BB, V8::SRLri, 2, DestReg).addZImm (shiftWidth).addReg(TmpReg3);
 495       }
 496     }
 497   } else {
 498     std::cerr << "Casts w/ long, fp, double still unsupported: " << I;
 499     abort ();
 500   }
 501 }
 502
 503 void V8ISel::visitLoadInst(LoadInst &I) {
 504   unsigned DestReg = getReg (I);
 505   unsigned PtrReg = getReg (I.getOperand (0));
 506   switch (getClassB (I.getType ())) {
 507    case cByte:
 508     if (I.getType ()->isSigned ())
 509       BuildMI (BB, V8::LDSBmr, 1, DestReg).addReg (PtrReg).addSImm(0);
 510     else
 511       BuildMI (BB, V8::LDUBmr, 1, DestReg).addReg (PtrReg).addSImm(0);
 512     return;
 513    case cShort:
 514     if (I.getType ()->isSigned ())
 515       BuildMI (BB, V8::LDSHmr, 1, DestReg).addReg (PtrReg).addSImm(0);
 516     else
 517       BuildMI (BB, V8::LDUHmr, 1, DestReg).addReg (PtrReg).addSImm(0);
 518     return;
 519    case cInt:
 520     BuildMI (BB, V8::LDmr, 1, DestReg).addReg (PtrReg).addSImm(0);
 521     return;
 522    case cLong:
 523     BuildMI (BB, V8::LDDmr, 1, DestReg).addReg (PtrReg).addSImm(0);
 524     return;
 525    default:
 526     std::cerr << "Load instruction not handled: " << I;
 527     abort ();
 528     return;
 529   }
 530 }
 531
 532 void V8ISel::visitStoreInst(StoreInst &I) {
 533   Value *SrcVal = I.getOperand (0);
 534   unsigned SrcReg = getReg (SrcVal);
 535   unsigned PtrReg = getReg (I.getOperand (1));
 536   switch (getClassB (SrcVal->getType ())) {
 537    case cByte:
 538     BuildMI (BB, V8::STBrm, 3).addReg (PtrReg).addSImm (0).addReg (SrcReg);
 539     return;
 540    case cShort:
 541     BuildMI (BB, V8::STHrm, 3).addReg (PtrReg).addSImm (0).addReg (SrcReg);
 542     return;
 543    case cInt:
 544     BuildMI (BB, V8::STrm, 3).addReg (PtrReg).addSImm (0).addReg (SrcReg);
 545     return;
 546    case cLong:
 547     BuildMI (BB, V8::STDrm, 3).addReg (PtrReg).addSImm (0).addReg (SrcReg);
 548     return;
 549    default:
 550     std::cerr << "Store instruction not handled: " << I;
 551     abort ();
 552     return;
 553   }
 554 }
 555
 556 void V8ISel::visitCallInst(CallInst &I) {
 557   MachineInstr *TheCall;
 558   // Is it an intrinsic function call?
 559   if (Function *F = I.getCalledFunction()) {
 560     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID()) {
 561       visitIntrinsicCall(ID, I);   // Special intrinsics are not handled here
 562       return;
 563     }
 564   }
 565
 566   // Deal with args
 567   assert (I.getNumOperands () < 8
 568           && "Can't handle pushing excess call args on the stack yet");
 569   static const unsigned OutgoingArgRegs[] = { V8::O0, V8::O1, V8::O2, V8::O3,
 570     V8::O4, V8::O5 };
 571   for (unsigned i = 1; i < 7; ++i)
 572     if (i < I.getNumOperands ()) {
 573       unsigned ArgReg = getReg (I.getOperand (i));
 574       // Schlep it over into the incoming arg register
 575       BuildMI (BB, V8::ORrr, 2, OutgoingArgRegs[i - 1]).addReg (V8::G0)
 576         .addReg (ArgReg);
 577     }
 578
 579   // Emit call instruction
 580   if (Function *F = I.getCalledFunction ()) {
 581     BuildMI (BB, V8::CALL, 1).addGlobalAddress (F, true);
 582   } else {  // Emit an indirect call...
 583     unsigned Reg = getReg (I.getCalledValue ());
 584     BuildMI (BB, V8::JMPLrr, 3, V8::O7).addReg (Reg).addReg (V8::G0);
 585   }
 586
 587   // Deal w/ return value: schlep it over into the destination register
 588   if (I.getType () == Type::VoidTy)
 589     return;
 590   unsigned DestReg = getReg (I);
 591   switch (getClass (I.getType ())) {
 592     case cByte:
 593     case cShort:
 594     case cInt:
 595       BuildMI (BB, V8::ORrr, 2, DestReg).addReg(V8::G0).addReg(V8::O0);
 596       break;
 597     case cFloat:
 598       BuildMI (BB, V8::FMOVS, 2, DestReg).addReg(V8::F0);
 599       break;
 600     default:
 601       std::cerr << "Return type of call instruction not handled: " << I;
 602       abort ();
 603   }
 604 }
 605
 606 void V8ISel::visitReturnInst(ReturnInst &I) {
 607   if (I.getNumOperands () == 1) {
 608     unsigned RetValReg = getReg (I.getOperand (0));
 609     switch (getClass (I.getOperand (0)->getType ())) {
 610       case cByte:
 611       case cShort:
 612       case cInt:
 613         // Schlep it over into i0 (where it will become o0 after restore).
 614         BuildMI (BB, V8::ORrr, 2, V8::I0).addReg(V8::G0).addReg(RetValReg);
 615         break;
 616       default:
 617         std::cerr << "Return instruction of this type not handled: " << I;
 618         abort ();
 619     }
 620   }
 621
 622   // Just emit a 'retl' instruction to return.
 623   BuildMI(BB, V8::RETL, 0);
 624   return;
 625 }
 626
 627 static inline BasicBlock *getBlockAfter(BasicBlock *BB) {
 628   Function::iterator I = BB; ++I;  // Get iterator to next block
 629   return I != BB->getParent()->end() ? &*I : 0;
 630 }
 631
 632 /// visitBranchInst - Handles conditional and unconditional branches.
 633 ///
 634 void V8ISel::visitBranchInst(BranchInst &I) {
 635   BasicBlock *takenSucc = I.getSuccessor (0);
 636   MachineBasicBlock *takenSuccMBB = MBBMap[takenSucc];
 637   BB->addSuccessor (takenSuccMBB);
 638   if (I.isConditional()) {  // conditional branch
 639     BasicBlock *notTakenSucc = I.getSuccessor (1);
 640     MachineBasicBlock *notTakenSuccMBB = MBBMap[notTakenSucc];
 641     BB->addSuccessor (notTakenSuccMBB);
 642
 643     // CondReg=(<condition>);
 644     // If (CondReg==0) goto notTakenSuccMBB;
 645     unsigned CondReg = getReg (I.getCondition ());
 646     BuildMI (BB, V8::CMPri, 2).addSImm (0).addReg (CondReg);
 647     BuildMI (BB, V8::BE, 1).addMBB (notTakenSuccMBB);
 648   }
 649   // goto takenSuccMBB;
 650   BuildMI (BB, V8::BA, 1).addMBB (takenSuccMBB);
 651 }
 652
 653 /// emitGEPOperation - Common code shared between visitGetElementPtrInst and
 654 /// constant expression GEP support.
 655 ///
 656 void V8ISel::emitGEPOperation (MachineBasicBlock *MBB,
 657                                MachineBasicBlock::iterator IP,
 658                                Value *Src, User::op_iterator IdxBegin,
 659                                User::op_iterator IdxEnd, unsigned TargetReg) {
 660   const TargetData &TD = TM.getTargetData ();
 661   const Type *Ty = Src->getType ();
 662   unsigned basePtrReg = getReg (Src);
 663
 664   // GEPs have zero or more indices; we must perform a struct access
 665   // or array access for each one.
 666   for (GetElementPtrInst::op_iterator oi = IdxBegin, oe = IdxEnd; oi != oe;
 667        ++oi) {
 668     Value *idx = *oi;
 669     unsigned nextBasePtrReg = makeAnotherReg (Type::UIntTy);
 670     if (const StructType *StTy = dyn_cast<StructType> (Ty)) {
 671       // It's a struct access.  idx is the index into the structure,
 672       // which names the field. Use the TargetData structure to
 673       // pick out what the layout of the structure is in memory.
 674       // Use the (constant) structure index's value to find the
 675       // right byte offset from the StructLayout class's list of
 676       // structure member offsets.
 677       unsigned fieldIndex = cast<ConstantUInt> (idx)->getValue ();
 678       unsigned memberOffset =
 679         TD.getStructLayout (StTy)->MemberOffsets[fieldIndex];
 680       // Emit an ADD to add memberOffset to the basePtr.
 681       BuildMI (*MBB, IP, V8::ADDri, 2,
 682                nextBasePtrReg).addReg (basePtrReg).addZImm (memberOffset);
 683       // The next type is the member of the structure selected by the
 684       // index.
 685       Ty = StTy->getElementType (fieldIndex);
 686     } else if (const SequentialType *SqTy = dyn_cast<SequentialType> (Ty)) {
 687       // It's an array or pointer access: [ArraySize x ElementType].
 688       // We want to add basePtrReg to (idxReg * sizeof ElementType). First, we
 689       // must find the size of the pointed-to type (Not coincidentally, the next
 690       // type is the type of the elements in the array).
 691       Ty = SqTy->getElementType ();
 692       unsigned elementSize = TD.getTypeSize (Ty);
 693       unsigned idxReg = getReg (idx, MBB, IP);
 694       unsigned OffsetReg = makeAnotherReg (Type::IntTy);
 695       unsigned elementSizeReg = makeAnotherReg (Type::UIntTy);
 696       BuildMI (*MBB, IP, V8::ORri, 2,
 697                elementSizeReg).addZImm (elementSize).addReg (V8::G0);
 698       // Emit a SMUL to multiply the register holding the index by
 699       // elementSize, putting the result in OffsetReg.
 700       BuildMI (*MBB, IP, V8::SMULrr, 2,
 701                OffsetReg).addReg (elementSizeReg).addReg (idxReg);
 702       // Emit an ADD to add OffsetReg to the basePtr.
 703       BuildMI (*MBB, IP, V8::ADDrr, 2,
 704                nextBasePtrReg).addReg (basePtrReg).addReg (OffsetReg);
 705     }
 706     basePtrReg = nextBasePtrReg;
 707   }
 708   // After we have processed all the indices, the result is left in
 709   // basePtrReg.  Move it to the register where we were expected to
 710   // put the answer.
 711   BuildMI (BB, V8::ORrr, 1, TargetReg).addReg (V8::G0).addReg (basePtrReg);
 712 }
 713
 714 void V8ISel::visitGetElementPtrInst (GetElementPtrInst &I) {
 715   unsigned outputReg = getReg (I);
 716   emitGEPOperation (BB, BB->end (), I.getOperand (0),
 717                     I.op_begin ()+1, I.op_end (), outputReg);
 718 }
 719
 720
 721 void V8ISel::visitBinaryOperator (Instruction &I) {
 722   unsigned DestReg = getReg (I);
 723   unsigned Op0Reg = getReg (I.getOperand (0));
 724   unsigned Op1Reg = getReg (I.getOperand (1));
 725
 726   unsigned ResultReg = DestReg;
 727   if (getClassB(I.getType()) != cInt)
 728     ResultReg = makeAnotherReg (I.getType ());
 729   unsigned OpCase = ~0;
 730
 731   // FIXME: support long, ulong, fp.
 732   switch (I.getOpcode ()) {
 733   case Instruction::Add: OpCase = 0; break;
 734   case Instruction::Sub: OpCase = 1; break;
 735   case Instruction::Mul: OpCase = 2; break;
 736   case Instruction::And: OpCase = 3; break;
 737   case Instruction::Or:  OpCase = 4; break;
 738   case Instruction::Xor: OpCase = 5; break;
 739   case Instruction::Shl: OpCase = 6; break;
 740   case Instruction::Shr: OpCase = 7+I.getType()->isSigned(); break;
 741
 742   case Instruction::Div:
 743   case Instruction::Rem: {
 744     unsigned Dest = ResultReg;
 745     if (I.getOpcode() == Instruction::Rem)
 746       Dest = makeAnotherReg(I.getType());
 747
 748     // FIXME: this is probably only right for 32 bit operands.
 749     if (I.getType ()->isSigned()) {
 750       unsigned Tmp = makeAnotherReg (I.getType ());
 751       // Sign extend into the Y register
 752       BuildMI (BB, V8::SRAri, 2, Tmp).addReg (Op0Reg).addZImm (31);
 753       BuildMI (BB, V8::WRrr, 2, V8::Y).addReg (Tmp).addReg (V8::G0);
 754       BuildMI (BB, V8::SDIVrr, 2, Dest).addReg (Op0Reg).addReg (Op1Reg);
 755     } else {
 756       // Zero extend into the Y register, ie, just set it to zero
 757       BuildMI (BB, V8::WRrr, 2, V8::Y).addReg (V8::G0).addReg (V8::G0);
 758       BuildMI (BB, V8::UDIVrr, 2, Dest).addReg (Op0Reg).addReg (Op1Reg);
 759     }
 760
 761     if (I.getOpcode() == Instruction::Rem) {
 762       unsigned Tmp = makeAnotherReg (I.getType ());
 763       BuildMI (BB, V8::SMULrr, 2, Tmp).addReg(Dest).addReg(Op1Reg);
 764       BuildMI (BB, V8::SUBrr, 2, ResultReg).addReg(Op0Reg).addReg(Tmp);
 765     }
 766     break;
 767   }
 768   default:
 769     visitInstruction (I);
 770     return;
 771   }
 772
 773   if (OpCase != ~0U) {
 774     static const unsigned Opcodes[] = {
 775       V8::ADDrr, V8::SUBrr, V8::SMULrr, V8::ANDrr, V8::ORrr, V8::XORrr,
 776       V8::SLLrr, V8::SRLrr, V8::SRArr
 777     };
 778     BuildMI (BB, Opcodes[OpCase], 2, ResultReg).addReg (Op0Reg).addReg (Op1Reg);
 779   }
 780
 781   switch (getClass (I.getType ())) {
 782     case cByte:
 783       if (I.getType ()->isSigned ()) { // add byte
 784         BuildMI (BB, V8::ANDri, 2, DestReg).addReg (ResultReg).addZImm (0xff);
 785       } else { // add ubyte
 786         unsigned TmpReg = makeAnotherReg (I.getType ());
 787         BuildMI (BB, V8::SLLri, 2, TmpReg).addReg (ResultReg).addZImm (24);
 788         BuildMI (BB, V8::SRAri, 2, DestReg).addReg (TmpReg).addZImm (24);
 789       }
 790       break;
 791     case cShort:
 792       if (I.getType ()->isSigned ()) { // add short
 793         unsigned TmpReg = makeAnotherReg (I.getType ());
 794         BuildMI (BB, V8::SLLri, 2, TmpReg).addReg (ResultReg).addZImm (16);
 795         BuildMI (BB, V8::SRAri, 2, DestReg).addReg (TmpReg).addZImm (16);
 796       } else { // add ushort
 797         unsigned TmpReg = makeAnotherReg (I.getType ());
 798         BuildMI (BB, V8::SLLri, 2, TmpReg).addReg (ResultReg).addZImm (16);
 799         BuildMI (BB, V8::SRLri, 2, DestReg).addReg (TmpReg).addZImm (16);
 800       }
 801       break;
 802     case cInt:
 803       // Nothing todo here.
 804       break;
 805     default:
 806       visitInstruction (I);
 807       return;
 808   }
 809 }
 810
 811 void V8ISel::visitSetCondInst(Instruction &I) {
 812   unsigned Op0Reg = getReg (I.getOperand (0));
 813   unsigned Op1Reg = getReg (I.getOperand (1));
 814   unsigned DestReg = getReg (I);
 815   const Type *Ty = I.getOperand (0)->getType ();
 816
 817   // Compare the two values.
 818   BuildMI(BB, V8::SUBCCrr, 2, V8::G0).addReg(Op0Reg).addReg(Op1Reg);
 819
 820   unsigned BranchIdx;
 821   switch (I.getOpcode()) {
 822   default: assert(0 && "Unknown setcc instruction!");
 823   case Instruction::SetEQ: BranchIdx = 0; break;
 824   case Instruction::SetNE: BranchIdx = 1; break;
 825   case Instruction::SetLT: BranchIdx = 2; break;
 826   case Instruction::SetGT: BranchIdx = 3; break;
 827   case Instruction::SetLE: BranchIdx = 4; break;
 828   case Instruction::SetGE: BranchIdx = 5; break;
 829   }
 830   static unsigned OpcodeTab[12] = {
 831                              // LLVM       SparcV8
 832                              //        unsigned signed
 833    V8::BE,   V8::BE,         // seteq = be      be
 834    V8::BNE,  V8::BNE,        // setne = bne     bne
 835    V8::BCS,  V8::BL,         // setlt = bcs     bl
 836    V8::BGU,  V8::BG,         // setgt = bgu     bg
 837    V8::BLEU, V8::BLE,        // setle = bleu    ble
 838    V8::BCC,  V8::BGE         // setge = bcc     bge
 839   };
 840   unsigned Opcode = OpcodeTab[2*BranchIdx + (Ty->isSigned() ? 1 : 0)];
 841
 842   MachineBasicBlock *thisMBB = BB;
 843   const BasicBlock *LLVM_BB = BB->getBasicBlock ();
 844   //  thisMBB:
 845   //  ...
 846   //   subcc %reg0, %reg1, %g0
 847   //   bCC copy1MBB
 848   //   ba copy0MBB
 849
 850   // FIXME: we wouldn't need copy0MBB (we could fold it into thisMBB)
 851   // if we could insert other, non-terminator instructions after the
 852   // bCC. But MBB->getFirstTerminator() can't understand this.
 853   MachineBasicBlock *copy1MBB = new MachineBasicBlock (LLVM_BB);
 854   F->getBasicBlockList ().push_back (copy1MBB);
 855   BuildMI (BB, Opcode, 1).addMBB (copy1MBB);
 856   MachineBasicBlock *copy0MBB = new MachineBasicBlock (LLVM_BB);
 857   F->getBasicBlockList ().push_back (copy0MBB);
 858   BuildMI (BB, V8::BA, 1).addMBB (copy0MBB);
 859   // Update machine-CFG edges
 860   BB->addSuccessor (copy1MBB);
 861   BB->addSuccessor (copy0MBB);
 862
 863   //  copy0MBB:
 864   //   %FalseValue = or %G0, 0
 865   //   ba sinkMBB
 866   BB = copy0MBB;
 867   unsigned FalseValue = makeAnotherReg (I.getType ());
 868   BuildMI (BB, V8::ORri, 2, FalseValue).addReg (V8::G0).addZImm (0);
 869   MachineBasicBlock *sinkMBB = new MachineBasicBlock (LLVM_BB);
 870   F->getBasicBlockList ().push_back (sinkMBB);
 871   BuildMI (BB, V8::BA, 1).addMBB (sinkMBB);
 872   // Update machine-CFG edges
 873   BB->addSuccessor (sinkMBB);
 874
 875   DEBUG (std::cerr << "thisMBB is at " << (void*)thisMBB << "\n");
 876   DEBUG (std::cerr << "copy1MBB is at " << (void*)copy1MBB << "\n");
 877   DEBUG (std::cerr << "copy0MBB is at " << (void*)copy0MBB << "\n");
 878   DEBUG (std::cerr << "sinkMBB is at " << (void*)sinkMBB << "\n");
 879
 880   //  copy1MBB:
 881   //   %TrueValue = or %G0, 1
 882   //   ba sinkMBB
 883   BB = copy1MBB;
 884   unsigned TrueValue = makeAnotherReg (I.getType ());
 885   BuildMI (BB, V8::ORri, 2, TrueValue).addReg (V8::G0).addZImm (1);
 886   BuildMI (BB, V8::BA, 1).addMBB (sinkMBB);
 887   // Update machine-CFG edges
 888   BB->addSuccessor (sinkMBB);
 889
 890   //  sinkMBB:
 891   //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, copy1MBB ]
 892   //  ...
 893   BB = sinkMBB;
 894   BuildMI (BB, V8::PHI, 4, DestReg).addReg (FalseValue)
 895     .addMBB (copy0MBB).addReg (TrueValue).addMBB (copy1MBB);
 896 }
 897
 898 void V8ISel::visitAllocaInst(AllocaInst &I) {
 899   // Find the data size of the alloca inst's getAllocatedType.
 900   const Type *Ty = I.getAllocatedType();
 901   unsigned TySize = TM.getTargetData().getTypeSize(Ty);
 902
 903   unsigned ArraySizeReg = getReg (I.getArraySize ());
 904   unsigned TySizeReg = getReg (ConstantUInt::get (Type::UIntTy, TySize));
 905   unsigned TmpReg1 = makeAnotherReg (Type::UIntTy);
 906   unsigned TmpReg2 = makeAnotherReg (Type::UIntTy);
 907   unsigned StackAdjReg = makeAnotherReg (Type::UIntTy);
 908
 909   // StackAdjReg = (ArraySize * TySize) rounded up to nearest doubleword boundary
 910   BuildMI (BB, V8::UMULrr, 2, TmpReg1).addReg (ArraySizeReg).addReg (TySizeReg);
 911
 912   // Round up TmpReg1 to nearest doubleword boundary:
 913   BuildMI (BB, V8::ADDri, 2, TmpReg2).addReg (TmpReg1).addSImm (7);
 914   BuildMI (BB, V8::ANDri, 2, StackAdjReg).addReg (TmpReg2).addSImm (-8);
 915
 916   // Subtract size from stack pointer, thereby allocating some space.
 917   BuildMI (BB, V8::SUBrr, 2, V8::SP).addReg (V8::SP).addReg (StackAdjReg);
 918
 919   // Put a pointer to the space into the result register, by copying
 920   // the stack pointer.
 921   BuildMI (BB, V8::ADDri, 2, getReg(I)).addReg (V8::SP).addSImm (96);
 922
 923   // Inform the Frame Information that we have just allocated a variable-sized
 924   // object.
 925   F->getFrameInfo()->CreateVariableSizedObject();
 926 }
 927
 928 /// LowerUnknownIntrinsicFunctionCalls - This performs a prepass over the
 929 /// function, lowering any calls to unknown intrinsic functions into the
 930 /// equivalent LLVM code.
 931 void V8ISel::LowerUnknownIntrinsicFunctionCalls(Function &F) {
 932   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 933     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
 934       if (CallInst *CI = dyn_cast<CallInst>(I++))
 935         if (Function *F = CI->getCalledFunction())
 936           switch (F->getIntrinsicID()) {
 937           case Intrinsic::not_intrinsic: break;
 938           default:
 939             // All other intrinsic calls we must lower.
 940             Instruction *Before = CI->getPrev();
 941             TM.getIntrinsicLowering().LowerIntrinsicCall(CI);
 942             if (Before) {        // Move iterator to instruction after call
 943               I = Before;  ++I;
 944             } else {
 945               I = BB->begin();
 946             }
 947           }
 948 }
 949
 950
 951 void V8ISel::visitIntrinsicCall(Intrinsic::ID ID, CallInst &CI) {
 952   unsigned TmpReg1, TmpReg2;
 953   switch (ID) {
 954   default: assert(0 && "Intrinsic not supported!");
 955   }
 956 }