2860 lines · python
1import argparse2import bisect3import collections4import copy5import glob6import os7import re8import subprocess9import sys10import shlex11 12from typing import List, Mapping, Set13 14##### Common utilities for update_*test_checks.py15 16 17_verbose = False18_prefix_filecheck_ir_name = ""19 20"""21Version changelog:22 231: Initial version, used by tests that don't specify --version explicitly.242: --function-signature is now enabled by default and also checks return25 type/attributes.263: Opening parenthesis of function args is kept on the first LABEL line27 in case arguments are split to a separate SAME line.284: --check-globals now has a third option ('smart'). The others are now called29 'none' and 'all'. 'smart' is the default.305: Basic block labels are matched by FileCheck expressions316: The semantics of TBAA checks has been incorporated in the check lines.327: Indent switch-cases correctly; CHECK-EMPTY instead of skipping blank lines.33"""34DEFAULT_VERSION = 635 36 37SUPPORTED_ANALYSES = {38 "Branch Probability Analysis",39 "Cost Model Analysis",40 "Dependence Analysis",41 "Delinearization",42 "Loop Access Analysis",43 "Scalar Evolution Analysis",44 "Scalar Evolution Division",45}46 47 48class Regex(object):49 """Wrap a compiled regular expression object to allow deep copy of a regexp.50 This is required for the deep copy done in do_scrub.51 52 """53 54 def __init__(self, regex):55 self.regex = regex56 57 def __deepcopy__(self, memo):58 result = copy.copy(self)59 result.regex = self.regex60 return result61 62 def search(self, line):63 return self.regex.search(line)64 65 def sub(self, repl, line):66 return self.regex.sub(repl, line)67 68 def pattern(self):69 return self.regex.pattern70 71 def flags(self):72 return self.regex.flags73 74 75class Filter(Regex):76 """Augment a Regex object with a flag indicating whether a match should be77 added (!is_filter_out) or removed (is_filter_out) from the generated checks.78 79 """80 81 def __init__(self, regex, is_filter_out, is_filter_out_after):82 super(Filter, self).__init__(regex)83 if is_filter_out and is_filter_out_after:84 raise ValueError("cannot use both --filter-out and --filter-out-after")85 self.is_filter_out = is_filter_out86 self.is_filter_out_after = is_filter_out_after87 88 def __deepcopy__(self, memo):89 result = copy.deepcopy(super(Filter, self), memo)90 result.is_filter_out = copy.deepcopy(self.is_filter_out, memo)91 result.is_filter_out_after = copy.deepcopy(self.is_filter_out_after, memo)92 return result93 94 95def parse_commandline_args(parser):96 class RegexAction(argparse.Action):97 """Add a regular expression option value to a list of regular expressions.98 This compiles the expression, wraps it in a Regex and adds it to the option99 value list."""100 101 def __init__(self, option_strings, dest, nargs=None, **kwargs):102 if nargs is not None:103 raise ValueError("nargs not allowed")104 super(RegexAction, self).__init__(option_strings, dest, **kwargs)105 106 def do_call(self, namespace, values, flags):107 value_list = getattr(namespace, self.dest)108 if value_list is None:109 value_list = []110 111 try:112 value_list.append(Regex(re.compile(values, flags)))113 except re.error as error:114 raise ValueError(115 "{}: Invalid regular expression '{}' ({})".format(116 option_string, error.pattern, error.msg117 )118 )119 120 setattr(namespace, self.dest, value_list)121 122 def __call__(self, parser, namespace, values, option_string=None):123 self.do_call(namespace, values, 0)124 125 class FilterAction(RegexAction):126 """Add a filter to a list of filter option values."""127 128 def __init__(self, option_strings, dest, nargs=None, **kwargs):129 super(FilterAction, self).__init__(option_strings, dest, nargs, **kwargs)130 131 def __call__(self, parser, namespace, values, option_string=None):132 super(FilterAction, self).__call__(parser, namespace, values, option_string)133 134 value_list = getattr(namespace, self.dest)135 136 is_filter_out = option_string == "--filter-out"137 138 is_filter_out_after = option_string == "--filter-out-after"139 140 value_list[-1] = Filter(141 value_list[-1].regex, is_filter_out, is_filter_out_after142 )143 144 setattr(namespace, self.dest, value_list)145 146 filter_group = parser.add_argument_group(147 "filtering",148 """Filters are applied to each output line according to the order given. The149 first matching filter terminates filter processing for that current line.""",150 )151 152 filter_group.add_argument(153 "--filter",154 action=FilterAction,155 dest="filters",156 metavar="REGEX",157 help="Only include lines matching REGEX (may be specified multiple times)",158 )159 filter_group.add_argument(160 "--filter-out",161 action=FilterAction,162 dest="filters",163 metavar="REGEX",164 help="Exclude lines matching REGEX",165 )166 filter_group.add_argument(167 "--filter-out-after",168 action=FilterAction,169 dest="filters",170 metavar="REGEX",171 help="Exclude all lines within a given function after line matching REGEX",172 )173 174 parser.add_argument(175 "--include-generated-funcs",176 action="store_true",177 help="Output checks for functions not in source",178 )179 parser.add_argument(180 "-v", "--verbose", action="store_true", help="Show verbose output"181 )182 parser.add_argument(183 "-u",184 "--update-only",185 action="store_true",186 help="Only update test if it was already autogened",187 )188 parser.add_argument(189 "--force-update",190 action="store_true",191 help="Update test even if it was autogened by a different script",192 )193 parser.add_argument(194 "--enable",195 action="store_true",196 dest="enabled",197 default=True,198 help="Activate CHECK line generation from this point forward",199 )200 parser.add_argument(201 "--disable",202 action="store_false",203 dest="enabled",204 help="Deactivate CHECK line generation from this point forward",205 )206 parser.add_argument(207 "--replace-value-regex",208 nargs="+",209 default=[],210 help="List of regular expressions to replace matching value names",211 )212 parser.add_argument(213 "--prefix-filecheck-ir-name",214 default="",215 help="Add a prefix to FileCheck IR value names to avoid conflicts with scripted names",216 )217 parser.add_argument(218 "--global-value-regex",219 nargs="+",220 default=[],221 help="List of regular expressions that a global value declaration must match to generate a check (has no effect if checking globals is not enabled)",222 )223 parser.add_argument(224 "--global-hex-value-regex",225 nargs="+",226 default=[],227 help="List of regular expressions such that, for matching global value declarations, literal integer values should be encoded in hex in the associated FileCheck directives",228 )229 # FIXME: in 3.9, we can use argparse.BooleanOptionalAction. At that point,230 # we need to rename the flag to just -generate-body-for-unused-prefixes.231 parser.add_argument(232 "--no-generate-body-for-unused-prefixes",233 action="store_false",234 dest="gen_unused_prefix_body",235 default=True,236 help="Generate a function body that always matches for unused prefixes. This is useful when unused prefixes are desired, and it avoids needing to annotate each FileCheck as allowing them.",237 )238 # This is the default when regenerating existing tests. The default when239 # generating new tests is determined by DEFAULT_VERSION.240 parser.add_argument(241 "--version", type=int, default=1, help="The version of output format"242 )243 args = parser.parse_args()244 # TODO: This should not be handled differently from the other options245 global _verbose, _global_value_regex, _global_hex_value_regex246 _verbose = args.verbose247 _global_value_regex = args.global_value_regex248 _global_hex_value_regex = args.global_hex_value_regex249 return args250 251 252def parse_args(parser, argv):253 args = parser.parse_args(argv)254 if args.version >= 2:255 args.function_signature = True256 # TODO: This should not be handled differently from the other options257 global _verbose, _global_value_regex, _global_hex_value_regex258 _verbose = args.verbose259 _global_value_regex = args.global_value_regex260 _global_hex_value_regex = args.global_hex_value_regex261 if "check_globals" in args and args.check_globals == "default":262 args.check_globals = "none" if args.version < 4 else "smart"263 return args264 265 266class InputLineInfo(object):267 def __init__(self, line, line_number, args, argv):268 self.line = line269 self.line_number = line_number270 self.args = args271 self.argv = argv272 273 274class TestInfo(object):275 def __init__(276 self,277 test,278 parser,279 script_name,280 input_lines,281 args,282 argv,283 comment_prefix,284 argparse_callback,285 ):286 self.parser = parser287 self.argparse_callback = argparse_callback288 self.path = test289 self.args = args290 if args.prefix_filecheck_ir_name:291 global _prefix_filecheck_ir_name292 _prefix_filecheck_ir_name = args.prefix_filecheck_ir_name293 self.argv = argv294 self.input_lines = input_lines295 self.run_lines = find_run_lines(test, self.input_lines)296 self.comment_prefix = comment_prefix297 if self.comment_prefix is None:298 if self.path.endswith(".mir") or self.path.endswith(".txt"):299 self.comment_prefix = "#"300 elif self.path.endswith(".s"):301 self.comment_prefix = "//"302 else:303 self.comment_prefix = ";"304 self.autogenerated_note_prefix = self.comment_prefix + " " + UTC_ADVERT305 self.test_autogenerated_note = self.autogenerated_note_prefix + script_name306 self.test_autogenerated_note += get_autogennote_suffix(parser, self.args)307 self.test_unused_note = (308 self.comment_prefix + self.comment_prefix + " " + UNUSED_NOTE309 )310 311 def ro_iterlines(self):312 for line_num, input_line in enumerate(self.input_lines):313 args, argv = check_for_command(314 input_line, self.parser, self.args, self.argv, self.argparse_callback315 )316 yield InputLineInfo(input_line, line_num, args, argv)317 318 def iterlines(self, output_lines):319 output_lines.append(self.test_autogenerated_note)320 for line_info in self.ro_iterlines():321 input_line = line_info.line322 # Discard any previous script advertising.323 if input_line.startswith(self.autogenerated_note_prefix):324 continue325 self.args = line_info.args326 self.argv = line_info.argv327 if not self.args.enabled:328 output_lines.append(input_line)329 continue330 yield line_info331 332 def get_checks_for_unused_prefixes(333 self, run_list, used_prefixes: List[str]334 ) -> List[str]:335 run_list = [element for element in run_list if element[0] is not None]336 unused_prefixes = set(337 [prefix for sublist in run_list for prefix in sublist[0]]338 ).difference(set(used_prefixes))339 340 ret = []341 if not unused_prefixes:342 return ret343 ret.append(self.test_unused_note)344 for unused in sorted(unused_prefixes):345 ret.append(346 "{comment} {prefix}: {match_everything}".format(347 comment=self.comment_prefix,348 prefix=unused,349 match_everything=r"""{{.*}}""",350 )351 )352 return ret353 354 355def itertests(356 test_patterns, parser, script_name, comment_prefix=None, argparse_callback=None357):358 for pattern in test_patterns:359 # On Windows we must expand the patterns ourselves.360 tests_list = glob.glob(pattern)361 if not tests_list:362 warn("Test file pattern '%s' was not found. Ignoring it." % (pattern,))363 continue364 for test in tests_list:365 with open(test) as f:366 input_lines = [l.rstrip() for l in f]367 first_line = input_lines[0] if input_lines else ""368 if UTC_AVOID in first_line:369 warn("Skipping test that must not be autogenerated: " + test)370 continue371 is_regenerate = UTC_ADVERT in first_line372 373 # If we're generating a new test, set the default version to the latest.374 argv = sys.argv[:]375 if not is_regenerate:376 argv.insert(1, "--version=" + str(DEFAULT_VERSION))377 378 args = parse_args(parser, argv[1:])379 if argparse_callback is not None:380 argparse_callback(args)381 if is_regenerate:382 if script_name not in first_line and not args.force_update:383 warn(384 "Skipping test which wasn't autogenerated by " + script_name,385 test,386 )387 continue388 args, argv = check_for_command(389 first_line, parser, args, argv, argparse_callback390 )391 elif args.update_only:392 assert UTC_ADVERT not in first_line393 warn("Skipping test which isn't autogenerated: " + test)394 continue395 final_input_lines = []396 for l in input_lines:397 if UNUSED_NOTE in l:398 break399 final_input_lines.append(l)400 yield TestInfo(401 test,402 parser,403 script_name,404 final_input_lines,405 args,406 argv,407 comment_prefix,408 argparse_callback,409 )410 411 412def should_add_line_to_output(413 input_line,414 prefix_set,415 *,416 skip_global_checks=False,417 skip_same_checks=False,418 comment_marker=";",419):420 # Skip any blank comment lines in the IR.421 if not skip_global_checks and input_line.strip() == comment_marker:422 return False423 # Skip a special double comment line we use as a separator.424 if input_line.strip() == comment_marker + SEPARATOR:425 return False426 # Skip any blank lines in the IR.427 # if input_line.strip() == '':428 # return False429 # And skip any CHECK lines. We're building our own.430 m = CHECK_RE.match(input_line)431 if m and m.group(1) in prefix_set:432 if skip_same_checks and CHECK_SAME_RE.match(input_line):433 # The previous CHECK line was removed, so don't leave this dangling434 return False435 if skip_global_checks:436 # Skip checks only if they are of global value definitions437 global_ir_value_re = re.compile(r"(\[\[|@)", flags=(re.M))438 is_global = global_ir_value_re.search(input_line)439 return not is_global440 return False441 442 return True443 444 445def collect_original_check_lines(ti: TestInfo, prefix_set: set):446 """447 Collect pre-existing check lines into a dictionary `result` which is448 returned.449 450 result[func_name][prefix] is filled with a list of right-hand-sides of check451 lines.452 """453 result = collections.defaultdict(lambda: {})454 455 current_prefix = None456 current_function = None457 for input_line_info in ti.ro_iterlines():458 input_line = input_line_info.line459 if input_line.lstrip().startswith(";"):460 m = CHECK_RE.match(input_line)461 if m is not None:462 prefix = m.group(1)463 check_kind = m.group(2)464 line = input_line[m.end() :].strip()465 466 if prefix != current_prefix:467 current_function = None468 current_prefix = None469 470 if check_kind not in ["LABEL", "SAME"]:471 if current_function is not None:472 current_function.append(line)473 continue474 475 if check_kind == "SAME":476 continue477 478 if check_kind == "LABEL":479 m = IR_FUNCTION_LABEL_RE.match(line)480 if m is not None:481 func_name = m.group(1)482 if (483 ti.args.function is not None484 and func_name != ti.args.function485 ):486 # When filtering on a specific function, skip all others.487 continue488 489 current_prefix = prefix490 current_function = result[func_name][prefix] = []491 continue492 493 current_function = None494 495 return result496 497 498# Perform lit-like substitutions499def getSubstitutions(sourcepath):500 sourcedir = os.path.dirname(sourcepath)501 return [502 ("%s", sourcepath),503 ("%S", sourcedir),504 ("%p", sourcedir),505 ("%{pathsep}", os.pathsep),506 ]507 508 509def applySubstitutions(s, substitutions):510 for a, b in substitutions:511 s = s.replace(a, b)512 return s513 514 515# Invoke the tool that is being tested.516def invoke_tool(exe, cmd_args, ir, preprocess_cmd=None, verbose=False):517 with open(ir) as ir_file:518 substitutions = getSubstitutions(ir)519 520 # TODO Remove the str form which is used by update_test_checks.py and521 # update_llc_test_checks.py522 # The safer list form is used by update_cc_test_checks.py523 if preprocess_cmd:524 # Allow pre-processing the IR file (e.g. using sed):525 assert isinstance(526 preprocess_cmd, str527 ) # TODO: use a list instead of using shell528 preprocess_cmd = applySubstitutions(preprocess_cmd, substitutions).strip()529 if verbose:530 print(531 "Pre-processing input file: ",532 ir,533 " with command '",534 preprocess_cmd,535 "'",536 sep="",537 file=sys.stderr,538 )539 pp = subprocess.Popen(540 preprocess_cmd,541 shell=True,542 stdin=subprocess.DEVNULL,543 stdout=subprocess.PIPE,544 )545 ir_file = pp.stdout546 547 if isinstance(cmd_args, list):548 args = [applySubstitutions(a, substitutions) for a in cmd_args]549 stdout = subprocess.check_output([exe] + args, stdin=ir_file)550 else:551 stdout = subprocess.check_output(552 exe + " " + applySubstitutions(cmd_args, substitutions),553 shell=True,554 stdin=ir_file,555 )556 if sys.version_info[0] > 2:557 # FYI, if you crashed here with a decode error, your run line probably558 # results in bitcode or other binary format being written to the pipe.559 # For an opt test, you probably want to add -S or -disable-output.560 stdout = stdout.decode()561 # Fix line endings to unix CR style.562 return stdout.replace("\r\n", "\n")563 564 565##### LLVM IR parser566RUN_LINE_RE = re.compile(r"^\s*(?://|[;#])\s*RUN:\s*(.*)$")567CHECK_PREFIX_RE = re.compile(r"--?check-prefix(?:es)?[= ](\S+)")568PREFIX_RE = re.compile("^[a-zA-Z0-9_-]+$")569CHECK_RE = re.compile(570 r"^\s*(?://|[;#])\s*([^:]+?)(?:-(NEXT|NOT|DAG|LABEL|SAME|EMPTY))?:"571)572CHECK_SAME_RE = re.compile(r"^\s*(?://|[;#])\s*([^:]+?)(?:-SAME)?:")573 574UTC_ARGS_KEY = "UTC_ARGS:"575UTC_ARGS_CMD = re.compile(r".*" + UTC_ARGS_KEY + r"\s*(?P<cmd>.*)\s*$")576UTC_ADVERT = "NOTE: Assertions have been autogenerated by "577UTC_AVOID = "NOTE: Do not autogenerate"578UNUSED_NOTE = "NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line:"579 580DATA_LAYOUT_RE = re.compile(581 r"target\s+datalayout\s+=\s+\"(?P<layout>.+)\"$", flags=(re.M | re.S)582)583 584OPT_FUNCTION_RE = re.compile(585 r"^(\s*;\s*Function\sAttrs:\s(?P<attrs>[\w\s():,]+?))?\s*define\s+(?P<funcdef_attrs_and_ret>[^@]*)@(?P<func>[\w.$-]+?)\s*"586 r"(?P<args_and_sig>\((\)|(.*?[\w.-]+?)\))[^{]*\{)\n(?P<body>.*?)^\}$",587 flags=(re.M | re.S),588)589 590ANALYZE_FUNCTION_RE = re.compile(591 r"^\s*\'(?P<analysis>[\w\s-]+?)\'\s+for\s+function\s+\'(?P<func>[\w.$-]+?)\':"592 r"\s*\n(?P<body>.*)$",593 flags=(re.X | re.S),594)595 596LOOP_PASS_DEBUG_RE = re.compile(597 r"^\s*\'(?P<func>[\w.$-]+?)\'[^\n]*" r"\s*\n(?P<body>.*)$", flags=(re.X | re.S)598)599 600IR_FUNCTION_RE = re.compile(r'^\s*define\s+(?:internal\s+)?[^@]*@"?([\w.$-]+)"?\s*\(')601IR_FUNCTION_LABEL_RE = re.compile(602 r'^\s*(?:define\s+(?:internal\s+)?[^@]*)?@"?([\w.$-]+)"?\s*\('603)604TRIPLE_IR_RE = re.compile(r'^\s*target\s+triple\s*=\s*"([^"]+)"$')605TRIPLE_ARG_RE = re.compile(r"-m?triple[= ]([^ ]+)")606MARCH_ARG_RE = re.compile(r"-march[= ]([^ ]+)")607DEBUG_ONLY_ARG_RE = re.compile(r"-debug-only[= ]([^ ]+)")608STOP_PASS_RE = re.compile(r"-stop-(before|after)=(\w+)")609 610IS_DEBUG_RECORD_RE = re.compile(r"^(\s+)#dbg_")611IS_SWITCH_CASE_RE = re.compile(r"^\s+i\d+ \d+, label %\S+")612 613SCRUB_LEADING_WHITESPACE_RE = re.compile(r"^(\s+)")614SCRUB_WHITESPACE_RE = re.compile(r"(?!^(| \w))[ \t]+", flags=re.M)615SCRUB_PRESERVE_LEADING_WHITESPACE_RE = re.compile(r"((?!^)[ \t]*(\S))[ \t]+")616SCRUB_TRAILING_WHITESPACE_RE = re.compile(r"[ \t]+$", flags=re.M)617SCRUB_TRAILING_WHITESPACE_TEST_RE = SCRUB_TRAILING_WHITESPACE_RE618SCRUB_TRAILING_WHITESPACE_AND_ATTRIBUTES_RE = re.compile(619 r"([ \t]|(#[0-9]+))+$", flags=re.M620)621SCRUB_KILL_COMMENT_RE = re.compile(r"^ *#+ +kill:.*\n")622SCRUB_LOOP_COMMENT_RE = re.compile(623 r"# =>This Inner Loop Header:.*|# in Loop:.*", flags=re.M624)625SCRUB_TAILING_COMMENT_TOKEN_RE = re.compile(r"(?<=\S)+[ \t]*#$", flags=re.M)626 627SEPARATOR = "."628 629METADATA_NODES_RE = re.compile(r"^\s*!(\d+)\s*=\s*!\{(.*)\}", re.M)630TBAA_TAGS_RE = re.compile(r"!tbaa\s*!([0-9]+)")631 632 633def error(msg, test_file=None):634 if test_file:635 msg = "{}: {}".format(msg, test_file)636 print("ERROR: {}".format(msg), file=sys.stderr)637 638 639def warn(msg, test_file=None):640 if test_file:641 msg = "{}: {}".format(msg, test_file)642 print("WARNING: {}".format(msg), file=sys.stderr)643 644 645def debug(*args, **kwargs):646 # Python2 does not allow def debug(*args, file=sys.stderr, **kwargs):647 if "file" not in kwargs:648 kwargs["file"] = sys.stderr649 if _verbose:650 print(*args, **kwargs)651 652 653def find_run_lines(test, lines):654 debug("Scanning for RUN lines in test file:", test)655 raw_lines = [m.group(1) for m in [RUN_LINE_RE.match(l) for l in lines] if m]656 run_lines = [raw_lines[0]] if len(raw_lines) > 0 else []657 for l in raw_lines[1:]:658 if run_lines[-1].endswith("\\"):659 run_lines[-1] = run_lines[-1].rstrip("\\") + " " + l660 else:661 run_lines.append(l)662 debug("Found {} RUN lines in {}:".format(len(run_lines), test))663 for l in run_lines:664 debug(" RUN: {}".format(l))665 return run_lines666 667 668def get_triple_from_march(march):669 triples = {670 "amdgcn": "amdgcn",671 "r600": "r600",672 "mips": "mips",673 "nvptx64": "nvptx64",674 "sparc": "sparc",675 "hexagon": "hexagon",676 "ve": "ve",677 }678 for prefix, triple in triples.items():679 if march.startswith(prefix):680 return triple681 print("Cannot find a triple. Assume 'x86'", file=sys.stderr)682 return "x86"683 684 685def get_globals_name_prefix(raw_tool_output):686 m = DATA_LAYOUT_RE.search(raw_tool_output)687 if not m:688 return None689 data_layout = m.group("layout")690 idx = data_layout.find("m:")691 if idx < 0:692 return None693 ch = data_layout[idx + 2]694 return "_" if ch == "o" or ch == "x" else None695 696 697def get_tbaa_records(version, raw_output_tools):698 if version < 6:699 return {}700 701 # Retrieve all unique tbaa tags for the given IR.702 unique_tbaa_tags = {f"!{n}" for n in TBAA_TAGS_RE.findall(raw_output_tools)}703 if not unique_tbaa_tags:704 return {}705 706 # Small dict of metadata ID and its node content as value.707 md_nodes = {708 f"!{m.group(1)}": m.group(2)709 for m in METADATA_NODES_RE.finditer(raw_output_tools)710 }711 assert md_nodes, "Shouldn't have TBAA tags without their type descriptors."712 713 result = {}714 for tag in unique_tbaa_tags:715 type_desc = md_nodes.get(tag)716 assert type_desc, f"Expected type descriptor for node {tag}."717 718 # We deal with a tag of kind `(BaseTy, AccessTy, Offset)`.719 access_ty = type_desc.split(",")[1].strip()720 721 parent_ty = md_nodes.get(access_ty)722 assert parent_ty, f"Couldn't find metadata for access type {access_ty}."723 724 # First operand should be a MDString. If not, likely dealing with725 # `new-struct-path-tbaa`.726 # TODO: Support `new-struct-path-tbaa` TBAA format.727 ty_name_field = parent_ty.split(",")[0]728 if not (ty_name_field.startswith('!"') and ty_name_field.endswith('"')):729 return {}730 ty_name = ty_name_field[2:-1]731 732 if ty_name.startswith("p"):733 # Dealing with a pointer here.734 pointee_ty_name = ty_name.split(maxsplit=1)[1]735 if pointee_ty_name.startswith("omnipotent"):736 pointee_ty_name = "char"737 # TODO: If pointee_ty_name is a C++ name, should it be demangled?738 pointee_ty_name = pointee_ty_name.replace(" ", "_")739 tbaa_prefix = f"{pointee_ty_name}ptr"740 elif ty_name.startswith("any"):741 tbaa_prefix = "anyptr"742 elif ty_name.startswith("omnipotent"):743 tbaa_prefix = "char"744 else:745 tbaa_prefix = ty_name.replace(" ", "_")746 747 # Record tag node and its semantics (e.g., INT_TBAA, INTPTR_TBAA).748 tbaa_sema = f"{tbaa_prefix.upper()}_TBAA"749 result[tag] = tbaa_sema750 751 return result752 753 754def apply_filters(line, filters):755 has_filter = False756 for f in filters:757 if f.is_filter_out_after:758 continue759 if not f.is_filter_out:760 has_filter = True761 if f.search(line):762 return False if f.is_filter_out else True763 # If we only used filter-out, keep the line, otherwise discard it since no764 # filter matched.765 return False if has_filter else True766 767 768def has_filter_out_after(filters):769 for f in filters:770 if f.is_filter_out_after:771 return True772 return False773 774 775def filter_out_after(body, filters):776 lines = []777 for line in body.splitlines():778 lines.append(line)779 for f in filters:780 if f.is_filter_out_after:781 if f.search(line):782 return lines783 return lines784 785 786def do_filter(body, filters):787 if not filters:788 return body789 filter_out_after_flag = has_filter_out_after(filters)790 lines = []791 if filter_out_after_flag:792 lines = filter_out_after(body, filters)793 else:794 lines = body.splitlines()795 return "\n".join(filter(lambda line: apply_filters(line, filters), lines))796 797 798def scrub_body(body):799 # Scrub runs of whitespace out of the assembly, but leave the leading800 # whitespace in place.801 body = SCRUB_PRESERVE_LEADING_WHITESPACE_RE.sub(lambda m: m.group(2) + " ", body)802 803 # Expand the tabs used for indentation.804 body = str.expandtabs(body, 2)805 # Strip trailing whitespace.806 body = SCRUB_TRAILING_WHITESPACE_TEST_RE.sub(r"", body)807 return body808 809 810def do_scrub(body, scrubber, scrubber_args, extra):811 if scrubber_args:812 local_args = copy.deepcopy(scrubber_args)813 local_args[0].extra_scrub = extra814 return scrubber(body, *local_args)815 return scrubber(body, *scrubber_args)816 817 818# Build up a dictionary of all the function bodies.819class function_body(object):820 def __init__(821 self,822 string,823 extra,824 funcdef_attrs_and_ret,825 args_and_sig,826 attrs,827 func_name_separator,828 ginfo,829 ):830 self.scrub = string831 self.extrascrub = extra832 self.funcdef_attrs_and_ret = funcdef_attrs_and_ret833 self.args_and_sig = args_and_sig834 self.attrs = attrs835 self.func_name_separator = func_name_separator836 self._ginfo = ginfo837 838 def is_same_except_arg_names(839 self, extrascrub, funcdef_attrs_and_ret, args_and_sig, attrs840 ):841 arg_names = set()842 843 def drop_arg_names(match):844 nameless_value = self._ginfo.get_nameless_value_from_match(match)845 if nameless_value.check_key == "%":846 arg_names.add(self._ginfo.get_name_from_match(match))847 substitute = ""848 else:849 substitute = match.group(2)850 return match.group(1) + substitute + match.group(match.lastindex)851 852 def repl_arg_names(match):853 nameless_value = self._ginfo.get_nameless_value_from_match(match)854 if (855 nameless_value.check_key == "%"856 and self._ginfo.get_name_from_match(match) in arg_names857 ):858 return match.group(1) + match.group(match.lastindex)859 return match.group(1) + match.group(2) + match.group(match.lastindex)860 861 if self.funcdef_attrs_and_ret != funcdef_attrs_and_ret:862 return False863 if self.attrs != attrs:864 return False865 866 regexp = self._ginfo.get_regexp()867 ans0 = regexp.sub(drop_arg_names, self.args_and_sig)868 ans1 = regexp.sub(drop_arg_names, args_and_sig)869 if ans0 != ans1:870 return False871 if self._ginfo.is_asm():872 # Check without replacements, the replacements are not applied to the873 # body for backend checks.874 return self.extrascrub == extrascrub875 876 es0 = regexp.sub(repl_arg_names, self.extrascrub)877 es1 = regexp.sub(repl_arg_names, extrascrub)878 es0 = SCRUB_IR_COMMENT_RE.sub(r"", es0)879 es1 = SCRUB_IR_COMMENT_RE.sub(r"", es1)880 return es0 == es1881 882 def __str__(self):883 return self.scrub884 885 886class FunctionTestBuilder:887 def __init__(self, run_list, flags, scrubber_args, path, ginfo):888 self._run_list = run_list889 self._verbose = flags.verbose890 self._record_args = flags.function_signature891 self._check_attributes = flags.check_attributes892 # Strip double-quotes if input was read by UTC_ARGS893 self._filters = (894 list(895 map(896 lambda f: Filter(897 re.compile(f.pattern().strip('"'), f.flags()),898 f.is_filter_out,899 f.is_filter_out_after,900 ),901 flags.filters,902 )903 )904 if flags.filters905 else []906 )907 self._scrubber_args = scrubber_args908 self._path = path909 self._ginfo = ginfo910 # Strip double-quotes if input was read by UTC_ARGS911 self._replace_value_regex = list(912 map(lambda x: x.strip('"'), flags.replace_value_regex)913 )914 self._func_dict = {}915 self._func_order = {}916 self._global_var_dict = {}917 self._processed_prefixes = set()918 for tuple in run_list:919 for prefix in tuple[0]:920 self._func_dict.update({prefix: dict()})921 self._func_order.update({prefix: []})922 self._global_var_dict.update({prefix: dict()})923 924 # Return true if there is conflicting output for different runs for the925 # given prefix and function name.926 def has_conflicting_output(self, prefix, func):927 # There was conflicting output if the func_dict is None for this928 # prefix and function.929 return self._func_dict[prefix].get(func) is None930 931 def finish_and_get_func_dict(self):932 all_funcs = set()933 for prefix in self._func_dict:934 all_funcs.update(self._func_dict[prefix].keys())935 936 warnings_to_print = collections.defaultdict(list)937 for func in sorted(list(all_funcs)):938 for i, run_info in enumerate(self._run_list):939 prefixes = run_info[0]940 if not prefixes:941 continue942 943 # Check if this RUN line produces this function at all. If944 # not, we can skip analysing this function for this RUN.945 run_contains_func = all(946 func in self._func_dict.get(p, {}) for p in prefixes947 )948 if not run_contains_func:949 continue950 951 # Check if this RUN line can print any checks for this952 # function. It can't if all of its prefixes have conflicting953 # (None) output.954 cannot_print_for_this_run = all(955 self.has_conflicting_output(p, func) for p in prefixes956 )957 if cannot_print_for_this_run:958 warnings_to_print[func].append((i, prefixes))959 960 for func, warning_info in warnings_to_print.items():961 conflict_strs = []962 for run_index, prefixes in warning_info:963 conflict_strs.append(964 f"RUN #{run_index + 1} (prefixes: {', '.join(prefixes)})"965 )966 warn(967 f"For function '{func}', the following RUN lines will not generate checks due to conflicting output: {', '.join(conflict_strs)}",968 test_file=self._path,969 )970 971 return self._func_dict972 973 def func_order(self):974 return self._func_order975 976 def global_var_dict(self):977 return self._global_var_dict978 979 def is_filtered(self):980 for f in self._filters:981 if not f.is_filter_out_after:982 return True983 return False984 985 def process_run_line(self, function_re, scrubber, raw_tool_output, prefixes):986 """987 Returns the number of functions processed from the output by the regex.988 """989 build_global_values_dictionary(990 self._global_var_dict, raw_tool_output, prefixes, self._ginfo991 )992 processed_func_count = 0993 for m in function_re.finditer(raw_tool_output):994 if not m:995 continue996 processed_func_count += 1997 func = m.group("func")998 body = m.group("body")999 # func_name_separator is the string that is placed right after function name at the1000 # beginning of assembly function definition. In most assemblies, that is just a1001 # colon: `foo:`. But, for example, in nvptx it is a brace: `foo(`. If is_backend is1002 # False, just assume that separator is an empty string.1003 if self._ginfo.is_asm():1004 # Use ':' as default separator.1005 func_name_separator = (1006 m.group("func_name_separator")1007 if "func_name_separator" in m.groupdict()1008 else ":"1009 )1010 else:1011 func_name_separator = ""1012 attrs = m.group("attrs") if self._check_attributes else ""1013 funcdef_attrs_and_ret = (1014 m.group("funcdef_attrs_and_ret") if self._record_args else ""1015 )1016 # Determine if we print arguments, the opening brace, or nothing after the1017 # function name1018 if self._record_args and "args_and_sig" in m.groupdict():1019 args_and_sig = scrub_body(m.group("args_and_sig").strip())1020 elif "args_and_sig" in m.groupdict():1021 args_and_sig = "("1022 else:1023 args_and_sig = ""1024 filtered_body = do_filter(body, self._filters)1025 scrubbed_body = do_scrub(1026 filtered_body, scrubber, self._scrubber_args, extra=False1027 )1028 scrubbed_extra = do_scrub(1029 filtered_body, scrubber, self._scrubber_args, extra=True1030 )1031 if "analysis" in m.groupdict():1032 analysis = m.group("analysis")1033 if analysis not in SUPPORTED_ANALYSES:1034 warn("Unsupported analysis mode: %r!" % (analysis,))1035 if func.startswith("stress"):1036 # We only use the last line of the function body for stress tests.1037 scrubbed_body = "\n".join(scrubbed_body.splitlines()[-1:])1038 if self._verbose:1039 print("Processing function: " + func, file=sys.stderr)1040 for l in scrubbed_body.splitlines():1041 print(" " + l, file=sys.stderr)1042 for prefix in prefixes:1043 # Replace function names matching the regex.1044 for regex in self._replace_value_regex:1045 # Pattern that matches capture groups in the regex in leftmost order.1046 group_regex = re.compile(r"\(.*?\)")1047 # Replace function name with regex.1048 match = re.match(regex, func)1049 if match:1050 func_repl = regex1051 # Replace any capture groups with their matched strings.1052 for g in match.groups():1053 func_repl = group_regex.sub(1054 re.escape(g), func_repl, count=11055 )1056 func = re.sub(func_repl, "{{" + func_repl + "}}", func)1057 1058 # Replace all calls to regex matching functions.1059 matches = re.finditer(regex, scrubbed_body)1060 for match in matches:1061 func_repl = regex1062 # Replace any capture groups with their matched strings.1063 for g in match.groups():1064 func_repl = group_regex.sub(1065 re.escape(g), func_repl, count=11066 )1067 # Substitute function call names that match the regex with the same1068 # capture groups set.1069 scrubbed_body = re.sub(1070 func_repl, "{{" + func_repl + "}}", scrubbed_body1071 )1072 1073 if func in self._func_dict[prefix]:1074 if self._func_dict[prefix][func] is not None and (1075 str(self._func_dict[prefix][func]) != scrubbed_body1076 or self._func_dict[prefix][func].args_and_sig != args_and_sig1077 or self._func_dict[prefix][func].attrs != attrs1078 or self._func_dict[prefix][func].funcdef_attrs_and_ret1079 != funcdef_attrs_and_ret1080 ):1081 if self._func_dict[prefix][func].is_same_except_arg_names(1082 scrubbed_extra,1083 funcdef_attrs_and_ret,1084 args_and_sig,1085 attrs,1086 ):1087 self._func_dict[prefix][func].scrub = scrubbed_extra1088 self._func_dict[prefix][func].args_and_sig = args_and_sig1089 else:1090 # This means a previous RUN line produced a body for this function1091 # that is different from the one produced by this current RUN line,1092 # so the body can't be common across RUN lines. We use None to1093 # indicate that.1094 self._func_dict[prefix][func] = None1095 else:1096 if prefix not in self._processed_prefixes:1097 self._func_dict[prefix][func] = function_body(1098 scrubbed_body,1099 scrubbed_extra,1100 funcdef_attrs_and_ret,1101 args_and_sig,1102 attrs,1103 func_name_separator,1104 self._ginfo,1105 )1106 self._func_order[prefix].append(func)1107 else:1108 # An earlier RUN line used this check prefixes but didn't produce1109 # a body for this function. This happens in Clang tests that use1110 # preprocesser directives to exclude individual functions from some1111 # RUN lines.1112 self._func_dict[prefix][func] = None1113 return processed_func_count1114 1115 def processed_prefixes(self, prefixes):1116 """1117 Mark a set of prefixes as having had at least one applicable RUN line fully1118 processed. This is used to filter out function bodies that don't have1119 outputs for all RUN lines.1120 """1121 self._processed_prefixes.update(prefixes)1122 1123 1124##### Generator of LLVM IR CHECK lines1125 1126SCRUB_IR_COMMENT_RE = re.compile(r"\s*;.*")1127# Comments to indicate the predecessors of a block in the IR.1128SCRUB_PRED_COMMENT_RE = re.compile(r"\s*; preds = .*")1129SCRUB_IR_FUNC_META_RE = re.compile(r"((?:\!(?!dbg\b)[a-zA-Z_]\w*(?:\s+![0-9]+)?)\s*)+")1130 1131# TODO: We should also derive check lines for global, debug, loop declarations, etc..1132 1133 1134class NamelessValue:1135 """1136 A NamelessValue object represents a type of value in the IR whose "name" we1137 generalize in the generated check lines; where the "name" could be an actual1138 name (as in e.g. `@some_global` or `%x`) or just a number (as in e.g. `%12`1139 or `!4`).1140 """1141 1142 def __init__(1143 self,1144 check_prefix,1145 check_key,1146 ir_prefix,1147 ir_regexp,1148 global_ir_rhs_regexp,1149 *,1150 is_before_functions=False,1151 is_number=False,1152 replace_number_with_counter=False,1153 match_literally=False,1154 interlaced_with_previous=False,1155 ir_suffix=r"",1156 ):1157 self.check_prefix = check_prefix1158 self.check_key = check_key1159 self.ir_prefix = ir_prefix1160 self.ir_regexp = ir_regexp1161 self.ir_suffix = ir_suffix1162 self.global_ir_rhs_regexp = global_ir_rhs_regexp1163 self.is_before_functions = is_before_functions1164 self.is_number = is_number1165 # Some variable numbers (e.g. MCINST1234) will change based on unrelated1166 # modifications to LLVM, replace those with an incrementing counter.1167 self.replace_number_with_counter = replace_number_with_counter1168 self.match_literally = match_literally1169 self.interlaced_with_previous = interlaced_with_previous1170 self.variable_mapping = {}1171 1172 # Return true if this kind of IR value is defined "locally" to functions,1173 # which we assume is only the case precisely for LLVM IR local values.1174 def is_local_def_ir_value(self):1175 return self.check_key == "%"1176 1177 # Return the IR regexp we use for this kind or IR value, e.g., [\w.-]+? for locals1178 def get_ir_regex(self):1179 # for backwards compatibility we check locals with '.*'1180 if self.is_local_def_ir_value():1181 return ".*"1182 return self.ir_regexp1183 1184 # Create a FileCheck variable name based on an IR name.1185 def get_value_name(self, var: str, check_prefix: str):1186 var = var.replace("!", "")1187 if self.replace_number_with_counter:1188 assert var1189 replacement = self.variable_mapping.get(var, None)1190 if replacement is None:1191 # Replace variable with an incrementing counter1192 replacement = str(len(self.variable_mapping) + 1)1193 self.variable_mapping[var] = replacement1194 var = replacement1195 # This is a nameless value, prepend check_prefix.1196 if var.isdigit():1197 var = check_prefix + var1198 else:1199 # This is a named value that clashes with the check_prefix, prepend with1200 # _prefix_filecheck_ir_name, if it has been defined.1201 if (1202 may_clash_with_default_check_prefix_name(check_prefix, var)1203 and _prefix_filecheck_ir_name1204 ):1205 var = _prefix_filecheck_ir_name + var1206 var = var.replace(".", "_")1207 var = var.replace("-", "_")1208 return var.upper()1209 1210 def get_affixes_from_match(self, match):1211 prefix = re.match(self.ir_prefix, match.group(2)).group(0)1212 suffix = re.search(self.ir_suffix + "$", match.group(2)).group(0)1213 return prefix, suffix1214 1215 1216class GeneralizerInfo:1217 """1218 A GeneralizerInfo object holds information about how check lines should be generalized1219 (e.g., variable names replaced by FileCheck meta variables) as well as per-test-file1220 state (e.g. information about IR global variables).1221 """1222 1223 MODE_IR = 01224 MODE_ASM = 11225 MODE_ANALYZE = 21226 1227 def __init__(1228 self,1229 version,1230 mode,1231 nameless_values: List[NamelessValue],1232 regexp_prefix,1233 regexp_suffix,1234 no_meta_details=False,1235 ):1236 self._version = version1237 self._mode = mode1238 self._nameless_values = nameless_values1239 1240 self._regexp_prefix = regexp_prefix1241 self._regexp_suffix = regexp_suffix1242 self._no_meta_details = no_meta_details1243 1244 self._regexp, _ = self._build_regexp(False, False)1245 (1246 self._unstable_globals_regexp,1247 self._unstable_globals_values,1248 ) = self._build_regexp(True, True)1249 1250 def _build_regexp(self, globals_only, unstable_only):1251 matches = []1252 values = []1253 for nameless_value in self._nameless_values:1254 is_global = nameless_value.global_ir_rhs_regexp is not None1255 if globals_only and not is_global:1256 continue1257 if unstable_only and nameless_value.match_literally:1258 continue1259 1260 match = f"(?:{nameless_value.ir_prefix}({nameless_value.ir_regexp}){nameless_value.ir_suffix})"1261 if self.is_ir() and not globals_only and is_global:1262 match = "^" + match1263 matches.append(match)1264 values.append(nameless_value)1265 1266 regexp_string = r"|".join(matches)1267 1268 return (1269 re.compile(1270 self._regexp_prefix + r"(" + regexp_string + r")" + self._regexp_suffix1271 ),1272 values,1273 )1274 1275 def get_version(self):1276 return self._version1277 1278 def is_ir(self):1279 return self._mode == GeneralizerInfo.MODE_IR1280 1281 def is_asm(self):1282 return self._mode == GeneralizerInfo.MODE_ASM1283 1284 def is_analyze(self):1285 return self._mode == GeneralizerInfo.MODE_ANALYZE1286 1287 def get_nameless_values(self):1288 return self._nameless_values1289 1290 def get_regexp(self):1291 return self._regexp1292 1293 def get_unstable_globals_regexp(self):1294 return self._unstable_globals_regexp1295 1296 def no_meta_details(self):1297 return self._no_meta_details1298 1299 # The entire match is group 0, the prefix has one group (=1), the entire1300 # IR_VALUE_REGEXP_STRING is one group (=2), and then the nameless values start.1301 FIRST_NAMELESS_GROUP_IN_MATCH = 31302 1303 def get_match_info(self, match):1304 """1305 Returns (name, nameless_value) for the given match object1306 """1307 if match.re == self._regexp:1308 values = self._nameless_values1309 else:1310 match.re == self._unstable_globals_regexp1311 values = self._unstable_globals_values1312 for i in range(len(values)):1313 g = match.group(i + GeneralizerInfo.FIRST_NAMELESS_GROUP_IN_MATCH)1314 if g is not None:1315 return g, values[i]1316 error("Unable to identify the kind of IR value from the match!")1317 return None, None1318 1319 # See get_idx_from_match1320 def get_name_from_match(self, match):1321 return self.get_match_info(match)[0]1322 1323 def get_nameless_value_from_match(self, match) -> NamelessValue:1324 return self.get_match_info(match)[1]1325 1326 1327def make_ir_generalizer(version, no_meta_details):1328 values = []1329 1330 if version >= 5:1331 values += [1332 NamelessValue(r"BB", "%", r"label %", r"[\w$.-]+?", None),1333 NamelessValue(r"BB", "%", r"^", r"[\w$.-]+?", None, ir_suffix=r":"),1334 ]1335 1336 values += [1337 # check_prefix check_key ir_prefix ir_regexp global_ir_rhs_regexp1338 NamelessValue(r"TMP", "%", r"%", r"[\w$.-]+?", None),1339 NamelessValue(r"ATTR", "#", r"#", r"[0-9]+", None),1340 NamelessValue(r"ATTR", "#", r"attributes #", r"[0-9]+", r"{[^}]*}"),1341 NamelessValue(r"GLOB", "@", r"@", r"[0-9]+", None),1342 NamelessValue(r"GLOB", "@", r"@", r"[0-9]+", r".+", is_before_functions=True),1343 NamelessValue(1344 r"GLOBNAMED",1345 "@",1346 r"@",1347 r"[a-zA-Z0-9_$\"\\.-]*[a-zA-Z_$\"\\.-][a-zA-Z0-9_$\"\\.-]*",1348 r".+",1349 is_before_functions=True,1350 match_literally=True,1351 interlaced_with_previous=True,1352 ),1353 NamelessValue(r"DBG", "!", r"!dbg ", r"![0-9]+", None),1354 NamelessValue(r"DIASSIGNID", "!", r"!DIAssignID ", r"![0-9]+", None),1355 NamelessValue(r"PROF", "!", r"!prof ", r"![0-9]+", None),1356 NamelessValue(r"TBAA", "!", r"!tbaa ", r"![0-9]+", None),1357 NamelessValue(r"TBAA_STRUCT", "!", r"!tbaa.struct ", r"![0-9]+", None),1358 NamelessValue(r"RNG", "!", r"!range ", r"![0-9]+", None),1359 NamelessValue(r"LOOP", "!", r"!llvm.loop ", r"![0-9]+", None),1360 NamelessValue(r"META", "!", r"", r"![0-9]+", r"(?:distinct |)!.*"),1361 NamelessValue(r"ACC_GRP", "!", r"!llvm.access.group ", r"![0-9]+", None),1362 NamelessValue(r"META", "!", r"![a-z.]+ ", r"![0-9]+", None),1363 NamelessValue(r"META", "!", r"[, (]", r"![0-9]+", None),1364 ]1365 1366 prefix = r"(\s*)"1367 suffix = r"([,\s\(\)\}\]]|\Z)"1368 1369 # values = [1370 # nameless_value1371 # for nameless_value in IR_NAMELESS_VALUES1372 # if not (globals_only and nameless_value.global_ir_rhs_regexp is None) and1373 # not (unstable_ids_only and nameless_value.match_literally)1374 # ]1375 1376 return GeneralizerInfo(1377 version, GeneralizerInfo.MODE_IR, values, prefix, suffix, no_meta_details1378 )1379 1380 1381def make_asm_generalizer(version):1382 values = [1383 NamelessValue(1384 r"MCINST",1385 "Inst#",1386 "<MCInst #",1387 r"\d+",1388 r".+",1389 is_number=True,1390 replace_number_with_counter=True,1391 ),1392 NamelessValue(1393 r"MCREG",1394 "Reg:",1395 "<MCOperand Reg:",1396 r"\d+",1397 r".+",1398 is_number=True,1399 replace_number_with_counter=True,1400 ),1401 ]1402 1403 prefix = r"((?:#|//)\s*)"1404 suffix = r"([>\s]|\Z)"1405 1406 return GeneralizerInfo(version, GeneralizerInfo.MODE_ASM, values, prefix, suffix)1407 1408 1409# TODO: This is no longer required. Generalize UTC over an empty GeneralizerInfo.1410def make_analyze_generalizer(version):1411 values = [1412 NamelessValue(1413 r"GRP",1414 "#",1415 r"",1416 r"0x[0-9a-f]+",1417 None,1418 replace_number_with_counter=True,1419 ),1420 ]1421 1422 prefix = r"(\s*)"1423 suffix = r"(\)?:)"1424 1425 return GeneralizerInfo(1426 version, GeneralizerInfo.MODE_ANALYZE, values, prefix, suffix1427 )1428 1429 1430# Return true if var clashes with the scripted FileCheck check_prefix.1431def may_clash_with_default_check_prefix_name(check_prefix, var):1432 return check_prefix and re.match(1433 r"^" + check_prefix + r"[0-9]+?$", var, re.IGNORECASE1434 )1435 1436 1437def find_diff_matching(lhs: List[str], rhs: List[str]) -> List[tuple]:1438 """1439 Find a large ordered matching between strings in lhs and rhs.1440 1441 Think of this as finding the *unchanged* lines in a diff, where the entries1442 of lhs and rhs are lines of the files being diffed.1443 1444 Returns a list of matched (lhs_idx, rhs_idx) pairs.1445 """1446 1447 if not lhs or not rhs:1448 return []1449 1450 # Collect matches in reverse order.1451 matches = []1452 1453 # First, collect a set of candidate matching edges. We limit this to a1454 # constant multiple of the input size to avoid quadratic runtime.1455 patterns = collections.defaultdict(lambda: ([], []))1456 1457 for idx in range(len(lhs)):1458 patterns[lhs[idx]][0].append(idx)1459 for idx in range(len(rhs)):1460 patterns[rhs[idx]][1].append(idx)1461 1462 multiple_patterns = []1463 1464 candidates = []1465 for pattern in patterns.values():1466 if not pattern[0] or not pattern[1]:1467 continue1468 1469 if len(pattern[0]) == len(pattern[1]) == 1:1470 candidates.append((pattern[0][0], pattern[1][0]))1471 else:1472 multiple_patterns.append(pattern)1473 1474 multiple_patterns.sort(key=lambda pattern: len(pattern[0]) * len(pattern[1]))1475 1476 for pattern in multiple_patterns:1477 if len(candidates) + len(pattern[0]) * len(pattern[1]) > 2 * (1478 len(lhs) + len(rhs)1479 ):1480 break1481 for lhs_idx in pattern[0]:1482 for rhs_idx in pattern[1]:1483 candidates.append((lhs_idx, rhs_idx))1484 1485 if not candidates:1486 # The LHS and RHS either share nothing in common, or lines are just too1487 # identical. In that case, let's give up and not match anything.1488 return []1489 1490 # Compute a maximal crossing-free matching via an algorithm that is1491 # inspired by a mixture of dynamic programming and line-sweeping in1492 # discrete geometry.1493 #1494 # I would be surprised if this algorithm didn't exist somewhere in the1495 # literature, but I found it without consciously recalling any1496 # references, so you'll have to make do with the explanation below.1497 # Sorry.1498 #1499 # The underlying graph is bipartite:1500 # - nodes on the LHS represent lines in the original check1501 # - nodes on the RHS represent lines in the new (updated) check1502 #1503 # Nodes are implicitly sorted by the corresponding line number.1504 # Edges (unique_matches) are sorted by the line number on the LHS.1505 #1506 # Here's the geometric intuition for the algorithm.1507 #1508 # * Plot the edges as points in the plane, with the original line1509 # number on the X axis and the updated line number on the Y axis.1510 # * The goal is to find a longest "chain" of points where each point1511 # is strictly above and to the right of the previous point.1512 # * The algorithm proceeds by sweeping a vertical line from left to1513 # right.1514 # * The algorithm maintains a table where `table[N]` answers the1515 # question "What is currently the 'best' way to build a chain of N+11516 # points to the left of the vertical line". Here, 'best' means1517 # that the last point of the chain is a as low as possible (minimal1518 # Y coordinate).1519 # * `table[N]` is `(y, point_idx)` where `point_idx` is the index of1520 # the last point in the chain and `y` is its Y coordinate1521 # * A key invariant is that the Y values in the table are1522 # monotonically increasing1523 # * Thanks to these properties, the table can be used to answer the1524 # question "What is the longest chain that can be built to the left1525 # of the vertical line using only points below a certain Y value",1526 # using a binary search over the table.1527 # * The algorithm also builds a backlink structure in which every point1528 # links back to the previous point on a best (longest) chain ending1529 # at that point1530 #1531 # The core loop of the algorithm sweeps the line and updates the table1532 # and backlink structure for every point that we cross during the sweep.1533 # Therefore, the algorithm is trivially O(M log M) in the number of1534 # points.1535 candidates.sort(key=lambda candidate: (candidate[0], -candidate[1]))1536 1537 backlinks = []1538 table_rhs_idx = []1539 table_candidate_idx = []1540 for _, rhs_idx in candidates:1541 candidate_idx = len(backlinks)1542 ti = bisect.bisect_left(table_rhs_idx, rhs_idx)1543 1544 # Update the table to record a best chain ending in the current point.1545 # There always is one, and if any of the previously visited points had1546 # a higher Y coordinate, then there is always a previously recorded best1547 # chain that can be improved upon by using the current point.1548 #1549 # There is only one case where there is some ambiguity. If the1550 # pre-existing entry table[ti] has the same Y coordinate / rhs_idx as1551 # the current point (this can only happen if the same line appeared1552 # multiple times on the LHS), then we could choose to keep the1553 # previously recorded best chain instead. That would bias the algorithm1554 # differently but should have no systematic impact on the quality of the1555 # result.1556 if ti < len(table_rhs_idx):1557 table_rhs_idx[ti] = rhs_idx1558 table_candidate_idx[ti] = candidate_idx1559 else:1560 table_rhs_idx.append(rhs_idx)1561 table_candidate_idx.append(candidate_idx)1562 if ti > 0:1563 backlinks.append(table_candidate_idx[ti - 1])1564 else:1565 backlinks.append(None)1566 1567 # Commit to names in the matching by walking the backlinks. Recursively1568 # attempt to fill in more matches in-between.1569 match_idx = table_candidate_idx[-1]1570 while match_idx is not None:1571 current = candidates[match_idx]1572 matches.append(current)1573 match_idx = backlinks[match_idx]1574 1575 matches.reverse()1576 return matches1577 1578 1579VARIABLE_TAG = "[[@@]]"1580METAVAR_RE = re.compile(r"\[\[([A-Z0-9_]+)(?::[^]]+)?\]\]")1581NUMERIC_SUFFIX_RE = re.compile(r"[0-9]*$")1582 1583 1584class TestVar:1585 def __init__(self, nameless_value: NamelessValue, prefix: str, suffix: str):1586 self._nameless_value = nameless_value1587 1588 self._prefix = prefix1589 self._suffix = suffix1590 1591 def seen(self, nameless_value: NamelessValue, prefix: str, suffix: str):1592 if prefix != self._prefix:1593 self._prefix = ""1594 if suffix != self._suffix:1595 self._suffix = ""1596 1597 def get_variable_name(self, text):1598 return self._nameless_value.get_value_name(1599 text, self._nameless_value.check_prefix1600 )1601 1602 def get_def(self, name, prefix, suffix):1603 if self._nameless_value.is_number:1604 return f"{prefix}[[#{name}:]]{suffix}"1605 if self._prefix:1606 assert self._prefix == prefix1607 prefix = ""1608 if self._suffix:1609 assert self._suffix == suffix1610 suffix = ""1611 return f"{prefix}[[{name}:{self._prefix}{self._nameless_value.get_ir_regex()}{self._suffix}]]{suffix}"1612 1613 def get_use(self, name, prefix, suffix):1614 if self._nameless_value.is_number:1615 return f"{prefix}[[#{name}]]{suffix}"1616 if self._prefix:1617 assert self._prefix == prefix1618 prefix = ""1619 if self._suffix:1620 assert self._suffix == suffix1621 suffix = ""1622 return f"{prefix}[[{name}]]{suffix}"1623 1624 1625class CheckValueInfo:1626 def __init__(1627 self,1628 key,1629 text,1630 name: str,1631 prefix: str,1632 suffix: str,1633 ):1634 # Key for the value, e.g. '%'1635 self.key = key1636 1637 # Text to be matched by the FileCheck variable (without any prefix or suffix)1638 self.text = text1639 1640 # Name of the FileCheck variable1641 self.name = name1642 1643 # Prefix and suffix that were captured by the NamelessValue regular expression1644 self.prefix = prefix1645 self.suffix = suffix1646 1647 1648# Represent a check line in a way that allows us to compare check lines while1649# ignoring some or all of the FileCheck variable names.1650class CheckLineInfo:1651 def __init__(self, line, values):1652 # Line with all FileCheck variable name occurrences replaced by VARIABLE_TAG1653 self.line: str = line1654 1655 # Information on each FileCheck variable name occurrences in the line1656 self.values: List[CheckValueInfo] = values1657 1658 def __repr__(self):1659 return f"CheckLineInfo(line={self.line}, self.values={self.values})"1660 1661 1662def remap_metavar_names(1663 old_line_infos: List[CheckLineInfo],1664 new_line_infos: List[CheckLineInfo],1665 committed_names: Set[str],1666) -> Mapping[str, str]:1667 """1668 Map all FileCheck variable names that appear in new_line_infos to new1669 FileCheck variable names in an attempt to reduce the diff from old_line_infos1670 to new_line_infos.1671 1672 This is done by:1673 * Matching old check lines and new check lines using a diffing algorithm1674 applied after replacing names with wildcards.1675 * Committing to variable names such that the matched lines become equal1676 (without wildcards) if possible1677 * This is done recursively to handle cases where many lines are equal1678 after wildcard replacement1679 """1680 # Initialize uncommitted identity mappings1681 new_mapping = {}1682 for line in new_line_infos:1683 for value in line.values:1684 new_mapping[value.name] = value.name1685 1686 # Recursively commit to the identity mapping or find a better one1687 def recurse(old_begin, old_end, new_begin, new_end):1688 if old_begin == old_end or new_begin == new_end:1689 return1690 1691 # Find a matching of lines where uncommitted names are replaced1692 # with a placeholder.1693 def diffify_line(line, mapper):1694 values = []1695 for value in line.values:1696 mapped = mapper(value.name)1697 values.append(mapped if mapped in committed_names else "?")1698 return line.line.strip() + " @@@ " + " @ ".join(values)1699 1700 lhs_lines = [1701 diffify_line(line, lambda x: x)1702 for line in old_line_infos[old_begin:old_end]1703 ]1704 rhs_lines = [1705 diffify_line(line, lambda x: new_mapping[x])1706 for line in new_line_infos[new_begin:new_end]1707 ]1708 1709 candidate_matches = find_diff_matching(lhs_lines, rhs_lines)1710 1711 candidate_matches = [1712 (old_begin + lhs_idx, new_begin + rhs_idx)1713 for lhs_idx, rhs_idx in candidate_matches1714 ]1715 1716 # Candidate matches may conflict if they require conflicting mappings of1717 # names. We want to determine a large set of compatible candidates,1718 # because that leads to a small diff.1719 #1720 # We think of the candidates as vertices in a conflict graph. The1721 # conflict graph has edges between incompatible candidates. We want to1722 # find a large independent set in this graph.1723 #1724 # Greedily selecting candidates and removing incompatible ones has the1725 # disadvantage that making few bad decisions early on can have huge1726 # consequences.1727 #1728 # Instead, we implicitly compute multiple independent sets by greedily1729 # assigning a *coloring* to the conflict graph. Then, we select the1730 # largest color class (which is the largest independent set we found),1731 # commit to all candidates in it, and recurse.1732 #1733 # Note that we don't actually materialize the conflict graph. Instead,1734 # each color class tracks the information needed to decide implicitly1735 # whether a vertex conflicts (has an edge to) any of the vertices added1736 # to the color class so far.1737 class Color:1738 def __init__(self):1739 # (lhs_idx, rhs_idx) of matches in this color1740 self.matches = []1741 1742 # rhs_name -> lhs_name mappings required by this color1743 self.mapping = {}1744 1745 # lhs_names committed for this color1746 self.committed = set()1747 1748 colors = []1749 1750 for lhs_idx, rhs_idx in candidate_matches:1751 lhs_line = old_line_infos[lhs_idx]1752 rhs_line = new_line_infos[rhs_idx]1753 1754 # We scan through the uncommitted names in the candidate line and1755 # filter out the color classes to which the candidate could be1756 # assigned.1757 #1758 # Simultaneously, we prepare a new color class in case the candidate1759 # conflicts with all colors that have been established so far.1760 compatible_colors = colors[:]1761 new_color = Color()1762 new_color.matches.append((lhs_idx, rhs_idx))1763 1764 for lhs_value, rhs_value in zip(lhs_line.values, rhs_line.values):1765 if new_mapping[rhs_value.name] in committed_names:1766 # The new value has already been committed. If it was mapped1767 # to the same name as the original value, we can consider1768 # committing other values from this line. Otherwise, we1769 # should ignore this line.1770 if new_mapping[rhs_value.name] == lhs_value.name:1771 continue1772 else:1773 break1774 1775 if rhs_value.name in new_color.mapping:1776 # Same, but for a possible commit happening on the same line1777 if new_color.mapping[rhs_value.name] == lhs_value.name:1778 continue1779 else:1780 break1781 1782 if (1783 lhs_value.name in committed_names1784 or lhs_value.name in new_color.committed1785 ):1786 # We can't map this value because the name we would map it1787 # to has already been committed for something else. Give up1788 # on this line.1789 break1790 1791 new_color.mapping[rhs_value.name] = lhs_value.name1792 new_color.committed.add(lhs_value.name)1793 1794 color_idx = 01795 while color_idx < len(compatible_colors):1796 color = compatible_colors[color_idx]1797 compatible = True1798 if rhs_value.name in color.mapping:1799 compatible = color.mapping[rhs_value.name] == lhs_value.name1800 else:1801 compatible = lhs_value.name not in color.committed1802 if compatible:1803 color_idx += 11804 else:1805 del compatible_colors[color_idx]1806 else:1807 # We never broke out of the loop, which means that at a minimum,1808 # this line is viable standalone1809 if compatible_colors:1810 color = max(compatible_colors, key=lambda color: len(color.matches))1811 color.mapping.update(new_color.mapping)1812 color.committed.update(new_color.committed)1813 color.matches.append((lhs_idx, rhs_idx))1814 else:1815 colors.append(new_color)1816 1817 if colors:1818 # Pick the largest color class. This gives us a large independent1819 # (non-conflicting) set of candidate matches. Assign all names1820 # required by the independent set and recurse.1821 max_color = max(colors, key=lambda color: len(color.matches))1822 1823 for rhs_var, lhs_var in max_color.mapping.items():1824 new_mapping[rhs_var] = lhs_var1825 committed_names.add(lhs_var)1826 1827 if (1828 lhs_var != rhs_var1829 and lhs_var in new_mapping1830 and new_mapping[lhs_var] == lhs_var1831 ):1832 new_mapping[lhs_var] = "conflict_" + lhs_var1833 1834 matches = (1835 [(old_begin - 1, new_begin - 1)]1836 + max_color.matches1837 + [(old_end, new_end)]1838 )1839 1840 for (lhs_prev, rhs_prev), (lhs_next, rhs_next) in zip(matches, matches[1:]):1841 recurse(lhs_prev + 1, lhs_next, rhs_prev + 1, rhs_next)1842 1843 recurse(0, len(old_line_infos), 0, len(new_line_infos))1844 1845 # Commit to remaining names and resolve conflicts1846 for new_name, mapped_name in new_mapping.items():1847 if mapped_name in committed_names:1848 continue1849 if not mapped_name.startswith("conflict_"):1850 assert mapped_name == new_name1851 committed_names.add(mapped_name)1852 1853 for new_name, mapped_name in new_mapping.items():1854 if mapped_name in committed_names:1855 continue1856 assert mapped_name.startswith("conflict_")1857 1858 m = NUMERIC_SUFFIX_RE.search(new_name)1859 base_name = new_name[: m.start()]1860 suffix = int(new_name[m.start() :]) if m.start() != m.end() else 11861 while True:1862 candidate = f"{base_name}{suffix}"1863 if candidate not in committed_names:1864 new_mapping[new_name] = candidate1865 committed_names.add(candidate)1866 break1867 suffix += 11868 1869 return new_mapping1870 1871 1872def generalize_check_lines(1873 lines,1874 ginfo: GeneralizerInfo,1875 vars_seen,1876 global_vars_seen,1877 global_tbaa_records={},1878 preserve_names=False,1879 original_check_lines=None,1880 *,1881 unstable_globals_only=False,1882 no_meta_details=False,1883 ignore_all_comments=True, # If False, only ignore comments of predecessors1884):1885 if unstable_globals_only:1886 regexp = ginfo.get_unstable_globals_regexp()1887 else:1888 regexp = ginfo.get_regexp()1889 1890 multiple_braces_re = re.compile(r"({{+)|(}}+)")1891 1892 def escape_braces(match_obj):1893 return "{{" + re.escape(match_obj.group(0)) + "}}"1894 1895 if ginfo.is_ir():1896 for i, line in enumerate(lines):1897 # An IR variable named '%.' matches the FileCheck regex string.1898 line = line.replace("%.", "%dot")1899 for regex in _global_hex_value_regex:1900 if re.match("^@" + regex + " = ", line):1901 line = re.sub(1902 r"\bi([0-9]+) ([0-9]+)",1903 lambda m: "i"1904 + m.group(1)1905 + " [[#"1906 + hex(int(m.group(2)))1907 + "]]",1908 line,1909 )1910 break1911 if ignore_all_comments:1912 # Ignore any comments, since the check lines will too.1913 scrubbed_line = SCRUB_IR_COMMENT_RE.sub(r"", line)1914 else:1915 # Ignore comments of predecessors only.1916 scrubbed_line = SCRUB_PRED_COMMENT_RE.sub(r"", line)1917 # Ignore the metadata details if check global is none1918 if no_meta_details:1919 scrubbed_line = SCRUB_IR_FUNC_META_RE.sub(r"{{.*}}", scrubbed_line)1920 lines[i] = scrubbed_line1921 1922 if not preserve_names:1923 committed_names = set(1924 test_var.get_variable_name(name)1925 for (name, _), test_var in vars_seen.items()1926 )1927 defs = set()1928 1929 # Collect information about new check lines, and generalize global reference1930 new_line_infos = []1931 for line in lines:1932 filtered_line = ""1933 values = []1934 while True:1935 m = regexp.search(line)1936 if m is None:1937 filtered_line += line1938 break1939 1940 name = ginfo.get_name_from_match(m)1941 nameless_value = ginfo.get_nameless_value_from_match(m)1942 prefix, suffix = nameless_value.get_affixes_from_match(m)1943 if may_clash_with_default_check_prefix_name(1944 nameless_value.check_prefix, name1945 ):1946 warn(1947 "Change IR value name '%s' or use --prefix-filecheck-ir-name to prevent possible conflict"1948 " with scripted FileCheck name." % (name,)1949 )1950 1951 # Record the variable as seen and (for locals) accumulate1952 # prefixes/suffixes1953 is_local_def = nameless_value.is_local_def_ir_value()1954 if is_local_def:1955 vars_dict = vars_seen1956 else:1957 vars_dict = global_vars_seen1958 1959 key = (name, nameless_value.check_key)1960 1961 if is_local_def:1962 test_prefix = prefix1963 test_suffix = suffix1964 else:1965 test_prefix = ""1966 test_suffix = ""1967 1968 if key in vars_dict:1969 vars_dict[key].seen(nameless_value, test_prefix, test_suffix)1970 else:1971 vars_dict[key] = TestVar(nameless_value, test_prefix, test_suffix)1972 defs.add(key)1973 1974 var = vars_dict[key].get_variable_name(name)1975 1976 # Replace with a [[@@]] tag, but be sure to keep the spaces and commas.1977 filtered_line += (1978 line[: m.start()] + m.group(1) + VARIABLE_TAG + m.group(m.lastindex)1979 )1980 line = line[m.end() :]1981 1982 values.append(1983 CheckValueInfo(1984 key=nameless_value.check_key,1985 text=name,1986 name=var,1987 prefix=prefix,1988 suffix=suffix,1989 )1990 )1991 1992 new_line_infos.append(CheckLineInfo(filtered_line, values))1993 1994 committed_names.update(1995 test_var.get_variable_name(name)1996 for (name, _), test_var in global_vars_seen.items()1997 )1998 1999 # Collect information about original check lines, if any.2000 orig_line_infos = []2001 for line in original_check_lines or []:2002 filtered_line = ""2003 values = []2004 while True:2005 m = METAVAR_RE.search(line)2006 if m is None:2007 filtered_line += line2008 break2009 2010 # Replace with a [[@@]] tag, but be sure to keep the spaces and commas.2011 filtered_line += line[: m.start()] + VARIABLE_TAG2012 line = line[m.end() :]2013 values.append(2014 CheckValueInfo(2015 key=None,2016 text=None,2017 name=m.group(1),2018 prefix="",2019 suffix="",2020 )2021 )2022 orig_line_infos.append(CheckLineInfo(filtered_line, values))2023 2024 # Compute the variable name mapping2025 mapping = remap_metavar_names(orig_line_infos, new_line_infos, committed_names)2026 2027 # Apply the variable name mapping2028 for i, line_info in enumerate(new_line_infos):2029 line_template = line_info.line2030 line = ""2031 2032 for value in line_info.values:2033 idx = line_template.find(VARIABLE_TAG)2034 line += line_template[:idx]2035 line_template = line_template[idx + len(VARIABLE_TAG) :]2036 2037 key = (value.text, value.key)2038 if value.key == "%":2039 vars_dict = vars_seen2040 else:2041 vars_dict = global_vars_seen2042 2043 mapped_name = mapping[value.name]2044 2045 # We have computed the name mapping. Now, if possible,2046 # substitute the TBAA value name with its semantics.2047 if ginfo.get_version() >= 6:2048 if (2049 value.key == "!"2050 and global_tbaa_records2051 and mapped_name.startswith("TBAA")2052 and mapped_name[4:].isdigit()2053 ):2054 tbaa_sema = global_tbaa_records.get(value.text)2055 assert tbaa_sema, f"Shouldn't miss TBAA name for {value.text}?"2056 mapped_name = f"{tbaa_sema}{mapped_name[4:]}"2057 2058 if key in defs:2059 line += vars_dict[key].get_def(2060 mapped_name, value.prefix, value.suffix2061 )2062 defs.remove(key)2063 else:2064 line += vars_dict[key].get_use(2065 mapped_name, value.prefix, value.suffix2066 )2067 2068 line += line_template2069 2070 lines[i] = line2071 2072 if ginfo.is_analyze():2073 for i, _ in enumerate(lines):2074 # Escape multiple {{ or }} as {{}} denotes a FileCheck regex.2075 scrubbed_line = multiple_braces_re.sub(escape_braces, lines[i])2076 lines[i] = scrubbed_line2077 2078 return lines2079 2080 2081def add_checks(2082 output_lines,2083 comment_marker,2084 prefix_list,2085 func_dict,2086 func_name,2087 check_label_format,2088 ginfo,2089 global_vars_seen_dict,2090 is_filtered,2091 global_tbaa_records_for_prefixes={},2092 preserve_names=False,2093 original_check_lines: Mapping[str, List[str]] = {},2094 check_inst_comments=True,2095):2096 # prefix_exclusions are prefixes we cannot use to print the function because it doesn't exist in run lines that use these prefixes as well.2097 prefix_exclusions = set()2098 printed_prefixes = []2099 for p in prefix_list:2100 checkprefixes = p[0]2101 # If not all checkprefixes of this run line produced the function we cannot check for it as it does not2102 # exist for this run line. A subset of the check prefixes might know about the function but only because2103 # other run lines created it.2104 if any(2105 map(2106 lambda checkprefix: func_name not in func_dict[checkprefix],2107 checkprefixes,2108 )2109 ):2110 prefix_exclusions |= set(checkprefixes)2111 continue2112 2113 # prefix_exclusions is constructed, we can now emit the output2114 for p in prefix_list:2115 global_vars_seen = {}2116 checkprefixes = p[0]2117 for checkprefix in checkprefixes:2118 if checkprefix in global_vars_seen_dict:2119 global_vars_seen.update(global_vars_seen_dict[checkprefix])2120 else:2121 global_vars_seen_dict[checkprefix] = {}2122 if checkprefix in printed_prefixes:2123 break2124 2125 # Check if the prefix is excluded.2126 if checkprefix in prefix_exclusions:2127 continue2128 2129 # If we do not have output for this prefix we skip it.2130 if not func_dict[checkprefix][func_name]:2131 continue2132 2133 # Add some space between different check prefixes, but not after the last2134 # check line (before the test code).2135 if ginfo.is_asm():2136 if len(printed_prefixes) != 0:2137 output_lines.append(comment_marker)2138 2139 if checkprefix not in global_vars_seen_dict:2140 global_vars_seen_dict[checkprefix] = {}2141 2142 global_vars_seen_before = [key for key in global_vars_seen.keys()]2143 global_tbaa_records = next(2144 (2145 val2146 for key, val in global_tbaa_records_for_prefixes.items()2147 if checkprefix in key2148 ),2149 None,2150 )2151 2152 vars_seen = {}2153 printed_prefixes.append(checkprefix)2154 attrs = str(func_dict[checkprefix][func_name].attrs)2155 attrs = "" if attrs == "None" else attrs2156 if ginfo.get_version() > 1:2157 funcdef_attrs_and_ret = func_dict[checkprefix][2158 func_name2159 ].funcdef_attrs_and_ret2160 else:2161 funcdef_attrs_and_ret = ""2162 2163 if attrs:2164 output_lines.append(2165 "%s %s: Function Attrs: %s" % (comment_marker, checkprefix, attrs)2166 )2167 args_and_sig = str(func_dict[checkprefix][func_name].args_and_sig)2168 if args_and_sig:2169 args_and_sig = generalize_check_lines(2170 [args_and_sig],2171 ginfo,2172 vars_seen,2173 global_vars_seen,2174 global_tbaa_records,2175 preserve_names,2176 original_check_lines=[],2177 no_meta_details=ginfo.no_meta_details(),2178 )[0]2179 func_name_separator = func_dict[checkprefix][func_name].func_name_separator2180 if "[[" in args_and_sig:2181 # Captures in label lines are not supported, thus split into a -LABEL2182 # and a separate -SAME line that contains the arguments with captures.2183 args_and_sig_prefix = ""2184 if ginfo.get_version() >= 3 and args_and_sig.startswith("("):2185 # Ensure the "(" separating function name and arguments is in the2186 # label line. This is required in case of function names that are2187 # prefixes of each other. Otherwise, the label line for "foo" might2188 # incorrectly match on "foo.specialized".2189 args_and_sig_prefix = args_and_sig[0]2190 args_and_sig = args_and_sig[1:]2191 2192 # Removing args_and_sig from the label match line requires2193 # func_name_separator to be empty. Otherwise, the match will not work.2194 assert func_name_separator == ""2195 output_lines.append(2196 check_label_format2197 % (2198 checkprefix,2199 funcdef_attrs_and_ret,2200 func_name,2201 args_and_sig_prefix,2202 func_name_separator,2203 )2204 )2205 output_lines.append(2206 "%s %s-SAME: %s" % (comment_marker, checkprefix, args_and_sig)2207 )2208 else:2209 output_lines.append(2210 check_label_format2211 % (2212 checkprefix,2213 funcdef_attrs_and_ret,2214 func_name,2215 args_and_sig,2216 func_name_separator,2217 )2218 )2219 func_body = str(func_dict[checkprefix][func_name]).splitlines()2220 if not func_body:2221 # We have filtered everything.2222 continue2223 2224 # For ASM output, just emit the check lines.2225 if ginfo.is_asm():2226 body_start = 12227 if is_filtered:2228 # For filtered output we don't add "-NEXT" so don't add extra spaces2229 # before the first line.2230 body_start = 02231 else:2232 output_lines.append(2233 "%s %s: %s" % (comment_marker, checkprefix, func_body[0])2234 )2235 func_lines = generalize_check_lines(2236 func_body[body_start:], ginfo, vars_seen, global_vars_seen2237 )2238 for func_line in func_lines:2239 if func_line.strip() == "":2240 output_lines.append(2241 "%s %s-EMPTY:" % (comment_marker, checkprefix)2242 )2243 else:2244 check_suffix = "-NEXT" if not is_filtered else ""2245 output_lines.append(2246 "%s %s%s: %s"2247 % (comment_marker, checkprefix, check_suffix, func_line)2248 )2249 # Remember new global variables we have not seen before2250 for key in global_vars_seen:2251 if key not in global_vars_seen_before:2252 global_vars_seen_dict[checkprefix][key] = global_vars_seen[key]2253 break2254 # For analyze output, generalize the output, and emit CHECK-EMPTY lines as well.2255 elif ginfo.is_analyze():2256 func_body = generalize_check_lines(2257 func_body, ginfo, vars_seen, global_vars_seen2258 )2259 for func_line in func_body:2260 if func_line.strip() == "":2261 output_lines.append(2262 "{} {}-EMPTY:".format(comment_marker, checkprefix)2263 )2264 else:2265 check_suffix = "-NEXT" if not is_filtered else ""2266 output_lines.append(2267 "{} {}{}: {}".format(2268 comment_marker, checkprefix, check_suffix, func_line2269 )2270 )2271 2272 # Add space between different check prefixes and also before the first2273 # line of code in the test function.2274 output_lines.append(comment_marker)2275 2276 # Remember new global variables we have not seen before2277 for key in global_vars_seen:2278 if key not in global_vars_seen_before:2279 global_vars_seen_dict[checkprefix][key] = global_vars_seen[key]2280 break2281 # For IR output, change all defs to FileCheck variables, so we're immune2282 # to variable naming fashions.2283 else:2284 if ginfo.get_version() >= 7:2285 # Record the indices of blank lines in the function body preemptively.2286 blank_line_indices = {2287 i for i, line in enumerate(func_body) if line.strip() == ""2288 }2289 else:2290 blank_line_indices = set()2291 2292 func_body = generalize_check_lines(2293 func_body,2294 ginfo,2295 vars_seen,2296 global_vars_seen,2297 global_tbaa_records,2298 preserve_names,2299 original_check_lines=original_check_lines.get(checkprefix),2300 # IR output might require comments checks, e.g., print-predicate-info, print<memssa>2301 ignore_all_comments=not check_inst_comments,2302 )2303 2304 # This could be selectively enabled with an optional invocation argument.2305 # Disabled for now: better to check everything. Be safe rather than sorry.2306 2307 # Handle the first line of the function body as a special case because2308 # it's often just noise (a useless asm comment or entry label).2309 # if func_body[0].startswith("#") or func_body[0].startswith("entry:"):2310 # is_blank_line = True2311 # else:2312 # output_lines.append('%s %s: %s' % (comment_marker, checkprefix, func_body[0]))2313 # is_blank_line = False2314 2315 is_blank_line = False2316 2317 for idx, func_line in enumerate(func_body):2318 if func_line.strip() == "":2319 # We should distinguish if the line is a 'fake' blank line generated by2320 # generalize_check_lines removing comments.2321 # Fortunately, generalize_check_lines does not change the index of each line,2322 # we can record the indices of blank lines preemptively.2323 if idx in blank_line_indices:2324 output_lines.append(2325 "{} {}-EMPTY:".format(comment_marker, checkprefix)2326 )2327 else:2328 is_blank_line = True2329 continue2330 if not check_inst_comments:2331 # Do not waste time checking IR comments unless necessary.2332 func_line = SCRUB_IR_COMMENT_RE.sub(r"", func_line)2333 2334 # Skip blank lines instead of checking them.2335 if is_blank_line:2336 output_lines.append(2337 "{} {}: {}".format(2338 comment_marker, checkprefix, func_line2339 )2340 )2341 else:2342 check_suffix = "-NEXT" if not is_filtered else ""2343 output_lines.append(2344 "{} {}{}: {}".format(2345 comment_marker, checkprefix, check_suffix, func_line2346 )2347 )2348 is_blank_line = False2349 2350 # Add space between different check prefixes and also before the first2351 # line of code in the test function.2352 output_lines.append(comment_marker)2353 2354 # Remember new global variables we have not seen before2355 for key in global_vars_seen:2356 if key not in global_vars_seen_before:2357 global_vars_seen_dict[checkprefix][key] = global_vars_seen[key]2358 break2359 return printed_prefixes2360 2361 2362def add_ir_checks(2363 output_lines,2364 comment_marker,2365 prefix_list,2366 func_dict,2367 func_name,2368 preserve_names,2369 function_sig,2370 ginfo: GeneralizerInfo,2371 global_vars_seen_dict,2372 global_tbaa_records_for_prefixes,2373 is_filtered,2374 check_inst_comments=False,2375 original_check_lines={},2376):2377 assert ginfo.is_ir()2378 # Label format is based on IR string.2379 if function_sig and ginfo.get_version() > 1:2380 function_def_regex = "define %s"2381 elif function_sig:2382 function_def_regex = "define {{[^@]+}}%s"2383 else:2384 function_def_regex = "%s"2385 check_label_format = "{} %s-LABEL: {}@%s%s%s".format(2386 comment_marker, function_def_regex2387 )2388 return add_checks(2389 output_lines,2390 comment_marker,2391 prefix_list,2392 func_dict,2393 func_name,2394 check_label_format,2395 ginfo,2396 global_vars_seen_dict,2397 is_filtered,2398 global_tbaa_records_for_prefixes,2399 preserve_names,2400 original_check_lines=original_check_lines,2401 check_inst_comments=check_inst_comments,2402 )2403 2404 2405def add_analyze_checks(2406 output_lines,2407 comment_marker,2408 prefix_list,2409 func_dict,2410 func_name,2411 ginfo: GeneralizerInfo,2412 is_filtered,2413):2414 assert ginfo.is_analyze()2415 check_label_format = "{} %s-LABEL: '%s%s%s%s'".format(comment_marker)2416 global_vars_seen_dict = {}2417 return add_checks(2418 output_lines,2419 comment_marker,2420 prefix_list,2421 func_dict,2422 func_name,2423 check_label_format,2424 ginfo,2425 global_vars_seen_dict,2426 is_filtered,2427 )2428 2429 2430def build_global_values_dictionary(glob_val_dict, raw_tool_output, prefixes, ginfo):2431 for nameless_value in ginfo.get_nameless_values():2432 if nameless_value.global_ir_rhs_regexp is None:2433 continue2434 2435 lhs_re_str = nameless_value.ir_prefix + nameless_value.ir_regexp2436 rhs_re_str = nameless_value.global_ir_rhs_regexp2437 2438 global_ir_value_re_str = r"^" + lhs_re_str + r"\s=\s" + rhs_re_str + r"$"2439 global_ir_value_re = re.compile(global_ir_value_re_str, flags=(re.M))2440 lines = []2441 for m in global_ir_value_re.finditer(raw_tool_output):2442 # Attach the substring's start index so that CHECK lines2443 # can be sorted properly even if they are matched by different nameless values.2444 # This is relevant for GLOB and GLOBNAMED since they may appear interlaced.2445 lines.append((m.start(), m.group(0)))2446 2447 for prefix in prefixes:2448 if glob_val_dict[prefix] is None:2449 continue2450 if nameless_value.check_prefix in glob_val_dict[prefix]:2451 if lines == glob_val_dict[prefix][nameless_value.check_prefix]:2452 continue2453 if prefix == prefixes[-1]:2454 warn("Found conflicting asm under the same prefix: %r!" % (prefix,))2455 else:2456 glob_val_dict[prefix][nameless_value.check_prefix] = None2457 continue2458 glob_val_dict[prefix][nameless_value.check_prefix] = lines2459 2460 2461def filter_globals_according_to_preference(2462 global_val_lines_w_index, global_vars_seen, nameless_value, global_check_setting2463):2464 if global_check_setting == "none":2465 return []2466 if global_check_setting == "all":2467 return global_val_lines_w_index2468 assert global_check_setting == "smart"2469 2470 if nameless_value.check_key == "#":2471 # attribute sets are usually better checked by --check-attributes2472 return []2473 2474 def extract(line, nv):2475 p = (2476 "^"2477 + nv.ir_prefix2478 + "("2479 + nv.ir_regexp2480 + ") = ("2481 + nv.global_ir_rhs_regexp2482 + ")"2483 )2484 match = re.match(p, line)2485 return (match.group(1), re.findall(nv.ir_regexp, match.group(2)))2486 2487 transitively_visible = set()2488 contains_refs_to = {}2489 2490 def add(var):2491 nonlocal transitively_visible2492 nonlocal contains_refs_to2493 if var in transitively_visible:2494 return2495 transitively_visible.add(var)2496 if not var in contains_refs_to:2497 return2498 for x in contains_refs_to[var]:2499 add(x)2500 2501 for i, line in global_val_lines_w_index:2502 (var, refs) = extract(line, nameless_value)2503 contains_refs_to[var] = refs2504 for var, check_key in global_vars_seen:2505 if check_key != nameless_value.check_key:2506 continue2507 add(var)2508 return [2509 (i, line)2510 for i, line in global_val_lines_w_index2511 if extract(line, nameless_value)[0] in transitively_visible2512 ]2513 2514 2515METADATA_FILTERS = [2516 (2517 r"(?<=\")(.+ )?(\w+ version )[\d.]+(?:[^\" ]*)(?: \([^)]+\))?",2518 r"{{.*}}\2{{.*}}",2519 ), # preface with glob also, to capture optional CLANG_VENDOR2520 (r'(!DIFile\(filename: ")(.+/)?([^/]+", directory: )".+"', r"\1{{.*}}\3{{.*}}"),2521]2522METADATA_FILTERS_RE = [(re.compile(f), r) for (f, r) in METADATA_FILTERS]2523 2524 2525def filter_unstable_metadata(line):2526 for f, replacement in METADATA_FILTERS_RE:2527 line = f.sub(replacement, line)2528 return line2529 2530 2531def flush_current_checks(output_lines, new_lines_w_index, comment_marker):2532 if not new_lines_w_index:2533 return2534 output_lines.append(comment_marker + SEPARATOR)2535 new_lines_w_index.sort()2536 for _, line in new_lines_w_index:2537 output_lines.append(line)2538 new_lines_w_index.clear()2539 2540 2541def add_global_checks(2542 glob_val_dict,2543 comment_marker,2544 prefix_list,2545 output_lines,2546 ginfo: GeneralizerInfo,2547 global_vars_seen_dict,2548 global_tbaa_records_for_prefixes,2549 preserve_names,2550 is_before_functions,2551 global_check_setting,2552):2553 printed_prefixes = set()2554 output_lines_loc = {} # Allows GLOB and GLOBNAMED to be sorted correctly2555 for nameless_value in ginfo.get_nameless_values():2556 if nameless_value.global_ir_rhs_regexp is None:2557 continue2558 if nameless_value.is_before_functions != is_before_functions:2559 continue2560 for p in prefix_list:2561 global_vars_seen = {}2562 checkprefixes = p[0]2563 if checkprefixes is None:2564 continue2565 for checkprefix in checkprefixes:2566 if checkprefix in global_vars_seen_dict:2567 global_vars_seen.update(global_vars_seen_dict[checkprefix])2568 else:2569 global_vars_seen_dict[checkprefix] = {}2570 if (checkprefix, nameless_value.check_prefix) in printed_prefixes:2571 break2572 if not glob_val_dict[checkprefix]:2573 continue2574 if nameless_value.check_prefix not in glob_val_dict[checkprefix]:2575 continue2576 if not glob_val_dict[checkprefix][nameless_value.check_prefix]:2577 continue2578 2579 check_lines = []2580 global_vars_seen_before = [key for key in global_vars_seen.keys()]2581 global_tbaa_records = next(2582 (2583 val2584 for key, val in global_tbaa_records_for_prefixes.items()2585 if checkprefix in key2586 ),2587 None,2588 )2589 2590 lines_w_index = glob_val_dict[checkprefix][nameless_value.check_prefix]2591 lines_w_index = filter_globals_according_to_preference(2592 lines_w_index,2593 global_vars_seen_before,2594 nameless_value,2595 global_check_setting,2596 )2597 for i, line in lines_w_index:2598 if _global_value_regex:2599 matched = False2600 for regex in _global_value_regex:2601 if re.match("^@" + regex + " = ", line) or re.match(2602 "^!" + regex + " = ", line2603 ):2604 matched = True2605 break2606 if not matched:2607 continue2608 [new_line] = generalize_check_lines(2609 [line],2610 ginfo,2611 {},2612 global_vars_seen,2613 global_tbaa_records,2614 preserve_names,2615 unstable_globals_only=True,2616 )2617 new_line = filter_unstable_metadata(new_line)2618 check_line = "%s %s: %s" % (comment_marker, checkprefix, new_line)2619 check_lines.append((i, check_line))2620 if not check_lines:2621 continue2622 2623 if not checkprefix in output_lines_loc:2624 output_lines_loc[checkprefix] = []2625 if not nameless_value.interlaced_with_previous:2626 flush_current_checks(2627 output_lines, output_lines_loc[checkprefix], comment_marker2628 )2629 for check_line in check_lines:2630 output_lines_loc[checkprefix].append(check_line)2631 2632 printed_prefixes.add((checkprefix, nameless_value.check_prefix))2633 2634 # Remembe new global variables we have not seen before2635 for key in global_vars_seen:2636 if key not in global_vars_seen_before:2637 global_vars_seen_dict[checkprefix][key] = global_vars_seen[key]2638 break2639 2640 if printed_prefixes:2641 for p in prefix_list:2642 if p[0] is None:2643 continue2644 for checkprefix in p[0]:2645 if checkprefix not in output_lines_loc:2646 continue2647 flush_current_checks(2648 output_lines, output_lines_loc[checkprefix], comment_marker2649 )2650 break2651 output_lines.append(comment_marker + SEPARATOR)2652 return printed_prefixes2653 2654 2655def check_prefix(prefix):2656 if not PREFIX_RE.match(prefix):2657 hint = ""2658 if "," in prefix:2659 hint = " Did you mean '--check-prefixes=" + prefix + "'?"2660 warn(2661 (2662 "Supplied prefix '%s' is invalid. Prefix must contain only alphanumeric characters, hyphens and underscores."2663 + hint2664 )2665 % (prefix)2666 )2667 2668 2669def get_check_prefixes(filecheck_cmd):2670 check_prefixes = [2671 item2672 for m in CHECK_PREFIX_RE.finditer(filecheck_cmd)2673 for item in m.group(1).split(",")2674 ]2675 if not check_prefixes:2676 check_prefixes = ["CHECK"]2677 return check_prefixes2678 2679 2680def verify_filecheck_prefixes(fc_cmd):2681 fc_cmd_parts = fc_cmd.split()2682 for part in fc_cmd_parts:2683 if "check-prefix=" in part:2684 prefix = part.split("=", 1)[1]2685 check_prefix(prefix)2686 elif "check-prefixes=" in part:2687 prefixes = part.split("=", 1)[1].split(",")2688 for prefix in prefixes:2689 check_prefix(prefix)2690 if prefixes.count(prefix) > 1:2691 warn(2692 "Supplied prefix '%s' is not unique in the prefix list."2693 % (prefix,)2694 )2695 2696 2697def get_autogennote_suffix(parser, args):2698 autogenerated_note_args = ""2699 for action in parser._actions:2700 if not hasattr(args, action.dest):2701 continue # Ignore options such as --help that aren't included in args2702 # Ignore parameters such as paths to the binary or the list of tests2703 if action.dest in (2704 "tests",2705 "update_only",2706 "tool_binary",2707 "opt_binary",2708 "llc_binary",2709 "clang",2710 "opt",2711 "llvm_bin",2712 "verbose",2713 "force_update",2714 "reset_variable_names",2715 "llvm_mc_binary",2716 ):2717 continue2718 value = getattr(args, action.dest)2719 if action.dest == "check_globals":2720 default_value = "none" if args.version < 4 else "smart"2721 if value == default_value:2722 continue2723 autogenerated_note_args += action.option_strings[0] + " "2724 if args.version < 4 and value == "all":2725 continue2726 autogenerated_note_args += "%s " % value2727 continue2728 if action.const is not None: # action stores a constant (usually True/False)2729 # Skip actions with different constant values (this happens with boolean2730 # --foo/--no-foo options)2731 if value != action.const:2732 continue2733 if parser.get_default(action.dest) == value:2734 continue # Don't add default values2735 if action.dest == "function_signature" and args.version >= 2:2736 continue # Enabled by default in version 22737 if action.dest == "filters":2738 # Create a separate option for each filter element. The value is a list2739 # of Filter objects.2740 for elem in value:2741 if elem.is_filter_out:2742 opt_name = "filter-out"2743 elif elem.is_filter_out_after:2744 opt_name = "filter-out-after"2745 else:2746 opt_name = "filter"2747 opt_value = elem.pattern()2748 new_arg = '--%s "%s" ' % (opt_name, opt_value.strip('"'))2749 if new_arg not in autogenerated_note_args:2750 autogenerated_note_args += new_arg2751 else:2752 autogenerated_note_args += action.option_strings[0] + " "2753 if action.const is None: # action takes a parameter2754 if action.nargs == "+":2755 value = " ".join(map(lambda v: '"' + v.strip('"') + '"', value))2756 autogenerated_note_args += "%s " % value2757 if autogenerated_note_args:2758 autogenerated_note_args = " %s %s" % (2759 UTC_ARGS_KEY,2760 autogenerated_note_args[:-1],2761 )2762 return autogenerated_note_args2763 2764 2765def check_for_command(line, parser, args, argv, argparse_callback):2766 cmd_m = UTC_ARGS_CMD.match(line)2767 if cmd_m:2768 for option in shlex.split(cmd_m.group("cmd").strip()):2769 if option:2770 argv.append(option)2771 args = parse_args(parser, filter(lambda arg: arg not in args.tests, argv))2772 if argparse_callback is not None:2773 argparse_callback(args)2774 return args, argv2775 2776 2777def find_arg_in_test(test_info, get_arg_to_check, arg_string, is_global):2778 result = get_arg_to_check(test_info.args)2779 if not result and is_global:2780 # See if this has been specified via UTC_ARGS. This is a "global" option2781 # that affects the entire generation of test checks. If it exists anywhere2782 # in the test, apply it to everything.2783 saw_line = False2784 for line_info in test_info.ro_iterlines():2785 line = line_info.line2786 if not line.startswith(";") and line.strip() != "":2787 saw_line = True2788 result = get_arg_to_check(line_info.args)2789 if result:2790 if warn and saw_line:2791 # We saw the option after already reading some test input lines.2792 # Warn about it.2793 print(2794 "WARNING: Found {} in line following test start: ".format(2795 arg_string2796 )2797 + line,2798 file=sys.stderr,2799 )2800 print(2801 "WARNING: Consider moving {} to top of file".format(arg_string),2802 file=sys.stderr,2803 )2804 break2805 return result2806 2807 2808def dump_input_lines(output_lines, test_info, prefix_set, comment_string):2809 for input_line_info in test_info.iterlines(output_lines):2810 line = input_line_info.line2811 args = input_line_info.args2812 if line.strip() == comment_string:2813 continue2814 if line.strip() == comment_string + SEPARATOR:2815 continue2816 if line.lstrip().startswith(comment_string):2817 m = CHECK_RE.match(line)2818 if m and m.group(1) in prefix_set:2819 continue2820 output_lines.append(line.rstrip("\n"))2821 2822 2823def add_checks_at_end(2824 output_lines, prefix_list, func_order, comment_string, check_generator2825):2826 added = set()2827 generated_prefixes = set()2828 for prefix in prefix_list:2829 prefixes = prefix[0]2830 tool_args = prefix[1]2831 for prefix in prefixes:2832 for func in func_order[prefix]:2833 # The func order can contain the same functions multiple times.2834 # If we see one again we are done.2835 if (func, prefix) in added:2836 continue2837 if added:2838 output_lines.append(comment_string)2839 2840 # The add_*_checks routines expect a run list whose items are2841 # tuples that have a list of prefixes as their first element and2842 # tool command args string as their second element. They output2843 # checks for each prefix in the list of prefixes. By doing so, it2844 # implicitly assumes that for each function every run line will2845 # generate something for that function. That is not the case for2846 # generated functions as some run lines might not generate them2847 # (e.g. -fopenmp vs. no -fopenmp).2848 #2849 # Therefore, pass just the prefix we're interested in. This has2850 # the effect of generating all of the checks for functions of a2851 # single prefix before moving on to the next prefix. So checks2852 # are ordered by prefix instead of by function as in "normal"2853 # mode.2854 for generated_prefix in check_generator(2855 output_lines, [([prefix], tool_args)], func2856 ):2857 added.add((func, generated_prefix))2858 generated_prefixes.add(generated_prefix)2859 return generated_prefixes2860