Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Log of /MLRISC/trunk/block-placement
ViewVC logotype

Log of /MLRISC/trunk/block-placement

View Directory Listing Directory Listing


Sticky Revision:

Revision 2126 - Directory Listing
Modified Thu Nov 2 16:11:29 2006 UTC (12 years, 8 months ago) by blume
moved MLRISC to toplevel

Revision 1334 - Directory Listing
Modified Thu May 22 22:46:30 2003 UTC (16 years, 2 months ago) by mblume
Original Path: sml/trunk/src/MLRISC/block-placement
major cleanup: eliminate all non-exhaustive pattern matches

Revision 1182 - Directory Listing
Modified Thu Mar 28 16:41:29 2002 UTC (17 years, 3 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Switch to CFG.exitId.

Revision 1177 - Directory Listing
Modified Mon Mar 25 16:49:18 2002 UTC (17 years, 3 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Minor fixes to get the block list in a consistent form.

Revision 1176 - Directory Listing
Modified Mon Mar 25 16:07:39 2002 UTC (17 years, 3 months ago) by george
Original Path: sml/trunk/src/MLRISC/block-placement
  inserted block with a single jump instruction to break multiple fallthroughs

Revision 1169 - Directory Listing
Modified Fri Mar 22 19:22:15 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Fix to handle fallsthru edges to block 0.

Revision 1168 - Directory Listing
Modified Fri Mar 22 19:19:32 2002 UTC (17 years, 4 months ago) by george
Original Path: sml/trunk/src/MLRISC/block-placement
Implemented the Ball-Larus branch prediction-heuristic, and
incorporated graphical viewers for control flow graphs.

Ball-Larus Heuristic:
---------------------
See the file compiler/CodeGen/cpscompile/cpsBranchProb.sml.

By design it uses the Dempster-Shafer theory for combining
probabilities.  For example, in the function:

    fun f(n,acc) = if n = 0 then acc else f(n-1, n*acc)

the ball-larus heuristics predicts that the n=0 is unlikely
(OH-heuristic), and the 'then' branch is unlikely because of the
RH-heuristic -- giving the 'then' branch an even lower combined
probability using the Dempster-Shater theory.

Finally, John Reppy's loop analysis in MLRISC, further lowers the
probability of the 'then' branch because of the loop in the else
branch.


Graphical Viewing:
------------------
I merely plugged in Allen's graphical viewers into the compiler. The
additional code is not much. At the top level, saying:

	Control.MLRISC.getFlag "cfg-graphical-view" := true;

will display the graphical view of the control flow graph just before
back-patching.  daVinci must be in your path for this to work. If
daVinci is not available, then the default viewer can be changed
using:

	Control.MLRISC.getString "viewer"

which can be set to "dot" or "vcg" for the corresponding viewers. Of
course, these viewers must be in your path.

The above will display the compilation unit at the level of clusters,
many of which are small, boring, and un-interesting. Also setting:

	Control.MLRISC.getInt "cfg-graphical-view_size"

will display clusters that are larger than the value set by the above.

Revision 1166 - Directory Listing
Modified Fri Mar 22 16:59:28 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Check EXIT edges too.

Revision 1165 - Directory Listing
Modified Fri Mar 22 16:31:37 2002 UTC (17 years, 4 months ago) by george
Original Path: sml/trunk/src/MLRISC/block-placement
 treat entry and exit nodes specially

Revision 1164 - Directory Listing
Modified Fri Mar 22 15:32:57 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Use CFG.entry and CFG.exit functions.

Revision 1163 - Directory Listing
Modified Fri Mar 22 15:32:30 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Added code to check JUMP and BRANCH true edges.

Revision 1162 - Directory Listing
Modified Fri Mar 22 15:16:46 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Added methods to get unique entry and exit blocks.

Revision 1160 - Directory Listing
Modified Fri Mar 22 14:24:36 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  New file -- debugging code to check correctness of block placements.

Revision 1157 - Directory Listing
Modified Thu Mar 21 22:33:35 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  New default block placement that respects edge kinds.

Revision 1156 - Directory Listing
Modified Thu Mar 21 22:01:11 2002 UTC (17 years, 4 months ago) by leunga
Original Path: sml/trunk/src/MLRISC/block-placement

     Bug fixes and improvements to x86 and cfg

Revision 1151 - Directory Listing
Modified Mon Mar 18 18:41:31 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Fixed flag names for dumping CFG.

Revision 1139 - Directory Listing
Modified Wed Mar 13 18:40:51 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Added flags to functor parameters to control hte behavior of the
  algorithm.  The reverseDirection flag is currently a nop.

Revision 1135 - Directory Listing
Modified Tue Mar 12 16:09:26 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Added functor to compute block and edge frequencies from edge
  probabilities.

Revision 1134 - Directory Listing
Modified Tue Mar 12 03:59:21 2002 UTC (17 years, 4 months ago) by george
Original Path: sml/trunk/src/MLRISC/block-placement
  pick between default and weighted block placement

Revision 1133 - Directory Listing
Modified Tue Mar 12 03:56:23 2002 UTC (17 years, 4 months ago) by george
Original Path: sml/trunk/src/MLRISC/block-placement
Tested the jump chain elimination on all architectures (except the
hppa).  This is on by default right now and is profitable for the
alpha and x86, however, it may not be profitable for the sparc and ppc
when compiling the compiler.

The gc test will typically jump to a label at the end of the cluster,
where there is another jump to an external cluster containing the actual
code to invoke gc. This is to allow factoring of common gc invocation
sequences. That is to say, we generate:

	f:
	   testgc
	   ja	L1	% jump if above to L1

	L1:
	   jmp L2


After jump chain elimination the 'ja L1' instructions is converted to
'ja L2'. On the sparc and ppc, many of the 'ja L2' instructions may end
up being implemented in their long form (if L2 is far away) using:

	jbe	L3	% jump if below or equal to L3
        jmp 	L2
     L3:
	...


For large compilation units L2  may be far away.

Revision 1129 - Directory Listing
Modified Sat Mar 9 03:21:44 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Fixed jump chaining bug.  Indentation fixes.

Revision 1126 - Directory Listing
Modified Thu Mar 7 21:16:28 2002 UTC (17 years, 4 months ago) by blume
Original Path: sml/trunk/src/MLRISC/block-placement
implemented generic Controls module and used it for
all compiler flags/tuneable knobs/...;
more command-line options accepted (for setting the above controls);
some minor bug fixes

Revision 1125 - Directory Listing
Modified Thu Mar 7 21:04:13 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Changed representation of probabilities and frequencies.

Revision 1120 - Directory Listing
Modified Wed Mar 6 17:16:36 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Simplified the fcond type in ml-tree-basis.  Put in a temporary
  fix for a type error in weighted-block-placement-fn.sml.

Revision 1113 - Directory Listing
Modified Fri Mar 1 16:57:47 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Dump CFG in block placement order.

Revision 1112 - Directory Listing
Modified Fri Mar 1 15:53:14 2002 UTC (17 years, 4 months ago) by george
Original Path: sml/trunk/src/MLRISC/block-placement
bug fixes

Revision 1111 - Directory Listing
Modified Fri Mar 1 14:57:13 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Removed use of polymorphic equality.

Revision 1106 - Directory Listing
Modified Thu Feb 28 19:58:04 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Fixed bugs and added control flags.

Revision 1105 - Directory Listing
Modified Thu Feb 28 19:57:47 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Added control flags.

Revision 1090 - Directory Listing
Modified Fri Feb 22 23:08:46 2002 UTC (17 years, 4 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  Added jump-chain elimination and fixed type errors in block placement.

Revision 1083 - Directory Listing
Modified Thu Feb 21 18:52:10 2002 UTC (17 years, 5 months ago) by jhr
Original Path: sml/trunk/src/MLRISC/block-placement
  New file: implementation of Pettis-Hansen block placement.

Revision 906 - Directory Listing
Added Fri Aug 24 17:36:40 2001 UTC (17 years, 10 months ago) by george
Original Path: sml/trunk/src/MLRISC/block-placement
Initial revision

Sort log by:

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0