12

gcc オプティマイザーを使用して効率的な x86-64 コードにコンパイルする、符号付き飽和 64 ビット加算用の C コードを探しています。移植可能なコードが理想的ですが、必要に応じて asm ソリューションを使用することもできます。

static const int64 kint64max = 0x7fffffffffffffffll;
static const int64 kint64min = 0x8000000000000000ll;

int64 signed_saturated_add(int64 x, int64 y) {
  bool x_is_negative = (x & kint64min) != 0;
  bool y_is_negative = (y & kint64min) != 0;
  int64 sum = x+y;
  bool sum_is_negative = (sum & kint64min) != 0;
  if (x_is_negative != y_is_negative) return sum;  // can't overflow
  if (x_is_negative && !sum_is_negative) return kint64min;
  if (!x_is_negative && sum_is_negative) return kint64max;
  return sum;
}

書かれている関数は、いくつかの分岐を持つかなり長いアセンブリ出力を生成します。最適化に関するヒントはありますか? ADDいくつかの指示だけで実装できるはずCMOVですが、私はこのようなものに少し慣れていません。

4

4 に答える 4

13

これはさらに最適化される可能性がありますが、ここに移植可能なソリューションがあります。未定義の動作は発生せず、整数オーバーフローが発生する前にチェックします。

#include <stdint.h>

int64_t sadd64(int64_t a, int64_t b)
{
    if (a > 0) {
        if (b > INT64_MAX - a) {
            return INT64_MAX;
        }
    } else if (b < INT64_MIN - a) {
            return INT64_MIN;
    }

    return a + b;
}
于 2013-07-10T22:57:37.610 に答える
8

これは、コメントの 1 つに記載されていた流れに沿ったソリューションであり、ouah のソリューションでも使用されています。ここで、生成されたコードは条件付きジャンプなしである必要があります

int64_t signed_saturated_add(int64_t x, int64_t y) {
  // determine the lower or upper bound of the result
  int64_t ret =  (x < 0) ? INT64_MIN : INT64_MAX;
  // this is always well defined:
  // if x < 0 this adds a positive value to INT64_MIN
  // if x > 0 this subtracts a positive value from INT64_MAX
  int64_t comp = ret - x;
  // the condition is equivalent to
  // ((x < 0) && (y > comp)) || ((x >=0) && (y <= comp))
  if ((x < 0) == (y > comp)) ret = x + y;
  return ret;
}

最初のものは、実行する条件付きの動きがあるかのように見えますが、特別な値のために、私のコンパイラは追加で終了します: 2 の補数INT64_MININT64_MAX+1. 何も問題がない場合に備えて、合計を割り当てるための条件付き移動は 1 つだけです。

抽象状態マシンでは、オーバーフローがない場合にのみ合計が行われるため、これらすべてに UB はありません。

于 2013-07-11T07:13:34.703 に答える
2

私はまだまともなポータブルソリューションを探していますが、これは私がこれまでに思いついたのと同じくらい良いです:

改善のための提案?

int64 saturated_add(int64 x, int64 y) {
#if __GNUC__ && __X86_64__
  asm("add %1, %0\n\t"
      "jno 1f\n\t"
      "cmovge %3, %0\n\t"
      "cmovl %2, %0\n"
      "1:" : "+r"(x) : "r"(y), "r"(kint64min), "r"(kint64max));
  return x;
#else
  return portable_saturated_add(x, y);
#endif
}
于 2013-07-10T21:24:34.500 に答える