671 lines · cpp
1//===--------------- IRNormalizer.cpp - IR Normalizer ---------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8/// \file9/// This file implements the IRNormalizer class which aims to transform LLVM10/// Modules into a normal form by reordering and renaming instructions while11/// preserving the same semantics. The normalizer makes it easier to spot12/// semantic differences while diffing two modules which have undergone13/// different passes.14///15//===----------------------------------------------------------------------===//16 17#include "llvm/Transforms/Utils/IRNormalizer.h"18#include "llvm/ADT/SetVector.h"19#include "llvm/ADT/SmallPtrSet.h"20#include "llvm/ADT/SmallString.h"21#include "llvm/ADT/SmallVector.h"22#include "llvm/IR/BasicBlock.h"23#include "llvm/IR/Function.h"24#include "llvm/IR/IRBuilder.h"25#include "llvm/IR/InstIterator.h"26#include "llvm/Pass.h"27#include <stack>28 29#define DEBUG_TYPE "normalize"30 31using namespace llvm;32 33namespace {34/// IRNormalizer aims to transform LLVM IR into normal form.35class IRNormalizer {36public:37 bool runOnFunction(Function &F);38 39 IRNormalizer(IRNormalizerOptions Options) : Options(Options) {}40 41private:42 const IRNormalizerOptions Options;43 44 // Random constant for hashing, so the state isn't zero.45 const uint64_t MagicHashConstant = 0x6acaa36bef8325c5ULL;46 DenseSet<const Instruction *> NamedInstructions;47 48 SmallVector<Instruction *, 16> Outputs;49 50 /// \name Naming.51 /// @{52 void nameFunctionArguments(Function &F) const;53 void nameBasicBlocks(Function &F) const;54 void nameInstruction(Instruction *I);55 void nameAsInitialInstruction(Instruction *I) const;56 void nameAsRegularInstruction(Instruction *I);57 void foldInstructionName(Instruction *I) const;58 /// @}59 60 /// \name Reordering.61 /// @{62 void reorderInstructions(Function &F) const;63 void reorderDefinition(Instruction *Definition,64 std::stack<Instruction *> &TopologicalSort,65 SmallPtrSet<const Instruction *, 32> &Visited) const;66 void reorderInstructionOperandsByNames(Instruction *I) const;67 void reorderPHIIncomingValues(PHINode *Phi) const;68 /// @}69 70 /// \name Utility methods.71 /// @{72 template <typename T>73 void sortCommutativeOperands(Instruction *I, T &Operands) const;74 SmallVector<Instruction *, 16> collectOutputInstructions(Function &F) const;75 bool isOutput(const Instruction *I) const;76 bool isInitialInstruction(const Instruction *I) const;77 bool hasOnlyImmediateOperands(const Instruction *I) const;78 SetVector<int>79 getOutputFootprint(Instruction *I,80 SmallPtrSet<const Instruction *, 32> &Visited) const;81 /// @}82};83} // namespace84 85/// Entry method to the IRNormalizer.86///87/// \param F Function to normalize.88bool IRNormalizer::runOnFunction(Function &F) {89 nameFunctionArguments(F);90 nameBasicBlocks(F);91 92 Outputs = collectOutputInstructions(F);93 94 if (!Options.PreserveOrder)95 reorderInstructions(F);96 97 // TODO: Reorder basic blocks via a topological sort.98 99 for (auto &I : Outputs)100 nameInstruction(I);101 102 for (auto &I : instructions(F)) {103 if (!Options.PreserveOrder) {104 if (Options.ReorderOperands)105 reorderInstructionOperandsByNames(&I);106 107 if (auto *Phi = dyn_cast<PHINode>(&I))108 reorderPHIIncomingValues(Phi);109 }110 foldInstructionName(&I);111 }112 113 return true;114}115 116/// Numbers arguments.117///118/// \param F Function whose arguments will be renamed.119void IRNormalizer::nameFunctionArguments(Function &F) const {120 int ArgumentCounter = 0;121 for (auto &A : F.args()) {122 if (Options.RenameAll || A.getName().empty()) {123 A.setName("a" + Twine(ArgumentCounter));124 ArgumentCounter += 1;125 }126 }127}128 129/// Names basic blocks using a generated hash for each basic block in130/// a function considering the opcode and the order of output instructions.131///132/// \param F Function containing basic blocks to rename.133void IRNormalizer::nameBasicBlocks(Function &F) const {134 for (auto &B : F) {135 // Initialize to a magic constant, so the state isn't zero.136 uint64_t Hash = MagicHashConstant;137 138 // Hash considering output instruction opcodes.139 for (auto &I : B)140 if (isOutput(&I))141 Hash = hashing::detail::hash_16_bytes(Hash, I.getOpcode());142 143 if (Options.RenameAll || B.getName().empty()) {144 // Name basic block. Substring hash to make diffs more readable.145 B.setName("bb" + std::to_string(Hash).substr(0, 5));146 }147 }148}149 150/// Names instructions graphically (recursive) in accordance with the151/// def-use tree, starting from the initial instructions (defs), finishing at152/// the output (top-most user) instructions (depth-first).153///154/// \param I Instruction to be renamed.155void IRNormalizer::nameInstruction(Instruction *I) {156 // Ensure instructions are not renamed. This is done157 // to prevent situation where instructions are used158 // before their definition (in phi nodes)159 if (NamedInstructions.contains(I))160 return;161 NamedInstructions.insert(I);162 if (isInitialInstruction(I)) {163 nameAsInitialInstruction(I);164 } else {165 // This must be a regular instruction.166 nameAsRegularInstruction(I);167 }168}169 170template <typename T>171void IRNormalizer::sortCommutativeOperands(Instruction *I, T &Operands) const {172 if (!(I->isCommutative() && Operands.size() >= 2))173 return;174 auto CommutativeEnd = Operands.begin();175 std::advance(CommutativeEnd, 2);176 llvm::sort(Operands.begin(), CommutativeEnd);177}178 179/// Names instruction following the scheme:180/// vl00000Callee(Operands)181///182/// Where 00000 is a hash calculated considering instruction's opcode and output183/// footprint. Callee's name is only included when instruction's type is184/// CallInst. In cases where instruction is commutative, operands list is also185/// sorted.186///187/// Renames instruction only when RenameAll flag is raised or instruction is188/// unnamed.189///190/// \see getOutputFootprint()191/// \param I Instruction to be renamed.192void IRNormalizer::nameAsInitialInstruction(Instruction *I) const {193 if (I->getType()->isVoidTy())194 return;195 if (!(I->getName().empty() || Options.RenameAll))196 return;197 LLVM_DEBUG(dbgs() << "Naming initial instruction: " << *I << "\n");198 199 // Instruction operands for further sorting.200 SmallVector<SmallString<64>, 4> Operands;201 202 // Collect operands.203 for (auto &Op : I->operands()) {204 if (!isa<Function>(Op)) {205 std::string TextRepresentation;206 raw_string_ostream Stream(TextRepresentation);207 Op->printAsOperand(Stream, false);208 Operands.push_back(StringRef(Stream.str()));209 }210 }211 212 sortCommutativeOperands(I, Operands);213 214 // Initialize to a magic constant, so the state isn't zero.215 uint64_t Hash = MagicHashConstant;216 217 // Consider instruction's opcode in the hash.218 Hash = hashing::detail::hash_16_bytes(Hash, I->getOpcode());219 220 SmallPtrSet<const Instruction *, 32> Visited;221 // Get output footprint for I.222 SetVector<int> OutputFootprint = getOutputFootprint(I, Visited);223 224 // Consider output footprint in the hash.225 for (const int &Output : OutputFootprint)226 Hash = hashing::detail::hash_16_bytes(Hash, Output);227 228 // Base instruction name.229 SmallString<256> Name;230 Name.append("vl" + std::to_string(Hash).substr(0, 5));231 232 // In case of CallInst, consider callee in the instruction name.233 if (const auto *CI = dyn_cast<CallInst>(I)) {234 Function *F = CI->getCalledFunction();235 236 if (F != nullptr)237 Name.append(F->getName());238 }239 240 Name.append("(");241 for (size_t i = 0; i < Operands.size(); ++i) {242 Name.append(Operands[i]);243 244 if (i < Operands.size() - 1)245 Name.append(", ");246 }247 Name.append(")");248 249 I->setName(Name);250}251 252/// Names instruction following the scheme:253/// op00000Callee(Operands)254///255/// Where 00000 is a hash calculated considering instruction's opcode, its256/// operands' opcodes and order. Callee's name is only included when257/// instruction's type is CallInst. In cases where instruction is commutative,258/// operand list is also sorted.259///260/// Names instructions recursively in accordance with the def-use tree,261/// starting from the initial instructions (defs), finishing at262/// the output (top-most user) instructions (depth-first).263///264/// Renames instruction only when RenameAll flag is raised or instruction is265/// unnamed.266///267/// \see getOutputFootprint()268/// \param I Instruction to be renamed.269void IRNormalizer::nameAsRegularInstruction(Instruction *I) {270 LLVM_DEBUG(dbgs() << "Naming regular instruction: " << *I << "\n");271 272 // Instruction operands for further sorting.273 SmallVector<SmallString<128>, 4> Operands;274 275 // The name of a regular instruction depends276 // on the names of its operands. Hence, all277 // operands must be named first in the use-def278 // walk.279 280 // Collect operands.281 for (auto &Op : I->operands()) {282 if (auto *I = dyn_cast<Instruction>(Op)) {283 // Walk down the use-def chain.284 nameInstruction(I);285 Operands.push_back(I->getName());286 } else if (!isa<Function>(Op)) {287 // This must be an immediate value.288 std::string TextRepresentation;289 raw_string_ostream Stream(TextRepresentation);290 Op->printAsOperand(Stream, false);291 Operands.push_back(StringRef(Stream.str()));292 }293 }294 295 sortCommutativeOperands(I, Operands);296 297 // Initialize to a magic constant, so the state isn't zero.298 uint64_t Hash = MagicHashConstant;299 300 // Consider instruction opcode in the hash.301 Hash = hashing::detail::hash_16_bytes(Hash, I->getOpcode());302 303 // Operand opcodes for further sorting (commutative).304 SmallVector<int, 4> OperandsOpcodes;305 306 // Collect operand opcodes for hashing.307 for (auto &Op : I->operands())308 if (auto *I = dyn_cast<Instruction>(Op))309 OperandsOpcodes.push_back(I->getOpcode());310 311 sortCommutativeOperands(I, OperandsOpcodes);312 313 // Consider operand opcodes in the hash.314 for (const int Code : OperandsOpcodes)315 Hash = hashing::detail::hash_16_bytes(Hash, Code);316 317 // Base instruction name.318 SmallString<512> Name;319 Name.append("op" + std::to_string(Hash).substr(0, 5));320 321 // In case of CallInst, consider callee in the instruction name.322 if (const auto *CI = dyn_cast<CallInst>(I))323 if (const Function *F = CI->getCalledFunction())324 Name.append(F->getName());325 326 Name.append("(");327 for (size_t i = 0; i < Operands.size(); ++i) {328 Name.append(Operands[i]);329 330 if (i < Operands.size() - 1)331 Name.append(", ");332 }333 Name.append(")");334 335 if ((I->getName().empty() || Options.RenameAll) && !I->getType()->isVoidTy())336 I->setName(Name);337}338 339/// Shortens instruction's name. This method removes called function name from340/// the instruction name and substitutes the call chain with a corresponding341/// list of operands.342///343/// Examples:344/// op00000Callee(op00001Callee(...), vl00000Callee(1, 2), ...) ->345/// op00000(op00001, vl00000, ...) vl00000Callee(1, 2) -> vl00000(1, 2)346///347/// This method omits output instructions and pre-output (instructions directly348/// used by an output instruction) instructions (by default). By default it also349/// does not affect user named instructions.350///351/// \param I Instruction whose name will be folded.352void IRNormalizer::foldInstructionName(Instruction *I) const {353 // If this flag is raised, fold all regular354 // instructions (including pre-outputs).355 if (!Options.FoldPreOutputs) {356 // Don't fold if one of the users is an output instruction.357 for (auto *U : I->users())358 if (auto *IU = dyn_cast<Instruction>(U))359 if (isOutput(IU))360 return;361 }362 363 // Don't fold if it is an output instruction or has no op prefix.364 if (isOutput(I) || !I->getName().starts_with("op"))365 return;366 367 // Instruction operands.368 SmallVector<SmallString<64>, 4> Operands;369 370 for (auto &Op : I->operands()) {371 if (const auto *I = dyn_cast<Instruction>(Op)) {372 bool HasNormalName =373 I->getName().starts_with("op") || I->getName().starts_with("vl");374 375 Operands.push_back(HasNormalName ? I->getName().substr(0, 7)376 : I->getName());377 }378 }379 380 sortCommutativeOperands(I, Operands);381 382 SmallString<256> Name;383 Name.append(I->getName().substr(0, 7));384 385 Name.append("(");386 for (size_t i = 0; i < Operands.size(); ++i) {387 Name.append(Operands[i]);388 389 if (i < Operands.size() - 1)390 Name.append(", ");391 }392 Name.append(")");393 394 I->setName(Name);395}396 397/// Reorders instructions by walking up the tree from each operand of an output398/// instruction and reducing the def-use distance.399/// This method assumes that output instructions were collected top-down,400/// otherwise the def-use chain may be broken.401/// This method is a wrapper for recursive reorderInstruction().402///403/// \see reorderInstruction()404void IRNormalizer::reorderInstructions(Function &F) const {405 for (auto &BB : F) {406 LLVM_DEBUG(dbgs() << "Reordering instructions in basic block: "407 << BB.getName() << "\n");408 // Find the source nodes of the DAG of instructions in this basic block.409 // Source nodes are instructions that have side effects, are terminators, or410 // don't have a parent in the DAG of instructions.411 //412 // We must iterate from the first to the last instruction otherwise side413 // effecting instructions could be reordered.414 415 std::stack<Instruction *> TopologicalSort;416 SmallPtrSet<const Instruction *, 32> Visited;417 for (auto &I : BB) {418 // First process side effecting and terminating instructions.419 if (!(isOutput(&I) || I.isTerminator()))420 continue;421 LLVM_DEBUG(dbgs() << "\tReordering from source effecting instruction: ";422 I.dump());423 reorderDefinition(&I, TopologicalSort, Visited);424 }425 426 for (auto &I : BB) {427 // Process the remaining instructions.428 //429 // TODO: Do more a intelligent sorting of these instructions. For example,430 // separate between dead instructinos and instructions used in another431 // block. Use properties of the CFG the order instructions that are used432 // in another block.433 if (Visited.contains(&I))434 continue;435 LLVM_DEBUG(dbgs() << "\tReordering from source instruction: "; I.dump());436 reorderDefinition(&I, TopologicalSort, Visited);437 }438 439 LLVM_DEBUG(dbgs() << "Inserting instructions into: " << BB.getName()440 << "\n");441 // Reorder based on the topological sort.442 while (!TopologicalSort.empty()) {443 auto *Instruction = TopologicalSort.top();444 auto FirstNonPHIOrDbgOrAlloca = BB.getFirstNonPHIOrDbgOrAlloca();445 if (auto *Call = dyn_cast<CallInst>(&*FirstNonPHIOrDbgOrAlloca)) {446 if (Call->getIntrinsicID() ==447 Intrinsic::experimental_convergence_entry ||448 Call->getIntrinsicID() == Intrinsic::experimental_convergence_loop)449 FirstNonPHIOrDbgOrAlloca++;450 }451 Instruction->moveBefore(FirstNonPHIOrDbgOrAlloca);452 TopologicalSort.pop();453 }454 }455}456 457void IRNormalizer::reorderDefinition(458 Instruction *Definition, std::stack<Instruction *> &TopologicalSort,459 SmallPtrSet<const Instruction *, 32> &Visited) const {460 if (Visited.contains(Definition))461 return;462 Visited.insert(Definition);463 464 {465 const auto *BasicBlock = Definition->getParent();466 const auto FirstNonPHIOrDbgOrAlloca =467 BasicBlock->getFirstNonPHIOrDbgOrAlloca();468 if (FirstNonPHIOrDbgOrAlloca == BasicBlock->end())469 return; // TODO: Is this necessary?470 if (Definition->comesBefore(&*FirstNonPHIOrDbgOrAlloca))471 return; // TODO: Do some kind of ordering for these instructions.472 }473 474 for (auto &Operand : Definition->operands()) {475 if (auto *Op = dyn_cast<Instruction>(Operand)) {476 if (Op->getParent() != Definition->getParent())477 continue; // Only reorder instruction within the same basic block478 reorderDefinition(Op, TopologicalSort, Visited);479 }480 }481 482 LLVM_DEBUG(dbgs() << "\t\tNext in topological sort: "; Definition->dump());483 if (Definition->isTerminator())484 return;485 if (auto *Call = dyn_cast<CallInst>(Definition)) {486 if (Call->isMustTailCall())487 return;488 if (Call->getIntrinsicID() == Intrinsic::experimental_deoptimize)489 return;490 if (Call->getIntrinsicID() == Intrinsic::experimental_convergence_entry)491 return;492 if (Call->getIntrinsicID() == Intrinsic::experimental_convergence_loop)493 return;494 }495 if (auto *BitCast = dyn_cast<BitCastInst>(Definition)) {496 if (auto *Call = dyn_cast<CallInst>(BitCast->getOperand(0))) {497 if (Call->isMustTailCall())498 return;499 }500 }501 502 TopologicalSort.emplace(Definition);503}504 505/// Reorders instruction's operands alphabetically. This method assumes506/// that passed instruction is commutative. Changing the operand order507/// in other instructions may change the semantics.508///509/// \param I Instruction whose operands will be reordered.510void IRNormalizer::reorderInstructionOperandsByNames(Instruction *I) const {511 // This method assumes that passed I is commutative,512 // changing the order of operands in other instructions513 // may change the semantics.514 515 // Instruction operands for further sorting.516 SmallVector<std::pair<std::string, Value *>, 4> Operands;517 518 // Collect operands.519 for (auto &Op : I->operands()) {520 if (auto *V = dyn_cast<Value>(Op)) {521 if (isa<Instruction>(V)) {522 // This is an an instruction.523 Operands.push_back(std::pair<std::string, Value *>(V->getName(), V));524 } else {525 std::string TextRepresentation;526 raw_string_ostream Stream(TextRepresentation);527 Op->printAsOperand(Stream, false);528 Operands.push_back(std::pair<std::string, Value *>(Stream.str(), V));529 }530 }531 }532 533 // Sort operands.534 sortCommutativeOperands(I, Operands);535 536 // Reorder operands.537 unsigned Position = 0;538 for (auto &Op : I->operands()) {539 Op.set(Operands[Position].second);540 Position += 1;541 }542}543 544/// Reorders PHI node's values according to the names of corresponding basic545/// blocks.546///547/// \param Phi PHI node to normalize.548void IRNormalizer::reorderPHIIncomingValues(PHINode *Phi) const {549 // Values for further sorting.550 SmallVector<std::pair<Value *, BasicBlock *>, 2> Values;551 552 // Collect blocks and corresponding values.553 for (auto &BB : Phi->blocks()) {554 Value *V = Phi->getIncomingValueForBlock(BB);555 Values.push_back(std::pair<Value *, BasicBlock *>(V, BB));556 }557 558 // Sort values according to the name of a basic block.559 llvm::sort(Values, [](const std::pair<Value *, BasicBlock *> &LHS,560 const std::pair<Value *, BasicBlock *> &RHS) {561 return LHS.second->getName() < RHS.second->getName();562 });563 564 // Swap.565 for (unsigned i = 0; i < Values.size(); ++i) {566 Phi->setIncomingBlock(i, Values[i].second);567 Phi->setIncomingValue(i, Values[i].first);568 }569}570 571/// Returns a vector of output instructions. An output is an instruction which572/// has side-effects or is ReturnInst. Uses isOutput().573///574/// \see isOutput()575/// \param F Function to collect outputs from.576SmallVector<Instruction *, 16>577IRNormalizer::collectOutputInstructions(Function &F) const {578 // Output instructions are collected top-down in each function,579 // any change may break the def-use chain in reordering methods.580 SmallVector<Instruction *, 16> Outputs;581 for (auto &I : instructions(F))582 if (isOutput(&I))583 Outputs.push_back(&I);584 return Outputs;585}586 587/// Helper method checking whether the instruction may have side effects or is588/// ReturnInst.589///590/// \param I Considered instruction.591bool IRNormalizer::isOutput(const Instruction *I) const {592 // Outputs are such instructions which may have side effects or is ReturnInst.593 return I->mayHaveSideEffects() || isa<ReturnInst>(I);594}595 596/// Helper method checking whether the instruction has users and only597/// immediate operands.598///599/// \param I Considered instruction.600bool IRNormalizer::isInitialInstruction(const Instruction *I) const {601 // Initial instructions are such instructions whose values are used by602 // other instructions, yet they only depend on immediate values.603 return !I->user_empty() && hasOnlyImmediateOperands(I);604}605 606/// Helper method checking whether the instruction has only immediate operands.607///608/// \param I Considered instruction.609bool IRNormalizer::hasOnlyImmediateOperands(const Instruction *I) const {610 for (const auto &Op : I->operands())611 if (isa<Instruction>(Op))612 return false; // Found non-immediate operand (instruction).613 return true;614}615 616/// Helper method returning indices (distance from the beginning of the basic617/// block) of outputs using the \p I (eliminates repetitions). Walks down the618/// def-use tree recursively.619///620/// \param I Considered instruction.621/// \param Visited Set of visited instructions.622SetVector<int> IRNormalizer::getOutputFootprint(623 Instruction *I, SmallPtrSet<const Instruction *, 32> &Visited) const {624 625 // Vector containing indexes of outputs (no repetitions),626 // which use I in the order of walking down the def-use tree.627 SetVector<int> Outputs;628 629 if (!Visited.count(I)) {630 Visited.insert(I);631 632 if (isOutput(I)) {633 // Gets output instruction's parent function.634 Function *Func = I->getParent()->getParent();635 636 // Finds and inserts the index of the output to the vector.637 unsigned Count = 0;638 for (const auto &B : *Func) {639 for (const auto &E : B) {640 if (&E == I)641 Outputs.insert(Count);642 Count += 1;643 }644 }645 646 // Returns to the used instruction.647 return Outputs;648 }649 650 for (auto *U : I->users()) {651 if (auto *UI = dyn_cast<Instruction>(U)) {652 // Vector for outputs which use UI.653 SetVector<int> OutputsUsingUI = getOutputFootprint(UI, Visited);654 // Insert the indexes of outputs using UI.655 Outputs.insert_range(OutputsUsingUI);656 }657 }658 }659 660 // Return to the used instruction.661 return Outputs;662}663 664PreservedAnalyses IRNormalizerPass::run(Function &F,665 FunctionAnalysisManager &AM) const {666 IRNormalizer(Options).runOnFunction(F);667 PreservedAnalyses PA;668 PA.preserveSet<CFGAnalyses>();669 return PA;670}671