DFG of machine functions

Hi,
I am trying to generate the DFG of machine functions.

Initially, I added a pass to generate the DFG of LLVM IR functions. This was based on the mail thread - http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-September/025582.html. This pass worked fine and I was able to generate DFG of LLVM IR functions.

Later, I ported the DFG pass code for machine functions. I ported the InstIterator.h (which was required to use inst_iterator in the template <> struct GraphTraits<DFG<Function*> >) to MachineInstrIterator.h to iterate over machine instructions in a machine function. But the build is throwing the following error:

llvm[2]: Compiling MC_DFG.cpp for Debug+Asserts build
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h: In member function ‘void llvm::GraphWriter::writeNodes() [with GraphType = llvm::MCDFGraphllvm::MachineFunction*]’:
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h:100: instantiated from ‘void llvm::GraphWriter::writeGraph(const std::string&) [with GraphType = llvm::MCDFGraphllvm::MachineFunction*]’
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h:304: instantiated from ‘llvm::raw_ostream& llvm::WriteGraph(llvm::raw_ostream&, const GraphType&, bool, const llvm::Twine&) [with GraphType = llvm::MCDFGraphllvm::MachineFunction*]’
/home/abhi/work/llvm31/llvm/lib/CodeGen/MC_DFG.cpp:249: instantiated from here
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h:139: error: no matching function for call to ‘llvm::GraphWriter<llvm::MCDFGraphllvm::MachineFunction* >::isNodeHidden(llvm::MachineInstr&)’
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h:143: note: candidates are: bool llvm::GraphWriter::isNodeHidden(typename llvm::GraphTraits::NodeType&) [with GraphType = llvm::MCDFGraphllvm::MachineFunction*]
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h:147: note: bool llvm::GraphWriter::isNodeHidden(typename llvm::GraphTraits::NodeType* const*) [with GraphType = llvm::MCDFGraphllvm::MachineFunction*]
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h:151: note: bool llvm::GraphWriter::isNodeHidden(typename llvm::GraphTraits::NodeType*) [with GraphType = llvm::MCDFGraphllvm::MachineFunction*]
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h:140: error: no matching function for call to ‘llvm::GraphWriter<llvm::MCDFGraphllvm::MachineFunction* >::writeNode(llvm::MachineInstr&)’
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h:155: note: candidates are: void llvm::GraphWriter::writeNode(typename llvm::GraphTraits::NodeType&) [with GraphType = llvm::MCDFGraphllvm::MachineFunction*]
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h:159: note: void llvm::GraphWriter::writeNode(typename llvm::GraphTraits::NodeType* const*) [with GraphType = llvm::MCDFGraphllvm::MachineFunction*]
/home/abhi/work/llvm31/llvm/include/llvm/Support/GraphWriter.h:163: note: void llvm::GraphWriter::writeNode(typename llvm::GraphTraits::NodeType*) [with GraphType = llvm::MCDFGraphllvm::MachineFunction*]
gmake[2]: *** [/home/abhi/work/llvm31/llvm-build-new/lib/CodeGen/Debug+Asserts/MC_DFG.o] Error 1
gmake[2]: Leaving directory /home/abhi/work/llvm31/llvm-build-new/lib/CodeGen' gmake[1]: *** [CodeGen/.makeall] Error 2 gmake[1]: Leaving directory /home/abhi/work/llvm31/llvm-build-new/lib’
gmake: *** [all] Error 1

The error seems to be a mismatch between types of the argument passed to the isNodeHidden and writeNode function in the GraphWriter.h file. But I am not sure where this type mismatch is originating from or how to fix it. Any idea what could be the issue here?

Here are some of the code snippets:

//templates for DFG and specializations of GraphTraits

template
class MCDFGraph {
private:
T p;
public:
MCDFGraph(T t) : p(t) {}
T operator*() { return p; }
};

template <> struct GraphTraits<MCDFGraph<MachineFunction*> > : public
GraphTraits<Value*> {
typedef mc_inst_iterator nodes_iterator;

static nodes_iterator nodes_begin(MCDFGraph<MachineFunction *> F) {
return mc_inst_begin(*F);
}

static nodes_iterator nodes_end(MCDFGraph<MachineFunction *> F) {
return mc_inst_end(*F);
}
};

template<>
struct DOTGraphTraits<MCDFGraph<MachineFunction*> > : public DefaultDOTGraphTraits {

DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}

static std::string getGraphName(MCDFGraph<MachineFunction *> F) {
return “DFG for the function”;
}

static std::string getSimpleNodeLabel(Value *Node,
const MCDFGraph<MachineFunction *> &F) {
std::string Str;
raw_string_ostream OS(Str);

WriteAsOperand(OS, Node, false);
return OS.str();
}

static std::string getCompleteNodeLabel(Value *Node,
const MCDFGraph<MachineFunction *> &F) {
std::string Str;
raw_string_ostream OS(Str);

if (!Node->getName().empty()) {
WriteAsOperand(OS, Node, false);
OS << “:\n”;
}

OS << *Node;
std::string OutStr = OS.str();
if (OutStr[0] == ‘\n’) OutStr.erase(OutStr.begin());

// Process string output to make it nicer…
for (unsigned i = 0; i != OutStr.length(); ++i)
if (OutStr[i] == ‘\n’) { // Left justify
OutStr[i] = ‘\’;
OutStr.insert(OutStr.begin()+i+1, ‘l’);
} else if (OutStr[i] == ‘;’) { // Delete comments!
unsigned Idx = OutStr.find(‘\n’, i+1); // Find end of line
OutStr.erase(OutStr.begin()+i, OutStr.begin()+Idx);
–i;
}

return OutStr;
}

