Cyclomatic complexity of SASS code

Many algorithms of my SASS optimizer work with code blocks. So I decided to collect some metrics about blocks, resources usage per block/function etc to find outliers (like too short blocks or blocks with anomaly high registers numbers). But before I present the results I should note that building of cyclomatic complexity for SASS is not easy task:

• approximately half of EIATTR attributes are undocumented. And yet, there are some very remarkable ones there - like EIATTR_COROUTINE_RESUME_ID_OFFSETS. Judging by the name they are clearly related to coroutines and so should be taken into account while carving code blocks. Unfortunately, there are no Cubin files in my collection that contain this attribute
• Predicated instructions. Well, this is not SASS-specific problem - for example old 32bit arm had them too. But for example how consider case with several instructions with predicates in the same block? Each of them can modify value of predicate register - then this will be another branch, right? So I just ignore predicates for now
• How to carve code blocks? For my needs, I require maximum-sized blocks to minimize the number of blocks used - so I ignore many cases like BSSY/BSYNC pairs. Sure you can modify my logic of CFG building and make it more similar to classic SSA - see function dg in dg2.pl and the preceding extensive commentary
  

All tests were conducted on libcublas.so.13.7.0.10 from CUDA SDK 13.4 for sm90 cubins, command line options for dg2.pl -gtT:

• -g to build CFG
• -t for registers/predicates tracking
• -T is new option added special to produce various useless metrics 

Count and length of blocks

libcublas.so.13.7.0.74.sm_90.cubin: 28796 total blocks 280570 total instrs avg block len 9.743367 instrs, 2600 back-edges, total 36812 edges 0.070629
150 public syms, avg len 191.973333 blocks

 

libcublas.so.13.7.0.608.sm_90.cubin: 4231 total blocks 176718 total instrs avg block len 41.767431 instrs, 626 back-edges, total 14897 edges 0.042022
380 public syms, avg len 11.134211 blocks

 

libcublas.so.13.7.0.935.sm_90.cubin: 10027 total blocks 124068 total instrs avg block len 12.373392 instrs, 658 back-edges, total 10161 edges 0.064757
184 public syms, avg len 54.494565 blocks

 

Note wide variation in average block length 9.7-41. It is clear that the larger the block size, the higher the chances of finding excessive stall counts. You can also estimate cyclomatic complexity of functions in average having 192 blocks

 

Resources usage per block

This is fairly obvious metric: the average number of unique registers/predicates used in a single block. I account 4 type of resources - general purpose registers, uniform registers, predicates & uniform predicates

libcublas.so.13.7.0.74.sm_90.cubin:

; 179458 regs, avg 6.232046 per block

; 22414 uregs, avg 0.778372 per block

; 25818 preds, avg 0.896583 per block

; 700 upreds, avg 0.024309 per block

libcublas.so.13.7.0.608.sm_90.cubin:

; 46415 regs, avg 10.970220 per block
; 9881 uregs, avg 2.335382 per block
; 6436 preds, avg 1.521153 per block
; 497 upreds, avg 0.117466 per block

 

libcublas.so.13.7.0.935.sm_90.cubin:

; 79716 regs, avg 7.950135 per block
; 8879 uregs, avg 0.885509 per block
; 7386 preds, avg 0.736611 per block
; 401 upreds, avg 0.039992 per block

 

Nothing special - the shorter the average block length, the fewer unique resources it uses

Resources used in single block

After the previous metric, the idea occurred to me to check if there are any resources used in only a single block - and from that moment on, metrics ceased to be a boring, yawn-inducing accounting exercise. It seems that we have a lot of cases like this

;;; Registers used in single block:
;  R1 in 0 end 27F S
;  R54 in 12B0 end 1D6F B
;  R60 in BF0 end 116F B
;  R59 in BF0 end 116F B
;  R57 in BF0 end 116F B
;  R61 in BF0 end 116F B
Here S at end stand for Starting blocks (and B for block having back-edge - loop). Track for R1 typically looks like:
; R1
;   0 mask 8000 <-
; R2
Single write at address 0 and zero reads. Ok, lets look at address 0:
/*0*/ LDC R1,c[0][0x28] ?trans8 ;
; CB 28 stack_ptr
; mask 0 mask2 0
; used regs:
;  R1: 80 write


Needless to note that this specific function does not call other functions - and still waste register to hold stack

Another example:
; R2
;   10 mask 8000 <-
; R3

/*10*/ S2R R2,SR_CTAID.Y &wr=0x0 ?trans1 ;
; mask 0 mask2 0
; used regs:
;  R2: 80 write
As you can guess this function does not use SR_CTAID.Y

It is quite likely there is undocumented ABI and ptxas can't optimize prologue for unused mandatory resources

Gaps in sequentially allocated registers

my hypothesis was that if EIATTR_REGCOUNT for some function was set to for example 32 - then those function should use registers in range R0 .. R31. So I decides to check if this is true.Surprisingly, there are gaps:

; RHoles max 53: R50 R52
; URHoles max 13: UR0 UR1 UR2 UR3 UR11 

Here EIATTR_REGCOUNT has value 54, function used registers up to R53 and UR14. At the same time it never used R50, R52 etc

It seems that registers UR0-UR3 never used - this is again probably undocumented ABI, but why waste 2 general purpose register in middle? I can guess that inside PTXAS there were some optimization passes after register allocation (AllocateRegisters) and they eliminated some instructions. Or it's just bug