Invariants (and Assume Aligned) - LLVM

[hfinkel]

Summary

LLVM support for IR invariants (and alignment assumptions as a first use case). The inliner uses ephemeral value analysis to avoid counting instructions contributing to the invariants against the inlining score.

[gribozavr]

docs/LangRef.html

9077

as the -> at the

9077

Is the return value is always equal to the first argument, regardless the offset?

9089–9092

Minus? I think it should be 'plus'. We aren't passing the negation of the offset, are we?

lib/Analysis/BasicAliasAnalysis.cpp

220 ↗

(On Diff #384)

This function is duplicated in this patch.

[hfinkel]

Changed to using @llvm.invariant; added analysis for ephemeral values.

[gribozavr]

docs/LangRef.html

9083–9085

What about adding explicitly: "If the condition does not hold during execution, the behavior is undefined"?

include/llvm/Analysis/EphemeralValues.h

9–11

Three slashes and '\file', please.

35

Three slashes please.

44

Does this need 'explicit'?

include/llvm/Analysis/InlineCost.h

110

Three slashes...

lib/Analysis/CaptureTracking.cpp

139–142 ↗

(On Diff #384)

Did you really intend to just move this piece of code a few lines down?

lib/Analysis/EphemeralValues.cpp

10–12

Three slashes and '\file', please.

lib/Analysis/InlineCost.cpp

47

Three slashes, please.

lib/CodeGen/IntrinsicLowering.cpp

458

Please correct the comment (something like "strip out these intrinsics")

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

5023

Please correct the comment.

lib/Transforms/Scalar/AlignmentInvProp.cpp

10–12

Three slashes and '\file'

243

Is the '+' required here?

[hfinkel]

Thanks!

Chandler was requested (on IRC) that I split this into 4 patches. I'll do that now, then I'll work on your comments.

-Hal

• Original Message -----

From: "Dmitri Gribenko" <[e-mail]>
To: [e-mail]
Cc: [e-mail], [e-mail], [e-mail]
Sent: Wednesday, December 5, 2012 4:06:31 PM
Subject: Re: [PATCH] Invariants (and Assume Aligned) - LLVM

Comment at: docs/LangRef.html:9083-9085
@@ +9082,5 @@
+
+<p>The intrinsic allows the optimizer to assume that the provided
condition is
+ always true. No code is generated for this intrinsic, and
instructions that
+ contribute only to the provided condition are not used for code
generation.</p>

+</div>

What about adding explicitly: "If the condition does not hold during
execution, the behavior is undefined"?

Comment at: include/llvm/Analysis/EphemeralValues.h:9-11
@@ +8,5 @@
+===----------------------------------------------------------------------===
+
+ Calculate ephemeral values - those used only (indirectly) by
invariants.
+//

+===----------------------------------------------------------------------===

Three slashes and '\file', please.

Comment at: include/llvm/Analysis/EphemeralValues.h:35
@@ +34,3 @@
+ // Returns true if the provided value is ephemeral.
+ bool isEphemeralValue(Value *V) const {

+ return EphValues.count(V);

Three slashes please.

Comment at: include/llvm/Analysis/InlineCost.h:110
@@ -108,1 +109,3 @@

const DataLayout *TD;

+ // EphemeralValues if available, or null.

+ const EphemeralValues *EV;

Three slashes...

Comment at: lib/Analysis/CaptureTracking.cpp:139-142
@@ -125,19 +138,6 @@

}

• case Instruction::Load:
• // Loading from a pointer does not cause it to be captured.
• break;
• case Instruction::VAArg:
• // "va-arg" from a pointer does not cause it to be captured.
• break;
• case Instruction::Store:
• if (V == I->getOperand(0))
• // Stored the pointer - conservatively assume it may be

captured.

• if (Tracker->captured(U))
• return;
• // Storing to the pointee does not cause the pointer to be

captured.

• break; case Instruction::BitCast: case Instruction::GetElementPtr: case Instruction::PHI: case Instruction::Select: // The original value is not captured via this if the new value isn't. ----------------

Did you really intend to just move this piece of code a few lines
down?

Comment at: lib/Analysis/EphemeralValues.cpp:10-12
@@ +9,5 @@
+===----------------------------------------------------------------------===
+
+ This file implements ephemeral value determination.
+//

+===----------------------------------------------------------------------===

Three slashes and '\file', please.

Comment at: include/llvm/Analysis/EphemeralValues.h:44
@@ +43,3 @@
+ static char ID;
+ explicit EphemeralValues();

+

Does this need 'explicit'?

Comment at: lib/Analysis/InlineCost.cpp:47
@@ -45,1 +46,3 @@

const DataLayout *const TD;

+ // EphemeralValues if available, or null.

+ const EphemeralValues *const EV;

Three slashes, please.

Comment at: lib/CodeGen/IntrinsicLowering.cpp:458
@@ -456,3 +457,3 @@

case Intrinsic::var_annotation:
  break;   // Strip out annotate intrinsic

---

Please correct the comment (something like "strip out these
intrinsics")

Comment at: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:5023
@@ -5021,3 +5022,3 @@

case Intrinsic::var_annotation:
  // Discard annotate attributes
  return 0;

---

Please correct the comment.

Comment at: lib/Transforms/Scalar/AlignmentInvProp.cpp:10-12
@@ +9,5 @@
+===----------------------------------------------------------------------===
+
+ This file implements alignment invariant propagation.
+//

+===----------------------------------------------------------------------===

Three slashes and '\file'

Comment at: lib/Transforms/Scalar/AlignmentInvProp.cpp:243
@@ +242,3 @@
+ unsigned(sizeof(unsigned) * CHAR_BIT - 1));
+ Alignment = std::min(1u << TrailingOnes,
+Value::MaximumAlignment);

+

Is the '+' required here?

http://llvm-reviews.chandlerc.com/D150

[hfinkel]

Thanks!

Chandler was requested (on IRC) that I split this into 4 patches. I'll do that now, then I'll work on your comments.

-Hal

• Original Message -----

From: "Dmitri Gribenko" <[e-mail]>
To: [e-mail]
Cc: [e-mail], [e-mail], [e-mail]
Sent: Wednesday, December 5, 2012 4:06:31 PM
Subject: Re: [PATCH] Invariants (and Assume Aligned) - LLVM

Comment at: docs/LangRef.html:9083-9085
@@ +9082,5 @@
+
+<p>The intrinsic allows the optimizer to assume that the provided
condition is
+ always true. No code is generated for this intrinsic, and
instructions that
+ contribute only to the provided condition are not used for code
generation.</p>

+</div>

What about adding explicitly: "If the condition does not hold during
execution, the behavior is undefined"?

Comment at: include/llvm/Analysis/EphemeralValues.h:9-11
@@ +8,5 @@
+===----------------------------------------------------------------------===
+
+ Calculate ephemeral values - those used only (indirectly) by
invariants.
+//

+===----------------------------------------------------------------------===

Three slashes and '\file', please.

Comment at: include/llvm/Analysis/EphemeralValues.h:35
@@ +34,3 @@
+ // Returns true if the provided value is ephemeral.
+ bool isEphemeralValue(Value *V) const {

+ return EphValues.count(V);

Three slashes please.

Comment at: include/llvm/Analysis/InlineCost.h:110
@@ -108,1 +109,3 @@

const DataLayout *TD;

+ // EphemeralValues if available, or null.

+ const EphemeralValues *EV;

Three slashes...

Comment at: lib/Analysis/CaptureTracking.cpp:139-142
@@ -125,19 +138,6 @@

}

• case Instruction::Load:
• // Loading from a pointer does not cause it to be captured.
• break;
• case Instruction::VAArg:
• // "va-arg" from a pointer does not cause it to be captured.
• break;
• case Instruction::Store:
• if (V == I->getOperand(0))
• // Stored the pointer - conservatively assume it may be

captured.

• if (Tracker->captured(U))
• return;
• // Storing to the pointee does not cause the pointer to be

captured.

• break; case Instruction::BitCast: case Instruction::GetElementPtr: case Instruction::PHI: case Instruction::Select: // The original value is not captured via this if the new value isn't. ----------------

Did you really intend to just move this piece of code a few lines
down?

Comment at: lib/Analysis/EphemeralValues.cpp:10-12
@@ +9,5 @@
+===----------------------------------------------------------------------===
+
+ This file implements ephemeral value determination.
+//

+===----------------------------------------------------------------------===

Three slashes and '\file', please.

Comment at: include/llvm/Analysis/EphemeralValues.h:44
@@ +43,3 @@
+ static char ID;
+ explicit EphemeralValues();

+

Does this need 'explicit'?

Comment at: lib/Analysis/InlineCost.cpp:47
@@ -45,1 +46,3 @@

const DataLayout *const TD;

+ // EphemeralValues if available, or null.

+ const EphemeralValues *const EV;

Three slashes, please.

Comment at: lib/CodeGen/IntrinsicLowering.cpp:458
@@ -456,3 +457,3 @@

case Intrinsic::var_annotation:
  break;   // Strip out annotate intrinsic

---

Please correct the comment (something like "strip out these
intrinsics")

Comment at: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:5023
@@ -5021,3 +5022,3 @@

case Intrinsic::var_annotation:
  // Discard annotate attributes
  return 0;

---

Please correct the comment.

Comment at: lib/Transforms/Scalar/AlignmentInvProp.cpp:10-12
@@ +9,5 @@
+===----------------------------------------------------------------------===
+
+ This file implements alignment invariant propagation.
+//

+===----------------------------------------------------------------------===

Three slashes and '\file'

Comment at: lib/Transforms/Scalar/AlignmentInvProp.cpp:243
@@ +242,3 @@
+ unsigned(sizeof(unsigned) * CHAR_BIT - 1));
+ Alignment = std::min(1u << TrailingOnes,
+Value::MaximumAlignment);

+

Is the '+' required here?

http://llvm-reviews.chandlerc.com/D150

[silvas]

FYI, the changes to LangRef need to be done against LangRef.rst now that LangRef.html is gone.

[Bigcheese]

include/llvm/Analysis/EphemeralValues.h

46–51

Three slashes and \ instead of @.

[hfinkel]

(this patchset has been split, and will be updated; abandoning...)

docs/LangRef.html

<ol>
             '<tt>llvm.trap</tt>' Intrinsic</a></li>
           <li><a href="#int_debugtrap">
             '<tt>llvm.debugtrap</tt>' Intrinsic</a></li>
           <li><a href="#int_stackprotector">
             '<tt>llvm.stackprotector</tt>' Intrinsic</a></li>
           <li><a href="#int_objectsize">
             '<tt>llvm.objectsize</tt>' Intrinsic</a></li>
           <li><a href="#int_expect">
+            '<tt>llvm.invariant</tt>' Intrinsic</a></li>
+          <li><a href="#int_invariant">
             '<tt>llvm.expect</tt>' Intrinsic</a></li>
           <li><a href="#int_donothing">
             '<tt>llvm.donothing</tt>' Intrinsic</a></li>
         </ol>
       </li>
     </ol>
   </li>
 </ol>
<p>The <tt>llvm.expect</tt> intrinsic takes two arguments. The first
    be a constant value, variables are not allowed.</p>
 
 <h5>Semantics:</h5>
 <p>This intrinsic is lowered to the <tt>val</tt>.</p>
 </div>
 
 <!-- _______________________________________________________________________ -->
 <h4>
+  <a name="int_invariant">'<tt>llvm.invariant</tt>' Intrinsic</a>
+</h4>
+
+<div>
+
+<h5>Syntax:</h5>
+<pre>
+  declare void @llvm.invariant(i1 %cond)
+</pre>
+
+<h5>Overview:</h5>
+<p>The '<tt>llvm.invariant</tt>' intrinsic allows the optimizer to assume
+   that the provided condition is true. This information can then be used
+   in simplifying other parts of the code.</p>
+
+<h5>Arguments:</h5>
+
+<p>The condition which the optimizer may assume is always true.</p>
+
+<h5>Semantics:</h5>
+
+<p>The intrinsic allows the optimizer to assume that the provided condition is
+   always true. No code is generated for this intrinsic, and instructions that
+   contribute only to the provided condition are not used for code generation.</p>
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
   <a name="int_donothing">'<tt>llvm.donothing</tt>' Intrinsic</a>
 </h4>
 
 <div>
 
 <h5>Syntax:</h5>
 <pre>
   declare void @llvm.donothing() nounwind readnone
 </pre>
 
 <h5>Overview:</h5>

include/llvm-c/Transforms/Scalar.h

  * @ingroup LLVMCTransforms
  *
  * @{
  */
 
 /** See llvm::createAggressiveDCEPass function. */
 void LLVMAddAggressiveDCEPass(LLVMPassManagerRef PM);
 
+/** See llvm::createAlignmentInvPropPass function. */
+void LLVMAddAlignmentInvPropPass(LLVMPassManagerRef PM);
+
 /** See llvm::createCFGSimplificationPass function. */
 void LLVMAddCFGSimplificationPass(LLVMPassManagerRef PM);
 
 /** See llvm::createDeadStoreEliminationPass function. */
 void LLVMAddDeadStoreEliminationPass(LLVMPassManagerRef PM);
 
 /** See llvm::createGVNPass function. */
 void LLVMAddGVNPass(LLVMPassManagerRef PM);

include/llvm/Analysis/EphemeralValues.h

+//===- EphemeralValues.h - Ephemeral value analysis -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Calculate ephemeral values - those used only (indirectly) by invariants.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_EPHEMERAL_VALUES_H
+#define LLVM_ANALYSIS_EPHEMERAL_VALUES_H
+
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+
+class Value;
+class raw_ostream;
+
+//===----------------------------------------------------------------------===//
+/// @brief Analysis that finds ephemeral values. 
+class EphemeralValues : public ModulePass {
+  DenseSet<Value *> EphValues;
+
+  EphemeralValues(const EphemeralValues &) LLVM_DELETED_FUNCTION;
+  const EphemeralValues &operator=(const EphemeralValues &) LLVM_DELETED_FUNCTION;
+
+public:
+  // Returns true if the provided value is ephemeral.
+  bool isEphemeralValue(Value *V) const {
+    return EphValues.count(V);
+  }
+  bool isEphemeralValue(const Value *V) const {
+    return isEphemeralValue(const_cast<Value *>(V));
+  }
+
+public:
+  static char ID;
+  explicit EphemeralValues();
+
+  /// @name ModulePass interface
+  //@{
+  virtual bool runOnModule(Module &M);
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+  virtual void print(raw_ostream &OS, const Module *M) const;
+  //@}
+};
+
+} // End llvm namespace
+#endif
+

include/llvm/Analysis/InlineCost.h

 #include <cassert>
 #include <climits>
 #include <vector>
 
 namespace llvm {
 
   class CallSite;
   class DataLayout;
+  class EphemeralValues;
 
   namespace InlineConstants {
     // Various magic constants used to adjust heuristics.
     const int InstrCost = 5;
     const int IndirectCallThreshold = 100;
     const int CallPenalty = 25;
     const int LastCallToStaticBonus = -15000;
     const int ColdccPenalty = 2000;
public:
     /// value if the cost is too high to inline.
     int getCostDelta() const { return Threshold - getCost(); }
   };
 
   /// InlineCostAnalyzer - Cost analyzer used by inliner.
   class InlineCostAnalyzer {
     // DataLayout if available, or null.
     const DataLayout *TD;
+    // EphemeralValues if available, or null.
+    const EphemeralValues *EV;
 
   public:
-    InlineCostAnalyzer(): TD(0) {}
+    InlineCostAnalyzer(): TD(0), EV(0) {}
 
     void setDataLayout(const DataLayout *TData) { TD = TData; }
+    void setEphemeralValues(const EphemeralValues *EVals) { EV = EVals; }
 
     /// \brief Get an InlineCost object representing the cost of inlining this
     /// callsite.
     ///
     /// Note that threshold is passed into this function. Only costs below the
     /// threshold are computed with any accuracy. The threshold can be used to
     /// bound the computation necessary to determine whether the cost is
     /// sufficiently low to warrant inlining.

include/llvm/Analysis/Passes.h

namespace llvm {
   //
   // createBasicAliasAnalysisPass - This pass implements the stateless alias
   // analysis.
   //
   ImmutablePass *createBasicAliasAnalysisPass();
 
   //===--------------------------------------------------------------------===//
   //
+  // createEphemeralValuesPass - This pass identifies ephemeral values.
+  //
+  ModulePass *createEphemeralValuesPass();
+
+  //===--------------------------------------------------------------------===//
+  //
   /// createLibCallAliasAnalysisPass - Create an alias analysis pass that knows
   /// about the semantics of a set of libcalls specified by LCI.  The newly
   /// constructed pass takes ownership of the pointer that is provided.
   ///
   FunctionPass *createLibCallAliasAnalysisPass(LibCallInfo *LCI);
 
   //===--------------------------------------------------------------------===//
   //

include/llvm/InitializePasses.h

 void initializeAAEvalPass(PassRegistry&);
 void initializeADCEPass(PassRegistry&);
 void initializeAliasAnalysisAnalysisGroup(PassRegistry&);
 void initializeAliasAnalysisCounterPass(PassRegistry&);
 void initializeAliasDebuggerPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlwaysInlinerPass(PassRegistry&);
 void initializeArgPromotionPass(PassRegistry&);
+void initializeAlignmentInvPropPass(PassRegistry&);
 void initializeBarrierNoopPass(PassRegistry&);
 void initializeBasicAliasAnalysisPass(PassRegistry&);
 void initializeBasicCallGraphPass(PassRegistry&);
 void initializeBlockExtractorPassPass(PassRegistry&);
 void initializeBlockFrequencyInfoPass(PassRegistry&);
 void initializeBlockPlacementPass(PassRegistry&);
 void initializeBoundsCheckingPass(PassRegistry&);
 void initializeBranchFolderPassPass(PassRegistry&);

 void initializeDomPrinterPass(PassRegistry&);
 void initializeDomViewerPass(PassRegistry&);
 void initializeDominanceFrontierPass(PassRegistry&);
 void initializeDominatorTreePass(PassRegistry&);
 void initializeEarlyIfConverterPass(PassRegistry&);
 void initializeEdgeBundlesPass(PassRegistry&);
 void initializeEdgeProfilerPass(PassRegistry&);
 void initializeExpandPostRAPass(PassRegistry&);
+void initializeEphemeralValuesPass(PassRegistry&);
 void initializePathProfilerPass(PassRegistry&);
 void initializeGCOVProfilerPass(PassRegistry&);
 void initializeAddressSanitizerPass(PassRegistry&);
 void initializeAddressSanitizerModulePass(PassRegistry&);
 void initializeMemorySanitizerPass(PassRegistry&);
 void initializeThreadSanitizerPass(PassRegistry&);
 void initializeEarlyCSEPass(PassRegistry&);
 void initializeExpandISelPseudosPass(PassRegistry&);

include/llvm/Intrinsics.td

 def int_prefetch      : Intrinsic<[],
                                   [llvm_ptr_ty, llvm_i32_ty, llvm_i32_ty,
                                    llvm_i32_ty],
                                   [IntrReadWriteArgMem, NoCapture<0>]>;
 def int_pcmarker      : Intrinsic<[], [llvm_i32_ty]>;
 
 def int_readcyclecounter : Intrinsic<[llvm_i64_ty]>;
 
+def int_invariant     : Intrinsic<[], [llvm_i1_ty], [IntrNoMem]>;
+
 // Stack Protector Intrinsic - The stackprotector intrinsic writes the stack
 // guard to the correct place on the stack frame.
 def int_stackprotector : Intrinsic<[], [llvm_ptr_ty, llvm_ptrptr_ty], []>;
 
 //===------------------- Standard C Library Intrinsics --------------------===//
 //
 
 def int_memcpy  : Intrinsic<[],

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       if (std::getenv("bar") != (char*) -1)
         return;
 
       (void) llvm::createAAEvalPass();
       (void) llvm::createAggressiveDCEPass();
       (void) llvm::createAliasAnalysisCounterPass();
       (void) llvm::createAliasDebugger();
       (void) llvm::createArgumentPromotionPass();
+      (void) llvm::createAlignmentInvPropPass();
       (void) llvm::createBasicAliasAnalysisPass();
       (void) llvm::createLibCallAliasAnalysisPass(0);
       (void) llvm::createScalarEvolutionAliasAnalysisPass();
       (void) llvm::createTypeBasedAliasAnalysisPass();
       (void) llvm::createBlockPlacementPass();
       (void) llvm::createBoundsCheckingPass();
       (void) llvm::createBreakCriticalEdgesPass();
       (void) llvm::createCFGSimplificationPass();

include/llvm/Transforms/Scalar.h

 //===----------------------------------------------------------------------===//
 //
 // ConstantPropagation - A worklist driven constant propagation pass
 //
 FunctionPass *createConstantPropagationPass();
 
 //===----------------------------------------------------------------------===//
 //
+// AlignmentInvProp - A worklist driven alignment assumption propagation pass
+//
+FunctionPass *createAlignmentInvPropPass();
+
+//===----------------------------------------------------------------------===//
+//
 // SCCP - Sparse conditional constant propagation.
 //
 FunctionPass *createSCCPPass();
 
 //===----------------------------------------------------------------------===//
 //
 // DeadInstElimination - This pass quickly removes trivially dead instructions
 // without modifying the CFG of the function.  It is a BasicBlockPass, so it

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeDomViewerPass(Registry);
   initializeDomPrinterPass(Registry);
   initializeDomOnlyViewerPass(Registry);
   initializePostDomViewerPass(Registry);
   initializeDomOnlyPrinterPass(Registry);
   initializePostDomPrinterPass(Registry);
   initializePostDomOnlyViewerPass(Registry);
   initializePostDomOnlyPrinterPass(Registry);
+  initializeEphemeralValuesPass(Registry);
   initializeIVUsersPass(Registry);
   initializeInstCountPass(Registry);
   initializeIntervalPartitionPass(Registry);
   initializeLazyValueInfoPass(Registry);
   initializeLibCallAliasAnalysisPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoPass(Registry);
   initializeMemDepPrinterPass(Registry);

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   CaptureTracking.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
   DbgInfoPrinter.cpp
   DependenceAnalysis.cpp
   DomPrinter.cpp
   DominanceFrontier.cpp
+  EphemeralValues.cpp
   IVUsers.cpp
   InlineCost.cpp
   InstCount.cpp
   InstructionSimplify.cpp
   Interval.cpp
   IntervalPartition.cpp
   LazyValueInfo.cpp
   LibCallAliasAnalysis.cpp

lib/Analysis/CodeMetrics.cpp

if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I))
     return GEP->hasAllConstantIndices();
 
   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
     default:
       return false;
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_value:
+    case Intrinsic::invariant:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
     case Intrinsic::lifetime_start:
     case Intrinsic::lifetime_end:
     case Intrinsic::objectsize:
     case Intrinsic::ptr_annotation:
     case Intrinsic::var_annotation:
       // These intrinsics don't count as size.

lib/Analysis/EphemeralValues.cpp

+//===------------------------ EphemeralValues.cpp ------------------------===//
+//              Code to perform Alignment Invariant Propagation
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements ephemeral value determination.
+//
+//===----------------------------------------------------------------------===//
+
+#define EV_NAME "eph-values"
+#define DEBUG_TYPE EV_NAME
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/Analysis/EphemeralValues.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/Constant.h"
+#include "llvm/DataLayout.h"
+#include "llvm/Instruction.h"
+#include "llvm/IntrinsicInst.h"
+#include "llvm/Intrinsics.h"
+#include "llvm/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/InstIterator.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+char EphemeralValues::ID = 0;
+static const char ev_name[] = "Ephemeral value analysis";
+INITIALIZE_PASS_BEGIN(EphemeralValues, EV_NAME,
+                ev_name, false, false)
+INITIALIZE_PASS_END(EphemeralValues, EV_NAME,
+                ev_name, false, false)
+
+ModulePass *llvm::createEphemeralValuesPass() {
+  return new EphemeralValues();
+}
+
+EphemeralValues::EphemeralValues() : ModulePass(ID) {
+  initializeEphemeralValuesPass(*PassRegistry::getPassRegistry());
+}
+
+void EphemeralValues::getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+}
+
+void EphemeralValues::print(raw_ostream &OS, const Module *M) const {
+  if (!M)
+    return;
+
+  OS << "Ephemeral values...\n";
+  for (Module::const_iterator L = M->begin(), LE = M->end(); L != LE; ++L)
+    for (Function::const_iterator I = L->begin(), IE = L->end(); I != IE; ++I)
+      for (BasicBlock::const_iterator J = I->getFirstInsertionPt(),
+           JE = I->end(); J != JE; ++J)
+        if (isEphemeralValue(J)) {
+          OS << "\tephemeral: " << L->getName() << ": " << I->getName() <<
+                ": " << *J << "\n";
+        }
+}
+
+bool EphemeralValues::runOnModule(Module &M) {
+  DenseSet<Value *> Visited;
+  SmallVector<Value *, 16> WorkSet;
+
+  EphValues.clear();
+
+  for (Module::iterator L = M.begin(), LE = M.end(); L != LE; ++L)
+    for (Function::iterator I = L->begin(), IE = L->end(); I != IE; ++I)
+      for (BasicBlock::iterator J = I->getFirstInsertionPt(), JE = I->end();
+           J != JE; ++J)
+        if (CallInst *CI = dyn_cast<CallInst>(J))
+          if (Function *F2 = CI->getCalledFunction())
+            if (F2->getIntrinsicID() == Intrinsic::invariant) {
+              WorkSet.push_back(CI);
+              EphValues.insert(CI);
+            }
+
+  while (!WorkSet.empty()) {
+    Value *V = WorkSet.pop_back_val();
+    if (!Visited.insert(V).second)
+      continue;
+
+    // If all uses of this value are ephemeral, then so is this value.
+    bool FoundNEUse = false;
+    for (Value::use_iterator I = V->use_begin(), IE = V->use_end();
+         I != IE; ++I)
+      if (!EphValues.count(*I)) {
+        FoundNEUse = true;
+        break;
+      }
+
+    if (!FoundNEUse) {
+      EphValues.insert(V);
+
+      if (User *U = dyn_cast<User>(V))
+        for (User::op_iterator J = U->op_begin(), JE = U->op_end();
+             J != JE; ++J)
+          WorkSet.push_back(*J);
+    }
+  }
+
+  return false;
+}
+

lib/Analysis/InlineCost.cpp

 //===- InlineCost.cpp - Cost analysis for inliner -------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements inline cost analysis.
 //
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "inline-cost"
+#include "llvm/Analysis/EphemeralValues.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"

 namespace {
 
 class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   typedef InstVisitor<CallAnalyzer, bool> Base;
   friend class InstVisitor<CallAnalyzer, bool>;
 
   // DataLayout if available, or null.
   const DataLayout *const TD;
+  // EphemeralValues if available, or null.
+  const EphemeralValues *const EV;
 
   // The called function.
   Function &F;
 
   int Threshold;
   int Cost;
 
   bool IsCallerRecursive;
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool visitICmp(ICmpInst &I);
   bool visitSub(BinaryOperator &I);
   bool visitBinaryOperator(BinaryOperator &I);
   bool visitLoad(LoadInst &I);
   bool visitStore(StoreInst &I);
   bool visitCallSite(CallSite CS);
 
 public:
-  CallAnalyzer(const DataLayout *TD, Function &Callee, int Threshold)
-    : TD(TD), F(Callee), Threshold(Threshold), Cost(0),
+  CallAnalyzer(const DataLayout *TD, const EphemeralValues *EV,
+               Function &Callee, int Threshold)
+    : TD(TD), EV(EV), F(Callee), Threshold(Threshold), Cost(0),
       IsCallerRecursive(false), IsRecursiveCall(false),
       ExposesReturnsTwice(false), HasDynamicAlloca(false), AllocatedSize(0),
       NumInstructions(0), NumVectorInstructions(0),
       FiftyPercentVectorBonus(0), TenPercentVectorBonus(0), VectorBonus(0),
       NumConstantArgs(0), NumConstantOffsetPtrArgs(0), NumAllocaArgs(0),
       NumConstantPtrCmps(0), NumConstantPtrDiffs(0),
       NumInstructionsSimplified(0), SROACostSavings(0), SROACostSavingsLost(0) {
   }
bool CallAnalyzer::visitCallSite(CallSite CS) {
   if (!F)
     return Base::visitCallSite(CS);
 
   // If we have a constant that we are calling as a function, we can peer
   // through it and see the function target. This happens not infrequently
   // during devirtualization and so we want to give it a hefty bonus for
   // inlining, but cap that bonus in the event that inlining wouldn't pan
   // out. Pretend to inline the function, with a custom threshold.
-  CallAnalyzer CA(TD, *F, InlineConstants::IndirectCallThreshold);
+  CallAnalyzer CA(TD, EV, *F, InlineConstants::IndirectCallThreshold);
   if (CA.analyzeCall(CS)) {
     // We were able to inline the indirect call! Subtract the cost from the
     // bonus we want to apply, but don't go below zero.
     Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost());
   }
 
   return Base::visitCallSite(CS);
 }
for (BasicBlock::iterator I = BB->begin(), E = llvm::prior(BB->end());
     if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy())
       ++NumVectorInstructions;
 
     // If the instruction simplified to a constant, there is no cost to this
     // instruction. Visit the instructions using our InstVisitor to account for
     // all of the per-instruction logic. The visit tree returns true if we
     // consumed the instruction in any way, and false if the instruction's base
     // cost should count against inlining.
-    if (Base::visit(I))
+    if ((EV && EV->isEphemeralValue(I)) || Base::visit(I))
       ++NumInstructionsSimplified;
     else
       Cost += InlineConstants::InstrCost;
 
     // If the visit this instruction detected an uninlinable pattern, abort.
     if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca)
       return false;
 
InlineCost InlineCostAnalyzer::getInlineCost(CallSite CS, Function *Callee,
   if (Callee->mayBeOverridden() ||
       Callee->getFnAttributes().hasAttribute(Attributes::NoInline) ||
       CS.isNoInline())
     return llvm::InlineCost::getNever();
 
   DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
         << "...\n");
 
-  CallAnalyzer CA(TD, *Callee, Threshold);
+  CallAnalyzer CA(TD, EV, *Callee, Threshold);
   bool ShouldInline = CA.analyzeCall(CS);
 
   DEBUG(CA.dump());
 
   // Check if there was a reason to force inlining or no inlining.
   if (!ShouldInline && CA.getCost() < CA.getThreshold())
     return InlineCost::getNever();
   if (ShouldInline && CA.getCost() >= CA.getThreshold())

lib/Analysis/ValueTracking.cpp

bool llvm::isSafeToSpeculativelyExecute(const Value *V,
    if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
      switch (II->getIntrinsicID()) {
        // These synthetic intrinsics have no side-effects, and just mark
        // information about their operands.
        // FIXME: There are other no-op synthetic instructions that potentially
        // should be considered at least *safe* to speculate...
        case Intrinsic::dbg_declare:
        case Intrinsic::dbg_value:
+       case Intrinsic::invariant:
          return true;
 
        case Intrinsic::bswap:
        case Intrinsic::ctlz:
        case Intrinsic::ctpop:
        case Intrinsic::cttz:
        case Intrinsic::objectsize:
        case Intrinsic::sadd_with_overflow:

lib/CodeGen/IntrinsicLowering.cpp

void IntrinsicLowering::LowerIntrinsicCall(CallInst *CI) {
   case Intrinsic::dbg_declare:
     break;    // Simply strip out debugging intrinsics
 
   case Intrinsic::eh_typeid_for:
     // Return something different to eh_selector.
     CI->replaceAllUsesWith(ConstantInt::get(CI->getType(), 1));
     break;
 
+  case Intrinsic::invariant:
   case Intrinsic::var_annotation:
     break;   // Strip out annotate intrinsic
     
   case Intrinsic::memcpy: {
     Type *IntPtr = TD.getIntPtrType(Context);
     Value *Size = Builder.CreateIntCast(CI->getArgOperand(2), IntPtr,
                                         /* isSigned */ false);
     Value *Ops[3];
     Ops[0] = CI->getArgOperand(0);
     Ops[1] = CI->getArgOperand(1);

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::objectsize: {
     if (CI->isZero())
       Res = DAG.getConstant(-1ULL, Ty);
     else
       Res = DAG.getConstant(0, Ty);
 
     setValue(&I, Res);
     return 0;
   }
+  case Intrinsic::invariant:
   case Intrinsic::var_annotation:
     // Discard annotate attributes
     return 0;
 
   case Intrinsic::init_trampoline: {
     const Function *F = cast<Function>(I.getArgOperand(1)->stripPointerCasts());
 
     SDValue Ops[6];
     Ops[0] = getRoot();
     Ops[1] = getValue(I.getArgOperand(0));

lib/Transforms/IPO/InlineSimple.cpp

 //===- InlineSimple.cpp - Code to perform simple function inlining --------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements bottom-up inlining of functions into callees.
 //
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "inline"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/EphemeralValues.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/CallingConv.h"
 #include "llvm/DataLayout.h"
 #include "llvm/Instructions.h"
 #include "llvm/IntrinsicInst.h"
 #include "llvm/Module.h"
 #include "llvm/Support/CallSite.h"
 #include "llvm/Transforms/IPO/InlinerPass.h"
public:
     SimpleInliner(int Threshold) : Inliner(ID, Threshold,
                                            /*InsertLifetime*/true) {
       initializeSimpleInlinerPass(*PassRegistry::getPassRegistry());
     }
     static char ID; // Pass identification, replacement for typeid
     InlineCost getInlineCost(CallSite CS) {
       return CA.getInlineCost(CS, getInlineThreshold(CS));
     }
+    virtual void getAnalysisUsage(AnalysisUsage &Info) const {
+      Info.addRequired<EphemeralValues>();
+      Inliner::getAnalysisUsage(Info);
+    }
     using llvm::Pass::doInitialization;
     virtual bool doInitialization(CallGraph &CG);
   };
 }
 
 char SimpleInliner::ID = 0;
 INITIALIZE_PASS_BEGIN(SimpleInliner, "inline",
                 "Function Integration/Inlining", false, false)
 INITIALIZE_AG_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(EphemeralValues)
 INITIALIZE_PASS_END(SimpleInliner, "inline",
                 "Function Integration/Inlining", false, false)
 
 Pass *llvm::createFunctionInliningPass() { return new SimpleInliner(); }
 
 Pass *llvm::createFunctionInliningPass(int Threshold) {
   return new SimpleInliner(Threshold);
 }
 
 // doInitialization - Initializes the vector of functions that have been
 // annotated with the noinline attribute.
 bool SimpleInliner::doInitialization(CallGraph &CG) {
   CA.setDataLayout(getAnalysisIfAvailable<DataLayout>());
+
+  // FIXME: We need to use getAnalysisIfAvailable instead of getAnalysis
+  // because, even though the pass was been required, it will not have been
+  // run. getAnalysisIfAvailable will run the pass now, while getAnalysis
+  // will not (and will assert instead).
+  CA.setEphemeralValues(getAnalysisIfAvailable<EphemeralValues>());
   return false;
 }
 

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(PassManagerBase &MPM) {
 
   if (LoopVectorize)
     MPM.add(createLoopVectorizePass());
 
   if (!DisableUnrollLoops)
     MPM.add(createLoopUnrollPass());          // Unroll small loops
   addExtensionsToPM(EP_LoopOptimizerEnd, MPM);
 
+  MPM.add(createAlignmentInvPropPass());      // Alignment invariants
+
   if (OptLevel > 1)
     MPM.add(createGVNPass());                 // Remove redundancies
   MPM.add(createMemCpyOptPass());             // Remove memcpy / form memset
   MPM.add(createSCCPPass());                  // Constant prop with SCCP
 
   // Run instcombine after redundancy elimination to exploit opportunities
   // opened up by them.
   MPM.add(createInstructionCombiningPass());

lib/Transforms/Scalar/ADCE.cpp

 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/BasicBlock.h"
 #include "llvm/Instructions.h"
 #include "llvm/IntrinsicInst.h"
+#include "llvm/Intrinsics.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/InstIterator.h"
 using namespace llvm;
 
 STATISTIC(NumRemoved, "Number of instructions removed");
 
 namespace {
struct ADCE : public FunctionPass {
     }
 
   };
 }
 
 char ADCE::ID = 0;
 INITIALIZE_PASS(ADCE, "adce", "Aggressive Dead Code Elimination", false, false)
 
+static bool isInvariantIntrinsic(Instruction *I) {
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
+    return II->getIntrinsicID() == Intrinsic::invariant;
+
+  return false;
+}
+
 bool ADCE::runOnFunction(Function& F) {
   SmallPtrSet<Instruction*, 128> alive;
   SmallVector<Instruction*, 128> worklist;
 
   // Collect the set of "root" instructions that are known live.
   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
     if (isa<TerminatorInst>(I.getInstructionIterator()) ||
         isa<DbgInfoIntrinsic>(I.getInstructionIterator()) ||
+        isInvariantIntrinsic(I.getInstructionIterator()) ||
         isa<LandingPadInst>(I.getInstructionIterator()) ||
         I->mayHaveSideEffects()) {
       alive.insert(I.getInstructionIterator());
       worklist.push_back(I.getInstructionIterator());
     }
 
   // Propagate liveness backwards to operands.
   while (!worklist.empty()) {

lib/Transforms/Scalar/AlignmentInvProp.cpp

+//===------------------------ AlignmentInvProp.cpp ------------------------===//
+//              Code to perform Alignment Invariant Propagation
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements alignment invariant propagation.
+//
+//===----------------------------------------------------------------------===//
+
+#define AA_NAME "alignment-inv-prop"
+#define DEBUG_TYPE AA_NAME
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Constant.h"
+#include "llvm/Instruction.h"
+#include "llvm/IntrinsicInst.h"
+#include "llvm/Intrinsics.h"
+#include "llvm/Pass.h"
+#include "llvm/DataLayout.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/InstIterator.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/PostOrderIterator.h"
+using namespace llvm;
+
+STATISTIC(NumLoadAlignChanged,
+  "Number of loads changed by alignment assumptions");
+STATISTIC(NumStoreAlignChanged,
+  "Number of stores changed by alignment assumptions");
+STATISTIC(NumMemIntAlignChanged,
+  "Number of memory intrinsics changed by alignment assumptions");
+
+namespace {
+  struct AlignmentInvProp : public FunctionPass {
+    static char ID; // Pass identification, replacement for typeid
+    AlignmentInvProp() : FunctionPass(ID) {
+      initializeAlignmentInvPropPass(*PassRegistry::getPassRegistry());
+    }
+
+    bool runOnFunction(Function &F);
+
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+      AU.setPreservesCFG();
+      AU.addRequired<ScalarEvolution>();
+    }
+  };
+}
+
+char AlignmentInvProp::ID = 0;
+static const char aip_name[] = "Alignment invariant propagation";
+INITIALIZE_PASS_BEGIN(AlignmentInvProp, AA_NAME,
+                aip_name, false, false)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
+INITIALIZE_PASS_END(AlignmentInvProp, AA_NAME,
+                aip_name, false, false)
+
+FunctionPass *llvm::createAlignmentInvPropPass() {
+  return new AlignmentInvProp();
+}
+
+static unsigned getNewAlignmentDiff(const SCEV *DiffSCEV,
+                                    const SCEV *AlignSCEV,
+                                    ScalarEvolution *SE) {
+  // DiffUnits = Diff % int64_t(Alignment)
+  const SCEV *DiffAlignDiv = SE->getUDivExpr(DiffSCEV, AlignSCEV);
+  const SCEV *DiffAlign = SE->getMulExpr(DiffAlignDiv, AlignSCEV);
+  const SCEV *DiffUnitsSCEV = SE->getMinusSCEV(DiffAlign, DiffSCEV);
+
+  DEBUG(dbgs() << "\talignment relative to " << *AlignSCEV << " is " <<
+                  *DiffUnitsSCEV << " (diff: " << *DiffSCEV << ")\n");
+
+  if (const SCEVConstant *ConstDUSCEV =
+      dyn_cast<SCEVConstant>(DiffUnitsSCEV)) {
+    int64_t DiffUnits = ConstDUSCEV->getValue()->getSExtValue();
+
+    if (!DiffUnits)
+      return (unsigned)
+        cast<SCEVConstant>(AlignSCEV)->getValue()->getSExtValue();
+
+    uint64_t DiffUnitsAbs = abs64(DiffUnits);
+    if (isPowerOf2_64(DiffUnitsAbs))
+      return (unsigned) DiffUnitsAbs;
+  }
+
+  return 0;
+}
+
+static unsigned getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV,
+                                const SCEV *OffSCEV, Value *Ptr,
+                                ScalarEvolution *SE) {
+  const SCEV *PtrSCEV = SE->getSCEV(Ptr);
+  const SCEV *DiffSCEV = SE->getMinusSCEV(PtrSCEV, AASCEV);
+
+  // What we really want to know if the overall offset to the aligned
+  // address. This address is displaced by the provided offset.
+  DiffSCEV = SE->getMinusSCEV(DiffSCEV, OffSCEV);
+
+  DEBUG(dbgs() << AA_NAME ": alignment of " << *Ptr << " relative to " <<
+                  *AlignSCEV << " and offset " << *OffSCEV <<
+                  " using diff " << *DiffSCEV << "\n");
+
+  unsigned NewAlignment = getNewAlignmentDiff(DiffSCEV, AlignSCEV, SE);
+  DEBUG(dbgs() << "\tnew alignment: " << NewAlignment << "\n");
+
+  if (NewAlignment) {
+    return NewAlignment;
+  } else if (const SCEVAddRecExpr *DiffARSCEV =
+             dyn_cast<SCEVAddRecExpr>(DiffSCEV)) {
+    // The relative offset to the alignment assumption did not yield a constant,
+    // but we should try harder: if we assume that a is 32-byte aligned, then in
+    // for (i = 0; i < 1024; i += 4) r += a[i]; not all of the loads from a are
+    // 32-byte aligned, but instead alternate between 32 and 16-byte alignment.
+    // As a result, the new alignment will not be a constant, but can still
+    // be improved over the default (of 4) to 16.
+
+    const SCEV *DiffStartSCEV = DiffARSCEV->getStart();
+    const SCEV *DiffIncSCEV = DiffARSCEV->getStepRecurrence(*SE);
+
+    DEBUG(dbgs() << "\ttrying start/inc alignment using start " <<
+                    *DiffStartSCEV << " and inc " << *DiffIncSCEV << "\n");
+
+    NewAlignment = getNewAlignmentDiff(DiffStartSCEV, AlignSCEV, SE);
+    unsigned NewIncAlignment = getNewAlignmentDiff(DiffIncSCEV, AlignSCEV, SE);
+
+    DEBUG(dbgs() << "\tnew start alignment: " << NewAlignment << "\n");
+    DEBUG(dbgs() << "\tnew inc alignment: " << NewIncAlignment << "\n");
+
+    if (NewAlignment > NewIncAlignment) {
+      if (NewAlignment % NewIncAlignment == 0) {
+        DEBUG(dbgs() << "\tnew start/inc alignment: " <<
+                        NewIncAlignment << "\n");
+        return NewIncAlignment;
+      }
+    } else if (NewIncAlignment > NewAlignment) {
+      if (NewIncAlignment % NewAlignment == 0) {
+        DEBUG(dbgs() << "\tnew start/inc alignment: " <<
+                        NewAlignment << "\n");
+        return NewAlignment;
+      }
+    } else if (NewIncAlignment == NewAlignment && NewIncAlignment) {
+      DEBUG(dbgs() << "\tnew start/inc alignment: " <<
+                      NewAlignment << "\n");
+      return NewAlignment;
+    }
+  }
+
+  return 0;
+}
+
+bool AlignmentInvProp::runOnFunction(Function &F) {
+  SmallVector<Value *, 4> InvConds;
+  BasicBlock *EntryBB = F.begin();
+  for (df_iterator<BasicBlock *> I = df_begin(EntryBB), IE = df_end(EntryBB);
+       I != IE; ++I)
+    for (BasicBlock::iterator J = I->getFirstInsertionPt(), JE = I->end();
+         J != JE; ++J)
+      if (CallInst *CI = dyn_cast<CallInst>(J))
+        if (Function *F2 = CI->getCalledFunction())
+          if (F2->getIntrinsicID() == Intrinsic::invariant)
+            InvConds.push_back(CI->getArgOperand(0));
+
+  // Visit all invariant conditions, and split those that are ands of
+  // other conditions.
+  DenseSet<Value *> VisitedInvCond;
+  while (VisitedInvCond.size() != InvConds.size()) {
+    SmallVector<Value *, 4> NewInvConds;
+    for (SmallVector<Value*, 4>::iterator I = InvConds.begin(),
+         IE = InvConds.end(); I != IE; ++I) {
+      if (BinaryOperator *BO = dyn_cast<BinaryOperator>(*I)) {
+        if (BO->getOpcode() == Instruction::And) {
+          NewInvConds.push_back(BO->getOperand(0));
+          NewInvConds.push_back(BO->getOperand(1));
+        }
+      }
+
+      VisitedInvCond.insert(*I);
+    }
+
+    InvConds.insert(InvConds.end(), NewInvConds.begin(), NewInvConds.end());
+    NewInvConds.clear();
+  }
+
+  bool Changed = false;
+  ScalarEvolution *SE = &getAnalysis<ScalarEvolution>();
+
+  DenseMap<MemTransferInst *, unsigned> NewDestAlignments, NewSrcAlignments;
+
+  for (SmallVector<Value *, 4>::iterator I = InvConds.begin(),
+       IE = InvConds.end(); I != IE; ++I) {
+    // An alignment invariant must be a statement about the least-significant
+    // bits of the pointer being zero, possibly with some offset.
+    ICmpInst *ICI = dyn_cast<ICmpInst>(*I);
+    if (!ICI)
+      continue;
+
+    // This must be an expression of the form: x & m == 0.
+    if (ICI->getPredicate() != ICmpInst::ICMP_EQ)
+      continue;
+
+    Value *CmpLHS = ICI->getOperand(0);
+    Value *CmpRHS = ICI->getOperand(1);
+    const SCEV *CmpLHSSCEV = SE->getSCEV(CmpLHS);
+    const SCEV *CmpRHSSCEV = SE->getSCEV(CmpRHS);
+    if (CmpLHSSCEV->isZero())
+      std::swap(CmpLHS, CmpRHS);
+    else if (!CmpRHSSCEV->isZero())
+      continue;
+
+    BinaryOperator *CmpBO = dyn_cast<BinaryOperator>(CmpLHS);
+    if (!CmpBO || CmpBO->getOpcode() != Instruction::And)
+      continue;
+
+    Value *AndLHS = CmpBO->getOperand(0);
+    Value *AndRHS = CmpBO->getOperand(1);
+    const SCEV *AndLHSSCEV = SE->getSCEV(AndLHS);
+    const SCEV *AndRHSSCEV = SE->getSCEV(AndRHS);
+    if (isa<SCEVConstant>(AndLHSSCEV)) {
+      std::swap(AndLHS, AndRHS);
+      std::swap(AndLHSSCEV, AndRHSSCEV);
+    }
+
+    const SCEVConstant *MaskSCEV = dyn_cast<SCEVConstant>(AndRHSSCEV);
+    if (!MaskSCEV)
+      continue;
+
+    unsigned TrailingOnes =
+      MaskSCEV->getValue()->getValue().countTrailingOnes();
+    if (!TrailingOnes)
+      continue;
+
+    uint64_t Alignment;
+    TrailingOnes = std::min(TrailingOnes,
+      unsigned(sizeof(unsigned) * CHAR_BIT - 1));
+    Alignment = std::min(1u << TrailingOnes, +Value::MaximumAlignment);
+
+    Type *Int64Ty = Type::getInt64Ty(F.getContext());
+    const SCEV *AlignSCEV = SE->getConstant(Int64Ty, Alignment);
+
+    // The LHS might be a ptrtoint instruction, or it might be the pointer
+    // with an offset.
+    Value *AAPtr = 0;
+    const SCEV *OffSCEV = 0;
+    if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(AndLHS)) {
+      AAPtr = PToI->getPointerOperand();
+      OffSCEV = SE->getConstant(Int64Ty, 0);
+    } else if (const SCEVAddExpr* AndLHSAddSCEV =
+               dyn_cast<SCEVAddExpr>(AndLHSSCEV)) {
+      // Try to find the ptrtoint; subtract it and the rest is the offset.
+      for (SCEVAddExpr::op_iterator J = AndLHSAddSCEV->op_begin(),
+           JE = AndLHSAddSCEV->op_end(); J != JE; ++J)
+        if (const SCEVUnknown *OpUnk = dyn_cast<SCEVUnknown>(*J))
+          if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(OpUnk->getValue())) {
+            AAPtr = PToI->getPointerOperand();
+            OffSCEV = SE->getMinusSCEV(AndLHSAddSCEV, *J);
+            break;
+          }
+    }
+
+    if (!AAPtr)
+      continue;
+    
+    unsigned OffSCEVBits = OffSCEV->getType()->getPrimitiveSizeInBits();
+    if (OffSCEVBits < 64)
+      OffSCEV = SE->getSignExtendExpr(OffSCEV, Int64Ty);
+    else if (OffSCEVBits > 64)
+      continue;
+
+    AAPtr = AAPtr->stripPointerCasts();
+    const SCEV *AASCEV = SE->getSCEV(AAPtr);
+
+    // Apply the assumption to all other users of the specified pointer.
+    DenseSet<Instruction *> Visited;
+    SmallVector<Instruction*, 16> WorkList;
+    for (Value::use_iterator J = AAPtr->use_begin(),
+         JE = AAPtr->use_end(); J != JE; ++J) {
+      if (*J == *I)
+        continue;
+
+      if (Instruction *K = dyn_cast<Instruction>(*J))
+        WorkList.push_back(K);
+    }
+
+    while (!WorkList.empty()) {
+      Instruction *J = WorkList.pop_back_val();
+
+      if (LoadInst *LI = dyn_cast<LoadInst>(J)) {
+        unsigned NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,
+          LI->getPointerOperand(), SE);
+
+        if (NewAlignment > LI->getAlignment()) {
+          LI->setAlignment(NewAlignment);
+          ++NumLoadAlignChanged;
+          Changed = true;
+        }
+      } else if (StoreInst *SI = dyn_cast<StoreInst>(J)) {
+        unsigned NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,
+          SI->getPointerOperand(), SE);
+
+        if (NewAlignment > SI->getAlignment()) {
+          SI->setAlignment(NewAlignment);
+          ++NumStoreAlignChanged;
+          Changed = true;
+        }
+      } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(J)) {
+        unsigned NewDestAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,
+          MI->getDest(), SE);
+
+        // For memory transfers, we need a common alignment for both the
+        // source and destination. If we have a new alignment for this
+        // instruction, but only for one operand, save it. If we reach the
+        // other operand through another assumption later, then we may
+        // change the alignment at that point.
+        if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) {
+          unsigned NewSrcAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV,
+            MTI->getSource(), SE);
+
+          DenseMap<MemTransferInst *, unsigned>::iterator DI =
+            NewDestAlignments.find(MTI);
+          unsigned AltDestAlignment = (DI == NewDestAlignments.end()) ?
+                                      0 : DI->second;
+
+          DenseMap<MemTransferInst *, unsigned>::iterator SI =
+            NewSrcAlignments.find(MTI);
+          unsigned AltSrcAlignment = (SI == NewSrcAlignments.end()) ?
+                                     0 : SI->second;
+
+          DEBUG(dbgs() << "\tmem trans: " << NewDestAlignment << " " <<
+                          AltDestAlignment << " " << NewSrcAlignment <<
+                          " " << AltSrcAlignment << "\n");
+
+          // If these four alignments, pick the largest possible...
+          unsigned NewAlignment = 0;
+          if (NewDestAlignment <= NewSrcAlignment ||
+              NewDestAlignment <= AltSrcAlignment)
+            NewAlignment = std::max(NewAlignment, NewDestAlignment);
+          if (AltDestAlignment <= NewSrcAlignment ||
+              AltDestAlignment <= AltSrcAlignment)
+            NewAlignment = std::max(NewAlignment, AltDestAlignment);
+          if (NewSrcAlignment <= NewDestAlignment ||
+              NewSrcAlignment <= AltDestAlignment)
+            NewAlignment = std::max(NewAlignment, NewSrcAlignment);
+          if (AltSrcAlignment <= NewDestAlignment ||
+              AltSrcAlignment <= AltDestAlignment)
+            NewAlignment = std::max(NewAlignment, AltSrcAlignment);
+
+          if (NewAlignment > MI->getAlignment()) {
+            MI->setAlignment(ConstantInt::get(Type::getInt32Ty(
+              MI->getParent()->getContext()), NewAlignment));
+            ++NumMemIntAlignChanged;
+            Changed = true;
+          }
+
+          NewDestAlignments.insert(std::make_pair(MTI, NewDestAlignment));
+          NewSrcAlignments.insert(std::make_pair(MTI, NewSrcAlignment));
+        } else if (NewDestAlignment > MI->getAlignment()) {
+          MI->setAlignment(ConstantInt::get(Type::getInt32Ty(
+            MI->getParent()->getContext()), NewDestAlignment));
+          ++NumMemIntAlignChanged;
+          Changed = true;
+        }
+      }
+
+      Visited.insert(J);
+      for (Value::use_iterator UJ = J->use_begin(), UE = J->use_end();
+           UJ != UE; ++UJ) {
+        Instruction *K = cast<Instruction>(*UJ);
+        if (!Visited.count(K))
+          WorkList.push_back(cast<Instruction>(*UJ));
+      }
+    }
+
+    Changed = true;
+  }
+
+  return Changed;
+}
+

