Thank you Edward. I am aware of these requirements - my problem is writing the code in which these will always hold (I'm optimizing Cmm and hand-written Cmm files tend to cause many problems that don't appear in automatically generated Cmm). Having a debugging tool in form of Fuel would be helpful for me, because instead of getting a freeze and seeing no output from -ddump-cmm I would see incorrectly transformed Cmm that would allow me to track bugs more easily.

In that case, I would recommend taking a look at when -dopt-fuel got removed and seeing if you can put it back in. I quite liked this feature and it is too bad it is gone.

...

• The transfer function must be monotonic: given a more infor- mative fact in, it must produce a more informative fact out.

I spent some considerable time thinking about this. Consider a simple example of copy propagation. Let's assume that { x = NAC }, i.e. we know that x has been defined earlier but is Not-A-Constant and so we cannot rewrite it. Now we have something llike this:

x := 3; y := x;

Here we are allowed to rewrite y := x with y := 3, because after first statement we learn that { x = 3 }. Now consider this:

x := 3; x := very_unsafe_stg_call(); y := x;

Here, after the first statement we learn that { x = 3 }, but after the second one we learn once again that x is NAC and so we are not allowed to rewrite statement y := x. So the value of x can change from NAC to a constant and from constant to a NAC. Is such a transfer function monotonic?

This is a point of confusion; I got confused about this when I was working on Hoopl. What is meant by a transfer function over instruction i is monotonic is: if x <= y then f_i(x) <= f_i(y) It says nothing about the "change" in x as you move along the statements. Thus, for your example, very_unsafe_stg_call always puts x to be NAC; this is trivially monotonic since NAC <= NAC. Edward

It's easy to get confused, but in fact the bedrock issues are quite simple. As Edward says, a function f is monotonic iff x <= y implies f(x) <= f(y) Monotonicity does NOT mean that x <= f(x)!!! The transfer function, and the 'join' function, must all be monotonic. It's that simple. ======= I would *not* mess with the rewrite fuel. It's not used at all for analysis, only for rewrites, and it's the analysis that is going bad on you. Instead, simply arrange give an extra "fuel" counter to function 'loop' line 603 of Compiler.Hoopl.Dataflow. If you run out of fuel, print some information about blocks left in the to-do list and the next few iterations. You can give enough fuel for (say) 100 passes through each block. Do this if DEBUG is defined. In this way you'll get much more information than non-termination. ========== For the constant-prop stuff, you want to know what each fact means. Something like x -> BOT "I have no information about x" x -> val "x always has value val, on all the control flow paths I have seen so far" x -> NAC "x can have more than one value depending on the control flow path that reaches this point" Now the transfer functions in your email make perfect sense. Simon | -----Original Message----- | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of Jan Stolarek | Sent: 26 July 2013 22:48 | To: Edward Z. Yang | Cc: ghc-devs | Subject: Re: Two Hoopl questions | | Thank you Edward. I am aware of these requirements - my problem is writing the | code in which these | will always hold (I'm optimizing Cmm and hand-written Cmm files tend to cause | many problems that | don't appear in automatically generated Cmm). Having a debugging tool in form of | Fuel would be | helpful for me, because instead of getting a freeze and seeing no output from - | ddump-cmm I would | see incorrectly transformed Cmm that would allow me to track bugs more easily. | | > > • The transfer function must be monotonic: given a more infor- | > > mative fact in, it must produce a more informative fact out. | I spent some considerable time thinking about this. Consider a simple example of | copy propagation. | Let's assume that { x = NAC }, i.e. we know that x has been defined earlier but is | Not-A-Constant | and so we cannot rewrite it. Now we have something llike this: | | x := 3; | y := x; | | Here we are allowed to rewrite y := x with y := 3, because after first statement we | learn that { x | = 3 }. Now consider this: | | x := 3; | x := very_unsafe_stg_call(); | y := x; | | Here, after the first statement we learn that { x = 3 }, but after the second one | we learn once | again that x is NAC and so we are not allowed to rewrite statement y := x. So the | value of x can | change from NAC to a constant and from constant to a NAC. Is such a transfer | function monotonic? | | Janek | | _______________________________________________ | ghc-devs mailing list | ghc-devs@haskell.org | http://www.haskell.org/mailman/listinfo/ghc-devs

I'll allow myself to ask my second question again: 2) In my algorithm I need to initialize all of the blocks in a graph with bottom element of a lattice, except for the entry block, which needs some other initial values. I've written something like this: cmmCopyPropagation dflags graph = do let entry_blk = g_entry graph g' <- dataflowPassFwd graph [(entry_blk, (Top, Top))] $ analRewFwd cpLattice cpTransfer cpRewrite return . fst $ g' cpLattice = DataflowLattice "copy propagation" (Bottom, Bottom) cpJoin However, it seems that Bottom values passed to cpLattice are ignored - I could replace second parameter to DataflowLattice with `undefined` and the code would still run without causing an error. Is there something obviously wrong in the way I pass initial fact values to dataflowPassFwd, or should I look for the problem in other parts of my code? Janek

