With this patch, we always update Inserted. That's OK because we only
read Inserted as shown in this patch. Without this patch, it's a
write-only variable.
When we check for similarity, right now there is no order to how it is checked, except for via the suffix tree ordering.
We can reduce how much structural analysis we perform by checking the the regions in decreasing size. In doing so, we know that if two large sections match, each of their contained regions also match. This allows us to skip the structural checking for each smaller section. IT does require that we use the large regions as a "bridge" to create the canonical mapping between the two regions.
This reduces compile time significantly for some benchmarks. It will not perform as well for programs with many small items.
Recommit fixes the IRSimilarity tests.
Recommit of: 805ec19d7d9915989be8a8a626176b5e29e19eee
Recommit fixes llvm-sim tests
Recommit of: 082ec267583100455fee356bb0d4ebd55aba2d46
Reviewer: paquette
Differential Revision: https://reviews.llvm.org/D139338
When we check for similarity, right now there is no order to how it is checked, except for via the suffix tree ordering.
We can reduce how much structural analysis we perform by checking the the regions in decreasing size. In doing so, we know that if two large sections match, each of their contained regions also match. This allows us to skip the structural checking for each smaller section. IT does require that we use the large regions as a "bridge" to create the canonical mapping between the two regions.
This reduces compile time significantly for some benchmarks. It will not perform as well for programs with many small items.
Recommit fixes the IRSimilarity tests.
Recommit of: 805ec19d7d9915989be8a8a626176b5e29e19eee
Reviewer: paquette
Differential Revision: https://reviews.llvm.org/D139338
When we check for similarity, right now there is no order to how it is checked, except for via the suffix tree ordering.
We can reduce how much structural analysis we perform by checking the the regions in decreasing size. In doing so, we know that if two large sections match, each of their contained regions also match. This allows us to skip the structural checking for each smaller section. IT does require that we use the large regions as a "bridge" to create the canonical mapping between the two regions.
This reduces compile time significantly for some benchmarks. It will not perform as well for programs with many small items.
Reviewer: paquette
Differential Revision: https://reviews.llvm.org/D139338
Previous:
When we do not make decisions about commutative operands, we can end up in a situation where two values have two potential canonical numbers between two regions. This ensures that an ordering is decided after the initial structure between two regions is determined.
Current:
Previously the outliner only checked that assignment to a value matched what was already known, this patch makes sure that it matches what has already been found, and creates a mapping between the two values where it is a one-to-one mapping.
Reviewer: paquette
Differential Revision: https://reviews.llvm.org/D139336
Branch operands are different from regular instructions. They can have a mix of boolean values and branch instructions. This makes sure that branches are treated as more of a special case and makes sure that the successor blocks are always in the same order, and that they do not include the conditional argument.
Reviewer: paquette
Differential Revision: https://reviews.llvm.org/D139337
value() has undesired exception checking semantics and calls
__throw_bad_optional_access in libc++. Moreover, the API is unavailable without
_LIBCPP_NO_EXCEPTIONS on older Mach-O platforms (see
_LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS).
This commit fixes LLVMAnalysis and its dependencies.
When the first commutative instruction in a region using the same value in both positions was compared to a corresponding instruction with two different values, there was an early check that determined that since the values were new, it was true that these values acted in the same way structurally. If this was not contradicted later in the program, the regions were marked as similar. This removes that check, so that it is clear that the same value cannot be mapped to two different values.
Reviewer: paquette
Differential Revision: https://reviews.llvm.org/D124775
When constructing canonical relationships between two regions, the first instruction of a basic block from the first region is used to find the corresponding basic block from the second region. However, debug instructions are not included in similarity matching, and therefore do not have a canonical numbering. This patch makes sure to ignore the debug instructions when finding the first instruction in a basic block.
Reviewer: paquette
Differential Revision: https://reviews.llvm.org/D123903
Issue: https://github.com/llvm/llvm-project/issues/54431
PHINodes that need to be generated to accommodate a PHINode outside the region due to different output paths need to have their own numbering to determine the number of output schemes required to properly handle all the outlined regions. This numbering was previously only determined by the order and values of the incoming values, as well as the parent block of the PHINode. This adds the incoming blocks to the calculation of a hash value for these PHINodes as well, and the supporting infrastructure to give each block in a region a corresponding canonical numbering.
Reviewer: paquette
Differential Revision: https://reviews.llvm.org/D122207
If an instruction is first legal instruction in the module, and is the only legal instruction in its basic block, it will be ignored by the outliner due to a length check inherited from the older version of the outliner that was restricted to outlining within a single basic block. This removes that check, and updates any tests that broke because of it.
Reviewer: paquette
Differential Revision: https://reviews.llvm.org/D120786
Musttail calls require extra handling to properly propagate the calling convention information and tail call information. The outliner does not currently do this, so we ignore call instructions that utilize the swifttailcc and tailcc calling convention as well as functions marked with the attribute musttail.
Reviewers: paquette, aschwaighofer
Differential Revision: https://reviews.llvm.org/D120733
Created to fix: https://github.com/llvm/llvm-project/issues/53537
Some intrinsics functions are considered commutative since they are performing operations like addition or multiplication. Some of these have extra parameters to provide extra information that are not part of the operation itself and are not commutative. This makes sure that if an instruction that is an intrinsic takes the non commutative path to handle this case.
Reviewer: paquette
Closes Issue #53537
Differential Revision: https://reviews.llvm.org/D118807
Due to some complications with lifetime, and assume-like intrinsics, intrinsics were not included as outlinable instructions. This patch opens up most intrinsics, excluding lifetime and assume-like intrinsics, to be outlined. For similarity, it is required that the intrinsic IDs, and the intrinsics names match exactly, as well as the function type. This puts intrinsics in a different class than normal call instructions (https://reviews.llvm.org/D109448), where the name will no longer have to match.
This also adds an additional command line flag debug option to disable outlining intrinsics.
Recommit of: 8de76bd569732acae6a10fdcb0152a49f7d4cd39
Adds extra checking of intrinsic function calls names to avoid taking the address of intrinsic calls when extracting function calls.
Reviewers: paquette, jroelofs
Differential Revision: https://reviews.llvm.org/D109450
We use the same similarity scheme we used for branch instructions for phi nodes, and allow them to be outlined. There is not a lot of special handling needed for these phi nodes when outlining, as they simply act as outputs. The code extractor does not currently allow for non entry blocks within the extracted region to have predecessors, so there are not conflicts to handle with respect to predecessors no longer contained in the function.
Recommit of 515eec3553b02533e9a88ee84bc245d5415163da
Reviewers: paquette
Differential Revision: https://reviews.llvm.org/D106997
Due to some complications with lifetime, and assume-like intrinsics, intrinsics were not included as outlinable instructions. This patch opens up most intrinsics, excluding lifetime and assume-like intrinsics, to be outlined. For similarity, it is required that the intrinsic IDs, and the intrinsics names match exactly, as well as the function type. This puts intrinsics in a different class than normal call instructions (https://reviews.llvm.org/D109448), where the name will no longer have to match.
This also adds an additional command line flag debug option to disable outlining intrinsics.
Reviewers: paquette, jroelofs
Differential Revision: https://reviews.llvm.org/D109450
The outliner currently requires that function calls not be indirect calls, and have that the function name, and function type must match, as well as other attributes such as calling conventions. This patch treats called functions as values, and just another operand, and named function calls as constants. This allows functions to be treated like any other constant, or input and output into the outlined functions.
There are also debugging flags added to enforce the old behaviors where indirect calls not be allowed, and to enforce the old rule that function calls names must also match.
Reviewers: paquette, jroelofs
Differential Revision: https://reviews.llvm.org/D109448
The current IRSimilarityIdentifier does not try to find similarity across blocks, this patch provides a mechanism to compare two branches against one another, to find similarity across basic blocks, rather than just within them.
This adds a step in the similarity identification process that labels all of the basic blocks so that we can identify the relative branching locations. Within an IRSimilarityCandidate we use these relative locations to determine whether if the branching to other relative locations in the same region is the same between branches. If they are, we consider them similar.
We do not consider the relative location of the branch if the target branch is outside of the region. In this case, both branches must exit to a location outside the region, but the exact relative location does not matter.
Reviewers: paquette, yroux
Differential Revision: https://reviews.llvm.org/D106989
