Changes between Version 17 and Version 18 of Commentary/Compiler/Backends/LLVM/Alias


Ignore:
Timestamp:
Jan 23, 2012 7:21:33 PM (4 years ago)
Author:
dterei
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/Backends/LLVM/Alias

    v17 v18  
    9696}}}
    9797
    98 == Progress ==
     98== Problems / Optmisations to Solve ==
    9999
    100 Some patches have been pushed that implement TBAA and significantly improve the Alias Analysis story. See ticket #5567 for more information.
     100=== Safe Loads (speculative load) ===
     101
     102We want to allow LLVM to speculatively hoist loads out of conditional blocks. Relevant LLVM source code is here:
     103
     104* [http://llvm.org/docs/doxygen/html/SimplifyCFG_8cpp_source.html SimplifyCFG Source Code]
     105* [http://llvm.org/docs/doxygen/html/namespacellvm.html#a4899ff634bf732c16dd22ecfdafdea7d llvm::isSafeToSpeculativelyExecute]
     106* [http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-January/046958.html LLVM Mailing List Discussion about 'Safe loads']
     107
     108'''Following is from Roman Leshchinskiy'''
     109
     110I've poked around a bit and things are rather complicated. So far I've identified two problems. Here is a small example function:
     111
     112{{{
     113 foo as n = loop 0# 0.0##
     114  where
     115    loop i x
     116      | i >=# n = (# x, I# i #)
     117      | otherwise = loop (i +# 1#) (x *## indexDoubleArray# as i)
     118}}}
     119
     120This is the interesting C-- bit:
     121
     122{{{
     123 saH_ret()
     124    cb0:
     125        Hp = Hp + 8;
     126        if (Hp > I32[BaseReg + 92]) goto cb5;
     127        ;
     128        if (%MO_S_Ge_W32(R1, I32[Sp + 16])) goto cb9;
     129        _saO::I32 = R1 + 1;
     130        F64[Sp + 0] = %MO_F_Mul_W64(F64[Sp + 0],
     131                                    F64[I32[Sp + 12] + ((R1 << 3) + 8)]);
     132        R1 = _saO::I32;
     133        Hp = Hp - 8;
     134        jump saH_info; // [R1]
     135}}}
     136
     137Look at what indexDoubleArray# compiles to: F64[I32[Sp + 12] + ((R1 << 3) + 8)]. We would very much like LLVM to hoist the I32[Sp+12] bit (i.e., loading the pointer to the ByteArray data) out of the loop because that might allow all sorts of wonderful optimisation such as promoting it to a register. But alas, this doesn't happen, LLVM leaves the load in the loop. Why? Because it assumes that the load might fail (for instance, if Sp is NULL) and so can't move it past conditionals. We know, of course, that this particular load can't fail and so can be executed speculatively but there doesn't seem to be a way of communicating this to LLVM.
     138
     139As a quick experiment, I hacked LLVM to accept "safe" annotations on loads and then manually annotated the LLVM assembly generated by GHC and that helped quite a bit. I suppose that's the way to go - we'll have to get this into LLVM in some form and then the backend will have to generate those annotations for loads which can't fail. I assume they are loads through the stack pointer and perhaps the heap pointer unless we're loading newly allocated memory (those loads can't be moved past heap checks). In any case, the stack pointer is the most important thing. I can also imagine annotating pointers (such as Sp) rather than instructions but that doesn't seem to be the LLVM way and it's also less flexible.
     140