[clang-tools-extra] [llvm] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
plotfi wrote: > Pinging @nikic for another round of review. @nikic is there more feedback or can this PR be merged? https://github.com/llvm/llvm-project/pull/68176 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang-tools-extra] [llvm] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
justinfargnoli wrote: Pinging @nikic for another round of review. https://github.com/llvm/llvm-project/pull/68176 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang-tools-extra] [llvm] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
justinfargnoli wrote: > I would recommend trying to run this pass (with all options enabled) over all > existing tests to make sure that it doesn't cause any crashes/verifier > failures. You're moving instructions around, and it's easy to get that wrong > when invoke, callbr or catchswitch are involved. Thanks for this suggestion! It helped iron out a lot of bugs in the implementation. > I would also try to add this pass at the end of the clang pipeline and run > llvm-test-suite to verify that the normalization this does is indeed > semantics-preserving. I'm running into some linking errors when trying to build [`llvm-test-suite`](https://github.com/llvm/llvm-test-suite/tree/main). Pinging for another round of review in the meantime. https://github.com/llvm/llvm-project/pull/68176 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang-tools-extra] [llvm] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
https://github.com/justinfargnoli edited https://github.com/llvm/llvm-project/pull/68176 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[llvm] [clang-tools-extra] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
https://github.com/justinfargnoli updated https://github.com/llvm/llvm-project/pull/68176 >From f792a030ac1761a96176332fea906cd2d1826c7b Mon Sep 17 00:00:00 2001 From: justinfargnoli Date: Sat, 12 Aug 2023 10:58:45 -0700 Subject: [PATCH 01/31] Add IRCanonicalizer.cpp --- llvm/lib/Transforms/Utils/CMakeLists.txt | 1 + llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 632 ++ 2 files changed, 633 insertions(+) create mode 100644 llvm/lib/Transforms/Utils/IRCanonicalizer.cpp diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt index a870071f3f641dc..7866e7a8c09c3be 100644 --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -34,6 +34,7 @@ add_llvm_component_library(LLVMTransformUtils InjectTLIMappings.cpp InstructionNamer.cpp IntegerDivision.cpp + IRCanonicalizer.cpp LCSSA.cpp LibCallsShrinkWrap.cpp Local.cpp diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp new file mode 100644 index 000..58e2dce0b96685b --- /dev/null +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -0,0 +1,632 @@ +//===--- IRCanonicalizer.cpp - IR Canonicalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRCanonicalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The canonicalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "canon" + +using namespace llvm; + +namespace { +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +class IRCanonicalizer : public FunctionPass { +public: + static char ID; + + /// \name Canonicalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + /// Constructor for the IRCanonicalizer. + IRCanonicalizer() : FunctionPass(ID) {} + + bool runOnFunction(Function ) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +char IRCanonicalizer::ID = 0; +static RegisterPass X("canon", "Canonicalize the IR", + false /* Only looks at CFG */, + false /* Analysis Pass */); + +cl::opt IRCanonicalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRCanonicalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRCanonicalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions
[clang-tools-extra] [llvm] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
michalpaszkowski wrote: [Here are the slides](https://llvm.org/devmtg/2019-10/slides/Paszkowski-LLVMCanon.pdf) that were presented at the LLVM Dev Meeting in 2019. It might be useful to include the link in the commit message for reference. @nikic Thanks for catching more things in the review! Especially the commutative ordering of operands/arguments. When it comes to including hashes in the naming algorithm (renaming is controlled using an option for already named values), the ideas is that by just looking at an instruction further down (a use) you can tell whether any inputs are different. And the other way around, by looking at initial instructions you can see how their "output footprint" has changed after transformations. The example below is a bit outdated, but reflects the general idea we had when considering naming algorithms: https://github.com/llvm/llvm-project/assets/13875746/fdb85b98-bce9-48df-91c0-35ffd115bae0;> https://github.com/llvm/llvm-project/assets/13875746/24d74cf1-ad21-47c0-9057-6065c7a4f472;> https://github.com/llvm/llvm-project/pull/68176 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[llvm] [clang-tools-extra] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
https://github.com/justinfargnoli updated https://github.com/llvm/llvm-project/pull/68176 >From f792a030ac1761a96176332fea906cd2d1826c7b Mon Sep 17 00:00:00 2001 From: justinfargnoli Date: Sat, 12 Aug 2023 10:58:45 -0700 Subject: [PATCH 01/30] Add IRCanonicalizer.cpp --- llvm/lib/Transforms/Utils/CMakeLists.txt | 1 + llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 632 ++ 2 files changed, 633 insertions(+) create mode 100644 llvm/lib/Transforms/Utils/IRCanonicalizer.cpp diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt index a870071f3f641dc..7866e7a8c09c3be 100644 --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -34,6 +34,7 @@ add_llvm_component_library(LLVMTransformUtils InjectTLIMappings.cpp InstructionNamer.cpp IntegerDivision.cpp + IRCanonicalizer.cpp LCSSA.cpp LibCallsShrinkWrap.cpp Local.cpp diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp new file mode 100644 index 000..58e2dce0b96685b --- /dev/null +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -0,0 +1,632 @@ +//===--- IRCanonicalizer.cpp - IR Canonicalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRCanonicalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The canonicalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "canon" + +using namespace llvm; + +namespace { +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +class IRCanonicalizer : public FunctionPass { +public: + static char ID; + + /// \name Canonicalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + /// Constructor for the IRCanonicalizer. + IRCanonicalizer() : FunctionPass(ID) {} + + bool runOnFunction(Function ) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +char IRCanonicalizer::ID = 0; +static RegisterPass X("canon", "Canonicalize the IR", + false /* Only looks at CFG */, + false /* Analysis Pass */); + +cl::opt IRCanonicalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRCanonicalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRCanonicalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions
[llvm] [clang-tools-extra] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
https://github.com/justinfargnoli updated https://github.com/llvm/llvm-project/pull/68176 >From f792a030ac1761a96176332fea906cd2d1826c7b Mon Sep 17 00:00:00 2001 From: justinfargnoli Date: Sat, 12 Aug 2023 10:58:45 -0700 Subject: [PATCH 01/29] Add IRCanonicalizer.cpp --- llvm/lib/Transforms/Utils/CMakeLists.txt | 1 + llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 632 ++ 2 files changed, 633 insertions(+) create mode 100644 llvm/lib/Transforms/Utils/IRCanonicalizer.cpp diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt index a870071f3f641dc..7866e7a8c09c3be 100644 --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -34,6 +34,7 @@ add_llvm_component_library(LLVMTransformUtils InjectTLIMappings.cpp InstructionNamer.cpp IntegerDivision.cpp + IRCanonicalizer.cpp LCSSA.cpp LibCallsShrinkWrap.cpp Local.cpp diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp new file mode 100644 index 000..58e2dce0b96685b --- /dev/null +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -0,0 +1,632 @@ +//===--- IRCanonicalizer.cpp - IR Canonicalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRCanonicalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The canonicalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "canon" + +using namespace llvm; + +namespace { +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +class IRCanonicalizer : public FunctionPass { +public: + static char ID; + + /// \name Canonicalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + /// Constructor for the IRCanonicalizer. + IRCanonicalizer() : FunctionPass(ID) {} + + bool runOnFunction(Function ) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +char IRCanonicalizer::ID = 0; +static RegisterPass X("canon", "Canonicalize the IR", + false /* Only looks at CFG */, + false /* Analysis Pass */); + +cl::opt IRCanonicalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRCanonicalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRCanonicalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions
[clang-tools-extra] [llvm] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
https://github.com/justinfargnoli updated https://github.com/llvm/llvm-project/pull/68176 >From f792a030ac1761a96176332fea906cd2d1826c7b Mon Sep 17 00:00:00 2001 From: justinfargnoli Date: Sat, 12 Aug 2023 10:58:45 -0700 Subject: [PATCH 01/26] Add IRCanonicalizer.cpp --- llvm/lib/Transforms/Utils/CMakeLists.txt | 1 + llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 632 ++ 2 files changed, 633 insertions(+) create mode 100644 llvm/lib/Transforms/Utils/IRCanonicalizer.cpp diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt index a870071f3f641dc..7866e7a8c09c3be 100644 --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -34,6 +34,7 @@ add_llvm_component_library(LLVMTransformUtils InjectTLIMappings.cpp InstructionNamer.cpp IntegerDivision.cpp + IRCanonicalizer.cpp LCSSA.cpp LibCallsShrinkWrap.cpp Local.cpp diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp new file mode 100644 index 000..58e2dce0b96685b --- /dev/null +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -0,0 +1,632 @@ +//===--- IRCanonicalizer.cpp - IR Canonicalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRCanonicalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The canonicalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "canon" + +using namespace llvm; + +namespace { +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +class IRCanonicalizer : public FunctionPass { +public: + static char ID; + + /// \name Canonicalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + /// Constructor for the IRCanonicalizer. + IRCanonicalizer() : FunctionPass(ID) {} + + bool runOnFunction(Function ) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +char IRCanonicalizer::ID = 0; +static RegisterPass X("canon", "Canonicalize the IR", + false /* Only looks at CFG */, + false /* Analysis Pass */); + +cl::opt IRCanonicalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRCanonicalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRCanonicalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions
[llvm] [clang-tools-extra] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
https://github.com/justinfargnoli updated https://github.com/llvm/llvm-project/pull/68176 >From f792a030ac1761a96176332fea906cd2d1826c7b Mon Sep 17 00:00:00 2001 From: justinfargnoli Date: Sat, 12 Aug 2023 10:58:45 -0700 Subject: [PATCH 01/25] Add IRCanonicalizer.cpp --- llvm/lib/Transforms/Utils/CMakeLists.txt | 1 + llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 632 ++ 2 files changed, 633 insertions(+) create mode 100644 llvm/lib/Transforms/Utils/IRCanonicalizer.cpp diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt index a870071f3f641dc..7866e7a8c09c3be 100644 --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -34,6 +34,7 @@ add_llvm_component_library(LLVMTransformUtils InjectTLIMappings.cpp InstructionNamer.cpp IntegerDivision.cpp + IRCanonicalizer.cpp LCSSA.cpp LibCallsShrinkWrap.cpp Local.cpp diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp new file mode 100644 index 000..58e2dce0b96685b --- /dev/null +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -0,0 +1,632 @@ +//===--- IRCanonicalizer.cpp - IR Canonicalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRCanonicalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The canonicalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "canon" + +using namespace llvm; + +namespace { +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +class IRCanonicalizer : public FunctionPass { +public: + static char ID; + + /// \name Canonicalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + /// Constructor for the IRCanonicalizer. + IRCanonicalizer() : FunctionPass(ID) {} + + bool runOnFunction(Function ) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +char IRCanonicalizer::ID = 0; +static RegisterPass X("canon", "Canonicalize the IR", + false /* Only looks at CFG */, + false /* Analysis Pass */); + +cl::opt IRCanonicalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRCanonicalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRCanonicalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions
[clang-tools-extra] [llvm] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
https://github.com/nikic edited https://github.com/llvm/llvm-project/pull/68176 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang-tools-extra] [llvm] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
@@ -0,0 +1,637 @@ +//===--- IRNormalizer.cpp - IR Normalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRNormalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The normalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/Transforms/Utils/IRNormalizer.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "normalize" + +using namespace llvm; + +namespace { +/// IRNormalizer aims to transform LLVM IR into canonical form. +class IRNormalizer { +public: + /// \name Normalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + bool runOnFunction(Function ); + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + DenseSet NamedInstructions; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +cl::opt IRNormalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRNormalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRNormalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions (including pre-outputs)")); +cl::opt IRNormalizer::ReorderOperands( +"reorder-operands", cl::Hidden, +cl::desc("Sorts and reorders operands in commutative instructions")); + +/// Entry method to the IRNormalizer. +/// +/// \param M Module to normalize. +bool IRNormalizer::runOnFunction(Function ) { + nameFunctionArguments(F); + nameBasicBlocks(F); + + SmallVector Outputs = collectOutputInstructions(F); + + if (!PreserveOrder) +reorderInstructions(Outputs); + + for (auto : Outputs) +nameInstruction(I); + + for (auto : instructions(F)) { +if (!PreserveOrder) { + if (ReorderOperands && I.isCommutative()) +reorderInstructionOperandsByNames(); + + if (auto *PN = dyn_cast()) +reorderPHIIncomingValues(PN); +} + +foldInstructionName(); + } + + return true; +} + +/// Numbers arguments. +/// +/// \param F Function whose arguments will be renamed. +void IRNormalizer::nameFunctionArguments(Function ) { + int ArgumentCounter = 0; + for (auto : F.args()) { +if (RenameAll || A.getName().empty()) { + A.setName("a" + Twine(ArgumentCounter)); + ++ArgumentCounter; +} + } +} + +/// Names basic blocks using a generated hash for each basic block in +/// a function considering the opcode and the order of output instructions. +/// +/// \param F Function containing basic blocks to rename. +void IRNormalizer::nameBasicBlocks(Function ) { + for (auto : F) { +// Initialize to a magic constant, so the state
[llvm] [clang-tools-extra] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
@@ -0,0 +1,637 @@ +//===--- IRNormalizer.cpp - IR Normalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRNormalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The normalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/Transforms/Utils/IRNormalizer.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "normalize" + +using namespace llvm; + +namespace { +/// IRNormalizer aims to transform LLVM IR into canonical form. +class IRNormalizer { +public: + /// \name Normalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + bool runOnFunction(Function ); + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + DenseSet NamedInstructions; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +cl::opt IRNormalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRNormalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRNormalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions (including pre-outputs)")); +cl::opt IRNormalizer::ReorderOperands( +"reorder-operands", cl::Hidden, +cl::desc("Sorts and reorders operands in commutative instructions")); + +/// Entry method to the IRNormalizer. +/// +/// \param M Module to normalize. +bool IRNormalizer::runOnFunction(Function ) { + nameFunctionArguments(F); + nameBasicBlocks(F); + + SmallVector Outputs = collectOutputInstructions(F); + + if (!PreserveOrder) +reorderInstructions(Outputs); + + for (auto : Outputs) +nameInstruction(I); + + for (auto : instructions(F)) { +if (!PreserveOrder) { + if (ReorderOperands && I.isCommutative()) +reorderInstructionOperandsByNames(); + + if (auto *PN = dyn_cast()) +reorderPHIIncomingValues(PN); +} + +foldInstructionName(); + } + + return true; +} + +/// Numbers arguments. +/// +/// \param F Function whose arguments will be renamed. +void IRNormalizer::nameFunctionArguments(Function ) { + int ArgumentCounter = 0; + for (auto : F.args()) { +if (RenameAll || A.getName().empty()) { + A.setName("a" + Twine(ArgumentCounter)); + ++ArgumentCounter; +} + } +} + +/// Names basic blocks using a generated hash for each basic block in +/// a function considering the opcode and the order of output instructions. +/// +/// \param F Function containing basic blocks to rename. +void IRNormalizer::nameBasicBlocks(Function ) { + for (auto : F) { +// Initialize to a magic constant, so the state
[clang-tools-extra] [llvm] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
@@ -0,0 +1,637 @@ +//===--- IRNormalizer.cpp - IR Normalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRNormalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The normalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/Transforms/Utils/IRNormalizer.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "normalize" + +using namespace llvm; + +namespace { +/// IRNormalizer aims to transform LLVM IR into canonical form. +class IRNormalizer { +public: + /// \name Normalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + bool runOnFunction(Function ); + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + DenseSet NamedInstructions; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +cl::opt IRNormalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRNormalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRNormalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions (including pre-outputs)")); +cl::opt IRNormalizer::ReorderOperands( +"reorder-operands", cl::Hidden, +cl::desc("Sorts and reorders operands in commutative instructions")); + +/// Entry method to the IRNormalizer. +/// +/// \param M Module to normalize. +bool IRNormalizer::runOnFunction(Function ) { + nameFunctionArguments(F); + nameBasicBlocks(F); + + SmallVector Outputs = collectOutputInstructions(F); + + if (!PreserveOrder) +reorderInstructions(Outputs); + + for (auto : Outputs) +nameInstruction(I); + + for (auto : instructions(F)) { +if (!PreserveOrder) { + if (ReorderOperands && I.isCommutative()) +reorderInstructionOperandsByNames(); + + if (auto *PN = dyn_cast()) +reorderPHIIncomingValues(PN); +} + +foldInstructionName(); + } + + return true; +} + +/// Numbers arguments. +/// +/// \param F Function whose arguments will be renamed. +void IRNormalizer::nameFunctionArguments(Function ) { + int ArgumentCounter = 0; + for (auto : F.args()) { +if (RenameAll || A.getName().empty()) { + A.setName("a" + Twine(ArgumentCounter)); + ++ArgumentCounter; +} + } +} + +/// Names basic blocks using a generated hash for each basic block in +/// a function considering the opcode and the order of output instructions. +/// +/// \param F Function containing basic blocks to rename. +void IRNormalizer::nameBasicBlocks(Function ) { + for (auto : F) { +// Initialize to a magic constant, so the state
[llvm] [clang-tools-extra] [clang] [LLVM] Add IRNormalizer Pass (PR #68176)
@@ -0,0 +1,637 @@ +//===--- IRNormalizer.cpp - IR Normalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRNormalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The normalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/Transforms/Utils/IRNormalizer.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "normalize" + +using namespace llvm; + +namespace { +/// IRNormalizer aims to transform LLVM IR into canonical form. +class IRNormalizer { +public: + /// \name Normalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + bool runOnFunction(Function ); + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + DenseSet NamedInstructions; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +cl::opt IRNormalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRNormalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRNormalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions (including pre-outputs)")); +cl::opt IRNormalizer::ReorderOperands( +"reorder-operands", cl::Hidden, +cl::desc("Sorts and reorders operands in commutative instructions")); + +/// Entry method to the IRNormalizer. +/// +/// \param M Module to normalize. +bool IRNormalizer::runOnFunction(Function ) { + nameFunctionArguments(F); + nameBasicBlocks(F); + + SmallVector Outputs = collectOutputInstructions(F); + + if (!PreserveOrder) +reorderInstructions(Outputs); + + for (auto : Outputs) +nameInstruction(I); + + for (auto : instructions(F)) { +if (!PreserveOrder) { + if (ReorderOperands && I.isCommutative()) +reorderInstructionOperandsByNames(); + + if (auto *PN = dyn_cast()) +reorderPHIIncomingValues(PN); +} + +foldInstructionName(); + } + + return true; +} + +/// Numbers arguments. +/// +/// \param F Function whose arguments will be renamed. +void IRNormalizer::nameFunctionArguments(Function ) { + int ArgumentCounter = 0; + for (auto : F.args()) { +if (RenameAll || A.getName().empty()) { + A.setName("a" + Twine(ArgumentCounter)); + ++ArgumentCounter; +} + } +} + +/// Names basic blocks using a generated hash for each basic block in +/// a function considering the opcode and the order of output instructions. +/// +/// \param F Function containing basic blocks to rename. +void IRNormalizer::nameBasicBlocks(Function ) { + for (auto : F) { +// Initialize to a magic constant, so the state
[clang] [LLVM] Add IRNormalizer Pass (PR #68176)
https://github.com/justinfargnoli updated https://github.com/llvm/llvm-project/pull/68176 >From f792a030ac1761a96176332fea906cd2d1826c7b Mon Sep 17 00:00:00 2001 From: justinfargnoli Date: Sat, 12 Aug 2023 10:58:45 -0700 Subject: [PATCH 01/20] Add IRCanonicalizer.cpp --- llvm/lib/Transforms/Utils/CMakeLists.txt | 1 + llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 632 ++ 2 files changed, 633 insertions(+) create mode 100644 llvm/lib/Transforms/Utils/IRCanonicalizer.cpp diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt index a870071f3f641dc..7866e7a8c09c3be 100644 --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -34,6 +34,7 @@ add_llvm_component_library(LLVMTransformUtils InjectTLIMappings.cpp InstructionNamer.cpp IntegerDivision.cpp + IRCanonicalizer.cpp LCSSA.cpp LibCallsShrinkWrap.cpp Local.cpp diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp new file mode 100644 index 000..58e2dce0b96685b --- /dev/null +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -0,0 +1,632 @@ +//===--- IRCanonicalizer.cpp - IR Canonicalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRCanonicalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The canonicalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "canon" + +using namespace llvm; + +namespace { +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +class IRCanonicalizer : public FunctionPass { +public: + static char ID; + + /// \name Canonicalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + /// Constructor for the IRCanonicalizer. + IRCanonicalizer() : FunctionPass(ID) {} + + bool runOnFunction(Function ) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +char IRCanonicalizer::ID = 0; +static RegisterPass X("canon", "Canonicalize the IR", + false /* Only looks at CFG */, + false /* Analysis Pass */); + +cl::opt IRCanonicalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRCanonicalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRCanonicalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions
[clang] [LLVM] Add IRNormalizer Pass (PR #68176)
https://github.com/justinfargnoli updated https://github.com/llvm/llvm-project/pull/68176 >From f792a030ac1761a96176332fea906cd2d1826c7b Mon Sep 17 00:00:00 2001 From: justinfargnoli Date: Sat, 12 Aug 2023 10:58:45 -0700 Subject: [PATCH 01/20] Add IRCanonicalizer.cpp --- llvm/lib/Transforms/Utils/CMakeLists.txt | 1 + llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 632 ++ 2 files changed, 633 insertions(+) create mode 100644 llvm/lib/Transforms/Utils/IRCanonicalizer.cpp diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt index a870071f3f641dc..7866e7a8c09c3be 100644 --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -34,6 +34,7 @@ add_llvm_component_library(LLVMTransformUtils InjectTLIMappings.cpp InstructionNamer.cpp IntegerDivision.cpp + IRCanonicalizer.cpp LCSSA.cpp LibCallsShrinkWrap.cpp Local.cpp diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp new file mode 100644 index 000..58e2dce0b96685b --- /dev/null +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -0,0 +1,632 @@ +//===--- IRCanonicalizer.cpp - IR Canonicalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRCanonicalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The canonicalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "canon" + +using namespace llvm; + +namespace { +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +class IRCanonicalizer : public FunctionPass { +public: + static char ID; + + /// \name Canonicalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + /// Constructor for the IRCanonicalizer. + IRCanonicalizer() : FunctionPass(ID) {} + + bool runOnFunction(Function ) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +char IRCanonicalizer::ID = 0; +static RegisterPass X("canon", "Canonicalize the IR", + false /* Only looks at CFG */, + false /* Analysis Pass */); + +cl::opt IRCanonicalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRCanonicalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRCanonicalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions
[clang] [LLVM] Add IRNormalizer Pass (PR #68176)
michalpaszkowski wrote: I added a couple more comments regarding the name change and formatting of the docs, but apart from these the patch looks good to me. https://github.com/llvm/llvm-project/pull/68176 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [LLVM] Add IRNormalizer Pass (PR #68176)
https://github.com/justinfargnoli updated https://github.com/llvm/llvm-project/pull/68176 >From f792a030ac1761a96176332fea906cd2d1826c7b Mon Sep 17 00:00:00 2001 From: justinfargnoli Date: Sat, 12 Aug 2023 10:58:45 -0700 Subject: [PATCH 01/19] Add IRCanonicalizer.cpp --- llvm/lib/Transforms/Utils/CMakeLists.txt | 1 + llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 632 ++ 2 files changed, 633 insertions(+) create mode 100644 llvm/lib/Transforms/Utils/IRCanonicalizer.cpp diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt index a870071f3f641dc..7866e7a8c09c3be 100644 --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -34,6 +34,7 @@ add_llvm_component_library(LLVMTransformUtils InjectTLIMappings.cpp InstructionNamer.cpp IntegerDivision.cpp + IRCanonicalizer.cpp LCSSA.cpp LibCallsShrinkWrap.cpp Local.cpp diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp new file mode 100644 index 000..58e2dce0b96685b --- /dev/null +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -0,0 +1,632 @@ +//===--- IRCanonicalizer.cpp - IR Canonicalizer ---===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===--===// +/// \file +/// This file implements the IRCanonicalizer class which aims to transform LLVM +/// Modules into a canonical form by reordering and renaming instructions while +/// preserving the same semantics. The canonicalizer makes it easier to spot +/// semantic differences while diffing two modules which have undergone +/// different passes. +/// +//===--===// + +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/PassRegistry.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils.h" +#include +#include + +#define DEBUG_TYPE "canon" + +using namespace llvm; + +namespace { +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +class IRCanonicalizer : public FunctionPass { +public: + static char ID; + + /// \name Canonicalizer flags. + /// @{ + /// Preserves original order of instructions. + static cl::opt PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt ReorderOperands; + /// @} + + /// Constructor for the IRCanonicalizer. + IRCanonicalizer() : FunctionPass(ID) {} + + bool runOnFunction(Function ) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function ); + void nameBasicBlocks(Function ); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector ); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet ); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function ); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet ); + /// @} +}; +} // namespace + +char IRCanonicalizer::ID = 0; +static RegisterPass X("canon", "Canonicalize the IR", + false /* Only looks at CFG */, + false /* Analysis Pass */); + +cl::opt IRCanonicalizer::PreserveOrder( +"preserve-order", cl::Hidden, +cl::desc("Preserves original instruction order")); +cl::opt IRCanonicalizer::RenameAll( +"rename-all", cl::Hidden, +cl::desc("Renames all instructions (including user-named)")); +cl::opt IRCanonicalizer::FoldPreoutputs( +"fold-all", cl::Hidden, +cl::desc("Folds all regular instructions