[LLVMdev] problem trying to write an LLVM register-allocation pass
Susan Horwitz
horwitz at cs.wisc.edu
Fri Nov 9 11:15:46 PST 2012
Thanks Lang, we are making progress! I no longer get the failed
assertion, but the code I'm using for vregs that don't get allocated a
preg, and thus need to be spilled and re-loaded is causing assembler errors.
I suspect the problem is my code for allocating space in the stack, but
I don't know how to fix it.
I've attached a new version of the simple register-allocation code, a
test program that causes the bad assembler to be produced, and the bc
file. (I had to name everything with a .txt extension to copy the files
to my laptop.)
As always, thank you for your help!
Susan
On 11/7/2012 7:31 PM, Lang Hames wrote:
> Hi Susan,
>
> In x86-64 the REX prefix must be used to access an extended register
> (r8-r15 and their aliases), but cannot be used when accessing the high
> byte of the ABCD regs (AH, BH, CH, DH). In your test case you have
> hardcoded %vreg1 to R8B, and %vreg15 to AH, and the test case contains
> a copy between these registers. The copy simultaneously must have a
> REX prefix, and cannot have a REX prefix, hence the assertion.
>
> The problem is that not all registers in a class are allocable for all
> vregs. As you can see from the above constraint, which pregs are valid
> varies dynamically depending on the context that the register is used.
> The trick is to query the "allocation order" for a class (and as an
> added headache filter out any reserved registers). I've attached a
> test-case where I do this somewhat manually. In short:
>
> int regClass = MRI->getRegClass(vreg)->getID();
> const TargetRegisterClass *trc = TRI->getRegClass(regClass);
> ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(Fn);
> ArrayRef<uint16_t>::iterator rItr = rawOrder.begin();
> while (reservedRegs.test(*rItr))
> ++rItr;
> preg = *rItr;
>
> Alternatively, you could use the AllocationOrder class
> (lib/CodeGen/AllocationOrder.h). This has the benefit of considering
> register hints for improved coalescing too. It does, however, require
> you to use VirtRegMap.
>
> Hope this helps!
>
> Cheers,
> Lang.
>
>
>
> On Wed, Nov 7, 2012 at 2:56 PM, Lang Hames <lhames at gmail.com
> <mailto:lhames at gmail.com>> wrote:
>
> Hi Susan,
>
> Sorry for the delayed response. Thanks for the test cases - I'm
> looking in to this now.
>
> - Lang.
>
>
> On Mon, Nov 5, 2012 at 2:58 PM, Susan Horwitz <horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>> wrote:
>
> Hi Lang,
>
> I looked more into one of the problems I'm now having, and
> I've attached 3 files:
>
> Gcra.cpp is like your version except that for two specific
> vregs it uses hard-coded pregs instead of the first in the
> corresponding class.
>
> bug1.c is an input that causes the failed assertion for me.
> If I use the non-debug version of LLVM-3.1 I instead get
> assembler errors like this:
> Error: can't encode register '%ah' in an instruction
> requiring REX prefix.
>
> bug1.bc is my bitcode version of bug1.c.
>
> The problematic vregs are both in register class 0. One is
> replaced with preg 1 and the other with preg 74. Those are
> both in register class 0, and are not aliased. Any idea why
> using those pregs causes trouble?
>
> Thanks!
>
> Susan
>
>
> On 11/04/2012 06:19 PM, Lang Hames wrote:
>
> Hi Susan,
>
> With your bitcode file I am now able to reproduce the
> issue you're
> seeing. It looks like this is a problem with the naive
> rewriting from
> virtregs to physregs. It appears that the subreg field of
> physreg
> operands is ignored post-register allocation. In your testcase
> %vreg11:sub32 is being rewritten to RBX:sub32, but the
> :sub32 part is
> being quietly dropped when the assembly is written out. If
> this is
> expected behaviour, and is still happening in the
> development branch,
> then I'll add some sort of verification to catch it.
>
> The VirtRegMap::rewrite() method sidesteps this issue by
> rewriting
> physreg operands to remove the subreg field. The code for
> this is in
> VirtRegMap.cpp, around line 165. In short:
>
> PhysReg = MO.getReg();
> if (MO.getSubReg() != 0) {
> PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg());
> MO.setSubReg(0);
> }
> MO.setReg(PhysReg);
>
> Adding this code to Gcra fixes the assembly issue for me.
> I've attached
> my updated copy. Hope this helps.
>
> Cheers,
> Lang.
>
>
> On Sun, Nov 4, 2012 at 2:08 PM, Susan Horwitz
> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu>>>
> wrote:
>
> My tst.bc is attached. I had to use ssh to copy it
> from my office
> machine to my home laptop. In case that corrupts it,
> I also put a
> copy here:
> http://pages.cs.wisc.edu/~horwitz/LANG/tst.bc
> <http://pages.cs.wisc.edu/%7Ehorwitz/LANG/tst.bc>
>
> I created the file like this:
>
> clang -emit-llvm -O0 -c tst.c -o tst.bc
> opt -mem2reg tst.bc > tst.mem2reg
> mv tst.mem2reg tst.bc
>
>
> Susan
>
>
> On 11/4/2012 3:27 PM, Lang Hames wrote:
>
> Hi Susan,
>
> I tested the version of Gcra.cpp that I sent you
> on x86-64 systems
> running MacOS 10.8 and Ubuntu 12.04 (Linux 3.2.0).
>
> Could you send me the bitcode file you're
> compiling? Different
> bitcodes (due to different clang versions or applied
> optimizations) could account for the different
> results we're
> seeing. For reference I've attached the *.ll file
> that I have
> tested with, which was compiled from your tst.c
> file with:
>
> clang -O0 -emit-llvm -S -o tst.ll tst.c
>
> My clang version was built from a recent checkout
> from subversion.
>
> It's unlikely that there is any fundamental
> problem with the
> register allocation APIs or the code generator
> that would prevent
> you from building a working allocator. The APIs
> certainly could
> have changed in a way that would break existing
> allocators though.
>
> - Lang.
>
>
> On Sat, Nov 3, 2012 at 4:34 PM, Susan Horwitz
> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>> wrote:
>
> Lang -
>
> Your version does NOT work for me (i.e., I
> still get an error
> from the assembler when I run your code on my
> tst.c) unless I
> force compilation and assembly for a 32-bit
> X86 machine:
>
> llc -march=x86 -regalloc=gc tst.bc
> gcc -m32 tst.s
>
> My machine is a 64-bit machine. Maybe you are
> working with a
> different architecture and that's why it
> worked for you?
>
> I would be happy if the above worked in
> general, but when I
> try other C code (with my "real" register
> allocator, not the
> naive one I sent you) I get assembly that includes
>
> %r8d
>
> which seems to be invalid for a 32-bit
> machine. Sigh. It
> looks to me like there's a problem with the
> LLVM-3.1 API for
> register allocation and/or the code-generation
> phase. What do
> you think?
>
> Susan
>
>
> On 11/1/2012 5:28 PM, Lang Hames wrote:
>
> Hi Susan,
>
> Without debugging symbols I can't make
> much out of that stack
> trace I'm afraid.
>
> I've attached my modified version of
> Gcra.cpp. I built llvm
> 3.1 by dropping this file into
> lib/CodeGen, and adding
> references to createGcra to
> include/lib/CodeGen/Passes.h and
>
> include/lib/CodeGen/LinkAllCodeGenComponents.h.
> (If you
> search for createRegAllocPBQP you'll see
> where to add the
> declarations).
>
> With that setup, running your allocator on
> the tst.c file you
> attached previously yielded a sane
> assembly file.
>
> Cheers,
> Lang.
>
> On Thu, Nov 1, 2012 at 3:13 PM, Susan Horwitz
> <horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>> wrote:
>
> I still get a coredump:
>
> 0 libLLVM-3.1.so
> <http://libLLVM-3.1.so> <http://libLLVM-3.1.so>
> 0x00007f0158a4e67f
> 1 libLLVM-3.1.so
> <http://libLLVM-3.1.so> <http://libLLVM-3.1.so>
> 0x00007f0158a500ca
> 2 libpthread.so.0 0x0000003a86c0f500
>
> 3 libLLVM-3.1.so
> <http://libLLVM-3.1.so> <http://libLLVM-3.1.so>
> 0x00007f01583c346c
> 4 libLLVM-3.1.so
> <http://libLLVM-3.1.so> <http://libLLVM-3.1.so>
> 0x00007f0158546349
>
> llvm::FPPassManager::runOnFunction(llvm::Function&) +
> 521
> 5 libLLVM-3.1.so
> <http://libLLVM-3.1.so> <http://libLLVM-3.1.so>
>
> 0x00007f01585463e3
>
> llvm::FPPassManager::runOnModule(llvm::Module&) + 51
> 6 libLLVM-3.1.so
> <http://libLLVM-3.1.so> <http://libLLVM-3.1.so>
>
> 0x00007f0158545fae
>
> llvm::MPPassManager::runOnModule(llvm::Module&) + 462
> 7 libLLVM-3.1.so
> <http://libLLVM-3.1.so> <http://libLLVM-3.1.so>
>
> 0x00007f01585460bd
>
> llvm::PassManagerImpl::run(llvm::Module&) + 125
> 8 llc 0x000000000040b012 main + 5218
> 9 libc.so.6 0x0000003a8601ecdd
> __libc_start_main + 253
> 10 llc 0x0000000000407d79
> Stack dump:
> 0. Program arguments: llc -load
> Debug/lib/P4.so
> -regalloc=gc tst.bc
> 1. Running pass 'Function Pass
> Manager' on module
> 'tst.bc'.
> 2. Running pass 'Machine Loop
> Invariant Code Motion'
> on function '@main'
> make: *** [tst.reg] Segmentation fault
> (core dumped)
>
>
>
> On 11/01/2012 04:59 PM, Lang Hames wrote:
>
> Hi Susan,
>
> Sorry - I had missed that you're
> using llvm-3.1,
> rather than the
> development branch. We encourage
> people to live on
> top-of-tree - it's
> well tested, easier for active
> developers to offer
> help with, and
> keeping up with incremental
> changes is often easier
> than porting between
> stable versions.
>
> It also sounds like you were
> building a Release
> version of LLVM. That
> will not have any asserts enabled
> (though it will
> have some other
> diagnostics). You will probably
> want to work with a
> Debug+Asserts
> version (<src>/configure
> --disable-optimized
> --enable-assertions) while
> you're developing your allocator
> and watch for any
> asserts that trigger.
>
> In your case the Assertion that is
> triggering in PEI
> indicates that the
> MachineRegisterInfo object still
> contained some
> virtregs post
> register-allocation. You need to call
> MRI->clearVirtRegs() at the end of
> your allocator.
>
> Hope this helps!
>
> Cheers,
> Lang.
>
> On Thu, Nov 1, 2012 at 2:41 PM,
> Susan Horwitz
> <horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>>> wrote:
>
> Hi again Lang,
>
> I decided to try the approach
> you proposed to see
> whether it makes
> the assembly-code problem go
> away. Again, I
> tried a very simple
> register allocator (attached)
> that just calls
> vrm.assignVirt2Phys
> for every vreg in each
> function, mapping the vreg
> to the first preg
> in the register class. I
> tried two versions: one
> maps *every* vreg,
> and the other only maps those
> for which
> MRI->reg_empty(vreg) returns
> false. In both cases I get a
> core dump somewhere
> after my
> reg-allocation pass has run
> (when I use the
> "tst.c" file that I sent
> last time as input).
>
> Note also that there is no
> VirtRegMap.h in the
> "include" directory
> of my installed llvm-3.1. I
> had to copy that
> file from the source
> directory. That seems suspicious.
>
> Any thoughts?
>
> Thanks!
>
> Susan
>
>
> On 10/31/2012 07:51 PM, Lang
> Hames wrote:
>
> Hi Susan,
>
> I'm having trouble
> reproducing that error on
> my end, but I think the
> problem is probably that
> you're not using the
> VirtRegRewriter
> infrastructure. What your
> allocator needs to
> do is populate the
> virtual
> register mapping
> (VirtRegMap pass) with your
> allocation, rather than
> rewriting the registers
> directly through
> MachineRegisterInfo.
>
> Have your allocator
> require and preserve the
> VirtRegMap pass,
> then in
> your runOnMachineFunction
> pass grab a
> reference to the pass with:
>
> VirtRegMap &vrm =
> getAnalysis<VirtRegMap>();
>
> You can then describe your
> register
> allocations with:
>
> vrm.assignVirt2Phys(<virtreg>, <physreg>)
>
> The VirtRegRewriter pass
> (in VirtRegMap.cpp)
> will run after your
> allocator and apply the
> mapping that you
> described in the
> VirtRegMap.
>
> I hope this helps. Let me
> know if it doesn't
> fix your issue.
>
> Cheers,
> Lang.
>
> On Wed, Oct 31, 2012 at
> 3:54 PM, Susan Horwitz
> <horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>>>> wrote:
>
> Thanks Lang!
>
> Here's another
> question: I'm trying to
> process this input:
>
> int main() {
> return 0;
> }
>
> but I'm getting an error
> Assertion
> `!Fn.getRegInfo().
> getNumVirtRegs() &&
> "Regalloc must
>
> assign all vregs"'
> failed.
>
> At the start of
> runOnMachineFunction I
> call Fn.getRegInfo().
> getNumVirtRegs();
> and find that there
> is 1 virtual
> register. However,
> MRI->reg_empty(vreg)
> tells me that it is
> not used or defined.
> So my
> register-allocation
> code never sees it,
> and thus can't
> allocate a preg for it.
> I tried
> using
> MRI->replaceRegWith(vreg, preg);
> (where preg is
> available to vreg's
> register class) but that
> didn't
> work. When I look,
> the number of vregs
> in the function is
> still 1.
>
> Can you help with this?
>
> Thanks again!
>
> Susan
>
>
> On 10/31/2012 04:55
> PM, Lang Hames wrote:
>
> Hi Susan,
>
> The meaning of
> "addRequired(X)" is
> that your pass needs
> X to be
> run, and
> for X to be
> preserved by all passes
> that run after X
> and before your
> pass. The
> PHIElemination and
> TwoAddressInstruction
> passes do not
> preserve each other, hence there's
> no way for the pass
> manager to
> schedule them for you if you
> addRequire(...) them.
>
> The trick is that
> CodeGen will
> schedule both of these
> passes to
> be run
> before _any_
> register allocation
> pass (see Passes.cpp),
> so you
> needn't
> require them
> explicitly - you can
> just assume they have
> been
> run. If you
> just remove those
> lines from your
> getAnalysisUsage
> method your pass
> should now run as
> you expect.
>
> Cheers,
> Lang.
>
> On Wed, Oct 31,
> 2012 at 1:46 PM,
> Susan Horwitz
> <horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>
> <mailto:horwitz at cs.wisc.edu
> <mailto:horwitz at cs.wisc.edu>>>>>> wrote:
>
> I'm trying to write a
> MachineFunctionPass to do
> register
> allocation.
> I have code that worked with
> an old version of
> LLVM. It
> does not
> work with llvm-3.1. (or various
> other versions
> that I've
> tried).
>
> The first problem is that
> including this line:
>
> AU.addRequiredID(__
> TwoAddressInstructionPassID);
>
>
> in method
> getAnalysisUsage
> causes a runtime error:
>
> Unable to schedule 'Eliminate
> PHI nodes for register
> allocation'
> required by 'Unnamed pass:
> implement
> Pass::getPassName()'
> Unable to schedule pass
> UNREACHABLE executed at ...
>
> I'm invoking the pass like this
> (given input file
> foo.c):
>
> clang -emit-llvm -O0 -c foo.c
> -o foo.bc
> opt -mem2reg foo.bc > foo.ssa
> mv foo.ssa
> foo.bc
> llc -load Debug/lib/P4.so
> -regalloc=gc foo.bc
>
>
> I've attached my entire file
> (it's very short).
> Any help
> would be
> much appreciated!
>
> Susan Horwitz
>
> ______________________________
> _________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>>>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>>>>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>>>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>
> <mailto:LLVMdev at cs.uiuc.edu
> <mailto:LLVMdev at cs.uiuc.edu>>>>>
>
> http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/ mailman/listinfo/llvmdev
>
> <http://lists.cs.uiuc.edu/__mailman/listinfo/llvmdev
>
> <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121109/898417a3/attachment.html>
-------------- next part --------------
//===-- Gcra.cpp - Graph-coloring Register Allocator --------------------===////// The LLVM Compiler Infrastructure//// This file is distributed under the University of Illinois Open Source// License. See LICENSE.TXT for details.////===--------------------------------------------------------------------===////// This file does Graph-coloring Register Allocation, for CS 701 Project 4.////===--------------------------------------------------------------------===//#define DEBUG_TYPE "gcra"#include <map>#include "llvm/CodeGen/Passes.h"#include "llvm/CodeGen/MachineFunctionPass.h"#include "llvm/CodeGen/MachineInstr.h"#include "llvm/CodeGen/MachineLoopInfo.h"#include "llvm/CodeGen/MachineFrameInfo.h"#include "llvm/CodeGen/MachineRegisterInfo.h"#include "llvm/CodeGen/RegAllocRegistry.h"#include "llvm/Target/TargetInstrInfo.h"#include "llvm/Target/TargetMachine.h"#include "llvm/Support/Debug.h"#include "llvm/Support/Compiler.h"#include "llvm/ADT/Statistic.h"#include <stack>#include <queue>#include <iostream>using namespace std;using namespace llvm;namespace { class Gcra : public MachineFunctionPass { private: MachineRegisterInfo *MRI; const TargetRegisterInfo *TRI; MachineFunction *MF; const TargetMachine *TM; const TargetInstrInfo *TII; static const bool DEBUG_VREG = true; map<MachineInstr *, unsigned> InstrToNumMap; public: static char ID; // Pass identification, replacement for typeid //********************************************************************** // constructor //********************************************************************** Gcra() : MachineFunctionPass(ID) { } //********************************************************************** // runOnMachineFunction //********************************************************************** bool runOnMachineFunction(MachineFunction &Fn) { if (DEBUG_VREG) { std::cerr << "START " << Fn.getFunction()->getName().str() << "\n"; } // get pointers to stuff that doesn't change over this fn // e.g., the register info classes MRI = &Fn.getRegInfo(); TRI = Fn.getTarget().getRegisterInfo(); MF = &Fn; TM = &Fn.getTarget(); TII = TM->getInstrInfo(); // STEP 1: get instruction-to-number map doInit(Fn); // STEP 2: get all vregs in this fn std::set<unsigned> vregSet = getAllVreg(Fn); // STEP 3: handle all vregs setAllVreg(Fn, vregSet); return true; } virtual void getAnalysisUsage(AnalysisUsage &AU) const { MachineFunctionPass::getAnalysisUsage(AU); } private: //********************************************************************** // doInit // // fill in // InstrToNumMap: map from instruction to unique # (for debugging) //********************************************************************** void doInit(MachineFunction &Fn) { // iterate over all basic blocks, all instructions in a block, // all operands in an instruction int insNum = 1; for (MachineFunction::iterator MFIt = Fn.begin(), MFendIt = Fn.end(); MFIt != MFendIt; MFIt++) { for (MachineBasicBlock::iterator MBBIt = MFIt->begin(), MBBendIt = MFIt->end(); MBBIt != MBBendIt; MBBIt++) { //*MBBIt is a MachineInstr InstrToNumMap[MBBIt] = insNum; insNum++; } // end iterate over all instructions in 1 basic block } // end iterate over all basic blocks in this fn } // end doInit //********************************************************************** // getAllVreg // // find and return the set of all vregs that occur in instructions // in this function // ********************************************************************** std::set<unsigned> getAllVreg(MachineFunction &Fn) { std::set<unsigned> vregSet; // vregs defined in this fn vregSet.clear(); // iterate over all basic blocks, all instructions in a block, // all operands in an instruction for (MachineFunction::iterator MFIt = Fn.begin(), MFendIt = Fn.end(); MFIt != MFendIt; MFIt++) { for (MachineBasicBlock::iterator MBBIt = MFIt->begin(), MBBendIt = MFIt->end(); MBBIt != MBBendIt; MBBIt++) { int numOp = MBBIt->getNumOperands(); for (int i = 0; i < numOp; i++) { MachineOperand MOp = MBBIt->getOperand(i); if (MOp.isReg() && MOp.getReg()) { unsigned reg = MOp.getReg(); // Here if this operand is // (a) a register // (b) not special reg 0 if (TargetRegisterInfo::isVirtualRegister(reg)) { vregSet.insert(reg); } } // end if operand is a reg } // end iterate over operands } // end iterate over instructions } // end iterate over blocks return vregSet; } //********************************************************************** // setAllVreg // // for each vreg in the given set: // 1. Allocate stackspace // 2. iterate over all instructions in this fn // for each, iterate over all operands // if an operand is a vreg // then set it to an appropriate preg and add a load/spill // depending on whether the vreg was a def or a use //********************************************************************** void setAllVreg(MachineFunction &Fn, std::set<unsigned> vregSet) { for (std::set<unsigned>::iterator it = vregSet.begin(); it != vregSet.end(); it++) { unsigned vreg = *it; // Allocate a new stack object for this vreg const TargetRegisterClass *RC = MRI->getRegClass(vreg); MachineFunction *MF = &Fn; int frameIndex = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), RC->getAlignment()); // iterate over all basic blocks, all instructions in a block, // all operands in an instruction for (MachineFunction::iterator MFIt = Fn.begin(), MFendIt = Fn.end(); MFIt != MFendIt; MFIt++) { for (MachineBasicBlock::iterator MBBIt = MFIt->begin(), MBBendIt = MFIt->end(); MBBIt != MBBendIt; MBBIt++) { MachineInstr *oneInst = MBBIt; MachineBasicBlock *parentBlock = oneInst->getParent(); int numOp = MBBIt->getNumOperands(); unsigned preg = -1; // iterate over the operands in this instruction for (int i = 0; i<numOp; i++) { MachineOperand &MOp = MBBIt->getOperand(i); if (MOp.isReg() && (MOp.getReg() == vreg)) { // found an instance of the crrent vreg // replace it with an appropriate preg // then add a load or store depending on whether // it is a use or a def if (preg == -1) { // get an appropriate preg for vreg int regClass = MRI->getRegClass(vreg)->getID(); const TargetRegisterClass *trc = TRI->getRegClass(regClass); TargetRegisterClass::iterator rItr = trc->begin(); preg = *rItr; // remove the sub-register field if (MOp.getSubReg()) { preg = TRI->getSubReg(preg, MOp.getSubReg()); MOp.setSubReg(0); } } // end we didn't have a preg yet for this instruction // replace vreg with preg MOp.setReg(preg); // add a store after curr instruction or a load before if (MOp.isDef()) { MachineBasicBlock::iterator IT = oneInst; IT++; TII->storeRegToStackSlot(*parentBlock, IT, preg, true, frameIndex, RC, TRI); } else { TII->loadRegFromStackSlot(*parentBlock, oneInst, preg, frameIndex, RC, TRI ); } // end if this was a def... else... } // end found an instance of curr vreg } // end iterate over all operands in this instruction } // end iterate over all instructions in 1 basic block } // end iterate over all basic blocks in this fn } // end iterate over all vregs in this fn MRI->clearVirtRegs(); } // end setAllVreg }; // The library-inclusion mechanism requires the following: char Gcra::ID = 0; FunctionPass *createGcra() { return new Gcra(); } static RegisterRegAlloc register_gcra("gc", "graph-coloring register allocator", createGcra);}
-------------- next part --------------
/* CAUSES UNREACHABLE executed error */
#include <stdlib.h>
int main(int argc, char **argv) {
int a, b, c, x, y, z;
x = rand();
printf("x: %d\n", x);
while (x > 1000) x = x/1000;
printf("x: %d\n", x);
y = x + 5;
z = x * 2 - 1;
a = x+y*z;
b = a/x - (5+y);
c = a+b+x+y+z;
printf("a: %d\nb: %d\nc: %d\nx: %d\ny: %d\nz: %d\n", a,b,c,x,y,z);
}
-------------- next part --------------
BCÀÞ!
ñ ?#?AÈI29??
%
?b?EB?
B¤28I
2D$H
?!#ÄR?
!r$ÈHb¨ ¨@Æð I
?ÿÿÿÿ ÀA?Âÿÿÿÿ` ? 2"H d??"¤??"ã?¡?L??
?¤LDsH
YhÌ?2e(å*A!U?b?M? Ì 0|À;ø; ?6¨wXwx?{p?6`?tp?zÀ?68w¨?
1Qm z`t v@z`tÐéz?z?m?x x xÐév q`zvÐé0r s z0rÐé`t v@z`tÐæ0r s z0rÐæ`t v@z`tÐö`t v@z`tÐör?zr?zr?mp p v@m0p v@z`tÐæ?p q x q xÐî?zv s z`tгr?:dH #DB?
?I @°#!?# ?( 0DY? ?!J d? 2
?
L?? &GÆC
jàu YACÉ ¬?È
±T"+Æ:P?¬Àë@%²"¯?È
½T"+ y
3?
Äá
f=?C8?Ã?B?yxs?q
æ íô?3
B
ÂÁ
Ρ
q F`<ÒL?
?46 at D@3 áKSd?/MQ
a I D, TF
ú¡? È
e@?ÉPI? #?
# 4K
T@ Ã
?b³
Â0?¤Ð,A0bP áH&- 0??]MÌÂD`R?Ò$²Å?m\Lë@`?û,` 1P ?x´.
$
Ë$
% ÆA Ã ?
o 0
ý (Ö?,? 8fÃåÓv@ ?!ØÄ 0?Q
RYÁPËm0
?1HTp?u
á
N3XH
C][D! ËR[E! ËbDFeC-PÍaR ÃPÓÖAHT°Û1 Un? ,?iÀ0à7?X²>Ñ
&bÀ²Ô6
More information about the llvm-dev
mailing list