<div dir="ltr">Hello everyone,<div><br>I have been thinking about implementing a fence elimination algorithm based on PRE over the last few weeks.  It will operate on target-dependent fences (as there are very few target-independent fence elimination opportunities), but should be general enough to be used by both the ARM and the Power backends just by tweaking some simple hooks. In this email I will try to summarize my ideas about it, to get some feedback before I start implementing. If you have any question/suggestion/comment/criticism, please say so !<br><br><font color="#ff0000"><b>TL;DR:</b></font> I have a handful of questions:<br>- Should I try to make the code general enough to be used for full PRE later, or only care about fences ?<br>- Is it ok to use metadata to preserve information that would otherwise be lost by a transformation pass (and would help a later pass) ?<br>- If you have read the text below, does the approach make sense ?</div><div><br></div><div>Thank you,</div><div>Robin Morisset</div><div><span id="docs-internal-guid-6b981587-66de-377a-fa95-6ee13db01f78"><h1 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:21px;font-family:'Trebuchet MS';color:rgb(0,0,0);font-weight:normal;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Fence elimination algorithm</span></h1><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Background, link to Partial Redundancy Elimination</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">There is already a local fence elimination algorithm for ARM (lib/Target/ARM/ARMOptimizeBarriersPass.cpp), that tries to find pairs of dmb with no memory access in between and eliminate one of the two (</span><a href="http://llvm.org/devmtg/2014-04/PDFs/Talks/Reinoud-report.pdf" style="text-decoration:none"><span style="font-size:15px;font-family:Arial;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">report describing the idea/results</span></a><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">). The goal here is to do better, in particular to hoist fences out of loops and do optimization across basic blocks.</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">This is closely related to </span><a href="http://en.wikipedia.org/wiki/Partial_redundancy_elimination" style="text-decoration:none"><span style="font-size:15px;font-family:Arial;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">PRE</span></a><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">: we want a dmb on every path between some accesses and some other accesses, PRE places a computation on every path between the definition of its operand and the uses of its results. Sadly, only an extremely limited form of PRE is done in LLVM, inside a sub-phase of the GVN pass, so we cannot reuse existing infrastructure.</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Most modern papers on PRE see it as a flow problem: if all the operands are connected to a source and all the uses of the computation are connected to a sink, then the goal is to find a cut of the graph between the source and the sink that verifies an additional property.</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">For classical PRE (i.e. conservative, static), the extra property is that no path through the CFG goes through more instances of the computation than before. For speculative PRE (SPRE), it is that the cut is a min-cut, when all edges in the CFG are annotated with their frequency (which requires profiling-based information in general). The same distinction can be made in our case: using profiling-based information allows more aggressive optimization but with a risk of mis-optimization if the information is wrong.</span></p><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Different levels of fences</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Quite often, there will be different kinds of fences to deal with, such as dmb ish/dmb ishst on swift ARM processors, or hwsync/lwsync on Power. I suggest a rather greedy approach: first insert the strongest fences without looking at the weaker ones; then insert the weaker ones while taking into account the stronger ones. If two fences are uncomparable, then insert each one independently, completely ignoring the other. The cost of this approach is having to do a cut for each kind of fences. However, I don’t expect the graphs under consideration to often be big.</span></p><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Building the graph</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">The graph on which we will compute the cut is based on the CFG, but there are several possible ways to tweak it, mostly to accelerate the algorithm:</span></p><ul style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">By default, there would be two nodes for each instruction (beginning and end), with an infinite weight on them (impossible to insert a Fence in the middle of an instruction), and an edge between the end of an instruction and the beginning of the next. We cannot use just one node per instruction, because the beginning of an instruction may be a sink, while its end is a source.</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">We can merge together all the instructions in a basic block which are not memory accesses (since fences commute with those anyway) and do not affect control-flow.</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">We can put an infinite weight on edges between basic blocks (fences must be inside BBs in this case) or not (we must then do edge-splitting to insert fences there)</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">The cut algorithm cost is only incurred on code with fences, and any part of the graph which is unreachable from the source or co-unreachable from the sink can be pruned (or not even built).</span></p></li></ul><h3 dir="ltr" style="line-height:1.15;margin-top:8pt;margin-bottom:0pt"><span style="font-size:16px;font-family:'Trebuchet MS';color:rgb(102,102,102);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Basic algorithm</span></h3><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">The basic algorithm I propose is thus the following:</span></p><ol style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:decimal;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Gather all Fences</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">For each Fence:</span></p></li><ol style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:decimal;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">On every path going down from the Fence, find the first memory access/return/call, and connect the beginning of this instruction to the sink (with infinite weight). If instead we first reach a stronger Fence, then do nothing for that path (do not connect it to the sink).</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">On every path going up from the Fence, find the first memory access/call/beginning of function, and connect the source to its end (with infinite weight). If instead we first reach a stronger Fence, then do nothing for that path.</span></p></li><li dir="ltr" style="list-style-type:decimal;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Remove the Fence</span></p></li></ol><li dir="ltr" style="list-style-type:decimal;font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;background-color:transparent"><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Execute the cut algorithm on this graph (only keeping the nodes/edges traversed above, merging all adjacent nodes that are not branches or memory accesses/call/return), and insert a Fence on every edge that is part of the cut.</span></p></li></ol><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">It is fairly obvious that this algorithm preserves the property that every pair of memory accesses that was separated by a fence still is (and of the same kind since we are operating only on fences of the same kind at a time).</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">In terms of implementation, the steps 1 & 2.1 & 2.2 could be one analysis pass, and 2.3 & 3 could be a transform pass depending on it.</span></p><h3 dir="ltr" style="line-height:1.15;margin-top:8pt;margin-bottom:0pt"><span style="font-size:16px;font-family:'Trebuchet MS';color:rgb(102,102,102);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Improvements</span></h3><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">A nice property of this framework is that it can easily be expanded to allow more optimizations. Here are some examples that may be added incrementally later.</span></p><h4 dir="ltr" style="line-height:1.15;margin-top:8pt;margin-bottom:0pt"><span style="font-size:15px;font-family:'Trebuchet MS';color:rgb(102,102,102);font-weight:normal;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Merging barriers coming from the same location</span></h4><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Accesses to the same location are automatically ordered on any reasonable architecture, so we do not need fences to order them. So when looking upwards from the fence introduced by a release, or downwards from the fence introduced by an acquire, we can skip any access to the same location (with the same size obviously). This may sound rare, but in practice it is crucial to hoisting fences out of loops. Consider for example the following code (which can be found any time a thread spins waiting on another one):</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt;margin-left:36pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">while (true)</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt;margin-left:72pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">if (x.load(acquire)) break;</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Without this optimization, there must be a Fence after every load, whereas after it there can be a single Fence after the loop. The only difficulty here is finding from what access (if any) a fence comes from.. see next part of this doc for ides on how to do that.</span></p><h4 dir="ltr" style="line-height:1.15;margin-top:8pt;margin-bottom:0pt"><span style="font-size:15px;font-family:'Trebuchet MS';color:rgb(102,102,102);font-weight:normal;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Making the optimization interprocedural</span></h4><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">It is fairly simple to make the pass partially (greedily) interprocedural for free: operate on the functions bottom-up, whenever a Fence is inserted just after the start of a function (resp. just before every return), tag this function with some special piece of metadata. Then whenever hitting a call to such a function when searching downwards (resp upwards) of a Fence, stop the search without connecting to the sink (resp source).</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">This is not necessarily optimal (as we cannot push a Fence through a function for example), but it is free and may only improve things (get rid of some Fences).</span></p><h4 dir="ltr" style="line-height:1.15;margin-top:8pt;margin-bottom:0pt"><span style="font-size:15px;font-family:'Trebuchet MS';color:rgb(102,102,102);font-weight:normal;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Turning acquire into consume</span></h4><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Neither Power nor ARM can reorder two memory accesses, if the first is a read, and the second has a data or address dependency on the first. This means that when searching memory accesses downward of a Fence fence inserted by an acquire read, we can skip any access that depends on that acquire read.</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">This would for example allow optimizing the following:</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt;margin-left:36pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">tmp = x.load(acquire);</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt;margin-left:36pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">tmp2 = (*tmp).load(acquire);</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt;margin-left:36pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">return tmp2;</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Which by default would require two Fences (after each load). Because the second load depends on the first, only the second Fence is required (in the algorithm, the source would be connected to the ends of both loads, but only the return would be connected to the sink).</span></p><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">In practice, this optimization might be extremely difficult to implement because of phase ordering issues: no later pass can be allowed to eliminate dependencies, which requires running extremely late (in the backend) at which point iterating over the control-flow is painful. So I think this optimization probably won’t be implemented (soon) despite its potential benefits.</span></p><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Cut algorithm</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">I have seen at least 4 broad categories of algorithms for computing such a cut.</span></p><h3 dir="ltr" style="line-height:1.15;margin-top:8pt;margin-bottom:0pt"><span style="font-size:16px;font-family:'Trebuchet MS';color:rgb(102,102,102);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Encoded as a dataflow problem with bitvectors</span></h3><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">This has two main benefits: extremely adaptable (for example can enforce the conservativeness requirement of classical PRE, or various other constraints in the literature), and can do up to 64 cuts in parallel (highly useful for PRE as it must do a cut for each expression, useless for us). This is what is used in most papers on PRE (most of which are about clever/unreadable ways of doing that encoding) but I think it would only make sense for us if we want to reuse the infrastructure to provide general-purpose PRE.</span></p><h3 dir="ltr" style="line-height:1.15;margin-top:8pt;margin-bottom:0pt"><span style="font-size:16px;font-family:'Trebuchet MS';color:rgb(102,102,102);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Boykov-Kolmogorov algorithm</span></h3><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Specially tuned for computer vision problems, with perfectly regular planar graphs with some special structure: probably useless for us (although easy to test as it is implemented in </span><a href="http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/boykov_kolmogorov_max_flow.html" style="text-decoration:none"><span style="font-size:15px;font-family:Arial;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">boost</span></a><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">).</span></p><h3 dir="ltr" style="line-height:1.15;margin-top:8pt;margin-bottom:0pt"><span style="font-size:16px;font-family:'Trebuchet MS';color:rgb(102,102,102);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Edmond-Karps algorithm</span></h3><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Probably too slow, but easy to test (</span><a href="http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/edmonds_karp_max_flow.html" style="text-decoration:none"><span style="font-size:15px;font-family:Arial;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">boost</span></a><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">).</span></p><h3 dir="ltr" style="line-height:1.15;margin-top:8pt;margin-bottom:0pt"><span style="font-size:16px;font-family:'Trebuchet MS';color:rgb(102,102,102);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Push-relabel algorithm</span></h3><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Probably the best for our purpose (and easy to test: </span><a href="http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/push_relabel_max_flow.html" style="text-decoration:none"><span style="font-size:15px;font-family:Arial;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">boost</span></a><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">). However, it is not obvious to me how to enforce the extra constraint required for conservative PRE, so if we use it we will need profiling information (or any reasonable static approximation, maybe from </span><a href="https://github.com/llvm-mirror/llvm/blob/master/docs/BlockFrequencyTerminology.rst" style="text-decoration:none"><span style="font-size:15px;font-family:Arial;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">BlockFrequency</span></a><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent"> ?).</span></p><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Pass Ordering</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">I am currently planning on running this pass just after AtomicExpandPass, i.e. just before lowering to SelectionDAG. It could in theory be executed later in the backend, but I would rather avoid doing a global, control-flow related optimization on SelectionDAGs if at all possible. It cannot be run earlier, because the target-specific fences do not exist yet.</span></p><h1 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:21px;font-family:'Trebuchet MS';color:rgb(0,0,0);font-weight:normal;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Receiving information from AtomicExpandPass</span></h1><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">As we saw previously in the previous section, several possible improvements to the graph building require this pass to find where a given Fence comes from. It is thus not mandatory and won’t be in the first patch, but we should have plan on how to do it later (incrementally). I see mostly three ways of doing this (I tried getting some </span><a href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-August/076326.html" style="text-decoration:none"><span style="font-size:15px;font-family:Arial;text-decoration:underline;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">discussion</span></a><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent"> on this, but without much success). For clarity, I am using DMB here for the target-dependent fence.</span></p><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Pass the information directly from AtomicExpandPass to FenceEliminationPass</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">This would be the easiest, but would utterly break encapsulation, force the two passes to run together all the time, and generally not respect the current PassManager-based infrastructure. I don’t think it is acceptable.</span></p><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Use rich pseudo-instructions instead of DMBs</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">In this proposal, AtomicExpandPass does not insert DMBs, but various pseudo-instructions such as FenceAfterAcquire(LoadItWasCreatedBy). This would work, but require adding some pseudo-instructions, that the backend/another pass would have to learn how to lower for -O0.</span></p><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Put metadata on Fences</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">This is a variant on the previous proposal: AtomicExpandPass keeps introducing DMBs, but tags them with special metadata describing their origin. FenceEliminationPass could then make use of this information as long as it is available, whereas the backend and any other pass would just automatically ignore it and correctly emit DMBs. Furthermore, if any other pass introduces/copies DMBs, FenceElimination will automatically be correctly conservative. This approach seems like the best, and is currently what I am planning on doing. For the optimizations currently envisioned, a single piece of metadata llvm.fence.from with one argument being the access that caused the fence to be emitted would be enough.</span></p><h1 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:21px;font-family:'Trebuchet MS';color:rgb(0,0,0);font-weight:normal;vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Adapting the algorithm to a variety of architectures</span></h1><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">x86</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">There is not much point in doing fence elimination on x86, because only fence seq_cst is lowered to a mfence. In particular atomic accesses do not ever introduce mfences, instead seq_cst stores are compiled to lock xchg, and everything else is just a mov.</span></p><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">ARM</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Arm will be my first target, everything in this document should apply to it straightforwardly.</span></p><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Power</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">The main difference between Power and ARM is that Power has both hwsync and lwsync where ARM only has DMB ISH (it has a few others, but none matching lwsync exactly). As described previously this is not a big problem, we can just insert the hwsyncs first, and the lwsyncs second, taking into account the hwsyncs in the step 2 of the algorithm.</span></p><h2 dir="ltr" style="line-height:1.15;margin-top:10pt;margin-bottom:0pt"><span style="font-size:17px;font-family:'Trebuchet MS';color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Others</span></h2><p dir="ltr" style="line-height:1.15;margin-top:0pt;margin-bottom:0pt"><span style="font-size:15px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">I do not know the other architectures well enough to propose a design for them. However, the approach looks general enough that it may be used for Sparc/Mips if someone with the required expertise is motivated to do it.</span></p></span></div></div>