<div dir="ltr">On Fri, Nov 15, 2013 at 9:21 AM, Lukas Hellebrandt <span dir="ltr"><<a href="mailto:kamikazecz@gmail.com" target="_blank">kamikazecz@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hi all,<br>
<br>
I'm trying to write a tool for detecting undefined behavior in C<br>
regarding sequence points and side effects.<br>
<br>
I'm not sure whether it should be a Clang plugin or LLVM run or<br>
something completely different (I'm really new to both Clang and LLVM)<br>
and that's what I need advice with.<br>
<br>
For my work, I need to use both AST and alias analysis<br>
<br>
Clang plugin:<br>
        +relatively easy to use<br>
        +access to AST with all the needed info EXCEPT alias analysis (right?)<br>
        -no alias analysis, I'd need to write one myself<br>
<br>
LLVM run:<br>
        +built-in alias analysis (I'd like to use it, writing my own alias<br>
analysis is not really what my work is all about)<br>
        -I do NOT have access to AST<br>
        -I don't know it at all (but I'm ready to learn it if it shows up to be<br>
the best option)<br>
<br>
The big PROBLEM is: a behavior that is undefined in C (and which Clang<br>
has access to) might be (and in my case WILL be) well defined in LLVM<br>
(for example, i=i++; is undefined in C but in LLVM code it will be<br>
already well defined and the result will depend on Clang behavior).<br>
<br>
So I thought I could use both, in Clang create a list of rules, for<br>
example "On line L, there is an undefined behavior if X aliases with Y"<br>
and then SOMEHOW dig this info from LLVM run.<br>
<br>
Is this a good idea? Is there a way (other than output to file from<br>
Clang and then read it in LLVM) to give this set of rules to LLVM? I'd<br>
also be glad for any other idea, not necessarily including LLVM and<br>
Clang, to solve this problem.</blockquote><div><br></div><div>I've thought about this a bit from the point of view of adding a check to -fsanitize=undefined. We already detect cases where it's "locally" obvious that the expression will have undefined behavior, for instance, we'll warn on your example of "i = i++;".</div>
<div><br></div><div>From the ubsan perspective, I think the thing to do here is to form a list of pairs of subexpressions within the full-expression where, if the two subexpressions refer to the same object, we will have unsequenced accesses (in the presence of ?:, &&, and ||, we'll need to be careful to only check these if the relevant subexpression was actually evaluated). Then, perhaps at the end of the full-expression, we emit a check that no such pair evaluated to the same address.</div>
<div><br></div><div>Building the set of pairs is a little tricky, but the code implementing -Wunsequenced can probably be reused to form this set.<br><br></div><div>That said, we have a representational weakness in LLVM here: we have no way to express that the language semantics allow us to freely reorder two memory operations. If we could emit somehow (perhaps as metadata) the information that we have about full-expressions, we could use that as input to an LLVM alias analysis -- then we could use the same representation both to drive a check and to drive optimizations. In the long term, that's probably the superior approach.</div>
<div><br></div><div><br></div><div>(Not-fully-baked ideas follow...) We could imagine this working something like the following. Given:<br></div><div><br></div><div>  (a++, b) = c ? d++ : e</div><div><br></div><div>We divide it into separately-sequenced portions:</div>
<div><br></div><div> full expression: seq 0</div><div> a++: seq 1 for load, seq 2 for store</div><div> b: seq 3</div><div> c: seq 4</div><div> d++: seq 5 for load, seq 6 for store</div><div> e: seq 7</div><div> assignment: seq 8</div>
<div><br></div><div>We know that:</div><div><br></div><div>  seq 2 and seq 3 are sequenced after seq 1</div><div>  seq 4 and seq 5 are sequenced after seq 3</div><div>  seq 6 is sequenced after seq 5</div><div>  seq 8 is sequenced after seq 3, 5, and 7</div>
<div>  seq 1-8 are nested within seq 0 (so are by default not sequenced with other things inside seq 0)</div><div><br></div><div>We could then express this as metadata as:</div><div><br></div><div>  %a = load @a, !seq !seq1</div>
<div>  %a.1 = add %a, 1</div><div>  store @a, %a.1, !seq !seq2</div><div>  ; ...</div><div><br></div><div>!seq0 = !{}</div><div>!seq1 = !{seq0} ; parent is 0</div><div>!seq2 = !{seq0, !{seq1}} ; parent is 0, sequenced after 1</div>
<div>!seq3 = !{seq0, !{seq1}} ; parent is 0, sequenced after 1</div><div>; ...</div><div><br></div><div>... with the semantics that memory operations A and B are known not to alias if at least one is a load, and they have the same parent, and neither is (transitively) sequenced before the other.</div>
</div></div></div>