こちらでも Rust(rustc)=C(gcc)>>>C(clang) となった
gccとrustcが同じ最適化をしてると思われる
確認のためLLVM IRを吐くrustcとclangでどのようにコードが異なるか調べてみた

まずclangによるLLVM IR生成
$ clang -S -emit-llvm -O2 -o fibonacci_cl.ll fibonacci.c
そのうちfibonacci()関数部分を抜粋すると以下のコードとなった

; Function Attrs: nounwind readnone uwtable
define dso_local i32 @fibonacci(i32 %0) local_unnamed_addr #0 {
　%2 = icmp ult i32 %0, 2
　br i1 %2, label %9, label %3

3: ; preds = %1
　%4 = add nsw i32 %0, -2
　%5 = tail call i32 @fibonacci(i32 %4)
　%6 = add nsw i32 %0, -1
　%7 = tail call i32 @fibonacci(i32 %6)
　%8 = add nsw i32 %7, %5
　ret i32 %8

9: ; preds = %1
　ret i32 %0
}

元のCコードそのままでnが2未満すなわち0と1の時はそのまま返して
それ以外は fibonacci(n-2) + fibonacci(n-1) を返している
最適化をしていないのでclangがgccよりも遅いのはこれで納得