Tag inference work.

This does three major things:
* Enforce the invariant that all strict fields must contain tagged
pointers.
* Try to predict the tag on bindings in order to omit tag checks.
* Allows functions to pass arguments unlifted (call-by-value).

The former is "simply" achieved by wrapping any constructor allocations with
a case which will evaluate the respective strict bindings.

The prediction is done by a new data flow analysis based on the STG
representation of a program. This also helps us to avoid generating
redudant cases for the above invariant.

StrictWorkers are created by W/W directly and SpecConstr indirectly.
See the Note [Strict Worker Ids]

Other minor changes:

* Add StgUtil module containing a few functions needed by, but
  not specific to the tag analysis.

-------------------------
Metric Decrease:
	T12545
	T18698b
	T18140
	T18923
        LargeRecord
Metric Increase:
        LargeRecord
	ManyAlternatives
	ManyConstructors
	T10421
	T12425
	T12707
	T13035
	T13056
	T13253
	T13253-spj
	T13379
	T15164
	T18282
	T18304
	T18698a
	T1969
	T20049
	T3294
	T4801
	T5321FD
	T5321Fun
	T783
	T9233
	T9675
	T9961
	T19695
	WWRec
-------------------------

3 files changed, 28 insertions, 0 deletions

diff --git a/rts/RtsSymbols.c b/rts/RtsSymbols.c
index e186830b4e..5f97568b62 100644
--- a/rts/RtsSymbols.c
+++ b/rts/RtsSymbols.c
@@ -541,6 +541,12 @@ extern char **environ;
       SymI_HasProto(RET_OLD_ctr)                        \
       SymI_HasProto(RET_UNBOXED_TUP_ctr)                \
       SymI_HasProto(RET_SEMI_loads_avoided)             \
+                                                        \
+      SymI_HasProto(TAG_UNTAGGED_pred)                  \
+      SymI_HasProto(TAG_UNTAGGED_miss)                  \
+      SymI_HasProto(TAG_TAGGED_pred)                    \
+      SymI_HasProto(TAG_TAGGED_miss)                    \
+                                                        \
       SymI_HasProto(RET_NEW_hst)                        \
       SymI_HasProto(RET_OLD_hst)                        \
       SymI_HasProto(RET_UNBOXED_TUP_hst)
diff --git a/rts/Ticky.c b/rts/Ticky.c
index c045f43f56..2ce4aab658 100644
--- a/rts/Ticky.c
+++ b/rts/Ticky.c
@@ -88,6 +88,10 @@ PrintTickyInfo(void)
   unsigned long tot_old_updates   = UPD_OLD_IND_ctr + UPD_OLD_PERM_IND_ctr;
   unsigned long tot_gengc_updates = tot_new_updates + tot_old_updates;
 
+  // Number of times tag inference predicted tagged/untagged correctly
+  // allowing us to skip a tag check (when ticky is disabled)
+  unsigned long tot_tag_preds = TAG_UNTAGGED_pred + TAG_TAGGED_pred;
+
   FILE *tf = RtsFlags.TickyFlags.tickyFile;
 
   /* If tf = NULL, that means the user passed in stderr for the ticky stats
@@ -196,6 +200,17 @@ PrintTickyInfo(void)
               PC(INTAVG(tot_old_updates,tot_gengc_updates)));
   }
 
+  if (tot_tag_preds != 0) {
+      fprintf(tf, "\nTOTAL TAG PREDICTIONS MADE: %9" FMT_Word64 " \n",
+              (StgWord64) tot_tag_preds);
+      fprintf(tf, "TAGGED PREDICTIONS HIT:     %9" FMT_Word64 " \n",
+              (StgWord64) TAG_TAGGED_pred);
+      fprintf(tf, "UNTAGGED PREDICTIONS HIT:   %9" FMT_Word64 " \n",
+              (StgWord64) (TAG_UNTAGGED_pred - TAG_UNTAGGED_miss));
+      fprintf(tf, "UNTAGGED PREDICTIONS MISS:  %9" FMT_Word64 " \n",
+              (StgWord64) TAG_UNTAGGED_miss);
+  }
+
   printRegisteredCounterInfo(tf);
 
   fprintf(tf,"\n**************************************************\n");
diff --git a/rts/include/stg/Ticky.h b/rts/include/stg/Ticky.h
index 3d9d4aee4f..3353bb2f1a 100644
--- a/rts/include/stg/Ticky.h
+++ b/rts/include/stg/Ticky.h
@@ -178,6 +178,13 @@ EXTERN StgInt RET_OLD_ctr INIT(0);
 EXTERN StgInt RET_UNBOXED_TUP_ctr INIT(0);
 
 EXTERN StgInt RET_SEMI_loads_avoided INIT(0);
+
+/* Performance characterization for tag inference */
+EXTERN StgInt TAG_UNTAGGED_pred INIT(0);
+EXTERN StgInt TAG_UNTAGGED_miss INIT(0);
+EXTERN StgInt TAG_TAGGED_pred INIT(0);
+EXTERN StgInt TAG_TAGGED_miss INIT(0);
+
 /* End of counter declarations. */
 
 /* How many bins in ticky's histograms */