-// $Id$
-//***************************************************************************
-// File:
-// SchedGraph.cpp
-//
-// Purpose:
-// Scheduling graph based on SSA graph plus extra dependence edges
-// capturing dependences due to machine resources (machine registers,
-// CC registers, and any others).
-//
-// History:
-// 7/20/01 - Vikram Adve - Created
-//**************************************************************************/
+//===- SchedGraph.cpp - Scheduling Graph Implementation -------------------===//
+//
+// Scheduling graph based on SSA graph plus extra dependence edges capturing
+// dependences due to machine resources (machine registers, CC registers, and
+// any others).
+//
+//===----------------------------------------------------------------------===//
#include "SchedGraph.h"
#include "llvm/CodeGen/InstrSelection.h"
-#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/Target/MachineInstrInfo.h"
+#include "llvm/CodeGen/MachineCodeForBasicBlock.h"
#include "llvm/Target/MachineRegInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/BasicBlock.h"
#include "llvm/Function.h"
#include "llvm/iOther.h"
#include "Support/StringExtras.h"
#include "Support/STLExtras.h"
-#include <iostream>
using std::vector;
using std::pair;
-using std::hash_map;
using std::cerr;
//*********************** Internal Data Structures *************************/
{
}
-void SchedGraphEdge::dump(int indent=0) const {
+void SchedGraphEdge::dump(int indent) const {
cerr << std::string(indent*2, ' ') << *this;
}
deleter<SchedGraphEdge>);
}
-void SchedGraphNode::dump(int indent=0) const {
+void SchedGraphNode::dump(int indent) const {
cerr << std::string(indent*2, ' ') << *this;
}
// Find the first branch instr in the sequence of machine instrs for term
//
unsigned first = 0;
- while (!mii.isBranch(termMvec[first]->getOpCode()))
+ while (! mii.isBranch(termMvec[first]->getOpCode()) &&
+ ! mii.isReturn(termMvec[first]->getOpCode()))
++first;
assert(first < termMvec.size() &&
- "No branch instructions for BR? Ok, but weird! Delete assertion.");
+ "No branch instructions for terminator? Ok, but weird!");
if (first == termMvec.size())
return;
-
- SchedGraphNode* firstBrNode = this->getGraphNodeForInstr(termMvec[first]);
-
+
+ SchedGraphNode* firstBrNode = getGraphNodeForInstr(termMvec[first]);
+
// Add CD edges from each instruction in the sequence to the
// *last preceding* branch instr. in the sequence
// Use a latency of 0 because we only need to prevent out-of-order issue.
//
- for (int i = (int) termMvec.size()-1; i > (int) first; i--)
+ for (unsigned i = termMvec.size(); i > first+1; --i)
{
- SchedGraphNode* toNode = this->getGraphNodeForInstr(termMvec[i]);
- assert(toNode && "No node for instr generated for branch?");
+ SchedGraphNode* toNode = getGraphNodeForInstr(termMvec[i-1]);
+ assert(toNode && "No node for instr generated for branch/ret?");
- for (int j = i-1; j >= 0; j--)
- if (mii.isBranch(termMvec[j]->getOpCode()))
+ for (unsigned j = i-1; j != 0; --j)
+ if (mii.isBranch(termMvec[j-1]->getOpCode()) ||
+ mii.isReturn(termMvec[j-1]->getOpCode()))
{
- SchedGraphNode* brNode = this->getGraphNodeForInstr(termMvec[j]);
- assert(brNode && "No node for instr generated for branch?");
+ SchedGraphNode* brNode = getGraphNodeForInstr(termMvec[j-1]);
+ assert(brNode && "No node for instr generated for branch/ret?");
(void) new SchedGraphEdge(brNode, toNode, SchedGraphEdge::CtrlDep,
SchedGraphEdge::NonDataDep, 0);
break; // only one incoming edge is enough
// Add CD edges from each instruction preceding the first branch
// to the first branch. Use a latency of 0 as above.
//
- for (int i = first-1; i >= 0; i--)
+ for (unsigned i = first; i != 0; --i)
{
- SchedGraphNode* fromNode = this->getGraphNodeForInstr(termMvec[i]);
+ SchedGraphNode* fromNode = getGraphNodeForInstr(termMvec[i-1]);
assert(fromNode && "No node for instr generated for branch?");
(void) new SchedGraphEdge(fromNode, firstBrNode, SchedGraphEdge::CtrlDep,
SchedGraphEdge::NonDataDep, 0);
// all preceding instructions in the basic block. Use 0 latency again.
//
const BasicBlock* bb = firstBrNode->getBB();
- const MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
+ const MachineCodeForBasicBlock& mvec = MachineCodeForBasicBlock::get(bb);
for (unsigned i=0, N=mvec.size(); i < N; i++)
{
- if (mvec[i] == termMvec[first]) // reached the first branch
+ if (mvec[i] == termMvec[first]) // reached the first branch
break;
SchedGraphNode* fromNode = this->getGraphNodeForInstr(mvec[i]);
SchedGraphNode* node = regRefVec[i].first;
unsigned int opNum = regRefVec[i].second;
bool isDef = node->getMachineInstr()->operandIsDefined(opNum);
-
+ bool isDefAndUse =
+ node->getMachineInstr()->operandIsDefinedAndUsed(opNum);
+
for (unsigned p=0; p < i; ++p)
{
SchedGraphNode* prevNode = regRefVec[p].first;
unsigned int prevOpNum = regRefVec[p].second;
bool prevIsDef =
prevNode->getMachineInstr()->operandIsDefined(prevOpNum);
-
+ bool prevIsDefAndUse =
+ prevNode->getMachineInstr()->operandIsDefinedAndUsed(prevOpNum);
if (isDef)
- new SchedGraphEdge(prevNode, node, regNum,
- (prevIsDef)? SchedGraphEdge::OutputDep
- : SchedGraphEdge::AntiDep);
- else if (prevIsDef)
- new SchedGraphEdge(prevNode, node, regNum,
- SchedGraphEdge::TrueDep);
+ {
+ if (prevIsDef)
+ new SchedGraphEdge(prevNode, node, regNum,
+ SchedGraphEdge::OutputDep);
+ if (!prevIsDef || prevIsDefAndUse)
+ new SchedGraphEdge(prevNode, node, regNum,
+ SchedGraphEdge::AntiDep);
+ }
+
+ if (prevIsDef)
+ if (!isDef || isDefAndUse)
+ new SchedGraphEdge(prevNode, node, regNum,
+ SchedGraphEdge::TrueDep);
}
}
}
}
+// Adds dependences to/from refNode from/to all other defs
+// in the basic block. refNode may be a use, a def, or both.
+// We do not consider other uses because we are not building use-use deps.
+//
void
SchedGraph::addEdgesForValue(SchedGraphNode* refNode,
const RefVec& defVec,
const Value* defValue,
bool refNodeIsDef,
+ bool refNodeIsDefAndUse,
const TargetMachine& target)
{
+ bool refNodeIsUse = !refNodeIsDef || refNodeIsDefAndUse;
+
// Add true or output dep edges from all def nodes before refNode in BB.
// Add anti or output dep edges to all def nodes after refNode.
for (RefVec::const_iterator I=defVec.begin(), E=defVec.end(); I != E; ++I)
continue; // Dont add any self-loops
if ((*I).first->getOrigIndexInBB() < refNode->getOrigIndexInBB())
- // (*).first is before refNode
- (void) new SchedGraphEdge((*I).first, refNode, defValue,
- (refNodeIsDef)? SchedGraphEdge::OutputDep
- : SchedGraphEdge::TrueDep);
+ { // (*).first is before refNode
+ if (refNodeIsDef)
+ (void) new SchedGraphEdge((*I).first, refNode, defValue,
+ SchedGraphEdge::OutputDep);
+ if (refNodeIsUse)
+ (void) new SchedGraphEdge((*I).first, refNode, defValue,
+ SchedGraphEdge::TrueDep);
+ }
else
- // (*).first is after refNode
- (void) new SchedGraphEdge(refNode, (*I).first, defValue,
- (refNodeIsDef)? SchedGraphEdge::OutputDep
- : SchedGraphEdge::AntiDep);
+ { // (*).first is after refNode
+ if (refNodeIsDef)
+ (void) new SchedGraphEdge(refNode, (*I).first, defValue,
+ SchedGraphEdge::OutputDep);
+ if (refNodeIsUse)
+ (void) new SchedGraphEdge(refNode, (*I).first, defValue,
+ SchedGraphEdge::AntiDep);
+ }
}
}
ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI);
if (I != valueToDefVecMap.end())
addEdgesForValue(node, (*I).second, mop.getVRegValue(),
- minstr.operandIsDefined(i), target);
+ minstr.operandIsDefined(i),
+ minstr.operandIsDefinedAndUsed(i), target);
}
break;
// value of a Ret instruction.
//
for (unsigned i=0, N=minstr.getNumImplicitRefs(); i < N; ++i)
- if (! minstr.implicitRefIsDefined(i))
+ if (! minstr.implicitRefIsDefined(i) ||
+ minstr.implicitRefIsDefinedAndUsed(i))
if (const Instruction* srcI =
dyn_cast_or_null<Instruction>(minstr.getImplicitRef(i)))
{
ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI);
if (I != valueToDefVecMap.end())
addEdgesForValue(node, (*I).second, minstr.getImplicitRef(i),
- minstr.implicitRefIsDefined(i), target);
+ minstr.implicitRefIsDefined(i),
+ minstr.implicitRefIsDefinedAndUsed(i), target);
}
}
-#undef NEED_SEPARATE_NONSSA_EDGES_CODE
-#ifdef NEED_SEPARATE_NONSSA_EDGES_CODE
-void
-SchedGraph::addNonSSAEdgesForValue(const Instruction* instr,
- const TargetMachine& target)
-{
- if (isa<PHINode>(instr))
- return;
-
- MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
- const MachineInstrInfo& mii = target.getInstrInfo();
- RefVec refVec;
-
- for (unsigned i=0, N=mvec.size(); i < N; i++)
- for (int o=0, N = mii.getNumOperands(mvec[i]->getOpCode()); o < N; o++)
- {
- const MachineOperand& mop = mvec[i]->getOperand(o);
-
- if ((mop.getOperandType() == MachineOperand::MO_VirtualRegister ||
- mop.getOperandType() == MachineOperand::MO_CCRegister)
- && mop.getVRegValue() == (Value*) instr)
- {
- // this operand is a definition or use of value `instr'
- SchedGraphNode* node = this->getGraphNodeForInstr(mvec[i]);
- assert(node && "No node for machine instruction in this BB?");
- refVec.push_back(std::make_pair(node, o));
- }
- }
-
- // refVec is ordered by control flow order of the machine instructions
- for (unsigned i=0; i < refVec.size(); ++i)
- {
- SchedGraphNode* node = refVec[i].first;
- unsigned int opNum = refVec[i].second;
- bool isDef = node->getMachineInstr()->operandIsDefined(opNum);
-
- if (isDef)
- // add output and/or anti deps to this definition
- for (unsigned p=0; p < i; ++p)
- {
- SchedGraphNode* prevNode = refVec[p].first;
- if (prevNode != node)
- {
- bool prevIsDef = prevNode->getMachineInstr()->
- operandIsDefined(refVec[p].second);
- new SchedGraphEdge(prevNode, node, SchedGraphEdge::ValueDep,
- (prevIsDef)? SchedGraphEdge::OutputDep
- : SchedGraphEdge::AntiDep);
- }
- }
- }
-}
-#endif //NEED_SEPARATE_NONSSA_EDGES_CODE
-
-
void
SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target,
SchedGraphNode* node,
// Build graph nodes for each VM instruction and gather def/use info.
// Do both those together in a single pass over all machine instructions.
- const MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
+ const MachineCodeForBasicBlock& mvec = MachineCodeForBasicBlock::get(bb);
for (unsigned i=0; i < mvec.size(); i++)
if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
{
// Find the machine instruction that makes a copy of inval to (*PI).
// This must be in the current basic block (bb).
- const MachineCodeForVMInstr& mvec = (*PI)->getMachineInstrVec();
+ const MachineCodeForVMInstr& mvec = MachineCodeForBasicBlock::get(*PI);
const MachineInstr* theCopy = NULL;
for (unsigned i=0; i < mvec.size() && theCopy == NULL; i++)
if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
for (int o=0, N=(int) mvec[i]->getNumOperands(); o < N; o++)
{
const MachineOperand& mop = mvec[i]->getOperand(o);
+
if (mvec[i]->operandIsDefined(o))
assert(mop.getVRegValue() == (*PI) && "dest shd be my Phi");
- else if (mop.getVRegValue() == inVal)
- { // found the copy!
- theCopy = mvec[i];
- break;
- }
+
+ if (! mvec[i]->operandIsDefined(o) ||
+ NOT NEEDED? mvec[i]->operandIsDefinedAndUsed(o))
+ if (mop.getVRegValue() == inVal)
+ { // found the copy!
+ theCopy = mvec[i];
+ break;
+ }
}
// Found the dang instruction. Now create a node and do the rest...
//
//----------------------------------------------------------------
- MachineCodeForBasicBlock& bbMvec = bb->getMachineInstrVec();
+ MachineCodeForBasicBlock& bbMvec = MachineCodeForBasicBlock::get(bb);
// First, add edges to the terminator instruction of the basic block.
this->addCDEdges(bb->getTerminator(), target);
const TargetMachine& target)
{
for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI)
- addGraph(new SchedGraph(*BI, target));
+ addGraph(new SchedGraph(BI, target));
}
projects / oota-llvm.git / blobdiff