Hongbin Can you elaborate more on your suggestion? I am not sure I fully understand what you suggested. -Milind On Wed, Jul 17, 2013 at 11:11 PM, Hongbin Zheng <etherzhhb at gmail.com> wrote:> Hi Milind, > > Maybe you could annotate the default case value as metadata to the swith > instruction. > > Thanks > Hongbin > > > On Thu, Jul 18, 2013 at 1:09 PM, Milind Chabbi <Milind.Chabbi at rice.edu> > wrote: >> >> Hi Mark, >> >> This will workaround the problem of "default" branch restriction on >> the switch instruction. The trouble with this technique is that it >> will trump later optimization phases such as constant propagation. >> When a block was part of a case, because of the knowledge of the case >> value, the block was a candidate for better optimization. However, >> when we move the body of the case into the default, the knowledge of >> the case value is lost and the body is less optimizable. >> >> -Milind >> >> >> On Wed, Jul 17, 2013 at 9:29 PM, Mark Lacey <mark.lacey at apple.com> wrote: >> > On Jul 17, 2013, at 9:01 PM, Milind Chabbi <Milind.Chabbi at rice.edu> >> > wrote: >> >> I am performing a transformation that requires changing the targets of >> >> a basic block ending with a switch instruction. >> >> In particular, I need to delete the edge that goes to the "default" >> >> basic block. >> >> But, LLVM switch instruction always wants a default target basic block >> >> for a switch instruction. >> >> It is not clear how to accomplish this, since I don't have a >> >> replacement default target block. >> >> I could potentially fake that edge to be one of the other case label >> >> targets, but that is an ugly hack and I don't want to do that. >> >> I would appreciate if you can suggest better alternatives. >> > >> > Hi Milind, >> > >> > If you make the "default" branch to a block that has an UnreachableInst >> > as a terminator, the SimplifyCFG pass will remove one of the switch cases >> > and replace the block that the default branches to with the block that this >> > removed case branches to. This sounds a lot like the "ugly hack" that you >> > would like to avoid. Would it be a reasonable solution for what you are >> > trying to accomplish? >> > >> > Mark >> > >> > >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >
Hi Milind, My suggestion just for your concern that if you eliminate the default block, a block associated with a case value will become the default block of the swhich instruction, since a switch instruction always requires a default block. But when a block associated with a case value become the default block, the associated case value is lost and may confuse the later optimizations such as constant propagation. To prevent such information lost when you eliminate the default block and make a block associated with a case value will become the default block, you can attach a metadata[1] to the switch instruction to provide the case value of the default block. In order to take the advantage of the attached metadata for the default case of the switch instruction you also need to modify the later optimization accordingly. Thanks Hongbin [1]http://blog.llvm.org/2010/04/extensible-metadata-in-llvm-ir.html On Thu, Jul 18, 2013 at 2:30 PM, Milind Chabbi <Milind.Chabbi at rice.edu>wrote:> Hongbin > > Can you elaborate more on your suggestion? I am not sure I fully > understand what you suggested. > > -Milind > > On Wed, Jul 17, 2013 at 11:11 PM, Hongbin Zheng <etherzhhb at gmail.com> > wrote: > > Hi Milind, > > > > Maybe you could annotate the default case value as metadata to the swith > > instruction. > > > > Thanks > > Hongbin > > > > > > On Thu, Jul 18, 2013 at 1:09 PM, Milind Chabbi <Milind.Chabbi at rice.edu> > > wrote: > >> > >> Hi Mark, > >> > >> This will workaround the problem of "default" branch restriction on > >> the switch instruction. The trouble with this technique is that it > >> will trump later optimization phases such as constant propagation. > >> When a block was part of a case, because of the knowledge of the case > >> value, the block was a candidate for better optimization. However, > >> when we move the body of the case into the default, the knowledge of > >> the case value is lost and the body is less optimizable. > >> > >> -Milind > >> > >> > >> On Wed, Jul 17, 2013 at 9:29 PM, Mark Lacey <mark.lacey at apple.com> > wrote: > >> > On Jul 17, 2013, at 9:01 PM, Milind Chabbi <Milind.Chabbi at rice.edu> > >> > wrote: > >> >> I am performing a transformation that requires changing the targets > of > >> >> a basic block ending with a switch instruction. > >> >> In particular, I need to delete the edge that goes to the "default" > >> >> basic block. > >> >> But, LLVM switch instruction always wants a default target basic > block > >> >> for a switch instruction. > >> >> It is not clear how to accomplish this, since I don't have a > >> >> replacement default target block. > >> >> I could potentially fake that edge to be one of the other case label > >> >> targets, but that is an ugly hack and I don't want to do that. > >> >> I would appreciate if you can suggest better alternatives. > >> > > >> > Hi Milind, > >> > > >> > If you make the "default" branch to a block that has an > UnreachableInst > >> > as a terminator, the SimplifyCFG pass will remove one of the switch > cases > >> > and replace the block that the default branches to with the block > that this > >> > removed case branches to. This sounds a lot like the "ugly hack" that > you > >> > would like to avoid. Would it be a reasonable solution for what you > are > >> > trying to accomplish? > >> > > >> > Mark > >> > > >> > > >> > >> _______________________________________________ > >> LLVM Developers mailing list > >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130718/bde3939f/attachment.html>
On Wed, Jul 17, 2013 at 11:58 PM, Hongbin Zheng <etherzhhb at gmail.com> wrote:> Hi Milind, > > My suggestion just for your concern that if you eliminate the default block, > a block associated with a case value will become the default block of the > swhich instruction, since a switch instruction always requires a default > block. > But when a block associated with a case value become the default block, the > associated case value is lost and may confuse the later optimizations such > as constant propagation. > > To prevent such information lost when you eliminate the default block and > make a block associated with a case value will become the default block, you > can attach a metadata[1] to the switch instruction to provide the case value > of the default block.If I'm understanding you correctly you're suggesting removing the default block & representing it in metadata only (instead of using an existing case block as the default as well). That seems like it would break the invariant that every switch has a default (if we didn't have that invariant we would just eliminate the unreachable default block & not bother associating it with an existing case), wouldn't it? Metadata has to be droppable (because not all passes preserve/understand all metadata) so we can't rely on the preservation of the metadata to maintain the switch instructions invariant.> > In order to take the advantage of the attached metadata for the default case > of the switch instruction you also need to modify the later optimization > accordingly. > > Thanks > Hongbin > > [1]http://blog.llvm.org/2010/04/extensible-metadata-in-llvm-ir.html > > > > On Thu, Jul 18, 2013 at 2:30 PM, Milind Chabbi <Milind.Chabbi at rice.edu> > wrote: >> >> Hongbin >> >> Can you elaborate more on your suggestion? I am not sure I fully >> understand what you suggested. >> >> -Milind >> >> On Wed, Jul 17, 2013 at 11:11 PM, Hongbin Zheng <etherzhhb at gmail.com> >> wrote: >> > Hi Milind, >> > >> > Maybe you could annotate the default case value as metadata to the swith >> > instruction. >> > >> > Thanks >> > Hongbin >> > >> > >> > On Thu, Jul 18, 2013 at 1:09 PM, Milind Chabbi <Milind.Chabbi at rice.edu> >> > wrote: >> >> >> >> Hi Mark, >> >> >> >> This will workaround the problem of "default" branch restriction on >> >> the switch instruction. The trouble with this technique is that it >> >> will trump later optimization phases such as constant propagation. >> >> When a block was part of a case, because of the knowledge of the case >> >> value, the block was a candidate for better optimization. However, >> >> when we move the body of the case into the default, the knowledge of >> >> the case value is lost and the body is less optimizable. >> >> >> >> -Milind >> >> >> >> >> >> On Wed, Jul 17, 2013 at 9:29 PM, Mark Lacey <mark.lacey at apple.com> >> >> wrote: >> >> > On Jul 17, 2013, at 9:01 PM, Milind Chabbi <Milind.Chabbi at rice.edu> >> >> > wrote: >> >> >> I am performing a transformation that requires changing the targets >> >> >> of >> >> >> a basic block ending with a switch instruction. >> >> >> In particular, I need to delete the edge that goes to the "default" >> >> >> basic block. >> >> >> But, LLVM switch instruction always wants a default target basic >> >> >> block >> >> >> for a switch instruction. >> >> >> It is not clear how to accomplish this, since I don't have a >> >> >> replacement default target block. >> >> >> I could potentially fake that edge to be one of the other case label >> >> >> targets, but that is an ugly hack and I don't want to do that. >> >> >> I would appreciate if you can suggest better alternatives. >> >> > >> >> > Hi Milind, >> >> > >> >> > If you make the "default" branch to a block that has an >> >> > UnreachableInst >> >> > as a terminator, the SimplifyCFG pass will remove one of the switch >> >> > cases >> >> > and replace the block that the default branches to with the block >> >> > that this >> >> > removed case branches to. This sounds a lot like the "ugly hack" that >> >> > you >> >> > would like to avoid. Would it be a reasonable solution for what you >> >> > are >> >> > trying to accomplish? >> >> > >> >> > Mark >> >> > >> >> > >> >> >> >> _______________________________________________ >> >> 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 >