utilities/softpipe/softpipe

   1 #!/usr/bin/python3
   2 #
   3 #  Copyright (c) 2020 Peter Hsu.  All Rights Reserved.  See LICENCE file for details.
   4 #
   5 #  Algorithm from https://apps.dtic.mil/dtic/tr/fulltext/u2/a163195.pdf
   6 #    Peter Yan-Tek Hsu, "Highly Concurrent Scalar Processing,"
   7 #    PhD Dissertation, University of Illinois at Urbana-Champaign, 1986
   8 #
   9 #  Usage:  softpipe < loop.def > prog.h
  10 #
  11 #  See vnv_spmv.def, vnv_spmv.h and ComputeSPVM.cpp for example usage
  12 #
  13
  14 import sys
  15 import re
  16
  17 SpecPattern = re.compile(r'^\s*([0-9]+)\s+(.*)')
  18 IterPattern = re.compile(r'^\?iter=(\w+)')
  19 LimitPattern = re.compile(r'^\?limit=(\w+)')
  20 VarPattern = re.compile(r'^(.+)([a-zA-Z_][a-zA-Z_0-9]*)\$')
  21 CmdPattern = re.compile(r'^\?([a-z]+)=([a-zA-Z_][a-zA-Z_0-9]*)')
  22
  23 lines = []
  24 for l in sys.stdin:
  25     lines.insert(0, l.rstrip('\r\n'))
  26
  27 lv = 'NONE'
  28 limit = 'NONE'
  29 pipe = {}
  30 depth = 0
  31
  32 vectors = []
  33 perm = []
  34
  35 def error(line):
  36     sys.stderr.write('Unrecognized line:\n')
  37     sys.stderr.write(line+'\n')
  38     exit(1)
  39
  40
  41 def PrintPipe(body):
  42     for stage in range(depth):
  43         stmt = '      Stage("{:2d}:")  '.format(stage)
  44         stmts = body[stage]
  45         for a in stmts:
  46             stmt += '  '+a
  47         print(stmt)
  48
  49 def Substitute(src, dollar, at):
  50     if at == 0:
  51         at = str(dollar)
  52     else:
  53         at = str(dollar) + str(at)
  54     dst = []
  55     for e in src:
  56         f = e.replace('$', str(dollar))
  57         f = f.replace('@', at)
  58         dst.append(f)
  59     return dst
  60
  61
  62 def GenEpilog(n):
  63     epi = [ None ]*2*depth
  64     for j in range(2*depth):
  65         epi[j] = {}
  66     for j in range(depth):
  67         for i in perm[j]:
  68             at = -depth
  69             if (i+j)%depth >= j:
  70                 at = 0
  71             for stmt in Substitute(pipe[j], i, at):
  72                 stage = (i+j) % depth
  73                 if stmt not in epi[stage] and not (i>=n and i+j<depth):
  74                     epi[stage][stmt] = 1
  75                 if stmt not in epi[stage+depth] and not (i>=n or i+j<depth):
  76                     epi[stage+depth][stmt] = 1
  77     return epi
  78
  79
  80 def GenProlog(n, depth):
  81     pro = [ None ]*2*depth
  82     for j in range(2*depth):
  83         pro[j] = {}
  84     for j in range(depth):
  85         for i in perm[j]:
  86             at = -depth
  87             if (i+j)%depth >= j:
  88                 at = 0
  89             for stmt in Substitute(pipe[j], i, 0):
  90                 stage = (i+j) % depth
  91                 if stmt not in pro[stage] and not (i>n or i+j>=depth):
  92                     pro[stage][stmt] = 1
  93                 if stmt not in pro[stage+depth] and not (i>n or i+j<depth):
  94                     pro[stage+depth][stmt] = 1
  95     return pro
  96
  97
  98 def GenerateSoftwarePipeline():
  99     # Generate vector variable declarations
 100     for (var, decl) in vectors:
 101         vec = []
 102         for i in range(depth):
 103             vec.append(var+str(i))
 104         comma = ', '
 105         decl += comma.join(vec)
 106         print(decl+';')
 107
 108     print('  if ({:s} < {:d}) {{  /* Single Pass */'.format(limit, depth))
 109     # Generate special short tripcount cases
 110     #   stmt[stage] = {} (key=statement, value=lowest remaining case to execute)
 111     #     stage  = software pipeline stage, 0..2*depth-1
 112     stmt = [ None ]*2*depth
 113     for trips in range(depth-1):
 114         pro = GenProlog(trips, depth)
 115         for stage in range(2*depth):
 116             for s in pro[stage].keys():
 117                 if stmt[stage] == None:
 118                     stmt[stage] = {}
 119                 if s not in stmt[stage]:
 120                     stmt[stage][s] = trips
 121                 elif stmt[stage][s] > trips:
 122                     stmt[stage][s] = trips
 123     for stage in range(2*depth):
 124         if stmt[stage] != None:
 125             buckets = {}
 126             always = []
 127             for a in stmt[stage].keys():
 128                 r = stmt[stage][a]
 129 #                if r == 0:
 130 #                    always.append(a)
 131 #                    continue
 132                 if r not in buckets:
 133                     buckets[r] = []
 134                 buckets[r].append(a)
 135             ifstmt = ''
 136             for a in always:
 137                 ifstmt += a+'  '
 138             for r in reversed(sorted(buckets.keys())):
 139                 ifstmt += 'if ({:s}>{:d}) {{'.format(limit, r)
 140                 for a in buckets[r]:
 141                     ifstmt += '  '+a
 142                 ifstmt += ' }  '
 143             if ifstmt != '':
 144                 ifstmt = '      Stage("{:2d}:")  '.format(stage) + ifstmt
 145                 print(ifstmt)
 146     print('  }')
 147     print('  else {')
 148
 149     # Generate pipeline prologue
 150     stages = [ None ]*depth
 151     for j in range(depth):
 152         stages[j] = []
 153     for j in range(depth):
 154         for i in perm[j]:
 155             if (i+j)%depth < i:
 156                 continue
 157             stages[(i+j)%depth] += Substitute(pipe[j], i, 0)
 158     print('    { /* Prologue */')
 159     PrintPipe(stages)
 160     print('    }')
 161
 162     # Generate pipeline body
 163     stages = [ None ]*depth
 164     for j in range(depth):
 165         stages[j] = []
 166     for j in range(depth):
 167         for i in perm[j]:
 168             at = -depth
 169             if (i+j)%depth >= j:
 170                 at = 0
 171             stages[(i+j)%depth] += Substitute(pipe[j], i, at)
 172     print('    /*   Body */')
 173     print('    for ({:s}+={:d}; {:s}+{:d}<={:s}; {:s}+={:d}) {{'.format(lv, depth, lv, depth, limit, lv, depth))
 174     PrintPipe(stages)
 175     print('    }')
 176
 177     # Generate pipeline epilogue
 178     #   stmt[stage] = {} (key=statement, value=highest remaining case to execute)
 179     #     stage  = software pipeline stage, 0..2*depth-1
 180     print('    { /* Epilogue */')
 181     stmt = [ None ]*2*depth
 182     for remaining in range(depth-1, -1, -1):
 183         epi = GenEpilog(remaining)
 184         for stage in range(2*depth):
 185             for s in epi[stage].keys():
 186                 if stmt[stage] == None:
 187                     stmt[stage] = {}
 188                 if s not in stmt[stage]:
 189                     stmt[stage][s] = remaining
 190                 elif stmt[stage][s] > remaining:
 191                     stmt[stage][s] = remaining
 192     for stage in range(2*depth):
 193         if stmt[stage] != None:
 194             buckets = {}
 195             always = []
 196             for a in stmt[stage].keys():
 197                 r = stmt[stage][a]
 198                 if r == 0:
 199                     always.append(a)
 200                     continue
 201                 if r not in buckets:
 202                     buckets[r] = []
 203                 buckets[r].append(a)
 204             ifstmt = ''
 205             for a in always:
 206                 ifstmt += a+'  '
 207             for r in reversed(sorted(buckets.keys())):
 208                 ifstmt += 'if ({:s}-{:s}>{:d}) {{'.format(limit, lv, r-1)
 209                 for a in buckets[r]:
 210                     ifstmt += '  '+a
 211                 ifstmt += ' }  '
 212             if ifstmt != '':
 213                 ifstmt = '      Stage("{:2d}:")  '.format(stage) + ifstmt
 214                 print(ifstmt)
 215     print('    }')
 216     print('  }')
 217
 218
 219
 220
 221 while lines:
 222     line = lines.pop()
 223     if line != '' and line[0] != '?':
 224         print(line)
 225     elif line == '?{':
 226         line = lines.pop()
 227         while line != '?}':
 228             m = VarPattern.match(line)
 229             if not m:
 230                 error(line)
 231             (declaration, variable) = m.groups()
 232             vectors.append( (variable, declaration) )
 233             line = lines.pop()
 234     elif line == '?[':
 235         line = lines.pop()
 236         while line != '?]':
 237             m = SpecPattern.match(line)
 238             if not m:
 239                 error(line)
 240             (stage, statement) = m.groups()
 241             stage = int(stage)
 242             statement = statement.lstrip()
 243             statement = statement.rstrip()
 244             if stage not in pipe:
 245                 pipe[stage] = []
 246             pipe[stage].append(statement)
 247             line = lines.pop()
 248         if stage > depth:
 249             depth = stage
 250         depth += 1
 251
 252         # Generate permutation table
 253         perm = [None]*depth
 254         for i in range(depth):
 255             perm[i] = list(range(i, depth)) + list(range(0, i))
 256
 257         for i in range(depth):
 258             if not i in pipe:
 259                 pipe[i] = []
 260         GenerateSoftwarePipeline()
 261
 262     else:
 263         m = CmdPattern.match(line)
 264         if m:
 265             cmd, value = m.groups()
 266             if cmd == 'limit':
 267                 limit = value
 268             elif cmd == 'iter':
 269                 lv = value
 270             else:
 271                 error(line)
 272         else:
 273             print(line)
 274
 275
 276
 277
 278
 279