Index: test/Transforms/ConstantExtractor/load-not-const-gep.ll =================================================================== --- test/Transforms/ConstantExtractor/load-not-const-gep.ll (revision 0) +++ test/Transforms/ConstantExtractor/load-not-const-gep.ll (revision 0) @@ -0,0 +1,24 @@ +; RUN: llvm-as < %s | opt -constextract | llvm-dis > %t +; RUN: cat %t | not grep alloca +; RUN: cat %t | not grep store +; RUN: cat %t | grep -F {@extracted_constant = internal constant \[5 x i32\] \[ i32 5, i32 4, i32 3, i32 2, i32 1 \]} | count 1 +; RUN: cat %t | grep getelementptr | count 1 + +define i32 @g(i32 %a) nounwind { +entry: + %v = alloca [5 x i32], align 4 ; <[5 x i32]*> [#uses=6] + %.array = getelementptr [5 x i32]* %v, i32 0, i32 0 ; [#uses=1] + store i32 5, i32* %.array + %.array1 = getelementptr [5 x i32]* %v, i32 0, i32 1 ; [#uses=1] + store i32 4, i32* %.array1 + %.array2 = getelementptr [5 x i32]* %v, i32 0, i32 2 ; [#uses=1] + store i32 3, i32* %.array2 + %.array3 = getelementptr [5 x i32]* %v, i32 0, i32 3 ; [#uses=1] + store i32 2, i32* %.array3 + %.array4 = getelementptr [5 x i32]* %v, i32 0, i32 4 ; [#uses=1] + store i32 1, i32* %.array4 + %arrayidx = getelementptr [5 x i32]* %v, i32 0, i32 %a ; [#uses=1] + %tmp5 = load i32* %arrayidx ; [#uses=1] + + ret i32 %tmp5 +} Index: test/Transforms/ConstantExtractor/load-const-gep.ll =================================================================== --- test/Transforms/ConstantExtractor/load-const-gep.ll (revision 0) +++ test/Transforms/ConstantExtractor/load-const-gep.ll (revision 0) @@ -0,0 +1,24 @@ +; RUN: llvm-as < %s | opt -constextract | llvm-dis > %t +; RUN: cat %t | not grep alloca +; RUN: cat %t | not grep store +; RUN: cat %t | grep -F {@extracted_constant = internal constant \[5 x i32\] \[ i32 1, i32 2, i32 3, i32 4, i32 5 \]} | count 1 +; RUN: cat %t | grep getelementptr | count 1 + +define i32 @f(...) nounwind { +entry: + %v = alloca [5 x i32], align 4 ; <[5 x i32]*> [#uses=6] + %.array = getelementptr [5 x i32]* %v, i32 0, i32 0 ; [#uses=1] + store i32 1, i32* %.array + %.array1 = getelementptr [5 x i32]* %v, i32 0, i32 1 ; [#uses=1] + store i32 2, i32* %.array1 + %.array2 = getelementptr [5 x i32]* %v, i32 0, i32 2 ; [#uses=1] + store i32 3, i32* %.array2 + %.array3 = getelementptr [5 x i32]* %v, i32 0, i32 3 ; [#uses=1] + store i32 4, i32* %.array3 + %.array4 = getelementptr [5 x i32]* %v, i32 0, i32 4 ; [#uses=1] + store i32 5, i32* %.array4 + %arrayidx= getelementptr [5 x i32]* %v, i32 0, i32 2 ; [#uses=1] + %tmp = load i32* %arrayidx ; [#uses=1] + + ret i32 %tmp +} Index: test/Transforms/ConstantExtractor/not-const-call.ll =================================================================== --- test/Transforms/ConstantExtractor/not-const-call.ll (revision 0) +++ test/Transforms/ConstantExtractor/not-const-call.ll (revision 0) @@ -0,0 +1,28 @@ +; RUN: llvm-as < %s | opt -constextract | llvm-dis > %t +; RUN: cat %t | grep alloca | count 1 +; RUN: cat %t | grep store | count 5 +; RUN: cat %t | not grep extracted_constant +; RUN: cat %t | grep getelementptr | count 6 + +define i32 @f(...) nounwind { +entry: + %v = alloca [5 x i32], align 4 ; <[5 x i32]*> [#uses=6] + %.array = getelementptr [5 x i32]* %v, i32 0, i32 0 ; [#uses=1] + store i32 1, i32* %.array + %.array1 = getelementptr [5 x i32]* %v, i32 0, i32 1 ; [#uses=1] + store i32 2, i32* %.array1 + %.array2 = getelementptr [5 x i32]* %v, i32 0, i32 2 ; [#uses=1] + store i32 3, i32* %.array2 + %.array3 = getelementptr [5 x i32]* %v, i32 0, i32 3 ; [#uses=1] + store i32 4, i32* %.array3 + %.array4 = getelementptr [5 x i32]* %v, i32 0, i32 4 ; [#uses=1] + store i32 5, i32* %.array4 + %arrayidx= getelementptr [5 x i32]* %v, i32 0, i32 2 ; [#uses=1] + %tmp = load i32* %arrayidx ; [#uses=1] + + call void @other(i32* %.array) + + ret i32 %tmp +} + +declare void @other(i32*) Index: test/Transforms/ConstantExtractor/dg.exp =================================================================== --- test/Transforms/ConstantExtractor/dg.exp (revision 0) +++ test/Transforms/ConstantExtractor/dg.exp (revision 0) @@ -0,0 +1,3 @@ +load_lib llvm.exp + +RunLLVMTests [lsort [glob -nocomplain $srcdir/$subdir/*.{ll,c,cpp}]] Index: test/Transforms/ConstantExtractor/const-call.ll =================================================================== --- test/Transforms/ConstantExtractor/const-call.ll (revision 0) +++ test/Transforms/ConstantExtractor/const-call.ll (revision 0) @@ -0,0 +1,27 @@ +; RUN: llvm-as < %s | opt -constextract | llvm-dis > %t +; RUN: cat %t | not grep alloca +; RUN: cat %t | not grep store +; RUN: cat %t | grep -F {@extracted_constant = internal constant \[5 x i32\] \[ i32 1, i32 2, i32 3, i32 4, i32 5 \]} | count 1 +; RUN: cat %t | grep getelementptr | count 2 + +define i32 @f(...) nounwind { +entry: + %v = alloca [5 x i32], align 4 ; <[5 x i32]*> [#uses=6] + %.array = getelementptr [5 x i32]* %v, i32 0, i32 0 ; [#uses=2] + store i32 1, i32* %.array + %.array1 = getelementptr [5 x i32]* %v, i32 0, i32 1 ; [#uses=1] + store i32 2, i32* %.array1 + %.array2 = getelementptr [5 x i32]* %v, i32 0, i32 2 ; [#uses=1] + store i32 3, i32* %.array2 + %.array3 = getelementptr [5 x i32]* %v, i32 0, i32 3 ; [#uses=2] + store i32 4, i32* %.array3 + %.array4 = getelementptr [5 x i32]* %v, i32 0, i32 4 ; [#uses=1] + store i32 5, i32* %.array4 + %tmp = load i32* %.array3 ; [#uses=1] + + call void @other(i32* %.array) + + ret i32 %tmp +} + +declare void @other(i32*) readnone Index: test/Transforms/ConstantExtractor/clang-const-gep.ll =================================================================== --- test/Transforms/ConstantExtractor/clang-const-gep.ll (revision 0) +++ test/Transforms/ConstantExtractor/clang-const-gep.ll (revision 0) @@ -0,0 +1,33 @@ +; RUN: llvm-as < %s | opt -constextract | llvm-dis > %t +; RUN: cat %t | grep alloca | count 2 +; RUN: cat %t | not grep -F {alloca \[} +; RUN: cat %t | grep store | count 2 +; RUN: cat %t | grep -F {@extracted_constant = internal constant \[5 x i32\] \[ i32 1, i32 2, i32 3, i32 0, i32 0 \]} | count 1 +; RUN: cat %t | grep getelementptr | count 1 + +define i32 @foo(i32 %a) nounwind { +entry: + %retval = alloca i32 ; [#uses=2] + %a.addr = alloca i32 ; [#uses=2] + %b = alloca [5 x i32], align 4 ; <[5 x i32]*> [#uses=6] + store i32 %a, i32* %a.addr + %.array = getelementptr [5 x i32]* %b, i32 0, i32 0 ; [#uses=1] + store i32 1, i32* %.array + %.array1 = getelementptr [5 x i32]* %b, i32 0, i32 1 ; [#uses=1] + store i32 2, i32* %.array1 + %.array2 = getelementptr [5 x i32]* %b, i32 0, i32 2 ; [#uses=1] + store i32 3, i32* %.array2 + %.array3 = getelementptr [5 x i32]* %b, i32 0, i32 3 ; [#uses=1] + store i32 0, i32* %.array3 + %.array4 = getelementptr [5 x i32]* %b, i32 0, i32 4 ; [#uses=1] + store i32 0, i32* %.array4 + %tmp = load i32* %a.addr ; [#uses=1] + %arrayidx = getelementptr [5 x i32]* %b, i32 0, i32 %tmp ; [#uses=1] + %tmp5 = load i32* %arrayidx ; [#uses=1] + store i32 %tmp5, i32* %retval + br label %return + +return: ; preds = %entry + %0 = load i32* %retval ; [#uses=1] + ret i32 %0 +} Index: test/Transforms/ConstantExtractor/recursive-phi-2.ll =================================================================== --- test/Transforms/ConstantExtractor/recursive-phi-2.ll (revision 0) +++ test/Transforms/ConstantExtractor/recursive-phi-2.ll (revision 0) @@ -0,0 +1,30 @@ +; RUN: llvm-as < %s | opt -constextract | llvm-dis > %t +; RUN: cat %t | grep alloca | count 1 +; RUN: cat %t | grep store | count 6 +; RUN: cat %t | grep getelementptr | count 6 +; RUN: cat %t | not grep extracted_constant + +define i32 @f(...) nounwind { +entry: + %b = alloca [5 x i32], align 4 ; <[5 x i32]*> [#uses=5] + %.array = getelementptr [5 x i32]* %b, i32 0, i32 0 ; [#uses=1] + store i32 1, i32* %.array + %.array1 = getelementptr [5 x i32]* %b, i32 0, i32 1 ; [#uses=1] + store i32 2, i32* %.array1 + %.array2 = getelementptr [5 x i32]* %b, i32 0, i32 2 ; [#uses=1] + store i32 3, i32* %.array2 + %.array3 = getelementptr [5 x i32]* %b, i32 0, i32 3 ; [#uses=1] + store i32 0, i32* %.array3 + %.array4 = getelementptr [5 x i32]* %b, i32 0, i32 4 ; [#uses=1] + store i32 0, i32* %.array4 + br label %bb1 + +bb1: + %phi1 = phi [5 x i32]* [ %b, %entry ], [ %phi2, %bb1 ] + %phi2 = phi [5 x i32]* [ %phi1, %bb1 ], [ null, %entry ] + %.array4.1 = getelementptr [5 x i32]* %b, i32 0, i32 4 ; [#uses=1] + store i32 1, i32* %.array4.1 + br i1 false, label %bb1, label %ret +ret: + ret i32 1 +} Index: test/Transforms/ConstantExtractor/not-const.ll =================================================================== --- test/Transforms/ConstantExtractor/not-const.ll (revision 0) +++ test/Transforms/ConstantExtractor/not-const.ll (revision 0) @@ -0,0 +1,24 @@ +; RUN: llvm-as < %s | opt -constextract | llvm-dis > %t +; RUN: cat %t | grep alloca | count 1 +; RUN: cat %t | grep store | count 5 +; RUN: cat %t | not grep extracted_constant +; RUN: cat %t | grep getelementptr | count 6 + +define i32 @f() nounwind { +entry: + %v = alloca [5 x i32], align 4 ; <[5 x i32]*> [#uses=6] + %.array = getelementptr [5 x i32]* %v, i32 0, i32 0 ; [#uses=1] + store i32 1, i32* %.array + %.array1 = getelementptr [5 x i32]* %v, i32 0, i32 1 ; [#uses=1] + store i32 2, i32* %.array1 + %.array2 = getelementptr [5 x i32]* %v, i32 0, i32 2 ; [#uses=1] + store i32 3, i32* %.array2 + %.array3 = getelementptr [5 x i32]* %v, i32 0, i32 1 ; [#uses=1] + store i32 4, i32* %.array3 + %.array4 = getelementptr [5 x i32]* %v, i32 0, i32 4 ; [#uses=1] + store i32 5, i32* %.array4 + %arrayidx= getelementptr [5 x i32]* %v, i32 0, i32 2 ; [#uses=1] + %tmp = load i32* %arrayidx ; [#uses=1] + + ret i32 %tmp +} Index: test/Transforms/ConstantExtractor/undef-vals.ll =================================================================== --- test/Transforms/ConstantExtractor/undef-vals.ll (revision 0) +++ test/Transforms/ConstantExtractor/undef-vals.ll (revision 0) @@ -0,0 +1,20 @@ +; RUN: llvm-as < %s | opt -constextract | llvm-dis > %t +; RUN: cat %t | not grep alloca +; RUN: cat %t | not grep store +; RUN: cat %t | grep -F {@extracted_constant = internal constant \[5 x i32\] \[ i32 1, i32 2, i32 undef, i32 undef, i32 5 \]} | count 1 +; RUN: cat %t | grep getelementptr | count 1 + +define i32 @f(...) nounwind { +entry: + %v = alloca [5 x i32], align 4 ; <[5 x i32]*> [#uses=6] + %.array = getelementptr [5 x i32]* %v, i32 0, i32 0 ; [#uses=1] + store i32 1, i32* %.array + %.array1 = getelementptr [5 x i32]* %v, i32 0, i32 1 ; [#uses=1] + store i32 2, i32* %.array1 + %.array4 = getelementptr [5 x i32]* %v, i32 0, i32 4 ; [#uses=1] + store i32 5, i32* %.array4 + %arrayidx= getelementptr [5 x i32]* %v, i32 0, i32 3 ; [#uses=1] + %tmp = load i32* %arrayidx ; [#uses=1] + + ret i32 %tmp +} Index: test/Transforms/ConstantExtractor/recursive-phi.ll =================================================================== --- test/Transforms/ConstantExtractor/recursive-phi.ll (revision 0) +++ test/Transforms/ConstantExtractor/recursive-phi.ll (revision 0) @@ -0,0 +1,28 @@ +; RUN: llvm-as < %s | opt -constextract | llvm-dis > %t +; RUN: cat %t | not grep alloca +; RUN: cat %t | not grep store +; RUN: cat %t | not grep getelementptr +; RUN: cat %t | grep -F {@extracted_constant = internal constant \[5 x i32\] \[ i32 1, i32 2, i32 3, i32 0, i32 0 \]} | count 1 + +define i32 @f(...) nounwind { +entry: + %b = alloca [5 x i32], align 4 ; <[5 x i32]*> [#uses=5] + %.array = getelementptr [5 x i32]* %b, i32 0, i32 0 ; [#uses=1] + store i32 1, i32* %.array + %.array1 = getelementptr [5 x i32]* %b, i32 0, i32 1 ; [#uses=1] + store i32 2, i32* %.array1 + %.array2 = getelementptr [5 x i32]* %b, i32 0, i32 2 ; [#uses=1] + store i32 3, i32* %.array2 + %.array3 = getelementptr [5 x i32]* %b, i32 0, i32 3 ; [#uses=1] + store i32 0, i32* %.array3 + %.array4 = getelementptr [5 x i32]* %b, i32 0, i32 4 ; [#uses=1] + store i32 0, i32* %.array4 + br label %bb1 + +bb1: + %phi1 = phi [5 x i32]* [ %b, %entry ], [ %phi2, %bb1 ] + %phi2 = phi [5 x i32]* [ %phi1, %bb1 ], [ null, %entry ] + br i1 false, label %bb1, label %ret +ret: + ret i32 1 +} Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h (revision 58329) +++ include/llvm/LinkAllPasses.h (working copy) @@ -55,6 +55,7 @@ (void) llvm::createBlockProfilerPass(); (void) llvm::createBreakCriticalEdgesPass(); (void) llvm::createCFGSimplificationPass(); + (void) llvm::createConstantExtractorPass(); (void) llvm::createConstantMergePass(); (void) llvm::createConstantPropagationPass(); (void) llvm::createDeadArgEliminationPass(); Index: include/llvm/Transforms/Scalar.h =================================================================== --- include/llvm/Transforms/Scalar.h (revision 58329) +++ include/llvm/Transforms/Scalar.h (working copy) @@ -26,6 +26,12 @@ //===----------------------------------------------------------------------===// // +// ConstantExtractor - Extracts (hidden) constants from the code +// +FunctionPass *createConstantExtractorPass(); + +//===----------------------------------------------------------------------===// +// // ConstantPropagation - A worklist driven constant propagation pass // FunctionPass *createConstantPropagationPass(); Index: lib/Transforms/Scalar/ConstantExtractor.cpp =================================================================== --- lib/Transforms/Scalar/ConstantExtractor.cpp (revision 0) +++ lib/Transforms/Scalar/ConstantExtractor.cpp (revision 0) @@ -0,0 +1,205 @@ +//===-------- ConstantExtractor.cpp - Extracts (hidden) constants ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass extracts (hidden) constants from the code. It transforms alloca'ted +// vectors that are only written once to internal constant GVs. +// +// example code in C that gets optimized (bar is extracted): +// int foo(int a) { +// int bar[] = {1,2,3,0,0}; +// return bar[a]; +// } +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "constextract" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Instructions.h" +#include "llvm/GlobalVariable.h" +#include "llvm/Constants.h" +#include "llvm/Pass.h" +#include "llvm/Function.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Support/Compiler.h" +#include +#include +#include +using namespace llvm; + +STATISTIC(NumExtractedConstants, "Number of extracted constants"); + +namespace { + +/// @brief Pass to extract constants from the code. +class VISIBILITY_HIDDEN ConstantExtractorPass : public FunctionPass { +public: + static char ID; // Pass identification, replacement for typeid + ConstantExtractorPass() : FunctionPass(&ID) { } + bool runOnFunction(Function& F); +}; + +} // end anonymous namespace + +char ConstantExtractorPass::ID = 0; +static RegisterPass +X("constextract", "Extract (hidden) constants"); + +typedef SmallPtrSet PHISet; + +// check if the given user may write to our target constant +static bool MayWriteMemory(User *U, Function& F, PHISet &guard) { + if (CallInst *CI = dyn_cast(U)) { + Function *CF = CI->getCalledFunction(); + return !CF || !CF->onlyReadsMemory(); + + } else if (isa(U) || + isa(U) || + isa(U)) { + return false; + + } else if (PHINode *phi = dyn_cast(U)) { + if (guard.count(phi)) + return false; + + guard.insert(phi); + + for (Value::use_iterator I = U->use_begin(), E = U->use_end(); I != E; ++I) { + if (MayWriteMemory(*I, F, guard)) + return true; + } + + guard.erase(phi); + return false; + + } else if (isa(U) || + isa(U) || + isa(U)) { + for (Value::use_iterator I = U->use_begin(), E = U->use_end(); I != E; ++I) { + if (MayWriteMemory(*I, F, guard)) + return true; + } + + return false; + + } else if (isa(U) || + isa(U)) { + return true; + + } else { + if (Instruction *I = dyn_cast(U)) + fprintf(stderr, "unhandled user: '%s' (%s)\n", I->getOpcodeName(), F.getName().c_str()); + else + fprintf(stderr, "unhandled user type: %u (%s::%s)\n", U->getValueID(), F.getName().c_str(), U->getName().c_str()); + return true; + } +} + + +static void HandleAlloca(AllocaInst *A, Function& F, std::stack& GlobalInstsToRemove) { + const ArrayType *AT = dyn_cast(A->getAllocatedType()); + if (!AT) + return; + + uint64_t size = AT->getNumElements(); + + UndefValue *UF = UndefValue::get(AT->getElementType()); + std::vector vec(size, UF); + BitVector written(size); + + std::stack InstsToRemove; + PHISet guard; + + for (Value::use_iterator I = A->use_begin(), E = A->use_end(); I != E; ++I) { + if (GetElementPtrInst *GEP = dyn_cast(I)) { + if (GEP->getNumIndices() != 2) + return; + + ConstantInt *CIindex = dyn_cast(GEP->getOperand(1)); + if (!CIindex || CIindex->getZExtValue() != 0) + return; + + CIindex = dyn_cast(GEP->getOperand(2)); + + for (Value::use_iterator I = GEP->use_begin(), E = GEP->use_end(); I != E; ++I) { + if (StoreInst *SI = dyn_cast(I)) { + if (!CIindex) + return; + uint64_t index = CIindex->getZExtValue(); + + if (written[index]) + return; + + Constant *C = dyn_cast(SI->getOperand(0)); + if (!C) + return; + + written[index] = 1; + vec[index] = C; + + InstsToRemove.push(SI); + if (GEP->hasNUses(1)) // GEP is only used by the store + InstsToRemove.push(GEP); + + } else if (MayWriteMemory(*I, F, guard)) { + return; + } + } + } else if (MayWriteMemory(*I, F, guard)) { + return; + } + } + + // Transform: Create static vector and remove Stores + GlobalVariable *var = new GlobalVariable(AT, true, + GlobalValue::InternalLinkage, + ConstantArray::get(AT, vec), + "extracted_constant", + F.getParent()); + A->replaceAllUsesWith(var); + GlobalInstsToRemove.push(A); + + // ok now we are sure that the opt is safe. copy the dead insts list + while (!InstsToRemove.empty()) { + GlobalInstsToRemove.push(InstsToRemove.top()); + InstsToRemove.pop(); + } + + ++NumExtractedConstants; +} + + +bool ConstantExtractorPass::runOnFunction(Function& F) { + BasicBlock &BB = F.getEntryBlock(); + std::stack InstructionsToRemove; + + // NOTE: we scan only for allocas in the first block + for (BasicBlock::iterator it = BB.begin(), end = BB.end(); it != end; ++it) { + if (AllocaInst *A = dyn_cast(it)) + HandleAlloca(A, F, InstructionsToRemove); + } + + // there will be at least an alloca inst in the list + // if the code was modified + if (InstructionsToRemove.empty()) + return false; + + // Remove stores plus new dead instructions + do { + InstructionsToRemove.top()->eraseFromParent(); + InstructionsToRemove.pop(); + } while (!InstructionsToRemove.empty()); + + return true; +} + +FunctionPass *llvm::createConstantExtractorPass() { + return new ConstantExtractorPass(); +}