https://github.com/justinfargnoli updated https://github.com/llvm/llvm-project/pull/68176
>From f792a030ac1761a96176332fea906cd2d1826c7b Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> 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 000000000000000..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 <algorithm> +#include <vector> + +#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<bool> PreserveOrder; + /// Renames all instructions (including user-named). + static cl::opt<bool> RenameAll; + /// Folds all regular instructions (including pre-outputs). + static cl::opt<bool> FoldPreoutputs; + /// Sorts and reorders operands in commutative instructions. + static cl::opt<bool> 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<Instruction *, 16> &Outputs); + void reorderInstruction(Instruction *Used, Instruction *User, + SmallPtrSet<const Instruction *, 32> &Visited); + void reorderInstructionOperandsByNames(Instruction *I); + void reorderPHIIncomingValues(PHINode *PN); + /// @} + + /// \name Utility methods. + /// @{ + SmallVector<Instruction *, 16> collectOutputInstructions(Function &F); + bool isOutput(const Instruction *I); + bool isInitialInstruction(const Instruction *I); + bool hasOnlyImmediateOperands(const Instruction *I); + SetVector<int> + getOutputFootprint(Instruction *I, + SmallPtrSet<const Instruction *, 32> &Visited); + /// @} +}; +} // namespace + +char IRCanonicalizer::ID = 0; +static RegisterPass<IRCanonicalizer> X("canon", "Canonicalize the IR", + false /* Only looks at CFG */, + false /* Analysis Pass */); + +cl::opt<bool> IRCanonicalizer::PreserveOrder( + "preserve-order", cl::Hidden, + cl::desc("Preserves original instruction order")); +cl::opt<bool> IRCanonicalizer::RenameAll( + "rename-all", cl::Hidden, + cl::desc("Renames all instructions (including user-named)")); +cl::opt<bool> IRCanonicalizer::FoldPreoutputs( + "fold-all", cl::Hidden, + cl::desc("Folds all regular instructions (including pre-outputs)")); +cl::opt<bool> 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<Instruction *, 16> 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<PHINode>(&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::nameBasicBlocks(Function &F) { + for (auto &B : F) { + // Initialize to a magic constant, so the state isn't zero. + uint64_t Hash = MagicHashConstant; + + // Hash considering output instruction opcodes. + for (auto &I : B) + if (isOutput(&I)) + Hash = hashing::detail::hash_16_bytes(Hash, I.getOpcode()); + + if (RenameAll || B.getName().empty()) { + // Name basic block. Substring hash to make diffs more readable. + B.setName("bb" + std::to_string(Hash).substr(0, 5)); + } + } +} + +/// Names instructions graphically (recursive) in accordance with the +/// def-use tree, starting from the initial instructions (defs), finishing at +/// the output (top-most user) instructions (depth-first). +/// +/// \param I Instruction to be renamed. +void IRCanonicalizer::nameInstruction(Instruction *I) { + // Determine the type of instruction to name. + if (isInitialInstruction(I)) { + // This is an initial instruction. + nameAsInitialInstruction(I); + } else { + // This must be a regular instruction. + nameAsRegularInstruction(I); + } +} + +/// Names instruction following the scheme: +/// vl00000Callee(Operands) +/// +/// Where 00000 is a hash calculated considering instruction's opcode and output +/// footprint. Callee's name is only included when instruction's type is +/// CallInst. In cases where instruction is commutative, operands list is also +/// sorted. +/// +/// Renames instruction only when RenameAll flag is raised or instruction is +/// unnamed. +/// +/// \see getOutputFootprint() +/// \param I Instruction to be renamed. +void IRCanonicalizer::nameAsInitialInstruction(Instruction *I) { + if (I->getType()->isVoidTy() || (!I->getName().empty() && !RenameAll)) + return; + + // Instruction operands for further sorting. + SmallVector<SmallString<64>, 4> Operands; + + // Collect operands. + for (auto &OP : I->operands()) { + if (!isa<Function>(OP)) { + std::string TextRepresentation; + raw_string_ostream Stream(TextRepresentation); + OP->printAsOperand(Stream, false); + Operands.push_back(StringRef(Stream.str())); + } + } + + if (I->isCommutative()) + llvm::sort(Operands); + + // Initialize to a magic constant, so the state isn't zero. + uint64_t Hash = MagicHashConstant; + + // Consider instruction's opcode in the hash. + Hash = hashing::detail::hash_16_bytes(Hash, I->getOpcode()); + + SmallPtrSet<const Instruction *, 32> Visited; + // Get output footprint for I. + SetVector<int> OutputFootprint = getOutputFootprint(I, Visited); + + // Consider output footprint in the hash. + for (const int &Output : OutputFootprint) + Hash = hashing::detail::hash_16_bytes(Hash, Output); + + // Base instruction name. + SmallString<256> Name; + Name.append("vl" + std::to_string(Hash).substr(0, 5)); + + // In case of CallInst, consider callee in the instruction name. + if (const auto *CI = dyn_cast<CallInst>(I)) { + Function *F = CI->getCalledFunction(); + + if (F != nullptr) { + Name.append(F->getName()); + } + } + + Name.append("("); + for (unsigned long i = 0; i < Operands.size(); ++i) { + Name.append(Operands[i]); + + if (i < Operands.size() - 1) + Name.append(", "); + } + Name.append(")"); + + I->setName(Name); +} + +/// Names instruction following the scheme: +/// op00000Callee(Operands) +/// +/// Where 00000 is a hash calculated considering instruction's opcode, its +/// operands' opcodes and order. Callee's name is only included when +/// instruction's type is CallInst. In cases where instruction is commutative, +/// operand list is also sorted. +/// +/// Names instructions recursively in accordance with the def-use tree, +/// starting from the initial instructions (defs), finishing at +/// the output (top-most user) instructions (depth-first). +/// +/// Renames instruction only when RenameAll flag is raised or instruction is +/// unnamed. +/// +/// \see getOutputFootprint() +/// \param I Instruction to be renamed. +void IRCanonicalizer::nameAsRegularInstruction(Instruction *I) { + // Instruction operands for further sorting. + SmallVector<SmallString<128>, 4> Operands; + + // The name of a regular instruction depends + // on the names of its operands. Hence, all + // operands must be named first in the use-def + // walk. + + // Collect operands. + for (auto &OP : I->operands()) { + if (auto *IOP = dyn_cast<Instruction>(OP)) { + // Walk down the use-def chain. + nameInstruction(IOP); + Operands.push_back(IOP->getName()); + } else if (isa<Value>(OP) && !isa<Function>(OP)) { + // This must be an immediate value. + std::string TextRepresentation; + raw_string_ostream Stream(TextRepresentation); + OP->printAsOperand(Stream, false); + Operands.push_back(StringRef(Stream.str())); + } + } + + if (I->isCommutative()) + llvm::sort(Operands.begin(), Operands.end()); + + // Initialize to a magic constant, so the state isn't zero. + uint64_t Hash = MagicHashConstant; + + // Consider instruction opcode in the hash. + Hash = hashing::detail::hash_16_bytes(Hash, I->getOpcode()); + + // Operand opcodes for further sorting (commutative). + SmallVector<int, 4> OperandsOpcodes; + + // Collect operand opcodes for hashing. + for (auto &OP : I->operands()) + if (auto *IOP = dyn_cast<Instruction>(OP)) + OperandsOpcodes.push_back(IOP->getOpcode()); + + if (I->isCommutative()) + llvm::sort(OperandsOpcodes.begin(), OperandsOpcodes.end()); + + // Consider operand opcodes in the hash. + for (const int Code : OperandsOpcodes) + Hash = hashing::detail::hash_16_bytes(Hash, Code); + + // Base instruction name. + SmallString<512> Name; + Name.append("op" + std::to_string(Hash).substr(0, 5)); + + // In case of CallInst, consider callee in the instruction name. + if (const auto *CI = dyn_cast<CallInst>(I)) + if (const Function *F = CI->getCalledFunction()) + Name.append(F->getName()); + + Name.append("("); + for (unsigned long i = 0; i < Operands.size(); ++i) { + Name.append(Operands[i]); + + if (i < Operands.size() - 1) + Name.append(", "); + } + Name.append(")"); + + if ((I->getName().empty() || RenameAll) && !I->getType()->isVoidTy()) + I->setName(Name); +} + +/// Shortens instruction's name. This method removes called function name from +/// the instruction name and substitutes the call chain with a corresponding +/// list of operands. +/// +/// Examples: +/// op00000Callee(op00001Callee(...), vl00000Callee(1, 2), ...) -> +/// op00000(op00001, vl00000, ...) vl00000Callee(1, 2) -> vl00000(1, 2) +/// +/// This method omits output instructions and pre-output (instructions directly +/// used by an output instruction) instructions (by default). By default it also +/// does not affect user named instructions. +/// +/// \param I Instruction whose name will be folded. +void IRCanonicalizer::foldInstructionName(Instruction *I) { + // If this flag is raised, fold all regular + // instructions (including pre-outputs). + if (!FoldPreoutputs) { + // Don't fold if one of the users is an output instruction. + for (auto *U : I->users()) + if (auto *IU = dyn_cast<Instruction>(U)) + if (isOutput(IU)) + return; + } + + // Don't fold if it is an output instruction or has no op prefix. + if (isOutput(I) || I->getName().substr(0, 2) != "op") + return; + + // Instruction operands. + SmallVector<SmallString<64>, 4> Operands; + + for (auto &OP : I->operands()) { + if (const Instruction *IOP = dyn_cast<Instruction>(OP)) { + bool HasCanonicalName = I->getName().substr(0, 2) == "op" || + I->getName().substr(0, 2) == "vl"; + + Operands.push_back(HasCanonicalName ? IOP->getName().substr(0, 7) + : IOP->getName()); + } + } + + if (I->isCommutative()) + llvm::sort(Operands.begin(), Operands.end()); + + SmallString<256> Name; + Name.append(I->getName().substr(0, 7)); + + Name.append("("); + for (unsigned long i = 0; i < Operands.size(); ++i) { + Name.append(Operands[i]); + + if (i < Operands.size() - 1) + Name.append(", "); + } + Name.append(")"); + + I->setName(Name); +} + +/// Reorders instructions by walking up the tree from each operand of an output +/// instruction and reducing the def-use distance. +/// This method assumes that output instructions were collected top-down, +/// otherwise the def-use chain may be broken. +/// This method is a wrapper for recursive reorderInstruction(). +/// +/// \see reorderInstruction() +/// \param Outputs Vector of pointers to output instructions collected top-down. +void IRCanonicalizer::reorderInstructions( + SmallVector<Instruction *, 16> &Outputs) { + // This method assumes output instructions were collected top-down, + // otherwise the def-use chain may be broken. + + SmallPtrSet<const Instruction *, 32> Visited; + + // Walk up the tree. + for (auto &I : Outputs) + for (auto &OP : I->operands()) + if (auto *IOP = dyn_cast<Instruction>(OP)) + reorderInstruction(IOP, I, Visited); +} + +/// Reduces def-use distance or places instruction at the end of the basic +/// block. Continues to walk up the def-use tree recursively. Used by +/// reorderInstructions(). +/// +/// \see reorderInstructions() +/// \param Used Pointer to the instruction whose value is used by the \p User. +/// \param User Pointer to the instruction which uses the \p Used. +/// \param Visited Set of visited instructions. +void IRCanonicalizer::reorderInstruction( + Instruction *Used, Instruction *User, + SmallPtrSet<const Instruction *, 32> &Visited) { + + if (!Visited.count(Used)) { + Visited.insert(Used); + + if (Used->getParent() == User->getParent()) { + // If Used and User share the same basic block move Used just before User. + Used->moveBefore(User); + } else { + // Otherwise move Used to the very end of its basic block. + Used->moveBefore(&Used->getParent()->back()); + } + + for (auto &OP : Used->operands()) { + if (auto *IOP = dyn_cast<Instruction>(OP)) { + // Walk up the def-use tree. + reorderInstruction(IOP, Used, Visited); + } + } + } +} + +/// Reorders instruction's operands alphabetically. This method assumes +/// that passed instruction is commutative. Changing the operand order +/// in other instructions may change the semantics. +/// +/// \param I Instruction whose operands will be reordered. +void IRCanonicalizer::reorderInstructionOperandsByNames(Instruction *I) { + // This method assumes that passed I is commutative, + // changing the order of operands in other instructions + // may change the semantics. + + // Instruction operands for further sorting. + SmallVector<std::pair<std::string, Value *>, 4> Operands; + + // Collect operands. + for (auto &OP : I->operands()) { + if (auto *VOP = dyn_cast<Value>(OP)) { + if (isa<Instruction>(VOP)) { + // This is an an instruction. + Operands.push_back( + std::pair<std::string, Value *>(VOP->getName(), VOP)); + } else { + std::string TextRepresentation; + raw_string_ostream Stream(TextRepresentation); + OP->printAsOperand(Stream, false); + Operands.push_back(std::pair<std::string, Value *>(Stream.str(), VOP)); + } + } + } + + // Sort operands. + llvm::sort(Operands.begin(), Operands.end(), llvm::less_first()); + + // Reorder operands. + unsigned Position = 0; + for (auto &OP : I->operands()) { + OP.set(Operands[Position].second); + Position++; + } +} + +/// Reorders PHI node's values according to the names of corresponding basic +/// blocks. +/// +/// \param PN PHI node to canonicalize. +void IRCanonicalizer::reorderPHIIncomingValues(PHINode *PN) { + // Values for further sorting. + SmallVector<std::pair<Value *, BasicBlock *>, 2> Values; + + // Collect blocks and corresponding values. + for (auto &BB : PN->blocks()) { + Value *V = PN->getIncomingValueForBlock(BB); + Values.push_back(std::pair<Value *, BasicBlock *>(V, BB)); + } + + // Sort values according to the name of a basic block. + llvm::sort(Values, [](const std::pair<Value *, BasicBlock *> &LHS, + const std::pair<Value *, BasicBlock *> &RHS) { + return LHS.second->getName() < RHS.second->getName(); + }); + + // Swap. + for (unsigned i = 0; i < Values.size(); ++i) { + PN->setIncomingBlock(i, Values[i].second); + PN->setIncomingValue(i, Values[i].first); + } +} + +/// Returns a vector of output instructions. An output is an instruction which +/// has side-effects or is ReturnInst. Uses isOutput(). +/// +/// \see isOutput() +/// \param F Function to collect outputs from. +SmallVector<Instruction *, 16> +IRCanonicalizer::collectOutputInstructions(Function &F) { + // Output instructions are collected top-down in each function, + // any change may break the def-use chain in reordering methods. + SmallVector<Instruction *, 16> Outputs; + + for (auto &I : instructions(F)) + if (isOutput(&I)) + Outputs.push_back(&I); + + return Outputs; +} + +/// Helper method checking whether the instruction may have side effects or is +/// ReturnInst. +/// +/// \param I Considered instruction. +bool IRCanonicalizer::isOutput(const Instruction *I) { + // Outputs are such instructions which may have side effects or is ReturnInst. + if (I->mayHaveSideEffects() || isa<ReturnInst>(I)) + return true; + + return false; +} + +/// Helper method checking whether the instruction has users and only +/// immediate operands. +/// +/// \param I Considered instruction. +bool IRCanonicalizer::isInitialInstruction(const Instruction *I) { + // Initial instructions are such instructions whose values are used by + // other instructions, yet they only depend on immediate values. + return !I->user_empty() && hasOnlyImmediateOperands(I); +} + +/// Helper method checking whether the instruction has only immediate operands. +/// +/// \param I Considered instruction. +bool IRCanonicalizer::hasOnlyImmediateOperands(const Instruction *I) { + for (const auto &OP : I->operands()) + if (isa<Instruction>(OP)) + return false; // Found non-immediate operand (instruction). + + return true; +} + +/// Helper method returning indices (distance from the beginning of the basic +/// block) of outputs using the \p I (eliminates repetitions). Walks down the +/// def-use tree recursively. +/// +/// \param I Considered instruction. +/// \param Visited Set of visited instructions. +SetVector<int> IRCanonicalizer::getOutputFootprint( + Instruction *I, SmallPtrSet<const Instruction *, 32> &Visited) { + + // Vector containing indexes of outputs (no repetitions), + // which use I in the order of walking down the def-use tree. + SetVector<int> Outputs; + + if (!Visited.count(I)) { + Visited.insert(I); + + if (isOutput(I)) { + // Gets output instruction's parent function. + Function *Func = I->getParent()->getParent(); + + // Finds and inserts the index of the output to the vector. + unsigned Count = 0; + for (const auto &B : *Func) { + for (const auto &E : B) { + if (&E == I) + Outputs.insert(Count); + Count++; + } + } + + // Returns to the used instruction. + return Outputs; + } + + for (auto *U : I->users()) { + if (auto *UI = dyn_cast<Instruction>(U)) { + // Vector for outputs which use UI. + SetVector<int> OutputsUsingUI = getOutputFootprint(UI, Visited); + + // Insert the indexes of outputs using UI. + Outputs.insert(OutputsUsingUI.begin(), OutputsUsingUI.end()); + } + } + } + + // Return to the used instruction. + return Outputs; +} >From d59bcfc2ccfd156e6ea152fc423feb213c169221 Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Sat, 12 Aug 2023 15:55:40 -0700 Subject: [PATCH 02/16] Port IRCanonicalizer to new pass manager --- .../llvm/Transforms/Utils/IRCanonicalizer.h | 15 +++++++++++++ llvm/lib/Passes/PassBuilder.cpp | 1 + llvm/lib/Passes/PassRegistry.def | 1 + llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 22 +++++++++---------- 4 files changed, 27 insertions(+), 12 deletions(-) create mode 100644 llvm/include/llvm/Transforms/Utils/IRCanonicalizer.h diff --git a/llvm/include/llvm/Transforms/Utils/IRCanonicalizer.h b/llvm/include/llvm/Transforms/Utils/IRCanonicalizer.h new file mode 100644 index 000000000000000..81bfd1bcfd2ad94 --- /dev/null +++ b/llvm/include/llvm/Transforms/Utils/IRCanonicalizer.h @@ -0,0 +1,15 @@ +#ifndef LLVM_TRANSFORMS_UTILS_IRCANONICALIZER_H +#define LLVM_TRANSFORMS_UTILS_IRCANONICALIZER_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// IRCanonicalizer aims to transform LLVM IR into canonical form. +struct IRCanonicalizerPass : public PassInfoMixin<IRCanonicalizerPass> { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_IRCANONICALIZER_H diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp index bb6b40b14f8b4c8..7b626f7df91cb39 100644 --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -237,6 +237,7 @@ #include "llvm/Transforms/Utils/HelloWorld.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/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def index fe24e9da9125ff7..fd30e5a8b4b58b8 100644 --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -300,6 +300,7 @@ FUNCTION_PASS("bdce", BDCEPass()) FUNCTION_PASS("bounds-checking", BoundsCheckingPass()) FUNCTION_PASS("break-crit-edges", BreakCriticalEdgesPass()) FUNCTION_PASS("callsite-splitting", CallSiteSplittingPass()) +FUNCTION_PASS("canon", IRCanonicalizerPass()) FUNCTION_PASS("consthoist", ConstantHoistingPass()) FUNCTION_PASS("count-visits", CountVisitsPass()) FUNCTION_PASS("constraint-elimination", ConstraintEliminationPass()) diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp index 58e2dce0b96685b..afa3d94e7f55be6 100644 --- a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -28,6 +28,7 @@ #include "llvm/PassRegistry.h" #include "llvm/Support/CommandLine.h" #include "llvm/Transforms/Utils.h" +#include "llvm/Transforms/Utils/IRCanonicalizer.h" #include <algorithm> #include <vector> @@ -37,10 +38,8 @@ using namespace llvm; namespace { /// IRCanonicalizer aims to transform LLVM IR into canonical form. -class IRCanonicalizer : public FunctionPass { +class IRCanonicalizer { public: - static char ID; - /// \name Canonicalizer flags. /// @{ /// Preserves original order of instructions. @@ -53,10 +52,7 @@ class IRCanonicalizer : public FunctionPass { static cl::opt<bool> ReorderOperands; /// @} - /// Constructor for the IRCanonicalizer. - IRCanonicalizer() : FunctionPass(ID) {} - - bool runOnFunction(Function &F) override; + bool runOnFunction(Function &F); private: // Random constant for hashing, so the state isn't zero. @@ -94,11 +90,6 @@ class IRCanonicalizer : public FunctionPass { }; } // namespace -char IRCanonicalizer::ID = 0; -static RegisterPass<IRCanonicalizer> X("canon", "Canonicalize the IR", - false /* Only looks at CFG */, - false /* Analysis Pass */); - cl::opt<bool> IRCanonicalizer::PreserveOrder( "preserve-order", cl::Hidden, cl::desc("Preserves original instruction order")); @@ -630,3 +621,10 @@ SetVector<int> IRCanonicalizer::getOutputFootprint( // Return to the used instruction. return Outputs; } + +PreservedAnalyses IRCanonicalizerPass::run(Function &F, + FunctionAnalysisManager &AM) { + errs() << F.getName() << "\n"; + IRCanonicalizer{}.runOnFunction(F); + return PreservedAnalyses::all(); +} >From 0c94ebab9a31092edfc409df6ffa922269fcf867 Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Sat, 12 Aug 2023 16:06:29 -0700 Subject: [PATCH 03/16] Port doc updates --- llvm/docs/Passes.rst | 8 ++++++++ llvm/docs/ReleaseNotes.rst | 5 ++++- 2 files changed, 12 insertions(+), 1 deletion(-) diff --git a/llvm/docs/Passes.rst b/llvm/docs/Passes.rst index 541e23677debf90..418ab17eb35e259 100644 --- a/llvm/docs/Passes.rst +++ b/llvm/docs/Passes.rst @@ -653,6 +653,14 @@ variables with initializers are marked as internal. An interprocedural variant of :ref:`Sparse Conditional Constant Propagation <passes-sccp>`. +``-ir-canonicalizer``: Transforms IR into canonical form +-------------------------------------------------------- + +This pass 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 +two different passes. + ``-jump-threading``: Jump Threading ----------------------------------- diff --git a/llvm/docs/ReleaseNotes.rst b/llvm/docs/ReleaseNotes.rst index 8eb8affb5eba9e2..dec2eec7566929e 100644 --- a/llvm/docs/ReleaseNotes.rst +++ b/llvm/docs/ReleaseNotes.rst @@ -42,7 +42,10 @@ Non-comprehensive list of changes in this release functionality, or simply have a lot to talk about), see the `NOTE` below for adding a new subsection. -* ... +* Added a new IRCanonicalizer pass 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 + when diffing two modules which have undergone different passes. Update on required toolchains to build LLVM ------------------------------------------- >From 9dbcab1948bba93e61d80a10038ab471f99e1448 Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Sat, 12 Aug 2023 16:29:46 -0700 Subject: [PATCH 04/16] Port tests --- .../IRCanonicalizer/naming-arguments.ll | 7 ++++++ .../IRCanonicalizer/naming-basic-blocks.ll | 8 +++++++ .../IRCanonicalizer/naming-instructions.ll | 12 ++++++++++ .../reordering-instructions.ll | 14 +++++++++++ .../reordering-phi-node-values.ll | 24 +++++++++++++++++++ 5 files changed, 65 insertions(+) create mode 100644 llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll create mode 100644 llvm/test/Transforms/IRCanonicalizer/naming-basic-blocks.ll create mode 100644 llvm/test/Transforms/IRCanonicalizer/naming-instructions.ll create mode 100644 llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll create mode 100644 llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll diff --git a/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll b/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll new file mode 100644 index 000000000000000..b3f7630abd042f1 --- /dev/null +++ b/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll @@ -0,0 +1,7 @@ +; RUN: opt -S -passes=canon < %s | FileCheck %s + +; CHECK: @foo(i32 %a0, i32 %a1) +define i32 @foo(i32, i32) { + %tmp = mul i32 %0, %1 + ret i32 %tmp +} diff --git a/llvm/test/Transforms/IRCanonicalizer/naming-basic-blocks.ll b/llvm/test/Transforms/IRCanonicalizer/naming-basic-blocks.ll new file mode 100644 index 000000000000000..79e526f8efb7ac7 --- /dev/null +++ b/llvm/test/Transforms/IRCanonicalizer/naming-basic-blocks.ll @@ -0,0 +1,8 @@ +; RUN: opt -S -passes=canon --rename-all < %s | FileCheck %s + +define i32 @foo(i32 %a0) { +; CHECK: bb{{([0-9]{5})}} +entry: + %a = add i32 %a0, 2 + ret i32 %a +} diff --git a/llvm/test/Transforms/IRCanonicalizer/naming-instructions.ll b/llvm/test/Transforms/IRCanonicalizer/naming-instructions.ll new file mode 100644 index 000000000000000..a22e816f5bf01e9 --- /dev/null +++ b/llvm/test/Transforms/IRCanonicalizer/naming-instructions.ll @@ -0,0 +1,12 @@ +; RUN: opt -S -passes=canon --rename-all < %s | FileCheck %s + +define i32 @foo(i32 %a0) { +entry: +; CHECK: %"vl{{([0-9]{5})}}(%a0, 2)" + %a = add i32 %a0, 2 +; CHECK: %"op{{([0-9]{5})}}(vl{{([0-9]{5})}})" + %b = add i32 %a, 6 +; CHECK: %"op{{([0-9]{5})}}(8, op{{([0-9]{5})}}(6, vl{{([0-9]{5})}}(%a0, 2)))" + %c = add i32 %b, 8 + ret i32 %c +} diff --git a/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll b/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll new file mode 100644 index 000000000000000..04660ac73c11bd2 --- /dev/null +++ b/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll @@ -0,0 +1,14 @@ +; RUN: opt -S -passes=canon < %s | FileCheck %s + +define double @foo(double %a0, double %a1) { +entry: +; CHECK: %a +; CHECK: %c +; CHECK: %b +; CHECK: %d + %a = fmul double %a0, %a1 + %b = fmul double %a0, 2.000000e+00 + %c = fmul double %a, 6.000000e+00 + %d = fmul double %b, 6.000000e+00 + ret double %d +} diff --git a/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll b/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll new file mode 100644 index 000000000000000..5f344ec29be66f0 --- /dev/null +++ b/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll @@ -0,0 +1,24 @@ +; RUN: opt -S -passes=canon < %s | FileCheck %s + +declare double @foo() + +declare double @bar() + +define double @baz(double %x) { +entry: + %ifcond = fcmp one double %x, 0.000000e+00 + br i1 %ifcond, label %then, label %else + +then: ; preds = %entry + %calltmp = call double @foo() + br label %ifcont + +else: ; preds = %entry + %calltmp1 = call double @bar() + br label %ifcont + +ifcont: ; preds = %else, %then +; CHECK: %iftmp = phi double [ %calltmp1, %else ], [ %calltmp, %then ] + %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ] + ret double %iftmp +} >From f5b7445662310a2f329e0f4aaf45822058f307ba Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Sat, 19 Aug 2023 15:23:09 -0700 Subject: [PATCH 05/16] Turn rename-all and -reorder-operands on by default --- llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 6 ++++-- llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll | 2 +- .../Transforms/IRCanonicalizer/reordering-instructions.ll | 2 +- .../IRCanonicalizer/reordering-phi-node-values.ll | 2 +- 4 files changed, 7 insertions(+), 5 deletions(-) diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp index afa3d94e7f55be6..b5a007c80b32b3f 100644 --- a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -95,13 +95,15 @@ cl::opt<bool> IRCanonicalizer::PreserveOrder( cl::desc("Preserves original instruction order")); cl::opt<bool> IRCanonicalizer::RenameAll( "rename-all", cl::Hidden, - cl::desc("Renames all instructions (including user-named)")); + cl::desc("Renames all instructions (including user-named)"), + cl::init(true)); cl::opt<bool> IRCanonicalizer::FoldPreoutputs( "fold-all", cl::Hidden, cl::desc("Folds all regular instructions (including pre-outputs)")); cl::opt<bool> IRCanonicalizer::ReorderOperands( "reorder-operands", cl::Hidden, - cl::desc("Sorts and reorders operands in commutative instructions")); + cl::desc("Sorts and reorders operands in commutative instructions"), + cl::init(true)); /// Entry method to the IRCanonicalizer. /// diff --git a/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll b/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll index b3f7630abd042f1..5a274f7cc5a3b70 100644 --- a/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll +++ b/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -passes=canon < %s | FileCheck %s +; RUN: opt -S -passes=canon --rename-all=false < %s | FileCheck %s ; CHECK: @foo(i32 %a0, i32 %a1) define i32 @foo(i32, i32) { diff --git a/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll b/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll index 04660ac73c11bd2..3ea19e8b6c78c97 100644 --- a/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll +++ b/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -passes=canon < %s | FileCheck %s +; RUN: opt -S -passes=canon --rename-all=false < %s | FileCheck %s define double @foo(double %a0, double %a1) { entry: diff --git a/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll b/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll index 5f344ec29be66f0..3ea0bab50b5b9ac 100644 --- a/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll +++ b/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -passes=canon < %s | FileCheck %s +; RUN: opt -S -passes=canon --rename-all=false < %s | FileCheck %s declare double @foo() >From 9f93dea7b9d1fb97f947481ac1211da11b897180 Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Sat, 19 Aug 2023 15:25:12 -0700 Subject: [PATCH 06/16] Add infinite loop regression test --- .../IRCanonicalizer/infinite-loop.ll | 100 ++++++++++++++++++ 1 file changed, 100 insertions(+) create mode 100644 llvm/test/Transforms/IRCanonicalizer/infinite-loop.ll diff --git a/llvm/test/Transforms/IRCanonicalizer/infinite-loop.ll b/llvm/test/Transforms/IRCanonicalizer/infinite-loop.ll new file mode 100644 index 000000000000000..f67c1eb7fa5b223 --- /dev/null +++ b/llvm/test/Transforms/IRCanonicalizer/infinite-loop.ll @@ -0,0 +1,100 @@ +; RUN: opt -passes=canon < %s + +; XFAIL: * +; FIXME: Infinite loop in name instructions + +define void @test(ptr) { +bb: + br label %bb1 + +bb1: ; preds = %bb1, %bb + %tmp = phi i32 [ undef, %bb ], [ %tmp87, %bb1 ] + %tmp2 = phi i32 [ undef, %bb ], [ %tmp86, %bb1 ] + %tmp3 = mul i32 %tmp, undef + %tmp4 = xor i32 %tmp3, -1 + %tmp5 = add i32 %tmp, %tmp4 + %tmp6 = add i32 %tmp2, -1 + %tmp7 = add i32 %tmp5, %tmp6 + %tmp8 = mul i32 %tmp7, %tmp3 + %tmp9 = xor i32 %tmp8, -1 + %tmp10 = add i32 %tmp7, %tmp9 + %tmp11 = add i32 %tmp10, undef + %tmp12 = mul i32 %tmp11, %tmp8 + %tmp13 = xor i32 %tmp12, -1 + %tmp14 = add i32 %tmp11, %tmp13 + %tmp15 = add i32 %tmp14, undef + %tmp16 = mul i32 %tmp15, %tmp12 + %tmp17 = add i32 %tmp15, undef + %tmp18 = add i32 %tmp17, undef + %tmp19 = mul i32 %tmp18, %tmp16 + %tmp20 = xor i32 %tmp19, -1 + %tmp21 = add i32 %tmp18, %tmp20 + %tmp22 = add i32 %tmp21, undef + %tmp23 = mul i32 %tmp22, %tmp19 + %tmp24 = xor i32 %tmp23, -1 + %tmp25 = add i32 %tmp22, %tmp24 + %tmp26 = add i32 %tmp25, undef + %tmp27 = mul i32 %tmp26, %tmp23 + %tmp28 = xor i32 %tmp27, -1 + %tmp29 = add i32 %tmp26, %tmp28 + %tmp30 = add i32 %tmp29, undef + %tmp31 = mul i32 %tmp30, %tmp27 + %tmp32 = xor i32 %tmp31, -1 + %tmp33 = add i32 %tmp30, %tmp32 + %tmp34 = add i32 %tmp33, undef + %tmp35 = mul i32 %tmp34, %tmp31 + %tmp36 = xor i32 %tmp35, -1 + %tmp37 = add i32 %tmp34, %tmp36 + %tmp38 = add i32 %tmp2, -9 + %tmp39 = add i32 %tmp37, %tmp38 + %tmp40 = mul i32 %tmp39, %tmp35 + %tmp41 = xor i32 %tmp40, -1 + %tmp42 = add i32 %tmp39, %tmp41 + %tmp43 = add i32 %tmp42, undef + %tmp44 = mul i32 %tmp43, %tmp40 + %tmp45 = xor i32 %tmp44, -1 + %tmp46 = add i32 %tmp43, %tmp45 + %tmp47 = add i32 %tmp46, undef + %tmp48 = mul i32 %tmp47, %tmp44 + %tmp49 = xor i32 %tmp48, -1 + %tmp50 = add i32 %tmp47, %tmp49 + %tmp51 = add i32 %tmp50, undef + %tmp52 = mul i32 %tmp51, %tmp48 + %tmp53 = xor i32 %tmp52, -1 + %tmp54 = add i32 %tmp51, %tmp53 + %tmp55 = add i32 %tmp54, undef + %tmp56 = mul i32 %tmp55, %tmp52 + %tmp57 = xor i32 %tmp56, -1 + %tmp58 = add i32 %tmp55, %tmp57 + %tmp59 = add i32 %tmp2, -14 + %tmp60 = add i32 %tmp58, %tmp59 + %tmp61 = mul i32 %tmp60, %tmp56 + %tmp62 = xor i32 %tmp61, -1 + %tmp63 = add i32 %tmp60, %tmp62 + %tmp64 = add i32 %tmp63, undef + %tmp65 = mul i32 %tmp64, %tmp61 + %tmp66 = xor i32 %tmp65, -1 + %tmp67 = add i32 %tmp64, %tmp66 + %tmp68 = add i32 %tmp67, undef + %tmp69 = mul i32 %tmp68, %tmp65 + %tmp70 = xor i32 %tmp69, -1 + %tmp71 = add i32 %tmp68, %tmp70 + %tmp72 = add i32 %tmp71, undef + %tmp73 = mul i32 %tmp72, %tmp69 + %tmp74 = xor i32 %tmp73, -1 + %tmp75 = add i32 %tmp72, %tmp74 + %tmp76 = add i32 %tmp75, undef + %tmp77 = mul i32 %tmp76, %tmp73 + %tmp78 = xor i32 %tmp77, -1 + %tmp79 = add i32 %tmp76, %tmp78 + %tmp80 = add i32 %tmp79, undef + %tmp81 = mul i32 %tmp80, %tmp77 + %tmp82 = xor i32 %tmp81, -1 + %tmp83 = add i32 %tmp80, %tmp82 + %tmp84 = add i32 %tmp83, undef + %tmp85 = add i32 %tmp84, undef + %tmp86 = add i32 %tmp2, -21 + %tmp87 = add i32 %tmp85, %tmp86 + store i32 %tmp87, ptr %0 + br label %bb1 +} >From 23a379fc765a86c35b7b9682a66199fdaa1b830f Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Sun, 27 Aug 2023 15:19:36 -0700 Subject: [PATCH 07/16] Add visited set to fix infinite loop bug --- llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp index b5a007c80b32b3f..73433a9a05c0d4e 100644 --- a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -57,6 +57,7 @@ class IRCanonicalizer { private: // Random constant for hashing, so the state isn't zero. const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL; + DenseSet<const Instruction *> NamedInstructions; /// \name Naming. /// @{ @@ -175,6 +176,9 @@ void IRCanonicalizer::nameBasicBlocks(Function &F) { /// /// \param I Instruction to be renamed. void IRCanonicalizer::nameInstruction(Instruction *I) { + if (NamedInstructions.contains(I)) + return; + NamedInstructions.insert(I); // Determine the type of instruction to name. if (isInitialInstruction(I)) { // This is an initial instruction. >From 560abe4f953f75a89e7a0407ff09ea866664a2fd Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Sun, 27 Aug 2023 15:20:12 -0700 Subject: [PATCH 08/16] Expand test to expose reordering bug --- .../Transforms/IRCanonicalizer/infinite-loop.ll | 13 ++++++------- 1 file changed, 6 insertions(+), 7 deletions(-) diff --git a/llvm/test/Transforms/IRCanonicalizer/infinite-loop.ll b/llvm/test/Transforms/IRCanonicalizer/infinite-loop.ll index f67c1eb7fa5b223..3438a05b4aee489 100644 --- a/llvm/test/Transforms/IRCanonicalizer/infinite-loop.ll +++ b/llvm/test/Transforms/IRCanonicalizer/infinite-loop.ll @@ -1,15 +1,14 @@ -; RUN: opt -passes=canon < %s +; RUN: opt -passes=canon -preserve-order=true < %s +; RUN: opt -passes=canon -preserve-order=false < %s -; XFAIL: * -; FIXME: Infinite loop in name instructions - -define void @test(ptr) { +define void @test(ptr, i32) { bb: + %a = add i32 %1, 1 br label %bb1 bb1: ; preds = %bb1, %bb - %tmp = phi i32 [ undef, %bb ], [ %tmp87, %bb1 ] - %tmp2 = phi i32 [ undef, %bb ], [ %tmp86, %bb1 ] + %tmp = phi i32 [ %a, %bb ], [ %tmp87, %bb1 ] + %tmp2 = phi i32 [ %a, %bb ], [ %tmp86, %bb1 ] %tmp3 = mul i32 %tmp, undef %tmp4 = xor i32 %tmp3, -1 %tmp5 = add i32 %tmp, %tmp4 >From 3aaecbddf6a45ba23a32706ac99c8e6e963c924b Mon Sep 17 00:00:00 2001 From: Aidan <aidan.goldf...@mail.mcgill.ca> Date: Mon, 28 Aug 2023 12:28:20 -0400 Subject: [PATCH 09/16] added some documentation --- llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 3 +++ 1 file changed, 3 insertions(+) diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp index 73433a9a05c0d4e..600c2baf6e013a5 100644 --- a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -176,6 +176,9 @@ 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) if (NamedInstructions.contains(I)) return; NamedInstructions.insert(I); >From 2111bf1e6a27c553990528abee3a9fa2c2390bdd Mon Sep 17 00:00:00 2001 From: Aidan <aidan.goldf...@mail.mcgill.ca> Date: Mon, 28 Aug 2023 13:56:05 -0400 Subject: [PATCH 10/16] pushed broken int test --- .../IRCanonicalizer/naming-args-instr-blocks.ll | 15 +++++++++++++++ 1 file changed, 15 insertions(+) create mode 100644 llvm/test/Transforms/IRCanonicalizer/naming-args-instr-blocks.ll diff --git a/llvm/test/Transforms/IRCanonicalizer/naming-args-instr-blocks.ll b/llvm/test/Transforms/IRCanonicalizer/naming-args-instr-blocks.ll new file mode 100644 index 000000000000000..74e1944825011b0 --- /dev/null +++ b/llvm/test/Transforms/IRCanonicalizer/naming-args-instr-blocks.ll @@ -0,0 +1,15 @@ +; RUN: opt -S -passes=canon --rename-all --preserve-order < %s | FileCheck %s + + +; CHECK: @foo(i32 %a0) +define i32 @foo(i32) { +; CHECK: bb{{([0-9]{5})}} +entry: + ; CHECK: %"vl{{([0-9]{5})}}(%a0, 2)" + %a = add i32 %0, 2 + + ; CHECK: %"op{{([0-9]{5})}}(vl{{([0-9]{5})}})" + %b = add i32 %a, 6 + + ret i32 %a +} >From 1db7ecbc4a461295f7cdf04488b94984803a3e60 Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Mon, 11 Sep 2023 12:27:35 -0700 Subject: [PATCH 11/16] Reformat `reorderInstruction` --- llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 30 +++++++++---------- 1 file changed, 15 insertions(+), 15 deletions(-) diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp index 600c2baf6e013a5..6f60d3d261d8286 100644 --- a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -443,23 +443,23 @@ void IRCanonicalizer::reorderInstructions( void IRCanonicalizer::reorderInstruction( Instruction *Used, Instruction *User, SmallPtrSet<const Instruction *, 32> &Visited) { + if (Visited.contains(Used)) { + return; + } + Visited.insert(Used); - if (!Visited.count(Used)) { - Visited.insert(Used); - - if (Used->getParent() == User->getParent()) { - // If Used and User share the same basic block move Used just before User. - Used->moveBefore(User); - } else { - // Otherwise move Used to the very end of its basic block. - Used->moveBefore(&Used->getParent()->back()); - } + if (Used->getParent() == User->getParent()) { + // If Used and User share the same basic block move Used just before User. + Used->moveBefore(User); + } else { + // Otherwise move Used to the very end of its basic block. + Used->moveBefore(&Used->getParent()->back()); + } - for (auto &OP : Used->operands()) { - if (auto *IOP = dyn_cast<Instruction>(OP)) { - // Walk up the def-use tree. - reorderInstruction(IOP, Used, Visited); - } + for (auto &OP : Used->operands()) { + if (auto *IOP = dyn_cast<Instruction>(OP)) { + // Walk up the def-use tree. + reorderInstruction(IOP, Used, Visited); } } } >From 2debd15624fe9b69840551288bec734e8ef2ea75 Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Mon, 11 Sep 2023 13:05:30 -0700 Subject: [PATCH 12/16] Bug fix: don't reorder PHI nodes --- llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp index 6f60d3d261d8286..a40435f7b822932 100644 --- a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -443,9 +443,10 @@ void IRCanonicalizer::reorderInstructions( void IRCanonicalizer::reorderInstruction( Instruction *Used, Instruction *User, SmallPtrSet<const Instruction *, 32> &Visited) { - if (Visited.contains(Used)) { + if(isa<PHINode>(Used)) + return; + if (Visited.contains(Used)) return; - } Visited.insert(Used); if (Used->getParent() == User->getParent()) { >From 8a05e501b94aa50a9802c4df5398dd5a0805572f Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Mon, 11 Sep 2023 13:29:27 -0700 Subject: [PATCH 13/16] Revert "Turn rename-all and -reorder-operands on by default" This reverts commit f5b7445662310a2f329e0f4aaf45822058f307ba. --- llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 6 ++---- llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll | 2 +- .../Transforms/IRCanonicalizer/reordering-instructions.ll | 2 +- .../IRCanonicalizer/reordering-phi-node-values.ll | 2 +- 4 files changed, 5 insertions(+), 7 deletions(-) diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp index a40435f7b822932..45dc954f97b9c7e 100644 --- a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -96,15 +96,13 @@ cl::opt<bool> IRCanonicalizer::PreserveOrder( cl::desc("Preserves original instruction order")); cl::opt<bool> IRCanonicalizer::RenameAll( "rename-all", cl::Hidden, - cl::desc("Renames all instructions (including user-named)"), - cl::init(true)); + cl::desc("Renames all instructions (including user-named)")); cl::opt<bool> IRCanonicalizer::FoldPreoutputs( "fold-all", cl::Hidden, cl::desc("Folds all regular instructions (including pre-outputs)")); cl::opt<bool> IRCanonicalizer::ReorderOperands( "reorder-operands", cl::Hidden, - cl::desc("Sorts and reorders operands in commutative instructions"), - cl::init(true)); + cl::desc("Sorts and reorders operands in commutative instructions")); /// Entry method to the IRCanonicalizer. /// diff --git a/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll b/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll index 5a274f7cc5a3b70..b3f7630abd042f1 100644 --- a/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll +++ b/llvm/test/Transforms/IRCanonicalizer/naming-arguments.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -passes=canon --rename-all=false < %s | FileCheck %s +; RUN: opt -S -passes=canon < %s | FileCheck %s ; CHECK: @foo(i32 %a0, i32 %a1) define i32 @foo(i32, i32) { diff --git a/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll b/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll index 3ea19e8b6c78c97..04660ac73c11bd2 100644 --- a/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll +++ b/llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -passes=canon --rename-all=false < %s | FileCheck %s +; RUN: opt -S -passes=canon < %s | FileCheck %s define double @foo(double %a0, double %a1) { entry: diff --git a/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll b/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll index 3ea0bab50b5b9ac..5f344ec29be66f0 100644 --- a/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll +++ b/llvm/test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -passes=canon --rename-all=false < %s | FileCheck %s +; RUN: opt -S -passes=canon < %s | FileCheck %s declare double @foo() >From fa6159c30002c530f40b41380ed2b64294543c01 Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Mon, 25 Sep 2023 11:13:25 -0500 Subject: [PATCH 14/16] Fix naming-args-instr-blocks.ll --- .../Transforms/IRCanonicalizer/naming-args-instr-blocks.ll | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/llvm/test/Transforms/IRCanonicalizer/naming-args-instr-blocks.ll b/llvm/test/Transforms/IRCanonicalizer/naming-args-instr-blocks.ll index 74e1944825011b0..605c62863f2ad38 100644 --- a/llvm/test/Transforms/IRCanonicalizer/naming-args-instr-blocks.ll +++ b/llvm/test/Transforms/IRCanonicalizer/naming-args-instr-blocks.ll @@ -8,8 +8,8 @@ entry: ; CHECK: %"vl{{([0-9]{5})}}(%a0, 2)" %a = add i32 %0, 2 - ; CHECK: %"op{{([0-9]{5})}}(vl{{([0-9]{5})}})" + ; CHECK: %"op{{([0-9]{5})}}(6, vl{{([0-9]{5})}}(%a0, 2))" %b = add i32 %a, 6 - ret i32 %a + ret i32 %b } >From aaef294128bb37afff42527cefbac08e29f08e95 Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Tue, 3 Oct 2023 21:55:04 -0700 Subject: [PATCH 15/16] clang format changes --- llvm/lib/Passes/PassBuilder.cpp | 4 ++-- llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 12 ++++++------ 2 files changed, 8 insertions(+), 8 deletions(-) diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp index 8a495e6d7dc14fc..7fc17ab31a11ec8 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 45dc954f97b9c7e..7ea3959e5e90d00 100644 --- a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp +++ b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp @@ -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. @@ -381,7 +381,7 @@ void IRCanonicalizer::foldInstructionName(Instruction *I) { SmallVector<SmallString<64>, 4> Operands; for (auto &OP : I->operands()) { - if (const Instruction *IOP = dyn_cast<Instruction>(OP)) { + if (const auto *IOP = dyn_cast<Instruction>(OP)) { bool HasCanonicalName = I->getName().substr(0, 2) == "op" || I->getName().substr(0, 2) == "vl"; @@ -441,7 +441,7 @@ void IRCanonicalizer::reorderInstructions( void IRCanonicalizer::reorderInstruction( Instruction *Used, Instruction *User, SmallPtrSet<const Instruction *, 32> &Visited) { - if(isa<PHINode>(Used)) + if (isa<PHINode>(Used)) return; if (Visited.contains(Used)) return; >From d7b9fd5da45515624c6aa4b321d5d897612d2395 Mon Sep 17 00:00:00 2001 From: justinfargnoli <justinfargn...@gmail.com> Date: Wed, 4 Oct 2023 08:12:40 -0700 Subject: [PATCH 16/16] clang-format changes --- llvm/lib/Transforms/Utils/IRCanonicalizer.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp b/llvm/lib/Transforms/Utils/IRCanonicalizer.cpp index 7ea3959e5e90d00..c12595ba48a3f79 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 <algorithm> #include <vector> _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
