[mlir][Transforms] Add pass to perform sparse conditional constant propagation

[rriddle]

Summary

This revision adds the initial pass for performing SCCP generically in MLIR. SCCP is an algorithm for propagating constants across control flow, and optimistically assumes all values to be constant unless proven otherwise. It currently supports branching control, with support for regions and inter-procedural propagation being added in followups.

[rriddle]

Cleanup pass summary

[bondhugula]

I think the test cases are missing one of the key scenarios where a control flow path / block isn't executed because the predicate is a constant but that is only known by detecting that the same constant propagates across the back edge as well as the other predecessor. And to know that the same constant propagates, you need to know that the aforementioned control flow path doesn't execute - sort of a catch22. An example (mixed basic blocks with some C for brevity).

func @foo

^bb0:
  c1 = constant 1
  br ^bb1(c1)

^bb1(x1)
 if x1 < 20
   x2 = 1
   br ^bb1(x2)
 else 
   x3 = 50
   br ^bb1(x3)

mlir/include/mlir/Transforms/Passes.td

282

remove -> removed

mlir/test/Transforms/sccp.mlir

38

Nit: No phi's please! PHI values -> arguments ?

[rriddle]

Resolve comments

[rriddle]

Thanks for the review Uday!

I added the test case as simple_loop_inner_control_flow, let me know if that is what you had in mind or if there are any other tests you'd like to see.

[bondhugula]

mlir/lib/Transforms/SCCP.cpp

44–45

Nit: A value with dynamic values can be confusing - instead, A value that cannot statically be determined to be a constant

130

Could you expand this comment?

157

Nit: do either backticks and regular single quotes work for parameters in doc comments?

314

You can with the last output parameter on tryToFold - is this what you were looking for?

bool inPlaceUpdate;
FoldUtils::tryToFold(op, nullptr, nullptr, &inPlaceUpdate);
// operation is folded if inPlaceUpdate is false

345–364

Could this reuse tryToFold?

374–378

Trivial braces.

mlir/test/Transforms/sccp.mlir

101

Mention here to the effect that this is not just inner control flow but you are testing sensitivity to non-executable edges in the CFG.

122–124

You could make this a little stronger/realistic by just doing an IV increment here.

%iv_inc = addi %iv, %cst_1
br ^bb1(%iv_inc)

Still the same result.

126–127

This looks good, but reading the test case in isolation won't make it clear as to what happens to the non-executable edge/path post SCCP on this test case. Does it stay as is, or becomes a dead/unreachable block, or is deleted? Add additional checks depending on what it is? (I just jumped here without looking at all of the actual code)

[bondhugula]

In D78397#1989834, @rriddle wrote:

Thanks for the review Uday!

I added the test case as simple_loop_inner_control_flow, let me know if that is what you had in mind or if there are any other tests you'd like to see.

The test case looks good - thanks. A round of mostly superficial comments. Btw, why is the build failing? I can't tell by chasing the links here:
https://reviews.llvm.org/harbormaster/build/61458/ and the status here is fine as well: https://buildkite.com/mlir/mlir-core
(This is for my future reference as well.)

[rriddle]

Resolve comments

[rriddle]

Thanks for the review!

mlir/lib/Transforms/SCCP.cpp

157

I'm not sure as we don't generate doxygen ATM for me to look at. The codebase is fairly inconsistent to either, but changed all within this file to consistently use ''. We should figure that out though, and standardize to using one.

314

This is a bit of a tricky situation. We don't actually want to fold here, this is essentially just simulated execution with constant parameters. The constants we have here aren't guaranteed to be those at runtime, so it's better to avoid the extra overhead of OperationFolder as we don't want to generated anything at this point.

345–364

Same comment above. We don't want to generate any constant operations here, we just want to know what the output would be. As stated above, the constant values are the current values from the lattice not the current IR. So even if we did use it, it wouldn't give us the result we want.

374–378

Thanks for the catch, they weren't trivial at one point but I forgot to cleanup.

mlir/test/Transforms/sccp.mlir

126–127

Added a few extra checks for making sure various things get folded. ATM we just insert constants. I've debated back and forth about adding in the CFG canonicalizations here, but given that canonicalize can already take care of those I decided to keep the initial versions focused on the propagation.

[rriddle]

Btw, why is the build failing? I can't tell by chasing the links here:
https://reviews.llvm.org/harbormaster/build/61458/ and the status here is fine as well: https://buildkite.com/mlir/mlir-core
(This is for my future reference as well.)

I tried looking at the log, but it seems like it's just failing to create a local git branch to apply the diff to. I have been seeing a lot of harbormaster failures lately that just result to "failed to apply patch". I've just been ignoring these failures if local testing works.

[bondhugula]

mlir/lib/Transforms/SCCP.cpp

314

Right - while the algorithm is still running, a current 'constant' lattice value could be later lowered to the bottom symbol ('overdefined'). But once the algorithm has converged, all 'Unknown' lattice values will become either 'constant' or 'overdefined' at which point we could fold the relevant ops. Do you want to collect such ops? You'll still ideally need a new pattern rewriting driver that takes in a list of ops to process as the starting point. In any case, the comment above on "Don't try to fold the results ... won't be in-place" needs to be fixed - it's misleading because tryToFold does in-place updates as well. Instead, change to "can't guarantee that ... will be out of place"?

[rriddle]

mlir/lib/Transforms/SCCP.cpp

314

Yeah, this is what I mentioned in the comment in the test file. I'm not sure all of the types of foldings we want to do within SCCP itself at this point. Right now we replace any results that were found to be constant and erase any operations that we can, but that doesn't cover all of the potential simplifications we could do. Right now my main goal is to get the constant propagation working across regions and inter-procedurally. After that I think we can tune the amount of additional simplifications we do here based on how it fits into user pipelines. Also, thank you for the comment suggestion!

[bondhugula]

In D78397#1990255, @rriddle wrote:

Btw, why is the build failing? I can't tell by chasing the links here:
https://reviews.llvm.org/harbormaster/build/61458/ and the status here is fine as well: https://buildkite.com/mlir/mlir-core
(This is for my future reference as well.)

I tried looking at the log, but it seems like it's just failing to create a local git branch to apply the diff to. I have been seeing a lot of harbormaster failures lately that just result to "failed to apply patch". I've just been ignoring these failures if local testing works.

Yes, I think nearly all the harbormaster builds from at least the last few days are failing (all for me) - this is also the reason many commits in the last few days broke builds - everyone is ignoring notifications. This is a slippery slope esp with the revisions that are changing CMake files.

[rriddle]

Clarify in-place fold comments

[bondhugula]

Some more comments. Again, I've been looking at things a bit locally. Will take a global look in the next round. Are your test cases still missing scenarios like:

