llvm-canon

[mpaszkowski]

Summary

Added a new llvm-canon tool which aims to transform LLVM Modules into a canonical form by reordering and renaming instructions while preserving the same semantics. This tool makes it easier to spot semantic differences while diffing two modules which have undergone different transformation passes.

[lebedev.ri]

Please run clang-format on the patch.
What is the plan for tests here?

tools/llvm-canon/CMakeLists.txt

9 ↗

(On Diff #214431)

The filenames generally start from uppercase letter.

[mgrang]

tools/llvm-canon/canonicalizer.cpp

164 ↗

(On Diff #214431)

Please use the range-based llvm::sort(Operands) instead of std::sort.

See https://llvm.org/docs/CodingStandards.html#beware-of-non-deterministic-sorting-order-of-equal-elements

256 ↗

(On Diff #214431)

Use llvm::sort.
Braces are not needed for single statement if's.

285 ↗

(On Diff #214431)

Ditto.

366 ↗

(On Diff #214431)

Ditto.

467 ↗

(On Diff #214431)

Use llvm::sort.

[hfinkel]

I also recommend that you canonicalize PHI nodes. In past experiments looking for fixed points in the optimization pipeline, this came up as a significant issue. The order of the predecessors in the PHI operand lists don't carry any significance, also also sometimes a predecessor can be listed multiple times (always with the same corresponding value). It's probably best to canonicalize those so each predecessor is listed only once and the blocks appear in their natural order.

At a high level, I'd much rather see the underlying logic under lib/Transforms/Utils, and then we can just run this with opt and we don't need a separate utility.

[Eugene.Zelenko]

tools/llvm-canon/canonicalizer.cpp

1 ↗

(On Diff #214431)

• C++ -* is not needed for .cpp files.

41 ↗

(On Diff #214431)

Please remove unnecessary empty line. Same below.

112 ↗

(On Diff #214431)

Please remove unnecessary empty line.

125 ↗

(On Diff #214431)

Please remove unnecessary empty line.

134 ↗

(On Diff #214431)

Please remove unnecessary empty line.

172 ↗

(On Diff #214431)

Please remove unnecessary empty line.

251 ↗

(On Diff #214431)

Please remove unnecessary empty line.

264 ↗

(On Diff #214431)

Please remove unnecessary empty line.

271 ↗

(On Diff #214431)

Please remove unnecessary empty line.

293 ↗

(On Diff #214431)

Please remove unnecessary empty line.

328 ↗

(On Diff #214431)

Please remove unnecessary empty line.

332 ↗

(On Diff #214431)

Please remove unnecessary empty line.

416 ↗

(On Diff #214431)

Please remove unnecessary empty line.

596 ↗

(On Diff #214431)

Please add // namespace llvm

598 ↗

(On Diff #214431)

Please remove unnecessary empty lines.

tools/llvm-canon/canonicalizer.h

44 ↗

(On Diff #214431)

Please use default member initialization for this and next members.

99 ↗

(On Diff #214431)

Please add // namespace llvm

101 ↗

(On Diff #214431)

Please add // LLVM_TOOLS_LLVM_CANON_CANONICALIZER_H

tools/llvm-canon/llvm-canon.cpp

1 ↗

(On Diff #214431)

C++ -* is not needed for .cpp files.

48 ↗

(On Diff #214431)

Please remove unnecessary empty line.

81 ↗

(On Diff #214431)

Please remove unnecessary empty lines.

[Eugene.Zelenko]

Please also add documentation and mention new tool in LLVM documentation and Release Notes.

[plotfi]

tools/llvm-canon/canonicalizer.cpp

88 ↗

(On Diff #214431)

What is this magic number? Could this be generated with something like srand at the begining of runOnFunction?

111 ↗

(On Diff #214431)

This function is a little short and only used in one place, could it be dropped and just have

for (auto &I : Outputs)
    nameInstruction(I);

put in its place at the call site?

129 ↗

(On Diff #214431)

clang-format should clean up the formatting here.

154 ↗

(On Diff #214431)

Remove isa<Value>(OP). Seems redundant. As far as I know, every LLVM object is a Value.

169 ↗

(On Diff #214431)

don't think you need -> std::string here.

175 ↗

(On Diff #214431)

Again, consider dropping magic numbers. Come up with something else, like setting based on srand()

185 ↗

(On Diff #214431)

drop braces

267 ↗

(On Diff #214431)

Drop magic number.

277 ↗

(On Diff #214431)

Drop the braces here.

297 ↗

(On Diff #214431)

Drop braces:

// In case of CallInst, consider callee in the instruction name.
if (const CallInst *CI = dyn_cast<CallInst>(I))
    if (const Function *F = CI->getCalledFunction())
        Name.append(F->getName());

307 ↗

(On Diff #214431)

Drop braces.

334 ↗

(On Diff #214431)

Drop braces

351 ↗

(On Diff #214431)

Drop braces and use ternary:

for (auto &OP : I->operands())
    if (const Instruction *IOP = dyn_cast<Instruction>(OP))
            Operands.push_back(
                  (I->getName().substr(0, 2) == "op" || I->getName().substr(0, 2) == "vl") ?
                  // Regular/initial instruction with canonicalized name.
                  IOP->getName().substr(0, 7)) :
                  // User-named instruction, don't substring.
                  Operands.push_back(IOP->getName());

395 ↗

(On Diff #214431)

Drop braces

tools/llvm-canon/canonicalizer.h

1 ↗

(On Diff #214431)

Move to somewhere in llvm/lib/Transforms.

Also, run clang-format on this entire file.

31 ↗

(On Diff #214431)

Rename to IRCanonicalizerPass

42 ↗

(On Diff #214431)

Do you really need both constructors? Why not

Canonicalizer() = delete;
Canonicalizer(bool renameAll = false, bool foldPreoutputs = false)
    : ModulePass(ID),
    renameAll(renameAll),
    foldPreoutputs(foldPreoutputs) {}

53 ↗

(On Diff #214431)

change rename and fold to RenameAll and FoldPreoutputs. They can be named the same for initializers.

65 ↗

(On Diff #214431)

Rename to start with upper case. I believe that is still currently the coding standard.

https://llvm.org/docs/CodingStandards.html#the-low-level-issues

65 ↗

(On Diff #214431)

Change to RenameAll

67 ↗

(On Diff #214431)

change to FoldPreoutputs

[plotfi]

Please add lit tests.

[fdeazeve]

tools/llvm-canon/canonicalizer.cpp

53 ↗

(On Diff #214431)

you can include "llvm/IR/InstIterator.h"

and use for (auto &I : instructions(F))

74 ↗

(On Diff #214431)

Is this comment really necessary? It feels like it is repeating the if statement in the opposite order.

88 ↗

(On Diff #214431)

I might be missing something, but don't we want this algorithm to produce the same result if it's run on the "same" (two identical functions, modulo renaming, etc) function twice in a row?

203 ↗

(On Diff #214431)

Make this an early return at the very start of the function? This entire method has no effects when this if statement is false, correct?

237 ↗

(On Diff #214431)

Please remove unnecessary comment

tools/llvm-canon/canonicalizer.h

94 ↗

(On Diff #214431)

High level comment about the header:

A lot of functions take function pointers instead of references, and yet they are never check for nullptr. This makes me believe you really wanted them to be references. In fact, if you check how those functions are called, the Instructions were originally references, and before calling the helper functions you are always doing &I

[fdeazeve]

tools/llvm-canon/canonicalizer.cpp

235 ↗

(On Diff #214431)

Isn't this a reference to a pointer? I think you meant auto *OP. The reason I'm saying this is because you use dyn_cast below, and yet dyn_cast doesn't work with references.

298 ↗

(On Diff #214431)

Guidelines suggest using auto * when copying pointers. https://llvm.org/docs/CodingStandards.html#beware-unnecessary-copies-with-auto

329 ↗

(On Diff #214431)

typo: flag

[alexandre.isoard]

Seems like a great idea!

Could we have an option to only rename without reordering? I have found, in the past, some issue that were order sensitive, but rarely name sensitive, and it would be great to be able to debug those.
Also, in my personal implementation I had missed anonymous types and anonymous global variable, I don't know if we captured those here.

Note that I'm not sure if we can name all metadata or function attribute lists.

[mpaszkowski]

First of all, thank you for your valuable feedback!

In D66029#1623654, @lebedev.ri wrote:

Please run clang-format on the patch.
What is the plan for tests here?

Sure, will run clang-format!

When it comes to tests, I don't have any plan yet. I am not sure if testing every scenario is the best solution here - the canonicalization techniques may change easily as these are my 'best' approaches.
Can you think of any way how to test it sensibly?

In D66029#1623760, @hfinkel wrote:

I also recommend that you canonicalize PHI nodes. In past experiments looking for fixed points in the optimization pipeline, this came up as a significant issue. The order of the predecessors in the PHI operand lists don't carry any significance, also also sometimes a predecessor can be listed multiple times (always with the same corresponding value). It's probably best to canonicalize those so each predecessor is listed only once and the blocks appear in their natural order.

At a high level, I'd much rather see the underlying logic under lib/Transforms/Utils, and then we can just run this with opt and we don't need a separate utility.

I will take a look at PHI nodes and move the pass to Transforms.

In D66029#1626100, @alexandre.isoard wrote:

Seems like a great idea!

Could we have an option to only rename without reordering? I have found, in the past, some issue that were order sensitive, but rarely name sensitive, and it would be great to be able to debug those.
Also, in my personal implementation I had missed anonymous types and anonymous global variable, I don't know if we captured those here.

Note that I'm not sure if we can name all metadata or function attribute lists.

I will add the option to run just naming or reordering - both stages are independent. We also haven't considered anonymous types and anonymous global variables.

[mpaszkowski]

I would like to thank everyone for your valuable feedback! I have fixed the code and moved the pass to lib/Tranfroms/Utils. I hope I have correctly integrated the pass with the rest of the LLVM (we should have some checklist for that).

[mpaszkowski]

tools/llvm-canon/canonicalizer.cpp

88 ↗

(On Diff #214431)

You are right, this number cannot be generated by srand. We want the canonicalization to be deterministic.

[mpaszkowski]

• PHI node canonicalization
• Tests
• Release notes
• Docs

[mpaszkowski]

We have been experimenting with various ways of reordering output instructions hoping to add it now, but it looks to be much tougher than we thought. We hope to add it in a next commit.

@hfinkel
Now the canonicalizer sorts values in PHI nodes. After a discussion, I have decided not to remove duplicates. Those duplicates could come from some other passes and in my opinion, the canonicalizer should make them stand out instead of removing them.
Values are sorted alphabetically according to canonicalized names of corresponding basic blocks.

I am open to suggestions. I would like to ask for a final review of the updated diff. Especially I would like to know if I have integrated the pass with the rest of the LLVM correctly.

[hfinkel]

Now the canonicalizer sorts values in PHI nodes. After a discussion, I have decided not to remove duplicates. Those duplicates could come from some other passes and in my opinion, the canonicalizer should make them stand out instead of removing them.

I suppose that you mean that, if passes are introducing duplicates, that's something that we'd rather fix? That might be true. I'm okay with proceeding on this basis. If we need the deduplicating behavior we'll find out.

[mpaszkowski]

In D66029#1639228, @hfinkel wrote:

Now the canonicalizer sorts values in PHI nodes. After a discussion, I have decided not to remove duplicates. Those duplicates could come from some other passes and in my opinion, the canonicalizer should make them stand out instead of removing them.

I suppose that you mean that, if passes are introducing duplicates, that's something that we'd rather fix? That might be true. I'm okay with proceeding on this basis. If we need the deduplicating behavior we'll find out.

Yes, this is exactly what I meant . We will see how this works, as you said alternatively we can add that later.

Does the rest of the code look good to you? I will need someone to commit this patch for me (I don't have commit rights).

[plotfi]

Looking a lot better.

[mpaszkowski]

Gentle ping ;)

I would like to ask someone to commit this for me. I don't have commit rights.

[lebedev.ri]

Some initial comments.
In general:

• Don't spell out type if you just used *cast<???>
• Don't drop */& after auto
• Do end files with newline
• Consider small-size optimization. Please try to see if some of these std::string can be replaced with reasonably-sized llvm::SmallString<?>
• Please consider preallocating some strings
• This needs a bit more refactoring i think

docs/Passes.rst

693

Too many -

include/llvm/Transforms/Utils/IRCanonicalizer.h

96

Please make sure that files end with newlines

lib/Transforms/Utils/IRCanonicalizer.cpp

38–46

Should these have defaults?

58–79

runOnFunction() ?

74

if(auto *PN = dyn_cast<PHINode>(&I))

151–171

This block will result in most of memory nagging in this pass.

152

Can you make any reasonable guess as to what would be 90'th percentile of Operand string length?
Maybe try using SmallString<64>.

167

It would be really good to predict+preallocate the size here.

184

const int& output = ?
The type is not clear to me here.

191

auto* CI

220

Same comments as for the previous function

264

auto* IOP

271

const int Code = ?

278

const auto *CI

306

auto*

307

auto*

332–336

I'm sensing a repetitive pattern. I think you want to refactor it.

389

auto*

428–431

llvm::less_first

505

!I->user_empty() ?

[plotfi]

In D66029#1648887, @mpaszkowski wrote:

Gentle ping ;)

I would like to ask someone to commit this for me. I don't have commit rights.

I don't know the current process but I think you should ask for them and commit it yourself so that you get the credit (and the blame :-P ) for this work.

PL

[mpaszkowski]

lib/Transforms/Utils/IRCanonicalizer.cpp

38–46

They are all false by default, this is why I haven't explicitly stated their value. I don't think this will change in the future.

58–79

Yes! I don't know why I haven't changed this any earlier.

167

Changed to standard for-loop and moved to the end of the function.

332–336

The pattern only repeats for creating the operand list.

[mpaszkowski]

Updated the diff for the new revision, refactored naming functions, accepted suggestions by lebedev.
Thank you for the review! @lebedev.ri
Is the code ready for the mainline?

[aykevl]

Just a drive by comment from someone interested in this pass.

docs/Passes.rst

697

It looks like this sentence is not finished.

[mpaszkowski]

Thanks, will fix that!

[mpaszkowski]

First of all, I am sorry for such a late reply (had many things going on recently). I have updated the patch for the upstream version of the LLVM. Thanks to @aykevl I have corrected the docs/Passes.rst file. Additionaly, I have added a new flag which enables/disables sorting and reordering operands in commutative instructions.

In the meantime, the project has been presented at the LLVM Developers' Meeting 2019 in San Jose. You may want to check out the slides or watch the presentation.

I would like to thank everyone who came to the presentation for all the valuable feedback and support! It was really nice to see you all.

Hopefully, the code looks good now. I would like to ask for further comments and eventual LGTM so the code can be committed to the mainline.

[mpaszkowski]

Gentle ping! Is the code ready for the mainline?
Could you @plotfi take a look?

[plotfi]

I've got a few nits. Will do a second pass shortly.

llvm/lib/Transforms/Utils/IRCanonicalizer.cpp

175 ↗

(On Diff #257243)

get this to conform to llvm style (ie OutputFootprint)

178 ↗

(On Diff #257243)

Output as well.

234 ↗

(On Diff #257243)

nit: auto *IOP

326 ↗

(On Diff #257243)

nit: HasCanonicalName

370 ↗

(On Diff #257243)

not: auto *IOP

421 ↗

(On Diff #257243)

not: auto *VOP

439 ↗

(On Diff #257243)

nit: Position

461 ↗

(On Diff #257243)

nit: LHS and RHS

517 ↗

(On Diff #257243)

for (const auto &OP : I->operands())
  if (isa<Instruction>(OP))
    return false; // Found non-immediate operand (instruction).

548 ↗

(On Diff #257243)

unsigned Count = 0;
for (const auto &B : *Func) {
  for (const auto &E : B) {
    if (&E == I)
      Outputs.insert(Count);
    Count++;
  }
}

562 ↗

(On Diff #257243)

nit: auto *U and auto *UI

[plotfi]

Please update the diff so the new HarborMaster setup can run some tests on it :-)

[plotfi]

llvm/include/llvm/Transforms/Utils/IRCanonicalizer.h

1 ↗

(On Diff #257243)

Does this need to be a separate header? Can the class be contained in a anonymous namespace in the .cpp file (IRCanonicalizer.cpp) like some of the other passes?

61 ↗

(On Diff #257243)

Is there any significance of this magic number? Can you either set this by a cl::opt or generated at runtime (maybe something using srand (time(NULL))) ?

[plotfi]

Ping? Any Update on this? I think this is close to an LGTM.

[mpaszkowski]

Thank you @plotfi for review! I will update the diff in a second.

llvm/include/llvm/Transforms/Utils/IRCanonicalizer.h

61 ↗

(On Diff #257243)

There is no significance in this particular number but it needs to be consistent among all canonicalized modules (so this shouldn't be set by cl::opt or randomly generated). I have used particularly this number since it has been used in many other places in LLVM, for example here.

[mpaszkowski]

Updated the diff with suggestions from @plotfi.

[mpaszkowski]

How do we get HarborMaster to run tests on the patch?

[plotfi]

In D66029#2016444, @mpaszkowski wrote:

How do we get HarborMaster to run tests on the patch?

I thought it just does it. Strange. Maybe because this is an older diff?

[plotfi]

llvm/test/Transforms/IRCanonicalizer/reordering-instructions.ll

5 ↗

(On Diff #261662)

consider making the last 3 check lines "CHECK-NEXT"

tools/llvm-canon/canonicalizer.cpp

88 ↗

(On Diff #214431)

Ah yes, that makes a lot of sense. The MIR Canonicalizer ran into the same sort of issue. That's why the value-numbering-esque rewrite of it doesn't hash certain types of MachineOperands that might be different run to run.

[plotfi]

Nice work. I think this LGTM.

[mpaszkowski]

In D66029#2028455, @plotfi wrote:

Nice work. I think this LGTM.

Thank you @plotfi ! I will update one of the tests and request commit access :)

[mpaszkowski]

Reverted the commit and reopened the review after unsuccessful builds:

1. builder clang-cmake-x86_64-sde-avx512-linux while building llvm
2. clang-armv7-linux-build-cache while building llvm
3. clang-aarch64-linux-build-cache while building llvm
4. clang-cmake-x86_64-avx2-linux while building cfe

[mpaszkowski]

@plotfi Should I create a new review so that the HarborMaster will be able run the builds after the fix?

[plotfi]

In D66029#2052030, @mpaszkowski wrote:

@plotfi Should I create a new review so that the HarborMaster will be able run the builds after the fix?

If updating this review did not trigger it, go ahead and create a new one. Sorry for the late reply @mpaszkowski.

[plotfi]

@mpaszkowski ping

[mpaszkowski]

In D66029#2255874, @plotfi wrote:

@mpaszkowski ping

Sorry, I will update the review and commit again at the end of next week.

[mpaszkowski]

Updated the patch to for the new version of LLVM. Currently the pass still utilizes the legacy pass manager. The pass will be ported to the new pass manager in a separate review.

docs/Passes.rst

 the mess.
 
 ``-ipsccp``: Interprocedural Sparse Conditional Constant Propagation
 --------------------------------------------------------------------
 
 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
+
 ``-jump-threading``: Jump Threading
 -----------------------------------
 
 Jump threading tries to find distinct threads of control flow running through a
 basic block.  This pass looks at blocks that have multiple predecessors and
 multiple successors.  If one or more of the predecessors of the block can be
 proven to always cause a jump to one of the successors, we forward the edge
 from the predecessor to the successor by duplicating the contents of this

docs/ReleaseNotes.rst

.. NOTE
    For small 1-3 sentence descriptions, just add an entry at the end of
    this list. If your description won't fit comfortably in one bullet
    point (e.g. maybe you would like to give an example of the
    functionality, or simply have a lot to talk about), see the `NOTE` below
    for adding a new subsection.
 
 * The ISD::FP_ROUND_INREG opcode and related code was removed from SelectionDAG.
 * Enabled MemorySSA as a loop dependency.
+* 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.
 
 .. NOTE
    If you would like to document a larger change, then you can add a
    subsection about it right here. You can copy the following boilerplate
    and un-indent it (the indentation causes it to be inside this comment).
 
    Special New Feature
    -------------------

include/llvm/InitializePasses.h

 void initializeGlobalSplitPass(PassRegistry&);
 void initializeGlobalsAAWrapperPassPass(PassRegistry&);
 void initializeGuardWideningLegacyPassPass(PassRegistry&);
 void initializeHardwareLoopsPass(PassRegistry&);
 void initializeHotColdSplittingLegacyPassPass(PassRegistry&);
 void initializeHWAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeIPCPPass(PassRegistry&);
 void initializeIPSCCPLegacyPassPass(PassRegistry&);
+void initializeIRCanonicalizerPass(PassRegistry&);
 void initializeIRCELegacyPassPass(PassRegistry&);
 void initializeIRTranslatorPass(PassRegistry&);
 void initializeIVUsersWrapperPassPass(PassRegistry&);
 void initializeIfConverterPass(PassRegistry&);
 void initializeImplicitNullChecksPass(PassRegistry&);
 void initializeIndVarSimplifyLegacyPassPass(PassRegistry&);
 void initializeIndirectBrExpandPassPass(PassRegistry&);
 void initializeInferAddressSpacesPass(PassRegistry&);

include/llvm/LinkAllPasses.h

 #include "llvm/Transforms/ObjCARC.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Scalar/InstSimplifyPass.h"
 #include "llvm/Transforms/Scalar/Scalarizer.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/SymbolRewriter.h"
 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
+#include "llvm/Transforms/Utils/IRCanonicalizer.h"
 #include "llvm/Transforms/Vectorize.h"
 #include <cstdlib>
 
 namespace {
   struct ForcePassLinking {
     ForcePassLinking() {
       // We must reference the passes in such a way that compilers will not
       // delete it all as dead code, even with whole program optimization,
ForcePassLinking() {
       (void) llvm::createAlwaysInlinerLegacyPass();
       (void) llvm::createGlobalDCEPass();
       (void) llvm::createGlobalOptimizerPass();
       (void) llvm::createGlobalsAAWrapperPass();
       (void) llvm::createGuardWideningPass();
       (void) llvm::createLoopGuardWideningPass();
       (void) llvm::createIPConstantPropagationPass();
       (void) llvm::createIPSCCPPass();
+      (void) llvm::createIRCanonicalizerPass();
       (void) llvm::createInductiveRangeCheckEliminationPass();
       (void) llvm::createIndVarSimplifyPass();
       (void) llvm::createInstSimplifyLegacyPass();
       (void) llvm::createInstructionCombiningPass();
       (void) llvm::createInternalizePass();
       (void) llvm::createLCSSAPass();
       (void) llvm::createLegacyDivergenceAnalysisPass();
       (void) llvm::createLICMPass();

include/llvm/Transforms/Utils/IRCanonicalizer.h

+//===---------------- IRCanonicalizer.h - IR Canonicalizer ------*- C++ -*-===//
+//
+// 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 header declares 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.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_IRCANONICALIZER_H
+#define LLVM_TRANSFORMS_UTILS_IRCANONICALIZER_H
+
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/PassRegistry.h"
+#include "llvm/Support/CommandLine.h"
+#include <vector>
+
+using namespace llvm;
+
+namespace llvm {
+
+/// 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;
+  /// @}
+
+  /// Constructor for the IRCanonicalizer.
+  IRCanonicalizer() : FunctionPass(ID) {
+    initializeIRCanonicalizerPass(*PassRegistry::getPassRegistry());
+  }
+
+  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);
+  /// @}
+};
+
+Pass *createIRCanonicalizerPass();
+
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_IRCANONICALIZER_H

lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   FunctionComparator.cpp
   FunctionImportUtils.cpp
   GlobalStatus.cpp
   GuardUtils.cpp
   InlineFunction.cpp
   ImportedFunctionsInliningStatistics.cpp
   InstructionNamer.cpp
   IntegerDivision.cpp
+  IRCanonicalizer.cpp
   LCSSA.cpp
   LibCallsShrinkWrap.cpp
   Local.cpp
   LoopRotationUtils.cpp
   LoopSimplify.cpp
   LoopUnroll.cpp
   LoopUnrollAndJam.cpp
   LoopUnrollPeel.cpp

lib/Transforms/Utils/IRCanonicalizer.cpp

+//===--------------- 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/Transforms/Utils/IRCanonicalizer.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.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/Support/CommandLine.h"
+#include <algorithm>
+#include <vector>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "ir-canonicalizer"
+
+char IRCanonicalizer::ID = 0;
+
+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)"));
+
+INITIALIZE_PASS(IRCanonicalizer, "ir-canonicalizer",
+                "Transforms IR into canonical form", false, false)
+
+Pass *llvm::createIRCanonicalizerPass() { return new IRCanonicalizer(); }
+
+/// 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 (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 (auto &OP : I->operands()) {
+    if (isa<Instruction>(OP)) {
+      // Found non-immediate operand (instruction).
+      return false;
+    }
+  }
+
+  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 (auto &B : *Func) {
+        for (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;
+}

lib/Transforms/Utils/Utils.cpp

 
 /// initializeTransformUtils - Initialize all passes in the TransformUtils
 /// library.
 void llvm::initializeTransformUtils(PassRegistry &Registry) {
   initializeAddDiscriminatorsLegacyPassPass(Registry);
   initializeBreakCriticalEdgesPass(Registry);
   initializeCanonicalizeAliasesLegacyPassPass(Registry);
   initializeInstNamerPass(Registry);
+  initializeIRCanonicalizerPass(Registry);
   initializeLCSSAWrapperPassPass(Registry);
   initializeLibCallsShrinkWrapLegacyPassPass(Registry);
   initializeLoopSimplifyPass(Registry);
   initializeLowerInvokeLegacyPassPass(Registry);
   initializeLowerSwitchPass(Registry);
   initializeNameAnonGlobalLegacyPassPass(Registry);
   initializePromoteLegacyPassPass(Registry);
   initializeStripNonLineTableDebugInfoPass(Registry);

test/Transforms/IRCanonicalizer/naming-arguments.ll

+; RUN: opt -S --ir-canonicalizer < %s | FileCheck %s
+
+; CHECK: @foo(i32 %a0, i32 %a1)
+define i32 @foo(i32, i32) {
+  %tmp = mul i32 %0, %1
+  ret i32 %tmp
+}

test/Transforms/IRCanonicalizer/naming-basic-blocks.ll

+; RUN: opt -S --ir-canonicalizer --rename-all < %s | FileCheck %s
+
+define i32 @foo(i32 %a0) {
+; CHECK: bb{{([0-9]{5})}}
+entry:
+  %a = add i32 %a0, 2
+  ret i32 %a
+}

test/Transforms/IRCanonicalizer/naming-instructions.ll

+; RUN: opt -S --ir-canonicalizer --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
+}

test/Transforms/IRCanonicalizer/reordering-instructions.ll

+; RUN: opt -S --ir-canonicalizer < %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
+}

test/Transforms/IRCanonicalizer/reordering-phi-node-values.ll

+; RUN: opt -S --ir-canonicalizer < %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
+}