std::string getNodeLabel(Value *&Node,
const MCDFGraph<MachineFunction *> &Graph) {
if (isSimple())
return getSimpleNodeLabel(Node, Graph);
else
return getCompleteNodeLabel(Node, Graph);
}

};

//Calls to ViewGraph and WriteGraph from the respective passes’ runOnMachineFunction

ViewGraph(MCDFGraph<MachineFunction*>(&F), “Function:” + (F.getFunction())->getName());

WriteGraph(File, (MCDFGraph<MachineFunction*>)&F);

The MachineInstrIterator.h is quite lengthy, please let me know if I need to post it.

I tried debugging it and the issue seems to be in the implementation of MachineInstrIterator.h and the way it interacts with GraphWriter.h functions. I found this by replacing the ( template <> struct GraphTraits<MCDFGraph<MachineFunction*> >) with a similar MCDFGraph based template of CFG similar to the one in MachineFunction.h (similarly replacing the DOTGraphTraits with the one for CFG) and it works and pops up the GraphViz window with the CFG for the machine function.

I am attaching the MachineInstrIterator.h file.

Also, I wrote a pass using the mc_inst_iterator (defined in the MachineInstrIterator.h - the direct iterator over MachineInstr in a MachineFunction) to iterate through the machine instructions in a machine function and it works.

I tried building LLVM 3.1 using clang in order to get a better idea of the error. Here is the build error output:

/home/arhishee/work/llvm-3.1.src/include/llvm/Support/GraphWriter.h:143:8: note: candidate function not viable: no known conversion from
‘IIty’ (aka ‘llvm::MachineInstr’) to ‘NodeType &’ (aka ‘llvm::Value &’) for 1st argument;
bool isNodeHidden(NodeType &Node) {
^
/home/arhishee/work/llvm-3.1.src/include/llvm/Support/GraphWriter.h:147:8: note: candidate function not viable: no known conversion from
‘IIty’ (aka ‘llvm::MachineInstr’) to ‘NodeType *const *’ (aka ‘llvm::Value *const *’) for 1st argument;
bool isNodeHidden(NodeType *const *Node) {
^
/home/arhishee/work/llvm-3.1.src/include/llvm/Support/GraphWriter.h:151:8: note: candidate function not viable: no known conversion from
‘IIty’ (aka ‘llvm::MachineInstr’) to ‘NodeType *’ (aka ‘llvm::Value *’) for 1st argument;
bool isNodeHidden(NodeType *Node) {

This seems to be a clear type mismatch between the argument expected by isNodeHidden in GraphWriter.h (either of 3 types - NodeType &Node, NodeType *const *Node, NodeType *Node, where NodeType corresponds to llvm::Value) and the llvm::MachineInstr type passed through the mc_inst_iterator template. But I am not sure how to fix it. Can someone provide some debug pointers?

MachineInstrIterator.h (5.89 KB)

I tried debugging it further. I think the issue lies in MachineInstr not being derived from the User base class. If I can do use_begin and use_end with MachineInstr, then instead of extending GraphTraits<MCDFGraph<MachineFunction*> > from GraphTraits<Value*> (defined in DataFlow.h), I can extend it from GraphTraits<MachineInstr*> (after defining it similar to the one in DataFlow.h but using the use_begin and use_end of MachineInstr) and the type mismatch in isNodeHidden may go away.

I tried adding User to the list of base classes of MachineInstr (and Value to the base classes of MachineBasicBlock, this may or may not be required), but there are some ctor mismatches. I was not using the usual Value and User constructors in the ctors of MachineBasicBlock and MachineInstr, instead added empty ctors for Value and User. Here is the build error report:

/home/arhishee/work/llvm-3.1.src/lib/CodeGen/MachineFunction.cpp:155:10: error: no matching function for call to ‘operator new’
return new (InstructionRecycler.Allocate(Allocator))
^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/arhishee/work/llvm-3.1.src/include/llvm/User.h:51:9: note: candidate function not viable: no known conversion from
‘llvm::MachineInstr *’ to ‘unsigned int’ for 2nd argument;
void *operator new(size_t s, unsigned Us);
^
/home/arhishee/work/llvm-3.1.src/include/llvm/User.h:35:9: note: candidate function not viable: requires 1 argument, but 2 were provided
void *operator new(size_t); // Do not implement
^
/home/arhishee/work/llvm-3.1.src/lib/CodeGen/MachineFunction.cpp:165:10: error: no matching function for call to ‘operator new’
return new (InstructionRecycler.Allocate(Allocator))
^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/arhishee/work/llvm-3.1.src/include/llvm/User.h:51:9: note: candidate function not viable: no known conversion from
‘llvm::MachineInstr *’ to ‘unsigned int’ for 2nd argument;
void *operator new(size_t s, unsigned Us);
^
/home/arhishee/work/llvm-3.1.src/include/llvm/User.h:35:9: note: candidate function not viable: requires 1 argument, but 2 were provided
void *operator new(size_t); // Do not implement

I tried #include , and/or changing the new in MachineFunction.cpp to ::new; that doesn’t help.

Also, instead of iterating over uses of MachineInstr, is there a way I can use the iteration over MachineRegisterInfo uses to build the DFG since use_begin/use_end and def_begin/def_end are already defined there. Since this is about DFG, I think that may suffice.