Change from slice/concatenation to insert/remove operations

[tommymcm]

Slice and concatenation operations require the compiler to identify and analyze diamond patterns that make engineering (and compilation time) expensive.

To remedy this, we need to encapsulate the most common of these operations in their own general-purpose operations.

Insert element. s' = INS(s, [i] = v) Insert range. s' = INS(s, [i], s_ins)

Remove element. s' = RMV(s, [i]) Remove range. s' = RMV(s, [i:j])

Additionally, the semantics of slice will change to be a view: s0 = s[i:j]

With this the mut2ssa transformations look as follows:

insert(s, i, v)       ==> s' = INS([i], v, s)
insert(s, i, s2)      ==> s' = INS([i], s2, s)
remove(s, i)          ==> s' = RMV([i], s)
remove(s, i, j)       ==> s' = RMV([i:j], s)
append(s, s2)         ==> s' = INS([end], s2, s)
swap(s, i, j, k)      ==> s0 = s[k:k+j-i]
                          s1 = DEF(s[i:j], s0)
                          s2 = s[i:j]
                          s' = DEF(s[k:k+j-i], s2)
swap(s, i, j, s2, i2) ==> s0 = s2[i2:i2+j-i]
                          s' = DEF(s[i:j], s0)
                          s2 = s[i:j]
                          s2' = DEF(s1[i2:i2+j-i], s2)
s2 = split(s, i, j)   ==> s2 = s[i:j]
                          s' = RMV([i:j], s)

This issue exists to nail down details of the change and work out any kinks before implementation.

[tommymcm]

Proposal for swap representations:

Add a swap operation to the IR, then represent the update with DefPHIs.

swap(s, i, j, k)       ==> SWAP(s[k:k+j-i], s[i:j])
                           s' = DEF(s)
swap(sa, i, j, sb, i2) ==> SWAP(sa[i:j], sb[k:k+j-i])
                           sa' = DEF(sa)
                           sb' = DEF(sb)