llvm dev - Dec 2002 - [LLVMdev] Tarjan+function_ptrs == trouble ?

Test Cases:
(attached)

Iteration code:
(...) 
  typedef TarjanSCC_iterator<CallGraph*> MyTarjan;
  CallGraph& callGraph = getAnalysis<CallGraph>();
  MyTarjan iter = tarj_begin(&callGraph);
  MyTarjan end  = tarj_end(&callGraph);
  while(iter!=end)
	iter++;
(...)

if you take the time to print out the function each non-looping node iter 
traverses, it never reaches main...

Thanks,
Dave

On Fri, 6 Dec 2002, Chris Lattner wrote:
> > Recently I incorporated code into my project such that function
pointers
> > were supported, however it seems that the TarjanSCC_iterator no longer
> > works on the call graph...  main() is no longer reached while the
function
> > pointers are...  I can provide code, but I have a feeling there is a
> > simple fix... Has anyone gone through this?
> 
> I'll need some more details before I can help.  I assume this has to do
> with data structure analysis?  Can you provide a testcase?
> 
> -Chris
> 
> 
-------------- next part --------------
#include <stdlib.h>
#include <stdio.h>

//#define WORKS

int * a_global;

int a_predicate = 1; 
int another_pred =0;

int func_one()
{
    return 1;
}

int func_two()
{
    return 2;
}

int func_three()
{
    return 3;
}

int main()
{    
    int (*func_ptr)();
    
    if(a_predicate)
        func_ptr = func_one;
    else if(another_pred)
        func_ptr = func_two;
    else 
        func_ptr = func_three;

#ifdef WORKS
    return func_one();
#else
    return func_ptr();
#endif
}

> if you take the time to print out the function each non-looping node iter
> traverses, it never reaches main...
Ok, first note that the CallGraph class does really stupid (but correct)
things for function pointers, so you're not going to see anything
remarkably nice here... Make sure to read the CallGraph.h comments to
understand exactly what is going on.

Despite that, I can verify that the SCC iterator seems to not be doing the
right thing.  On the testcase (below), and with the pass below, I get the
following:

$ opt -load /localhome/lattner/llvm/lib/Debug/libtest.so -test < test.o >
/dev/null
New SCC
  Node: __main
New SCC
  Node: func_one
New SCC
  Node: func_two
New SCC
  Node: func_three

Which doesn't visit main.  Vikram, could you look into this if you get a
chance?

-Chris

------------------- Pass code ----------------------------

#include "llvm/Analysis/CallGraph.h"
#include "llvm/Function.h"
#include "llvm/Pass.h"
#include "Support/TarjanSCCIterator.h"

struct Test : public Pass {
  virtual bool run(Module &F) {
    typedef TarjanSCC_iterator<CallGraph*> MyTarjan;
    CallGraph& callGraph = getAnalysis<CallGraph>();
    for (MyTarjan I = tarj_begin(&callGraph), E = tarj_end(&callGraph);
I != E; ++I) {
      SCC<CallGraph*> *S = *I;
      assert(S);
      std::cerr << "New SCC\n";
      for (unsigned i = 0, e = S->size(); i != e; ++i)
        if (Function *F = (*S)[i]->getFunction())
          std::cerr << "  Node: " << F->getName()
<< "\n";
        else
          std::cerr << "  Indirect node\n";
    }
    return false;
  }
  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
    AU.setPreservesAll();
    AU.addRequired<CallGraph>();
  };
};
RegisterOpt<Test> Z("test", "test");


-------------------- Testcase ------------------------

#include <stdlib.h>
#include <stdio.h>

//#define WORKS

int * a_global;

int a_predicate = 1;
int another_pred =0;

int func_one()
{
    return 1;
}

int func_two()
{
    return 2;
}

int func_three()
{
    return 3;
}

int main()
{
    int (*func_ptr)();

    if(a_predicate)
        func_ptr = func_one;
    else if(another_pred)
        func_ptr = func_two;
    else
        func_ptr = func_three;

#ifdef WORKS
    return func_one();
#else
    return func_ptr();
#endif
}

Thanks,

I've been through the documentation, and if I visit main, i think 
everything will turn out correctly...  Printing out the Call graph reveals 
that main is calling this external node i think you are making reference 
to.  Could this be the problem?

Dave

 On Fri, 6 Dec 2002, Chris Lattner wrote:
> > if you take the time to print out the function each non-looping node
iter
> > traverses, it never reaches main...
> 
> Ok, first note that the CallGraph class does really stupid (but correct)
> things for function pointers, so you're not going to see anything
> remarkably nice here... Make sure to read the CallGraph.h comments to
> understand exactly what is going on.
> 
> Despite that, I can verify that the SCC iterator seems to not be doing the
> right thing.  On the testcase (below), and with the pass below, I get the
> following:
> 
> $ opt -load /localhome/lattner/llvm/lib/Debug/libtest.so -test < test.o
> /dev/null
> New SCC
>   Node: __main
> New SCC
>   Node: func_one
> New SCC
>   Node: func_two
> New SCC
>   Node: func_three
> 
> Which doesn't visit main.  Vikram, could you look into this if you get
a
> chance?
> 
> -Chris
> 
> ------------------- Pass code ----------------------------
> 
> #include "llvm/Analysis/CallGraph.h"
> #include "llvm/Function.h"
> #include "llvm/Pass.h"
> #include "Support/TarjanSCCIterator.h"
> 
> struct Test : public Pass {
>   virtual bool run(Module &F) {
>     typedef TarjanSCC_iterator<CallGraph*> MyTarjan;
>     CallGraph& callGraph = getAnalysis<CallGraph>();
>     for (MyTarjan I = tarj_begin(&callGraph), E =
tarj_end(&callGraph); I != E; ++I) {
>       SCC<CallGraph*> *S = *I;
>       assert(S);
>       std::cerr << "New SCC\n";
>       for (unsigned i = 0, e = S->size(); i != e; ++i)
>         if (Function *F = (*S)[i]->getFunction())
>           std::cerr << "  Node: " << F->getName()
<< "\n";
>         else
>           std::cerr << "  Indirect node\n";
>     }
>     return false;
>   }
>   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
>     AU.setPreservesAll();
>     AU.addRequired<CallGraph>();
>   };
> };
> RegisterOpt<Test> Z("test", "test");
> 
> 
> -------------------- Testcase ------------------------
> 
> #include <stdlib.h>
> #include <stdio.h>
> 
> //#define WORKS
> 
> int * a_global;
> 
> int a_predicate = 1;
> int another_pred =0;
> 
> int func_one()
> {
>     return 1;
> }
> 
> int func_two()
> {
>     return 2;
> }
> 
> int func_three()
> {
>     return 3;
> }
> 
> int main()
> {
>     int (*func_ptr)();
> 
>     if(a_predicate)
>         func_ptr = func_one;
>     else if(another_pred)
>         func_ptr = func_two;
>     else
>         func_ptr = func_three;
> 
> #ifdef WORKS
>     return func_one();
> #else
>     return func_ptr();
> #endif
> }
> 
>

The tarj_end() function had never been tested and one of the methods 
it used was broken.  This has now been fixed:
    
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20021202/001852.html

Note that there is already a pass that prints out the SCCs of the
CallGraph, and another one that prints SCCs of each CFG.
You can run them as
	analyze -callscc
	analyze -cfgscc
The passes are in llvm/lib/Analysis/PrintSCC.cpp.

--Vikram
http://www.cs.uiuc.edu/~vadve

> From: Chris Lattner <sabre at nondot.org>
> Subject: [LLVMbugs] Re: [LLVMdev] Tarjan+function_ptrs == trouble ?
> Sender: llvmbugs-admin at cs.uiuc.edu
> Date: Fri, 6 Dec 2002 01:00:07 -0600 (CST)
> 
> > if you take the time to print out the function each non-looping node
iter
> > traverses, it never reaches main...
> 
> Ok, first note that the CallGraph class does really stupid (but correct)
> things for function pointers, so you're not going to see anything
> remarkably nice here... Make sure to read the CallGraph.h comments to
> understand exactly what is going on.
> 
> Despite that, I can verify that the SCC iterator seems to not be doing the
> right thing.  On the testcase (below), and with the pass below, I get the
> following:
> 
> $ opt -load /localhome/lattner/llvm/lib/Debug/libtest.so -test < test.o
> /dev/null
> New SCC
>   Node: __main
> New SCC
>   Node: func_one
> New SCC
>   Node: func_two
> New SCC
>   Node: func_three
> 
> Which doesn't visit main.  Vikram, could you look into this if you get
a
> chance?
> 
> -Chris
> 
> ------------------- Pass code ----------------------------
> 
> #include "llvm/Analysis/CallGraph.h"
> #include "llvm/Function.h"
> #include "llvm/Pass.h"
> #include "Support/TarjanSCCIterator.h"
> 
> struct Test : public Pass {
>   virtual bool run(Module &F) {
>     typedef TarjanSCC_iterator<CallGraph*> MyTarjan;
>     CallGraph& callGraph = getAnalysis<CallGraph>();
>     for (MyTarjan I = tarj_begin(&callGraph), E =
tarj_end(&callGraph); I != E; ++I) {
>       SCC<CallGraph*> *S = *I;
>       assert(S);
>       std::cerr << "New SCC\n";
>       for (unsigned i = 0, e = S->size(); i != e; ++i)
>         if (Function *F = (*S)[i]->getFunction())
>           std::cerr << "  Node: " << F->getName()
<< "\n";
>         else
>           std::cerr << "  Indirect node\n";
>     }
>     return false;
>   }
>   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
>     AU.setPreservesAll();
>     AU.addRequired<CallGraph>();
>   };
> };
> RegisterOpt<Test> Z("test", "test");
> 
> 
> -------------------- Testcase ------------------------
> 
> #include <stdlib.h>
> #include <stdio.h>
> 
> //#define WORKS
> 
> int * a_global;
> 
> int a_predicate = 1;
> int another_pred =0;
> 
> int func_one()
> {
>     return 1;
> }
> 
> int func_two()
> {
>     return 2;
> }
> 
> int func_three()
> {
>     return 3;
> }
> 
> int main()
> {
>     int (*func_ptr)();
> 
>     if(a_predicate)
>         func_ptr = func_one;
>     else if(another_pred)
>         func_ptr = func_two;
>     else
>         func_ptr = func_three;
> 
> #ifdef WORKS
>     return func_one();
> #else
>     return func_ptr();
> #endif
> }
> 
> 
> _______________________________________________
> LLVMbugs mailing list
> LLVMbugs at cs.uiuc.edu
> http://mail.cs.uiuc.edu/mailman/listinfo/llvmbugs
>