I forget; are expr's guaranteed to be "GroupByComplexity"'d? If so, ContainsConstantSomewhere can be optimized greatly. If there's any constant, it's guaranteed to be in a group at the end. You only recurse on Add and Mul, so if you've gone past those (to umax, smax, unknown or could-not-compute, you can stop).

Also, please iterate with a worklist instead of recursing. Create a SmallVector<SCEV*>, push your starting element into it, use pop_back_val to grab the latest one off the top of the list. If you're worried about revisiting the same thing multiple times, add a SmallSet<SCEV*> and test whether inserting the new element succeeds -- if it doesn't, it's already in the set.

Please give this function a name that starts with a lower case letter. Also, pointers bind to the variable name.

"SCEV* StartExpr" should be "SCEV *StartExpr".

It's more natural in LLVM to write:

const auto *Target = dyn_cast<SCEVNAryExpr>(Expr);

This would probably read easier as:

for (const SCEV *Operand : Target->operands())

This cast is guaranteed to succeed because of the if isa's above. Use cast<> instead of dyn_cast<>.

These extra parens look strange.

I think this would look a little more natural:

for (const SCEV *Operand : Target->operands()) {
  if (isa<SCEVConstant>(*Operand))
    return true;
  if (isa<SCEVAddExpr>(*Operand) || isa<SCEVMulExpr>(*Operand))
    if (containsConstantSomewhere(*Operand))
      return true;
}

Capitalize 'If', remove extra space before 'then'.