1#!/usr/bin/env python2.7 2 3"""A test case update script. 4 5This script is a utility to update LLVM 'llvm-mca' based test cases with new 6FileCheck patterns. 7""" 8 9import argparse 10from collections import defaultdict 11import glob 12import os 13import sys 14import warnings 15 16from UpdateTestChecks import common 17 18 19COMMENT_CHAR = '#' 20ADVERT_PREFIX = '{} NOTE: Assertions have been autogenerated by '.format( 21 COMMENT_CHAR) 22ADVERT = '{}utils/{}'.format(ADVERT_PREFIX, os.path.basename(__file__)) 23 24 25class Error(Exception): 26 """ Generic Error that can be raised without printing a traceback. 27 """ 28 pass 29 30 31def _warn(msg): 32 """ Log a user warning to stderr. 33 """ 34 warnings.warn(msg, Warning, stacklevel=2) 35 36 37def _configure_warnings(args): 38 warnings.resetwarnings() 39 if args.w: 40 warnings.simplefilter('ignore') 41 if args.Werror: 42 warnings.simplefilter('error') 43 44 45def _showwarning(message, category, filename, lineno, file=None, line=None): 46 """ Version of warnings.showwarning that won't attempt to print out the 47 line at the location of the warning if the line text is not explicitly 48 specified. 49 """ 50 if file is None: 51 file = sys.stderr 52 if line is None: 53 line = '' 54 file.write(warnings.formatwarning(message, category, filename, lineno, line)) 55 56 57def _parse_args(): 58 parser = argparse.ArgumentParser(description=__doc__) 59 parser.add_argument('-v', '--verbose', 60 action='store_true', 61 help='show verbose output') 62 parser.add_argument('-w', 63 action='store_true', 64 help='suppress warnings') 65 parser.add_argument('-Werror', 66 action='store_true', 67 help='promote warnings to errors') 68 parser.add_argument('--llvm-mca-binary', 69 metavar='<path>', 70 default='llvm-mca', 71 help='the binary to use to generate the test case ' 72 '(default: llvm-mca)') 73 parser.add_argument('tests', 74 metavar='<test-path>', 75 nargs='+') 76 args = parser.parse_args() 77 78 _configure_warnings(args) 79 80 if not args.llvm_mca_binary: 81 raise Error('--llvm-mca-binary value cannot be empty string') 82 83 if 'llvm-mca' not in os.path.basename(args.llvm_mca_binary): 84 _warn('unexpected binary name: {}'.format(args.llvm_mca_binary)) 85 86 return args 87 88 89def _find_run_lines(input_lines, args): 90 raw_lines = [m.group(1) 91 for m in [common.RUN_LINE_RE.match(l) for l in input_lines] 92 if m] 93 run_lines = [raw_lines[0]] if len(raw_lines) > 0 else [] 94 for l in raw_lines[1:]: 95 if run_lines[-1].endswith(r'\\'): 96 run_lines[-1] = run_lines[-1].rstrip('\\') + ' ' + l 97 else: 98 run_lines.append(l) 99 100 if args.verbose: 101 sys.stderr.write('Found {} RUN line{}:\n'.format( 102 len(run_lines), '' if len(run_lines) == 1 else 's')) 103 for line in run_lines: 104 sys.stderr.write(' RUN: {}\n'.format(line)) 105 106 return run_lines 107 108 109def _get_run_infos(run_lines, args): 110 run_infos = [] 111 for run_line in run_lines: 112 try: 113 (tool_cmd, filecheck_cmd) = tuple([cmd.strip() 114 for cmd in run_line.split('|', 1)]) 115 except ValueError: 116 _warn('could not split tool and filecheck commands: {}'.format(run_line)) 117 continue 118 119 tool_basename = os.path.splitext(os.path.basename(args.llvm_mca_binary))[0] 120 121 if not tool_cmd.startswith(tool_basename + ' '): 122 _warn('skipping non-{} RUN line: {}'.format(tool_basename, run_line)) 123 continue 124 125 if not filecheck_cmd.startswith('FileCheck '): 126 _warn('skipping non-FileCheck RUN line: {}'.format(run_line)) 127 continue 128 129 tool_cmd_args = tool_cmd[len(tool_basename):].strip() 130 tool_cmd_args = tool_cmd_args.replace('< %s', '').replace('%s', '').strip() 131 132 check_prefixes = [item 133 for m in common.CHECK_PREFIX_RE.finditer(filecheck_cmd) 134 for item in m.group(1).split(',')] 135 if not check_prefixes: 136 check_prefixes = ['CHECK'] 137 138 run_infos.append((check_prefixes, tool_cmd_args)) 139 140 return run_infos 141 142 143def _break_down_block(block_info, common_prefix): 144 """ Given a block_info, see if we can analyze it further to let us break it 145 down by prefix per-line rather than per-block. 146 """ 147 texts = block_info.keys() 148 prefixes = list(block_info.values()) 149 # Split the lines from each of the incoming block_texts and zip them so that 150 # each element contains the corresponding lines from each text. E.g. 151 # 152 # block_text_1: A # line 1 153 # B # line 2 154 # 155 # block_text_2: A # line 1 156 # C # line 2 157 # 158 # would become: 159 # 160 # [(A, A), # line 1 161 # (B, C)] # line 2 162 # 163 line_tuples = list(zip(*list((text.splitlines() for text in texts)))) 164 165 # To simplify output, we'll only proceed if the very first line of the block 166 # texts is common to each of them. 167 if len(set(line_tuples[0])) != 1: 168 return [] 169 170 result = [] 171 lresult = defaultdict(list) 172 for i, line in enumerate(line_tuples): 173 if len(set(line)) == 1: 174 # We're about to output a line with the common prefix. This is a sync 175 # point so flush any batched-up lines one prefix at a time to the output 176 # first. 177 for prefix in sorted(lresult): 178 result.extend(lresult[prefix]) 179 lresult = defaultdict(list) 180 181 # The line is common to each block so output with the common prefix. 182 result.append((common_prefix, line[0])) 183 else: 184 # The line is not common to each block, or we don't have a common prefix. 185 # If there are no prefixes available, warn and bail out. 186 if not prefixes[0]: 187 _warn('multiple lines not disambiguated by prefixes:\n{}\n' 188 'Some blocks may be skipped entirely as a result.'.format( 189 '\n'.join(' - {}'.format(l) for l in line))) 190 return [] 191 192 # Iterate through the line from each of the blocks and add the line with 193 # the corresponding prefix to the current batch of results so that we can 194 # later output them per-prefix. 195 for i, l in enumerate(line): 196 for prefix in prefixes[i]: 197 lresult[prefix].append((prefix, l)) 198 199 # Flush any remaining batched-up lines one prefix at a time to the output. 200 for prefix in sorted(lresult): 201 result.extend(lresult[prefix]) 202 return result 203 204 205def _get_useful_prefix_info(run_infos): 206 """ Given the run_infos, calculate any prefixes that are common to every one, 207 and the length of the longest prefix string. 208 """ 209 try: 210 all_sets = [set(s) for s in list(zip(*run_infos))[0]] 211 common_to_all = set.intersection(*all_sets) 212 longest_prefix_len = max(len(p) for p in set.union(*all_sets)) 213 except IndexError: 214 common_to_all = [] 215 longest_prefix_len = 0 216 else: 217 if len(common_to_all) > 1: 218 _warn('Multiple prefixes common to all RUN lines: {}'.format( 219 common_to_all)) 220 if common_to_all: 221 common_to_all = sorted(common_to_all)[0] 222 return common_to_all, longest_prefix_len 223 224 225def _align_matching_blocks(all_blocks, farthest_indexes): 226 """ Some sub-sequences of blocks may be common to multiple lists of blocks, 227 but at different indexes in each one. 228 229 For example, in the following case, A,B,E,F, and H are common to both 230 sets, but only A and B would be identified as such due to the indexes 231 matching: 232 233 index | 0 1 2 3 4 5 6 234 ------+-------------- 235 setA | A B C D E F H 236 setB | A B E F G H 237 238 This function attempts to align the indexes of matching blocks by 239 inserting empty blocks into the block list. With this approach, A, B, E, 240 F, and H would now be able to be identified as matching blocks: 241 242 index | 0 1 2 3 4 5 6 7 243 ------+---------------- 244 setA | A B C D E F H 245 setB | A B E F G H 246 """ 247 248 # "Farthest block analysis": essentially, iterate over all blocks and find 249 # the highest index into a block list for the first instance of each block. 250 # This is relatively expensive, but we're dealing with small numbers of 251 # blocks so it doesn't make a perceivable difference to user time. 252 for blocks in all_blocks.values(): 253 for block in blocks: 254 if not block: 255 continue 256 257 index = blocks.index(block) 258 259 if index > farthest_indexes[block]: 260 farthest_indexes[block] = index 261 262 # Use the results of the above analysis to identify any blocks that can be 263 # shunted along to match the farthest index value. 264 for blocks in all_blocks.values(): 265 for index, block in enumerate(blocks): 266 if not block: 267 continue 268 269 changed = False 270 while(index < farthest_indexes[block]): 271 blocks.insert(index, '') 272 index += 1 273 changed = True 274 275 if changed: 276 # Bail out. We'll need to re-do the farthest block analysis now that 277 # we've inserted some blocks. 278 return True 279 280 return False 281 282 283def _get_block_infos(run_infos, test_path, args, common_prefix): # noqa 284 """ For each run line, run the tool with the specified args and collect the 285 output. We use the concept of 'blocks' for uniquing, where a block is 286 a series of lines of text with no more than one newline character between 287 each one. For example: 288 289 This 290 is 291 one 292 block 293 294 This is 295 another block 296 297 This is yet another block 298 299 We then build up a 'block_infos' structure containing a dict where the 300 text of each block is the key and a list of the sets of prefixes that may 301 generate that particular block. This then goes through a series of 302 transformations to minimise the amount of CHECK lines that need to be 303 written by taking advantage of common prefixes. 304 """ 305 306 def _block_key(tool_args, prefixes): 307 """ Get a hashable key based on the current tool_args and prefixes. 308 """ 309 return ' '.join([tool_args] + prefixes) 310 311 all_blocks = {} 312 max_block_len = 0 313 314 # A cache of the furthest-back position in any block list of the first 315 # instance of each block, indexed by the block itself. 316 farthest_indexes = defaultdict(int) 317 318 # Run the tool for each run line to generate all of the blocks. 319 for prefixes, tool_args in run_infos: 320 key = _block_key(tool_args, prefixes) 321 raw_tool_output = common.invoke_tool(args.llvm_mca_binary, 322 tool_args, 323 test_path) 324 325 # Replace any lines consisting of purely whitespace with empty lines. 326 raw_tool_output = '\n'.join(line if line.strip() else '' 327 for line in raw_tool_output.splitlines()) 328 329 # Split blocks, stripping all trailing whitespace, but keeping preceding 330 # whitespace except for newlines so that columns will line up visually. 331 all_blocks[key] = [b.lstrip('\n').rstrip() 332 for b in raw_tool_output.split('\n\n')] 333 max_block_len = max(max_block_len, len(all_blocks[key])) 334 335 # Attempt to align matching blocks until no more changes can be made. 336 made_changes = True 337 while made_changes: 338 made_changes = _align_matching_blocks(all_blocks, farthest_indexes) 339 340 # If necessary, pad the lists of blocks with empty blocks so that they are 341 # all the same length. 342 for key in all_blocks: 343 len_to_pad = max_block_len - len(all_blocks[key]) 344 all_blocks[key] += [''] * len_to_pad 345 346 # Create the block_infos structure where it is a nested dict in the form of: 347 # block number -> block text -> list of prefix sets 348 block_infos = defaultdict(lambda: defaultdict(list)) 349 for prefixes, tool_args in run_infos: 350 key = _block_key(tool_args, prefixes) 351 for block_num, block_text in enumerate(all_blocks[key]): 352 block_infos[block_num][block_text].append(set(prefixes)) 353 354 # Now go through the block_infos structure and attempt to smartly prune the 355 # number of prefixes per block to the minimal set possible to output. 356 for block_num in range(len(block_infos)): 357 # When there are multiple block texts for a block num, remove any 358 # prefixes that are common to more than one of them. 359 # E.g. [ [{ALL,FOO}] , [{ALL,BAR}] ] -> [ [{FOO}] , [{BAR}] ] 360 all_sets = [s for s in block_infos[block_num].values()] 361 pruned_sets = [] 362 363 for i, setlist in enumerate(all_sets): 364 other_set_values = set([elem for j, setlist2 in enumerate(all_sets) 365 for set_ in setlist2 for elem in set_ 366 if i != j]) 367 pruned_sets.append([s - other_set_values for s in setlist]) 368 369 for i, block_text in enumerate(block_infos[block_num]): 370 371 # When a block text matches multiple sets of prefixes, try removing any 372 # prefixes that aren't common to all of them. 373 # E.g. [ {ALL,FOO} , {ALL,BAR} ] -> [{ALL}] 374 common_values = set.intersection(*pruned_sets[i]) 375 if common_values: 376 pruned_sets[i] = [common_values] 377 378 # Everything should be uniqued as much as possible by now. Apply the 379 # newly pruned sets to the block_infos structure. 380 # If there are any blocks of text that still match multiple prefixes, 381 # output a warning. 382 current_set = set() 383 for s in pruned_sets[i]: 384 s = sorted(list(s)) 385 if s: 386 current_set.add(s[0]) 387 if len(s) > 1: 388 _warn('Multiple prefixes generating same output: {} ' 389 '(discarding {})'.format(','.join(s), ','.join(s[1:]))) 390 391 if block_text and not current_set: 392 raise Error( 393 'block not captured by existing prefixes:\n\n{}'.format(block_text)) 394 block_infos[block_num][block_text] = sorted(list(current_set)) 395 396 # If we have multiple block_texts, try to break them down further to avoid 397 # the case where we have very similar block_texts repeated after each 398 # other. 399 if common_prefix and len(block_infos[block_num]) > 1: 400 # We'll only attempt this if each of the block_texts have the same number 401 # of lines as each other. 402 same_num_Lines = (len(set(len(k.splitlines()) 403 for k in block_infos[block_num].keys())) == 1) 404 if same_num_Lines: 405 breakdown = _break_down_block(block_infos[block_num], common_prefix) 406 if breakdown: 407 block_infos[block_num] = breakdown 408 409 return block_infos 410 411 412def _write_block(output, block, not_prefix_set, common_prefix, prefix_pad): 413 """ Write an individual block, with correct padding on the prefixes. 414 Returns a set of all of the prefixes that it has written. 415 """ 416 end_prefix = ': ' 417 previous_prefix = None 418 num_lines_of_prefix = 0 419 written_prefixes = set() 420 421 for prefix, line in block: 422 if prefix in not_prefix_set: 423 _warn('not writing for prefix {0} due to presence of "{0}-NOT:" ' 424 'in input file.'.format(prefix)) 425 continue 426 427 # If the previous line isn't already blank and we're writing more than one 428 # line for the current prefix output a blank line first, unless either the 429 # current of previous prefix is common to all. 430 num_lines_of_prefix += 1 431 if prefix != previous_prefix: 432 if output and output[-1]: 433 if num_lines_of_prefix > 1 or any(p == common_prefix 434 for p in (prefix, previous_prefix)): 435 output.append('') 436 num_lines_of_prefix = 0 437 previous_prefix = prefix 438 439 written_prefixes.add(prefix) 440 output.append( 441 '{} {}{}{} {}'.format(COMMENT_CHAR, 442 prefix, 443 end_prefix, 444 ' ' * (prefix_pad - len(prefix)), 445 line).rstrip()) 446 end_prefix = '-NEXT:' 447 448 output.append('') 449 return written_prefixes 450 451 452def _write_output(test_path, input_lines, prefix_list, block_infos, # noqa 453 args, common_prefix, prefix_pad): 454 prefix_set = set([prefix for prefixes, _ in prefix_list 455 for prefix in prefixes]) 456 not_prefix_set = set() 457 458 output_lines = [] 459 for input_line in input_lines: 460 if input_line.startswith(ADVERT_PREFIX): 461 continue 462 463 if input_line.startswith(COMMENT_CHAR): 464 m = common.CHECK_RE.match(input_line) 465 try: 466 prefix = m.group(1) 467 except AttributeError: 468 prefix = None 469 470 if '{}-NOT:'.format(prefix) in input_line: 471 not_prefix_set.add(prefix) 472 473 if prefix not in prefix_set or prefix in not_prefix_set: 474 output_lines.append(input_line) 475 continue 476 477 if common.should_add_line_to_output(input_line, prefix_set): 478 # This input line of the function body will go as-is into the output. 479 # Except make leading whitespace uniform: 2 spaces. 480 input_line = common.SCRUB_LEADING_WHITESPACE_RE.sub(r' ', input_line) 481 482 # Skip empty lines if the previous output line is also empty. 483 if input_line or output_lines[-1]: 484 output_lines.append(input_line) 485 else: 486 continue 487 488 # Add a blank line before the new checks if required. 489 if len(output_lines) > 0 and output_lines[-1]: 490 output_lines.append('') 491 492 output_check_lines = [] 493 used_prefixes = set() 494 for block_num in range(len(block_infos)): 495 for block_text in sorted(block_infos[block_num]): 496 if not block_text: 497 continue 498 499 if type(block_infos[block_num]) is list: 500 # The block is of the type output from _break_down_block(). 501 used_prefixes |= _write_block(output_check_lines, 502 block_infos[block_num], 503 not_prefix_set, 504 common_prefix, 505 prefix_pad) 506 break 507 elif block_infos[block_num][block_text]: 508 # _break_down_block() was unable to do do anything so output the block 509 # as-is. 510 lines = block_text.split('\n') 511 for prefix in block_infos[block_num][block_text]: 512 used_prefixes |= _write_block(output_check_lines, 513 [(prefix, line) for line in lines], 514 not_prefix_set, 515 common_prefix, 516 prefix_pad) 517 518 unused_prefixes = (prefix_set - not_prefix_set) - used_prefixes 519 if unused_prefixes: 520 raise Error('unused prefixes: {}'.format(sorted(unused_prefixes))) 521 522 if output_check_lines: 523 output_lines.insert(0, ADVERT) 524 output_lines.extend(output_check_lines) 525 526 # The file should not end with two newlines. It creates unnecessary churn. 527 while len(output_lines) > 0 and output_lines[-1] == '': 528 output_lines.pop() 529 530 if input_lines == output_lines: 531 sys.stderr.write(' [unchanged]\n') 532 return 533 sys.stderr.write(' [{} lines total]\n'.format(len(output_lines))) 534 535 if args.verbose: 536 sys.stderr.write( 537 'Writing {} lines to {}...\n\n'.format(len(output_lines), test_path)) 538 539 with open(test_path, 'wb') as f: 540 f.writelines(['{}\n'.format(l).encode() for l in output_lines]) 541 542def main(): 543 args = _parse_args() 544 test_paths = [test for pattern in args.tests for test in glob.glob(pattern)] 545 for test_path in test_paths: 546 sys.stderr.write('Test: {}\n'.format(test_path)) 547 548 # Call this per test. By default each warning will only be written once 549 # per source location. Reset the warning filter so that now each warning 550 # will be written once per source location per test. 551 _configure_warnings(args) 552 553 if args.verbose: 554 sys.stderr.write( 555 'Scanning for RUN lines in test file: {}\n'.format(test_path)) 556 557 if not os.path.isfile(test_path): 558 raise Error('could not find test file: {}'.format(test_path)) 559 560 with open(test_path) as f: 561 input_lines = [l.rstrip() for l in f] 562 563 run_lines = _find_run_lines(input_lines, args) 564 run_infos = _get_run_infos(run_lines, args) 565 common_prefix, prefix_pad = _get_useful_prefix_info(run_infos) 566 block_infos = _get_block_infos(run_infos, test_path, args, common_prefix) 567 _write_output(test_path, 568 input_lines, 569 run_infos, 570 block_infos, 571 args, 572 common_prefix, 573 prefix_pad) 574 575 return 0 576 577 578if __name__ == '__main__': 579 try: 580 warnings.showwarning = _showwarning 581 sys.exit(main()) 582 except Error as e: 583 sys.stdout.write('error: {}\n'.format(e)) 584 sys.exit(1) 585