mapping liveness to variables
Hi guys, I am trying to get as close mapping from liveness information ( in bb->il.rtl->global_live_at_start ) to global and local variables as possible. Mapping to stack slots would be a good first step. What data structures should I look at use? What would be the best way to do it? Any suggestions appreciated, Gregory -- What would you attempt to do if you knew you could not fail?
Fixing jumps reachability after block reordering
Hi, I am working on adding support for code-copying to GCC that can be used to safely speed up interpreter-based VMs, as will be presented at GCC Summit: http://www.gccsummit.org/2007/view_abstract.php?content_key=30 One of the operations I need to perform is to reorder basic blocks in a particular manner. This works fine for example on i386 and other that have HAS_LONG_COND_BRANCH, HAS_LONG_UNCOND_BRANCH set. However on platforms like PPC, after the reordering, some branches are trying to reach destinations beyond their reach and I get errors during the final assembly. The draft of a solution I came up with after a few days of digging in the existing code is this: For each function that has basic blocks reordered for code-copying, Scan all the insn's, find all jumps, For each jump check its destination label, and 1. compute the distance between the jump and the label (if possible use insn_lengths[] form final.c, or build it yourself using get_attr_length()) 2. compare the distance with what can be reached using the Mode (GET_MODE_SIZE, exact_log2()) 3. if Mode won't reach the destination, create an extra BB with an unconditional or indirect jump to the label (like bb-reorder.c) and redirect the original jump to it. Is there an esier way of doing it? (maybe there's mechanisms in GCC that do it already?) What am I missing? Any similar code in GCC I should look at? Thanks, Gregory -- Gregory B. Prokopski <[EMAIL PROTECTED]> Sable Research Group http://www.sable.mcgill.ca Montreal, Quebec, Canada
Re: Fixing jumps reachability after block reordering
+++ Ian Lance Taylor [05/07/07 17:48 -0700]: > "Gregory B. Prokopski" <[EMAIL PROTECTED]> writes: > > > One of the operations I need to perform is to reorder basic blocks in a > > particular manner. This works fine for example on i386 and other that have > > HAS_LONG_COND_BRANCH, HAS_LONG_UNCOND_BRANCH set. However on platforms like > > PPC, after the reordering, some branches are trying to reach destinations > > beyond their reach and I get errors during the final assembly. > > The hot/cold block partitioning code, -freorder-blocks-and-partition, > faces a similar problem. How do they solve it? They only care about the edges that cross hot/cold sections boundaries. In my case, for all I care, the code of whole function can be in the hot section. > > For each function that has basic blocks reordered for code-copying, > > Scan all the insn's, find all jumps, > > For each jump check its destination label, and > > 1. compute the distance between the jump and the label > > (if possible use insn_lengths[] form final.c, or build it yourself > > using get_attr_length()) > > 2. compare the distance with what can be reached using the Mode > > (GET_MODE_SIZE, exact_log2()) > > 3. if Mode won't reach the destination, create an extra BB with an > > unconditional or indirect jump to the label (like bb-reorder.c) > > and redirect the original jump to it. > > But you seem to be within a single function, so I don't understand why > you have any trouble at all. Why doesn't the shorten_branches pass > work for you? I reorder the basic blocks in passes.c, right after compute_alignmnets (). I added a call to shorten_branches(NULL_RTX) right after my BB reordering, but it didn't change a thing, and I am still getting as errors: libsablevm.s: Assembler messages: libsablevm.s:56077: Error: operand out of range (91824 not between -32768 and 32767) libsablevm.s:71896: Error: operand out of range (-38472 not between -32768 and 32767) libsablevm.s:97418: Error: operand out of range (-51652 not between -32768 and 32767) Almost a hundred of these. I would need a way to debug this problem, which means I'd like to detect this problem earlier, say, when I do the block reordering. I thought I could do it with the algorigthm I described above. G. -- Gregory B. Prokopski <[EMAIL PROTECTED]> Sable Research Group http://www.sable.mcgill.ca Montreal, Quebec, Canada
Re: Fixing jumps reachability after block reordering
+++ Ian Lance Taylor [06/07/07 09:16 -0700]: > shorten_branches should work correctly--you shouldn't need to do > anything special. My only guess is that there is something wrong with > the way you are reordering the blocks. For example, perhaps you are > simply reordering the CFG without reordering the insn chain. Note > that shorten_branches is not (yet) CFG aware. It simply walks the > insn chain. To reorder BBs I use the following procedure: 1. cfg_layout_initialize (0); 2. FOR_EACH_BB(bb) set bb->rbi->next properly for each, so they all create a chain of BB 3. cfg_layout_finalize(); Does this reorder the insn chain? If not, how do I reorder it? Or where do I look for how it's done? G. -- Gregory B. Prokopski <[EMAIL PROTECTED]> Sable Research Group http://www.sable.mcgill.ca Montreal, Quebec, Canada
Extending jumps after block reordering
+++ Ian Lance Taylor [06/07/07 09:16 -0700]: > shorten_branches should work correctly--you shouldn't need to do > anything special. My only guess is that there is something wrong with > the way you are reordering the blocks. For example, perhaps you are > simply reordering the CFG without reordering the insn chain. Note > that shorten_branches is not (yet) CFG aware. It simply walks the > insn chain. > > I think that should work. Although it's bb->aux, not bb->rbi->next. > I'm not sure what bb->rbi is; which version of gcc are you using? It's the latest one now, so I have bb->aux. +++ Jim Wilson [09/07/07 15:36 -0700]: > that the main call to it is > shorten_branches (get_insns ()); > which runs it on the entire function. This is probably what you want. Recap: I am reordering the basic blocks in a special manner and it seems to be done properly, I do update the insns order after. The problem is on PPC some branches are too short to reach their targets which at assembly time results in assembler errors: Error: operand out of range (0x00017ef0 is not between 0x8000 and 0x7fff) In passes.c shorten_branches() is already run AFTER my pass (which is run just before pass_duplicate_computed_gotos). What I believe I need to do: a) find which branches cannot reach their destination, e.g. cond branches with relative addr, with targets beyond the maximum distance, b) split these branches into a cond branch to a non-cond branch, which should have a longer target span (create a new BB w/ non-cond branch to the target label and redirect the original branch to it) Questions: * shorten_branches() computes sizes of instructions so I know what the distance is between a jump instr and its target label. But how do I know what is the maximum distance each kind of branch can safely take? bb-reorder.c assumes that its only when cold/hot partitions are crossed it has to use indirect jumps, which is not the appropriate test in my case. * do I get it right that shorten_branches() does not really modify instructions but it helps to shorten branches by providing more accurate insns lengths? Thanks, Gregory -- Gregory B. Prokopski <[EMAIL PROTECTED]> Sable Research Group http://www.sable.mcgill.ca Montreal, Quebec, Canada
Re: Extending jumps after block reordering
+++ Eric Botcazou [02/11/07 09:56 +0100]: > > Questions: > > * shorten_branches() computes sizes of instructions so I know what the > > distance is between a jump instr and its target label. But how do I know > > what is the maximum distance each kind of branch can safely take? > > bb-reorder.c assumes that its only when cold/hot partitions are crossed > > it has to use indirect jumps, which is not the appropriate test in my case. > > You cannot easily, it's buried in the architecture back-ends. > > > * do I get it right that shorten_branches() does not really modify > > instructions but it helps to shorten branches by providing more accurate > > insns lengths? > > Yes, but this should work automatically. IOW, as Ian said, you shouldn't > need > to do anything special. Maybe it's simply a latent bug in the PPC back-end. Got it working. It turns out I was renumbering the instructions just before pass_final and it was messing up the creation of jump islands in PPC (and I believe other archs with short cond branches). I changed my code not to require the renumbering and it's all working now. Thanks a lot, Gregory -- Gregory B. Prokopski <[EMAIL PROTECTED]> Sable Research Group http://www.sable.mcgill.ca Montreal, Quebec, Canada
