Backend test fail with --no-fold

[bradunov]

Backend test fails with --no-fold: EXTRAOPTS=--no-fold make passfold-eval-5.test -B

[ghost]

Simple to debug:

C output without --no-fold:

x_ln20_1 = x_ln20_1 + 1;
x_ln20_1 = x_ln20_1 + 1;
__struct12.re = x_ln20_1;
__struct12.im = x_ln20_1;
xln30_13.re = __struct12.re;
xln30_13.im = __struct12.im;
eval_1_ln28_14 = xln30_13.re;

C output with --no-fold:

int32 f_ln22_2(int32* x3)
{
    *x3 = *x3 + 1;
    return *x3;
}

...

mem_idx15 = wpl_get_free_idx(pheap_ctx);
ret14 = f_ln22_2(&x_ln20_1);
wpl_restore_free_idx(pheap_ctx, mem_idx15);
mem_idx17 = wpl_get_free_idx(pheap_ctx);
ret16 = f_ln22_2(&x_ln20_1);
wpl_restore_free_idx(pheap_ctx, mem_idx17);
__struct18.re = ret14;
__struct18.im = ret16;
xln30_19.re = __struct18.re;
xln30_19.im = __struct18.im;
eval_1_ln30_20 = xln30_19.re;

x_ln20_1 is initially 0. So instead of the expected value of 2, it returns 1.

[dimitriv]

Huh --- it looks like a code generator bug actually, not an optimizer bug. Doing '--ddump-fold --stdout-dump' reveals:

var x{_r2} : int32 :=
    0 in
((read[int32] >>>
  seq { a{_r9} <- take[int32];
        let eval_1{_r13} : int32 =
            let x{_r11} : complex32 =
              complex32 {re = x{_r2} := -- (easgn)
                                x{_r2}+1;
                              x{_r2}, im = x{_r2} := -- (easgn)
                                             x{_r2}+1;
                                           x{_r2}}
            in
            x{_r11}.re
        in
        seq { _unused_22{_pf22} <- emit a{_r9};
              _unused_21{_pf21} <- emit eval_1{_r13};
              _unused_20{_pf20} <- emit x{_r2};
              emit a{_r9}
            }
      }) >>>
 write[int32])

Which still looks right to me but the evaluation bug is that it decided to execute all side-effects /first/ and then do assignments to the re and im part of the complex number. Now, in the case of function calls, because it created different temporaries the bug did not manifest. In the case of inlined expressions, since they both returned x, the bug manifested. The solution is to fix this in the "abstract evaluator", which does (Analysis/AbsInt.hs):

  go (EStruct nm tfs) = do
    atfs <- mapM eval_fld tfs
    rValM (aStruct nm atfs)
    where eval_fld (f,x) = absEvalRVal x >>= \v -> return (f, v)

Similarly the code generator (CgValDom.hs) does:

cgStruct :: DynFlags -> SrcLoc -> Ty -> [(FldName,C.Exp)] -> Cg C.Exp
cgStruct _dfs _loc t@(TStruct _sn fld_tys) fld_exps = do
   snm <- freshName "__struct" t Mut
   let csnm = [cexp| $id:(name snm)|]
   appendCodeGenDeclGroup (name snm) t ZeroOut
   let fld_ty f   = fromJust $ lookup f fld_tys
       proj_exp f = cgStrProj (fld_ty f) csnm t f
   mapM_ (\(fn,fe) -> assignByVal (fld_ty fn) (proj_exp fn) fe) fld_exps

And where does he get those C.Exp? The main expression code generator (CgExpr.hs) does:

  go (EStruct t tes) = do
      ctes <- mapM (\(f,ef) ->
        do cef <- cgEvalRVal dfs ef
           return (f,cef)) tes
      Right <$> cgStruct dfs loc t ctes

Hence they all agree to hoist out the side effects, execute them one by one and then do assignments. They are consistent with each other at least (and I believe the partial evaluator Interpreter.hs) is also consistent. But I think a much nicer approach (and one that would avoid these problems) would be to change all those parts to (a) execute, (b) assign and /then/ move on to the next field of the structure. @siddhanathan, @mainland makes sense? Another alternative would be to have made sure that all side-effects are already hoisted out by code generation time. E.g. we could have a pass that converts:

complex16 { x = big-complicated-expression, ... }

to

let x_tmp = big-complicated-expression
in complex16 { x = x_tmp, ... }

and let the inliner worry about avoiding extra memory copies etc. Thoughts?

[dimitriv]

Yeah I kind of like the idea that in the core expression language you never see a side-effect inside the field assignments of a struct, i.e. the evaluation order has become more explicit than in source. (Adding @bradunov in the discussion)

[dimitriv]

I admit I kind of knew this all along, but I guess we should fix it at some point.

[ghost]

I don't fully understand. Shouldn't all the side-effects occur before assignments? I would assume that is the expected behavior. I thought the bug manifested in the case of function calls, but everything was okay in the case of inlined expressions.

And I completely agree with isolating side-effects, by having all side effects occur before assignment of struct fields.

[mainland]

I asked about this very test earlier on the email list :) Yes, I think struct field assignments should be pure in the core language. The alternative front end I have lowers all effects, including assignment and dereferences, so things like struct field assignments and function call arguments are all pure.

[bradunov]

Sorry, I missed that. ☺ I was actually chasing another bug with --no-fold that I observed with pedantic LTE tests, and then stumbled upon this one while trying to make a smaller test case.

From: Geoffrey Mainland [mailto:notifications@github.com] Sent: 16 October 2015 04:47 To: dimitriv/Ziria Ziria@noreply.github.com Cc: Bozidar Radunovic bozidar@microsoft.com Subject: Re: [Ziria] Backend test fail with --no-fold (#120)

I asked about this very test earlier on the email list :) Yes, I think struct field assignments should be pure in the core language. The alternative front end I have lowers all effects, including assignment and dereferences, so things like struct field assignments and function call arguments are all pure.

— Reply to this email directly or view it on GitHubhttps://na01.safelinks.protection.outlook.com/?url=https%3a%2f%2fgithub.com%2fdimitriv%2fZiria%2fissues%2f120%23issuecomment-148592241&data=01%7c01%7cbozidar%40064d.mgd.microsoft.com%7c37f4e49b07b34a2daf4d08d2d5dc67d5%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=NNx6%2bHfUyH6wbsu%2fMyxVLRfdtcm3NqW4If4LbiE1OIE%3d.

[dimitriv]

Indeed. I think the fix (in the current compiler) might be as simple as implementing a mandatory pass that hoists out the side effects when assigning to struct fields. Then I don't have to review every single interpreter/abstract interpreter/code generator piece in the compiler. I can try and get 10-15' to do that today. (In a refactoring, I agree with Geoff -- it'd be nice to have that invariant by construction expressed in the AST)