petit/Lang-Interf3.0

   1 This document describes the major changes to the interface provided for
   2 compilers to make use of our routines for dependence testing with the
   3 omega test.  The interface itself is described in lang-interf.generic,
   4 and it is used to interface our routines to extended petit, via the
   5 files lang-interf.h and lang-interf.c.  These may serve as useful
   6 examples to anyone trying to figure out the interface.
   7
   8 The basic point of this software, and some of the terms used here, are
   9 described in the paper "Eliminating False Data Dependences using the
  10 Omega Test", by William Pugh & David Wonnacott.  This is available via
  11 ftp, or as Tech. Report CS-TR-2993, from the Dept. of Computer Science,
  12 Univ. of Maryland, and an earlier version appeared at the ACM SIGPLAN
  13 PLDI'92 conference.
  14
  15
  16 Major changes to lang-interf for release 3.0:
  17
  18 The flag "Flows_Covered" has been replaced by a value associated with
  19 each array access showing the level at which it is "covered" and
  20 "terminated".
  21
  22 Reduction dependences are computed between update accesses.  Thus there
  23 is a new type of dependence, and the interface requires new tests to
  24 determine whether we are working with an update access.
  25
  26 Variables may be private to a loop - we must be able to tell if a
  27 variable is private, and if so determine the level of the loop for
  28 which it is private.
  29
  30 Dependences may be computed from the Entry point and to the Exit from
  31 the routine being analyzed.  If this is done, we must be able to
  32 distinguish the accesses representing these nodes by comparing them to
  33 the values "Entry" and "ExitNode".
  34
  35 More information is needed about ifs, including the number of loops
  36 containing them.
  37
  38 The dir_and_dist_info structure has been revised so that it no longer
  39 contains a pointer to dependence distance information.  Distance
  40 information is now stored directly in the dir_and_dist_info.
  41
  42 To ensure that the dependence killing function works, all
  43 "memory-based" output dependences must be in the dependence graph. To
  44 ensure that this is the case, our system sometimes needs to duplicate a
  45 node in the dependence graph.  To do this, it calls a function
  46 clone_dd_graph_node_for_refinement, providing the an argument that is
  47 selected from the dd_graph_node_to_be_cloned member of the
  48 dir_and_dist_info structure.  You must initialize this field and
  49 provide the function.
  50
  51 You also need to provide interface functions dir_and_dist_into_ddnode
  52 and ddnode_to_dir_and_dist, to convert dd graph nodes into
  53 dir_and_dist_info structures.
  54
  55 The function try_to_eliminate computes assertions that can be used to
  56 eliminate dependences.  It relies on the function add_GEQ_assertion to
  57 put these assertions into the program.
  58
  59 Currently, many of the functions require string arguments that are used
  60 for generating debugging output.  These may go away in the future, with
  61 functions depending instead on interface functions to generate
  62 printable representations of dependences or expressions.