New pass to produce more easily-read IR.

[arnt]

Summary

This doesn't change the compiled output, merely reorders the basic blocks.
Frontends tend to create basic blocks in the order they discover that they
need the blocks, which is often not a great order for reading and
understanding the IR output.

The new pass is never called by default, but can be invoked with opt:

opt -S -passes improve-reading-order somefile.bc | less

[arnt]

This patch's reviewer selection algorithm: Those who have changed two or more files in the same directory recently. I hope you don't mind.

[MaskRay]

llvm/lib/Passes/PassBuilder.cpp

1822

Good catch! This is irrelevant to this revision. You may commit it separately.

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp

52

BasicBlock * lastSoFar = nullptr; -> BasicBlock *LastSoFar = nullptr;
for( -> for (

https://llvm.org/docs/CodingStandards.html
docs/Proposals/VariableNames.rst (lower_case vs lowerCase is still a debate; (I prefer snake_case :) ))

llvm/test/Transforms/Util/improve-reading-order.ll

2

Missing -S

[MaskRay]

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp

53

For a not-necessarily-sorted set, you may use SmallPtrSet or DenseSet.

57

This can be a SetVector (since we want determinism but set::set is slow)

135

In some pessimistic cases, preferredNextBlock is of O(|input|^2) and this while loop is cubic..

Do you want to rewrite the loop to use a worklist?

if (condition) {
  complex   /////// I believe the current algorithm only reorders the 'then' part
} else {
  complex    /////// this is not touched
}

[arnt]

Reworked based on good comments from maskray; thanks.

[arnt]

I pushed an update now. Will this comment submit the unsubmitted drafts?

llvm/lib/Passes/PassBuilder.cpp

1822

Can do, but I'll do it at the same time, OK? Haven't figured out how to push from my git monorepo to the svn source of truth yet.

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp

135

The while loop exits as soon as preferredNextBlock() returns non-null, so it's quadratic, not cubic.

I'm not sure whether a rewrite for speed is worthwhile. It'll help if a function has very many dead blocks, exception handlers or targets for a single switch, but it's not clear to me whether it'll ever make such a function readable. Sucking quickly instead of slowly isn't worth much effort.

On the other hand, if a function has, say, a thousand dead blocks, then one may have a particularly strong reason to inspect that function, and printing it shouldn't take thirty minutes.

So I'm on the fence.

I rewrote. You pointed me to SetVector and SetVector wants to be used ;) The new version's weak point is a thousands-wide switch where half the branches fall through to the other half, and the fallen-through-to branches contain many basic blocks and loops and so on. I'll upload a new revision later today.

llvm/test/Transforms/Util/improve-reading-order.ll

2

Ooops, fixed. Why did the tests pass without? It seems I've been running check-llvm-unit instead of check-llvm.

[arnt]

Ran clang-format.

[arnt]

Hi,

neither of you have commented in the past couple of weeks. Should I:

• look for other reviewers? if so, do you have suggestions?
• abandon the feature and merely submit the corrected comment (".inc file")?

Sorry to bother you. I do understand that reviewing isn't high on anyone's priority list.

[hfinkel]

In D60619#1483868, @arnt wrote:

Hi,

neither of you have commented in the past couple of weeks. Should I:

• look for other reviewers? if so, do you have suggestions?
• abandon the feature and merely submit the corrected comment (".inc file")?

Sorry to bother you. I do understand that reviewing isn't high on anyone's priority list.

Looks like there were some coding-convention comments that are not yet addressed (e.g., for variable names).

[arnt]

This revision updates the variable names as requested by hfinkel.

Specifically, I updated all variables and parameter names to start with an
upper-case letter, except loop iterators (for which the upper-case rule
appears to be honoured more in the breach than in the observance).

It does not contain any code changes. But I added some more documentation.

I don't think I will do any more with this unless someone comments on the
substance or purpose of the patch. Commenting on code style is fine, but
a total absence of other comments gets tiresome.

[jdoerfert]

I added various formatting and code comments but other than that, this LGTM.

So, please update according to the comments or respond to them before committing.

llvm/include/llvm/Transforms/Utils/ImproveReadingOrder.h

19

Don't open a namespace in a header.

namespace llvm {
...
}

38

Most "new PM" transformations only expose the run method. See the preferredNextBlock definition comment.

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp

16

Leftover

58

Variable names commonly start with an upper case letter: b -> BB.
You can also simply "iterate" over F: BasicBlock &BB : F

97

uint -> uint64_t (to match getZExtValue)
Also, why do you do sorting through a std::map? Is there a guarantee that it will be sorted (in the way you need it)?
I'd put all in a SmallVector<std::pair<uint64_t, uint64_t>, 8> Ordered., then
call llvm::sort(Ordered);

100

Weight

110

With a vector, as described above, it will be a Successors.append(Ordered.begin(), Ordered.end()).

122

auto u -> BasicBlock *BB

124

It took me a while to see that you only want to find one witness:
Add a break, remove the !HadingTowardsUnreachable.

132

I don't understand the interplay between HeadingTowardsUnreachable and LeadsToUnreachable. Maybe add a comment to explain.

135

I would assume you could use LoopInfo and the nesting depth of loops to reason here as well.

157

If you move this at the beginning of the file you can make it static.

166

i is associated with integers (in my mind). BasicBlock &PossiblePredBB maybe

[fhahn]

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp

97

Or use MapVector, if it accepts std::pair as KeyT https://www.llvm.org/docs/ProgrammersManual.html#llvm-adt-mapvector-h

[fhahn]

As a way to test this on a larger number of cases, could you add it to the default pass pipeline (maybe at multiple points) and bootstrap clang with it (or build the test-suite & co)?

[arnt]

Updated diff coming in a few minutes...

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp

53

I kept SetVector; the performance isn't a problem and its order produces nice results. (Performance is generally not a problem here since the pass's application limits the data size. A million-line function isn't readable in any reading order, see?)

97

There must be dozens of ways to get the order I want (heaviest branch weight first, falling back to input order), all of which have essentially the same performance: fast enough for any function a human can aspire to read.

Why did I pick the one I picked? Most likely because I had worked on STL-heavy code in the days before, and used the same idioms. IMO it doesn't matter. MapVector would be as good, but changing now would just be effort without significant improvement.

132

OK... but let me try here first. It's about happypaths, sad paths and even sadder paths, like code that throws an exception while trying to throw or handle another exception.

Suppose that a function contains a couple of blocks that end with a return and a couple of blocks that end with unreachables. In that case the pass will generally try to output everything that can lead to a return first, but eventually it has to start outputting the blocks whose successors end with either/both unreachables.

Once it has started on a block that is postdominated by one of those unreachables, then it's best to output everything related to that unreachable. For example, if the two unreachables are for throwing "null pointer dereferenced" and "index out of bounds", then it's best to print all of the null-pointer blocks in one group, and all of the index-checking blocks in another group.

So that's what it tries to do: If the current block is already heading for an unreachable, then distinguishes between blocks that lead to the "current" unreachable, and other, even sadder paths unreachables.

I renamed one variable and added a comment. Thanks. Compiling now.

135

I would assume so too, but I still haven't come across any functions where I'm unsatisified with the output order and think that LoopInfo would help.

(I've used this to read code for most of a year now.)

[arnt]

Updates from review by jdoerfert etc

[arnt]

Now with the ones I missed.

Left out are: Some for-loop variable names (AIUI the upper-case rule is widely ignored for those, I join that chorus), and at least one case where I don't see any reason to change type (from std::map) because it's work for insignificant benefit. Maybe I'd do it differently if writing from scratch.

llvm/include/llvm/Transforms/Utils/ImproveReadingOrder.h

19

Ugh. I missed this. Coming.

38

I didn't notice that from the ones I skimmed... is this a rule, and if so, what motivates it?

[lebedev.ri]

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp

18

different pass and debug name will be very confusing.

[arnt]

Respond to a few more comments, by lebedevri and jdoerfert.

[jdoerfert]

I haven't had time to read through the explanation that is to become a comment yet.

llvm/include/llvm/Transforms/Utils/ImproveReadingOrder.h

38

Afaik, not a hard rule, just something I feel is being adapted as the norm.

llvm/lib/Passes/PassBuilder.cpp

1822

git llvm push HEAD~2 will push the last two commits. -n is for dryrun.

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp

117

Please do not use uint, I'm with him: https://stackoverflow.com/a/5678057

[arnt]

Hi,

thanks for pinging.

I've been on vacation since jdoerfert's review (and his blessing to land the patch). I live in Munich, where schools close for two weeks around this time and families pack up to go eat gelato in Italy.

As far as I can remember I attended to everything jdoerfert brought up, and my next task ought to be to rebase it to the current tip-of-trunk and (find out how to) land it.

My primary purpose for these four patches is to learn about the LLVM patch process. I picked four rather different patches precisely because they're different. If some of the four fail I won't cry. But if this is landed I'll rebase another of the four and see if I can get it in, too.

[arnt]

Attends to most comments, not all.

A reqeust to introduce break/continue/goto is more than I'll do. That's
where I stop.

[arnt]

I rebased onto this morning's LLVM now.

I don't have commit access (as far as I can tell at least) and cannot find a way to land code from phabricator, so if this is to land, one of the reviewers has to commit it for me. Is that right?

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp

117

If it pleases you.

124

Sorry, adding break, goto or continue is more than I'll do without compelling, specific reason.

llvm/include/llvm/Transforms/Utils/ImproveReadingOrder.h

+//===- ImproveReadingOrder.h - Improve IR readability -----------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_IMPROVEREADINGORDER_H
+#define LLVM_TRANSFORMS_UTILS_IMPROVEREADINGORDER_H
+
+#include "llvm/ADT/SetVector.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+
+/// This pass reorders the basic blocks in each function such that the function
+/// isn't unnecessarily difficult for a human to read.
+///
+/// Frontends tend to create basic blocks in the order they discover that they
+/// need the blocks, which is often not a great order for reading and
+/// understanding the IR output. This pass reorders the blocks such that blocks
+/// that form a loop tend to be near each other, inner loops are inside outer
+/// loops, blocks that form if(a){b}c are ordered a, b, c, and so on.
+///
+/// This pass does not change either the control flow, instruction order or any
+/// instruction. It also doesn't add, remove or merge blocks. Even if it
+/// discovers dead code, the code is left in the function (at the end of the
+/// function, instead of being mixed with live code).
+///
+/// A convenient way to use this pass is:
+///     opt -S -passes improve-reading-order somefile.bc
+struct ImproveReadingOrder : public PassInfoMixin<ImproveReadingOrder> {
+  ImproveReadingOrder() = default;
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
+};
+} // namespace llvm
+
+#endif

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/SpeculateAroundPHIs.h"
 #include "llvm/Transforms/Scalar/SpeculativeExecution.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
 #include "llvm/Transforms/Scalar/WarnMissedTransforms.h"
 #include "llvm/Transforms/Utils/AddDiscriminators.h"
 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "llvm/Transforms/Utils/CanonicalizeAliases.h"
 #include "llvm/Transforms/Utils/EntryExitInstrumenter.h"
+#include "llvm/Transforms/Utils/ImproveReadingOrder.h"
 #include "llvm/Transforms/Utils/LCSSA.h"
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
 #include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LowerInvoke.h"
 #include "llvm/Transforms/Utils/Mem2Reg.h"
 #include "llvm/Transforms/Utils/NameAnonGlobals.h"
 #include "llvm/Transforms/Utils/SymbolRewriter.h"
 #include "llvm/Transforms/Vectorize/LoadStoreVectorizer.h"
if (Matches[1] == "default") {
       MPM.addPass(buildLTOPreLinkDefaultPipeline(L, DebugLogging));
     } else {
       assert(Matches[1] == "lto" && "Not one of the matched options!");
       MPM.addPass(buildLTODefaultPipeline(L, DebugLogging, nullptr));
     }
     return Error::success();
   }
 
-  // Finally expand the basic registered passes from the .inc file.
+  // Finally expand the basic registered passes from PassRegistry.def.
 #define MODULE_PASS(NAME, CREATE_PASS)                                         \
   if (Name == NAME) {                                                          \
     MPM.addPass(CREATE_PASS);                                                  \
     return Error::success();                                                   \
   }
 #define MODULE_ANALYSIS(NAME, CREATE_PASS)                                     \
   if (Name == "require<" NAME ">") {                                           \
     MPM.addPass(                                                               \

llvm/lib/Passes/PassRegistry.def

 FUNCTION_PASS("no-op-function", NoOpFunctionPass())
 FUNCTION_PASS("libcalls-shrinkwrap", LibCallsShrinkWrapPass())
 FUNCTION_PASS("loweratomic", LowerAtomicPass())
 FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass())
 FUNCTION_PASS("lower-guard-intrinsic", LowerGuardIntrinsicPass())
 FUNCTION_PASS("lower-widenable-condition", LowerWidenableConditionPass())
 FUNCTION_PASS("guard-widening", GuardWideningPass())
 FUNCTION_PASS("gvn", GVN())
+FUNCTION_PASS("improve-reading-order", ImproveReadingOrder())
 FUNCTION_PASS("load-store-vectorizer", LoadStoreVectorizerPass())
 FUNCTION_PASS("loop-simplify", LoopSimplifyPass())
 FUNCTION_PASS("loop-sink", LoopSinkPass())
 FUNCTION_PASS("lowerinvoke", LowerInvokePass())
 FUNCTION_PASS("mem2reg", PromotePass())
 FUNCTION_PASS("memcpyopt", MemCpyOptPass())
 FUNCTION_PASS("mergeicmps", MergeICmpsPass())
 FUNCTION_PASS("mldst-motion", MergedLoadStoreMotionPass())

llvm/lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   Evaluator.cpp
   FlattenCFG.cpp
   FunctionComparator.cpp
   FunctionImportUtils.cpp
   GlobalStatus.cpp
   GuardUtils.cpp
   InlineFunction.cpp
   ImportedFunctionsInliningStatistics.cpp
+  ImproveReadingOrder.cpp
   InstructionNamer.cpp
   IntegerDivision.cpp
   LCSSA.cpp
   LibCallsShrinkWrap.cpp
   Local.cpp
   LoopRotationUtils.cpp
   LoopSimplify.cpp
   LoopUnroll.cpp

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp

+//===- ImproveReadingOrder.cpp - Improve IR readability ---------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/ImproveReadingOrder.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "improve-reading-order"
+
+static BasicBlock *preferredNextBlock(SetVector<BasicBlock *> &Input,
+                                      const PostDominatorTree &PDT) {
+  BasicBlock *Result = nullptr;
+  BasicBlock *BetterCandidate = Input.back();
+  while (BetterCandidate) {
+    Result = BetterCandidate;
+    BetterCandidate = nullptr;
+
+    SmallVector<BasicBlock *, 16> PossiblePredecessors;
+    PDT.getDescendants(Result, PossiblePredecessors);
+    for (auto i : PossiblePredecessors) {
+      if (i != Result && Input.count(i)) {
+        BetterCandidate = i;
+        break;
+      }
+    }
+  }
+  Input.remove(Result);
+  return Result;
+}
+
+// Reorder the function's basic blocks so the happy path is near the top and
+// the exceptional cases move down. The general order is: Happy path first, then
+// in-function error handling, then exception handlers, finally dead code.
+//
+// The result has exactly the same control flow graph as the input, the only
+// difference is that if you need to read IR output, then the blocks that form a
+// loop or other group tend to be together in the IR. In code like the
+// following, the IR blocks tend to be ordered in order of these lines, even if
+// the frontend creates blocks in a totally different order:
+//
+//     if(a)
+//       for(b : c)
+//         e(b);
+//     else
+//       for(e : f)
+//         g(a, e);
+//
+// This makes no difference for the code generators, but can lower the strain on
+// a poor brain trying to read IR code.
+//
+// The order of the basic blocks is based largely on the control flow graph and
+// branch weights, although in some cases the order in the input is used. This
+// seems to matter mostly for the switch instruction.
+
+// It never uses source line numbers, because I've found that that helps little
+// in the best cases and hurts readability significantly in the worst (when the
+// function is based on macros and/or inlining).
+
+PreservedAnalyses ImproveReadingOrder::run(Function &F,
+                                           FunctionAnalysisManager &FAM) {
+  BasicBlock *LastSoFar = nullptr;
+  SmallPtrSet<BasicBlock *, 16> Processed;
+  SetVector<BasicBlock *> ToBeDone;
+  SetVector<BasicBlock *> ExceptionHandlers;
+
+  SmallPtrSet<BasicBlock *, 16> BlocksWithUnreachables;
+  for (auto &b : F.getBasicBlockList())
+    if (isa<UnreachableInst>(b.getTerminator()))
+      BlocksWithUnreachables.insert(&b);
+
+  PostDominatorTree &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
+
+  BasicBlock *Current = &F.getEntryBlock();
+  while (Current) {
+    Processed.insert(Current);
+    if (LastSoFar)
+      Current->moveAfter(LastSoFar);
+    LastSoFar = Current;
+
+    Instruction *Terminator = Current->getTerminator();
+    MDNode *BranchWeights = Terminator->getMetadata(LLVMContext::MD_prof);
+    SmallVector<BasicBlock *, 16> Successors;
+    if (isa<InvokeInst>(Terminator)) {
+      // Invoke's normal destination is the happy path
+      InvokeInst *Invoke = cast<InvokeInst>(Terminator);
+      Successors.push_back(Invoke->getUnwindDest());
+      Successors.push_back(Invoke->getNormalDest());
+    } else if (Terminator->getNumSuccessors() == 2 &&
+               PDT.dominates(Terminator->getSuccessor(0),
+                             Terminator->getSuccessor(1))) {
+      // This is an if-then construction without any else clause, so we prefer
+      // to start with the 'then' block.
+      Successors.push_back(Terminator->getSuccessor(0));
+      Successors.push_back(Terminator->getSuccessor(1));
+    } else if (Terminator->getNumSuccessors() == 2 &&
+               PDT.dominates(Terminator->getSuccessor(1),
+                             Terminator->getSuccessor(0))) {
+      // This too is an if-then construction, so ditto
+      Successors.push_back(Terminator->getSuccessor(1));
+      Successors.push_back(Terminator->getSuccessor(0));
+    } else if (BranchWeights) {
+      // There are branch weights; we start with the most-likely branches, and
+      // use successor numbers just for tiebreaking.
+      assert(BranchWeights->getNumOperands() ==
+             Terminator->getNumSuccessors() + 1);
+      std::map<std::pair<unsigned int, unsigned int>, BasicBlock *> Ordered;
+      unsigned int n = 0;
+      while (n < Terminator->getNumSuccessors()) {
+        ConstantInt *Weight =
+            mdconst::dyn_extract<ConstantInt>(BranchWeights->getOperand(n + 1));
+        assert(Weight && "Weight should be a ConstantInt");
+        assert(Weight->getValue().getActiveBits() <= 32 &&
+               "Too many bits for uint32_t");
+        Ordered.emplace(
+            std::make_pair((unsigned int)(Weight->getZExtValue()), n),
+            Terminator->getSuccessor(n));
+        n++;
+      }
+      for (auto it : Ordered)
+        Successors.push_back(it.second);
+    } else {
+      // There's nothing to base any decision on... we'll start with the
+      // lowest-numbered successor. This is ungood: Most of switch's arguments
+      // form an unordered set, so this bases basic block order on an unordered
+      // aspect of the input syntax rather than on a significant aspect of the
+      // code.
+      unsigned int n = Terminator->getNumSuccessors();
+      while (n-- > 0)
+        Successors.push_back(Terminator->getSuccessor(n));
+    }
+    BasicBlock *UnreachablePostDominator = nullptr;
+    for (BasicBlock *BB : BlocksWithUnreachables)
+      if (!UnreachablePostDominator && PDT.dominates(BB, Current))
+        UnreachablePostDominator = BB;
+    // If the current block is post-dominated by a block that ends with
+    // unreachable, then it's best to emit blocks related to that unreachable,
+    // and wait with blocks that have other successors.  (This generally means
+    // that all of the code that's involved in throwing one exception, or one
+    // kind of exception, goes together.)
+    for (auto s : Successors) {
+      if (!Processed.count(s)) {
+        bool LeadsToOtherUnreachable = false;
+        for (auto u : BlocksWithUnreachables)
+          if (u != UnreachablePostDominator && PDT.dominates(u, s))
+            LeadsToOtherUnreachable = true;
+        if (LeadsToOtherUnreachable) {
+          ExceptionHandlers.insert(s);
+        } else {
+          // Later insertion has to win over earlier so that inner loops are
+          // inside outer loops.
+          ToBeDone.remove(s);
+          ToBeDone.insert(s);
+        }
+      }
+    }
+
+    while (Current && Processed.count(Current)) {
+      if (!ToBeDone.empty())
+        Current = preferredNextBlock(ToBeDone, PDT);
+      else if (!ExceptionHandlers.empty())
+        Current = preferredNextBlock(ExceptionHandlers, PDT);
+      else
+        Current = nullptr;
+    }
+  }
+
+  return PreservedAnalyses::all();
+}

llvm/test/Transforms/Util/improve-reading-order.ll

+; RUN: opt -S -passes improve-reading-order < %s | FileCheck %s
+
+; test utility/debugging pass that reorders basic block for easier
+; reading, without making any functional changes.
+
+; the function below is typed by hand, with blocks made in the order a
+; simplistic frontend might might make them. it's sort of like:
+;
+;  if(bar) {
+;  } else {
+;  }
+;  if(bar) {
+;    for(int i = 0; i < 10; i++)
+;      test1(42);
+;  }
+;  foo.test1(true); // throws if foo is null
+;  if(foo)
+;    test1(foo, false);
+;  return 1
+
+declare void @throw()
+
+define i32 @test1(i32 %foo, i1 %bar) {
+entry:
+  br label %if1
+
+if1:
+  br i1 0, label %then1, label %else1
+
+continue1:
+  br i1 0, label %then2, label %continue2
+
+then1:
+  br label %continue1
+
+else1:
+  br label %continue1
+
+continue2:
+  %cmp2 = icmp eq i32 %foo, 0
+  br i1 %cmp2, label %throw1, label %normal1, !prof !2
+
+throw1:
+  call void @throw();
+  unreachable
+
+normal1:
+  br i1 %cmp2, label %then4, label %continue4, !prof !2
+
+then2:
+  br label %loop1
+
+else2:
+  br label %continue2
+
+loop1:
+  %acc = phi i32 [ 0, %then2 ], [ %next, %body1 ]
+  %next = add i32 1, %acc
+  %cmp1 = icmp eq i32 %next, 10
+  br i1 %cmp1, label %body1, label %continue3
+
+continue3:
+  br label %continue2
+
+body1:
+  call i32 @test1(i32 42, i1 0)
+  br label %loop1
+
+then4:
+  br label %continue4
+
+continue4:
+  ret i32 1
+}
+
+!1 = !{!"branch_weights", i32 2, i32 1}
+!2 = !{!"branch_weights", i32 1, i32 2}
+
+; CHECK: entry
+
+; a basic if-then-else gets order matching that description
+; CHECK: if1
+; CHECK: then1
+; CHECK: else1
+; CHECK: continue1
+
+; a basic if-then places all of the then blocks before the continuing
+; block, and a loop head goes before the loop body.
+; CHECK: then2
+; CHECK: loop1
+; CHECK: body1
+; CHECK: continue3
+
+; a null pointer test generally passes, and the code reads better if
+; the jump to the passing code is short, and the exception handler is
+; delayed until far down.
+; CHECK: continue2
+; CHECK: normal1
+
+; an unlikely 'then' branch is best placed before the block it jumps
+; to, even if skipping the 'then' is the most common path
+; CHECK then4
+; CHECK continue4
+
+; exception handlers are pushed towards the end
+; CHECK: throw1
+
+; dead blocks are at the very end
+; CHECK: else2