[clang-tools-extra] llvm-canon (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/17] 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 &F) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function &F); + void nameBasicBlocks(Function &F); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector &Outputs); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet &Visited); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function &F); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet &Visited); + /// @} +}; +} // 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
[clang-tools-extra] llvm-canon (PR #68176)
nikic wrote: Using the term for MIR is okay, because it does not have a pre-existing notion of canonical form. Doing the same for IR is not okay, because it already has a canonical form and this pass does not produce it. Calling this `ir-normalizer` instead of `ir-canonicalizer` should convey about the same intent without overloading an existing, widely used term. 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-canon (PR #68176)
michalpaszkowski wrote: > Please don't use the term canon/canonicalize for this pass or tool. LLVM has > an existing notion of "canonicalization" which does not coincide with what is > being done here. @nikic I don't think the name "canon" or "canonicalizer" will lead to any confusion here. This is in fact what the pass is doing and mimics the name of MIR canonicalizer with similar assumptions as @plotfi noted . Using the term "canonicalization" for the current/existing set of passes is not really common or well defined. As for the RFC, there was a discussion thread in the LLVM Dev Mailing: https://lists.llvm.org/pipermail/llvm-dev/2019-August/134475.html 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-canon (PR #68176)
plotfi wrote: > Please don't use the term canon/canonicalize for this pass or tool. LLVM has > an existing notion of "canonicalization" which does not coincide with what is > being done here. The term comes from an older pass that did similar algorithms on MIR. They are only borrowing the term from it. 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-canon (PR #68176)
AaronBallman wrote: > Thanks for reaching out guys. > > I recall approving the original PR on phab. I can re-review if needed. This > work was approved to land before, so personally I think it might be overkill > to RFC it on discourse again but I am not certain of the right process to > take. > > > Added @plotfi as a reviewer; one drive-by question is whether adding a new > > LLVM tool like this requires an RFC to be posted to Discourse or not > > (https://llvm.org/docs/DeveloperPolicy.html#introducing-new-components-into-llvm). > > (I don't have any opinions on the tool; just trying to help the review > > move along.) I don't have strong opinions on whether this should have an RFC or not, but the original review didn't come with an RFC that I could find either. Given that there are some concerns about what the name of the tool is, I weakly lean towards running an RFC just to make sure everyone is comfortable with the tool. But again, I don't insist, it's just a drive-by comment because I happened to notice the PR. 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-canon (PR #68176)
AaronBallman wrote: Added @plotfi as a reviewer; one drive-by question is whether adding a new LLVM tool like this requires an RFC to be posted to Discourse or not (https://llvm.org/docs/DeveloperPolicy.html#introducing-new-components-into-llvm). (I don't have any opinions on the tool; just trying to help the review move along.) 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-canon (PR #68176)
@@ -0,0 +1,638 @@ +//===--- 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 "llvm/Transforms/Utils/IRCanonicalizer.h" +#include +#include + +#define DEBUG_TYPE "canon" + +using namespace llvm; + +namespace { +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +class IRCanonicalizer { +public: + /// \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; + /// @} + + bool runOnFunction(Function &F); + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + DenseSet NamedInstructions; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function &F); + void nameBasicBlocks(Function &F); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector &Outputs); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet &Visited); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function &F); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet &Visited); + /// @} +}; +} // namespace + +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 (including pre-outputs)")); +cl::opt IRCanonicalizer::ReorderOperands( +"reorder-operands", cl::Hidden, +cl::desc("Sorts and reorders operands in commutative instructions")); + +/// Entry method to the IRCanonicalizer. +/// +/// \param M Module to canonicalize. +bool IRCanonicalizer::runOnFunction(Function &F) { + nameFunctionArguments(F); + nameBasicBlocks(F); + + SmallVector Outputs = collectOutputInstructions(F); + + if (!PreserveOrder) +reorderInstructions(Outputs); + + for (auto &I : Outputs) +nameInstruction(I); + + for (auto &I : instructions(F)) { +if (!PreserveOrder) { + if (ReorderOperands && I.isCommutative()) +reorderInstructionOperandsByNames(&I); + + if (auto *PN = dyn_cast(&I)) +reorderPHIIncomingValues(PN); +} + +foldInstructionName(&I); + } + + return true; +} + +/// Numbers arguments. +/// +/// \param F Function whose arguments will be renamed. +void IRCanonicalizer::nameFunctionArguments(Function &F) { + int ArgumentCounter = 0; + for (auto &A : 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 IRCanonicalizer::nameBas
[clang-tools-extra] llvm-canon (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/16] 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 &F) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function &F); + void nameBasicBlocks(Function &F); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector &Outputs); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet &Visited); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function &F); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet &Visited); + /// @} +}; +} // 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
[clang-tools-extra] llvm-canon (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/15] 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 &F) override; + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function &F); + void nameBasicBlocks(Function &F); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector &Outputs); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet &Visited); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function &F); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet &Visited); + /// @} +}; +} // 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
[clang-tools-extra] llvm-canon (PR #68176)
@@ -0,0 +1,638 @@ +//===--- 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 "llvm/Transforms/Utils/IRCanonicalizer.h" +#include +#include + +#define DEBUG_TYPE "canon" + +using namespace llvm; + +namespace { +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +class IRCanonicalizer { +public: + /// \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; + /// @} + + bool runOnFunction(Function &F); + +private: + // Random constant for hashing, so the state isn't zero. + const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + DenseSet NamedInstructions; + + /// \name Naming. + /// @{ + void nameFunctionArguments(Function &F); + void nameBasicBlocks(Function &F); + void nameInstruction(Instruction *I); + void nameAsInitialInstruction(Instruction *I); + void nameAsRegularInstruction(Instruction *I); + void foldInstructionName(Instruction *I); + /// @} + + /// \name Reordering. + /// @{ + void reorderInstructions(SmallVector &Outputs); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet &Visited); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector collectOutputInstructions(Function &F); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector + getOutputFootprint(Instruction *I, + SmallPtrSet &Visited); + /// @} +}; +} // namespace + +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 (including pre-outputs)")); +cl::opt IRCanonicalizer::ReorderOperands( +"reorder-operands", cl::Hidden, +cl::desc("Sorts and reorders operands in commutative instructions")); + +/// Entry method to the IRCanonicalizer. +/// +/// \param M Module to canonicalize. +bool IRCanonicalizer::runOnFunction(Function &F) { + nameFunctionArguments(F); + nameBasicBlocks(F); + + SmallVector Outputs = collectOutputInstructions(F); + + if (!PreserveOrder) +reorderInstructions(Outputs); + + for (auto &I : Outputs) +nameInstruction(I); + + for (auto &I : instructions(F)) { +if (!PreserveOrder) { + if (ReorderOperands && I.isCommutative()) +reorderInstructionOperandsByNames(&I); + + if (auto *PN = dyn_cast(&I)) +reorderPHIIncomingValues(PN); +} + +foldInstructionName(&I); + } + + return true; +} + +/// Numbers arguments. +/// +/// \param F Function whose arguments will be renamed. +void IRCanonicalizer::nameFunctionArguments(Function &F) { + int ArgumentCounter = 0; + for (auto &A : 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 IRCanonicalizer::nameBas
[clang-tools-extra] llvm-canon (PR #68176)
michalpaszkowski wrote: Thank you @justinfargnoli and @AidanGoldfarb for taking over this work and reaching out! I will review your changes in the coming week. CC @ChrisCummins FYI 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-canon (PR #68176)
github-actions[bot] wrote: :warning: C/C++ code formatter, clang-format found issues in your code. :warning: You can test this locally with the following command: ``bash git-clang-format --diff 8641cdf397d86f33ac45e4c691ca4f843c359370 90912d2b40121936c239f9275bebd52db5d3a116 -- llvm/include/llvm/Transforms/Utils/IRCanonicalizer.h llvm/lib/Transforms/Utils/IRCanonicalizer.cpp llvm/lib/Passes/PassBuilder.cpp `` View the diff from clang-format here. ``diff diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp index 8a495e6d7dc1..7fc17ab31a11 100644 --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -233,14 +233,14 @@ #include "llvm/Transforms/Utils/CanonicalizeAliases.h" #include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h" #include "llvm/Transforms/Utils/CountVisits.h" -#include "llvm/Transforms/Utils/Debugify.h" #include "llvm/Transforms/Utils/DXILUpgrade.h" +#include "llvm/Transforms/Utils/Debugify.h" #include "llvm/Transforms/Utils/EntryExitInstrumenter.h" #include "llvm/Transforms/Utils/FixIrreducible.h" #include "llvm/Transforms/Utils/HelloWorld.h" +#include "llvm/Transforms/Utils/IRCanonicalizer.h" #include "llvm/Transforms/Utils/InjectTLIMappings.h" #include "llvm/Transforms/Utils/InstructionNamer.h" -#include "llvm/Transforms/Utils/IRCanonicalizer.h" #include "llvm/Transforms/Utils/LCSSA.h" #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h" #include "llvm/Transforms/Utils/LoopSimplify.h" diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp index 45dc954f97b9..1a4edadec42f 100644 --- a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -14,6 +14,7 @@ /// //===--===// +#include "llvm/Transforms/Utils/IRCanonicalizer.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallString.h" @@ -28,7 +29,6 @@ #include "llvm/PassRegistry.h" #include "llvm/Support/CommandLine.h" #include "llvm/Transforms/Utils.h" -#include "llvm/Transforms/Utils/IRCanonicalizer.h" #include #include @@ -174,12 +174,12 @@ void IRCanonicalizer::nameBasicBlocks(Function &F) { /// /// \param I Instruction to be renamed. void IRCanonicalizer::nameInstruction(Instruction *I) { - //ensure instructions are not renamed. This is done - //to prevent situation where instructions are used - //before their definition (in phi nodes) + // ensure instructions are not renamed. This is done + // to prevent situation where instructions are used + // before their definition (in phi nodes) if (NamedInstructions.contains(I)) return; - NamedInstructions.insert(I); + NamedInstructions.insert(I); // Determine the type of instruction to name. if (isInitialInstruction(I)) { // This is an initial instruction. @@ -441,7 +441,7 @@ void IRCanonicalizer::reorderInstructions( void IRCanonicalizer::reorderInstruction( Instruction *Used, Instruction *User, SmallPtrSet &Visited) { - if(isa(Used)) + if (isa(Used)) return; if (Visited.contains(Used)) return; `` 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