+++ /dev/null
-//===-- InstrForest.cpp - Build instruction forest for inst selection -----===//
-//
-// 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.
-//
-//===----------------------------------------------------------------------===//
-//
-// The key goal is to group instructions into a single
-// tree if one or more of them might be potentially combined into a single
-// complex instruction in the target machine.
-// Since this grouping is completely machine-independent, we do it as
-// aggressive as possible to exploit any possible target instructions.
-// In particular, we group two instructions O and I if:
-// (1) Instruction O computes an operand used by instruction I,
-// and (2) O and I are part of the same basic block,
-// and (3) O has only a single use, viz., I.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Constant.h"
-#include "llvm/Function.h"
-#include "llvm/iTerminators.h"
-#include "llvm/iMemory.h"
-#include "llvm/Type.h"
-#include "llvm/CodeGen/InstrForest.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "Support/STLExtras.h"
-#include "Config/alloca.h"
-
-namespace llvm {
-
-//------------------------------------------------------------------------
-// class InstrTreeNode
-//------------------------------------------------------------------------
-
-void
-InstrTreeNode::dump(int dumpChildren, int indent) const {
- dumpNode(indent);
-
- if (dumpChildren) {
- if (LeftChild)
- LeftChild->dump(dumpChildren, indent+1);
- if (RightChild)
- RightChild->dump(dumpChildren, indent+1);
- }
-}
-
-
-InstructionNode::InstructionNode(Instruction* I)
- : InstrTreeNode(NTInstructionNode, I), codeIsFoldedIntoParent(false)
-{
- opLabel = I->getOpcode();
-
- // Distinguish special cases of some instructions such as Ret and Br
- //
- if (opLabel == Instruction::Ret && cast<ReturnInst>(I)->getReturnValue()) {
- opLabel = RetValueOp; // ret(value) operation
- }
- else if (opLabel ==Instruction::Br && !cast<BranchInst>(I)->isUnconditional())
- {
- opLabel = BrCondOp; // br(cond) operation
- } else if (opLabel >= Instruction::SetEQ && opLabel <= Instruction::SetGT) {
- opLabel = SetCCOp; // common label for all SetCC ops
- } else if (opLabel == Instruction::Alloca && I->getNumOperands() > 0) {
- opLabel = AllocaN; // Alloca(ptr, N) operation
- } else if (opLabel == Instruction::GetElementPtr &&
- cast<GetElementPtrInst>(I)->hasIndices()) {
- opLabel = opLabel + 100; // getElem with index vector
- } else if (opLabel == Instruction::Xor &&
- BinaryOperator::isNot(I)) {
- opLabel = (I->getType() == Type::BoolTy)? NotOp // boolean Not operator
- : BNotOp; // bitwise Not operator
- } else if (opLabel == Instruction::And || opLabel == Instruction::Or ||
- opLabel == Instruction::Xor) {
- // Distinguish bitwise operators from logical operators!
- if (I->getType() != Type::BoolTy)
- opLabel = opLabel + 100; // bitwise operator
- } else if (opLabel == Instruction::Cast) {
- const Type *ITy = I->getType();
- switch(ITy->getPrimitiveID())
- {
- case Type::BoolTyID: opLabel = ToBoolTy; break;
- case Type::UByteTyID: opLabel = ToUByteTy; break;
- case Type::SByteTyID: opLabel = ToSByteTy; break;
- case Type::UShortTyID: opLabel = ToUShortTy; break;
- case Type::ShortTyID: opLabel = ToShortTy; break;
- case Type::UIntTyID: opLabel = ToUIntTy; break;
- case Type::IntTyID: opLabel = ToIntTy; break;
- case Type::ULongTyID: opLabel = ToULongTy; break;
- case Type::LongTyID: opLabel = ToLongTy; break;
- case Type::FloatTyID: opLabel = ToFloatTy; break;
- case Type::DoubleTyID: opLabel = ToDoubleTy; break;
- case Type::ArrayTyID: opLabel = ToArrayTy; break;
- case Type::PointerTyID: opLabel = ToPointerTy; break;
- default:
- // Just use `Cast' opcode otherwise. It's probably ignored.
- break;
- }
- }
-}
-
-
-void
-InstructionNode::dumpNode(int indent) const {
- for (int i=0; i < indent; i++)
- std::cerr << " ";
- std::cerr << getInstruction()->getOpcodeName()
- << " [label " << getOpLabel() << "]" << "\n";
-}
-
-void
-VRegListNode::dumpNode(int indent) const {
- for (int i=0; i < indent; i++)
- std::cerr << " ";
-
- std::cerr << "List" << "\n";
-}
-
-
-void
-VRegNode::dumpNode(int indent) const {
- for (int i=0; i < indent; i++)
- std::cerr << " ";
-
- std::cerr << "VReg " << getValue() << "\t(type "
- << (int) getValue()->getValueType() << ")" << "\n";
-}
-
-void
-ConstantNode::dumpNode(int indent) const {
- for (int i=0; i < indent; i++)
- std::cerr << " ";
-
- std::cerr << "Constant " << getValue() << "\t(type "
- << (int) getValue()->getValueType() << ")" << "\n";
-}
-
-void LabelNode::dumpNode(int indent) const {
- for (int i=0; i < indent; i++)
- std::cerr << " ";
-
- std::cerr << "Label " << getValue() << "\n";
-}
-
-//------------------------------------------------------------------------
-// class InstrForest
-//
-// A forest of instruction trees, usually for a single method.
-//------------------------------------------------------------------------
-
-InstrForest::InstrForest(Function *F) {
- for (Function::iterator BB = F->begin(), FE = F->end(); BB != FE; ++BB) {
- for(BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
- buildTreeForInstruction(I);
- }
-}
-
-InstrForest::~InstrForest() {
- for_each(treeRoots.begin(), treeRoots.end(), deleter<InstructionNode>);
-}
-
-void InstrForest::dump() const {
- for (const_root_iterator I = roots_begin(); I != roots_end(); ++I)
- (*I)->dump(/*dumpChildren*/ 1, /*indent*/ 0);
-}
-
-inline void InstrForest::eraseRoot(InstructionNode* node) {
- for (RootSet::reverse_iterator RI=treeRoots.rbegin(), RE=treeRoots.rend();
- RI != RE; ++RI)
- if (*RI == node)
- treeRoots.erase(RI.base()-1);
-}
-
-inline void InstrForest::noteTreeNodeForInstr(Instruction *instr,
- InstructionNode *treeNode) {
- (*this)[instr] = treeNode;
- treeRoots.push_back(treeNode); // mark node as root of a new tree
-}
-
-
-inline void InstrForest::setLeftChild(InstrTreeNode *parent,
- InstrTreeNode *child) {
- parent->LeftChild = child;
- child->Parent = parent;
- if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
- eraseRoot(instrNode); // no longer a tree root
-}
-
-inline void InstrForest::setRightChild(InstrTreeNode *parent,
- InstrTreeNode *child) {
- parent->RightChild = child;
- child->Parent = parent;
- if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
- eraseRoot(instrNode); // no longer a tree root
-}
-
-
-InstructionNode* InstrForest::buildTreeForInstruction(Instruction *instr) {
- InstructionNode *treeNode = getTreeNodeForInstr(instr);
- if (treeNode) {
- // treeNode has already been constructed for this instruction
- assert(treeNode->getInstruction() == instr);
- return treeNode;
- }
-
- // Otherwise, create a new tree node for this instruction.
- //
- treeNode = new InstructionNode(instr);
- noteTreeNodeForInstr(instr, treeNode);
-
- if (instr->getOpcode() == Instruction::Call) {
- // Operands of call instruction
- return treeNode;
- }
-
- // If the instruction has more than 2 instruction operands,
- // then we need to create artificial list nodes to hold them.
- // (Note that we only count operands that get tree nodes, and not
- // others such as branch labels for a branch or switch instruction.)
- //
- // To do this efficiently, we'll walk all operands, build treeNodes
- // for all appropriate operands and save them in an array. We then
- // insert children at the end, creating list nodes where needed.
- // As a performance optimization, allocate a child array only
- // if a fixed array is too small.
- //
- int numChildren = 0;
- InstrTreeNode** childArray = new InstrTreeNode*[instr->getNumOperands()];
-
- //
- // Walk the operands of the instruction
- //
- for (Instruction::op_iterator O = instr->op_begin(); O!=instr->op_end(); ++O)
- {
- Value* operand = *O;
-
- // Check if the operand is a data value, not an branch label, type,
- // method or module. If the operand is an address type (i.e., label
- // or method) that is used in an non-branching operation, e.g., `add'.
- // that should be considered a data value.
-
- // Check latter condition here just to simplify the next IF.
- bool includeAddressOperand =
- (isa<BasicBlock>(operand) || isa<Function>(operand))
- && !instr->isTerminator();
-
- if (includeAddressOperand || isa<Instruction>(operand) ||
- isa<Constant>(operand) || isa<Argument>(operand) ||
- isa<GlobalVariable>(operand))
- {
- // This operand is a data value
-
- // An instruction that computes the incoming value is added as a
- // child of the current instruction if:
- // the value has only a single use
- // AND both instructions are in the same basic block.
- // AND the current instruction is not a PHI (because the incoming
- // value is conceptually in a predecessor block,
- // even though it may be in the same static block)
- //
- // (Note that if the value has only a single use (viz., `instr'),
- // the def of the value can be safely moved just before instr
- // and therefore it is safe to combine these two instructions.)
- //
- // In all other cases, the virtual register holding the value
- // is used directly, i.e., made a child of the instruction node.
- //
- InstrTreeNode* opTreeNode;
- if (isa<Instruction>(operand) && operand->hasOneUse() &&
- cast<Instruction>(operand)->getParent() == instr->getParent() &&
- instr->getOpcode() != Instruction::PHI &&
- instr->getOpcode() != Instruction::Call)
- {
- // Recursively create a treeNode for it.
- opTreeNode = buildTreeForInstruction((Instruction*)operand);
- } else if (Constant *CPV = dyn_cast<Constant>(operand)) {
- // Create a leaf node for a constant
- opTreeNode = new ConstantNode(CPV);
- } else {
- // Create a leaf node for the virtual register
- opTreeNode = new VRegNode(operand);
- }
-
- childArray[numChildren++] = opTreeNode;
- }
- }
-
- //--------------------------------------------------------------------
- // Add any selected operands as children in the tree.
- // Certain instructions can have more than 2 in some instances (viz.,
- // a CALL or a memory access -- LOAD, STORE, and GetElemPtr -- to an
- // array or struct). Make the operands of every such instruction into
- // a right-leaning binary tree with the operand nodes at the leaves
- // and VRegList nodes as internal nodes.
- //--------------------------------------------------------------------
-
- InstrTreeNode *parent = treeNode;
-
- if (numChildren > 2) {
- unsigned instrOpcode = treeNode->getInstruction()->getOpcode();
- assert(instrOpcode == Instruction::PHI ||
- instrOpcode == Instruction::Call ||
- instrOpcode == Instruction::Load ||
- instrOpcode == Instruction::Store ||
- instrOpcode == Instruction::GetElementPtr);
- }
-
- // Insert the first child as a direct child
- if (numChildren >= 1)
- setLeftChild(parent, childArray[0]);
-
- int n;
-
- // Create a list node for children 2 .. N-1, if any
- for (n = numChildren-1; n >= 2; n--) {
- // We have more than two children
- InstrTreeNode *listNode = new VRegListNode();
- setRightChild(parent, listNode);
- setLeftChild(listNode, childArray[numChildren - n]);
- parent = listNode;
- }
-
- // Now insert the last remaining child (if any).
- if (numChildren >= 2) {
- assert(n == 1);
- setRightChild(parent, childArray[numChildren - 1]);
- }
-
- delete [] childArray;
- return treeNode;
-}
-
-} // End llvm namespace
+++ /dev/null
-//===- InstrSelection.cpp - Machine Independent Inst Selection Driver -----===//
-//
-// 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.
-//
-//===----------------------------------------------------------------------===//
-//
-// Machine-independent driver file for instruction selection. This file
-// constructs a forest of BURG instruction trees and then uses the
-// BURG-generated tree grammar (BURM) to find the optimal instruction sequences
-// for a given machine.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/CodeGen/InstrSelection.h"
-#include "llvm/Function.h"
-#include "llvm/IntrinsicLowering.h"
-#include "llvm/iPHINode.h"
-#include "llvm/iOther.h"
-#include "llvm/Pass.h"
-#include "llvm/CodeGen/InstrForest.h"
-#include "llvm/CodeGen/InstrSelectionSupport.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetRegInfo.h"
-#include "Support/CommandLine.h"
-#include "Support/LeakDetector.h"
-
-namespace llvm {
- std::vector<MachineInstr*>
- FixConstantOperandsForInstr(Instruction *I, MachineInstr *MI,
- TargetMachine &TM);
-}
-
-namespace {
- //===--------------------------------------------------------------------===//
- // SelectDebugLevel - Allow command line control over debugging.
- //
- enum SelectDebugLevel_t {
- Select_NoDebugInfo,
- Select_PrintMachineCode,
- Select_DebugInstTrees,
- Select_DebugBurgTrees,
- };
-
- // Enable Debug Options to be specified on the command line
- cl::opt<SelectDebugLevel_t>
- SelectDebugLevel("dselect", cl::Hidden,
- cl::desc("enable instruction selection debug information"),
- cl::values(
- clEnumValN(Select_NoDebugInfo, "n", "disable debug output"),
- clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
- clEnumValN(Select_DebugInstTrees, "i",
- "print debugging info for instruction selection"),
- clEnumValN(Select_DebugBurgTrees, "b", "print burg trees"),
- 0));
-
-
- //===--------------------------------------------------------------------===//
- // InstructionSelection Pass
- //
- // This is the actual pass object that drives the instruction selection
- // process.
- //
- class InstructionSelection : public FunctionPass {
- TargetMachine &Target;
- void InsertCodeForPhis(Function &F);
- void InsertPhiElimInstructions(BasicBlock *BB,
- const std::vector<MachineInstr*>& CpVec);
- void SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt);
- void PostprocessMachineCodeForTree(InstructionNode* instrNode,
- int ruleForNode, short* nts);
- public:
- InstructionSelection(TargetMachine &TM) : Target(TM) {}
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesCFG();
- }
-
- bool runOnFunction(Function &F);
- virtual const char *getPassName() const { return "Instruction Selection"; }
- };
-}
-
-
-TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
- Value *s1, Value *s2, const std::string &name)
- : Instruction(s1->getType(), Instruction::UserOp1, name)
-{
- mcfi.addTemp(this);
-
- Operands.push_back(Use(s1, this)); // s1 must be non-null
- if (s2)
- Operands.push_back(Use(s2, this));
-
- // TmpInstructions should not be garbage checked.
- LeakDetector::removeGarbageObject(this);
-}
-
-// Constructor that requires the type of the temporary to be specified.
-// Both S1 and S2 may be NULL.(
-TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
- const Type *Ty, Value *s1, Value* s2,
- const std::string &name)
- : Instruction(Ty, Instruction::UserOp1, name)
-{
- mcfi.addTemp(this);
-
- if (s1)
- Operands.push_back(Use(s1, this));
- if (s2)
- Operands.push_back(Use(s2, this));
-
- // TmpInstructions should not be garbage checked.
- LeakDetector::removeGarbageObject(this);
-}
-
-bool InstructionSelection::runOnFunction(Function &F) {
- // First pass - Walk the function, lowering any calls to intrinsic functions
- // which the instruction selector cannot handle.
- for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
- for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
- if (CallInst *CI = dyn_cast<CallInst>(I++))
- if (Function *F = CI->getCalledFunction())
- switch (F->getIntrinsicID()) {
-#undef va_start
-#undef va_copy
-#undef va_end
- case Intrinsic::not_intrinsic:
- case Intrinsic::va_start:
- case Intrinsic::va_copy:
- case Intrinsic::va_end:
- // We directly implement these intrinsics. Note that this knowledge
- // is incestuously entangled with the code in
- // SparcInstrSelection.cpp and must be updated when it is updated.
- // Since ALL of the code in this library is incestuously intertwined
- // with it already and sparc specific, we will live with this.
- break;
- default:
- // All other intrinsic calls we must lower.
- Instruction *Before = CI->getPrev();
- Target.getIntrinsicLowering().LowerIntrinsicCall(CI);
- if (Before) { // Move iterator to instruction after call
- I = Before; ++I;
- } else {
- I = BB->begin();
- }
- }
-
- //
- // Build the instruction trees to be given as inputs to BURG.
- //
- InstrForest instrForest(&F);
-
- if (SelectDebugLevel >= Select_DebugInstTrees) {
- std::cerr << "\n\n*** Input to instruction selection for function "
- << F.getName() << "\n\n" << F
- << "\n\n*** Instruction trees for function "
- << F.getName() << "\n\n";
- instrForest.dump();
- }
-
- //
- // Invoke BURG instruction selection for each tree
- //
- for (InstrForest::const_root_iterator RI = instrForest.roots_begin();
- RI != instrForest.roots_end(); ++RI) {
- InstructionNode* basicNode = *RI;
- assert(basicNode->parent() == NULL && "A `root' node has a parent?");
-
- // Invoke BURM to label each tree node with a state
- burm_label(basicNode);
-
- if (SelectDebugLevel >= Select_DebugBurgTrees) {
- printcover(basicNode, 1, 0);
- std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n";
- printMatches(basicNode);
- }
-
- // Then recursively walk the tree to select instructions
- SelectInstructionsForTree(basicNode, /*goalnt*/1);
- }
-
- //
- // Create the MachineBasicBlock records and add all of the MachineInstrs
- // defined in the MachineCodeForInstruction objects to also live in the
- // MachineBasicBlock objects.
- //
- MachineFunction &MF = MachineFunction::get(&F);
- for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
- MachineBasicBlock *MCBB = new MachineBasicBlock(BI);
- MF.getBasicBlockList().push_back(MCBB);
-
- for (BasicBlock::iterator II = BI->begin(); II != BI->end(); ++II) {
- MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(II);
- MCBB->insert(MCBB->end(), mvec.begin(), mvec.end());
- }
- }
-
- // Insert phi elimination code
- InsertCodeForPhis(F);
-
- if (SelectDebugLevel >= Select_PrintMachineCode) {
- std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
- MachineFunction::get(&F).dump();
- }
-
- return true;
-}
-
-
-//-------------------------------------------------------------------------
-// This method inserts phi elimination code for all BBs in a method
-//-------------------------------------------------------------------------
-
-void
-InstructionSelection::InsertCodeForPhis(Function &F) {
- // for all basic blocks in function
- //
- MachineFunction &MF = MachineFunction::get(&F);
- for (MachineFunction::iterator BB = MF.begin(); BB != MF.end(); ++BB) {
- for (BasicBlock::const_iterator IIt = BB->getBasicBlock()->begin();
- const PHINode *PN = dyn_cast<PHINode>(IIt); ++IIt) {
- // FIXME: This is probably wrong...
- Value *PhiCpRes = new PHINode(PN->getType(), "PhiCp:");
-
- // The leak detector shouldn't track these nodes. They are not garbage,
- // even though their parent field is never filled in.
- //
- LeakDetector::removeGarbageObject(PhiCpRes);
-
- // for each incoming value of the phi, insert phi elimination
- //
- for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) {
- // insert the copy instruction to the predecessor BB
- std::vector<MachineInstr*> mvec, CpVec;
- Target.getRegInfo().cpValue2Value(PN->getIncomingValue(i), PhiCpRes,
- mvec);
- for (std::vector<MachineInstr*>::iterator MI=mvec.begin();
- MI != mvec.end(); ++MI) {
- std::vector<MachineInstr*> CpVec2 =
- FixConstantOperandsForInstr(const_cast<PHINode*>(PN), *MI, Target);
- CpVec2.push_back(*MI);
- CpVec.insert(CpVec.end(), CpVec2.begin(), CpVec2.end());
- }
-
- InsertPhiElimInstructions(PN->getIncomingBlock(i), CpVec);
- }
-
- std::vector<MachineInstr*> mvec;
- Target.getRegInfo().cpValue2Value(PhiCpRes, const_cast<PHINode*>(PN),
- mvec);
- BB->insert(BB->begin(), mvec.begin(), mvec.end());
- } // for each Phi Instr in BB
- } // for all BBs in function
-}
-
-//-------------------------------------------------------------------------
-// Thid method inserts a copy instruction to a predecessor BB as a result
-// of phi elimination.
-//-------------------------------------------------------------------------
-
-void
-InstructionSelection::InsertPhiElimInstructions(BasicBlock *BB,
- const std::vector<MachineInstr*>& CpVec)
-{
- Instruction *TermInst = (Instruction*)BB->getTerminator();
- MachineCodeForInstruction &MC4Term = MachineCodeForInstruction::get(TermInst);
- MachineInstr *FirstMIOfTerm = MC4Term.front();
- assert (FirstMIOfTerm && "No Machine Instrs for terminator");
-
- MachineFunction &MF = MachineFunction::get(BB->getParent());
-
- // FIXME: if PHI instructions existed in the machine code, this would be
- // unnecessary.
- MachineBasicBlock *MBB = 0;
- for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
- if (I->getBasicBlock() == BB) {
- MBB = I;
- break;
- }
-
- // find the position of first machine instruction generated by the
- // terminator of this BB
- MachineBasicBlock::iterator MCIt =
- std::find(MBB->begin(), MBB->end(), FirstMIOfTerm);
-
- assert(MCIt != MBB->end() && "Start inst of terminator not found");
-
- // insert the copy instructions just before the first machine instruction
- // generated for the terminator
- MBB->insert(MCIt, CpVec.begin(), CpVec.end());
-}
-
-
-//---------------------------------------------------------------------------
-// Function SelectInstructionsForTree
-//
-// Recursively walk the tree to select instructions.
-// Do this top-down so that child instructions can exploit decisions
-// made at the child instructions.
-//
-// E.g., if br(setle(reg,const)) decides the constant is 0 and uses
-// a branch-on-integer-register instruction, then the setle node
-// can use that information to avoid generating the SUBcc instruction.
-//
-// Note that this cannot be done bottom-up because setle must do this
-// only if it is a child of the branch (otherwise, the result of setle
-// may be used by multiple instructions).
-//---------------------------------------------------------------------------
-
-void
-InstructionSelection::SelectInstructionsForTree(InstrTreeNode* treeRoot,
- int goalnt)
-{
- // Get the rule that matches this node.
- //
- int ruleForNode = burm_rule(treeRoot->state, goalnt);
-
- if (ruleForNode == 0) {
- std::cerr << "Could not match instruction tree for instr selection\n";
- abort();
- }
-
- // Get this rule's non-terminals and the corresponding child nodes (if any)
- //
- short *nts = burm_nts[ruleForNode];
-
- // First, select instructions for the current node and rule.
- // (If this is a list node, not an instruction, then skip this step).
- // This function is specific to the target architecture.
- //
- if (treeRoot->opLabel != VRegListOp) {
- std::vector<MachineInstr*> minstrVec;
-
- InstructionNode* instrNode = (InstructionNode*)treeRoot;
- assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
-
- GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
-
- MachineCodeForInstruction &mvec =
- MachineCodeForInstruction::get(instrNode->getInstruction());
- mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
- }
-
- // Then, recursively compile the child nodes, if any.
- //
- if (nts[0]) {
- // i.e., there is at least one kid
- InstrTreeNode* kids[2];
- int currentRule = ruleForNode;
- burm_kids(treeRoot, currentRule, kids);
-
- // First skip over any chain rules so that we don't visit
- // the current node again.
- //
- while (ThisIsAChainRule(currentRule)) {
- currentRule = burm_rule(treeRoot->state, nts[0]);
- nts = burm_nts[currentRule];
- burm_kids(treeRoot, currentRule, kids);
- }
-
- // Now we have the first non-chain rule so we have found
- // the actual child nodes. Recursively compile them.
- //
- for (unsigned i = 0; nts[i]; i++) {
- assert(i < 2);
- InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
- if (nodeType == InstrTreeNode::NTVRegListNode ||
- nodeType == InstrTreeNode::NTInstructionNode)
- SelectInstructionsForTree(kids[i], nts[i]);
- }
- }
-
- // Finally, do any post-processing on this node after its children
- // have been translated
- //
- if (treeRoot->opLabel != VRegListOp)
- PostprocessMachineCodeForTree((InstructionNode*)treeRoot, ruleForNode, nts);
-}
-
-//---------------------------------------------------------------------------
-// Function PostprocessMachineCodeForTree
-//
-// Apply any final cleanups to machine code for the root of a subtree
-// after selection for all its children has been completed.
-//
-void
-InstructionSelection::PostprocessMachineCodeForTree(InstructionNode* instrNode,
- int ruleForNode,
- short* nts)
-{
- // Fix up any constant operands in the machine instructions to either
- // use an immediate field or to load the constant into a register
- // Walk backwards and use direct indexes to allow insertion before current
- //
- Instruction* vmInstr = instrNode->getInstruction();
- MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(vmInstr);
- for (unsigned i = mvec.size(); i != 0; --i) {
- std::vector<MachineInstr*> loadConstVec =
- FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target);
-
- mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end());
- }
-}
-
-
-//===----------------------------------------------------------------------===//
-// createInstructionSelectionPass - Public entrypoint for instruction selection
-// and this file as a whole...
-//
-FunctionPass *llvm::createInstructionSelectionPass(TargetMachine &TM) {
- return new InstructionSelection(TM);
-}
+++ /dev/null
-//===-- InstrSelectionSupport.cpp -----------------------------------------===//
-//
-// 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.
-//
-//===----------------------------------------------------------------------===//
-//
-// Target-independent instruction selection code. See SparcInstrSelection.cpp
-// for usage.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/CodeGen/InstrSelectionSupport.h"
-#include "llvm/CodeGen/InstrSelection.h"
-#include "llvm/CodeGen/MachineInstrAnnot.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/CodeGen/InstrForest.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetRegInfo.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Constants.h"
-#include "llvm/BasicBlock.h"
-#include "llvm/DerivedTypes.h"
-#include "../../Target/Sparc/SparcInstrSelectionSupport.h" // FIXME!
-
-namespace llvm {
-
-// Generate code to load the constant into a TmpInstruction (virtual reg) and
-// returns the virtual register.
-//
-static TmpInstruction*
-InsertCodeToLoadConstant(Function *F,
- Value* opValue,
- Instruction* vmInstr,
- std::vector<MachineInstr*>& loadConstVec,
- TargetMachine& target)
-{
- // Create a tmp virtual register to hold the constant.
- MachineCodeForInstruction &mcfi = MachineCodeForInstruction::get(vmInstr);
- TmpInstruction* tmpReg = new TmpInstruction(mcfi, opValue);
-
- target.getInstrInfo().CreateCodeToLoadConst(target, F, opValue, tmpReg,
- loadConstVec, mcfi);
-
- // Record the mapping from the tmp VM instruction to machine instruction.
- // Do this for all machine instructions that were not mapped to any
- // other temp values created by
- // tmpReg->addMachineInstruction(loadConstVec.back());
-
- return tmpReg;
-}
-
-
-MachineOperand::MachineOperandType
-ChooseRegOrImmed(int64_t intValue,
- bool isSigned,
- MachineOpCode opCode,
- const TargetMachine& target,
- bool canUseImmed,
- unsigned int& getMachineRegNum,
- int64_t& getImmedValue)
-{
- MachineOperand::MachineOperandType opType=MachineOperand::MO_VirtualRegister;
- getMachineRegNum = 0;
- getImmedValue = 0;
-
- if (canUseImmed &&
- target.getInstrInfo().constantFitsInImmedField(opCode, intValue)) {
- opType = isSigned? MachineOperand::MO_SignExtendedImmed
- : MachineOperand::MO_UnextendedImmed;
- getImmedValue = intValue;
- } else if (intValue == 0 && target.getRegInfo().getZeroRegNum() >= 0) {
- opType = MachineOperand::MO_MachineRegister;
- getMachineRegNum = target.getRegInfo().getZeroRegNum();
- }
-
- return opType;
-}
-
-
-MachineOperand::MachineOperandType
-ChooseRegOrImmed(Value* val,
- MachineOpCode opCode,
- const TargetMachine& target,
- bool canUseImmed,
- unsigned int& getMachineRegNum,
- int64_t& getImmedValue)
-{
- getMachineRegNum = 0;
- getImmedValue = 0;
-
- // To use reg or immed, constant needs to be integer, bool, or a NULL pointer
- // TargetInstrInfo::ConvertConstantToIntType() does the right conversions:
- bool isValidConstant;
- uint64_t valueToUse =
- target.getInstrInfo().ConvertConstantToIntType(target, val, val->getType(),
- isValidConstant);
- if (! isValidConstant)
- return MachineOperand::MO_VirtualRegister;
-
- // Now check if the constant value fits in the IMMED field.
- //
- return ChooseRegOrImmed((int64_t) valueToUse, val->getType()->isSigned(),
- opCode, target, canUseImmed,
- getMachineRegNum, getImmedValue);
-}
-
-//---------------------------------------------------------------------------
-// Function: FixConstantOperandsForInstr
-//
-// Purpose:
-// Special handling for constant operands of a machine instruction
-// -- if the constant is 0, use the hardwired 0 register, if any;
-// -- if the constant fits in the IMMEDIATE field, use that field;
-// -- else create instructions to put the constant into a register, either
-// directly or by loading explicitly from the constant pool.
-//
-// In the first 2 cases, the operand of `minstr' is modified in place.
-// Returns a vector of machine instructions generated for operands that
-// fall under case 3; these must be inserted before `minstr'.
-//---------------------------------------------------------------------------
-
-std::vector<MachineInstr*>
-FixConstantOperandsForInstr(Instruction* vmInstr,
- MachineInstr* minstr,
- TargetMachine& target)
-{
- std::vector<MachineInstr*> MVec;
-
- MachineOpCode opCode = minstr->getOpCode();
- const TargetInstrInfo& instrInfo = target.getInstrInfo();
- int resultPos = instrInfo.getResultPos(opCode);
- int immedPos = instrInfo.getImmedConstantPos(opCode);
-
- Function *F = vmInstr->getParent()->getParent();
-
- for (unsigned op=0; op < minstr->getNumOperands(); op++)
- {
- const MachineOperand& mop = minstr->getOperand(op);
-
- // Skip the result position, preallocated machine registers, or operands
- // that cannot be constants (CC regs or PC-relative displacements)
- if (resultPos == (int)op ||
- mop.getType() == MachineOperand::MO_MachineRegister ||
- mop.getType() == MachineOperand::MO_CCRegister ||
- mop.getType() == MachineOperand::MO_PCRelativeDisp)
- continue;
-
- bool constantThatMustBeLoaded = false;
- unsigned int machineRegNum = 0;
- int64_t immedValue = 0;
- Value* opValue = NULL;
- MachineOperand::MachineOperandType opType =
- MachineOperand::MO_VirtualRegister;
-
- // Operand may be a virtual register or a compile-time constant
- if (mop.getType() == MachineOperand::MO_VirtualRegister) {
- assert(mop.getVRegValue() != NULL);
- opValue = mop.getVRegValue();
- if (Constant *opConst = dyn_cast<Constant>(opValue)) {
- opType = ChooseRegOrImmed(opConst, opCode, target,
- (immedPos == (int)op), machineRegNum,
- immedValue);
- if (opType == MachineOperand::MO_VirtualRegister)
- constantThatMustBeLoaded = true;
- }
- } else {
- //
- // If the operand is from the constant pool, don't try to change it.
- //
- if (mop.getType() == MachineOperand::MO_ConstantPoolIndex) {
- continue;
- }
- assert(mop.isImmediate());
- bool isSigned = mop.getType() == MachineOperand::MO_SignExtendedImmed;
-
- // Bit-selection flags indicate an instruction that is extracting
- // bits from its operand so ignore this even if it is a big constant.
- if (mop.isHiBits32() || mop.isLoBits32() ||
- mop.isHiBits64() || mop.isLoBits64())
- continue;
-
- opType = ChooseRegOrImmed(mop.getImmedValue(), isSigned,
- opCode, target, (immedPos == (int)op),
- machineRegNum, immedValue);
-
- if (opType == MachineOperand::MO_SignExtendedImmed ||
- opType == MachineOperand::MO_UnextendedImmed) {
- // The optype is an immediate value
- // This means we need to change the opcode, e.g. ADDr -> ADDi
- unsigned newOpcode = convertOpcodeFromRegToImm(opCode);
- minstr->setOpcode(newOpcode);
- }
-
- if (opType == mop.getType())
- continue; // no change: this is the most common case
-
- if (opType == MachineOperand::MO_VirtualRegister) {
- constantThatMustBeLoaded = true;
- opValue = isSigned
- ? (Value*)ConstantSInt::get(Type::LongTy, immedValue)
- : (Value*)ConstantUInt::get(Type::ULongTy,(uint64_t)immedValue);
- }
- }
-
- if (opType == MachineOperand::MO_MachineRegister)
- minstr->SetMachineOperandReg(op, machineRegNum);
- else if (opType == MachineOperand::MO_SignExtendedImmed ||
- opType == MachineOperand::MO_UnextendedImmed) {
- minstr->SetMachineOperandConst(op, opType, immedValue);
- // The optype is or has become an immediate
- // This means we need to change the opcode, e.g. ADDr -> ADDi
- unsigned newOpcode = convertOpcodeFromRegToImm(opCode);
- minstr->setOpcode(newOpcode);
- } else if (constantThatMustBeLoaded ||
- (opValue && isa<GlobalValue>(opValue)))
- { // opValue is a constant that must be explicitly loaded into a reg
- assert(opValue);
- TmpInstruction* tmpReg = InsertCodeToLoadConstant(F, opValue, vmInstr,
- MVec, target);
- minstr->SetMachineOperandVal(op, MachineOperand::MO_VirtualRegister,
- tmpReg);
- }
- }
-
- // Also, check for implicit operands used by the machine instruction
- // (no need to check those defined since they cannot be constants).
- // These include:
- // -- arguments to a Call
- // -- return value of a Return
- // Any such operand that is a constant value needs to be fixed also.
- // The current instructions with implicit refs (viz., Call and Return)
- // have no immediate fields, so the constant always needs to be loaded
- // into a register.
- //
- bool isCall = instrInfo.isCall(opCode);
- unsigned lastCallArgNum = 0; // unused if not a call
- CallArgsDescriptor* argDesc = NULL; // unused if not a call
- if (isCall)
- argDesc = CallArgsDescriptor::get(minstr);
-
- for (unsigned i=0, N=minstr->getNumImplicitRefs(); i < N; ++i)
- if (isa<Constant>(minstr->getImplicitRef(i)) ||
- isa<GlobalValue>(minstr->getImplicitRef(i)))
- {
- Value* oldVal = minstr->getImplicitRef(i);
- TmpInstruction* tmpReg =
- InsertCodeToLoadConstant(F, oldVal, vmInstr, MVec, target);
- minstr->setImplicitRef(i, tmpReg);
-
- if (isCall) {
- // find and replace the argument in the CallArgsDescriptor
- unsigned i=lastCallArgNum;
- while (argDesc->getArgInfo(i).getArgVal() != oldVal)
- ++i;
- assert(i < argDesc->getNumArgs() &&
- "Constant operands to a call *must* be in the arg list");
- lastCallArgNum = i;
- argDesc->getArgInfo(i).replaceArgVal(tmpReg);
- }
- }
-
- return MVec;
-}
-
-} // End llvm namespace
+++ /dev/null
-##===- lib/CodeGen/InstrSelection/Makefile -----------------*- Makefile -*-===##
-#
-# 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.
-#
-##===----------------------------------------------------------------------===##
-LEVEL = ../../..
-
-DIRS =
-
-LIBRARYNAME = select
-
-include $(LEVEL)/Makefile.common
-##===- lib/CodeGen/Makefile ------------------------------*- Makefile -*-===##
+##===- lib/CodeGen/Makefile --------------------------------*- Makefile -*-===##
#
# The LLVM Compiler Infrastructure
#
# the University of Illinois Open Source License. See LICENSE.TXT for details.
#
##===----------------------------------------------------------------------===##
+
LEVEL = ../..
-PARALLEL_DIRS = InstrSelection InstrSched SelectionDAG
+PARALLEL_DIRS = InstrSched SelectionDAG
LIBRARYNAME = codegen
include $(LEVEL)/Makefile.common
projects / oota-llvm.git / commitdiff