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