Bowtie Part 2

Written by Hunter Jansen on November 25, 2014

This post continues on in my exploration of porting Bowtie from last post, so if you haven’t read that yet, you should probably start there.

With that little preface out of the way, let me say that I’ve actually made a bunch of progress - I’ll try to be succinct with what’s happened in the last few days since the previous post, but to be honest - it’s kinda a lot. If I had the time to sit down and post an intermediate entry, that would have been great - but here we are with me trying to remember all the steps I’ve taken to get to where I am today.

Github

After realizing that I actually get to work on Bowtie I figured I should check in on the git repository to see if the problem’s either already been addressed, or if like some other projects I’ve looked at, the source code’s changed drastically. I found the repo here. Aside from there being a minor version update, it didn’t look like anything was all that different. So, I forked and cloned the project and began to investigate to see if I could begin to nail down the problem and maybe even start to think of a solution.

Makefile stuff

I said in the last post that the -m64 flag was causing an issue in the makefile, which was the very first issue I needed to resolve. However, when I pulled the source in from github, a new issue arose; I received an error that told me that bowtie can only install on 64 bit systems.

‘Well that’s odd’, I thought to myself, ‘I’m ON a 64 bit system. Something must be funky.’ After a bit of digging around I found the following:

ifeq (1,$(LINUX))
    ifeq (x86_64, $(shell uname -p))
        BITS=64
    endif
endif

ifeq (32,$(BITS))
    $(error bowtie2 compilation requires a 64-bit platform )
endif

Huh, so unless I’m on an x86_64 machine, (or other platforms, it does work on windows and mac; this is just the check for linux) it thinks I’m on a 32 bit machine and thus won’t build. Neat. SO to resolve this, I added in another ifeq statement checking if the uname is aarch64, and if so make BITS=64.

ifeq (1,$(LINUX))
    ifeq (x86_64, $(shell uname -p))
        BITS=64
    endif
    ifeq (aarch64, $(shell uname -p))
        BITS=64
    endif
endif

I tried looking for an ‘or’ style way to deal with ifeq, but I couldn’t find one. it’s possible that there’s a more elegant solution to deal with the multiple conditions, but for now this is good enough. So NOW when making it with this adjustment, I run into the previous nondescript error that I ran into previously. I tracked that error down to this part a bit further down:

DEBUG_FLAGS = -O0 -g3 -m64
RELEASE_FLAGS = -O3 -m64

This is setting the various gcc flags for optimization and the -m64 flag that I mentioned before. So to get around this on aarch64 I did this:

ifeq (aarch64, $(shell uname -p))
    DEBUG_FLAGS = -O0 -g3
    RELEASE_FLAGS = -O3
else
    DEBUG_FLAGS = -O0 -g3 -m64
    RELEASE_FLAGS = -O3 -m64
endif


A simple solution that should solve the m64 flag problem. After I finished that off, that looks to be the end of my makefile adjustments (for now at least).

CPUID

Now that that’s solved, the build progresses further - progress! But at this point I’m receiving errors about exceptions in assembler code in a /third-party/cpuid.h file.

Checking inside that file, I discover a bunch of assembler for x84 dealing with the cpuid and returning either a 1 or a 0 depending on some stuff. So, I start investigating. . . It turns out that this file is actually an older version of the cpuid.h file included in gcc that’s been retained for no reason that anyone can think of and the community has actually asked for clarification for this choice a couple times. Upstream seems to have been unresponsive on this topic. So, this file was the source of my next investigation.

I began by removing the reference to that file in the compile command from last time and trying that on an x86 system and doing a couple checks. Everything seemed gravy from my quick tests, so I moved on to trying it on the arm machine, thinking that maybe gcc’s more updated version would have already addressed this issue.

Nope. A new slew of errors saying that cpuid.h is not defined, everything breaks

So after a lot of time searching for a simple, already implemented solution I came up with absolutely nothing regarding cpuid.h for gcc on arm. I reached out to my prof, and discovered that cpuid is an x86 only call. Neat! After further investigation, I found that the CPUid for aarch is kept in a register, but then I began to question what it was actually used for.

Digging into the file in question I eventually found that all the assembler in the file boils down to use in this one function:

static __inline int
__get_cpuid (unsigned int __level, unsigned int *__eax, unsigned int *__ebx, unsigned int *__ecx, unsigned int *__edx)
{
  unsigned int __ext = __level & 0x80000000;

  if (__get_cpuid_max (__ext, 0) < __level)
    return 0;

  __cpuid (__level, *__eax, *__ebx, *__ecx, *__edx);
    return 1;
}

So it returns either 1 or 0, I reckon it’s a flag of some sort, but I haven’t yet the chance to dig into what it’s actually used for. However, I figured that since cpuid isn’t so much used in aarch the same way that it’s needed for x86 (there’s not the backwards compatibility issues that x86 need to take into account) that to try to get everything working and progressing, I’d just always have this function return 1.

This involved commenting out all the assembler code in the rest of the file and changing the file to:

static __inline int
__get_cpuid (unsigned int __level, unsigned int *__eax, unsigned int *__ebx, unsigned int *__ecx, unsigned int *__edx)
{
  unsigned int __ext = __level & 0x80000000;

 // if (__get_cpuid_max (__ext, 0) < __level)
  //  return 0;

 // __cpuid (__level, *__eax, *__ebx, *__ecx, *__edx);
  return 1;
}

