> I guess another way to select interesting transformations could be to look for sequences where the > result uses a "subset" of the input instruction sequence.Yeah, I had been noticing those subsets too. It sounds like it's worth a try doing a run that looks only for those. One nice thing is that if we're just looking for subsets, we will not even give the syntehsizer the option to use instructions that aren't in the subset -- this should give a nice speedup, and probably will even make synthesis more likely to succeed (assuming that an optimization exists within the subset). John
On 07/23/2015 07:24 AM, John Regehr wrote:>> I guess another way to select interesting transformations could be to >> look for sequences where the >> result uses a "subset" of the input instruction sequence. > > Yeah, I had been noticing those subsets too. It sounds like it's > worth a try doing a run that looks only for those. > > One nice thing is that if we're just looking for subsets, we will not > even give the syntehsizer the option to use instructions that aren't > in the subset -- this should give a nice speedup, and probably will > even make synthesis more likely to succeed (assuming that an > optimization exists within the subset).+1 - This sounds like a very interesting approach. I suspect it might also find cases which are easier to hand generalize, but that's just a guess. Another option would be exclude extensions of i1 and non cmov-like selects from the candidate set. A lot of the examples in this set end up converting conditional codes to register values which is non-ideal. I saw a couple of examples which had obvious cmov implementations which just weren't expressed that way in the output. A couple of small suggestions on the output formatting: - Give each entry a unique ID (result set 3 #25 would be fine). That would make them much easier to discuss. - Exclude examples where only a prefix changes. There were several instances where the last instruction in the sequence was duplicated exactly. This is essentially an instance of synthesizing the subproblem and results in duplicates in the output. - Group all inputs at the beginning. Follow with an instructions which are shared between input and output. This'll make it easier to scan the output.> > John > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> Another option would be exclude extensions of i1 and non cmov-like selects > from the candidate set.Sorry, can you explain what a non-cmov-like select looks like? OK, you and Sean have convinced me about the condition codes-- I'll assign cost >1 to sext/zext of i1 and we'll see how that works out.> - Give each entry a unique ID (result set 3 #25 would be fine). That would > make them much easier to discuss.Oops-- I had intended to give permalinks to the optimizations but somehow dropped that, will do it next time.> - Exclude examples where only a prefix changes. There were several instances > where the last instruction in the sequence was duplicated exactly. This is > essentially an instance of synthesizing the subproblem and results in > duplicates in the output.Weird, I read the entire list and totally overlooked this, will filter next time.> - Group all inputs at the beginning. Follow with an instructions which are > shared between input and output. This'll make it easier to scan the output.Yeah. Alternately, we already translate each Souper LHS into LLVM-- I could put the LLVM code on the web instead of the Souper code, then you'd have inputs as function arguments, if that's easier on the eyes? Thanks! John
Hi, On 23/07/15 19:11, Philip Reames wrote:> > > On 07/23/2015 07:24 AM, John Regehr wrote: >>> I guess another way to select interesting transformations could be to look >>> for sequences where the >>> result uses a "subset" of the input instruction sequence. >> >> Yeah, I had been noticing those subsets too. It sounds like it's worth a try >> doing a run that looks only for those. >> >> One nice thing is that if we're just looking for subsets, we will not even >> give the syntehsizer the option to use instructions that aren't in the subset >> -- this should give a nice speedup, and probably will even make synthesis more >> likely to succeed (assuming that an optimization exists within the subset). > +1 - This sounds like a very interesting approach. I suspect it might also find > cases which are easier to hand generalize, but that's just a guess.this sounds like what my LLVM superoptimizer did: simplified expressions to subexpressions that were already present in the original expression, for example (x+y)-x -> y. Here the right-hand side "y" is a particularly simple subexpression of the original :) One big advantage is that you can process expressions very fast, typically hundreds per second. The other advantage is that optimizations you find are unlikely to make things worse (but they can increase register pressure). The big disadvantage is of course that it misses many interesting optimizations, for example it will miss x-(x+y) -> -y because -y wasn't in the original expression. Another simple trick for finding optimizations is to detect inputs that have no effect on outputs. For example, in x-(x+y), the result of the expression doesn't depend on the value of x. Thus you can replace x with whatever you like without changing anything, for example replacing x with 0 you get 0-(0+y) which simplifies down to 0-y, i.e. -y. You have found x-(x+y) -> -y. Ciao, Duncan.> > Another option would be exclude extensions of i1 and non cmov-like selects from > the candidate set. A lot of the examples in this set end up converting > conditional codes to register values which is non-ideal. I saw a couple of > examples which had obvious cmov implementations which just weren't expressed > that way in the output. > > A couple of small suggestions on the output formatting: > - Give each entry a unique ID (result set 3 #25 would be fine). That would make > them much easier to discuss. > - Exclude examples where only a prefix changes. There were several instances > where the last instruction in the sequence was duplicated exactly. This is > essentially an instance of synthesizing the subproblem and results in duplicates > in the output. > - Group all inputs at the beginning. Follow with an instructions which are > shared between input and output. This'll make it easier to scan the output. >> >> John >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev