Was the instruction really much more complex than eg some byte-string comparison instruction? For string comparison you’re doing a simpler operation at each step, and the accumulation is much simpler, but maybe you have short-circuiting too. POLY corresponds to the following C, I think:

  float poly(int d, float x, float *c) {
    c+=d;
    float y = *c;
    while(d--)
      y = *c-- + y * x;
    return y;
  }

I also don’t see why you consider this to be the CISCiest instruction from an architecture that includes a substring-search instruction, a vaguely printf-like instruction with its own mini instruction set for the pattern strings it takes, and an instruction to do polynomial division in the ring of polynomials over F_2 (ok this is just CRC)