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, 31 insertions, 9 deletions

diff --git a/compiler/codeGen/StgCmmMonad.hs b/compiler/codeGen/StgCmmMonad.hs
index 836bf30f29..2184e12a8c 100644
--- a/compiler/codeGen/StgCmmMonad.hs
+++ b/compiler/codeGen/StgCmmMonad.hs
@@ -26,6 +26,8 @@ module StgCmmMonad (
         getCodeR, getCode, getCodeScoped, getHeapUsage,
 
         mkCmmIfThenElse, mkCmmIfThen, mkCmmIfGoto,
+        mkCmmIfThenElse', mkCmmIfThen', mkCmmIfGoto',
+
         mkCall, mkCmmCall,
 
         forkClosureBody, forkLneBody, forkAlts, codeOnly,
@@ -833,30 +835,50 @@ getCmm code
 
 
 mkCmmIfThenElse :: CmmExpr -> CmmAGraph -> CmmAGraph -> FCode CmmAGraph
-mkCmmIfThenElse e tbranch fbranch = do
+mkCmmIfThenElse e tbranch fbranch = mkCmmIfThenElse' e tbranch fbranch Nothing
+
+mkCmmIfThenElse' :: CmmExpr -> CmmAGraph -> CmmAGraph
+                 -> Maybe Bool -> FCode CmmAGraph
+mkCmmIfThenElse' e tbranch fbranch likely = do
   tscp  <- getTickScope
   endif <- newLabelC
   tid   <- newLabelC
   fid   <- newLabelC
-  return $ catAGraphs [ mkCbranch e tid fid Nothing
-                      , mkLabel tid tscp, tbranch, mkBranch endif
-                      , mkLabel fid tscp, fbranch, mkLabel endif tscp ]
+
+  let
+    (test, then_, else_, likely') = case likely of
+      Just False | Just e' <- maybeInvertCmmExpr e
+        -- currently NCG doesn't know about likely
+        -- annotations. We manually switch then and
+        -- else branch so the likely false branch
+        -- becomes a fallthrough.
+        -> (e', fbranch, tbranch, Just True)
+      _ -> (e, tbranch, fbranch, likely)
+
+  return $ catAGraphs [ mkCbranch test tid fid likely'
+                      , mkLabel tid tscp, then_, mkBranch endif
+                      , mkLabel fid tscp, else_, mkLabel endif tscp ]
 
 mkCmmIfGoto :: CmmExpr -> BlockId -> FCode CmmAGraph
-mkCmmIfGoto e tid = do
+mkCmmIfGoto e tid = mkCmmIfGoto' e tid Nothing
+
+mkCmmIfGoto' :: CmmExpr -> BlockId -> Maybe Bool -> FCode CmmAGraph
+mkCmmIfGoto' e tid l = do
   endif <- newLabelC
   tscp  <- getTickScope
-  return $ catAGraphs [ mkCbranch e tid endif Nothing, mkLabel endif tscp ]
+  return $ catAGraphs [ mkCbranch e tid endif l, mkLabel endif tscp ]
 
 mkCmmIfThen :: CmmExpr -> CmmAGraph -> FCode CmmAGraph
-mkCmmIfThen e tbranch = do
+mkCmmIfThen e tbranch = mkCmmIfThen' e tbranch Nothing
+
+mkCmmIfThen' :: CmmExpr -> CmmAGraph -> Maybe Bool -> FCode CmmAGraph
+mkCmmIfThen' e tbranch l = do
   endif <- newLabelC
   tid   <- newLabelC
   tscp  <- getTickScope
-  return $ catAGraphs [ mkCbranch e tid endif Nothing
+  return $ catAGraphs [ mkCbranch e tid endif l
                       , mkLabel tid tscp, tbranch, mkLabel endif tscp ]
 
-
 mkCall :: CmmExpr -> (Convention, Convention) -> [CmmFormal] -> [CmmExpr]
        -> UpdFrameOffset -> [CmmExpr] -> FCode CmmAGraph
 mkCall f (callConv, retConv) results actuals updfr_off extra_stack = do