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

Timestamp:

01/23/12 11:21:33 (16 months ago)

Author:

dterei

Comment:

--

Commentary/Compiler/Backends/LLVM/Alias

@@ -96 +96 @@
 }}}
 
-== Progress ==
+== Problems / Optmisations to Solve ==
 
-Some patches have been pushed that implement TBAA and significantly improve the Alias Analysis story. See ticket #5567 for more information.
+=== Safe Loads (speculative load) ===
+
+We want to allow LLVM to speculatively hoist loads out of conditional blocks. Relevant LLVM source code is here:
+
+* [http://llvm.org/docs/doxygen/html/SimplifyCFG_8cpp_source.html SimplifyCFG Source Code]
+* [http://llvm.org/docs/doxygen/html/namespacellvm.html#a4899ff634bf732c16dd22ecfdafdea7d llvm::isSafeToSpeculativelyExecute]
+* [http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-January/046958.html LLVM Mailing List Discussion about 'Safe loads']
+
+'''Following is from Roman Leshchinskiy'''
+
+I've poked around a bit and things are rather complicated. So far I've identified two problems. Here is a small example function:
+
+{{{
+ foo as n = loop 0# 0.0##
+  where
+    loop i x
+      | i >=# n = (# x, I# i #)
+      | otherwise = loop (i +# 1#) (x *## indexDoubleArray# as i)
+}}}
+
+This is the interesting C-- bit:
+
+{{{
+ saH_ret()
+    cb0:
+        Hp = Hp + 8;
+        if (Hp > I32[BaseReg + 92]) goto cb5;
+        ;
+        if (%MO_S_Ge_W32(R1, I32[Sp + 16])) goto cb9;
+        _saO::I32 = R1 + 1;
+        F64[Sp + 0] = %MO_F_Mul_W64(F64[Sp + 0],
+                                    F64[I32[Sp + 12] + ((R1 << 3) + 8)]);
+        R1 = _saO::I32;
+        Hp = Hp - 8;
+        jump saH_info; // [R1]
+}}}
+
+Look 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.
+
+As 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.
+