Now obviously, should this be part of a working solution, I’ll toss in some ifdef statements to properly handle this, but for now it’s just to see if this can contribute to making everything work on arm.

EBTW

The above steps got me even FURTHER in the compile steps! But now I’m hit with a new error:

/tmp/ccqEjsKY.s: Assembler messages:
/tmp/ccqEjsKY.s:6723: Error: unknown mnemonic `popcntq' -- `popcntq x3,x10'
/tmp/ccqEjsKY.s:6753: Error: unknown mnemonic `popcntq' -- `popcntq x3,x8'
/tmp/ccqEjsKY.s:18031: Error: unknown mnemonic `popcntq' -- `popcntq x3,x4'
/tmp/ccqEjsKY.s:18074: Error: unknown mnemonic `popcntq' -- `popcntq x3,x9'


Aww jeez, what the heck is this mess o.O? After some more poking around, I find that the only reference to popcntq in all of the source is in the ebtw.h file. So let’s check it out.

In here, I find the reference to popcntq:

#ifdef POPCNT_CAPABILITY
    struct USE_POPCNT_INSTRUCTION {
        inline static int pop64(uint64_t x) {
            int64_t count;
            asm ("popcntq %[x],%[count]\n": [count] "=&r" (count): [x] "r" (x));
            return count;
        }
    };
#endif

Oki doke - after some research I find that popcntq is x86_64 syntax and the syntax for arm64 is just popcntq. So I tried changing that, but it still didn’t work appropriately. Investigating further, I discovered that there’s a builtin gcc version of popcount. I’m a fan of functions already built into compilers when they’ve been manually written in assembler, because it PROBABLY means that it’s been done better and more universally than the handwritten assembler. So I tried replacing the assembler with the builtin version:

#ifdef POPCNT_CAPABILITY
    struct USE_POPCNT_INSTRUCTION {
        inline static int pop64(uint64_t x) {
            int64_t count;
            count = __builtin_popcount(x);
                //asm ("popcnt %[x],%[count]\n": [count] "=&r" (count): [x] "r" (x));
            return count;
        }
    };
#endif

I need to double check to make sure that that does essentially the same thing as the inline, but for now we’ll leave it at that. Let’s try our make again.

. . . The make takes a lot longer at this point, filling me with hope. . . .

When it’s finally finished, I try running a basic test using the built in e-coli genome:

./bowtie e_coli reads/e_coli_1000.fq

HOLY MOLY, it works!

But just to be sure, I decided to remove the bowtie file and make again. When I try to make I get the answer: Nothing to be done for ‘all’.

Hmm, that’s weird; why won’t it make my bowtie?

So I ended up removing all the other bowtie related programs that the makefile should make (bowtie-build and bowtie-inspect). Following this, I run make again - again, it takes a long time to complete. When it’s finished this time around I run the ls command and there’s no ‘bowtie’ command anywhere. Thinking perhaps there’s a fluke or something I’ve missed, I try making again; Nothing to be done for all. Clearly something’s up, and bowtie’s either failing its build or being put somewhere else. SOooo it’s back to the :

Makefile . . . Again

When I was playing around in the makefile earlier, I took note of where it was setting up the command to compile the bowtie program (Some of my early debugging brought me here). I discovered a weird difference between the git version I’d pulled and the version from the fedpkg code that I’d pulled before. The fedpkg version has:

BIN_LIST = bowtie-build \
           bowtie \
           bowtie-inspect

AND FURTHER DOWN

bowtie: ebwt_search.cpp $(SEARCH_CPPS) $(OTHER_CPPS) $(HEADERS) $(SEARCH_FRAGMENTS)
        $(CXX) $(RELEASE_FLAGS) $(RELEASE_DEFS) $(ALL_FLAGS) \
                $(DEFS) $(NOASSERT_FLAGS) -Wall \
                $(INC) \
                -o $@ $< \
                $(OTHER_CPPS) $(SEARCH_CPPS_MAIN) \
                $(LIBS) $(SEARCH_LIBS)

But the github version has neither. Which I thought was quite queer, how are you supposed to tie your bows without a bowtie? So for testing sake, I added it back into the Makefile. After another make, bowtie was there!

So I ran through the e-coli test again and a couple other steps in the getting started guide and they’ve all worked so far! I was so happy I stood up and breathed a sigh of relief when it all started working. I think everyone else in class was too entrenched in their own mind crushing work to notice, but it was a big victory for me; FINALLY a project I could work on AND results.

Next

So there’s a few things I need to do next. Here they are in no specific order:

  • Reach out to upstream, introduce myself and ask why the build part of the Makefile is gone
  • Fix up the code to include ifdefs instead of the currently commented out and overwritten solutions I have
  • Test - Benchmark on x86 before and after to make sure my changes haven’t negatively effected anything
  • Test - Find as many test scenarios as I can to make sure that they all behave the same on each architecture
  • Create a pull request

I’m pretty excited about the progress I’ve made so far, quite a change from the frustration of the last few weeks

Until next time -Hunter