<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Dec 24, 2013 at 8:37 PM, William Moses <span dir="ltr"><<a href="mailto:moses.williamsteven@gmail.com" target="_blank">moses.williamsteven@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">All,<br><br>Recently, while developing a language based on LLVM (<a href="https://github.com/taekwonbilly/optricks" target="_blank">https://github.com/taekwonbilly/optricks</a>), I began to create a framework for function-local variables that may be useful to others.<div>
<br></div><div>A function-local variable is simply a value stored on the stack (and created by the llvm alloc instruction). When one wants to update it, one simply can use the store instruction, and when one wants to determine its value, one would use the load instruction.<br>
<br>However, when one uses a series of load and store instructions, some store instructions may not have any effect and some load instructions may be unnecessarily recalculating values. I propose that additional functionality be added to the llvm:IRBuilder class that can solve this problem without need for an optimization pass.</div>
<div><br></div><div>While there exist passes at a later stage that take care of this problem, they spent significant time attempting to determine when this optimization applies.</div></div></blockquote><div><br></div><div>
Can you supply some test cases and measurements (please include the raw data as well) that exhibit the performance issue as compared to the approach you propose?</div><div><br></div><div>Is this purely a performance optimization?</div>
<div><br></div><div>One thing to take into consideration is that the passes that form SSA from these alloca/load/store patterns are function passes and with the new PassManager and other upcoming changes, these transformations can be parallelized at function granularity without any extra work from the frontend. The approach you suggest puts the work of forming SSA into the path of creating the IR for functions, which would require the frontend's IR generation to be parallelized in order to gain performance from parallelism.</div>
<div><br></div><div>On the other hand, if the approach you suggest can be implemented in such a way that it avoids creating so many alloca/load/store instructions in the first place (operating on the already-in-cache function that is being constructed), there may be a potentially large memory bandwidth win which results in a potentially large net speedup.</div>
<div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div> Additionally, doing this when the IR is generated allows for more optimizations to be done during this stage (instead of generating the instructions and then deleting or modifying them).</div>
<div><br></div><div>The current way that I have designed the code involves a with a similar form to below.</div><div><br></div><div>struct Variable {<br>Value* pointerToMemory;<br>std::map<BasicBlock*,Value*> mostRecentValue;<br>
} <br><br>The variable pointerToMemory simply holds the actual pointer to the data. The map mostRecentVaue stores a cache of the most recent value loaded from memory in that block. If the mapped value for a block is NULL, the current value is assumed to have been modified by some external process (e.g. as an argument another function) and must be loaded the next time it is required.<br>
<br>Likewise, five functions should be added to IRBuilder that allow for the use of these variables.</div><div><br></div><div>The first function,<br>Variable* createVariable(Value* pointer)<br>will create the variable with the provided pointer to the memory.<br>
<br></div><div>The second function,<br>Value* getValue(Variable* var)<br>will return a Value* representing the contents of the variable at the end of the current BasicBlock.<br><br>It will be implemented as follows:<br>check if the current block is in the map (cache) and is non-null, and if so return it.<br>
check if the current block is in the map and is null, and if so update the cache with a load instruction, then return that load instruction<br>create a blank phi-node, update the cache to map this block to the phi node, then return the phi node<br>
<br>The phi-node acts as a placeholder and will be updated when the no more IR will be added to the function.<br><br>The third function,<br>void setValue(Variable* var, Value* newVal)<br>will update the contents of the variable var at the end of the current BasicBlock.<br>
<br>This is implemented by simply setting the map's value at the current BasicBlock to be newVal.<br><br>Setting the variable to a value of NULL using this method is considered invalid.<br><br>The fourth function,<br>
void updatePointer()<br>will flush all updates to the pointer so that it can be used in an external process.<br><br>Specifically, this will involve storing the current value of the map if it is non-null, and setting the map at the current BasicBlock to be null to indicate that the variable must be loaded from memory the next time it is used.<br>
<br>The final function,<br>void finalizeVariablesInCurrentFunction()<br>would clean up all of the PHINodes created for variables in this function.</div><div><br></div><div>For each PHINode, this method would retrieve the cached value of each BasicBlock predecessor (which represents the last value in that block) and use that as a predecessor for the PHINode.<br>
<br>If there is only one predecessor or all the cached values of predecessors are the same, the method should run replaceAllUsesWith on the PHINode with the unique value.<br><br>This replacement should then be coupled with basic optimizations such as folding the addition of two constants.<br>
<br>Overall, I believe that this addition will be very useful to those who use LLVM for reasons of both performance and additional functionality.<br><br>The preliminary (although terribly messy) implementation of this can be found here (<a href="https://github.com/taekwonbilly/optricks/blob/075fa3c2c89c97c010783a5d91f4a57afc63dfb3/Optricks/containers/settings.hpp" target="_blank">https://github.com/taekwonbilly/optricks/blob/075fa3c2c89c97c010783a5d91f4a57afc63dfb3/Optricks/containers/settings.hpp</a>) and is called "LazyLocation"<br>
<br>Even if this is not added to the main LLVM source, I would appreciate any comments about it.<br><br>Thanks,<br>Billy Moses<br><br></div></div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br></div></div>