-//===- PreSelection.cpp - Specialize LLVM code for target machine ---------===//
+//===- SparcV9PreSelection.cpp - Specialize LLVM code for SparcV9 ---------===//
//
-// This file defines the PreSelection pass which specializes LLVM code for a
-// target machine, while remaining in legal portable LLVM form and
-// preserving type information and type safety. This is meant to enable
-// dataflow optimizations on target-specific operations such as accesses to
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the PreSelection pass which specializes LLVM code for
+// the SparcV9 instruction selector, while remaining in legal portable LLVM
+// form and preserving type information and type safety. This is meant to enable
+// dataflow optimizations on SparcV9-specific operations such as accesses to
// constants, globals, and array indexing.
//
//===----------------------------------------------------------------------===//
-#include "llvm/CodeGen/PreSelection.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/MachineInstrInfo.h"
-#include "llvm/Transforms/Scalar.h"
-#include "llvm/Support/InstVisitor.h"
-#include "llvm/Module.h"
+#include "SparcV9Internals.h"
+#include "SparcV9BurgISel.h"
#include "llvm/Constants.h"
-#include "llvm/iMemory.h"
-#include "llvm/iPHINode.h"
-#include "llvm/iOther.h"
#include "llvm/DerivedTypes.h"
+#include "llvm/Instructions.h"
+#include "llvm/Module.h"
#include "llvm/Pass.h"
-#include "llvm/Annotation.h"
-#include "Support/CommandLine.h"
-#include "Support/NonCopyable.h"
+#include "llvm/Support/InstVisitor.h"
+#include "llvm/Support/GetElementPtrTypeIterator.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Transforms/Scalar.h"
#include <algorithm>
-using namespace std;
+using namespace llvm;
namespace {
- //===--------------------------------------------------------------------===//
- // SelectDebugLevel - Allow command line control over debugging.
- //
- enum PreSelectDebugLevel_t {
- PreSelect_NoDebugInfo,
- PreSelect_PrintOutput,
- };
-
- // Enable Debug Options to be specified on the command line
- cl::opt<PreSelectDebugLevel_t>
- PreSelectDebugLevel("dpreselect", cl::Hidden,
- cl::desc("debug information for target-dependent pre-selection"),
- cl::values(
- clEnumValN(PreSelect_NoDebugInfo, "n", "disable debug output (default)"),
- clEnumValN(PreSelect_PrintOutput, "y", "print generated machine code"),
- /* default level = */ PreSelect_NoDebugInfo));
-
-
- //===--------------------------------------------------------------------===//
- // class ConstantPoolForModule:
- //
- // The pool of constants that must be emitted for a module.
- // This is a single pool for the entire module and is shared by
- // all invocations of the PreSelection pass for this module by putting
- // this as an annotation on the Module object.
- // A single GlobalVariable is created for each constant in the pool
- // representing the memory for that constant.
- //
- static AnnotationID CPFM_AID(
- AnnotationManager::getID("CodeGen::ConstantPoolForModule"));
-
- class ConstantPoolForModule: private Annotation, public NonCopyable {
- Module* myModule;
- std::map<const Constant*, GlobalVariable*> gvars;
- std::map<const Constant*, GlobalVariable*> origGVars;
- ConstantPoolForModule(Module* M); // called only by annotation builder
- ConstantPoolForModule(); // do not implement
- public:
- static ConstantPoolForModule& get(Module* M) {
- ConstantPoolForModule* cpool =
- (ConstantPoolForModule*) M->getAnnotation(CPFM_AID);
- if (cpool == NULL) // create a new annotation and add it to the Module
- M->addAnnotation(cpool = new ConstantPoolForModule(M));
- return *cpool;
- }
-
- GlobalVariable* getGlobalForConstant(Constant* CV) {
- std::map<const Constant*, GlobalVariable*>::iterator I = gvars.find(CV);
- if (I != gvars.end())
- return I->second; // global exists so return it
- return addToConstantPool(CV); // create a new global and return it
- }
-
- GlobalVariable* addToConstantPool(Constant* CV) {
- GlobalVariable*& GV = gvars[CV]; // handle to global var entry in map
- if (GV == NULL)
- { // check if a global constant already existed; otherwise create one
- std::map<const Constant*, GlobalVariable*>::iterator PI =
- origGVars.find(CV);
- if (PI != origGVars.end())
- GV = PI->second; // put in map
- else
- {
- GV = new GlobalVariable(CV->getType(), true,true,CV); //put in map
- myModule->getGlobalList().push_back(GV); // GV owned by module now
- }
- }
- return GV;
- }
- };
-
- /* ctor */
- ConstantPoolForModule::ConstantPoolForModule(Module* M)
- : Annotation(CPFM_AID), myModule(M)
- {
- // Build reverse map for pre-existing global constants so we can find them
- for (Module::giterator GI = M->gbegin(), GE = M->gend(); GI != GE; ++GI)
- if (GI->hasInitializer() && GI->isConstant())
- origGVars[GI->getInitializer()] = GI;
- }
//===--------------------------------------------------------------------===//
- // PreSelection Pass - Specialize LLVM code for the current target machine.
- // This was and will be a basicblock pass, but make it a FunctionPass until
- // BasicBlockPass ::doFinalization(Function&) is available.
- //
- class PreSelection : public BasicBlockPass, public InstVisitor<PreSelection>
- {
- const TargetMachine ⌖
- Function* function;
-
- GlobalVariable* getGlobalForConstant(Constant* CV) {
- Module* M = function->getParent();
- return ConstantPoolForModule::get(M).getGlobalForConstant(CV);
- }
+ // PreSelection Pass - Specialize LLVM code for the SparcV9 instr. selector.
+ //
+ class PreSelection : public FunctionPass, public InstVisitor<PreSelection> {
+ const TargetInstrInfo &instrInfo;
public:
- PreSelection (const TargetMachine &T): target(T), function(NULL) {}
+ PreSelection(const TargetMachine &T)
+ : instrInfo(*T.getInstrInfo()) {}
- // runOnBasicBlock - apply this pass to each BB
- bool runOnBasicBlock(BasicBlock &BB) {
- function = BB.getParent();
- this->visit(BB);
+ // runOnFunction - apply this pass to each Function
+ bool runOnFunction(Function &F) {
+ visit(F);
return true;
}
-
- bool doFinalization(Function &F) {
- if (PreSelectDebugLevel >= PreSelect_PrintOutput)
- cerr << "\n\n*** LLVM code after pre-selection for function "
- << F.getName() << ":\n\n" << F;
- return false;
- }
+ const char *getPassName() const { return "SparcV9 Instr. Pre-selection"; }
// These methods do the actual work of specializing code
- void visitInstruction(Instruction &I); // common work for every instr.
+ void visitInstruction(Instruction &I); // common work for every instr.
void visitGetElementPtrInst(GetElementPtrInst &I);
- void visitLoadInst(LoadInst &I);
- void visitCastInst(CastInst &I);
- void visitStoreInst(StoreInst &I);
+ void visitCallInst(CallInst &I);
+ void visitPHINode(PHINode &PN);
+
+ void visitBasicBlock(BasicBlock &BB) {
+ if (isa<UnreachableInst>(BB.getTerminator())) {
+ BB.getInstList().pop_back();
+ const Type *RetTy = BB.getParent()->getReturnType();
+ Value *RetVal = RetTy == Type::VoidTy ? 0 : UndefValue::get(RetTy);
+ new ReturnInst(RetVal, &BB);
+ }
+ }
// Helper functions for visiting operands of every instruction
- void visitOperands(Instruction &I); // work on all operands of instr.
- void visitOneOperand(Instruction &I, Constant* CV, unsigned opNum,
- Instruction& insertBefore); // iworks on one operand
+ //
+ // visitOperands() works on every operand in [firstOp, lastOp-1].
+ // If lastOp==0, lastOp defaults to #operands or #incoming Phi values.
+ //
+ // visitOneOperand() does all the work for one operand.
+ //
+ void visitOperands(Instruction &I, int firstOp=0);
+ void visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
+ Instruction& insertBefore);
};
-} // end anonymous namespace
+#if 0
+ // Register the pass...
+ RegisterPass<PreSelection> X("preselect",
+ "Specialize LLVM code for a target machine"
+ createPreselectionPass);
+#endif
+
+} // end anonymous namespace
-// Register the pass...
-static RegisterOpt<PreSelection> X("preselect",
- "Specialize LLVM code for a target machine",
- createPreSelectionPass);
//------------------------------------------------------------------------------
// Helper functions used by methods of class PreSelection
// getGlobalAddr(): Put address of a global into a v. register.
-static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore)
-{
- if (isa<ConstantPointerRef>(ptr))
- ptr = cast<ConstantPointerRef>(ptr)->getValue();
+static GetElementPtrInst* getGlobalAddr(Value* ptr, Instruction& insertBefore) {
- return (isa<GlobalValue>(ptr))
+ return (isa<GlobalVariable>(ptr))
? new GetElementPtrInst(ptr,
std::vector<Value*>(1, ConstantSInt::get(Type::LongTy, 0U)),
- "addrOfGlobal", &insertBefore)
+ "addrOfGlobal:" + ptr->getName(), &insertBefore)
: NULL;
}
-
-// Wrapper on Constant::classof to use in find_if :-(
-inline static bool nonConstant(const Use& U)
-{
+// Wrapper on Constant::classof to use in find_if
+inline static bool nonConstant(const Use& U) {
return ! isa<Constant>(U);
}
-
static Instruction* DecomposeConstantExpr(ConstantExpr* CE,
Instruction& insertBefore)
{
return new CastInst(getArg1, CE->getType(), "constantCast",&insertBefore);
case Instruction::GetElementPtr:
-# ifndef NDEBUG
- assert(find_if(++CE->op_begin(), CE->op_end(),nonConstant) == CE->op_end()
+ assert(std::find_if(CE->op_begin()+1, CE->op_end(),
+ nonConstant) == CE->op_end()
&& "All indices in ConstantExpr getelementptr must be constant!");
-# endif
getArg1 = CE->getOperand(0);
if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
else if (GetElementPtrInst* gep = getGlobalAddr(getArg1, insertBefore))
getArg1 = gep;
return new GetElementPtrInst(getArg1,
- std::vector<Value*>(++CE->op_begin(), CE->op_end()),
- "constantGEP", &insertBefore);
+ std::vector<Value*>(CE->op_begin()+1, CE->op_end()),
+ "constantGEP:" + getArg1->getName(), &insertBefore);
+
+ case Instruction::Select: {
+ Value *C, *S1, *S2;
+ C = CE->getOperand (0);
+ if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (C))
+ C = DecomposeConstantExpr (CEarg, insertBefore);
+ S1 = CE->getOperand (1);
+ if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (S1))
+ S1 = DecomposeConstantExpr (CEarg, insertBefore);
+ S2 = CE->getOperand (2);
+ if (ConstantExpr* CEarg = dyn_cast<ConstantExpr> (S2))
+ S2 = DecomposeConstantExpr (CEarg, insertBefore);
+ return new SelectInst (C, S1, S2, "constantSelect", &insertBefore);
+ }
+
+ case Instruction::Shr: {
+ getArg1 = CE->getOperand(0);
+ if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
+ getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
+ getArg2 = CE->getOperand(1);
+ if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
+ getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
+ return new ShiftInst (static_cast<Instruction::OtherOps>(CE->getOpcode()),
+ getArg1, getArg2,
+ "constantShr:" + getArg1->getName(), &insertBefore);
+ }
+
+ case Instruction::Shl: {
+ getArg1 = CE->getOperand(0);
+ if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
+ getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
+ getArg2 = CE->getOperand(1);
+ if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg2))
+ getArg2 = DecomposeConstantExpr(CEarg, insertBefore);
+ return new ShiftInst (static_cast<Instruction::OtherOps>(CE->getOpcode()),
+ getArg1, getArg2,
+ "constantShl:" + getArg1->getName(), &insertBefore);
+ }
default: // must be a binary operator
assert(CE->getOpcode() >= Instruction::BinaryOpsBegin &&
CE->getOpcode() < Instruction::BinaryOpsEnd &&
- "Unrecognized opcode in ConstantExpr");
+ "Unhandled opcode in ConstantExpr");
getArg1 = CE->getOperand(0);
if (ConstantExpr* CEarg = dyn_cast<ConstantExpr>(getArg1))
getArg1 = DecomposeConstantExpr(CEarg, insertBefore);
}
}
+static inline bool ConstantTypeMustBeLoaded(const Type* CVT) {
+ assert(CVT->isPrimitiveType() || isa<PointerType>(CVT));
+ return !(CVT->isIntegral() || isa<PointerType>(CVT));
+}
//------------------------------------------------------------------------------
// Instruction visitor methods to perform instruction-specific operations
//------------------------------------------------------------------------------
-
-// Common work for *all* instructions. This needs to be called explicitly
-// by other visit<InstructionType> functions.
inline void
-PreSelection::visitInstruction(Instruction &I)
-{
- visitOperands(I); // Perform operand transformations
-}
-
-
-// GetElementPtr instructions: check if pointer is a global
-void
-PreSelection::visitGetElementPtrInst(GetElementPtrInst &I)
-{
- // Check for a global and put its address into a register before this instr
- if (GetElementPtrInst* gep = getGlobalAddr(I.getPointerOperand(), I))
- I.setOperand(I.getPointerOperandIndex(), gep); // replace pointer operand
+PreSelection::visitOneOperand(Instruction &I, Value* Op, unsigned opNum,
+ Instruction& insertBefore)
+{
+ assert(&insertBefore != NULL && "Must have instruction to insert before.");
- // Decompose multidimensional array references
- DecomposeArrayRef(&I);
+ if (GetElementPtrInst* gep = getGlobalAddr(Op, insertBefore)) {
+ I.setOperand(opNum, gep); // replace global operand
+ return; // nothing more to do for this op.
+ }
- // Perform other transformations common to all instructions
- visitInstruction(I);
+ Constant* CV = dyn_cast<Constant>(Op);
+ if (CV == NULL)
+ return;
+
+ if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV)) {
+ // load-time constant: factor it out so we optimize as best we can
+ Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
+ I.setOperand(opNum, computeConst); // replace expr operand with result
+ } else if (ConstantTypeMustBeLoaded(CV->getType())) {
+ // load address of constant into a register, then load the constant
+ // this is now done during instruction selection
+ // the constant will live in the MachineConstantPool later on
+ } else if (ConstantMayNotFitInImmedField(CV, &I)) {
+ // put the constant into a virtual register using a cast
+ CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
+ &insertBefore);
+ I.setOperand(opNum, castI); // replace operand with copy in v.reg.
+ }
}
-
-// Load instructions: check if pointer is a global
-void
-PreSelection::visitLoadInst(LoadInst &I)
-{
- // Check for a global and put its address into a register before this instr
- if (GetElementPtrInst* gep = getGlobalAddr(I.getPointerOperand(), I))
- I.setOperand(I.getPointerOperandIndex(), gep); // replace pointer operand
-
- // Perform other transformations common to all instructions
- visitInstruction(I);
+/// visitOperands - transform individual operands of all instructions:
+/// -- Load "large" int constants into a virtual register. What is large
+/// depends on the type of instruction and on the target architecture.
+/// -- For any constants that cannot be put in an immediate field,
+/// load address into virtual register first, and then load the constant.
+///
+/// firstOp and lastOp can be used to skip leading and trailing operands.
+/// If lastOp is 0, it defaults to #operands or #incoming Phi values.
+///
+inline void PreSelection::visitOperands(Instruction &I, int firstOp) {
+ // For any instruction other than PHI, copies go just before the instr.
+ for (unsigned i = firstOp, e = I.getNumOperands(); i != e; ++i)
+ visitOneOperand(I, I.getOperand(i), i, I);
}
-// Store instructions: check if pointer is a global
-void
-PreSelection::visitStoreInst(StoreInst &I)
-{
- // Check for a global and put its address into a register before this instr
- if (GetElementPtrInst* gep = getGlobalAddr(I.getPointerOperand(), I))
- I.setOperand(I.getPointerOperandIndex(), gep); // replace pointer operand
-
- // Perform other transformations common to all instructions
- visitInstruction(I);
+void PreSelection::visitPHINode(PHINode &PN) {
+ // For a PHI, operand copies must be before the terminator of the
+ // appropriate predecessor basic block. Remaining logic is simple
+ // so just handle PHIs and other instructions separately.
+ //
+ for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
+ visitOneOperand(PN, PN.getIncomingValue(i),
+ PN.getOperandNumForIncomingValue(i),
+ *PN.getIncomingBlock(i)->getTerminator());
+ // do not call visitOperands!
}
+// Common work for *all* instructions. This needs to be called explicitly
+// by other visit<InstructionType> functions.
+inline void PreSelection::visitInstruction(Instruction &I) {
+ visitOperands(I); // Perform operand transformations
+}
-// Cast instructions:
-// -- check if argument is a global
-// -- make multi-step casts explicit:
-// -- float/double to uint32_t:
-// If target does not have a float-to-unsigned instruction, we
-// need to convert to uint64_t and then to uint32_t, or we may
-// overflow the signed int representation for legal uint32_t
-// values. Expand this without checking target.
-//
-void
-PreSelection::visitCastInst(CastInst &I)
-{
- CastInst* castI = NULL;
-
- // Check for a global and put its address into a register before this instr
- if (GetElementPtrInst* gep = getGlobalAddr(I.getOperand(0), I))
- {
- I.setOperand(0, gep); // replace pointer operand
- }
- else if (I.getType() == Type::UIntTy &&
- I.getOperand(0)->getType()->isFloatingPoint())
- { // insert a cast-fp-to-long before I, and then replace the operand of I
- castI = new CastInst(I.getOperand(0), Type::LongTy, "fp2Long2Uint", &I);
- I.setOperand(0, castI); // replace fp operand with long
+// GetElementPtr instructions: check if pointer is a global
+void PreSelection::visitGetElementPtrInst(GetElementPtrInst &I) {
+ Instruction* curI = &I;
+
+ // The Sparc backend doesn't handle array indexes that are not long types, so
+ // insert a cast from whatever it is to long, if the sequential type index is
+ // not a long already.
+ unsigned Idx = 1;
+ for (gep_type_iterator TI = gep_type_begin(I), E = gep_type_end(I); TI != E;
+ ++TI, ++Idx)
+ if (isa<SequentialType>(*TI) &&
+ I.getOperand(Idx)->getType() != Type::LongTy) {
+ Value *Op = I.getOperand(Idx);
+ if (Op->getType()->isUnsigned()) // Must sign extend!
+ Op = new CastInst(Op, Op->getType()->getSignedVersion(), "v9", &I);
+ if (Op->getType() != Type::LongTy)
+ Op = new CastInst(Op, Type::LongTy, "v9", &I);
+ I.setOperand(Idx, Op);
}
- // Perform other transformations common to all instructions
- visitInstruction(I);
- if (castI)
- visitInstruction(*castI);
-}
+ // Decompose multidimensional array references
+ if (I.getNumIndices() >= 2) {
+ // DecomposeArrayRef() replaces I and deletes it, if successful,
+ // so remember predecessor in order to find the replacement instruction.
+ // Also remember the basic block in case there is no predecessor.
+ Instruction* prevI = I.getPrev();
+ BasicBlock* bb = I.getParent();
+ if (DecomposeArrayRef(&I))
+ // first instr. replacing I
+ curI = cast<GetElementPtrInst>(prevI? prevI->getNext() : &bb->front());
+ }
-// visitOperands() transforms individual operands of all instructions:
-// -- Load "large" int constants into a virtual register. What is large
-// depends on the type of instruction and on the target architecture.
-// -- For any constants that cannot be put in an immediate field,
-// load address into virtual register first, and then load the constant.
-//
-void
-PreSelection::visitOperands(Instruction &I)
-{
- // For any instruction other than PHI, copies go just before the instr.
- // For a PHI, operand copies must be before the terminator of the
- // appropriate predecessor basic block. Remaining logic is simple
- // so just handle PHIs and other instructions separately.
- //
- if (PHINode* phi = dyn_cast<PHINode>(&I))
- {
- for (unsigned i=0, N=phi->getNumIncomingValues(); i < N; ++i)
- if (Constant* CV = dyn_cast<Constant>(phi->getIncomingValue(i)))
- this->visitOneOperand(I, CV, phi->getOperandNumForIncomingValue(i),
- * phi->getIncomingBlock(i)->getTerminator());
- }
- else
- for (unsigned i=0, N=I.getNumOperands(); i < N; ++i)
- if (Constant* CV = dyn_cast<Constant>(I.getOperand(i)))
- this->visitOneOperand(I, CV, i, I);
+ // Perform other transformations common to all instructions
+ visitInstruction(*curI);
}
-void
-PreSelection::visitOneOperand(Instruction &I, Constant* CV, unsigned opNum,
- Instruction& insertBefore)
-{
- if (ConstantExpr* CE = dyn_cast<ConstantExpr>(CV))
- { // load-time constant: factor it out so we optimize as best we can
- Instruction* computeConst = DecomposeConstantExpr(CE, insertBefore);
- I.setOperand(opNum, computeConst); // replace expr operand with result
- }
- else if (target.getInstrInfo().ConstantTypeMustBeLoaded(CV))
- { // load address of constant into a register, then load the constant
- GetElementPtrInst* gep = getGlobalAddr(getGlobalForConstant(CV),
- insertBefore);
- LoadInst* ldI = new LoadInst(gep, "loadConst", &insertBefore);
- I.setOperand(opNum, ldI); // replace operand with copy in v.reg.
- }
- else if (target.getInstrInfo().ConstantMayNotFitInImmedField(CV, &I))
- { // put the constant into a virtual register using a cast
- CastInst* castI = new CastInst(CV, CV->getType(), "copyConst",
- &insertBefore);
- I.setOperand(opNum, castI); // replace operand with copy in v.reg.
- }
+void PreSelection::visitCallInst(CallInst &I) {
+ // Tell visitOperands to ignore the function name if this is a direct call.
+ visitOperands(I, (/*firstOp=*/ I.getCalledFunction()? 1 : 0));
}
-
-//===----------------------------------------------------------------------===//
-// createPreSelectionPass - Public entrypoint for pre-selection pass
-// and this file as a whole...
-//
-Pass*
-createPreSelectionPass(TargetMachine &T)
-{
- return new PreSelection(T);
+/// createPreSelectionPass - Public entry point for the PreSelection pass
+///
+FunctionPass* llvm::createPreSelectionPass(const TargetMachine &TM) {
+ return new PreSelection(TM);
}
-