lib/Transforms/Scalar/CMakeLists.txt

 add_llvm_library(LLVMScalarOpts
   ADCE.cpp
+  AlignmentInvProp.cpp
   BasicBlockPlacement.cpp
   CodeGenPrepare.cpp
   ConstantProp.cpp
   CorrelatedValuePropagation.cpp
   DCE.cpp
   DeadStoreElimination.cpp
   EarlyCSE.cpp
   GlobalMerge.cpp

lib/Transforms/Scalar/Scalar.cpp

 #include "llvm/PassManager.h"
 
 using namespace llvm;
 
 /// initializeScalarOptsPasses - Initialize all passes linked into the
 /// ScalarOpts library.
 void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeADCEPass(Registry);
+  initializeAlignmentInvPropPass(Registry);
   initializeBlockPlacementPass(Registry);
   initializeCodeGenPreparePass(Registry);
   initializeConstantPropagationPass(Registry);
   initializeCorrelatedValuePropagationPass(Registry);
   initializeDCEPass(Registry);
   initializeDeadInstEliminationPass(Registry);
   initializeDSEPass(Registry);
   initializeGVNPass(Registry);

 void LLVMInitializeScalarOpts(LLVMPassRegistryRef R) {
   initializeScalarOpts(*unwrap(R));
 }
 
 void LLVMAddAggressiveDCEPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createAggressiveDCEPass());
 }
 
