[NoTTI] reject negative scale in addressing mode

[jingyue]

Summary

I noticed this bug when deubging a WIP on LSR. I wonder whether and how we
should add a regression test for this.

[hfinkel]

Re: Testing, it might be nice to put this into lib/Analysis/CostModel.cpp and then add a test in test/Analysis/CostModel/no_info.ll

[jingyue]

Seems hard in CostModel. I cannot come up with any instruction (e.g. GEP)
that triggers negative scales (unless element sizes can be negative).

This bug was triggered at
http://llvm.org/docs/doxygen/html/LoopStrengthReduce_8cpp_source.html#l01022.
isAMCompletelyFolded considered some SCEV in the form "reg - reg" free. LSR
seems the only place that computes addressing mode from SCEV where negative
scales are possible. I am trying to write an LSR test that can expose this
bug.

Jingyue

[atrick]

Please add comments explaining the behavior that you discovered and rationale. Are you just trying to avoid considering reg - reg to be free, or can scale be < -1?

You should be able to test LSR now with opt -loop-reduce and specifying TTI. I'm not sure off the top of my head the best way to specify TTI, but -mtriple probably works.

Otherwise looks good. Thanks for the fix.

[jingyue]

added an LSR test that exposes this bug

[jingyue]

Forgot the RUN line

llvm/trunk/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   void getUnrollingPreferences(Loop *, TTI::UnrollingPreferences &) {}
 
   bool isLegalAddImmediate(int64_t Imm) { return false; }
 
   bool isLegalICmpImmediate(int64_t Imm) { return false; }
 
   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                              bool HasBaseReg, int64_t Scale) {
-    // Guess that reg+reg addressing is allowed. This heuristic is taken from
-    // the implementation of LSR.
-    return !BaseGV && BaseOffset == 0 && Scale <= 1;
+    // Guess that only reg and reg+reg addressing is allowed. This heuristic is
+    // taken from the implementation of LSR.
+    return !BaseGV && BaseOffset == 0 && (Scale == 0 || Scale == 1);
   }
 
   bool isLegalMaskedStore(Type *DataType, int Consecutive) { return false; }
 
   bool isLegalMaskedLoad(Type *DataType, int Consecutive) { return false; }
 
   int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                            bool HasBaseReg, int64_t Scale) {

llvm/trunk/test/Transforms/LoopStrengthReduce/negative-scale.ll

+; RUN: opt < %s -loop-reduce -S | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+
+declare void @foo(i8)
+
+define void @not_addressing_mode(i8* %input, i64 %n) {
+; CHECK-LABEL: @not_addressing_mode(
+entry:
+  br label %loop
+
+loop:
+; CHECK: loop:
+; CHECK: %lsr.iv = phi i8* [ {{%[^,]+}}, %loop ], [ %input, %entry ]
+  %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
+  %i.next = add i64 %i, 1
+  %j = mul i64 %i, -2
+  ; (%input - 2 * %j) is not foldable. Worth another indvar.
+  %p = getelementptr i8, i8* %input, i64 %j
+  %v = load i8, i8* %p
+; CHECK: %v = load i8, i8* %lsr.iv
+  call void @foo(i8 %v)
+  %exitcond = icmp slt i64 %i.next, %n
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  ret void
+}