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 <xm...@cs.wisc.edu> 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 <w...@krellinst.org> 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 <xm...@cs.wisc.edu> 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 <j...@krellinst.org> 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 <j...@krellinst.org> 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@cs.wisc.edu
>> https://lists.cs.wisc.edu/mailman/listinfo/dyninst-api
>>
>>
>>
>>
_______________________________________________
Dyninst-api mailing list
Dyninst-api@cs.wisc.edu
https://lists.cs.wisc.edu/mailman/listinfo/dyninst-api
