Q:

Why does GNU make always re-link my project? 

I have the following Makefile in a directory full of .cpp and .h files:
CFLAGS=-g -std=c++0x -Wall -pedantic -Wextra -D __STDC_LIMIT_MACROS -D __STDC_FORMAT_MACROS -O0
CXX=g++
LDFLAGS=-lgmp -lmathsat -lz3

all: Foo.o Bar.o
        $(CXX) $(CFLAGS) -o myexe Foo.o Bar.o $(LDFLAGS)

depend: .depend

.depend: $(wildcard *.cpp)
        rm -f ./.depend
        $(CXX) $(CFLAGS) -MM $^ > ./.depend

include .depend

%.o: %.cpp
        $(CXX) $(CFLAGS) $(INCLUDE) $< -c

clean:
        rm -f *.o myexe

When I hit make, it invariably executes the last step (linking) even when none of the .o files have changed.  How can I prevent make from doing that?  I'd expect make to output Everything up-to-date or something similar. 
I'm on a i686 GNU/Linux machine with GNU Make 3.82 and g++ version 4.8.2. 

A:

Make relinks your project because it tries to build all.  The rule for all does not create any file named all.  Instead it produces myexe.  Next time you run make, it will see that there's no all, but there's a rule to build one, so it dutifully executes that rule which happens to link myexe every time you run make.  
In order to fix your problem you need to change your makefile to look roughly like this:
all: myexe
    echo Build done

myexe: <myexe dependencies go here>
    $(CXX) $(CFLAGS) -o myexe $(wildcard *.o) $(LDFLAGS)

A:

Make always tries to build the top rule.  For you, this is all.  Since your all rule doesn't actually make an all file it will always be run. 
Your probably want your all rule to be a myexe rule and, if you want an explicit all rule, have a dependency only rule: all: myexe. 
(With GNU Make, you might want to explicitly declare those targets which aren't supposed to generate a real file with a .PHONY rule.  e.g. .PHONY: all depend clean.) 

A:

make is a rule-based expert system. 
You give it a heap of rules and a target (default target is the first one listed), and then it builds a complete dependency tree. 
All parts are rebuilt iff they are non-existent resp.  older than their dependencies, recursively. 
The rule you are stumbling over is this: Because the target all does not create an output file all, make invokes the non-existent-or-outdated rule. 
You can correct this by making the target all not do any work but instead just depend on the output file.  Marking it .PHONY is also a good idea.