1. paths propagating different constants meeting (you have one with back edges (the last one) but none with the straightforward if/else style).
2. a test case where you have say a multi operand op (say addi) that has one operand coming directly from a constant op and the other via a block argument whose both predecessors send in the same constant.

mlir/lib/Transforms/SCCP.cpp

324

But getResults() is empty!

354

Nit: Try to fold -> Simulate folding .... This is the part that's contradictory in the face of FoldUtils::tryToFold and the comment above "Don't try to fold ..."

359

Why isn't this conservative? If you mark it overdefined already, it can never be highered again. What if some of its operand lattice values are later lowered from unknown to constant? Are you treating both unknown and overdefined in the same way here for simulated folding purposes?

[rriddle]

Resolve comments

[rriddle]

In D78397#1990284, @bondhugula wrote:

Some more comments. Again, I've been looking at things a bit locally. Will take a global look in the next round. Are your test cases still missing scenarios like:

1. paths propagating different constants meeting (you have one with back edges (the last one) but none with the straightforward if/else style).
2. a test case where you have say a multi operand op (say addi) that has one operand coming directly from a constant op and the other via a block argument whose both predecessors send in the same constant.

Added a test case for 1, 2 doesn't seem to cover any new code paths. There is already a test for folding an addi that has an input from a loop iv.

mlir/lib/Transforms/SCCP.cpp

324

getResults isn't necessarily empty if the operations has regions.

359

It already is conservative, if you look above we only get to this point if all of the operands have been resolved. At this point the operands can only go to overdefined, so there isn't a way that more information can be propagated to this point.

[bondhugula]

mlir/lib/Transforms/SCCP.cpp

324

But you've already handled the > 0 regions case in the block above and have returned for all those cases. You don't need the '|| conditional' altogether here.

[rriddle]

Resolve comments

mlir/lib/Transforms/SCCP.cpp

324

Oh duh, sorry about that. Thanks for pointing that out. Accidentally missed that when changing region handling.

[bondhugula]

Since the 'S' in SCCP is for sparse because this is for SSA representations and given that MLIR is all already SSA, there won't be a CCP. So you could just call this file ConditionalConstantPropagation.cpp if you prefer too instead of adding yet another hard to type four letter uppercase acronym. The CL flag could continue to use -sccp or -ccp.

[bondhugula]

Overall, this code looks really good. I can do a complete review unless Jacques/Mehdi who were originally added as reviewers plan to review it anyway.

mlir/lib/Transforms/SCCP.cpp

90

The standard term for this in the SCCP paper and the literature is meet - these are the meet rules. mergeIn -> meet?

132

Typo: any -> many.

359

Thanks - that's what I missed - the check above for unknown operands.

456

argLattice is actually invariant? Hoist it out of the loop, and use it in the block above where you are marking it overdefined.

[rriddle]

Resolve comments

mlir/lib/Transforms/SCCP.cpp

456

It is recomputed in the loop to avoid potential iterator invalidation w.r.t the lattice for the branch operand. Refactored to avoid eagerly constructing the branch operand lattice.

[fhahn]

Conceptually this looks very similar to LLVM's SCCP. Do you anticipate using any MLIR specific properties to cover more cases than the LLVM version? I am not really up-to-speed with the latest on MLIR dialects, but to me it seems like there is a set of transformations where there is currently no additional information to use from MLIR dialects compared to LLVM IR, like SCCP or GVN.

Viewed very simplistically, they only require the following from an IR: SSA, a way to traverse a function along CFG edges, a way to simplify instructions and a way to replace values. Do you think it would be feasible to provide some kind of interface to abstract those and then work towards sharing the implementations of the underlying algorithms between LLVM & MLIR? Or is the plan to duplicate various passes from LLVM also in MLIR?

[rriddle]

In D78397#1990753, @fhahn wrote:

Conceptually this looks very similar to LLVM's SCCP. Do you anticipate using any MLIR specific properties to cover more cases than the LLVM version? I am not really up-to-speed with the latest on MLIR dialects, but to me it seems like there is a set of transformations where there is currently no additional information to use from MLIR dialects compared to LLVM IR, like SCCP or GVN.

Viewed very simplistically, they only require the following from an IR: SSA, a way to traverse a function along CFG edges, a way to simplify instructions and a way to replace values. Do you think it would be feasible to provide some kind of interface to abstract those and then work towards sharing the implementations of the underlying algorithms between LLVM & MLIR? Or is the plan to duplicate various passes from LLVM also in MLIR?

Thanks for the comment Florian! I would be very +1 on sharing common implementations of the more generalized algorithms if we can. From a technical perspective, the major problems I've encountered with bridging the gap are a few impedance mismatches between LLVM and MLIR that arise from different implementation decisions:

• The multi-level aspect leads to special handling for various constructs in MLIR(e.g. regions/structured control flow/etc.) that aren't present in LLVM.
• MLIR globals(like functions) are not SSA values, and require specific handling because they do not use or interact with the traditional SSA use list.
• Block arguments vs PHIs

When adding things in MLIR that already exist in LLVM, at least for me, it is a cost-benefit computation between the amount of work it would take to refactor the thing in LLVM to be usable by MLIR. By amount of work I mean not only the technical aspects, but also the effort to convince the community that it is the right thing to do. I'd love to share as much as possible(as we do for things like ADT/Support/etc) and I'm happy to collaborate in that direction, but if I'm driving it alone the cost has often out-weighed the benefits.

[rriddle]

Tidy up a few things

[mehdi_amini]

In D78397#1990753, @fhahn wrote:

Viewed very simplistically, they only require the following from an IR: SSA, a way to traverse a function along CFG edges, a way to simplify instructions and a way to replace values. Do you think it would be feasible to provide some kind of interface to abstract those and then work towards sharing the implementations of the underlying algorithms between LLVM & MLIR? Or is the plan to duplicate various passes from LLVM also in MLIR?

That'll be an interesting and likely recurring question moving forward. I wonder however if when applicable LLVM would be OK to take a slow-down from generalizing passes to MLIR and going through interfaces for the sake of sharing the implementation?

[rriddle]

Tidy up terminator handling

[fhahn]

In D78397#1990777, @rriddle wrote:

In D78397#1990753, @fhahn wrote:

Conceptually this looks very similar to LLVM's SCCP. Do you anticipate using any MLIR specific properties to cover more cases than the LLVM version? I am not really up-to-speed with the latest on MLIR dialects, but to me it seems like there is a set of transformations where there is currently no additional information to use from MLIR dialects compared to LLVM IR, like SCCP or GVN.

Viewed very simplistically, they only require the following from an IR: SSA, a way to traverse a function along CFG edges, a way to simplify instructions and a way to replace values. Do you think it would be feasible to provide some kind of interface to abstract those and then work towards sharing the implementations of the underlying algorithms between LLVM & MLIR? Or is the plan to duplicate various passes from LLVM also in MLIR?

Thanks for the comment Florian! I would be very +1 on sharing common implementations of the more generalized algorithms if we can. From a technical perspective, the major problems I've encountered with bridging the gap are a few impedance mismatches between LLVM and MLIR that arise from different implementation decisions:

• The multi-level aspect leads to special handling for various constructs in MLIR(e.g. regions/structured control flow/etc.) that aren't present in LLVM.
• MLIR globals(like functions) are not SSA values, and require specific handling because they do not use or interact with the traditional SSA use list.
• Block arguments vs PHIs

Thanks for sharing the list. It seems like handling nested regions/structured control flow would be the most tricky to abstract. I am not really up-to-date on what is possible with nested regions, but would the interactions allowed between different regions be similar across all types of regions or could it be dependent on the region type? I.e. is it safe to propagate constants to all regions or is it unsafe to propagate constants between certain types of regions?

I think the other 2 issues should be fairly straight-forward to abstract.

When adding things in MLIR that already exist in LLVM, at least for me, it is a cost-benefit computation between the amount of work it would take to refactor the thing in LLVM to be usable by MLIR. By amount of work I mean not only the technical aspects, but also the effort to convince the community that it is the right thing to do. I'd love to share as much as possible(as we do for things like ADT/Support/etc) and I'm happy to collaborate in that direction, but if I'm driving it alone the cost has often out-weighed the benefits.

I think that's a reasonable trade-off. I mostly wanted to get a discussions started on that topic, which would definitely not be a short-term kind of project. I'm not too familiar with the MLIR side of things, but I might have a bit of time to collaborate on the LLVM side of such a project. It might be good to sync up/discuss ideas somewhere else than the current review ;)

In D78397#1990865, @mehdi_amini wrote:

In D78397#1990753, @fhahn wrote:

Viewed very simplistically, they only require the following from an IR: SSA, a way to traverse a function along CFG edges, a way to simplify instructions and a way to replace values. Do you think it would be feasible to provide some kind of interface to abstract those and then work towards sharing the implementations of the underlying algorithms between LLVM & MLIR? Or is the plan to duplicate various passes from LLVM also in MLIR?

That'll be an interesting and likely recurring question moving forward. I wonder however if when applicable LLVM would be OK to take a slow-down from generalizing passes to MLIR and going through interfaces for the sake of sharing the implementation?

I think the answer here depends a lot on how this would look like in practice. Are you referring to slow-down in terms of runtime or development?

In terms of run-time overhead, the abstraction would have to be very cheap I think, but that should be feasible as long as it is limited to a few key aspects (like traversing functions/blocks/regions and an interface to simplify instructions given a set of input values (which LLVM has)). In terms of slowing down development, I am personally not too concerned. The passes that seem likely candidates (SCCP, GVN) don't seem to see a huge amount of ongoing development.

I think sharing implementations could be beneficial for both LLVM and MLIR, as it would hopefully mean more users = more testing = more people willing to work on fixes/improvements.

[mehdi_amini]

To clarify I was referring to compile-time slow-down as in LLVM would get slower.

[bondhugula]

Are @jpienaar or @mehdi_amini planning to review this anyway?

[bondhugula]

mlir/lib/Transforms/SCCP.cpp

157

The doxygen is actually generated - it's here. https://mlir.llvm.org/doxygen/

308

If the value is an op result, do you want to / can you erase this op? You already have a pre inc iterator at its call site.

[rriddle]

mlir/lib/Transforms/SCCP.cpp

157

Oh, nice.

308

If you look at Line 281 we erase the op if it is valid and all of the results were replaced.

mlir/include/mlir/Dialect/StandardOps/IR/Ops.td

def BranchOp : Std_Op<"br",
   let verifier = ?;
 
   let extraClassDeclaration = [{
     Block *getDest();
     void setDest(Block *block);
 
     /// Erase the operand at 'index' from the operand list.
     void eraseOperand(unsigned index);
+
+    /// Returns the successor that would be chosen with the given constant
+    /// operands. Returns nullptr if a single successor could not be chosen.
+    Block *getSuccessorForOperands(ArrayRef<Attribute>);
   }];
 
   let hasCanonicalizer = 1;
   let assemblyFormat = [{
     $dest (`(` $destOperands^ `:` type($destOperands) `)`)? attr-dict
   }];
 }
 
let extraClassDeclaration = [{
 
     unsigned getNumFalseOperands() { return getFalseOperands().size(); }
 
     /// Erase the operand at 'index' from the false operand list.
     void eraseFalseOperand(unsigned index) {
       eraseSuccessorOperand(falseIndex, index);
     }
 
+    /// Returns the successor that would be chosen with the given constant
+    /// operands. Returns nullptr if a single successor could not be chosen.
+    Block *getSuccessorForOperands(ArrayRef<Attribute> operands);
+
   private:
     /// Get the index of the first true destination operand.
     unsigned getTrueDestOperandIndex() { return 1; }
 
     /// Get the index of the first false destination operand.
     unsigned getFalseDestOperandIndex() {
       return getTrueDestOperandIndex() + getNumTrueOperands();
     }

mlir/include/mlir/Interfaces/ControlFlowInterfaces.td

InterfaceMethod<[{
         for (unsigned i = 0, e = opaqueOp->getNumSuccessors(); i != e; ++i) {
           if (Optional<BlockArgument> arg = detail::getBranchSuccessorArgument(
                 op.getSuccessorOperands(i), operandIndex,
                 opaqueOp->getSuccessor(i)))
             return arg;
         }
         return llvm::None;
       }]
+    >,
+    InterfaceMethod<[{
+        Returns the successor that would be chosen with the given constant
+        operands. Returns nullptr if a single successor could not be chosen.
+      }],
+      "Block *", "getSuccessorForOperands",
+      (ins "ArrayRef<Attribute>":$operands), [{}],
+      /*defaultImplementation=*/[{ return nullptr; }]
     >
   ];
 
   let verify = [{
     auto concreteOp = cast<ConcreteOpType>($_op);
     for (unsigned i = 0, e = $_op->getNumSuccessors(); i != e; ++i) {
       Optional<OperandRange> operands = concreteOp.getSuccessorOperands(i);
       if (failed(detail::verifyBranchSuccessorOperands($_op, i, operands)))
         return failure();
     }
     return success();
   }];
 }
 
 #endif // MLIR_INTERFACES_CONTROLFLOWINTERFACES

mlir/include/mlir/Transforms/FoldUtils.h

create(OpBuilder &builder, Location location, Args &&... args) {
     // Folding cannot remove a zero-result operation, so for convenience we
     // continue to return it.
     return op;
   }
 
   /// Clear out any constants cached inside of the folder.
   void clear();
 
