<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 03/10/2017 02:26 AM, Chandler
Carruth wrote:<br>
</div>
<blockquote
cite="mid:CAGCO0KiYBRP1N-P9QWtyC63Ao9XurpjMTfVqULDXmdQumG_wbg@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div dir="ltr">
<div class="gmail_quote">
<div dir="ltr">On Thu, Mar 9, 2017 at 3:55 PM Hal Finkel <<a
moz-do-not-send="true" href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex"><br
class="gmail_msg">
On 03/09/2017 03:49 PM, Wei Mi wrote:<br class="gmail_msg">
> On Thu, Mar 9, 2017 at 10:54 AM, Hal Finkel <<a
moz-do-not-send="true" href="mailto:hfinkel@anl.gov"
class="gmail_msg" target="_blank">hfinkel@anl.gov</a>>
wrote:<br class="gmail_msg">
>> On 03/09/2017 12:14 PM, Wei Mi via llvm-dev wrote:<br
class="gmail_msg">
>>> In<br class="gmail_msg">
>>> <a moz-do-not-send="true"
href="http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20120827/063200.html"
rel="noreferrer" class="gmail_msg" target="_blank">http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20120827/063200.html</a>,<br
class="gmail_msg">
>>> consecutive bitfields are wrapped as a group
and represented as a<br class="gmail_msg">
>>> large integer and emits loads stores and bit
operations appropriate<br class="gmail_msg">
>>> for extracting bits from within it. It fixes
the problem of violating<br class="gmail_msg">
>>> C++11 memory model that original widen
load/store of bitfield was<br class="gmail_msg">
>>> facing. It also brings more coalescing
opportunities across bitfields.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> If some bitfields are natural aligned and their
num of bits can form a<br class="gmail_msg">
>>> legal integer type that the target supports, it
is more efficient to<br class="gmail_msg">
>>> access them directly than doing a large integer
load/store plus a<br class="gmail_msg">
>>> series of bit operations. We call such reverse
transformation legal<br class="gmail_msg">
>>> type bitfield shrinking. Currently, llvm
depends on DAGCombiner to do<br class="gmail_msg">
>>> such shrinking.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> However, DAGCombiner has the
one-basic-block-a-time limitation, so we<br
class="gmail_msg">
>>> started to implement a new shrinking
optimization in<br class="gmail_msg">
>>> <a moz-do-not-send="true"
href="https://reviews.llvm.org/D30416" rel="noreferrer"
class="gmail_msg" target="_blank">https://reviews.llvm.org/D30416</a>,
and initially put it in instcombine,<br class="gmail_msg">
>>> then moved it to CGP because we want to use
some TargetLowering<br class="gmail_msg">
>>> information.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> The initial implementation in D30416 only
supports load-and-or-store<br class="gmail_msg">
>>> pattern matching, and it uses a inst-by-inst
scan as a safety check to<br class="gmail_msg">
>>> make sure there is no other memory write insn
between the load and<br class="gmail_msg">
>>> store (no alias query is done). After getting
the initial<br class="gmail_msg">
>>> implementation, we found more problems:
EarlyCSE, LoadPRE and even<br class="gmail_msg">
>>> InstCombine itself can do coalescing before the
shrinking (LoadPRE<br class="gmail_msg">
>>> does it the most thoroughly).<br
class="gmail_msg">
>>> The coalescing can move the load many
BasicBlocks earlier and make<br class="gmail_msg">
>>> simple inst-by-inst scan unscalable and
oftentimes fail. It also<br class="gmail_msg">
>>> breaks the load-and-or-store pattern. An
example is below:<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Before coalescing done by earlycse/loadpre:<br
class="gmail_msg">
>>> %bf.load = load i64, i64* %0, align 8<br
class="gmail_msg">
>>> %bf.clear = and i64 %bf.load, -65536<br
class="gmail_msg">
>>> %bf.set = or i64 %bf.value, %bf.clear<br
class="gmail_msg">
>>> store i64 %bf.set2, i64* %9, align 8<br
class="gmail_msg">
>>> .....<br class="gmail_msg">
>>> %bf.load1 = load i64, i64* %0, align 8<br
class="gmail_msg">
>>> %bf.clear1 = and i64 %bf.load1, -4294901761<br
class="gmail_msg">
>>> %bf.set1 = or i64 %bf.value1, %bf.clear1<br
class="gmail_msg">
>>> store i64 %bf.set2, i64* %9, align 8<br
class="gmail_msg">
>>> .....<br class="gmail_msg">
>>> %bf.load2 = load i64, i64* %0, align 8<br
class="gmail_msg">
>>> %bf.clear2 = and i64 %bf.load2, -4294901761<br
class="gmail_msg">
>>> %bf.set2 = or i64 %bf.value2, %bf.clear2<br
class="gmail_msg">
>>> store i64 %bf.set2, i64* %9, align 8<br
class="gmail_msg">
>>><br class="gmail_msg">
>>> After coalescing, it will become:<br
class="gmail_msg">
>>> %bf.load = load i64, i64* %0, align 8<br
class="gmail_msg">
>>> %bf.clear = and i64 %bf.load, -65536<br
class="gmail_msg">
>>> %bf.set = or i64 %bf.value, %bf.clear<br
class="gmail_msg">
>>> .....<br class="gmail_msg">
>>> %bf.clear1 = and i64 %bf.set, -4294901761<br
class="gmail_msg">
>>> %bf.set1 = or i64 %bf.value1, %bf.clear1<br
class="gmail_msg">
>>> .....<br class="gmail_msg">
>>> %bf.clear2 = and i64 %bf.set1, -4294901761<br
class="gmail_msg">
>>> %bf.set2 = or i64 %bf.value2, %bf.clear2<br
class="gmail_msg">
>>> store i64 %bf.set2, i64* %9, align 8<br
class="gmail_msg">
>>><br class="gmail_msg">
>>> After load-store coalescing, %bf.load now is
far away from the store,<br class="gmail_msg">
>>> and the previous load-and-or-store pattern
disappears.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> A simple idea to fix it is to move the
shrinking in a very early pass<br class="gmail_msg">
>>> before the first pass of EarlyCSE. However, if
we move shrinking<br class="gmail_msg">
>>> earlier, it is possible to block the coalescing
of other ilegal type<br class="gmail_msg">
>>> bitfields which can not be shrinked. So for
coalescing and shrinking,<br class="gmail_msg">
>>> no matter which one is first, it will block the
other one.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> After some discussions with Eli and Michael, I
come up with another<br class="gmail_msg">
>>> idea to let shrinking stay in the late
pipeline. It needs two changes<br class="gmail_msg">
>>> to the current patch:<br class="gmail_msg">
>>><br class="gmail_msg">
>>> 1. extending the pattern match to handle
store(or(and(or(and...))<br class="gmail_msg">
>>> pattern above. It needs to analyze the bit mask
of every and-or pairs.<br class="gmail_msg">
>>> If the last and-or pair touch different section
with the other and-or<br class="gmail_msg">
>>> pairs, we can split the original store into
two, and do the shrinking<br class="gmail_msg">
>>> for the second store, like below<br
class="gmail_msg">
>>><br class="gmail_msg">
>>> %bf.load = load i64, i64* %0, align 8<br
class="gmail_msg">
>>> %bf.clear = and i64 %bf.load, -65536<br
class="gmail_msg">
>>> %bf.set = or i64 %bf.value, %bf.clear<br
class="gmail_msg">
>>> .....<br class="gmail_msg">
>>><br class="gmail_msg">
>>> %bf.clear1 = and i64 %bf.set, -4294901761<br
class="gmail_msg">
>>> %bf.set1 = or i64 %bf.value1, %bf.clear1<br
class="gmail_msg">
>>> store i64 %bf.set1, i64* %0, align 8
// the first<br class="gmail_msg">
>>> store.<br class="gmail_msg">
>>> .....<br class="gmail_msg">
>>><br class="gmail_msg">
>>> %bf.value2.shrinked = shrink_op %bf.value2<br
class="gmail_msg">
>>> store i16 %bf.value2.shrinked, i64* %0, align
8 // shrinked store.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> 2. use memoryssa + alias query to do the safety
check. Because<br class="gmail_msg">
>>> dominator tree is not properly updated in CGP,
I have to create a new<br class="gmail_msg">
>>> pass and put it before CGP, in order to use
memoryssa.<br class="gmail_msg">
>><br class="gmail_msg">
>> This makes sense to me. Should we just fix CGP to
update the DT instead of<br class="gmail_msg">
>> working around it?<br class="gmail_msg">
>><br class="gmail_msg">
>> -Hal<br class="gmail_msg">
> I am not familiar enough with CGP to tell. I just
notice ModifiedDT is<br class="gmail_msg">
> modified at several places in CGP, which indicates
there are a few<br class="gmail_msg">
> transformations needing their specific dominator tree
maintainance<br class="gmail_msg">
> work. And I remember simplifyCFG also doesn't use
dominator tree to<br class="gmail_msg">
> save the effort to maintain it on the fly. So maybe it
is easier to<br class="gmail_msg">
> separate CGP into two parts: which does need dominator
tree and<br class="gmail_msg">
> doesn't. Those transformations which don't need
dominator tree can<br class="gmail_msg">
> stay together.<br class="gmail_msg">
><br class="gmail_msg">
> Currently, I know consthoisting is another potential
CGP<br class="gmail_msg">
> transformation but left out because of its need of
dominator tree. But<br class="gmail_msg">
> consthoisting has already evolved to contain a
substantial amount of<br class="gmail_msg">
> code so may be better to stay as a separate pass.<br
class="gmail_msg">
<br class="gmail_msg">
That might very well be the case here too (the matching
logic might grow<br class="gmail_msg">
in complexity). CGP has now grown to over 5K lines, and
there are<br class="gmail_msg">
definitely pieces that can get split out. There is a big
chunk that runs<br class="gmail_msg">
iteratively, however, so that might not buy us as much as we
might hope.<br class="gmail_msg">
</blockquote>
<div><br>
</div>
<div>I think a lot of the reasons why we used CGP as a grabbag
was because for a while we didn't really have a compelling
model for *why* we were moving out of canonical form. But
we've really clarified the pass pipeline structure now so
I'd love to try and build reasonable "optimization" (as
opposed to "canonicalization" or "simplification") passes
and organize them nicely.</div>
</div>
</div>
</blockquote>
<br>
Sounds good (although we still need to be careful not to lose the
iterative nature of the current optimizations in cases where that's
important).<br>
<br>
<blockquote
cite="mid:CAGCO0KiYBRP1N-P9QWtyC63Ao9XurpjMTfVqULDXmdQumG_wbg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_quote">
<div><br>
</div>
<div>One perhaps especially notable thing: this will often end
up *narrowing*. I think that it would be very valuable to
try and place this or other passes that effectively narrow
data access types *before the vectorizers*. This seems
important to enable efficient packing of element types.</div>
</div>
</div>
</blockquote>
<br>
I think it would be useful to work through some examples in this
context. It might help vectorization to narrow beforehand, or it
might end up requiring more scatter/gather load/stores (whereas, in
the context of vectorization, the shifts and masks might have been
more efficient).<br>
<br>
-Hal<br>
<br>
<blockquote
cite="mid:CAGCO0KiYBRP1N-P9QWtyC63Ao9XurpjMTfVqULDXmdQumG_wbg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_quote">
<div><br>
</div>
<div>Past that, I generally like the plan of a dedicated pass
to narrow integer stuff across basic blocks, etc., using
MemorySSA and other efficient tools. =]</div>
<div><br>
</div>
<div>-Chandler</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<br class="gmail_msg">
-Hal<br class="gmail_msg">
<br class="gmail_msg">
><br class="gmail_msg">
> Thanks,<br class="gmail_msg">
> Wei.<br class="gmail_msg">
><br class="gmail_msg">
>>> Eli suggested me to ask for more opinions
before start writting code.<br class="gmail_msg">
>>> I think it is a good idea and here is the post.
Comments are<br class="gmail_msg">
>>> appreciated.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Thanks,<br class="gmail_msg">
>>> Wei.<br class="gmail_msg">
>>> _______________________________________________<br
class="gmail_msg">
>>> LLVM Developers mailing list<br
class="gmail_msg">
>>> <a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" class="gmail_msg"
target="_blank">llvm-dev@lists.llvm.org</a><br
class="gmail_msg">
>>> <a moz-do-not-send="true"
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
rel="noreferrer" class="gmail_msg" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br
class="gmail_msg">
>><br class="gmail_msg">
>> --<br class="gmail_msg">
>> Hal Finkel<br class="gmail_msg">
>> Lead, Compiler Technology and Programming Languages<br
class="gmail_msg">
>> Leadership Computing Facility<br class="gmail_msg">
>> Argonne National Laboratory<br class="gmail_msg">
>><br class="gmail_msg">
<br class="gmail_msg">
--<br class="gmail_msg">
Hal Finkel<br class="gmail_msg">
Lead, Compiler Technology and Programming Languages<br
class="gmail_msg">
Leadership Computing Facility<br class="gmail_msg">
Argonne National Laboratory<br class="gmail_msg">
<br class="gmail_msg">
</blockquote>
</div>
</div>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>