SLO Documentation

SLO code overview

  • High level explaination of techniques- http://escher.elis.ugent.be/publ/Edocs/DOC/P106_138.pdf
  • All the code can be svn from source forge
  • This code includes four directories within the svn trunk:
    • documentation - eighty percent pictures, there is helpful information on how to get the code running, but nothing about the code structure
    • gcc-slo - this is the modified gcc (version 4.1.1) that runs the analysis
    • slo - includes some code from Beyls' earlier tool RDVIS (http://trappist.elis.ugent.be/~kbeyls/rdvis/ ) and SLO. This directory handles the Java back end which displays results.
    • testsuite - python scripts to test the validity of the gcc-slo and SLO code

gcc-slo

  • gcc-slo is split up in to two main pieces. The first is a modification of the gcc 4.1.1 source code. The second is an added external library entitled librd. The library analyzes the information sent to it by gcc-slo.
  • Documentation on how to use the SLO tool can be found here. Little is included about the structure of the actual code.
  • The always useful build script can also be found here.

gcc-slo-src/gcc

  • Most of the interesting code from this project is found within this gcc-slo-src directory.
  • The gcc structure is somewhat stripped. For example, there is no ADA support, etc.
  • Slo gcc was built on top of rdvis gcc (another tool developed by Beyls, "Reuse Distance Visualizer").
  • The directory "gcc" has the changes to the original gcc code which use the librd library.
  • The makefiles and several of the scripts have been modified to account for the librd library. Many of the other files have not been changed from the original gcc 4.1.1.

  • GCC-SLO basically instruments three things:
    • Code that generates memory accesses
    • Basic block transitions
    • Function entries and exits
  • The gcc code is not too heavily modified, but there are some important additions.
    • Two passes are added to gcc. pass_instrument_memaccess instruments the memory accesses in the code and pass_instrument_basicblock instruments the control flow.
      • Regarding the first pass, the function that instruments the memory accesses in a single function is instrument_memaccess. It calls walk_statements_to_instruments, which iterates over all statements in the function. For each expression encountered in a statement, it calls instrument_node_memaccess, which will finally instrument the code when the current expression results in a memory access. When such an expression is found, build_instrument_memaccess_for creates the instrumentation code that must be inserted. At this moment, the instrumentation code isn't inserted into the abstract syntax tree yet. Instead the instrumentation code is remembered in a separate hash table. Later on, during the instrumentation of the basic blocks, the instrumentation code for the memory accesses will be inserted. This is needed because memory instrumentation and basic block instrumentation influence each other.
      • The second pass is mainly handled by tree-mudflap.c. This is explained better at SloMudFlap.
    • A structure has been added to basic blocks that tracks source code locations. This allows the program to trace where memory accesses originate from.
    • tree-mudflap.c is the most heavily modified file. It modifies the gimple tree to call external methods in librd after basic blocks are executed. It is further documented HERE .
    • Pseudo basic blocks have been introduced. These are basic blocks that are additionally bordered/limited by function calls. These are created to allow the program to know exactly how many and which memory accesses will occur.

gcc-slo-src/librd

  • The directory "librd" has most of the real analysis code. File names should be helpful. More about this directory will be added later.
    • rd = reuse distance
    • nosl = no sampling
    • bb = basic blocks
    • log2 =the position of the highest bit being set, which is close to log based 2
    • nr = number
    • sri = single reuse information
    • RDTSC = reuse distance time stamp ?collection?
    • NASLT = number of accesses since last traced
    • PBI = pseudo block iterator
    • BSI = Block statement iterator
  • measure_log2_rd.c - General Util file ( initialize hash map, alloc table, alloc node, find node, add node, etc )
  • basic_block_histograms.cpp - Stores most information on basic blocks, spits out histograms information.
  • call_stack.cpp - function utilities, stack analyzer, keeper of the modified tree.
  • sampled_reuses.cpp - implements Vitters' reservoir sampling ( "Reservoir-Sampling Algorithms of Time Complexity O(n(1+log(N/n)))", By Kim-Hung Li )

slo

  • This directory contains the Java back end to display the results files from SLO.
  • Some of the result file syntax can be found is the listed documentation.

-- A significant amount of the above information is taken from Beyls.

-- IanChristopher - 29 May 2008


This topic: Main > TWikiUsers > IanChristopher > SloR > SLODoc
Topic revision: r7 - 2008-06-06 - IanChristopher
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback