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


Ignore:
Timestamp:
Jan 23, 2012 7:21:33 PM (2 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