Re: [DynInst_API:] getLoopHead interface in BPatch_basicBlockLoop class

[William Hachfeld <wdh@xxxxxxxxxxxxx>]

Hi Xiaozhu & Jim,

What we are looking for here doesnât really have a specific theoretical meaning. But think of it from a user interface perspective. If you were a user sitting in front a performance tool that showed you a list of the top 10 loops taking the largest amount of time, how would you want it to identify those loops in a âshortâ manner? And if you double-clicked on a particular loop in the list, and the tool popped up a source code editor, where would you want it to focus?

For, say:

205: for (int i = 0; i < 100; ++i)

206: {

207: std::cout << i << std::endl;

208: }

the answer is probably line #205. For:

305: int i = 0;

306: do

307: {

308: std::cout << i << std::endl;

309: ++i;

310: } while (i < 100);

I suppose I would say line #306. Although line #310 could be a reasonable answer too. But I donât know that it needs to be the last source statement of the loop.

â Bill

On Jul 31, 2015, at 2:30 PM, Xiaozhu Meng <xmeng@xxxxxxxxxxx> wrote:

Hi Bill,

I am not clear about the concept of the "defining statement of the
loop". If the "defining statement of the loop" refers to the statement
in the loop that has the minimum source line number, then I think your
alternative way can work. But if the "defining statement of the loop"
refers to the statement that contains the loop condition, then your
alternative way would not work because the loop condition can be last
source statement of the loop. Could you provide more details on what
you mean by the defining statement of the loop?

Thanks

--Xiaozhu

On Thu, Jul 30, 2015 at 9:28 PM, William Hachfeld <wdh@xxxxxxxxxxxxx> wrote:

Hi Jim,

To get a better understanding of what Xiaozhu is writing about, take a look
at the diagrams on the right side of:

https://en.wikipedia.org/wiki/Control_flow_graph

Figure (d) shows an irreducible CFG. In particular, Xiaozhu is indicating
that the new API is designed to allow for the representation of the two
middle nodes in (d). These two nodes represent a loop which has 2 different
entry points. I.e. multiple âheadâ.

Unfortunately because the old Dyninst API didnât handle this case, the
Open|SpeedShop database schema I designed doesnât either. :-( It also
doesnât necessarily matter. The only place that the âaddr_headâ value is
used is in order to identify which source statement is the âdefinitionâ of
the loop.

Is there some, alternate, way of identifying which basic block is contained
within the defining statement of the loop, Xiaozhu? I donât have the Dyninst
9 API available to me right nowâ Otherwise we need some alternate mechanism
of picking the âheadâ address, Jim.

One possibility - just off the cuff mind you - might be to call
getLoopEntries() to get the basic block of each entry. Then, for each of
these, take the first address of that basic block and query the source
file/line containing that address. Assuming that all line numbers are within
a single source file, the minimum line number is probably reasonably the
loop definition. And the first address in that basic block would be the one
to use for âaddr_headâ in the Open|SS database.

â Bill



On Jul 28, 2015, at 11:08 AM, Xiaozhu Meng <xmeng@xxxxxxxxxxx> wrote:

It is more complicated than that. For a natural loop, it only has one
entry, which is also called the head because the entry dominates all
blocks of the loop. However, for an irreducible loop, it can have
multiple entries and it is possible that none of the entries dominates
the other blocks in the loop.

Thanks

--Xiaozhu

On Tue, Jul 28, 2015 at 10:58 AM, Jim Galarowicz <jeg@xxxxxxxxxxxxx> wrote:

Hi Xiaozhu,

Is the first entry in the vector e the loop head?


              BPatch_Vector<BPatch_basicBlock*> entries;
              loop->getLoopEntries(entries);
              BPatch_basicBlock* head  entries[0];

              if (head == NULL)
              {
                  continue;
              }

              LoopInfo info(Address(head->getStartAddress()) -
module_base);

              BPatch_Vector<BPatch_basicBlock*> blocks;
              loop->getLoopBasicBlocks(blocks);

              for (unsigned int i  0; i < blocks.size(); ++i)
              {
                  BPatch_basicBlock* block  blocks[i];


Or is it more complicated than that?

Thanks,
Jim G


Thanks,
Jim G
On 07/28/2015 10:37 AM, Xiaozhu Meng wrote:


Hi Jim,

The old getLoopHead() method has been replaced by the following new
interface to appropriately represent irreducible loops:

int
BPatch_basicBlockLoop::getLoopEntries(BPatch_Vector<BPatch_basicBlock*> &e);

The new interface returns the number of entry blocks of this loop and
the entries blocks are returned as the output parameter.

On Tue, Jul 28, 2015 at 8:42 AM, Jim Galarowicz <jeg@xxxxxxxxxxxxx> wrote:


Hi all,

I've downloaded the git source version of dyninst and built it on NASA's
pfe
machine and my laptop in an attempt to run it on Intel MIC binaries.  The
8.2.1 asserts in switches related to the architecture type.

However, I ran into a compile error with our loop code:

[ 16%] Building CXX object

libopenss-framework/CMakeFiles/openss-framework-symtabapi.dir/DyninstSymbols.cxx.o
cd /u/jgalarow/OpenSpeedShop/build_mic_offline_fe/libopenss-framework &&
/nasa/pkgsrc/2014Q3/gcc49/bin/g++   -DHAVE_DYNINST -DHAVE_STDINT_H=1
-DHAVE_SYS_STAT_H=1 -DOPENSS_USE_SYMTABAPI=1

-DOpenSpeedShop_LIBRARY_FILE_DIR=\"/nobackupp8/jgalarow/maia/pfe_ossoffline/lib64\"
-DPACKAGE=1 -DPACKAGE_VERSION=1 -DVERSION=\"2.1\" -D_GNU_SOURCE
-Dopenss_framework_symtabapi_EXPORTS -g -fPIC
-I/u/jgalarow/OpenSpeedShop/libopenss-framework
-I/u/jgalarow/OpenSpeedShop/build_mic_offline_fe/libopenss-framework

-I/u/jgalarow/OpenSpeedShop/build_mic_offline_fe/libopenss-framework/offline
-I/nasa/boost/1.50.0/include
-I/nobackup/jgalarow/dyninst-9.0.0/include/dyninst
-I/nobackup/jgalarow/dyninst-9.0.0/include
-I/u/jgalarow/krellroot_v2.1u8/include

-I/u/jgalarow/OpenSpeedShop/build_mic_offline_fe/libopenss-framework/../libopenss-framework
-o CMakeFiles/openss-framework-symtabapi.dir/DyninstSymbols.cxx.o -c
/u/jgalarow/OpenSpeedShop/libopenss-framework/DyninstSymbols.cxx
/u/jgalarow/OpenSpeedShop/libopenss-framework/DyninstSymbols.cxx: In
function 'std::vector<LoopInfo> getLoopsAt(const
OpenSpeedShop::Framework::Address&, BPatch_image&)':
/u/jgalarow/OpenSpeedShop/libopenss-framework/DyninstSymbols.cxx:140:49:
error: 'class BPatch_basicBlockLoop' has no member named 'getLoopHead'
                BPatch_basicBlock* head  loop->getLoopHead();
                                                ^
make[2]: ***

[libopenss-framework/CMakeFiles/openss-framework-symtabapi.dir/DyninstSymbols.cxx.o]
Error 1
make[2]: Leaving directory
`/home4/jgalarow/OpenSpeedShop/build_mic_offline_fe'
make[1]: ***
[libopenss-framework/CMakeFiles/openss-framework-symtabapi.dir/all] Error
2
make[1]: Leaving directory
`/home4/jgalarow/OpenSpeedShop/build_mic_offline_fe'

I found this in my emails about dyninst:

Hi,

We are planing to improve our current loop detection algorithm to be able
to
handle irreducible loops. Such loops can have multiple entry blocks. For
this matter, the original interface to get the loop head needs to be
changed
to return a vector of heads of a loop.

The involved interface is:

BPatch_basicBlock*  BPatch_basicBlockLoop::getLoopHead();

We plan to change it to:

bool BPatch_basicBlockLoop::getLoopHead(std::vector<BPatch_basicBlock*>&
entries);

Let us know if you are using the interface and if the interface change
will
cause significant inconvenience to you.

Thanks

--Xiaozhu


However, I can't find any examples of the new getLoopHead code in the
latest
Dyninst source.   Can someone point me to it?


pfe21-101>pwd
/nobackupp8/jgalarow/OpenSpeedShop_ROOT/BUILD/pfe20/dyninst-9.0.0

pfe21-94>grep basicBlockLoop::getLoopHead *
pfe21-95>!!/*
grep basicBlockLoop::getLoopHead */*
pfe21-96>!!/*
grep basicBlockLoop::getLoopHead */*/*
pfe21-97>!!/*
grep basicBlockLoop::getLoopHead */*/*/*
pfe21-98>!!/*
grep basicBlockLoop::getLoopHead */*/*/*/*
pfe21-99>!!/*
grep basicBlockLoop::getLoopHead */*/*/*/*/*
pfe21-100>!!/*
grep basicBlockLoop::getLoopHead */*/*/*/*/*/*
pfe21-101>pwd
/nobackupp8/jgalarow/OpenSpeedShop_ROOT/BUILD/pfe20/dyninst-9.0.0

pfe21-104>grep getLoopHead *
pfe21-105>!!/*
grep getLoopHead */*
pfe21-106>!!/*
grep getLoopHead */*/*
!!/*

LOOKS LIKE THE OLD INTERFACE:

dyninstAPI/src/hybridOverwrites.C://
(*lIter)->getLoopHead()->getStartAddress(),
dyninstAPI/src/hybridOverwrites.C://
writeLoop->getLoopHead()->getStartAddress(),
pfe21-107>!!/*
grep getLoopHead */*/*/*
pfe21-108>!!/*
grep getLoopHead */*/*/*/*
pfe21-109>!!/*
grep getLoopHead */*/*/*/*/*
pfe21-110>


I need to change this to work with the new API:
cat -n /u/jgalarow/OpenSpeedShop/libopenss-framework/DyninstSymbols.cxx
...
...

 122                BPatch_Vector<BPatch_basicBlockLoop*> loops;
  123                cfg->getLoops(loops);
  124
  125                for (unsigned int l  0; l < loops.size(); ++l)
  126                {
  127                    BPatch_basicBlockLoop* loop  loops[l];
  128
  129                    if ((loop == NULL) ||
!loop->containsAddressInclusive(
  130                            (module_base + address).getValue()
  131                            ))
  132                    {
  133                        continue;
  134                    }
  135
  136                    // A loop containing this address has been
found!
Rejoice!
  137                    // And, of course, obtain the loop's head
address
and basic
  138                    // block address ranges...
  139
  140                    BPatch_basicBlock* head  loop->getLoopHead();
  141
  142                    if (head == NULL)
  143                    {
  144                        continue;
  145                    }
  146
  147                    LoopInfo info(Address(head->getStartAddress())
-
module_base);
  148
  149                    BPatch_Vector<BPatch_basicBlock*> blocks;
  150                    loop->getLoopBasicBlocks(blocks);
  151
  152                    for (unsigned int i  0; i < blocks.size();
++i)
  153                    {
...
...


Thanks,
Jim G


On 09/23/2014 04:57 PM, Xiaozhu Meng wrote:

Hi,

We are planing to improve our current loop detection algorithm to be able
to
handle irreducible loops. Such loops can have multiple entry blocks. For
this matter, the original interface to get the loop head needs to be
changed
to return a vector of heads of a loop.

The involved interface is:

BPatch_basicBlock*  BPatch_basicBlockLoop::getLoopHead();

We plan to change it to:

bool BPatch_basicBlockLoop::getLoopHead(std::vector<BPatch_basicBlock*>&
entries);

Let us know if you are using the interface and if the interface change
will
cause significant inconvenience to you.

Thanks

--Xiaozhu


_______________________________________________
Dyninst-api mailing list
Dyninst-api@xxxxxxxxxxx
https://lists.cs.wisc.edu/mailman/listinfo/dyninst-api