Add loop level analysis to the NCG backend.

For backends maintaining the CFG during codegen
we can now find loops and their nesting level.

This is based on the Cmm CFG and dominator analysis.

As a result we can estimate edge frequencies a lot better
for methods, resulting in far better code layout.

Speedup on nofib: ~1.5%
Increase in compile times: ~1.9%

To make this feasible this commit adds:
* Dominator analysis based on the Lengauer-Tarjan Algorithm.
* An algorithm estimating global edge frequences from branch
probabilities - In CFG.hs

A few static branch prediction heuristics:

* Expect to take the backedge in loops.
* Expect to take the branch NOT exiting a loop.
* Expect integer vs constant comparisons to be false.

We also treat heap/stack checks special for branch prediction
to avoid them being treated as loops.
21 jobs for master in 496 minutes and 26 seconds (queued for 6 seconds)
Status Job ID Name Coverage
  Lint
passed #179624
lint
lint-linters

00:00:22

passed #179627
lint
lint-submods-branch

00:00:33

passed #179625
lint
lint-testsuite

00:00:25

passed #179626
lint
typecheck-testsuite

00:00:20

 
  Quick Build
passed #179628
x86_64-linux
hadrian-ghc-in-ghci

00:18:35

 
  Build
passed #179631
x86_64-linux
release-x86_64-linux-deb9-dwarf

01:19:44

passed #179630
x86_64-linux
validate-x86_64-linux-deb9-debug

03:32:12

passed #179629
x86_64-linux
validate-x86_64-linux-deb9-hadrian

02:11:37

 
  Full Build
failed #179633
aarch64-linux allowed to fail
validate-aarch64-linux-deb9

01:02:07

passed #179634
x86_64-linux
validate-i386-linux-deb9

01:43:05

passed #179632
x86_64-darwin
validate-x86_64-darwin

01:32:26

passed #179635
x86_64-linux
validate-x86_64-linux-deb9-integer-simple

01:42:37

passed #179636
x86_64-linux
validate-x86_64-linux-deb9-unreg

03:42:41

passed #179637
x86_64-linux
validate-x86_64-linux-fedora27

02:05:47

failed #179639
x86_64-windows allowed to fail
validate-x86_64-windows

00:45:15

failed #179638
x86_64-windows allowed to fail
validate-x86_64-windows-hadrian

00:42:45

 
  Cleanup
passed #179640
x86_64-darwin
cleanup-darwin

00:00:11

 
  Packaging
failed #179641
x86_64-linux allowed to fail
doc-tarball

00:04:08

 
  Testing
manual #179642
x86_64-linux allowed to fail manual
hackage
passed #179643
x86_64-linux
perf-nofib

00:25:21

 
  Deploy
failed #179644
x86_64-linux allowed to fail
pages

00:00:10

 
Name Stage Failure
failed
pages Deploy
$ git checkout .gitmodules
$ git fetch https://gitlab.haskell.org/ghc/ghc-performance-notes.git refs/notes/perf:refs/notes/perf || true
From https://gitlab.haskell.org/ghc/ghc-performance-notes
37d9da76e0..947dc58647 refs/notes/perf -> refs/notes/perf
$ mkdir -p public/doc
$ tar -xf haddock.html.tar.xz -C public/doc
tar: haddock.html.tar.xz: Cannot open: No such file or directory
tar: Error is not recoverable: exiting now
ERROR: Job failed: exit code 1
failed
validate-aarch64-linux-deb9 Full Build
$ cp -Rf $HOME/.cabal cabal-cache
Uploading artifacts...
WARNING: ghc-*.tar.xz: no matching files
WARNING: junit.xml: no matching files
ERROR: No files to upload
Uploading artifacts...
WARNING: junit.xml: no matching files
ERROR: No files to upload
ERROR: Job failed: exit code 1
failed
doc-tarball Packaging
Synchronizing submodule url for 'utils/hsc2hs'
$ git submodule update --init --recursive
$ git checkout .gitmodules
$ git fetch https://gitlab.haskell.org/ghc/ghc-performance-notes.git refs/notes/perf:refs/notes/perf || true
From https://gitlab.haskell.org/ghc/ghc-performance-notes
37d9da76e0..947dc58647 refs/notes/perf -> refs/notes/perf
$ if [ ! -f "$LINUX_BINDIST" ]; then # collapsed multi-line command
Error: ghc-x86_64-mingw32.tar.xz does not exist. Did the 64-bit Windows job fail?
ERROR: Job failed: exit code 1
failed
validate-x86_64-windows-hadrian Full Build
Runtime platform                                    arch=amd64 os=windows pid=4248 revision=1f513601 version=11.10.1
WARNING: ghc.tar.xz: no matching files
WARNING: junit.xml: no matching files
ERROR: No files to upload
Uploading artifacts...
Runtime platform
arch=amd64 os=windows pid=4400 revision=1f513601 version=11.10.1
WARNING: junit.xml: no matching files
ERROR: No files to upload
ERROR: Job failed: exit status 1
failed
validate-x86_64-windows Full Build
Runtime platform                                    arch=amd64 os=windows pid=4348 revision=1f513601 version=11.10.1
WARNING: ghc-*.tar.xz: no matching files
WARNING: junit.xml: no matching files
ERROR: No files to upload
Uploading artifacts...
Runtime platform
arch=amd64 os=windows pid=856 revision=1f513601 version=11.10.1
WARNING: junit.xml: no matching files
ERROR: No files to upload
ERROR: Job failed: exit status 2