From 338cd6ba6e36c291185541bb8e391427f57a32b1 Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Fri, 2 Jan 2009 11:54:37 +0000 Subject: [PATCH] When calculating 'nocapture' argument attributes, allow the argument to be stored to an alloca by tracking uses of the alloca. This occurs 4 times (out of 7121, 0.05%) in MultiSource/Applications, so may not be worth it. On the other hand, it is easy to do and fairly cheap. The functions it helps are: W_addcom and W_addlit in spiff; process_args (argv) in d (make_dparser); ercPixConcealIMB in JM/ldecod. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61570 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/IPO/FunctionAttrs.cpp | 81 ++++++++++++++----- .../FunctionAttrs/2009-01-02-LocalStores.ll | 23 ++++++ 2 files changed, 83 insertions(+), 21 deletions(-) create mode 100644 test/Transforms/FunctionAttrs/2009-01-02-LocalStores.ll diff --git a/lib/Transforms/IPO/FunctionAttrs.cpp b/lib/Transforms/IPO/FunctionAttrs.cpp index df881fac92b..13fb75619d4 100644 --- a/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/lib/Transforms/IPO/FunctionAttrs.cpp @@ -24,7 +24,8 @@ #include "llvm/GlobalVariable.h" #include "llvm/Instructions.h" #include "llvm/Analysis/CallGraph.h" -#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/InstIterator.h" @@ -182,30 +183,51 @@ bool FunctionAttrs::AddReadAttrs(const std::vector &SCC) { /// isCaptured - Return true if this pointer value may be captured. bool FunctionAttrs::isCaptured(Function &F, Value *V) { - SmallVector Worklist; - SmallPtrSet Visited; + typedef PointerIntPair UseWithDepth; + SmallVector Worklist; + SmallSet Visited; for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; ++UI) { - Use *U = &UI.getUse(); - Visited.insert(U); - Worklist.push_back(U); + UseWithDepth UD(&UI.getUse(), 0); + Visited.insert(UD); + Worklist.push_back(UD); } while (!Worklist.empty()) { - Use *U = Worklist.pop_back_val(); + UseWithDepth UD = Worklist.pop_back_val(); + Use *U = UD.getPointer(); Instruction *I = cast(U->getUser()); V = U->get(); - - if (isa(I)) { - // Loading a pointer does not cause it to be captured. Note that the - // loaded value might be the pointer itself (think of self-referential - // objects), but that's ok as long as it's not this function that stored - // the pointer there. - } else if (isa(I)) { - if (V == I->getOperand(0)) - // Stored the pointer - it is captured. TODO: improve this. - return true; + // The depth represents the number of loads that need to be performed to + // get back the original pointer (or a bitcast etc of it). For example, + // if the pointer is stored to an alloca, then all uses of the alloca get + // depth 1: if the alloca is loaded then you get the original pointer back. + // If a load of the alloca is returned then the pointer has been captured. + // The depth is needed in order to know which loads dereference the original + // pointer (these do not capture), and which return a value which needs to + // be tracked because if it is captured then so is the original pointer. + unsigned Depth = UD.getInt(); + + if (isa(I)) { + if (V == I->getOperand(0)) { + // Stored the pointer - it may be captured. If it is stored to a local + // object (alloca) then track that object. Otherwise give up. + Value *Target = I->getOperand(1)->getUnderlyingObject(); + if (!isa(Target)) + // Didn't store to an obviously local object - captured. + return true; + if (Depth >= 3) + // Alloca recursion too deep - give up. + return true; + // Analyze all uses of the alloca. + for (Value::use_iterator UI = Target->use_begin(), + UE = Target->use_end(); UI != UE; ++UI) { + UseWithDepth NUD(&UI.getUse(), Depth + 1); + if (Visited.insert(NUD)) + Worklist.push_back(NUD); + } + } // Storing to the pointee does not cause the pointer to be captured. } else if (isa(I)) { // Freeing a pointer does not cause it to be captured. @@ -230,14 +252,31 @@ bool FunctionAttrs::isCaptured(Function &F, Value *V) { return true; // Only passed via 'nocapture' arguments, or is the called function - not // captured. - } else if (isa(I) || isa(I) || + } else if (isa(I) || isa(I) || isa(I) || isa(I) || isa(I)) { + + // Usually loads can be ignored because they dereference the original + // pointer. However the loaded value needs to be tracked if loading + // from an object that the original pointer was stored to. + if (isa(I)) { + if (Depth == 0) + // Loading the original pointer or a variation of it. This does not + // cause the pointer to be captured. Note that the loaded value might + // be the pointer itself (think of self-referential objects), but that + // is fine as long as it's not this function that stored it there. + continue; + // Loading a pointer to (a pointer to...) the original pointer or a + // variation of it. Track uses of the loaded value, noting that one + // dereference was performed. + --Depth; + } + // The original value is not captured via this if the instruction isn't. for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; ++UI) { - Use *U = &UI.getUse(); - if (Visited.insert(U)) - Worklist.push_back(U); + UseWithDepth UD(&UI.getUse(), Depth); + if (Visited.insert(UD)) + Worklist.push_back(UD); } } else { // Something else - be conservative and say it is captured. diff --git a/test/Transforms/FunctionAttrs/2009-01-02-LocalStores.ll b/test/Transforms/FunctionAttrs/2009-01-02-LocalStores.ll new file mode 100644 index 00000000000..17b443980b7 --- /dev/null +++ b/test/Transforms/FunctionAttrs/2009-01-02-LocalStores.ll @@ -0,0 +1,23 @@ +; RUN: llvm-as < %s | opt -functionattrs | llvm-dis | not grep {nocapture *%%q} +; RUN: llvm-as < %s | opt -functionattrs | llvm-dis | grep {nocapture *%%p} + +@g = external global i32** + +define i32 @f(i32* %p, i32* %q) { + %a1 = alloca i32* + %a2 = alloca i32** + store i32* %p, i32** %a1 + store i32** %a1, i32*** %a2 + %reload1 = load i32*** %a2 + %reload2 = load i32** %reload1 + %load_p = load i32* %reload2 + store i32 0, i32* %reload2 + + %b1 = alloca i32* + %b2 = alloca i32** + store i32* %q, i32** %b1 + store i32** %b1, i32*** %b2 + %reload3 = load i32*** %b2 + store i32** %reload3, i32*** @g + ret i32 %load_p +} -- 2.34.1