几类循环模式的指令集角度观察（2）

[meton-robean]

往期 #31 几类循环模式的指令集角度观察

simple sgemm

这个例子来自论文XLOOP 提供的benchmark

void sgemm_scalar_int( int C[], int A[], int B[], int size )
{

  for ( int mm = 0; mm < size; ++mm  ) {
    for ( int nn = 0; nn < size; ++nn ) {
      int c = 0;
      for ( int i = 0; i < size; ++i ) {
        int a = A[mm + i * size];
        int b = B[nn + i * size];
        c += a * b;
      }
      C[mm+nn*size] = c;
    }
  }

}

000000008000110a <sgemm_scalar_int>:
    8000110a:	06d05363          	blez	a3,80001170 <sgemm_scalar_int+0x66>
    8000110e:	1141                	addi	sp,sp,-16
    80001110:	e422                	sd	s0,8(sp)
    80001112:	82aa                	mv	t0,a0
    80001114:	8336                	mv	t1,a3
    80001116:	8432                	mv	s0,a2
    80001118:	8fae                	mv	t6,a1
    8000111a:	00269513          	slli	a0,a3,0x2
    8000111e:	4381                	li	t2,0
    80001120:	8f22                	mv	t5,s0
    80001122:	8e96                	mv	t4,t0
    80001124:	4e01                	li	t3,0
    80001126:	867a                	mv	a2,t5
    80001128:	86fe                	mv	a3,t6
    8000112a:	4781                	li	a5,0
    8000112c:	4581                	li	a1,0

  **最内层循环的汇编代码------------------------------------
    **8000112e:	4298                lw	a4,0(a3)
    80001130:	00062803          	lw	a6,0(a2)
    80001134:	88be                mv	a7,a5
    80001136:	2785                addiw	a5,a5,1
    80001138:	0307073b          	mulw	a4,a4,a6
    8000113c:	96aa                add	a3,a3,a0
    8000113e:	962a                add	a2,a2,a0
    80001140:	9db9                addw	a1,a1,a4
    80001142:	fef316e3          	bne	t1,a5,8000112e <sgemm_scalar_int+0x24>

** 最内层循环的汇编代码--end----------------------------------

    80001146:	00bea023          	sw	a1,0(t4)
    8000114a:	001e079b          	addiw	a5,t3,1
    8000114e:	9eaa                	add	t4,t4,a0
    80001150:	0f11                	addi	t5,t5,4
    80001152:	011e0463          	beq	t3,a7,8000115a <sgemm_scalar_int+0x50>
    80001156:	8e3e                	mv	t3,a5
    80001158:	b7f9                	j	80001126 <sgemm_scalar_int+0x1c>
    8000115a:	0013879b          	addiw	a5,t2,1


    8000115e:	0f91                	addi	t6,t6,4
    80001160:	0291                	addi	t0,t0,4
    80001162:	01c38463          	beq	t2,t3,8000116a <sgemm_scalar_int+0x60>
    80001166:	83be                	mv	t2,a5
    80001168:	bf65                	j	80001120 <sgemm_scalar_int+0x16>
    8000116a:	6422                	ld	s0,8(sp)


    8000116c:	0141                	addi	sp,sp,16
    8000116e:	8082                	ret
    80001170:	8082                	ret

[meton-robean]

dynamic programing (这个例子来自 xloop 的dynprog)

 __attribute__((noinline))
  void dynprog_scalar_longlong( int length, long long *c, long long *W, long long *out )
  {

    int out_l = 0;
    int i, j, k;
    for (i = 0; i < length - 1; i++)
    {
      
      for (j = i + 1; j < length; j++)
      {

        int s = 0;

        asm volatile ("fence");
        for (k = i + 1; k < j; k++)
          s += c[i * length + k] + c[k * length + j];
        asm volatile ("fence" ::: "memory");

        c[i * length + j] = s + W[i * length + j];
        

      }
      
      out_l += c[length - 1];
    }

    *out = out_l;
  }

000000008000115e <dynprog_scalar_longlong>:
    8000115e:	7159                	addi	sp,sp,-112
    80001160:	f4a2                	sd	s0,104(sp)
    80001162:	f0a6                	sd	s1,96(sp)
    80001164:	ecca                	sd	s2,88(sp)
    80001166:	e8ce                	sd	s3,80(sp)
    80001168:	e4d2                	sd	s4,72(sp)
    8000116a:	e0d6                	sd	s5,64(sp)
    8000116c:	fc5a                	sd	s6,56(sp)
    8000116e:	f85e                	sd	s7,48(sp)
    80001170:	f462                	sd	s8,40(sp)
    80001172:	f066                	sd	s9,32(sp)
    80001174:	ec6a                	sd	s10,24(sp)
    80001176:	e86e                	sd	s11,16(sp)
    80001178:	4785                	li	a5,1
    8000117a:	e436                	sd	a3,8(sp)
    8000117c:	0ea7de63          	bge	a5,a0,80001278 <dynprog_scalar_longlong+0x11a>
    80001180:	00351813          	slli	a6,a0,0x3
    80001184:	ff880d93          	addi	s11,a6,-8
    80001188:	00050d1b          	sext.w	s10,a0
    8000118c:	9f89                	subw	a5,a5,a0
    8000118e:	8f2a                	mv	t5,a0
    80001190:	8fae                	mv	t6,a1
    80001192:	83b2                	mv	t2,a2
    80001194:	9dae                	add	s11,s11,a1
    80001196:	e03e                	sd	a5,0(sp)
    80001198:	8c6a                	mv	s8,s10
    8000119a:	4b01                	li	s6,0
    8000119c:	4a85                	li	s5,1
    8000119e:	4a01                	li	s4,0
    800011a0:	4b81                	li	s7,0
    800011a2:	4c81                	li	s9,0
    800011a4:	01058993          	addi	s3,a1,16
    800011a8:	000a889b          	sext.w	a7,s5
    800011ac:	82c6                	mv	t0,a7
    800011ae:	09e8d663          	bge	a7,t5,8000123a <dynprog_scalar_longlong+0xdc>
    800011b2:	015a0333          	add	t1,s4,s5
    800011b6:	030e                	slli	t1,t1,0x3
    800011b8:	414c0eb3          	sub	t4,s8,s4
    800011bc:	006f8e33          	add	t3,t6,t1
    800011c0:	0e8e                	slli	t4,t4,0x3
    800011c2:	8972                	mv	s2,t3
    800011c4:	9efe                	add	t4,t4,t6
    800011c6:	ffeb049b          	addiw	s1,s6,-2
    800011ca:	017a0433          	add	s0,s4,s7
    800011ce:	0ff0000f          	fence

    800011d2:	0512d763          	bge	t0,a7,80001220 <dynprog_scalar_longlong+0xc2>
    800011d6:	0114853b          	addw	a0,s1,a7
    800011da:	1502                	slli	a0,a0,0x20
    800011dc:	9101                	srli	a0,a0,0x20
    800011de:	9522                	add	a0,a0,s0
    800011e0:	050e                	slli	a0,a0,0x3
    800011e2:	01d306b3          	add	a3,t1,t4
    800011e6:	954e                	add	a0,a0,s3
    800011e8:	87ca                	mv	a5,s2
    800011ea:	4601                	li	a2,
    
    ## 最内层循环 ------------------------------------------
    800011ec:	6398                	ld	a4,0(a5)
    800011ee:	628c                	ld	a1,0(a3)
    800011f0:	07a1                	addi	a5,a5,8
    800011f2:	96c2                	add	a3,a3,a6
    800011f4:	9f2d                	addw	a4,a4,a1
    800011f6:	9e39                	addw	a2,a2,a4
    800011f8:	fef51ae3          	bne	a0,a5,800011ec <dynprog_scalar_longlong+0x8e>
    ## 最内层循环 end----------------------------------------
    800011fc:	0ff0000f          	fence


    80001200:	006387b3          	add	a5,t2,t1
    80001204:	639c                	ld	a5,0(a5)
    80001206:	2885                	addiw	a7,a7,1
    80001208:	0321                	addi	t1,t1,8
    8000120a:	963e                	add	a2,a2,a5
    8000120c:	00ce3023          	sd	a2,0(t3)
    80001210:	031f0563          	beq	t5,a7,8000123a <dynprog_scalar_longlong+0xdc>
    80001214:	006f8e33          	add	t3,t6,t1
    80001218:	0ff0000f          	fence
    8000121c:	fb12cde3          	blt	t0,a7,800011d6 <dynprog_scalar_longlong+0x78>
    80001220:	4601                	li	a2,0
    80001222:	0ff0000f          	fence
    80001226:	006387b3          	add	a5,t2,t1
    8000122a:	639c                	ld	a5,0(a5)
    8000122c:	2885                	addiw	a7,a7,1
    8000122e:	0321                	addi	t1,t1,8
    80001230:	963e                	add	a2,a2,a5
    80001232:	00ce3023          	sd	a2,0(t3)
    80001236:	fd1f1fe3          	bne	t5,a7,80001214 <dynprog_scalar_longlong+0xb6>
    8000123a:	000db783          	ld	a5,0(s11)
    8000123e:	3b7d                	addiw	s6,s6,-1
    80001240:	0b85                	addi	s7,s7,1
    80001242:	01978cbb          	addw	s9,a5,s9
    80001246:	6782                	ld	a5,0(sp)
    80001248:	01aa0a3b          	addw	s4,s4,s10
    8000124c:	0a85                	addi	s5,s5,1
    8000124e:	018d0c3b          	addw	s8,s10,s8
    80001252:	f4fb1be3          	bne	s6,a5,800011a8 <dynprog_scalar_longlong+0x4a>
    80001256:	67a2                	ld	a5,8(sp)
    80001258:	7426                	ld	s0,104(sp)
    8000125a:	7486                	ld	s1,96(sp)
    8000125c:	0197b023          	sd	s9,0(a5)
    80001260:	6966                	ld	s2,88(sp)
    80001262:	69c6                	ld	s3,80(sp)
    80001264:	6a26                	ld	s4,72(sp)
    80001266:	6a86                	ld	s5,64(sp)
    80001268:	7b62                	ld	s6,56(sp)
    8000126a:	7bc2                	ld	s7,48(sp)
    8000126c:	7c22                	ld	s8,40(sp)
    8000126e:	7c82                	ld	s9,32(sp)
    80001270:	6d62                	ld	s10,24(sp)
    80001272:	6dc2                	ld	s11,16(sp)
    80001274:	6165                	addi	sp,sp,112
    80001276:	8082                	ret
    80001278:	4c81                	li	s9,0
    8000127a:	bff1                	j	80001256 <dynprog_scalar_longlong+0xf8>

[meton-robean]

warshall computing 例子来自xloop的benchmark

  __attribute__((noinline))
  void warshall_scalar( int n, float *path, float *path_in )
  {
    int i, j, k;

    // initially copy the input path to path
    memcpy( path, path_in, sizeof(float) * n * n );

    for (k = 0; k < n; k++)
    {
      for (i = 0; i < n; i++)
        asm volatile ("fence");  //最内层循环中有条件判断
        for (j = 0; j < n; j++)
          path[i*n+j] = path[i*n+j] < path[i*n+k] + path[k*n+j] ?
                        path[i*n+j] : path[i*n+k] + path[k*n+j];
        asm volatile ("fence" ::: "memory");
        
    }
  }

    80001098:	0ff0000f          	fence
    8000109c:	86be                	mv	a3,a5
    8000109e:	2785                	addiw	a5,a5,1
    800010a0:	fef41ce3          	bne	s0,a5,80001098 <warshall_scalar+0x50>
    800010a4:	879a                	mv	a5,t1


    800010a6:	00b78733          	add	a4,a5,a1
    800010aa:	9742                	add	a4,a4,a6
    800010ac:	00072787          	flw	fa5,0(a4)
    800010b0:	00062687          	flw	fa3,0(a2)
    800010b4:	0007a707          	flw	fa4,0(a5)
    800010b8:	00d7f7d3          	fadd.s	fa5,fa5,fa3
    800010bc:	a0f71753          	flt.s	a4,fa4,fa5
    800010c0:	e319                	bnez	a4,800010c6 <warshall_scalar+0x7e>

    800010c2:	20f78753          	fmv.s	fa4,fa5
    800010c6:	0791                	addi	a5,a5,4


    800010c8:	fee7ae27          	fsw	fa4,-4(a5)
    800010cc:	fcf51de3          	bne	a0,a5,800010a6 <warshall_scalar+0x5e>
    800010d0:	0ff0000f          	fence