+  /// Get or create a constant using the given builder. On success this returns
+  /// the constant operation, nullptr otherwise.
+  Value getOrCreateConstant(OpBuilder &builder, Dialect *dialect,
+                            Attribute value, Type type, Location loc);
+
 private:
   /// This map keeps track of uniqued constants by dialect, attribute, and type.
   /// A constant operation materializes an attribute with a type. Dialects may
   /// generate different constants with the same input attribute and type, so we
   /// also need to track per-dialect.
   using ConstantMap =
       DenseMap<std::tuple<Dialect *, Attribute, Type>, Operation *>;
 

mlir/include/mlir/Transforms/Passes.h

 /// Creates a pass which prints the list of ops and the number of occurrences in
 /// the module.
 std::unique_ptr<OperationPass<ModuleOp>> createPrintOpStatsPass();
 
 /// Creates a pass which inlines calls and callable operations as defined by
 /// the CallGraph.
 std::unique_ptr<Pass> createInlinerPass();
 
+/// Creates a pass which performs sparse conditional constant propagation over
+/// nested operations.
+std::unique_ptr<Pass> createSCCPPass();
+
 /// Creates a pass which delete symbol operations that are unreachable. This
 /// pass may *only* be scheduled on an operation that defines a SymbolTable.
 std::unique_ptr<Pass> createSymbolDCEPass();
 } // end namespace mlir
 
 #endif // MLIR_TRANSFORMS_PASSES_H

mlir/include/mlir/Transforms/Passes.td

def PrintOpStats : Pass<"print-op-stats", "ModuleOp"> {
   let constructor = "mlir::createPrintOpStatsPass()";
 }
 
 def PrintOp : Pass<"print-op-graph", "ModuleOp"> {
   let summary = "Print op graph per-Region";
   let constructor = "mlir::createPrintOpGraphPass()";
 }
 
