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

SCM Repository

[smlnj] Diff of /sml/branches/primop-branch-3/NOTES/HISTORY
ViewVC logotype

Diff of /sml/branches/primop-branch-3/NOTES/HISTORY

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1179, Tue Mar 26 03:04:46 2002 UTC revision 1180, Tue Mar 26 22:24:24 2002 UTC
# Line 14  Line 14 
14    
15  ----------------------------------------------------------------------  ----------------------------------------------------------------------
16  Name: Matthias Blume  Name: Matthias Blume
17    Date: 2002/03/25 17:25:00 EST
18    Tag: blume-20020325-divmod
19    Description:
20    
21    I improved (hopefully without breaking them) the implementation of Int.div,
22    Int.mod, and Int.rem.   For this, the code in translate.sml now takes
23    advantage of the following observations:
24    
25      Let  q = x quot y      r = x rem y
26           d = x div  y      m = x mod y
27    
28    where "quot" is the round-to-zero version of integer division that
29    hardware usually provides.  Then we have:
30    
31         r = x - q * y        where neither the * nor the - will overflow
32         d = if q >= 0 orelse x = q * y then q else q - 1
33                              where neither the * nor the - will overflow
34         m = if q >= 0 orelse r = 0 then r else r + y
35                              where the + will not overflow
36    
37    This results in substantial simplification of the generated code.
38    The following table shows the number of CFG nodes and edges generated
39    for
40            fun f (x, y) = x OPER y
41            (* with OPER \in div, mod, quot, rem *)
42    
43    
44        OPER | nodes(old) | edges(old) | nodes(new) | edges(new)
45        --------------------------------------------------------
46         div |         24 |         39 |         12 |         16
47         mod |         41 |         71 |         12 |         16
48        quot |          8 |         10 |          8 |         10
49         rem |         10 |         14 |          8 |         10
50    
51    
52    ----------------------------------------------------------------------
53    Name: Matthias Blume
54  Date: 2002/03/25 22:06:00 EST  Date: 2002/03/25 22:06:00 EST
55  Tag: blume-20020325-cprotobug  Tag: blume-20020325-cprotobug
56  Description:  Description:

Legend:
Removed from v.1179  
changed lines
  Added in v.1180

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