GHC che genera operazioni core ridondanti

Question

Ho il seguente programma per convertire ASCII a 6 bit in formato binario.

ascii2bin :: Char -> B.ByteString 
ascii2bin = B.reverse . fst . B.unfoldrN 6 decomp . to6BitASCII -- replace to6BitASCII with ord if you want to compile this 
    where decomp n = case quotRem n 2 of (q,r) -> Just (chr r,q) 

bs2bin :: B.ByteString -> B.ByteString 
bs2bin = B.concatMap ascii2bin 

Questo produce il seguente segmento di base:

Rec { 
$wa 
$wa = 
    \ ww ww1 ww2 w -> 
    case ww2 of wild { 
     __DEFAULT -> 
     let { 
      wild2 
      wild2 = remInt# ww1 2 } in 
     case leWord# (int2Word# wild2) (__word 1114111) of _ { 
      False -> (lvl2 wild2) `cast` ...;                     
      True -> 
      case writeWord8OffAddr# 
        ww 0 (narrow8Word# (int2Word# (ord# (chr# wild2)))) w 
      of s2 { __DEFAULT -> 
      $wa (plusAddr# ww 1) (quotInt# ww1 2) (+# wild 1) s2 
      } 
     }; 
     6 -> (# w, (lvl, lvl1, Just (I# ww1)) #) 
    } 
end Rec } 

notare che ord . chr == id, e quindi v'è un funzionamento ridondante qui: narrow8Word# (int2Word# (ord# (chr# wild2)))

C'è una ragione GHC è inutilmente la conversione da Int - > Char -> Int, o si tratta di un esempio di scarsa generazione di codice? Questo può essere ottimizzato?

MODIFICA: utilizza GHC 7.4.2, non ho provato la compilazione con altre versioni. Da allora ho scoperto che il problema rimane in GHC 7.6.2, ma le operazioni ridondanti vengono rimosse nel ramo HEAD corrente su github.

Answer 1

C'è un motivo per cui GHC sta convertendo inutilmente da Int -> Char -> Int oppure è un esempio di generazione di codice scadente? Questo può essere ottimizzato?

Non proprio (per entrambi). Il core che ottieni da -ddump-simpl non è la fine. Ci sono alcune ottimizzazioni e trasformazioni ancora fatte dopo quella sulla via del codice assembly. Ma rimuovere le conversioni ridondanti qui non è in realtà un'ottimizzazione.

Possono essere e sono rimossi tra il nucleo e il gruppo. Il punto è che questi primop - tranne che per il restringimento - sono no-op, sono presenti solo nel core perché è tipizzato. Dal momento che sono no-op, non importa se nel core c'è una catena ridondante.

Il gruppo che produce 7.6.1 dal codice [è più leggibile di quello che produce 7.4.2, così prendo che] - con ord invece di to6BitASCII - è

ASCII.$wa_info: 
_cXT: 
    addq $64,%r12 
    cmpq 144(%r13),%r12 
    ja _cXX 
    movq %rdi,%rcx 
    cmpq $6,%rdi 
    jne _cXZ 
    movq $GHC.Types.I#_con_info,-56(%r12) 
    movq %rsi,-48(%r12) 
    movq $Data.Maybe.Just_con_info,-40(%r12) 
    leaq -55(%r12),%rax 
    movq %rax,-32(%r12) 
    movq $(,,)_con_info,-24(%r12) 
    movq $lvl1_rVq_closure+1,-16(%r12) 
    movq $lvl_rVp_closure+1,-8(%r12) 
    leaq -38(%r12),%rax 
    movq %rax,0(%r12) 
    leaq -23(%r12),%rbx 
    jmp *0(%rbp) 
_cXX: 
    movq $64,192(%r13) 
_cXV: 
    movl $ASCII.$wa_closure,%ebx 
    jmp *-8(%r13) 
_cXZ: 
    movl $2,%ebx 
    movq %rsi,%rax 
    cqto 
    idivq %rbx 
    movq %rax,%rsi 
    cmpq $1114111,%rdx 
    jbe _cY2 
    movq %rdx,%r14 
    addq $-64,%r12 
    jmp GHC.Char.chr2_info 
_cY2: 
    movb %dl,(%r14) 
    incq %r14 
    leaq 1(%rcx),%rdi 
    addq $-64,%r12 
    jmp ASCII.$wa_info 
    .size ASCII.$wa_info, .-ASCII.$wa_info 

La parte in cui la narrow8Word# (int2Word# (ord# (chr# wild2))) appare nel core è dopo il cmpq $1114111, %rdx. Se il quoziente non è fuori intervallo, il codice passa a _cY2 che non contiene più tali conversioni. Un byte viene scritto sull'array, alcuni puntatori/contatori vengono incrementati, e il gioco è fatto, torna all'inizio.

Penso che sarebbe possibile generare un codice migliore da questo rispetto a GHC attualmente, ma le conversioni non opzionali ridondanti già svaniscono.