+void LLVMAddAlignmentInvPropPass(LLVMPassManagerRef PM) {
+  unwrap(PM)->add(createAlignmentInvPropPass());
+}
+
 void LLVMAddCFGSimplificationPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createCFGSimplificationPass());
 }
 
 void LLVMAddDeadStoreEliminationPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createDeadStoreEliminationPass());
 }
 

lib/Transforms/Utils/Local.cpp

if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
     return true;
   }
   if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
     if (DVI->getValue())
       return false;
     return true;
   }
 
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+    // Invariants are dead if their condition is undef.
+    if (II->getIntrinsicID() == Intrinsic::invariant)
+      return isa<UndefValue>(II->getArgOperand(0));
+  }
+
   if (!I->mayHaveSideEffects()) return true;
 
   // Special case intrinsics that "may have side effects" but can be deleted
   // when dead.
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
     // Safe to delete llvm.stacksave if dead.
     if (II->getIntrinsicID() == Intrinsic::stacksave)
       return true;

test/Analysis/EphemeralValues/lit.local.cfg

+config.suffixes = ['.ll', '.c', '.cpp']

test/Analysis/EphemeralValues/simple.ll

+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+; RUN: opt < %s -analyze -eph-values | FileCheck %s
+
+define i32 @foo(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  tail call void @llvm.invariant(i1 %maskcond)
+  %0 = load i32* %a, align 4, !tbaa !0
+  ret i32 %0
+
+; CHECK: ephemeral: foo: entry:   %ptrint = ptrtoint i32* %a to i64
+; CHECK: ephemeral: foo: entry:   %maskedptr = and i64 %ptrint, 31
+; CHECK: ephemeral: foo: entry:   %maskcond = icmp eq i64 %maskedptr, 0
+; CHECK: ephemeral: foo: entry:   tail call void @llvm.invariant(i1 %maskcond)
+}
+
+define i32 @foo2(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %offsetptr = add i64 %ptrint, 24
+  %maskedptr = and i64 %offsetptr, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  tail call void @llvm.invariant(i1 %maskcond)
+  %arrayidx = getelementptr inbounds i32* %a, i64 2
+  %0 = load i32* %arrayidx, align 4, !tbaa !0
+  ret i32 %0
+
+; CHECK: ephemeral: foo2: entry:   %ptrint = ptrtoint i32* %a to i64
+; CHECK: ephemeral: foo2: entry:   %offsetptr = add i64 %ptrint, 24
+; CHECK: ephemeral: foo2: entry:   %maskedptr = and i64 %offsetptr, 31
+; CHECK: ephemeral: foo2: entry:   %maskcond = icmp eq i64 %maskedptr, 0
+; CHECK: ephemeral: foo2: entry:   tail call void @llvm.invariant(i1 %maskcond)
+}
+
+define i32 @hoo(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %r.06 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds i32* %a, i64 %indvars.iv
+  %0 = load i32* %arrayidx, align 4, !tbaa !0
+  %add = add nsw i32 %0, %r.06
+  %indvars.iv.next = add i64 %indvars.iv, 8
+  %1 = trunc i64 %indvars.iv.next to i32
+  %cmp = icmp slt i32 %1, 2048
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  tail call void @llvm.invariant(i1 %maskcond)
+  ret i32 %add.lcssa
+
+; CHECK: ephemeral: hoo: entry:   %ptrint = ptrtoint i32* %a to i64
+; CHECK: ephemeral: hoo: entry:   %maskedptr = and i64 %ptrint, 31
+; CHECK: ephemeral: hoo: entry:   %maskcond = icmp eq i64 %maskedptr, 0
+; CHECK: ephemeral: hoo: for.end:   tail call void @llvm.invariant(i1 %maskcond)
+}
+
+define i32 @moo2(i32* nocapture %a, i32* nocapture %b) nounwind uwtable {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  tail call void @llvm.invariant(i1 %maskcond)
+  %ptrint1 = ptrtoint i32* %b to i64
+  %maskedptr3 = and i64 %ptrint1, 127
+  %maskcond4 = icmp eq i64 %maskedptr3, 0
+  tail call void @llvm.invariant(i1 %maskcond4)
+  %0 = bitcast i32* %a to i8*
+  %1 = bitcast i32* %b to i8*
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 64, i32 4, i1 false)
+  ret i32 undef
+
+; CHECK: ephemeral: moo2: entry:   %ptrint = ptrtoint i32* %a to i64
+; CHECK: ephemeral: moo2: entry:   %maskedptr = and i64 %ptrint, 31
+; CHECK: ephemeral: moo2: entry:   %maskcond = icmp eq i64 %maskedptr, 0
+; CHECK: ephemeral: moo2: entry:   tail call void @llvm.invariant(i1 %maskcond)
+; CHECK: ephemeral: moo2: entry:   %ptrint1 = ptrtoint i32* %b to i64
+; CHECK: ephemeral: moo2: entry:   %maskedptr3 = and i64 %ptrint1, 127
+; CHECK: ephemeral: moo2: entry:   %maskcond4 = icmp eq i64 %maskedptr3, 0
+; CHECK: ephemeral: moo2: entry:   tail call void @llvm.invariant(i1 %maskcond4)
+}
+
+declare void @llvm.invariant(i1) nounwind readnone
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind
+
+!0 = metadata !{metadata !"int", metadata !1}
+!1 = metadata !{metadata !"omnipotent char", metadata !2}
+!2 = metadata !{metadata !"Simple C/C++ TBAA"}
+

