[SR-7102] Compiler performance issue for expressions with generic types

[swift-ci]

Previous ID	SR-7102
Radar	rdar://problem/38141434
Original Reporter	ttflee (JIRA User)
Type	Bug

Attachment: Download

Environment

macOS 10.13.3 (17D47) with Xcode Version 9.3 beta 3 (9Q117m)
Ubuntu 16.04 LTS with Swift version 4.1-dev (LLVM c4ec2ab808, Clang af436f313e, Swift 34e77c0)

Older versions of compilers were also flawed in a similar manner.

Additional Detail from JIRA

Votes	0
Component/s	Compiler
Labels	Bug, Performance, TypeChecker
Assignee	@xedin
Priority	Medium

md5: ec0c55905c6ab64074bc476d9a6292d2

Issue Description:

The following code snippet shows a good case and a bad case for a compilation performance issue for generic. It seems that when '-' and '+' are mixed in the same expression with generic types, compilation time may greatly deteriorate.

import Foundation

func compute2<T: Numeric>(_ t1: T, _ t2: T, _ t3: T, _ t4: T) -> T {
/// Bad case:
return t1 * t1 + t2 * t2 + t3 * t3 - t4 * t4 // Line 5

/// Good case:  
// return t1 \* t1 + t2 \* t2 + t3 \* t3 + t4 \* t4 // Line 8  

}
let result = compute2(2.1, 3, 1.2, 233)
print(result)

In line 5, the Subtract ( - ) operator greatly reduced the speed of compilation in contrast to that of line 8. For reference, the following cases were tested in Ubuntu 16.04 with master build 2018-03-01:

Without any SUBTRACT (i.e., all ADDs) in the expression (GOOD CASE):

real 0m1.667s
user 0m0.285s
sys 0m1.059s

With ALL ADDs replaced by SUBTRACTs (Deteriorate by a little):

real 0m1.041s
user 0m0.896s
sys 0m0.120s

With only the first ADD replaced by a SUBTRACT (BAD),

real 0m3.443s
user 0m2.005s
sys 0m1.101s

With only the second or the last ADD replaced by a SUBTRACT (BAD):

The compilation stopped after 15-20 secs, with 'error: expression was too complex to be solved in reasonable time; consider breaking up the expression into distinct sub-expressions'.

For generic type T, Numeric, FloatingPoint, SignedInteger were also tested and seems to coincide with the one above.

[swift-ci]

Comment by Zhang Chen (JIRA)

The code snippet is uploaded as an attachment.

[swift-ci]

Comment by Zhang Chen (JIRA)

A more simplified case:

func f<T:Numeric>(t: T) -> T{
return t * t - t * t + t * t - t * t
}

[jckarter]

cc @rudkx, @xedin

[jckarter]

@swift-ci create

[slavapestov]

This is now fast, I'll add a regression test.