Index: include/llvm/InitializePasses.h
===================================================================
--- include/llvm/InitializePasses.h
+++ include/llvm/InitializePasses.h
@@ -186,6 +186,7 @@
void initializeLiveDebugValuesPass(PassRegistry&);
void initializeLiveDebugVariablesPass(PassRegistry&);
void initializeLiveIntervalsPass(PassRegistry&);
+void initializeLiveRangeShrinkLegacyPassPass(PassRegistry&);
void initializeLiveRegMatrixPass(PassRegistry&);
void initializeLiveStacksPass(PassRegistry&);
void initializeLiveVariablesPass(PassRegistry&);
Index: include/llvm/LinkAllPasses.h
===================================================================
--- include/llvm/LinkAllPasses.h
+++ include/llvm/LinkAllPasses.h
@@ -114,6 +114,7 @@
(void) llvm::createInternalizePass();
(void) llvm::createLCSSAPass();
(void) llvm::createLICMPass();
+ (void) llvm::createLiveRangeShrinkPass();
(void) llvm::createLoopSinkPass();
(void) llvm::createLazyValueInfoPass();
(void) llvm::createLoopExtractorPass();
Index: include/llvm/Transforms/Scalar.h
===================================================================
--- include/llvm/Transforms/Scalar.h
+++ include/llvm/Transforms/Scalar.h
@@ -134,6 +134,13 @@
//===----------------------------------------------------------------------===//
//
+// LiveRangeShrink - This pass moves the instruction near the def of its
+// operands inside the basic block to shrink live range.
+//
+BasicBlockPass *createLiveRangeShrinkPass();
+
+//===----------------------------------------------------------------------===//
+//
// LICM - This pass is a loop invariant code motion and memory promotion pass.
//
Pass *createLICMPass();
Index: lib/Transforms/IPO/PassManagerBuilder.cpp
===================================================================
--- lib/Transforms/IPO/PassManagerBuilder.cpp
+++ lib/Transforms/IPO/PassManagerBuilder.cpp
@@ -673,6 +673,8 @@
if (MergeFunctions)
MPM.add(createMergeFunctionsPass());
+ MPM.add(createLiveRangeShrinkPass());
+
// LoopSink pass sinks instructions hoisted by LICM, which serves as a
// canonicalization pass that enables other optimizations. As a result,
// LoopSink pass needs to be a very late IR pass to avoid undoing LICM
Index: lib/Transforms/Scalar/CMakeLists.txt
===================================================================
--- lib/Transforms/Scalar/CMakeLists.txt
+++ lib/Transforms/Scalar/CMakeLists.txt
@@ -19,6 +19,7 @@
InferAddressSpaces.cpp
JumpThreading.cpp
LICM.cpp
+ LiveRangeShrink.cpp
LoopAccessAnalysisPrinter.cpp
LoopSink.cpp
LoadCombine.cpp
Index: lib/Transforms/Scalar/LiveRangeShrink.cpp
===================================================================
--- /dev/null
+++ lib/Transforms/Scalar/LiveRangeShrink.cpp
@@ -0,0 +1,93 @@
+//===- LiveRangeShrink.cpp - Shrink life range within BB ------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass moves instructions close to the definition of its operands to
+// shrink live range of the def instruction.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/Scalar.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "lrshrink"
+
+namespace {
+void ShrinkLifeRange(BasicBlock &BB) {
+ DenseMap<Instruction *, int> InstOrderMap;
+ int i = 0;
+ for (Instruction &I : BB)
+ InstOrderMap[&I] = i++;
+
+ Instruction *Next = BB.getFirstNonPHI();
+ for (Instruction *I = Next; !isa<TerminatorInst>(I); I = Next) {
+ Next = I->getNextNode();
+ if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) &&
+ !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) &&
+ !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) &&
+ !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) &&
+ !isa<InsertValueInst>(I))
+ continue;
+ if (I->getNumUses() > 1)
+ continue;
+ Instruction *Insert = nullptr;
+ for (Value *V : I->operands()) {
+ if (!V->hasOneUse()) {
+ Insert = nullptr;
+ break;
+ }
+ if (Instruction *Inst = dyn_cast<Instruction>(V))
+ if (Inst->getParent() == &BB &&
+ (Insert == nullptr || InstOrderMap[Inst] > InstOrderMap[Insert]))
+ Insert = Inst;
+ }
+ if (Insert == nullptr)
+ continue;
+ do {
+ Insert = Insert->getNextNode();
+ } while (isa<PHINode>(Insert));
+ if (Insert != I) {
+ InstOrderMap[I] = InstOrderMap[Insert];
+ for (Instruction *U = Insert; U != I; U = U->getNextNode())
+ InstOrderMap[U]++;
+ I->moveBefore(Insert);
+ }
+ }
+}
+
+class LiveRangeShrinkLegacyPass : public BasicBlockPass {
+public:
+ static char ID; // Pass identification, replacement for typeid
+ LiveRangeShrinkLegacyPass() : BasicBlockPass(ID) {
+ initializeLiveRangeShrinkLegacyPassPass(*PassRegistry::getPassRegistry());
+ }
+
+ bool runOnBasicBlock(BasicBlock &BB) override {
+ if (skipBasicBlock(BB))
+ return false;
+
+ ShrinkLifeRange(BB);
+ return false;
+ }
+
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.setPreservesCFG();
+ }
+};
+} // namespace
+
+char LiveRangeShrinkLegacyPass::ID = 0;
+INITIALIZE_PASS(LiveRangeShrinkLegacyPass, "lrshrink", "Live Range Shrinking",
+ false, false)
+
+BasicBlockPass *llvm::createLiveRangeShrinkPass() {
+ return new LiveRangeShrinkLegacyPass();
+}
Index: lib/Transforms/Scalar/Scalar.cpp
===================================================================
--- lib/Transforms/Scalar/Scalar.cpp
+++ lib/Transforms/Scalar/Scalar.cpp
@@ -54,6 +54,7 @@
initializeJumpThreadingPass(Registry);
initializeLegacyLICMPassPass(Registry);
initializeLegacyLoopSinkPassPass(Registry);
+ initializeLiveRangeShrinkLegacyPassPass(Registry);
initializeLoopDataPrefetchLegacyPassPass(Registry);
initializeLoopDeletionLegacyPassPass(Registry);
initializeLoopAccessLegacyAnalysisPass(Registry);
@@ -154,6 +155,10 @@
unwrap(PM)->add(createJumpThreadingPass());
}
+void LLVMAddLiveRangeShrinkPass(LLVMPassManagerRef PM) {
+ unwrap(PM)->add(createLiveRangeShrinkPass());
+}
+
void LLVMAddLoopSinkPass(LLVMPassManagerRef PM) {
unwrap(PM)->add(createLoopSinkPass());
}
Index: test/Transforms/Reassociate/hoist.ll
===================================================================
--- /dev/null
+++ test/Transforms/Reassociate/hoist.ll
@@ -0,0 +1,92 @@
+; RUN: opt < %s -reassociate -lrshrink -S | FileCheck %s
+
+declare i32 @foo()
+declare void @bar(i64)
+
+; The add should stay close of its operand def.
+;CHECK-LABEL: @test1
+;CHECK: call
+;CHECK: call
+;CHECK: add
+;CHECK: call
+;CHECK: add
+define i64 @test1() {
+ %1 = call i32 @foo()
+ %2 = zext i32 %1 to i64
+ %3 = mul i64 4, %2
+ %4 = add i64 0, %3
+ %5 = call i32 @foo()
+ %6 = zext i32 %5 to i64
+ %7 = mul i64 4, %6
+ %8 = add i64 %4, %7
+ %9 = call i32 @foo()
+ %10 = zext i32 %9 to i64
+ %11 = mul i64 4, %10
+ %12 = add i64 %8, %11
+ ret i64 %12
+}
+
+; There are 2 uses of %2, thus the add will not be hoisted.
+;CHECK-LABEL: @test1_nohoist
+;CHECK: call
+;CHECK: call
+;CHECK: call
+;CHECK: add
+;CHECK: add
+define i64 @test1_nohoist() {
+ %1 = call i32 @foo()
+ %2 = zext i32 %1 to i64
+ %3 = mul i64 4, %2
+ %4 = add i64 0, %3
+ %5 = call i32 @foo()
+ %6 = zext i32 %5 to i64
+ %7 = mul i64 4, %6
+ %8 = add i64 %4, %7
+ %9 = call i32 @foo()
+ %10 = zext i32 %9 to i64
+ %11 = mul i64 4, %10
+ %12 = add i64 %8, %11
+ call void @bar(i64 %2)
+ ret i64 %12
+}
+
+; The add should stay close of its operand def.
+;CHECK-LABEL: @test2
+;CHECK: call
+;CHECK: call
+;CHECK: add
+;CHECK: call
+;CHECK: add
+define i64 @test2() {
+ %1 = call i32 @foo()
+ %2 = zext i32 %1 to i64
+ %3 = add i64 0, %2
+ %4 = call i32 @foo()
+ %5 = zext i32 %4 to i64
+ %6 = add i64 %3, %5
+ %7 = call i32 @foo()
+ %8 = zext i32 %7 to i64
+ %9 = add i64 %6, %8
+ ret i64 %9
+}
+
+; There are 2 uses of %2, thus the add will not be hoisted.
+;CHECK-LABEL: @test2_nohoist
+;CHECK: call
+;CHECK: call
+;CHECK: call
+;CHECK: add
+;CHECK: add
+define i64 @test2_nohoist() {
+ %1 = call i32 @foo()
+ %2 = zext i32 %1 to i64
+ %3 = add i64 0, %2
+ %4 = call i32 @foo()
+ %5 = zext i32 %4 to i64
+ %6 = add i64 %3, %5
+ %7 = call i32 @foo()
+ %8 = zext i32 %7 to i64
+ %9 = add i64 %6, %8
+ call void @bar(i64 %2)
+ ret i64 %9
+}