For some reason they are ignored, or at least the rewritten code looks as if only a single pass was done. I have facts represented like this: data AssignmentFactBot a = Bottom | Const (M.Map a CmmExpr) I initialize the entry node with: g' <- dataflowPassFwd graph [(entry_blk, Const M.empty)] $ analRewFwd cpLattice cpTransfer (cpRewrite dflags) And lattice is initialized with Bottom. Now the join function: joinCpFacts old Bottom = panic "AAAAAAAAAAA" joinCpFacts (Const old) (Const new) = ... joinCpFacts Bottom Bottom = panic "Joining bottom with bottom" joinCpFacts Bottom (Const _) = panic "Joining bottom with const" Two last panics are intended - they should never happen. The first one is for debugging purposes and surprisingly it is never called - only the second equation is. I'm puzzled. Where did I go wrong? Janek ----- Oryginalna wiadomość ----- Od: "Edward Z. Yang" Do: "Jan Stolarek" DW: "Simon Peyton-Jones" , "ghc-devs" Wysłane: wtorek, 30 lipiec 2013 20:40:53 Temat: Re: Two Hoopl questions What happens when you put a loop in your code? Edward Excerpts from Jan Stolarek's message of Tue Jul 30 08:34:44 -0700 2013:

I'll allow myself to ask my second question again:

2) In my algorithm I need to initialize all of the blocks in a graph with bottom element of a lattice, except for the entry block, which needs some other initial values. I've written something like this:

cmmCopyPropagation dflags graph = do let entry_blk = g_entry graph g' <- dataflowPassFwd graph [(entry_blk, (Top, Top))] $ analRewFwd cpLattice cpTransfer cpRewrite return . fst $ g'

cpLattice = DataflowLattice "copy propagation" (Bottom, Bottom) cpJoin

However, it seems that Bottom values passed to cpLattice are ignored - I could replace second parameter to DataflowLattice with `undefined` and the code would still run without causing an error. Is there something obviously wrong in the way I pass initial fact values to dataflowPassFwd, or should I look for the problem in other parts of my code?

Janek

Does Hoopl handle Bottom internally? By "Bottom" I mean the loop-breaking thing that means "this predecessor does not execute". From the debugging output I added to my code it looks that it in fact does because it doesn't do a join when first analyzing a block with two predecessors. If this is really the case then what is the purpose of defining bottom in DataflowLattice? Janek ----- Oryginalna wiadomość ----- Od: "Edward Z. Yang" Do: "Jan Stolarek" DW: "Simon Peyton-Jones" , "ghc-devs" Wysłane: wtorek, 30 lipiec 2013 20:40:53 Temat: Re: Two Hoopl questions What happens when you put a loop in your code? Edward Excerpts from Jan Stolarek's message of Tue Jul 30 08:34:44 -0700 2013:

I'll allow myself to ask my second question again:

2) In my algorithm I need to initialize all of the blocks in a graph with bottom element of a lattice, except for the entry block, which needs some other initial values. I've written something like this:

cmmCopyPropagation dflags graph = do let entry_blk = g_entry graph g' <- dataflowPassFwd graph [(entry_blk, (Top, Top))] $ analRewFwd cpLattice cpTransfer cpRewrite return . fst $ g'

cpLattice = DataflowLattice "copy propagation" (Bottom, Bottom) cpJoin

However, it seems that Bottom values passed to cpLattice are ignored - I could replace second parameter to DataflowLattice with `undefined` and the code would still run without causing an error. Is there something obviously wrong in the way I pass initial fact values to dataflowPassFwd, or should I look for the problem in other parts of my code?

Janek

| Does Hoopl handle Bottom internally? By "Bottom" I mean the loop-breaking thing | that means "this predecessor does not execute". From the debugging output I I don't think so. You supply a lattice data DataflowLattice a = DataflowLattice { fact_name :: String -- Documentation , fact_bot :: a -- Lattice bottom element , fact_join :: JoinFun a -- Lattice join plus change flag -- (changes iff result > old fact) } and the fact_bot value should really be the bottom element. Simon | -----Original Message----- | From: Jan Stolarek [mailto:jan.stolarek@p.lodz.pl] | Sent: 31 July 2013 17:45 | To: Edward Z. Yang | Cc: Simon Peyton-Jones; ghc-devs | Subject: Re: Two Hoopl questions | | Does Hoopl handle Bottom internally? By "Bottom" I mean the loop-breaking thing | that means "this predecessor does not execute". From the debugging output I | added to my code it looks that it in fact does because it doesn't do a join when | first analyzing a block with two predecessors. If this is really the case then what is | the purpose of defining bottom in DataflowLattice? | | Janek | | ----- Oryginalna wiadomość ----- | Od: "Edward Z. Yang" | Do: "Jan Stolarek" | DW: "Simon Peyton-Jones" , "ghc-devs" | Wysłane: wtorek, 30 lipiec 2013 20:40:53 | Temat: Re: Two Hoopl questions | | What happens when you put a loop in your code? | | Edward | | Excerpts from Jan Stolarek's message of Tue Jul 30 08:34:44 -0700 2013: | > I'll allow myself to ask my second question again: | > | > 2) In my algorithm I need to initialize all of the blocks in a graph with bottom | element of a lattice, except for the entry block, which needs some other initial | values. I've written something like this: | > | > cmmCopyPropagation dflags graph = do | > let entry_blk = g_entry graph | > g' <- dataflowPassFwd graph [(entry_blk, (Top, Top))] $ | > analRewFwd cpLattice cpTransfer cpRewrite | > return . fst $ g' | > | > cpLattice = DataflowLattice "copy propagation" (Bottom, Bottom) cpJoin | > | > However, it seems that Bottom values passed to cpLattice are ignored - I could | replace second parameter to DataflowLattice with `undefined` and the code would | still run without causing an error. Is there something obviously wrong in the way I | pass initial fact values to dataflowPassFwd, or should I look for the problem in | other parts of my code? | > | > Janek |