590 lines · python
1#!/usr/bin/env python32 3"""A test case update script.4 5This script is a utility to update LLVM 'llvm-mca' based test cases with new6FileCheck patterns.7"""8 9from sys import stderr10from traceback import print_exc11import argparse12from collections import defaultdict13import glob14import os15import sys16import warnings17 18from UpdateTestChecks import common19 20 21COMMENT_CHAR = "#"22ADVERT_PREFIX = "{} NOTE: Assertions have been autogenerated by ".format(COMMENT_CHAR)23ADVERT = "{}utils/{}".format(ADVERT_PREFIX, os.path.basename(__file__))24 25 26class Error(Exception):27 """Generic Error that can be raised without printing a traceback."""28 29 pass30 31 32def _warn(msg):33 """Log a user warning to stderr."""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 the47 line at the location of the warning if the line text is not explicitly48 specified.49 """50 if file is None:51 file = sys.stderr52 if line is None:53 line = ""54 file.write(warnings.formatwarning(message, category, filename, lineno, line))55 56 57def _get_parser():58 parser = argparse.ArgumentParser(description=__doc__)59 parser.add_argument("-w", action="store_true", help="suppress warnings")60 parser.add_argument(61 "-Werror", action="store_true", help="promote warnings to errors"62 )63 parser.add_argument(64 "--llvm-mca-binary",65 metavar="<path>",66 default="llvm-mca",67 help="the binary to use to generate the test case " "(default: llvm-mca)",68 )69 parser.add_argument("tests", metavar="<test-path>", nargs="+")70 return parser71 72def _get_run_infos(run_lines, args):73 run_infos = []74 for run_line in run_lines:75 try:76 (tool_cmd, filecheck_cmd) = tuple(77 [cmd.strip() for cmd in run_line.split("|", 1)]78 )79 except ValueError:80 _warn("could not split tool and filecheck commands: {}".format(run_line))81 continue82 83 common.verify_filecheck_prefixes(filecheck_cmd)84 tool_basename = os.path.splitext(os.path.basename(args.llvm_mca_binary))[0]85 86 if not tool_cmd.startswith(tool_basename + " "):87 _warn("skipping non-{} RUN line: {}".format(tool_basename, run_line))88 continue89 90 if not filecheck_cmd.startswith("FileCheck "):91 _warn("skipping non-FileCheck RUN line: {}".format(run_line))92 continue93 94 tool_cmd_args = tool_cmd[len(tool_basename) :].strip()95 tool_cmd_args = tool_cmd_args.replace("< %s", "").replace("%s", "").strip()96 97 check_prefixes = common.get_check_prefixes(filecheck_cmd)98 99 run_infos.append((check_prefixes, tool_cmd_args))100 101 return run_infos102 103 104def _break_down_block(block_info, common_prefix):105 """Given a block_info, see if we can analyze it further to let us break it106 down by prefix per-line rather than per-block.107 """108 texts = block_info.keys()109 prefixes = list(block_info.values())110 # Split the lines from each of the incoming block_texts and zip them so that111 # each element contains the corresponding lines from each text. E.g.112 #113 # block_text_1: A # line 1114 # B # line 2115 #116 # block_text_2: A # line 1117 # C # line 2118 #119 # would become:120 #121 # [(A, A), # line 1122 # (B, C)] # line 2123 #124 line_tuples = list(zip(*list((text.splitlines() for text in texts))))125 126 # To simplify output, we'll only proceed if the very first line of the block127 # texts is common to each of them.128 if len(set(line_tuples[0])) != 1:129 return []130 131 result = []132 lresult = defaultdict(list)133 for i, line in enumerate(line_tuples):134 if len(set(line)) == 1:135 # We're about to output a line with the common prefix. This is a sync136 # point so flush any batched-up lines one prefix at a time to the output137 # first.138 for prefix in sorted(lresult):139 result.extend(lresult[prefix])140 lresult = defaultdict(list)141 142 # The line is common to each block so output with the common prefix.143 result.append((common_prefix, line[0]))144 else:145 # The line is not common to each block, or we don't have a common prefix.146 # If there are no prefixes available, warn and bail out.147 if not prefixes[0]:148 _warn(149 "multiple lines not disambiguated by prefixes:\n{}\n"150 "Some blocks may be skipped entirely as a result.".format(151 "\n".join(" - {}".format(l) for l in line)152 )153 )154 return []155 156 # Iterate through the line from each of the blocks and add the line with157 # the corresponding prefix to the current batch of results so that we can158 # later output them per-prefix.159 for i, l in enumerate(line):160 for prefix in prefixes[i]:161 lresult[prefix].append((prefix, l))162 163 # Flush any remaining batched-up lines one prefix at a time to the output.164 for prefix in sorted(lresult):165 result.extend(lresult[prefix])166 return result167 168 169def _get_useful_prefix_info(run_infos):170 """Given the run_infos, calculate any prefixes that are common to every one,171 and the length of the longest prefix string.172 """173 try:174 all_sets = [set(s) for s in list(zip(*run_infos))[0]]175 common_to_all = set.intersection(*all_sets)176 longest_prefix_len = max(len(p) for p in set.union(*all_sets))177 except IndexError:178 common_to_all = []179 longest_prefix_len = 0180 else:181 if len(common_to_all) > 1:182 _warn("Multiple prefixes common to all RUN lines: {}".format(common_to_all))183 if common_to_all:184 common_to_all = sorted(common_to_all)[0]185 return common_to_all, longest_prefix_len186 187 188def _align_matching_blocks(all_blocks, farthest_indexes):189 """Some sub-sequences of blocks may be common to multiple lists of blocks,190 but at different indexes in each one.191 192 For example, in the following case, A,B,E,F, and H are common to both193 sets, but only A and B would be identified as such due to the indexes194 matching:195 196 index | 0 1 2 3 4 5 6197 ------+--------------198 setA | A B C D E F H199 setB | A B E F G H200 201 This function attempts to align the indexes of matching blocks by202 inserting empty blocks into the block list. With this approach, A, B, E,203 F, and H would now be able to be identified as matching blocks:204 205 index | 0 1 2 3 4 5 6 7206 ------+----------------207 setA | A B C D E F H208 setB | A B E F G H209 """210 211 # "Farthest block analysis": essentially, iterate over all blocks and find212 # the highest index into a block list for the first instance of each block.213 # This is relatively expensive, but we're dealing with small numbers of214 # blocks so it doesn't make a perceivable difference to user time.215 for blocks in all_blocks.values():216 for block in blocks:217 if not block:218 continue219 220 index = blocks.index(block)221 222 if index > farthest_indexes[block]:223 farthest_indexes[block] = index224 225 # Use the results of the above analysis to identify any blocks that can be226 # shunted along to match the farthest index value.227 for blocks in all_blocks.values():228 for index, block in enumerate(blocks):229 if not block:230 continue231 232 changed = False233 # If the block has not already been subject to alignment (i.e. if the234 # previous block is not empty) then insert empty blocks until the index235 # matches the farthest index identified for that block.236 if (index > 0) and blocks[index - 1]:237 while index < farthest_indexes[block]:238 blocks.insert(index, "")239 index += 1240 changed = True241 242 if changed:243 # Bail out. We'll need to re-do the farthest block analysis now that244 # we've inserted some blocks.245 return True246 247 return False248 249 250def _get_block_infos(run_infos, test_path, args, common_prefix): # noqa251 """For each run line, run the tool with the specified args and collect the252 output. We use the concept of 'blocks' for uniquing, where a block is253 a series of lines of text with no more than one newline character between254 each one. For example:255 256 This257 is258 one259 block260 261 This is262 another block263 264 This is yet another block265 266 We then build up a 'block_infos' structure containing a dict where the267 text of each block is the key and a list of the sets of prefixes that may268 generate that particular block. This then goes through a series of269 transformations to minimise the amount of CHECK lines that need to be270 written by taking advantage of common prefixes.271 """272 273 def _block_key(tool_args, prefixes):274 """Get a hashable key based on the current tool_args and prefixes."""275 return " ".join([tool_args] + prefixes)276 277 all_blocks = {}278 max_block_len = 0279 280 # A cache of the furthest-back position in any block list of the first281 # instance of each block, indexed by the block itself.282 farthest_indexes = defaultdict(int)283 284 # Run the tool for each run line to generate all of the blocks.285 for prefixes, tool_args in run_infos:286 key = _block_key(tool_args, prefixes)287 raw_tool_output = common.invoke_tool(args.llvm_mca_binary, tool_args, test_path)288 289 # Replace any lines consisting of purely whitespace with empty lines.290 raw_tool_output = "\n".join(291 line if line.strip() else "" for line in raw_tool_output.splitlines()292 )293 294 # Split blocks, stripping all trailing whitespace, but keeping preceding295 # whitespace except for newlines so that columns will line up visually.296 all_blocks[key] = [297 b.lstrip("\n").rstrip() for b in raw_tool_output.split("\n\n")298 ]299 max_block_len = max(max_block_len, len(all_blocks[key]))300 301 # Attempt to align matching blocks until no more changes can be made.302 made_changes = True303 while made_changes:304 made_changes = _align_matching_blocks(all_blocks, farthest_indexes)305 306 # If necessary, pad the lists of blocks with empty blocks so that they are307 # all the same length.308 for key in all_blocks:309 len_to_pad = max_block_len - len(all_blocks[key])310 all_blocks[key] += [""] * len_to_pad311 312 # Create the block_infos structure where it is a nested dict in the form of:313 # block number -> block text -> list of prefix sets314 block_infos = defaultdict(lambda: defaultdict(list))315 for prefixes, tool_args in run_infos:316 key = _block_key(tool_args, prefixes)317 for block_num, block_text in enumerate(all_blocks[key]):318 block_infos[block_num][block_text].append(set(prefixes))319 320 # Now go through the block_infos structure and attempt to smartly prune the321 # number of prefixes per block to the minimal set possible to output.322 for block_num in range(len(block_infos)):323 # When there are multiple block texts for a block num, remove any324 # prefixes that are common to more than one of them.325 # E.g. [ [{ALL,FOO}] , [{ALL,BAR}] ] -> [ [{FOO}] , [{BAR}] ]326 all_sets = [s for s in block_infos[block_num].values()]327 pruned_sets = []328 329 for i, setlist in enumerate(all_sets):330 other_set_values = set(331 [332 elem333 for j, setlist2 in enumerate(all_sets)334 for set_ in setlist2335 for elem in set_336 if i != j337 ]338 )339 pruned_sets.append([s - other_set_values for s in setlist])340 341 for i, block_text in enumerate(block_infos[block_num]):342 343 # When a block text matches multiple sets of prefixes, try removing any344 # prefixes that aren't common to all of them.345 # E.g. [ {ALL,FOO} , {ALL,BAR} ] -> [{ALL}]346 common_values = set.intersection(*pruned_sets[i])347 if common_values:348 pruned_sets[i] = [common_values]349 350 # Everything should be uniqued as much as possible by now. Apply the351 # newly pruned sets to the block_infos structure.352 # If there are any blocks of text that still match multiple prefixes,353 # output a warning.354 current_set = set()355 for s in pruned_sets[i]:356 s = sorted(list(s))357 if s:358 current_set.add(s[0])359 if len(s) > 1:360 _warn(361 "Multiple prefixes generating same output: {} "362 "(discarding {})".format(",".join(s), ",".join(s[1:]))363 )364 365 if block_text and not current_set:366 raise Error(367 "block not captured by existing prefixes:\n\n{}".format(block_text)368 )369 block_infos[block_num][block_text] = sorted(list(current_set))370 371 # If we have multiple block_texts, try to break them down further to avoid372 # the case where we have very similar block_texts repeated after each373 # other.374 if common_prefix and len(block_infos[block_num]) > 1:375 # We'll only attempt this if each of the block_texts have the same number376 # of lines as each other.377 same_num_Lines = (378 len(set(len(k.splitlines()) for k in block_infos[block_num].keys()))379 == 1380 )381 if same_num_Lines:382 breakdown = _break_down_block(block_infos[block_num], common_prefix)383 if breakdown:384 block_infos[block_num] = breakdown385 386 return block_infos387 388 389def _write_block(output, block, not_prefix_set, common_prefix, prefix_pad):390 """Write an individual block, with correct padding on the prefixes.391 Returns a set of all of the prefixes that it has written.392 """393 end_prefix = ": "394 previous_prefix = None395 num_lines_of_prefix = 0396 written_prefixes = set()397 398 for prefix, line in block:399 if prefix in not_prefix_set:400 _warn(401 'not writing for prefix {0} due to presence of "{0}-NOT:" '402 "in input file.".format(prefix)403 )404 continue405 406 # If the previous line isn't already blank and we're writing more than one407 # line for the current prefix output a blank line first, unless either the408 # current of previous prefix is common to all.409 num_lines_of_prefix += 1410 if prefix != previous_prefix:411 if output and output[-1]:412 if num_lines_of_prefix > 1 or any(413 p == common_prefix for p in (prefix, previous_prefix)414 ):415 output.append("")416 num_lines_of_prefix = 0417 previous_prefix = prefix418 419 written_prefixes.add(prefix)420 output.append(421 "{} {}{}{} {}".format(422 COMMENT_CHAR, prefix, end_prefix, " " * (prefix_pad - len(prefix)), line423 ).rstrip()424 )425 end_prefix = "-NEXT:"426 427 output.append("")428 return written_prefixes429 430 431def _write_output(432 test_path,433 input_lines,434 prefix_list,435 block_infos, # noqa436 args,437 common_prefix,438 prefix_pad,439):440 prefix_set = set([prefix for prefixes, _ in prefix_list for prefix in prefixes])441 not_prefix_set = set()442 443 output_lines = []444 for input_line in input_lines:445 if input_line.startswith(ADVERT_PREFIX):446 continue447 448 if input_line.startswith(COMMENT_CHAR):449 m = common.CHECK_RE.match(input_line)450 try:451 prefix = m.group(1)452 except AttributeError:453 prefix = None454 455 if "{}-NOT:".format(prefix) in input_line:456 not_prefix_set.add(prefix)457 458 if prefix not in prefix_set or prefix in not_prefix_set:459 output_lines.append(input_line)460 continue461 462 if common.should_add_line_to_output(input_line, prefix_set):463 # This input line of the function body will go as-is into the output.464 # Except make leading whitespace uniform: 2 spaces.465 input_line = common.SCRUB_LEADING_WHITESPACE_RE.sub(r" ", input_line)466 467 # Skip empty lines if the previous output line is also empty.468 if input_line or output_lines[-1]:469 output_lines.append(input_line)470 else:471 continue472 473 # Add a blank line before the new checks if required.474 if len(output_lines) > 0 and output_lines[-1]:475 output_lines.append("")476 477 output_check_lines = []478 used_prefixes = set()479 for block_num in range(len(block_infos)):480 if type(block_infos[block_num]) is list:481 # The block is of the type output from _break_down_block().482 used_prefixes |= _write_block(483 output_check_lines,484 block_infos[block_num],485 not_prefix_set,486 common_prefix,487 prefix_pad,488 )489 else:490 # _break_down_block() was unable to do do anything so output the block491 # as-is.492 493 # Rather than writing out each block as soon we encounter it, save it494 # indexed by prefix so that we can write all of the blocks out sorted by495 # prefix at the end.496 output_blocks = defaultdict(list)497 498 for block_text in sorted(block_infos[block_num]):499 500 if not block_text:501 continue502 503 lines = block_text.split("\n")504 for prefix in block_infos[block_num][block_text]:505 assert prefix not in output_blocks506 used_prefixes |= _write_block(507 output_blocks[prefix],508 [(prefix, line) for line in lines],509 not_prefix_set,510 common_prefix,511 prefix_pad,512 )513 514 for prefix in sorted(output_blocks):515 output_check_lines.extend(output_blocks[prefix])516 517 unused_prefixes = (prefix_set - not_prefix_set) - used_prefixes518 if unused_prefixes:519 raise Error("unused prefixes: {}".format(sorted(unused_prefixes)))520 521 if output_check_lines:522 output_lines.insert(0, ADVERT)523 output_lines.extend(output_check_lines)524 525 # The file should not end with two newlines. It creates unnecessary churn.526 while len(output_lines) > 0 and output_lines[-1] == "":527 output_lines.pop()528 529 if input_lines == output_lines:530 sys.stderr.write(" [unchanged]\n")531 return532 sys.stderr.write(" [{} lines total]\n".format(len(output_lines)))533 534 common.debug("Writing", len(output_lines), "lines to", test_path, "..\n\n")535 536 with open(test_path, "wb") as f:537 f.writelines(["{}\n".format(l).encode("utf-8") for l in output_lines])538 539 540def update_test_file(args, test_path, autogenerated_note):541 sys.stderr.write("Test: {}\n".format(test_path))542 543 # Call this per test. By default each warning will only be written once544 # per source location. Reset the warning filter so that now each warning545 # will be written once per source location per test.546 _configure_warnings(args)547 548 with open(test_path) as f:549 input_lines = [l.rstrip() for l in f]550 551 run_lines = common.find_run_lines(test_path, input_lines)552 run_infos = _get_run_infos(run_lines, args)553 common_prefix, prefix_pad = _get_useful_prefix_info(run_infos)554 block_infos = _get_block_infos(run_infos, test_path, args, common_prefix)555 _write_output(556 test_path,557 input_lines,558 run_infos,559 block_infos,560 args,561 common_prefix,562 prefix_pad,563 )564 565def main():566 warnings.showwarning = _showwarning567 script_name = "utils/" + os.path.basename(__file__)568 parser = _get_parser()569 args = common.parse_commandline_args(parser)570 if not args.llvm_mca_binary:571 stderr.write("Error: --llvm-mca-binary value cannot be empty string\n")572 return 1573 574 if "llvm-mca" not in os.path.basename(args.llvm_mca_binary):575 _warn("unexpected binary name: {}".format(args.llvm_mca_binary))576 577 returncode = 0578 for ti in common.itertests(args.tests, parser, script_name=script_name):579 try:580 update_test_file(ti.args, ti.path, ti.test_autogenerated_note)581 except Exception:582 stderr.write(f"Error: Failed to update test {ti.path}\n")583 print_exc()584 returncode = 1585 return returncode586 587 588if __name__ == "__main__":589 sys.exit(main())590