test/Transforms/AlignmentInvProp/lit.local.cfg

+config.suffixes = ['.ll', '.c', '.cpp']
+

test/Transforms/AlignmentInvProp/simple.ll

+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+; RUN: opt < %s -alignment-inv-prop -S | FileCheck %s
+
+define i32 @foo(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  tail call void @llvm.invariant(i1 %maskcond)
+  %0 = load i32* %a, align 4, !tbaa !0
+  ret i32 %0
+
+; CHECK: @foo
+; CHECK: load i32* {{[^,]+}}, align 32
+; CHECK: ret i32
+}
+
+define i32 @foo2(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %offsetptr = add i64 %ptrint, 24
+  %maskedptr = and i64 %offsetptr, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  tail call void @llvm.invariant(i1 %maskcond)
+  %arrayidx = getelementptr inbounds i32* %a, i64 2
+  %0 = load i32* %arrayidx, align 4, !tbaa !0
+  ret i32 %0
+
+; CHECK: @foo2
+; CHECK: load i32* {{[^,]+}}, align 16
+; CHECK: ret i32
+}
+
+define i32 @foo2a(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %offsetptr = add i64 %ptrint, 28
+  %maskedptr = and i64 %offsetptr, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  tail call void @llvm.invariant(i1 %maskcond)
+  %arrayidx = getelementptr inbounds i32* %a, i64 -1
+  %0 = load i32* %arrayidx, align 4, !tbaa !0
+  ret i32 %0
+
+; CHECK: @foo2a
+; CHECK: load i32* {{[^,]+}}, align 32
+; CHECK: ret i32
+}
+
+define i32 @goo(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  tail call void @llvm.invariant(i1 %maskcond)
+  %0 = load i32* %a, align 4, !tbaa !0
+  ret i32 %0
+
+; CHECK: @goo
+; CHECK: load i32* {{[^,]+}}, align 32
+; CHECK: ret i32
+}
+
+define i32 @hoo(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %r.06 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds i32* %a, i64 %indvars.iv
+  %0 = load i32* %arrayidx, align 4, !tbaa !0
+  %add = add nsw i32 %0, %r.06
+  %indvars.iv.next = add i64 %indvars.iv, 8
+  %1 = trunc i64 %indvars.iv.next to i32
+  %cmp = icmp slt i32 %1, 2048
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  tail call void @llvm.invariant(i1 %maskcond)
+  ret i32 %add.lcssa
+
+; CHECK: @hoo
+; CHECK: load i32* %arrayidx, align 32
+; CHECK: ret i32 %add.lcssa
+}
+
+define i32 @joo(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 4, %entry ], [ %indvars.iv.next, %for.body ]
+  %r.06 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds i32* %a, i64 %indvars.iv
+  %0 = load i32* %arrayidx, align 4, !tbaa !0
+  %add = add nsw i32 %0, %r.06
+  %indvars.iv.next = add i64 %indvars.iv, 8
+  %1 = trunc i64 %indvars.iv.next to i32
+  %cmp = icmp slt i32 %1, 2048
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  tail call void @llvm.invariant(i1 %maskcond)
+  ret i32 %add.lcssa
+
+; CHECK: @joo
+; CHECK: load i32* %arrayidx, align 16
+; CHECK: ret i32 %add.lcssa
+}
+
+define i32 @koo(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %r.06 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds i32* %a, i64 %indvars.iv
+  %0 = load i32* %arrayidx, align 4, !tbaa !0
+  %add = add nsw i32 %0, %r.06
+  %indvars.iv.next = add i64 %indvars.iv, 4
+  %1 = trunc i64 %indvars.iv.next to i32
+  %cmp = icmp slt i32 %1, 2048
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  tail call void @llvm.invariant(i1 %maskcond)
+  ret i32 %add.lcssa
+
+; CHECK: @koo
+; CHECK: load i32* %arrayidx, align 16
+; CHECK: ret i32 %add.lcssa
+}
+
+define i32 @koo2(i32* nocapture %a) nounwind uwtable readonly {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ -4, %entry ], [ %indvars.iv.next, %for.body ]
+  %r.06 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds i32* %a, i64 %indvars.iv
+  %0 = load i32* %arrayidx, align 4, !tbaa !0
+  %add = add nsw i32 %0, %r.06
+  %indvars.iv.next = add i64 %indvars.iv, 4
+  %1 = trunc i64 %indvars.iv.next to i32
+  %cmp = icmp slt i32 %1, 2048
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  tail call void @llvm.invariant(i1 %maskcond)
+  ret i32 %add.lcssa
+
+; CHECK: @koo2
+; CHECK: load i32* %arrayidx, align 16
+; CHECK: ret i32 %add.lcssa
+}
+
+define i32 @moo(i32* nocapture %a) nounwind uwtable {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  tail call void @llvm.invariant(i1 %maskcond)
+  %0 = bitcast i32* %a to i8*
+  tail call void @llvm.memset.p0i8.i64(i8* %0, i8 0, i64 64, i32 4, i1 false)
+  ret i32 undef
+
+; CHECK: @moo
+; CHECK: @llvm.memset.p0i8.i64(i8* %0, i8 0, i64 64, i32 32, i1 false)
+; CHECK: ret i32 undef
+}
+
+define i32 @moo2(i32* nocapture %a, i32* nocapture %b) nounwind uwtable {
+entry:
+  %ptrint = ptrtoint i32* %a to i64
+  %maskedptr = and i64 %ptrint, 31
+  %maskcond = icmp eq i64 %maskedptr, 0
+  tail call void @llvm.invariant(i1 %maskcond)
+  %ptrint1 = ptrtoint i32* %b to i64
+  %maskedptr3 = and i64 %ptrint1, 127
+  %maskcond4 = icmp eq i64 %maskedptr3, 0
+  tail call void @llvm.invariant(i1 %maskcond4)
+  %0 = bitcast i32* %a to i8*
+  %1 = bitcast i32* %b to i8*
+  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 64, i32 4, i1 false)
+  ret i32 undef
+
+; CHECK: @moo2
+; CHECK: @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 64, i32 32, i1 false)
+; CHECK: ret i32 undef
+}
+
+declare void @llvm.invariant(i1) nounwind readnone
+
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind
+
+!0 = metadata !{metadata !"int", metadata !1}
+!1 = metadata !{metadata !"omnipotent char", metadata !2}
+!2 = metadata !{metadata !"Simple C/C++ TBAA"}
+

test/Transforms/Inline/ephemeral.ll

+; RUN: opt -S -Oz %s | FileCheck %s
+
+@a = global i32 4
+
+define i1 @inner() {
+  %a1 = load volatile i32* @a
+  %x1 = add i32 %a1, %a1
+  %c = icmp eq i32 %x1, 0
+
+  %a2 = mul i32 %a1, %a1
+  %a3 = sub i32 %a1, 5
+  %a4 = udiv i32 %a3, -13
+  %a5 = mul i32 %a4, %a4
+  %a6 = add i32 %a5, %x1
+  %ca = icmp sgt i32 %a6, -7
+  tail call void @llvm.invariant(i1 %ca)
+
+  ret i1 %c
+}
+
+; @inner() should be inlined for -Oz.
+; CHECK-NOT: call i1 @inner
+define i1 @outer() optsize {
+   %r = call i1 @inner()
+   ret i1 %r
+}
+
+declare void @llvm.invariant(i1) nounwind readnone
+