LLVM generate llvm.expect for conditional branches

This patch adds likeliness annotations to heap and and stack checks and
modifies the llvm codegen to recognize those to help it generate better
code.

So with this patch

```
...
if ((Sp + 8) - 24 < SpLim) (likely: False) goto c23c; else goto c23d;
...
```

roughly generates:

```
  %ln23k = icmp ult i64 %ln23j, %SpLim_Arg
  %ln23m = call ccc i1 (i1, i1) @llvm.expect.i1( i1 %ln23k, i1 0 )
  br i1 %ln23m, label %c23c, label %c23d
```

Note the call to `llvm.expect` which denotes the expected result for
the comparison.

Test Plan: Look at assembler code with and without this patch. If the
heap-checks moved out of the way we are happy.

Reviewers: austin, simonmar, bgamari

Reviewed By: bgamari

Subscribers: michalt, thomie

Differential Revision: https://phabricator.haskell.org/D2688

GHC Trac Issues: #8321

1 files changed, 28 insertions, 7 deletions

diff --git a/compiler/llvmGen/LlvmCodeGen/CodeGen.hs b/compiler/llvmGen/LlvmCodeGen/CodeGen.hs
index fa47d6ada3..7b610c0a0a 100644
--- a/compiler/llvmGen/LlvmCodeGen/CodeGen.hs
+++ b/compiler/llvmGen/LlvmCodeGen/CodeGen.hs
@@ -118,8 +118,8 @@ stmtToInstrs stmt = case stmt of
     CmmStore addr src    -> genStore addr src
 
     CmmBranch id         -> genBranch id
-    CmmCondBranch arg true false _      -- TODO: likely annotation
-                         -> genCondBranch arg true false
+    CmmCondBranch arg true false likely
+                         -> genCondBranch arg true false likely
     CmmSwitch arg ids    -> genSwitch arg ids
 
     -- Foreign Call
@@ -925,20 +925,41 @@ genBranch id =
 
 
 -- | Conditional branch
-genCondBranch :: CmmExpr -> BlockId -> BlockId -> LlvmM StmtData
-genCondBranch cond idT idF = do
+genCondBranch :: CmmExpr -> BlockId -> BlockId -> Maybe Bool -> LlvmM StmtData
+genCondBranch cond idT idF likely = do
     let labelT = blockIdToLlvm idT
     let labelF = blockIdToLlvm idF
     -- See Note [Literals and branch conditions].
-    (vc, stmts, top) <- exprToVarOpt i1Option cond
+    (vc, stmts1, top1) <- exprToVarOpt i1Option cond
     if getVarType vc == i1
         then do
-            let s1 = BranchIf vc labelT labelF
-            return (stmts `snocOL` s1, top)
+            (vc', (stmts2, top2)) <- case likely of
+              Just b -> genExpectLit (if b then 1 else 0) i1  vc
+              _      -> pure (vc, (nilOL, []))
+            let s1 = BranchIf vc' labelT labelF
+            return (stmts1 `appOL` stmts2 `snocOL` s1, top1 ++ top2)
         else do
             dflags <- getDynFlags
             panic $ "genCondBranch: Cond expr not bool! (" ++ showSDoc dflags (ppr vc) ++ ")"
 
+
+-- | Generate call to llvm.expect.x intrinsic. Assigning result to a new var.
+genExpectLit :: Integer -> LlvmType -> LlvmVar -> LlvmM (LlvmVar, StmtData)
+genExpectLit expLit expTy var = do
+  dflags <- getDynFlags
+
+  let
+    lit = LMLitVar $ LMIntLit expLit expTy
+
+    llvmExpectName
+      | isInt expTy = fsLit $ "llvm.expect." ++ showSDoc dflags (ppr expTy)
+      | otherwise   = panic $ "genExpectedLit: Type not an int!"
+
+  (llvmExpect, stmts, top) <-
+    getInstrinct llvmExpectName expTy [expTy, expTy]
+  (var', call) <- doExpr expTy $ Call StdCall llvmExpect [var, lit] []
+  return (var', (stmts `snocOL` call, top))
+
 {- Note [Literals and branch conditions]
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~