LLVM API Documentation

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(std::find_if(CE->op_begin()+1, CE->op_end(),
00124                           nonConstant) == CE->op_end()
00125              && "All indices in ConstantExpr getelementptr must be constant!");
00126       getArg1 = CE->getOperand(0);
00127       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
00128         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
00129       else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore))
00130         getArg1 = gep;
00131       return new GetElementPtrInst(getArg1,
00132                           std::vector<Value*>(CE->op_begin()+1, CE->op_end()),
00133                           "constantGEP:" + getArg1->getName(), &insertBefore);
00134 
00135     case Instruction::Select: {
00136       Value *C, *S1, *S2;
00137       C = CE->getOperand (0);
00138       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (C))
00139         C = DecomposeConstantExpr (CEarg, insertBefore);
00140       S1 = CE->getOperand (1);
00141       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (S1))
00142         S1 = DecomposeConstantExpr (CEarg, insertBefore);
00143       S2 = CE->getOperand (2);
00144       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (S2))
00145         S2 = DecomposeConstantExpr (CEarg, insertBefore);
00146       return new SelectInst (C, S1, S2, "constantSelect", &insertBefore);
00147     }
00148 
00149     case Instruction::Shr: {
00150       getArg1 = CE->getOperand(0);
00151       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
00152         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
00153       getArg2 = CE->getOperand(1);
00154       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
00155         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
00156       return new ShiftInst (static_cast<Instruction::OtherOps>(CE->getOpcode()),
00157                             getArg1, getArg2,
00158                             "constantShr:" + getArg1->getName(), &insertBefore);
00159     }
00160 
00161     case Instruction::Shl: {
00162       getArg1 = CE->getOperand(0);
00163       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
00164         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
00165       getArg2 = CE->getOperand(1);
00166       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
00167         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
00168       return new ShiftInst (static_cast<Instruction::OtherOps>(CE->getOpcode()),
00169                             getArg1, getArg2,
00170                             "constantShl:" + getArg1->getName(), &insertBefore);
00171     }
00172 
00173     default:                            // must be a binary operator
00174       assert(CE->getOpcode() >= Instruction::BinaryOpsBegin &&
00175              CE->getOpcode() <  Instruction::BinaryOpsEnd &&
00176              "Unhandled opcode in ConstantExpr");
00177       getArg1 = CE->getOperand(0);
00178       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
00179         getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
00180       getArg2 = CE->getOperand(1);
00181       if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
00182         getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
00183       return BinaryOperator::create((Instruction::BinaryOps) CE->getOpcode(),
00184                                     getArg1, getArg2,
00185                                     "constantBinaryOp", &insertBefore);
00186     }
00187 }
00188 
00189 static inline bool ConstantTypeMustBeLoaded(const Type* CVT) {
00190   assert(CVT->isPrimitiveType() || isa<PointerType>(CVT));
00191   return !(CVT->isIntegral() || isa<PointerType>(CVT));
00192 }
00193 
00194 //------------------------------------------------------------------------------
00195 // Instruction visitor methods to perform instruction-specific operations
00196 //------------------------------------------------------------------------------
00197 inline void
00198 PreSelection::visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
00199                               Instruction& insertBefore)
00200 {
00201   assert(&insertBefore != NULL && "Must have instruction to insert before.");
00202 
00203   if (GetElementPtrInst* gep = getGlobalAddr(Op, insertBefore)) {
00204     I.setOperand(opNum, gep);           // replace global operand
00205     return;                             // nothing more to do for this op.
00206   }
00207 
00208   Constant* CV  = dyn_cast<Constant>(Op);
00209   if (CV == NULL)
00210     return;
00211 
00212   if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV)) {
00213     // load-time constant: factor it out so we optimize as best we can
00214     Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
00215     I.setOperand(opNum, computeConst); // replace expr operand with result
00216   } else if (ConstantTypeMustBeLoaded(CV->getType())) {
00217     // load address of constant into a register, then load the constant
00218     // this is now done during instruction selection
00219     // the constant will live in the MachineConstantPool later on
00220   } else if (ConstantMayNotFitInImmedField(CV, &I)) {
00221     // put the constant into a virtual register using a cast
00222     CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
00223                                    &insertBefore);
00224     I.setOperand(opNum, castI);      // replace operand with copy in v.reg.
00225   }
00226 }
00227 
00228 /// visitOperands - transform individual operands of all instructions:
00229 /// -- Load "large" int constants into a virtual register.  What is large
00230 ///    depends on the type of instruction and on the target architecture.
00231 /// -- For any constants that cannot be put in an immediate field,
00232 ///    load address into virtual register first, and then load the constant.
00233 ///
00234 /// firstOp and lastOp can be used to skip leading and trailing operands.
00235 /// If lastOp is 0, it defaults to #operands or #incoming Phi values.
00236 ///
00237 inline void PreSelection::visitOperands(Instruction &I, int firstOp) {
00238   // For any instruction other than PHI, copies go just before the instr.
00239   for (unsigned i = firstOp, e = I.getNumOperands(); i != e; ++i)
00240     visitOneOperand(I, I.getOperand(i), i, I);
00241 }
00242 
00243 
00244 void PreSelection::visitPHINode(PHINode &PN) {
00245   // For a PHI, operand copies must be before the terminator of the
00246   // appropriate predecessor basic block.  Remaining logic is simple
00247   // so just handle PHIs and other instructions separately.
00248   //
00249   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
00250     visitOneOperand(PN, PN.getIncomingValue(i),
00251                     PN.getOperandNumForIncomingValue(i),
00252                     *PN.getIncomingBlock(i)->getTerminator());
00253   // do not call visitOperands!
00254 }
00255 
00256 // Common work for *all* instructions.  This needs to be called explicitly
00257 // by other visit<InstructionType> functions.
00258 inline void PreSelection::visitInstruction(Instruction &I) {
00259   visitOperands(I);              // Perform operand transformations
00260 }
00261 
00262 // GetElementPtr instructions: check if pointer is a global
00263 void PreSelection::visitGetElementPtrInst(GetElementPtrInst &I) {
00264   Instruction* curI = &I;
00265 
00266   // The Sparc backend doesn't handle array indexes that are not long types, so
00267   // insert a cast from whatever it is to long, if the sequential type index is
00268   // not a long already.
00269   unsigned Idx = 1;
00270   for (gep_type_iterator TI = gep_type_begin(I), E = gep_type_end(I); TI != E;
00271        ++TI, ++Idx)
00272     if (isa<SequentialType>(*TI) &&
00273         I.getOperand(Idx)->getType() != Type::LongTy) {
00274       Value *Op = I.getOperand(Idx);
00275       if (Op->getType()->isUnsigned())    // Must sign extend!
00276         Op = new CastInst(Op, Op->getType()->getSignedVersion(), "v9", &I);
00277       if (Op->getType() != Type::LongTy)
00278         Op = new CastInst(Op, Type::LongTy, "v9", &I);
00279       I.setOperand(Idx, Op);
00280     }
00281 
00282 
00283   // Decompose multidimensional array references
00284   if (I.getNumIndices() >= 2) {
00285     // DecomposeArrayRef() replaces I and deletes it, if successful,
00286     // so remember predecessor in order to find the replacement instruction.
00287     // Also remember the basic block in case there is no predecessor.
00288     Instruction* prevI = I.getPrev();
00289     BasicBlock* bb = I.getParent();
00290     if (DecomposeArrayRef(&I))
00291       // first instr. replacing I
00292       curI = cast<GetElementPtrInst>(prevI? prevI->getNext() : &bb->front());
00293   }
00294 
00295   // Perform other transformations common to all instructions
00296   visitInstruction(*curI);
00297 }
00298 
00299 void PreSelection::visitCallInst(CallInst &I) {
00300   // Tell visitOperands to ignore the function name if this is a direct call.
00301   visitOperands(I, (/*firstOp=*/ I.getCalledFunction()? 1 : 0));
00302 }
00303 
00304 /// createPreSelectionPass - Public entry point for the PreSelection pass
00305 ///
00306 FunctionPass* llvm::createPreSelectionPass(const TargetMachine &TM) {
00307   return new PreSelection(TM);
00308 }