Two quick questions on call graph nodes

Hello all,

When I examined the callgraph generated by LLVM via this command:

  opt -print-callgraph-sccs -dot-callgraph a.out.bc

I ran into two confusions:

First, there is a "indirect call node" dominating all other nodes
(include "main"). My question is: what does this special node serves
for?

Second, there are two identical functions except that the functions
have slightly different names.

  define void @_ZN6StringC2Ev(%struct.String* %this) nounwind ssp {}
  define void @_ZN6StringC1Ev(%struct.String* %this) nounwind ssp {}

So, why is it so?

Thanks!

best,
Xiaolong

PS: My running example is a simple code as below:

  #include "string.h"

  int main()
  {
    String y, z;
    String x("Hello World!");
    y = x; // strongly update y
    z = y; // use y
    return 0;
  }

The string class definition is:

  class String {
  public:
    // Default constructor
    String();

    // Copy constructor
    String(const String& that);

    // One argument constructor that takes a character array as the initial
    // value for the string
    String(const char str[]);

    // Destructor
    ~String();

    // Assignment operator
    String& operator=(const String& that);
                                                                          
  private:
    int length;
    int capacity;
    char* buffer;
  };

  String::String() : capacity(0), length(0), buffer(0)
  {
    // Nothing else to do
  }
                                                                          
  String::String(const String& that)
  {
    ...
  }

  ...

Hi Xiaolong,

First, there is a "indirect call node" dominating all other nodes
(include "main"). My question is: what does this special node serves
for?

what version of LLVM are you using? I don't think LLVM 2.7 uses a
"indirect call node". However it does use a "external node", which
is used when a function external to the current module is called.

Second, there are two identical functions except that the functions
have slightly different names.

   define void @_ZN6StringC2Ev(%struct.String* %this) nounwind ssp {}
   define void @_ZN6StringC1Ev(%struct.String* %this) nounwind ssp {}

So, why is it so?

These are generated by the C++ front-end, and represent the base object
constructor and the complete object constructor respectively.

Ciao,

Duncan.

Hello Duncan,

Thanks!

> First, there is a "indirect call node" dominating all other nodes
> (include "main"). My question is: what does this special node serves
> for?

what version of LLVM are you using? I don't think LLVM 2.7 uses a
"indirect call node". However it does use a "external node", which
is used when a function external to the current module is called.

The "external node" makes sense. However, I am using LLVM 2.8. (See
the output from "opt -version") and build it against Revision 105271
in the svn repository. So, can I say that the presence of "indirect
call node" is new in LLVM 2.8?
  
  Low Level Virtual Machine (http://llvm.org/):
    llvm version 2.8svn
    DEBUG build with assertions.
    Built Jun 1 2010 (12:21:00).
    Host: x86_64-apple-darwin10
    Host CPU: core2

Best,
Xiaolong

Hi Xiaolong,

what version of LLVM are you using? I don't think LLVM 2.7 uses a
"indirect call node". However it does use a "external node", which
is used when a function external to the current module is called.

The "external node" makes sense. However, I am using LLVM 2.8. (See
the output from "opt -version") and build it against Revision 105271
in the svn repository. So, can I say that the presence of "indirect
call node" is new in LLVM 2.8?

I couldn't find any code that printed "indirect call node", and I
couldn't produce it with a testcase that does an indirect call.
This is with LLVM 2.8. That's why I asked which version you are
using. At this point I think you should provide a testcase.

Ciao,

Duncan.

Hello Duncan,

>> what version of LLVM are you using? I don't think LLVM 2.7 uses a
>> "indirect call node". However it does use a "external node", which
>> is used when a function external to the current module is called.
>>
>
> The "external node" makes sense. However, I am using LLVM 2.8. (See
> the output from "opt -version") and build it against Revision 105271
> in the svn repository. So, can I say that the presence of "indirect
> call node" is new in LLVM 2.8?

I couldn't find any code that printed "indirect call node", and I
couldn't produce it with a testcase that does an indirect call.
This is with LLVM 2.8. That's why I asked which version you are
using. At this point I think you should provide a testcase.

The test code is comprised of three files: example.cpp, string.cpp and
string.h. They are attached later.

I used these commands (in chronic order):

llvm-g++ -c -emit-llvm string.cpp
llvm-g++ -c -emit-llvm example.cpp
llvm-ld string.o example.o
opt -dot-callgraph a.out.bc
open -a Graphviz callgraph.dot

Followed are the three files.
  
- example.cpp

#include "string.h"

int main()
{
  String y, z;
  String x("Hello World!");
  y = x; // strongly update y
  z = y; // use y
  return 0;
}

- string.cpp

// String.cpp

#include "String.h"

String::String() : capacity(0), length(0), buffer(0)
{
  // Nothing else to do
}

String::String(const String& that)
{
  length = that.length;
  if(that.length > capacity) {
    delete [] buffer;
    capacity = 1.5 * length;
    buffer = new char[capacity];
  }
  for(int i=0; i<length; ++i) {
    buffer[i] = that.buffer[i];
  }
}

String::String(const char str[])
{
  length = 0;
  while(str[length]!='\0') {
    ++length;
  }

  capacity = length * 1.5;
  buffer = new char[capacity];

  for(int i=0; i<length; ++i) {
    buffer[i] = str[i];
  }
}

String::~String()
{
  if(capacity) {
    delete [] buffer;
  }
}

String& String::operator=(const String& that)
{
  length = that.length;
  if(that.length > capacity) {
    delete [] buffer;
    capacity = 1.5 * length;
    buffer = new char[capacity];
  }
  for(int i=0; i<length; ++i) {
    buffer[i] = that.buffer[i];
  }
  return *this;
}

- string.h

#ifndef STRING_H
#define STRING_H

class String {
public:
  // Default constructor
  String();

  // Copy constructor
  String(const String& that);

  // One argument constructor that takes a character array as the initial
  // value for the string
  String(const char str[]);

  // Destructor
  ~String();

  // Assignment operator
  String& operator=(const String& that);
                                                                          
private:
  int length;
  int capacity;
  char* buffer;
};

#endif

Best,
Xiaolong

Hi Xiaolong, I changed the code so it now prints "external node" instead. The
external node represents all functions external to the module. So, for example,
if a function F calls a function G, but G is only declared in the module, rather
than being defined there, then the callgraph gets an edge from F to the
external node (the fact that the call was to G is discarded, only the fact that
F called something external is remembered). I hope this helps.

Best wishes,

Duncan.

Hi Xiaolong, I changed the code so it now prints "external node" instead. The
external node represents all functions external to the module. So, for example,
if a function F calls a function G, but G is only declared in the module, rather
than being defined there, then the callgraph gets an edge from F to the
external node (the fact that the call was to G is discarded, only the fact that
F called something external is remembered). I hope this helps.

Thanks, Duncan!

Best,
Xiaolong