• Ömer Sinan Ağacan's avatar
    Fix chaining tagged and untagged ptrs in compacting GC · 0e57d8a1
    Ömer Sinan Ağacan authored
    Currently compacting GC has the invariant that in a chain all fields are tagged
    the same. However this does not really hold: root pointers are not tagged, so
    when we thread a root we initialize a chain without a tag. When the pointed
    objects is evaluated and we have more pointers to it from the heap, we then add
    *tagged* fields to the chain (because pointers to it from the heap are tagged),
    ending up chaining fields with different tags (pointers from roots are NOT
    tagged, pointers from heap are). This breaks the invariant and as a result
    compacting GC turns tagged pointers into non-tagged.
    
    This later causes problem in the generated code where we do reads assuming that
    the pointer is aligned, e.g.
    
        0x7(%rax) -- assumes that pointer is tagged 1
    
    which causes misaligned reads. This caused #17088.
    
    We fix this using the "pointer tagging for large families" patch (#14373,
    !1742):
    
    - With the pointer tagging patch the GC can know what the tagged pointer to a
      CONSTR should be (previously we'd need to know the family size -- large
      families are always tagged 1, small families are tagged depending on the
      constructor).
    
    - Since we now know what the tags should be we no longer need to store the
      pointer tag in the info table pointers when forming chains in the compacting
      GC.
    
    As a result we no longer need to tag pointers in chains with 1/2 depending on
    whether the field points to an info table pointer, or to another field: an info
    table pointer is always tagged 0, everything else in the chain is tagged 1. The
    lost tags in pointers can be retrieved by looking at the info table.
    
    Finally, instead of using tag 1 for fields and tag 0 for info table pointers, we
    use two different tags for fields:
    
    - 1 for fields that have untagged pointers
    - 2 for fields that have tagged pointers
    
    When unchaining we then look at the pointer to a field, and depending on its tag
    we either leave a tagged pointer or an untagged pointer in the field.
    
    This allows chaining untagged and tagged fields together in compacting GC.
    
    Fixes #17088
    
    Nofib results
    -------------
    
    Binaries are smaller because of smaller `Compact.c` code.
    
    make mode=fast EXTRA_RUNTEST_OPTS="-cachegrind" EXTRA_HC_OPTS="-with-rtsopts=-c" NoFibRuns=1
    
        --------------------------------------------------------------------------------
                Program           Size    Allocs    Instrs     Reads    Writes
        --------------------------------------------------------------------------------
                     CS          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                    CSD          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                     FS          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                      S          -0.3%      0.0%     +5.4%     +0.8%     +3.9%
                     VS          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                    VSD          -0.3%      0.0%     -0.0%     -0.0%     -0.2%
                    VSM          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                   anna          -0.1%      0.0%     +0.0%     +0.0%     +0.0%
                   ansi          -0.3%      0.0%     +0.1%     +0.0%     +0.0%
                   atom          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                 awards          -0.2%      0.0%     +0.0%      0.0%     -0.0%
                 banner          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
             bernouilli          -0.3%      0.0%     +0.1%     +0.0%     +0.0%
           binary-trees          -0.2%      0.0%     +0.0%      0.0%     +0.0%
                  boyer          -0.3%      0.0%     +0.2%     +0.0%     +0.0%
                 boyer2          -0.2%      0.0%     +0.2%     +0.1%     +0.0%
                   bspt          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
              cacheprof          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
               calendar          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
               cichelli          -0.3%      0.0%     +1.1%     +0.2%     +0.5%
                circsim          -0.2%      0.0%     +0.0%     -0.0%     -0.0%
               clausify          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
          comp_lab_zift          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
               compress          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
              compress2          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
            constraints          -0.3%      0.0%     +0.2%     +0.1%     +0.1%
           cryptarithm1          -0.3%      0.0%     +0.0%     -0.0%      0.0%
           cryptarithm2          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                    cse          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
           digits-of-e1          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
           digits-of-e2          -0.3%      0.0%     +0.0%     +0.0%     -0.0%
                 dom-lt          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                  eliza          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                  event          -0.3%      0.0%     +0.1%     +0.0%     -0.0%
            exact-reals          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                 exp3_8          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                 expert          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
         fannkuch-redux          -0.3%      0.0%     -0.0%     -0.0%     -0.0%
                  fasta          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                    fem          -0.2%      0.0%     +0.1%     +0.0%     +0.0%
                    fft          -0.2%      0.0%     +0.0%     -0.0%     -0.0%
                   fft2          -0.2%      0.0%     +0.0%     -0.0%     +0.0%
               fibheaps          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                   fish          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                  fluid          -0.2%      0.0%     +0.4%     +0.1%     +0.1%
                 fulsom          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                 gamteb          -0.2%      0.0%     +0.1%     +0.0%     +0.0%
                    gcd          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
            gen_regexps          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                 genfft          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                     gg          -0.2%      0.0%     +0.7%     +0.3%     +0.2%
                   grep          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                 hidden          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                    hpg          -0.2%      0.0%     +0.1%     +0.0%     +0.0%
                    ida          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                  infer          -0.2%      0.0%     +0.0%     -0.0%     -0.0%
                integer          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
              integrate          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
           k-nucleotide          -0.2%      0.0%     +0.0%     +0.0%     -0.0%
                  kahan          -0.3%      0.0%     -0.0%     -0.0%     -0.0%
                knights          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                 lambda          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
             last-piece          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                   lcss          -0.3%      0.0%     +0.0%     +0.0%      0.0%
                   life          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                   lift          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                 linear          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
              listcompr          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
               listcopy          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
               maillist          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                 mandel          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                mandel2          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                   mate          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                minimax          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                mkhprog          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
             multiplier          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                 n-body          -0.2%      0.0%     -0.0%     -0.0%     -0.0%
               nucleic2          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                   para          -0.2%      0.0%     +0.0%     -0.0%     -0.0%
              paraffins          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                 parser          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                parstof          -0.2%      0.0%     +0.8%     +0.2%     +0.2%
                    pic          -0.2%      0.0%     +0.1%     -0.1%     -0.1%
               pidigits          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                  power          -0.2%      0.0%     +0.0%     -0.0%     -0.0%
                 pretty          -0.3%      0.0%     -0.0%     -0.0%     -0.1%
                 primes          -0.3%      0.0%     +0.0%     +0.0%     -0.0%
              primetest          -0.2%      0.0%     +0.0%     -0.0%     -0.0%
                 prolog          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                 puzzle          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                 queens          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                reptile          -0.2%      0.0%     +0.2%     +0.1%     +0.0%
        reverse-complem          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                rewrite          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                   rfib          -0.2%      0.0%     +0.0%     +0.0%     -0.0%
                    rsa          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                    scc          -0.3%      0.0%     -0.0%     -0.0%     -0.1%
                  sched          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                    scs          -0.2%      0.0%     +0.1%     +0.0%     +0.0%
                 simple          -0.2%      0.0%     +3.4%     +1.0%     +1.8%
                  solid          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                sorting          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
          spectral-norm          -0.2%      0.0%     -0.0%     -0.0%     -0.0%
                 sphere          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                 symalg          -0.2%      0.0%     +0.0%     +0.0%     +0.0%
                    tak          -0.3%      0.0%     +0.0%     +0.0%     -0.0%
              transform          -0.2%      0.0%     +0.2%     +0.1%     +0.1%
               treejoin          -0.3%      0.0%     +0.2%     -0.0%     -0.1%
              typecheck          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
                veritas          -0.1%      0.0%     +0.0%     +0.0%     +0.0%
                   wang          -0.2%      0.0%     +0.0%     -0.0%     -0.0%
              wave4main          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
           wheel-sieve1          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
           wheel-sieve2          -0.3%      0.0%     +0.0%     -0.0%     -0.0%
                   x2n1          -0.3%      0.0%     +0.0%     +0.0%     +0.0%
        --------------------------------------------------------------------------------
                    Min          -0.3%      0.0%     -0.0%     -0.1%     -0.2%
                    Max          -0.1%      0.0%     +5.4%     +1.0%     +3.9%
         Geometric Mean          -0.3%     -0.0%     +0.1%     +0.0%     +0.1%
    
        --------------------------------------------------------------------------------
                Program           Size    Allocs    Instrs     Reads    Writes
        --------------------------------------------------------------------------------
                circsim          -0.2%      0.0%     +1.6%     +0.4%     +0.7%
            constraints          -0.3%      0.0%     +4.3%     +1.5%     +2.3%
               fibheaps          -0.3%      0.0%     +3.5%     +1.2%     +1.3%
                 fulsom          -0.2%      0.0%     +3.6%     +1.2%     +1.8%
               gc_bench          -0.3%      0.0%     +4.1%     +1.3%     +2.3%
                   hash          -0.3%      0.0%     +6.6%     +2.2%     +3.6%
                   lcss          -0.3%      0.0%     +0.7%     +0.2%     +0.7%
              mutstore1          -0.3%      0.0%     +4.8%     +1.4%     +2.8%
              mutstore2          -0.3%      0.0%     +3.4%     +1.0%     +1.7%
                  power          -0.2%      0.0%     +2.7%     +0.6%     +1.9%
             spellcheck          -0.3%      0.0%     +1.1%     +0.4%     +0.4%
        --------------------------------------------------------------------------------
                    Min          -0.3%      0.0%     +0.7%     +0.2%     +0.4%
                    Max          -0.2%      0.0%     +6.6%     +2.2%     +3.6%
         Geometric Mean          -0.3%     +0.0%     +3.3%     +1.0%     +1.8%
    
    Metric changes
    --------------
    
    While it sounds ridiculous, this change causes increased allocations in
    the following tests. We concluded that this change can't cause a
    difference in allocations and decided to land this patch. Fluctuations
    in "bytes allocated" metric is tracked in #17686.
    
    Metric Increase:
        Naperian
        T10547
        T12150
        T12234
        T12425
        T13035
        T5837
        T6048
    0e57d8a1
Compact.c 24.8 KB