LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

SparcV9PreSelection.cpp

Go to the documentation of this file.
00001 //===- SparcV9PreSelection.cpp - Specialize LLVM code for SparcV9 ---------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the PreSelection pass which specializes LLVM code for
00011 // the SparcV9 instruction selector, while remaining in legal portable LLVM
00012 // form and preserving type information and type safety. This is meant to enable
00013 // dataflow optimizations on SparcV9-specific operations such as accesses to
00014 // constants, globals, and array indexing.
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #include "SparcV9Internals.h"
00019 #include "SparcV9BurgISel.h"
00020 #include "llvm/Constants.h"
00021 #include "llvm/DerivedTypes.h"
00022 #include "llvm/Instructions.h"
00023 #include "llvm/Module.h"
00024 #include "llvm/Pass.h"
00025 #include "llvm/Support/InstVisitor.h"
00026 #include "llvm/Support/GetElementPtrTypeIterator.h"
00027 #include "llvm/Target/TargetInstrInfo.h"
00028 #include "llvm/Target/TargetMachine.h"
00029 #include "llvm/Transforms/Scalar.h"
00030 #include <algorithm>
00031 using namespace llvm;
00032 
00033 namespace {
00034 
00035   //===--------------------------------------------------------------------===//
00036   // PreSelection Pass - Specialize LLVM code for the SparcV9 instr. selector.
00037   // 
00038   class PreSelection : public FunctionPass, public InstVisitor<PreSelection> {
00039     const TargetInstrInfo &instrInfo;
00040 
00041   public:
00042     PreSelection(const TargetMachine &T)
00043       : instrInfo(*T.getInstrInfo()) {}
00044 
00045     // runOnFunction - apply this pass to each Function
00046     bool runOnFunction(Function &F) {
00047       visit(F);
00048       return true;
00049     }
00050     const char *getPassName() const { return "SparcV9 Instr. Pre-selection"; }
00051 
00052     // These methods do the actual work of specializing code
00053     void visitInstruction(Instruction &I);   // common work for every instr. 
00054     void visitGetElementPtrInst(GetElementPtrInst &I);
00055     void visitCallInst(CallInst &I);
00056     void visitPHINode(PHINode &PN);
00057 
00058     void visitBasicBlock(BasicBlock &BB) {
00059       if (isa<UnreachableInst>(BB.getTerminator())) {
00060         BB.getInstList().pop_back();
00061         const Type *RetTy = BB.getParent()->getReturnType();
00062         Value *RetVal = RetTy == Type::VoidTy ? 0 : UndefValue::get(RetTy);
00063         new ReturnInst(RetVal, &BB);
00064       }
00065     }
00066 
00067     // Helper functions for visiting operands of every instruction
00068     // 
00069     // visitOperands() works on every operand in [firstOp, lastOp-1].
00070     // If lastOp==0, lastOp defaults to #operands or #incoming Phi values.
00071     // 
00072     // visitOneOperand() does all the work for one operand.
00073     // 
00074     void visitOperands(Instruction &I, int firstOp=0);
00075     void visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
00076                          Instruction& insertBefore);
00077   };
00078 
00079 #if 0
00080   // Register the pass...
00081   RegisterPass<PreSelection> X("preselect",
00082                                "Specialize LLVM code for a target machine"
00083                                createPreselectionPass);
00084 #endif
00085 
00086 }  // end anonymous namespace
00087 
00088 
00089 //------------------------------------------------------------------------------
00090 // Helper functions used by methods of class PreSelection
00091 //------------------------------------------------------------------------------
00092 
00093 
00094 // getGlobalAddr(): Put address of a global into a v. register.
00095 static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore) {
00096 
00097   return (isa<GlobalVariable>(ptr))
00098     ? new GetElementPtrInst(ptr,
00099                     std::vector<Value*>(1, ConstantSInt::get(Type::LongTy, 0U)),
00100                     "addrOfGlobal:" + ptr->getName(), &insertBefore)
00101     : NULL;
00102 }
00103 
00104 // Wrapper on Constant::classof to use in find_if
00105 inline static bool nonConstant(const Use& U) {
00106   return ! isa<Constant>(U);
00107 }
00108 
00109 static Instruction* DecomposeConstantExpr(ConstantExpr* CE,
00110                                           Instruction& insertBefore)
00111 {
00112   Value *getArg1, *getArg2;
00113   
00114   switch(CE->getOpcode())
00115     {
00116     case Instruction::Cast:
00117       getArg1 = CE->getOperand(0);
00118       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
00119         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
00120       return new CastInst(getArg1, CE->getType(), "constantCast",&insertBefore);
00121 
00122     case Instruction::GetElementPtr:
00123       assert(find_if(CE->op_begin()+1, CE->op_end(),nonConstant) == CE->op_end()
00124              && "All indices in ConstantExpr getelementptr must be constant!");
00125       getArg1 = CE->getOperand(0);
00126       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
00127         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
00128       else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore))
00129         getArg1 = gep;
00130       return new GetElementPtrInst(getArg1,
00131                           std::vector<Value*>(CE->op_begin()+1, CE->op_end()),
00132                           "constantGEP:" + getArg1->getName(), &insertBefore);
00133                           
00134     case Instruction::Select: {
00135       Value *C, *S1, *S2;
00136       C = CE->getOperand (0);
00137       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (C))
00138         C = DecomposeConstantExpr (CEarg, insertBefore);
00139       S1 = CE->getOperand (1);
00140       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (S1))
00141         S1 = DecomposeConstantExpr (CEarg, insertBefore);
00142       S2 = CE->getOperand (2);
00143       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (S2))
00144         S2 = DecomposeConstantExpr (CEarg, insertBefore);
00145       return new SelectInst (C, S1, S2, "constantSelect", &insertBefore);
00146     }
00147     
00148     default:                            // must be a binary operator
00149       assert(CE->getOpcode() >= Instruction::BinaryOpsBegin &&
00150              CE->getOpcode() <  Instruction::BinaryOpsEnd &&
00151              "Unhandled opcode in ConstantExpr");
00152       getArg1 = CE->getOperand(0);
00153       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
00154         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
00155       getArg2 = CE->getOperand(1);
00156       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
00157         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
00158       return BinaryOperator::create((Instruction::BinaryOps) CE->getOpcode(),
00159                                     getArg1, getArg2,
00160                                     "constantBinaryOp", &insertBefore);
00161     }
00162 }
00163 
00164 static inline bool ConstantTypeMustBeLoaded(const Type* CVT) {
00165   assert(CVT->isPrimitiveType() || isa<PointerType>(CVT));
00166   return !(CVT->isIntegral() || isa<PointerType>(CVT));
00167 }
00168 
00169 //------------------------------------------------------------------------------
00170 // Instruction visitor methods to perform instruction-specific operations
00171 //------------------------------------------------------------------------------
00172 inline void
00173 PreSelection::visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
00174                               Instruction& insertBefore)
00175 {
00176   assert(&insertBefore != NULL && "Must have instruction to insert before.");
00177 
00178   if (GetElementPtrInst* gep = getGlobalAddr(Op, insertBefore)) {
00179     I.setOperand(opNum, gep);           // replace global operand
00180     return;                             // nothing more to do for this op.
00181   }
00182 
00183   Constant* CV  = dyn_cast<Constant>(Op);
00184   if (CV == NULL)
00185     return;
00186 
00187   if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV)) {
00188     // load-time constant: factor it out so we optimize as best we can
00189     Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
00190     I.setOperand(opNum, computeConst); // replace expr operand with result
00191   } else if (ConstantTypeMustBeLoaded(CV->getType())) {
00192     // load address of constant into a register, then load the constant
00193     // this is now done during instruction selection
00194     // the constant will live in the MachineConstantPool later on
00195   } else if (ConstantMayNotFitInImmedField(CV, &I)) {
00196     // put the constant into a virtual register using a cast
00197     CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
00198                                    &insertBefore);
00199     I.setOperand(opNum, castI);      // replace operand with copy in v.reg.
00200   }
00201 }
00202 
00203 /// visitOperands - transform individual operands of all instructions:
00204 /// -- Load "large" int constants into a virtual register.  What is large
00205 ///    depends on the type of instruction and on the target architecture.
00206 /// -- For any constants that cannot be put in an immediate field,
00207 ///    load address into virtual register first, and then load the constant.
00208 /// 
00209 /// firstOp and lastOp can be used to skip leading and trailing operands.
00210 /// If lastOp is 0, it defaults to #operands or #incoming Phi values.
00211 ///  
00212 inline void PreSelection::visitOperands(Instruction &I, int firstOp) {
00213   // For any instruction other than PHI, copies go just before the instr.
00214   for (unsigned i = firstOp, e = I.getNumOperands(); i != e; ++i)
00215     visitOneOperand(I, I.getOperand(i), i, I);
00216 }
00217 
00218 
00219 void PreSelection::visitPHINode(PHINode &PN) {
00220   // For a PHI, operand copies must be before the terminator of the
00221   // appropriate predecessor basic block.  Remaining logic is simple
00222   // so just handle PHIs and other instructions separately.
00223   // 
00224   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
00225     visitOneOperand(PN, PN.getIncomingValue(i),
00226                     PN.getOperandNumForIncomingValue(i),
00227                     *PN.getIncomingBlock(i)->getTerminator());
00228   // do not call visitOperands!
00229 }
00230 
00231 // Common work for *all* instructions.  This needs to be called explicitly
00232 // by other visit<InstructionType> functions.
00233 inline void PreSelection::visitInstruction(Instruction &I) { 
00234   visitOperands(I);              // Perform operand transformations
00235 }
00236 
00237 // GetElementPtr instructions: check if pointer is a global
00238 void PreSelection::visitGetElementPtrInst(GetElementPtrInst &I) { 
00239   Instruction* curI = &I;
00240 
00241   // The Sparc backend doesn't handle array indexes that are not long types, so
00242   // insert a cast from whatever it is to long, if the sequential type index is
00243   // not a long already.
00244   unsigned Idx = 1;
00245   for (gep_type_iterator TI = gep_type_begin(I), E = gep_type_end(I); TI != E;
00246        ++TI, ++Idx)
00247     if (isa<SequentialType>(*TI) &&
00248         I.getOperand(Idx)->getType() != Type::LongTy) {
00249       Value *Op = I.getOperand(Idx);
00250       if (Op->getType()->isUnsigned())    // Must sign extend!
00251         Op = new CastInst(Op, Op->getType()->getSignedVersion(), "v9", &I);
00252       if (Op->getType() != Type::LongTy)
00253         Op = new CastInst(Op, Type::LongTy, "v9", &I);
00254       I.setOperand(Idx, Op);
00255     }
00256 
00257 
00258   // Decompose multidimensional array references
00259   if (I.getNumIndices() >= 2) {
00260     // DecomposeArrayRef() replaces I and deletes it, if successful,
00261     // so remember predecessor in order to find the replacement instruction.
00262     // Also remember the basic block in case there is no predecessor.
00263     Instruction* prevI = I.getPrev();
00264     BasicBlock* bb = I.getParent();
00265     if (DecomposeArrayRef(&I))
00266       // first instr. replacing I
00267       curI = cast<GetElementPtrInst>(prevI? prevI->getNext() : &bb->front());
00268   }
00269 
00270   // Perform other transformations common to all instructions
00271   visitInstruction(*curI);
00272 }
00273 
00274 void PreSelection::visitCallInst(CallInst &I) {
00275   // Tell visitOperands to ignore the function name if this is a direct call.
00276   visitOperands(I, (/*firstOp=*/ I.getCalledFunction()? 1 : 0));
00277 }
00278 
00279 /// createPreSelectionPass - Public entry point for the PreSelection pass
00280 ///
00281 FunctionPass* llvm::createPreSelectionPass(const TargetMachine &TM) {
00282   return new PreSelection(TM);
00283 }