[SR-10667] Optimise chained SubSequence producing methods into fewer calls

Previous ID	SR-10667
Radar	None
Original Reporter	bnut (JIRA User)
Type	Improvement
Status	In Progress
Resolution

Votes	1
Component/s	Compiler
Labels	Improvement, Performance, SILGen, StarterBug
Assignee	mkita (JIRA)
Priority	Medium

md5: 3d2eff2a03f31963319181f67fe2b19a

Issue Description:

This code (on BidirectionalCollection) is nice and concise, but it's not efficient:

self.suffix(2).dropLast().last

It could be optimised by the compiler into something like this:

index(endIndex, offsetBy: -2, limitedBy: startIndex).map { self[$0] }

At @jckarter's suggestion this could be implemented with @_semantics similar to some existing optimisations on Array and String. An example of this is here: https://github.com/apple/swift/pull/5978.

There's a lot of permutations for suffix, prefix, dropFirst, dropLast, first, last, etc. so adding a special case for every one would be excessive. Ideally there is a more generic approach to pattern match and reduce these kinds of expressions. This might be done by having multiple small patterns, that can be combined to reduce the chain of calls iteratively.

Here are some ideas for further optimisations:

// Sequence:
suffix(m).suffix(n) -> suffix(Swift.min(m, n))
prefix(m).prefix(n) -> prefix(Swift.min(m, n))
dropFirst(m).dropFirst(n) -> dropFirst(m + n)
dropLast(m).dropLast(n) -> dropLast(m + n)

prefix(m).dropFirst(n) -> prefix(m - Swift.min(n,m))
suffix(m).dropFirst(n) -> suffix(m - Swift.min(n,m))

filter(where: predicate).first -> first(where: predicate)

// Collection
prefix(n).first -> first
suffix(n).last -> last

prefix(n).last  -> index(startIndex, offsetBy: n, limitedBy: endIndex).map { self[$0] }

// BidirectionalCollection
suffix(n).first -> index(endIndex, offsetBy: -n, limitedBy: startIndex).map { self[$0] }