+def SCCP : Pass<"sccp"> {
+  let summary = "Sparse Conditional Constant Propagation";
+  let description = [{
+    This pass implements a general algorithm for sparse conditional constant
+    propagation. This algorithm detects values that are known to be constant and
+    optimistically propagates this throughout the IR. Any values proven to be
+    constant are replaced, and removed if possible.
+
+    This implementation is based on the algorithm described by Wegman and Zadeck
+    in [“Constant Propagation with Conditional Branches”](https://dl.acm.org/doi/10.1145/103135.103136) (1991).
+  }];
+  let constructor = "mlir::createSCCPPass()";
+}
+
 def StripDebugInfo : Pass<"strip-debuginfo"> {
   let summary = "Strip debug info from all operations";
   let description = [{
     This pass strips the IR of any location information, by replacing all
     operation locations with [`unknown`](Diagnostics.md#unknown-location).
   }];
   let constructor = "mlir::createStripDebugInfoPass()";
 }

mlir/lib/Dialect/StandardOps/IR/Ops.cpp

 
 Optional<OperandRange> BranchOp::getSuccessorOperands(unsigned index) {
   assert(index == 0 && "invalid successor index");
   return getOperands();
 }
 
 bool BranchOp::canEraseSuccessorOperand() { return true; }
 
+Block *BranchOp::getSuccessorForOperands(ArrayRef<Attribute>) { return dest(); }
+
 //===----------------------------------------------------------------------===//
 // CallOp
 //===----------------------------------------------------------------------===//
 
 static LogicalResult verify(CallOp op) {
   // Check that the callee attribute was specified.
   auto fnAttr = op.getAttrOfType<FlatSymbolRefAttr>("callee");
   if (!fnAttr)

 
 Optional<OperandRange> CondBranchOp::getSuccessorOperands(unsigned index) {
   assert(index < getNumSuccessors() && "invalid successor index");
   return index == trueIndex ? getTrueOperands() : getFalseOperands();
 }
 
 bool CondBranchOp::canEraseSuccessorOperand() { return true; }
 
+Block *CondBranchOp::getSuccessorForOperands(ArrayRef<Attribute> operands) {
+  if (BoolAttr condAttr = operands.front().dyn_cast_or_null<BoolAttr>())
+    return condAttr.getValue() ? trueDest() : falseDest();
+  if (IntegerAttr condAttr = operands.front().dyn_cast_or_null<IntegerAttr>())
+    return condAttr.getValue().isOneValue() ? trueDest() : falseDest();
+  return nullptr;
+}
+
 //===----------------------------------------------------------------------===//
 // Constant*Op
 //===----------------------------------------------------------------------===//
 
 static void print(OpAsmPrinter &p, ConstantOp &op) {
   p << "constant ";
   p.printOptionalAttrDict(op.getAttrs(), /*elidedAttrs=*/{"value"});
 

mlir/lib/Transforms/CMakeLists.txt

 add_subdirectory(Utils)
 
 add_mlir_library(MLIRTransforms
   Canonicalizer.cpp
   CSE.cpp
   DialectConversion.cpp
   Inliner.cpp
   LocationSnapshot.cpp
   LoopCoalescing.cpp
   LoopFusion.cpp
   LoopInvariantCodeMotion.cpp
   MemRefDataFlowOpt.cpp
   OpStats.cpp
   ParallelLoopCollapsing.cpp
   PipelineDataTransfer.cpp
+  SCCP.cpp
   StripDebugInfo.cpp
   SymbolDCE.cpp
   ViewOpGraph.cpp
   ViewRegionGraph.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${MLIR_MAIN_INCLUDE_DIR}/mlir/Transforms
 

mlir/lib/Transforms/SCCP.cpp

+//===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This transformation pass performs a sparse conditional constant propagation
+// in MLIR. It identifies values known to be constant, propagates that
+// information throughout the IR, and replaces them. This is done with an
+// optimisitic dataflow analysis that assumes that all values are constant until
+// proven otherwise.
+//
+//===----------------------------------------------------------------------===//
+
+#include "PassDetail.h"
+#include "mlir/IR/Builders.h"
+#include "mlir/IR/Dialect.h"
+#include "mlir/Interfaces/ControlFlowInterfaces.h"
+#include "mlir/Interfaces/SideEffects.h"
+#include "mlir/Pass/Pass.h"
+#include "mlir/Transforms/FoldUtils.h"
+#include "mlir/Transforms/Passes.h"
+
+using namespace mlir;
+
+namespace {
+/// This class represents a single lattice value. A lattive value corresponds to
+/// the various different states that a value in the SCCP dataflow anaylsis can
+/// take. See 'Kind' below for more details on the different states a value can
+/// take.
+class LatticeValue {
+  enum Kind {
+    /// A value with a yet to be determined value. This state may be changed to
+    /// anything.
+    Unknown,
+
+    /// A value that is known to be a constant. This state may be changed to
+    /// overdefined.
+    Constant,
+
+    /// A value that cannot statically be determined to be a constant. This
+    /// state cannot be changed.
+    Overdefined
+  };
+
+public:
+  /// Initialize a lattice value with "Unknown".
+  LatticeValue()
+      : constantAndTag(nullptr, Kind::Unknown), constantDialect(nullptr) {}
+  /// Initialize a lattice value with a constant.
+  LatticeValue(Attribute attr, Dialect *dialect)
+      : constantAndTag(attr, Kind::Constant), constantDialect(dialect) {}
+
+  /// Returns true if this lattice value is unknown.
+  bool isUnknown() const { return constantAndTag.getInt() == Kind::Unknown; }
+
+  /// Mark the lattice value as overdefined.
+  void markOverdefined() {
+    constantAndTag.setPointerAndInt(nullptr, Kind::Overdefined);
+    constantDialect = nullptr;
+  }
+
+  /// Returns true if the lattice is overdefined.
+  bool isOverdefined() const {
+    return constantAndTag.getInt() == Kind::Overdefined;
+  }
+
+  /// Mark the lattice value as constant.
+  void markConstant(Attribute value, Dialect *dialect) {
+    constantAndTag.setPointerAndInt(value, Kind::Constant);
+    constantDialect = dialect;
+  }
+
+  /// If this lattice is constant, return the constant. Returns nullptr
+  /// otherwise.
+  Attribute getConstant() const { return constantAndTag.getPointer(); }
+
+  /// If this lattice is constant, return the dialect to use when materializing
+  /// the constant.
+  Dialect *getConstantDialect() const {
+    assert(getConstant() && "expected valid constant");
+    return constantDialect;
+  }
+
+  /// Merge in the value of the 'rhs' lattice into this one. Returns true if the
+  /// lattice value changed.
+  bool meet(const LatticeValue &rhs) {
+    // If we are already overdefined, or rhs is unknown, there is nothing to do.
+    if (isOverdefined() || rhs.isUnknown())
+      return false;
+    // If we are unknown, just take the value of rhs.
+    if (isUnknown()) {
+      constantAndTag = rhs.constantAndTag;
+      constantDialect = rhs.constantDialect;
+      return true;
+    }
+
+    // Otherwise, if this value doesn't match rhs go straight to overdefined.
+    if (constantAndTag != rhs.constantAndTag) {
+      markOverdefined();
+      return true;
+    }
+    return false;
+  }
+
+private:
+  /// The attribute value if this is a constant and the tag for the element
+  /// kind.
+  llvm::PointerIntPair<Attribute, 2, Kind> constantAndTag;
+
+  /// The dialect the constant originated from. This is only valid if the
+  /// lattice is a constant. This is not used as part of the key, and is only
+  /// needed to materialize the held constant if necessary.
+  Dialect *constantDialect;
+};
+
+/// This class represents the solver for the SCCP analysis. This class acts as
+/// the propagation engine for computing which values form constants.
+class SCCPSolver {
+public:
+  /// Initialize the solver with a given set of regions.
+  SCCPSolver(MutableArrayRef<Region> regions);
+
+  /// Run the solver until it converges.
+  void solve();
+
+  /// Rewrite the given regions using the computing analysis. This replaces the
+  /// uses of all values that have been computed to be constant, and erases as
+  /// many newly dead operations.
+  void rewrite(MLIRContext *context, MutableArrayRef<Region> regions);
+
+private:
+  /// Replace the given value with a constant if the corresponding lattice
+  /// represents a constant. Returns success if the value was replaced, failure
+  /// otherwise.
+  LogicalResult replaceWithConstant(OpBuilder &builder, OperationFolder &folder,
+                                    Value value);
+
+  /// Visit the given operation and compute any necessary lattice state.
+  void visitOperation(Operation *op);
+
+  /// Visit the given operation, which defines regions, and compute any
+  /// necessary lattice state. This also resolves the lattice state of both the
+  /// operation results and any nested regions.
+  void visitRegionOperation(Operation *op);
+
+  /// Visit the given terminator operation and compute any necessary lattice
+  /// state.
+  void visitTerminatorOperation(Operation *op,
+                                ArrayRef<Attribute> constantOperands);
+
+  /// Visit the given block and compute any necessary lattice state.
+  void visitBlock(Block *block);
+
+  /// Visit argument #'i' of the given block and compute any necessary lattice
+  /// state.
+  void visitBlockArgument(Block *block, int i);
+
+  /// Mark the given block as executable. Returns false if the block was already
+  /// marked executable.
+  bool markBlockExecutable(Block *block);
+
+  /// Returns true if the given block is executable.
+  bool isBlockExecutable(Block *block) const;
+
+  /// Mark the edge between 'from' and 'to' as executable.
+  void markEdgeExecutable(Block *from, Block *to);
+
+  /// Return true if the edge between 'from' and 'to' is executable.
+  bool isEdgeExecutable(Block *from, Block *to) const;
+
+  /// Mark the given value as overdefined. This means that we cannot refine a
+  /// specific constant for this value.
+  void markOverdefined(Value value);
+
+  /// Mark all of the given values as overdefined.
+  template <typename ValuesT>
+  void markAllOverdefined(ValuesT values) {
+    for (auto value : values)
+      markOverdefined(value);
+  }
+  template <typename ValuesT>
+  void markAllOverdefined(Operation *op, ValuesT values) {
+    markAllOverdefined(values);
+    opWorklist.push_back(op);
+  }
+
+  /// Returns true if the given value was marked as overdefined.
+  bool isOverdefined(Value value) const;
+
+  /// Merge in the given lattice 'from' into the lattice 'to'. 'owner'
+  /// corresponds to the parent operation of 'to'.
+  void meet(Operation *owner, LatticeValue &to, const LatticeValue &from);
+
+  /// The lattice for each SSA value.
+  DenseMap<Value, LatticeValue> latticeValues;
+
+  /// The set of blocks that are known to execute, or are intrinsically live.
+  SmallPtrSet<Block *, 16> executableBlocks;
+
+  /// The set of control flow edges that are known to execute.
+  DenseSet<std::pair<Block *, Block *>> executableEdges;
+
+  /// A worklist containing blocks that need to be processed.
+  SmallVector<Block *, 64> blockWorklist;
+
+  /// A worklist of operations that need to be processed.
+  SmallVector<Operation *, 64> opWorklist;
+};
+} // end anonymous namespace
+
+SCCPSolver::SCCPSolver(MutableArrayRef<Region> regions) {
+  for (Region &region : regions) {
+    if (region.empty())
+      continue;
+    Block *entryBlock = &region.front();
+
+    // Mark the entry block as executable.
+    markBlockExecutable(entryBlock);
+
+    // The values passed to these regions are invisible, so mark any arguments
+    // as overdefined.
+    markAllOverdefined(entryBlock->getArguments());
+  }
+}
+
+void SCCPSolver::solve() {
+  while (!blockWorklist.empty() || !opWorklist.empty()) {
+    // Process any operations in the op worklist.
+    while (!opWorklist.empty()) {
+      Operation *op = opWorklist.pop_back_val();
+
+      // Visit all of the live users to propagate changes to this operation.
+      for (Operation *user : op->getUsers()) {
+        if (isBlockExecutable(user->getBlock()))
+          visitOperation(user);
+      }
+    }
+
+    // Process any blocks in the block worklist.
+    while (!blockWorklist.empty())
+      visitBlock(blockWorklist.pop_back_val());
+  }
+}
+
+void SCCPSolver::rewrite(MLIRContext *context,
+                         MutableArrayRef<Region> initialRegions) {
+  SmallVector<Block *, 8> worklist;
+  auto addToWorklist = [&](MutableArrayRef<Region> regions) {
+    for (Region &region : regions)
+      for (Block &block : region)
+        if (isBlockExecutable(&block))
+          worklist.push_back(&block);
+  };
+
+  // An operation folder used to create and unique constants.
+  OperationFolder folder(context);
+  OpBuilder builder(context);
+
+  addToWorklist(initialRegions);
+  while (!worklist.empty()) {
+    Block *block = worklist.pop_back_val();
+
+    // Replace any block arguments with constants.
+    builder.setInsertionPointToStart(block);
+    for (BlockArgument arg : block->getArguments())
+      replaceWithConstant(builder, folder, arg);
+
+    for (Operation &op : llvm::make_early_inc_range(*block)) {
+      builder.setInsertionPoint(&op);
+
+      // Replace any result with constants.
+      bool replacedAll = op.getNumResults() != 0;
+      for (Value res : op.getResults())
+        replacedAll &= succeeded(replaceWithConstant(builder, folder, res));
+
+      // If all of the results of the operation were replaced, try to erase
+      // the operation completely.
+      if (replacedAll && wouldOpBeTriviallyDead(&op)) {
+        assert(op.use_empty() && "expected all uses to be replaced");
+        op.erase();
+        continue;
+      }
+
+      // Add any the regions of this operation to the worklist.
+      addToWorklist(op.getRegions());
+    }
+  }
+}
+
+LogicalResult SCCPSolver::replaceWithConstant(OpBuilder &builder,
+                                              OperationFolder &folder,
+                                              Value value) {
+  auto &latticeValue = latticeValues[value];
+  Attribute attrResult = latticeValue.getConstant();
+  if (!attrResult)
+    return failure();
+
+  // Attempt to materialize a constant for the given value.
+  Dialect *dialect = latticeValue.getConstantDialect();
+  Value constant = folder.getOrCreateConstant(builder, dialect, attrResult,
+                                              value.getType(), value.getLoc());
+  if (!constant)
+    return failure();
+
+  value.replaceAllUsesWith(constant);
+  return success();
+}
+
+void SCCPSolver::visitOperation(Operation *op) {
+  // Collect all of the constant operands feeding into this operation. If any
+  // are not ready to be resolved, bail out and wait for them to resolve.
+  SmallVector<Attribute, 8> operandConstants;
+  operandConstants.reserve(op->getNumOperands());
+  for (Value operand : op->getOperands()) {
+    // Make sure all of the operands are resolved first.
+    auto &operandLattice = latticeValues[operand];
+    if (operandLattice.isUnknown())
+      return;
+    operandConstants.push_back(operandLattice.getConstant());
+  }
+
+  // If this is a terminator operation, process any control flow lattice state.
+  if (op->isKnownTerminator())
+    visitTerminatorOperation(op, operandConstants);
+
+  // Process region holding operations. The region visitor processes result
+  // values, so we can exit afterwards.
+  if (op->getNumRegions())
+    return visitRegionOperation(op);
+
+  // If this op produces no results, it can't produce any constants.
+  if (op->getNumResults() == 0)
+    return;
+
+  // If all of the results of this operation are already overdefined, bail out
+  // early.
+  auto isOverdefinedFn = [&](Value value) { return isOverdefined(value); };
+  if (llvm::all_of(op->getResults(), isOverdefinedFn))
+    return;
+
+  // Save the original operands and attributes just in case the operation folds
+  // in-place. The constant passed in may not correspond to the real runtime
+  // value, so in-place updates are not allowed.
+  SmallVector<Value, 8> originalOperands(op->getOperands());
+  NamedAttributeList originalAttrs = op->getAttrList();
+
+  // Simulate the result of folding this operation to a constant. If folding
+  // fails or was an in-place fold, mark the results as overdefined.
+  SmallVector<OpFoldResult, 8> foldResults;
+  foldResults.reserve(op->getNumResults());
+  if (failed(op->fold(operandConstants, foldResults)))
+    return markAllOverdefined(op, op->getResults());
+
+  // If the folding was in-place, mark the results as overdefined and reset the
+  // operation. We don't allow in-place folds as the desire here is for
+  // simulated execution, and not general folding.
+  if (foldResults.empty()) {
+    op->setOperands(originalOperands);
+    op->setAttrs(originalAttrs);
+    return markAllOverdefined(op, op->getResults());
+  }
+
+  // Merge the fold results into the lattice for this operation.
+  assert(foldResults.size() == op->getNumResults() && "invalid result size");
+  Dialect *opDialect = op->getDialect();
+  for (unsigned i = 0, e = foldResults.size(); i != e; ++i) {
+    LatticeValue &resultLattice = latticeValues[op->getResult(i)];
+
+    // Merge in the result of the fold, either a constant or a value.
+    OpFoldResult foldResult = foldResults[i];
+    if (Attribute foldAttr = foldResult.dyn_cast<Attribute>())
+      meet(op, resultLattice, LatticeValue(foldAttr, opDialect));
+    else
+      meet(op, resultLattice, latticeValues[foldResult.get<Value>()]);
+  }
+}
+
+void SCCPSolver::visitRegionOperation(Operation *op) {
+  for (Region &region : op->getRegions()) {
+    if (region.empty())
+      continue;
+    Block *entryBlock = &region.front();
+    markBlockExecutable(entryBlock);
+    markAllOverdefined(entryBlock->getArguments());
+  }
+
+  // Don't try to simulate the results of a region operation as we can't
+  // guarantee that folding will be out-of-place. We don't allow in-place folds
+  // as the desire here is for simulated execution, and not general folding.
+  return markAllOverdefined(op, op->getResults());
+}
+
+void SCCPSolver::visitTerminatorOperation(
+    Operation *op, ArrayRef<Attribute> constantOperands) {
+  if (op->getNumSuccessors() == 0)
+    return;
+
+  // Try to resolve to a specific successor with the constant operands.
+  if (auto branch = dyn_cast<BranchOpInterface>(op)) {
+    if (Block *singleSucc = branch.getSuccessorForOperands(constantOperands)) {
+      markEdgeExecutable(op->getBlock(), singleSucc);
+      return;
+    }
+  }
+
+  // Otherwise, conservatively treat all edges as executable.
+  Block *block = op->getBlock();
+  for (Block *succ : op->getSuccessors())
+    markEdgeExecutable(block, succ);
+}
+
+void SCCPSolver::visitBlock(Block *block) {
+  // If the block is not the entry block we need to compute the lattice state
+  // for the block arguments. Entry block argument lattices are computed
+  // elsewhere, such as when visiting the parent operation.
+  if (!block->isEntryBlock()) {
+    for (int i : llvm::seq<int>(0, block->getNumArguments()))
+      visitBlockArgument(block, i);
+  }
+
+  // Visit all of the operations within the block.
+  for (Operation &op : *block)
+    visitOperation(&op);
+}
+
+void SCCPSolver::visitBlockArgument(Block *block, int i) {
+  BlockArgument arg = block->getArgument(i);
+  LatticeValue &argLattice = latticeValues[arg];
+  if (argLattice.isOverdefined())
+    return;
+
+  bool updatedLattice = false;
+  for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) {
+    Block *pred = *it;
+
+    // We only care about this predecessor if it is going to execute.
+    if (!isEdgeExecutable(pred, block))
+      continue;
+
+    // Try to get the operand forwarded by the predecessor. If we can't reason
+    // about the terminator of the predecessor, mark overdefined.
+    Optional<OperandRange> branchOperands;
+    if (auto branch = dyn_cast<BranchOpInterface>(pred->getTerminator()))
+      branchOperands = branch.getSuccessorOperands(it.getSuccessorIndex());
+    if (!branchOperands) {
+      updatedLattice = true;
+      argLattice.markOverdefined();
+      break;
+    }
+
+    // If the operand hasn't been resolved, it is unknown which can merge with
+    // anything.
+    auto operandLattice = latticeValues.find((*branchOperands)[i]);
+    if (operandLattice == latticeValues.end())
+      continue;
+
+    // Otherwise, meet the two lattice values.
+    updatedLattice |= argLattice.meet(operandLattice->second);
+    if (argLattice.isOverdefined())
+      break;
+  }
+
+  // If the lattice was updated, visit any executable users of the argument.
+  if (updatedLattice) {
+    for (Operation *user : arg.getUsers())
+      if (isBlockExecutable(user->getBlock()))
+        visitOperation(user);
+  }
+}
+
+bool SCCPSolver::markBlockExecutable(Block *block) {
+  bool marked = executableBlocks.insert(block).second;
+  if (marked)
+    blockWorklist.push_back(block);
+  return marked;
+}
+
+bool SCCPSolver::isBlockExecutable(Block *block) const {
+  return executableBlocks.count(block);
+}
+
+void SCCPSolver::markEdgeExecutable(Block *from, Block *to) {
+  if (!executableEdges.insert(std::make_pair(from, to)).second)
+    return;
+  // Mark the destination as executable, and reprocess its arguments if it was
+  // already executable.
+  if (!markBlockExecutable(to)) {
+    for (int i : llvm::seq<int>(0, to->getNumArguments()))
+      visitBlockArgument(to, i);
+  }
+}
+
+bool SCCPSolver::isEdgeExecutable(Block *from, Block *to) const {
+  return executableEdges.count(std::make_pair(from, to));
+}
+
+void SCCPSolver::markOverdefined(Value value) {
+  latticeValues[value].markOverdefined();
+}
+
+bool SCCPSolver::isOverdefined(Value value) const {
+  auto it = latticeValues.find(value);
+  return it != latticeValues.end() && it->second.isOverdefined();
+}
+
+void SCCPSolver::meet(Operation *owner, LatticeValue &to,
+                      const LatticeValue &from) {
+  if (to.meet(from))
+    opWorklist.push_back(owner);
+}
+
+//===----------------------------------------------------------------------===//
+// SCCP Pass
+//===----------------------------------------------------------------------===//
+
+namespace {
+struct SCCP : public SCCPBase<SCCP> {
+  void runOnOperation() override;
+};
+} // end anonymous namespace
+
+void SCCP::runOnOperation() {
+  Operation *op = getOperation();
+
+  // Solve for SCCP constraints within nested regions.
+  SCCPSolver solver(op->getRegions());
+  solver.solve();
+
+  // Cleanup any operations using the solver analysis.
+  solver.rewrite(&getContext(), op->getRegions());
+}
+
+std::unique_ptr<Pass> mlir::createSCCPPass() {
+  return std::make_unique<SCCP>();
+}

mlir/lib/Transforms/Utils/FoldUtils.cpp

 }
 
 /// Clear out any constants cached inside of the folder.
 void OperationFolder::clear() {
   foldScopes.clear();
   referencedDialects.clear();
 }
 
+/// Get or create a constant using the given builder. On success this returns
+/// the constant operation, nullptr otherwise.
+Value OperationFolder::getOrCreateConstant(OpBuilder &builder, Dialect *dialect,
+                                           Attribute value, Type type,
+                                           Location loc) {
+  OpBuilder::InsertionGuard foldGuard(builder);
+
+  // Use the builder insertion block to find an insertion point for the
+  // constant.
+  auto *insertRegion =
+      getInsertionRegion(interfaces, builder.getInsertionBlock());
+  auto &entry = insertRegion->front();
+  builder.setInsertionPoint(&entry, entry.begin());
+
+  // Get the constant map for the insertion region of this operation.
+  auto &uniquedConstants = foldScopes[insertRegion];
+  Operation *constOp = tryGetOrCreateConstant(uniquedConstants, dialect,
+                                              builder, value, type, loc);
+  return constOp ? constOp->getResult(0) : Value();
+}
+
 /// Tries to perform folding on the given `op`. If successful, populates
 /// `results` with the results of the folding.
 LogicalResult OperationFolder::tryToFold(
     OpBuilder &builder, Operation *op, SmallVectorImpl<Value> &results,
     function_ref<void(Operation *)> processGeneratedConstants) {
   SmallVector<Attribute, 8> operandConstants;
   SmallVector<OpFoldResult, 8> foldResults;
 

mlir/test/Transforms/sccp.mlir

+// RUN: mlir-opt -allow-unregistered-dialect %s -pass-pipeline="func(sccp)" -split-input-file | FileCheck %s
+
+/// Check simple forward constant propagation without any control flow.
+
+// CHECK-LABEL: func @no_control_flow
+func @no_control_flow(%arg0: i32) -> i32 {
+  // CHECK: %[[CST:.*]] = constant 1 : i32
+  // CHECK: return %[[CST]] : i32
+
+  %cond = constant 1 : i1
+  %cst_1 = constant 1 : i32
+  %select = select %cond, %cst_1, %arg0 : i32
+  return %select : i32
+}
+
+/// Check that a constant is properly propagated when only one edge of a branch
+/// is taken.
+
+// CHECK-LABEL: func @simple_control_flow
+func @simple_control_flow(%arg0 : i32) -> i32 {
+  // CHECK: %[[CST:.*]] = constant 1 : i32
+
+  %cond = constant true
+  %1 = constant 1 : i32
+  cond_br %cond, ^bb1, ^bb2(%arg0 : i32)
+
+^bb1:
+  br ^bb2(%1 : i32)
+
+^bb2(%arg : i32):
+  // CHECK: ^bb2(%{{.*}}: i32):
+  // CHECK: return %[[CST]] : i32
+
+  return %arg : i32
+}
+
+/// Check that the arguments go to overdefined if the branch cannot detect when
+/// a specific successor is taken.
+
+// CHECK-LABEL: func @simple_control_flow_overdefined
+func @simple_control_flow_overdefined(%arg0 : i32, %arg1 : i1) -> i32 {
+  %1 = constant 1 : i32
+  cond_br %arg1, ^bb1, ^bb2(%arg0 : i32)
+
+^bb1:
+  br ^bb2(%1 : i32)
+
+^bb2(%arg : i32):
+  // CHECK: ^bb2(%[[ARG:.*]]: i32):
+  // CHECK: return %[[ARG]] : i32
+
+  return %arg : i32
+}
+
+/// Check that the arguments go to overdefined if there are conflicting
+/// constants.
+
+// CHECK-LABEL: func @simple_control_flow_constant_overdefined
+func @simple_control_flow_constant_overdefined(%arg0 : i32, %arg1 : i1) -> i32 {
+  %1 = constant 1 : i32
+  %2 = constant 2 : i32
+  cond_br %arg1, ^bb1, ^bb2(%arg0 : i32)
+
+^bb1:
+  br ^bb2(%2 : i32)
+
+^bb2(%arg : i32):
+  // CHECK: ^bb2(%[[ARG:.*]]: i32):
+  // CHECK: return %[[ARG]] : i32
+
+  return %arg : i32
+}
+
+/// Check that the arguments go to overdefined if the branch is unknown.
+
+// CHECK-LABEL: func @unknown_terminator
+func @unknown_terminator(%arg0 : i32, %arg1 : i1) -> i32 {
+  %1 = constant 1 : i32
+  "foo.cond_br"() [^bb1, ^bb2] : () -> ()
+
+^bb1:
+  br ^bb2(%1 : i32)
+
+^bb2(%arg : i32):
+  // CHECK: ^bb2(%[[ARG:.*]]: i32):
+  // CHECK: return %[[ARG]] : i32
+
+  return %arg : i32
+}
+
+/// Check that arguments are properly merged across loop-like control flow.
+
+func @ext_cond_fn() -> i1
+
+// CHECK-LABEL: func @simple_loop
+func @simple_loop(%arg0 : i32, %cond1 : i1) -> i32 {
+  // CHECK: %[[CST:.*]] = constant 1 : i32
+
+  %cst_1 = constant 1 : i32
+  cond_br %cond1, ^bb1(%cst_1 : i32), ^bb2(%cst_1 : i32)
+
+^bb1(%iv: i32):
+  // CHECK: ^bb1(%{{.*}}: i32):
+  // CHECK-NEXT: %[[COND:.*]] = call @ext_cond_fn()
+  // CHECK-NEXT: cond_br %[[COND]], ^bb1(%[[CST]] : i32), ^bb2(%[[CST]] : i32)
+
+  %cst_0 = constant 0 : i32
+  %res = addi %iv, %cst_0 : i32
+  %cond2 = call @ext_cond_fn() : () -> i1
+  cond_br %cond2, ^bb1(%res : i32), ^bb2(%res : i32)
+
+^bb2(%arg : i32):
+  // CHECK: ^bb2(%{{.*}}: i32):
+  // CHECK: return %[[CST]] : i32
+
+  return %arg : i32
+}
+
+/// Test that we can properly propagate within inner control, and in situations
+/// where the executable edges within the CFG are sensitive to the current state
+/// of the analysis.
+
+// CHECK-LABEL: func @simple_loop_inner_control_flow
+func @simple_loop_inner_control_flow(%arg0 : i32) -> i32 {
+  // CHECK-DAG: %[[CST:.*]] = constant 1 : i32
+  // CHECK-DAG: %[[TRUE:.*]] = constant 1 : i1
+
+  %cst_1 = constant 1 : i32
+  br ^bb1(%cst_1 : i32)
+
+^bb1(%iv: i32):
+  %cond2 = call @ext_cond_fn() : () -> i1
+  cond_br %cond2, ^bb5(%iv : i32), ^bb2
+
+^bb2:
+  // CHECK: ^bb2:
+  // CHECK: cond_br %[[TRUE]], ^bb3, ^bb4
+
+  %cst_20 = constant 20 : i32
+  %cond = cmpi "ult", %iv, %cst_20 : i32
+  cond_br %cond, ^bb3, ^bb4
+
+^bb3:
+  // CHECK: ^bb3:
+  // CHECK: br ^bb1(%[[CST]] : i32)
+
+  %cst_1_2 = constant 1 : i32
+  br ^bb1(%cst_1_2 : i32)
+
+^bb4:
+  %iv_inc = addi %iv, %cst_1 : i32
+  br ^bb1(%iv_inc : i32)
+
+^bb5(%result: i32):
+  // CHECK: ^bb5(%{{.*}}: i32):
+  // CHECK: return %[[CST]] : i32
+
+  return %result : i32
+}
+
+/// Check that arguments go to overdefined when loop backedges produce a
+/// conflicting value.
+
+func @ext_cond_and_value_fn() -> (i1, i32)
+
+// CHECK-LABEL: func @simple_loop_overdefined
+func @simple_loop_overdefined(%arg0 : i32, %cond1 : i1) -> i32 {
+  %cst_1 = constant 1 : i32
+  cond_br %cond1, ^bb1(%cst_1 : i32), ^bb2(%cst_1 : i32)
+
+^bb1(%iv: i32):
+  %cond2, %res = call @ext_cond_and_value_fn() : () -> (i1, i32)
+  cond_br %cond2, ^bb1(%res : i32), ^bb2(%res : i32)
+
+^bb2(%arg : i32):
+  // CHECK: ^bb2(%[[ARG:.*]]: i32):
+  // CHECK: return %[[ARG]] : i32
+
+  return %arg : i32
+}