Source file src/cmd/compile/internal/ssa/rewriteCond_test.go

     1  // Copyright 2020 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package ssa
     6  
     7  import (
     8  	"math"
     9  	"math/rand"
    10  	"testing"
    11  )
    12  
    13  var (
    14  	x64   int64  = math.MaxInt64 - 2
    15  	x64b  int64  = math.MaxInt64 - 2
    16  	x64c  int64  = math.MaxInt64 - 2
    17  	y64   int64  = math.MinInt64 + 1
    18  	x32   int32  = math.MaxInt32 - 2
    19  	x32b  int32  = math.MaxInt32 - 2
    20  	x32c  int32  = math.MaxInt32 - 2
    21  	y32   int32  = math.MinInt32 + 1
    22  	one64 int64  = 1
    23  	one32 int32  = 1
    24  	v64   int64  = 11 // ensure it's not 2**n +/- 1
    25  	v64_n int64  = -11
    26  	v32   int32  = 11
    27  	v32_n int32  = -11
    28  	uv32  uint32 = 19
    29  	uz    uint8  = 1 // for lowering to SLL/SRL/SRA
    30  )
    31  
    32  var crTests = []struct {
    33  	name string
    34  	tf   func(t *testing.T)
    35  }{
    36  	{"AddConst64", testAddConst64},
    37  	{"AddConst32", testAddConst32},
    38  	{"AddVar64", testAddVar64},
    39  	{"AddVar32", testAddVar32},
    40  	{"MAddVar64", testMAddVar64},
    41  	{"MAddVar32", testMAddVar32},
    42  	{"MSubVar64", testMSubVar64},
    43  	{"MSubVar32", testMSubVar32},
    44  	{"AddShift32", testAddShift32},
    45  	{"SubShift32", testSubShift32},
    46  }
    47  
    48  var crBenches = []struct {
    49  	name string
    50  	bf   func(b *testing.B)
    51  }{
    52  	{"SoloJump", benchSoloJump},
    53  	{"CombJump", benchCombJump},
    54  }
    55  
    56  // Test int32/int64's add/sub/madd/msub operations with boundary values to
    57  // ensure the optimization to 'comparing to zero' expressions of if-statements
    58  // yield expected results.
    59  // 32 rewriting rules are covered. At least two scenarios for "Canonicalize
    60  // the order of arguments to comparisons", which helps with CSE, are covered.
    61  // The tedious if-else structures are necessary to ensure all concerned rules
    62  // and machine code sequences are covered.
    63  // It's for arm64 initially, please see https://github.com/golang/go/issues/38740
    64  func TestCondRewrite(t *testing.T) {
    65  	for _, test := range crTests {
    66  		t.Run(test.name, test.tf)
    67  	}
    68  }
    69  
    70  // Profile the aforementioned optimization from two angles:
    71  //   SoloJump: generated branching code has one 'jump', for '<' and '>='
    72  //   CombJump: generated branching code has two consecutive 'jump', for '<=' and '>'
    73  // We expect that 'CombJump' is generally on par with the non-optimized code, and
    74  // 'SoloJump' demonstrates some improvement.
    75  // It's for arm64 initially, please see https://github.com/golang/go/issues/38740
    76  func BenchmarkCondRewrite(b *testing.B) {
    77  	for _, bench := range crBenches {
    78  		b.Run(bench.name, bench.bf)
    79  	}
    80  }
    81  
    82  // var +/- const
    83  func testAddConst64(t *testing.T) {
    84  	if x64+11 < 0 {
    85  	} else {
    86  		t.Errorf("'%#x + 11 < 0' failed", x64)
    87  	}
    88  
    89  	if x64+13 <= 0 {
    90  	} else {
    91  		t.Errorf("'%#x + 13 <= 0' failed", x64)
    92  	}
    93  
    94  	if y64-11 > 0 {
    95  	} else {
    96  		t.Errorf("'%#x - 11 > 0' failed", y64)
    97  	}
    98  
    99  	if y64-13 >= 0 {
   100  	} else {
   101  		t.Errorf("'%#x - 13 >= 0' failed", y64)
   102  	}
   103  
   104  	if x64+19 > 0 {
   105  		t.Errorf("'%#x + 19 > 0' failed", x64)
   106  	}
   107  
   108  	if x64+23 >= 0 {
   109  		t.Errorf("'%#x + 23 >= 0' failed", x64)
   110  	}
   111  
   112  	if y64-19 < 0 {
   113  		t.Errorf("'%#x - 19 < 0' failed", y64)
   114  	}
   115  
   116  	if y64-23 <= 0 {
   117  		t.Errorf("'%#x - 23 <= 0' failed", y64)
   118  	}
   119  }
   120  
   121  // 32-bit var +/- const
   122  func testAddConst32(t *testing.T) {
   123  	if x32+11 < 0 {
   124  	} else {
   125  		t.Errorf("'%#x + 11 < 0' failed", x32)
   126  	}
   127  
   128  	if x32+13 <= 0 {
   129  	} else {
   130  		t.Errorf("'%#x + 13 <= 0' failed", x32)
   131  	}
   132  
   133  	if y32-11 > 0 {
   134  	} else {
   135  		t.Errorf("'%#x - 11 > 0' failed", y32)
   136  	}
   137  
   138  	if y32-13 >= 0 {
   139  	} else {
   140  		t.Errorf("'%#x - 13 >= 0' failed", y32)
   141  	}
   142  
   143  	if x32+19 > 0 {
   144  		t.Errorf("'%#x + 19 > 0' failed", x32)
   145  	}
   146  
   147  	if x32+23 >= 0 {
   148  		t.Errorf("'%#x + 23 >= 0' failed", x32)
   149  	}
   150  
   151  	if y32-19 < 0 {
   152  		t.Errorf("'%#x - 19 < 0' failed", y32)
   153  	}
   154  
   155  	if y32-23 <= 0 {
   156  		t.Errorf("'%#x - 23 <= 0' failed", y32)
   157  	}
   158  }
   159  
   160  // var + var
   161  func testAddVar64(t *testing.T) {
   162  	if x64+v64 < 0 {
   163  	} else {
   164  		t.Errorf("'%#x + %#x < 0' failed", x64, v64)
   165  	}
   166  
   167  	if x64+v64 <= 0 {
   168  	} else {
   169  		t.Errorf("'%#x + %#x <= 0' failed", x64, v64)
   170  	}
   171  
   172  	if y64+v64_n > 0 {
   173  	} else {
   174  		t.Errorf("'%#x + %#x > 0' failed", y64, v64_n)
   175  	}
   176  
   177  	if y64+v64_n >= 0 {
   178  	} else {
   179  		t.Errorf("'%#x + %#x >= 0' failed", y64, v64_n)
   180  	}
   181  
   182  	if x64+v64 > 0 {
   183  		t.Errorf("'%#x + %#x > 0' failed", x64, v64)
   184  	}
   185  
   186  	if x64+v64 >= 0 {
   187  		t.Errorf("'%#x + %#x >= 0' failed", x64, v64)
   188  	}
   189  
   190  	if y64+v64_n < 0 {
   191  		t.Errorf("'%#x + %#x < 0' failed", y64, v64_n)
   192  	}
   193  
   194  	if y64+v64_n <= 0 {
   195  		t.Errorf("'%#x + %#x <= 0' failed", y64, v64_n)
   196  	}
   197  }
   198  
   199  // 32-bit var+var
   200  func testAddVar32(t *testing.T) {
   201  	if x32+v32 < 0 {
   202  	} else {
   203  		t.Errorf("'%#x + %#x < 0' failed", x32, v32)
   204  	}
   205  
   206  	if x32+v32 <= 0 {
   207  	} else {
   208  		t.Errorf("'%#x + %#x <= 0' failed", x32, v32)
   209  	}
   210  
   211  	if y32+v32_n > 0 {
   212  	} else {
   213  		t.Errorf("'%#x + %#x > 0' failed", y32, v32_n)
   214  	}
   215  
   216  	if y32+v32_n >= 0 {
   217  	} else {
   218  		t.Errorf("'%#x + %#x >= 0' failed", y32, v32_n)
   219  	}
   220  
   221  	if x32+v32 > 0 {
   222  		t.Errorf("'%#x + %#x > 0' failed", x32, v32)
   223  	}
   224  
   225  	if x32+v32 >= 0 {
   226  		t.Errorf("'%#x + %#x >= 0' failed", x32, v32)
   227  	}
   228  
   229  	if y32+v32_n < 0 {
   230  		t.Errorf("'%#x + %#x < 0' failed", y32, v32_n)
   231  	}
   232  
   233  	if y32+v32_n <= 0 {
   234  		t.Errorf("'%#x + %#x <= 0' failed", y32, v32_n)
   235  	}
   236  }
   237  
   238  // multiply-add
   239  func testMAddVar64(t *testing.T) {
   240  	if x64+v64*one64 < 0 {
   241  	} else {
   242  		t.Errorf("'%#x + %#x*1 < 0' failed", x64, v64)
   243  	}
   244  
   245  	if x64+v64*one64 <= 0 {
   246  	} else {
   247  		t.Errorf("'%#x + %#x*1 <= 0' failed", x64, v64)
   248  	}
   249  
   250  	if y64+v64_n*one64 > 0 {
   251  	} else {
   252  		t.Errorf("'%#x + %#x*1 > 0' failed", y64, v64_n)
   253  	}
   254  
   255  	if y64+v64_n*one64 >= 0 {
   256  	} else {
   257  		t.Errorf("'%#x + %#x*1 >= 0' failed", y64, v64_n)
   258  	}
   259  
   260  	if x64+v64*one64 > 0 {
   261  		t.Errorf("'%#x + %#x*1 > 0' failed", x64, v64)
   262  	}
   263  
   264  	if x64+v64*one64 >= 0 {
   265  		t.Errorf("'%#x + %#x*1 >= 0' failed", x64, v64)
   266  	}
   267  
   268  	if y64+v64_n*one64 < 0 {
   269  		t.Errorf("'%#x + %#x*1 < 0' failed", y64, v64_n)
   270  	}
   271  
   272  	if y64+v64_n*one64 <= 0 {
   273  		t.Errorf("'%#x + %#x*1 <= 0' failed", y64, v64_n)
   274  	}
   275  }
   276  
   277  // 32-bit multiply-add
   278  func testMAddVar32(t *testing.T) {
   279  	if x32+v32*one32 < 0 {
   280  	} else {
   281  		t.Errorf("'%#x + %#x*1 < 0' failed", x32, v32)
   282  	}
   283  
   284  	if x32+v32*one32 <= 0 {
   285  	} else {
   286  		t.Errorf("'%#x + %#x*1 <= 0' failed", x32, v32)
   287  	}
   288  
   289  	if y32+v32_n*one32 > 0 {
   290  	} else {
   291  		t.Errorf("'%#x + %#x*1 > 0' failed", y32, v32_n)
   292  	}
   293  
   294  	if y32+v32_n*one32 >= 0 {
   295  	} else {
   296  		t.Errorf("'%#x + %#x*1 >= 0' failed", y32, v32_n)
   297  	}
   298  
   299  	if x32+v32*one32 > 0 {
   300  		t.Errorf("'%#x + %#x*1 > 0' failed", x32, v32)
   301  	}
   302  
   303  	if x32+v32*one32 >= 0 {
   304  		t.Errorf("'%#x + %#x*1 >= 0' failed", x32, v32)
   305  	}
   306  
   307  	if y32+v32_n*one32 < 0 {
   308  		t.Errorf("'%#x + %#x*1 < 0' failed", y32, v32_n)
   309  	}
   310  
   311  	if y32+v32_n*one32 <= 0 {
   312  		t.Errorf("'%#x + %#x*1 <= 0' failed", y32, v32_n)
   313  	}
   314  }
   315  
   316  // multiply-sub
   317  func testMSubVar64(t *testing.T) {
   318  	if x64-v64_n*one64 < 0 {
   319  	} else {
   320  		t.Errorf("'%#x - %#x*1 < 0' failed", x64, v64_n)
   321  	}
   322  
   323  	if x64-v64_n*one64 <= 0 {
   324  	} else {
   325  		t.Errorf("'%#x - %#x*1 <= 0' failed", x64, v64_n)
   326  	}
   327  
   328  	if y64-v64*one64 > 0 {
   329  	} else {
   330  		t.Errorf("'%#x - %#x*1 > 0' failed", y64, v64)
   331  	}
   332  
   333  	if y64-v64*one64 >= 0 {
   334  	} else {
   335  		t.Errorf("'%#x - %#x*1 >= 0' failed", y64, v64)
   336  	}
   337  
   338  	if x64-v64_n*one64 > 0 {
   339  		t.Errorf("'%#x - %#x*1 > 0' failed", x64, v64_n)
   340  	}
   341  
   342  	if x64-v64_n*one64 >= 0 {
   343  		t.Errorf("'%#x - %#x*1 >= 0' failed", x64, v64_n)
   344  	}
   345  
   346  	if y64-v64*one64 < 0 {
   347  		t.Errorf("'%#x - %#x*1 < 0' failed", y64, v64)
   348  	}
   349  
   350  	if y64-v64*one64 <= 0 {
   351  		t.Errorf("'%#x - %#x*1 <= 0' failed", y64, v64)
   352  	}
   353  
   354  	if x64-x64b*one64 < 0 {
   355  		t.Errorf("'%#x - %#x*1 < 0' failed", x64, x64b)
   356  	}
   357  
   358  	if x64-x64b*one64 >= 0 {
   359  	} else {
   360  		t.Errorf("'%#x - %#x*1 >= 0' failed", x64, x64b)
   361  	}
   362  }
   363  
   364  // 32-bit multiply-sub
   365  func testMSubVar32(t *testing.T) {
   366  	if x32-v32_n*one32 < 0 {
   367  	} else {
   368  		t.Errorf("'%#x - %#x*1 < 0' failed", x32, v32_n)
   369  	}
   370  
   371  	if x32-v32_n*one32 <= 0 {
   372  	} else {
   373  		t.Errorf("'%#x - %#x*1 <= 0' failed", x32, v32_n)
   374  	}
   375  
   376  	if y32-v32*one32 > 0 {
   377  	} else {
   378  		t.Errorf("'%#x - %#x*1 > 0' failed", y32, v32)
   379  	}
   380  
   381  	if y32-v32*one32 >= 0 {
   382  	} else {
   383  		t.Errorf("'%#x - %#x*1 >= 0' failed", y32, v32)
   384  	}
   385  
   386  	if x32-v32_n*one32 > 0 {
   387  		t.Errorf("'%#x - %#x*1 > 0' failed", x32, v32_n)
   388  	}
   389  
   390  	if x32-v32_n*one32 >= 0 {
   391  		t.Errorf("'%#x - %#x*1 >= 0' failed", x32, v32_n)
   392  	}
   393  
   394  	if y32-v32*one32 < 0 {
   395  		t.Errorf("'%#x - %#x*1 < 0' failed", y32, v32)
   396  	}
   397  
   398  	if y32-v32*one32 <= 0 {
   399  		t.Errorf("'%#x - %#x*1 <= 0' failed", y32, v32)
   400  	}
   401  
   402  	if x32-x32b*one32 < 0 {
   403  		t.Errorf("'%#x - %#x*1 < 0' failed", x32, x32b)
   404  	}
   405  
   406  	if x32-x32b*one32 >= 0 {
   407  	} else {
   408  		t.Errorf("'%#x - %#x*1 >= 0' failed", x32, x32b)
   409  	}
   410  }
   411  
   412  // 32-bit ADDshift, pick up 1~2 scenarios randomly for each condition
   413  func testAddShift32(t *testing.T) {
   414  	if x32+v32<<1 < 0 {
   415  	} else {
   416  		t.Errorf("'%#x + %#x<<%#x < 0' failed", x32, v32, 1)
   417  	}
   418  
   419  	if x32+v32>>1 <= 0 {
   420  	} else {
   421  		t.Errorf("'%#x + %#x>>%#x <= 0' failed", x32, v32, 1)
   422  	}
   423  
   424  	if x32+int32(uv32>>1) > 0 {
   425  		t.Errorf("'%#x + int32(%#x>>%#x) > 0' failed", x32, uv32, 1)
   426  	}
   427  
   428  	if x32+v32<<uz >= 0 {
   429  		t.Errorf("'%#x + %#x<<%#x >= 0' failed", x32, v32, uz)
   430  	}
   431  
   432  	if x32+v32>>uz > 0 {
   433  		t.Errorf("'%#x + %#x>>%#x > 0' failed", x32, v32, uz)
   434  	}
   435  
   436  	if x32+int32(uv32>>uz) < 0 {
   437  	} else {
   438  		t.Errorf("'%#x + int32(%#x>>%#x) < 0' failed", x32, uv32, uz)
   439  	}
   440  }
   441  
   442  // 32-bit SUBshift, pick up 1~2 scenarios randomly for each condition
   443  func testSubShift32(t *testing.T) {
   444  	if y32-v32<<1 > 0 {
   445  	} else {
   446  		t.Errorf("'%#x - %#x<<%#x > 0' failed", y32, v32, 1)
   447  	}
   448  
   449  	if y32-v32>>1 < 0 {
   450  		t.Errorf("'%#x - %#x>>%#x < 0' failed", y32, v32, 1)
   451  	}
   452  
   453  	if y32-int32(uv32>>1) >= 0 {
   454  	} else {
   455  		t.Errorf("'%#x - int32(%#x>>%#x) >= 0' failed", y32, uv32, 1)
   456  	}
   457  
   458  	if y32-v32<<uz < 0 {
   459  		t.Errorf("'%#x - %#x<<%#x < 0' failed", y32, v32, uz)
   460  	}
   461  
   462  	if y32-v32>>uz >= 0 {
   463  	} else {
   464  		t.Errorf("'%#x - %#x>>%#x >= 0' failed", y32, v32, uz)
   465  	}
   466  
   467  	if y32-int32(uv32>>uz) <= 0 {
   468  		t.Errorf("'%#x - int32(%#x>>%#x) <= 0' failed", y32, uv32, uz)
   469  	}
   470  }
   471  
   472  var rnd = rand.New(rand.NewSource(0))
   473  var sink int64
   474  
   475  func benchSoloJump(b *testing.B) {
   476  	r1 := x64
   477  	r2 := x64b
   478  	r3 := x64c
   479  	r4 := y64
   480  	d := rnd.Int63n(10)
   481  
   482  	// 6 out 10 conditions evaluate to true
   483  	for i := 0; i < b.N; i++ {
   484  		if r1+r2 < 0 {
   485  			d *= 2
   486  			d /= 2
   487  		}
   488  
   489  		if r1+r3 >= 0 {
   490  			d *= 2
   491  			d /= 2
   492  		}
   493  
   494  		if r1+r2*one64 < 0 {
   495  			d *= 2
   496  			d /= 2
   497  		}
   498  
   499  		if r2+r3*one64 >= 0 {
   500  			d *= 2
   501  			d /= 2
   502  		}
   503  
   504  		if r1-r2*v64 >= 0 {
   505  			d *= 2
   506  			d /= 2
   507  		}
   508  
   509  		if r3-r4*v64 < 0 {
   510  			d *= 2
   511  			d /= 2
   512  		}
   513  
   514  		if r1+11 < 0 {
   515  			d *= 2
   516  			d /= 2
   517  		}
   518  
   519  		if r1+13 >= 0 {
   520  			d *= 2
   521  			d /= 2
   522  		}
   523  
   524  		if r4-17 < 0 {
   525  			d *= 2
   526  			d /= 2
   527  		}
   528  
   529  		if r4-19 >= 0 {
   530  			d *= 2
   531  			d /= 2
   532  		}
   533  	}
   534  	sink = d
   535  }
   536  
   537  func benchCombJump(b *testing.B) {
   538  	r1 := x64
   539  	r2 := x64b
   540  	r3 := x64c
   541  	r4 := y64
   542  	d := rnd.Int63n(10)
   543  
   544  	// 6 out 10 conditions evaluate to true
   545  	for i := 0; i < b.N; i++ {
   546  		if r1+r2 <= 0 {
   547  			d *= 2
   548  			d /= 2
   549  		}
   550  
   551  		if r1+r3 > 0 {
   552  			d *= 2
   553  			d /= 2
   554  		}
   555  
   556  		if r1+r2*one64 <= 0 {
   557  			d *= 2
   558  			d /= 2
   559  		}
   560  
   561  		if r2+r3*one64 > 0 {
   562  			d *= 2
   563  			d /= 2
   564  		}
   565  
   566  		if r1-r2*v64 > 0 {
   567  			d *= 2
   568  			d /= 2
   569  		}
   570  
   571  		if r3-r4*v64 <= 0 {
   572  			d *= 2
   573  			d /= 2
   574  		}
   575  
   576  		if r1+11 <= 0 {
   577  			d *= 2
   578  			d /= 2
   579  		}
   580  
   581  		if r1+13 > 0 {
   582  			d *= 2
   583  			d /= 2
   584  		}
   585  
   586  		if r4-17 <= 0 {
   587  			d *= 2
   588  			d /= 2
   589  		}
   590  
   591  		if r4-19 > 0 {
   592  			d *= 2
   593  			d /= 2
   594  		}
   595  	}
   596  	sink = d
   597  }
   598  

View as plain text