@@ -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