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 @@ -315,6 +315,7 @@ MPM.add(createTailCallEliminationPass()); // Eliminate tail calls MPM.add(createCFGSimplificationPass()); // Merge & remove BBs MPM.add(createReassociatePass()); // Reassociate expressions + MPM.add(createLiveRangeShrinkPass()); // Rotate Loop - disable header duplication at -Oz MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1)); MPM.add(createLICMPass()); // Hoist loop invariants 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 InstOrderMap; + int i = 0; + for (Instruction &I : BB) + InstOrderMap[&I] = i++; + + Instruction *Next = BB.getFirstNonPHI(); + for (Instruction *I = Next; !isa(I); I = Next) { + Next = I->getNextNode(); + if (!isa(I) && !isa(I) && !isa(I) && + !isa(I) && !isa(I) && + !isa(I) && !isa(I) && + !isa(I) && !isa(I) && + !isa(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(V)) + if (Inst->getParent() == &BB && + (Insert == nullptr || InstOrderMap[Inst] > InstOrderMap[Insert])) + Insert = Inst; + } + if (Insert == nullptr) + continue; + do { + Insert = Insert->getNextNode(); + } while (isa(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 +}