1 //=== ScopDetectionDiagnostic.cpp - Error diagnostics --------- -*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Small set of diagnostic helper classes to encapsulate any errors occurred
11 // during the detection of Scops.
12 //
13 // The ScopDetection defines a set of error classes (via Statistic variables)
14 // that groups a number of individual errors into a group, e.g. non-affinity
15 // related errors.
16 // On error we generate an object that carries enough additional information
17 // to diagnose the error and generate a helpful error message.
18 //
19 //===----------------------------------------------------------------------===//
20 #include "polly/ScopDetectionDiagnostic.h"
21 #include "polly/Support/ScopLocation.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/AliasSetTracker.h"
25 #include "llvm/Analysis/LoopInfo.h"
26 #include "llvm/Analysis/RegionInfo.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/DebugInfo.h"
29 #include "llvm/IR/DebugLoc.h"
30 #include "llvm/IR/DiagnosticInfo.h"
31 #include "llvm/IR/LLVMContext.h"
32 #include "llvm/IR/Value.h"
33 
34 #define DEBUG_TYPE "polly-detect"
35 #include "llvm/Support/Debug.h"
36 
37 #include <string>
38 
39 using namespace llvm;
40 
41 #define SCOP_STAT(NAME, DESC)                                                  \
42   { "polly-detect", "NAME", "Number of rejected regions: " DESC, {0}, false }
43 
44 llvm::Statistic RejectStatistics[] = {
45     SCOP_STAT(CFG, ""),
46     SCOP_STAT(InvalidTerminator, "Unsupported terminator instruction"),
47     SCOP_STAT(IrreducibleRegion, "Irreducible loops"),
48     SCOP_STAT(LastCFG, ""),
49     SCOP_STAT(AffFunc, ""),
50     SCOP_STAT(UndefCond, "Undefined branch condition"),
51     SCOP_STAT(InvalidCond, "Non-integer branch condition"),
52     SCOP_STAT(UndefOperand, "Undefined operands in comparison"),
53     SCOP_STAT(NonAffBranch, "Non-affine branch condition"),
54     SCOP_STAT(NoBasePtr, "No base pointer"),
55     SCOP_STAT(UndefBasePtr, "Undefined base pointer"),
56     SCOP_STAT(VariantBasePtr, "Variant base pointer"),
57     SCOP_STAT(NonAffineAccess, "Non-affine memory accesses"),
58     SCOP_STAT(DifferentElementSize, "Accesses with differing sizes"),
59     SCOP_STAT(LastAffFunc, ""),
60     SCOP_STAT(LoopBound, "Uncomputable loop bounds"),
61     SCOP_STAT(LoopHasNoExit, "Loop without exit"),
62     SCOP_STAT(FuncCall, "Function call with side effects"),
63     SCOP_STAT(NonSimpleMemoryAccess, "Compilated access semantics (volatile or "
64                                      "atomic)"),
65     SCOP_STAT(Alias, "Base address aliasing"),
66     SCOP_STAT(Other, ""),
67     SCOP_STAT(IntToPtr, "Integer to pointer conversions"),
68     SCOP_STAT(Alloca, "Stack allocations"),
69     SCOP_STAT(UnknownInst, "Unknown Instructions"),
70     SCOP_STAT(Entry, "Contains entry block"),
71     SCOP_STAT(Unprofitable, "Assumed to be unprofitable"),
72     SCOP_STAT(LastOther, ""),
73 };
74 
75 namespace polly {
76 /// Small string conversion via raw_string_stream.
77 template <typename T> std::string operator+(Twine LHS, const T &RHS) {
78   std::string Buf;
79   raw_string_ostream fmt(Buf);
80   fmt << RHS;
81   fmt.flush();
82 
83   return LHS.concat(Buf).str();
84 }
85 } // namespace polly
86 
87 namespace llvm {
88 // Lexicographic order on (line, col) of our debug locations.
89 static bool operator<(const llvm::DebugLoc &LHS, const llvm::DebugLoc &RHS) {
90   return LHS.getLine() < RHS.getLine() ||
91          (LHS.getLine() == RHS.getLine() && LHS.getCol() < RHS.getCol());
92 }
93 } // namespace llvm
94 
95 namespace polly {
96 BBPair getBBPairForRegion(const Region *R) {
97   return std::make_pair(R->getEntry(), R->getExit());
98 }
99 
100 void getDebugLocations(const BBPair &P, DebugLoc &Begin, DebugLoc &End) {
101   SmallPtrSet<BasicBlock *, 32> Seen;
102   SmallVector<BasicBlock *, 32> Todo;
103   Todo.push_back(P.first);
104   while (!Todo.empty()) {
105     auto *BB = Todo.pop_back_val();
106     if (BB == P.second)
107       continue;
108     if (!Seen.insert(BB).second)
109       continue;
110     Todo.append(succ_begin(BB), succ_end(BB));
111     for (const Instruction &Inst : *BB) {
112       DebugLoc DL = Inst.getDebugLoc();
113       if (!DL)
114         continue;
115 
116       Begin = Begin ? std::min(Begin, DL) : DL;
117       End = End ? std::max(End, DL) : DL;
118     }
119   }
120 }
121 
122 void emitRejectionRemarks(const BBPair &P, const RejectLog &Log) {
123   Function &F = *P.first->getParent();
124   LLVMContext &Ctx = F.getContext();
125 
126   DebugLoc Begin, End;
127   getDebugLocations(P, Begin, End);
128 
129   emitOptimizationRemarkMissed(
130       Ctx, DEBUG_TYPE, F, Begin,
131       "The following errors keep this region from being a Scop.");
132 
133   for (RejectReasonPtr RR : Log) {
134     if (const DebugLoc &Loc = RR->getDebugLoc())
135       emitOptimizationRemarkMissed(Ctx, DEBUG_TYPE, F, Loc,
136                                    RR->getEndUserMessage());
137   }
138 
139   emitOptimizationRemarkMissed(Ctx, DEBUG_TYPE, F, End,
140                                "Invalid Scop candidate ends here.");
141 }
142 
143 //===----------------------------------------------------------------------===//
144 // RejectReason.
145 
146 RejectReason::RejectReason(RejectReasonKind K) : Kind(K) {
147   RejectStatistics[static_cast<int>(K)]++;
148 }
149 
150 const DebugLoc RejectReason::Unknown = DebugLoc();
151 
152 const llvm::DebugLoc &RejectReason::getDebugLoc() const {
153   // Allocate an empty DebugLoc and return it a reference to it.
154   return Unknown;
155 }
156 
157 // RejectLog.
158 void RejectLog::print(raw_ostream &OS, int level) const {
159   int j = 0;
160   for (auto Reason : ErrorReports)
161     OS.indent(level) << "[" << j++ << "] " << Reason->getMessage() << "\n";
162 }
163 
164 //===----------------------------------------------------------------------===//
165 // ReportCFG.
166 
167 ReportCFG::ReportCFG(const RejectReasonKind K) : RejectReason(K) {}
168 
169 bool ReportCFG::classof(const RejectReason *RR) {
170   return RR->getKind() >= RejectReasonKind::CFG &&
171          RR->getKind() <= RejectReasonKind::LastCFG;
172 }
173 
174 //===----------------------------------------------------------------------===//
175 // ReportInvalidTerminator.
176 
177 std::string ReportInvalidTerminator::getMessage() const {
178   return ("Invalid instruction terminates BB: " + BB->getName()).str();
179 }
180 
181 const DebugLoc &ReportInvalidTerminator::getDebugLoc() const {
182   return BB->getTerminator()->getDebugLoc();
183 }
184 
185 bool ReportInvalidTerminator::classof(const RejectReason *RR) {
186   return RR->getKind() == RejectReasonKind::InvalidTerminator;
187 }
188 
189 //===----------------------------------------------------------------------===//
190 // ReportIrreducibleRegion.
191 
192 std::string ReportIrreducibleRegion::getMessage() const {
193   return "Irreducible region encountered: " + R->getNameStr();
194 }
195 
196 const DebugLoc &ReportIrreducibleRegion::getDebugLoc() const { return DbgLoc; }
197 
198 std::string ReportIrreducibleRegion::getEndUserMessage() const {
199   return "Irreducible region encountered in control flow.";
200 }
201 
202 bool ReportIrreducibleRegion::classof(const RejectReason *RR) {
203   return RR->getKind() == RejectReasonKind::IrreducibleRegion;
204 }
205 
206 //===----------------------------------------------------------------------===//
207 // ReportAffFunc.
208 
209 ReportAffFunc::ReportAffFunc(const RejectReasonKind K, const Instruction *Inst)
210     : RejectReason(K), Inst(Inst) {}
211 
212 bool ReportAffFunc::classof(const RejectReason *RR) {
213   return RR->getKind() >= RejectReasonKind::AffFunc &&
214          RR->getKind() <= RejectReasonKind::LastAffFunc;
215 }
216 
217 //===----------------------------------------------------------------------===//
218 // ReportUndefCond.
219 
220 std::string ReportUndefCond::getMessage() const {
221   return ("Condition based on 'undef' value in BB: " + BB->getName()).str();
222 }
223 
224 bool ReportUndefCond::classof(const RejectReason *RR) {
225   return RR->getKind() == RejectReasonKind::UndefCond;
226 }
227 
228 //===----------------------------------------------------------------------===//
229 // ReportInvalidCond.
230 
231 std::string ReportInvalidCond::getMessage() const {
232   return ("Condition in BB '" + BB->getName()).str() +
233          "' neither constant nor an icmp instruction";
234 }
235 
236 bool ReportInvalidCond::classof(const RejectReason *RR) {
237   return RR->getKind() == RejectReasonKind::InvalidCond;
238 }
239 
240 //===----------------------------------------------------------------------===//
241 // ReportUndefOperand.
242 
243 std::string ReportUndefOperand::getMessage() const {
244   return ("undef operand in branch at BB: " + BB->getName()).str();
245 }
246 
247 bool ReportUndefOperand::classof(const RejectReason *RR) {
248   return RR->getKind() == RejectReasonKind::UndefOperand;
249 }
250 
251 //===----------------------------------------------------------------------===//
252 // ReportNonAffBranch.
253 
254 std::string ReportNonAffBranch::getMessage() const {
255   return ("Non affine branch in BB '" + BB->getName()).str() +
256          "' with LHS: " + *LHS + " and RHS: " + *RHS;
257 }
258 
259 bool ReportNonAffBranch::classof(const RejectReason *RR) {
260   return RR->getKind() == RejectReasonKind::NonAffBranch;
261 }
262 
263 //===----------------------------------------------------------------------===//
264 // ReportNoBasePtr.
265 
266 std::string ReportNoBasePtr::getMessage() const { return "No base pointer"; }
267 
268 bool ReportNoBasePtr::classof(const RejectReason *RR) {
269   return RR->getKind() == RejectReasonKind::NoBasePtr;
270 }
271 
272 //===----------------------------------------------------------------------===//
273 // ReportUndefBasePtr.
274 
275 std::string ReportUndefBasePtr::getMessage() const {
276   return "Undefined base pointer";
277 }
278 
279 bool ReportUndefBasePtr::classof(const RejectReason *RR) {
280   return RR->getKind() == RejectReasonKind::UndefBasePtr;
281 }
282 
283 //===----------------------------------------------------------------------===//
284 // ReportVariantBasePtr.
285 
286 std::string ReportVariantBasePtr::getMessage() const {
287   return "Base address not invariant in current region:" + *BaseValue;
288 }
289 
290 std::string ReportVariantBasePtr::getEndUserMessage() const {
291   return "The base address of this array is not invariant inside the loop";
292 }
293 
294 bool ReportVariantBasePtr::classof(const RejectReason *RR) {
295   return RR->getKind() == RejectReasonKind::VariantBasePtr;
296 }
297 
298 //===----------------------------------------------------------------------===//
299 // ReportDifferentArrayElementSize
300 
301 std::string ReportDifferentArrayElementSize::getMessage() const {
302   return "Access to one array through data types of different size";
303 }
304 
305 bool ReportDifferentArrayElementSize::classof(const RejectReason *RR) {
306   return RR->getKind() == RejectReasonKind::DifferentElementSize;
307 }
308 
309 std::string ReportDifferentArrayElementSize::getEndUserMessage() const {
310   llvm::StringRef BaseName = BaseValue->getName();
311   std::string Name = (BaseName.size() > 0) ? BaseName : "UNKNOWN";
312   return "The array \"" + Name + "\" is accessed through elements that differ "
313                                  "in size";
314 }
315 
316 //===----------------------------------------------------------------------===//
317 // ReportNonAffineAccess.
318 
319 std::string ReportNonAffineAccess::getMessage() const {
320   return "Non affine access function: " + *AccessFunction;
321 }
322 
323 bool ReportNonAffineAccess::classof(const RejectReason *RR) {
324   return RR->getKind() == RejectReasonKind::NonAffineAccess;
325 }
326 
327 std::string ReportNonAffineAccess::getEndUserMessage() const {
328   llvm::StringRef BaseName = BaseValue->getName();
329   std::string Name = (BaseName.size() > 0) ? BaseName : "UNKNOWN";
330   return "The array subscript of \"" + Name + "\" is not affine";
331 }
332 
333 //===----------------------------------------------------------------------===//
334 // ReportLoopBound.
335 
336 ReportLoopBound::ReportLoopBound(Loop *L, const SCEV *LoopCount)
337     : RejectReason(RejectReasonKind::LoopBound), L(L), LoopCount(LoopCount),
338       Loc(L->getStartLoc()) {}
339 
340 std::string ReportLoopBound::getMessage() const {
341   return "Non affine loop bound '" + *LoopCount +
342          "' in loop: " + L->getHeader()->getName();
343 }
344 
345 const DebugLoc &ReportLoopBound::getDebugLoc() const { return Loc; }
346 
347 bool ReportLoopBound::classof(const RejectReason *RR) {
348   return RR->getKind() == RejectReasonKind::LoopBound;
349 }
350 
351 std::string ReportLoopBound::getEndUserMessage() const {
352   return "Failed to derive an affine function from the loop bounds.";
353 }
354 
355 //===----------------------------------------------------------------------===//
356 // ReportLoopHasNoExit.
357 
358 std::string ReportLoopHasNoExit::getMessage() const {
359   return "Loop " + L->getHeader()->getName() + " has no exit.";
360 }
361 
362 bool ReportLoopHasNoExit::classof(const RejectReason *RR) {
363   return RR->getKind() == RejectReasonKind::LoopHasNoExit;
364 }
365 
366 const DebugLoc &ReportLoopHasNoExit::getDebugLoc() const { return Loc; }
367 
368 std::string ReportLoopHasNoExit::getEndUserMessage() const {
369   return "Loop cannot be handled because it has no exit.";
370 }
371 
372 //===----------------------------------------------------------------------===//
373 // ReportFuncCall.
374 
375 ReportFuncCall::ReportFuncCall(Instruction *Inst)
376     : RejectReason(RejectReasonKind::FuncCall), Inst(Inst) {}
377 
378 std::string ReportFuncCall::getMessage() const {
379   return "Call instruction: " + *Inst;
380 }
381 
382 const DebugLoc &ReportFuncCall::getDebugLoc() const {
383   return Inst->getDebugLoc();
384 }
385 
386 std::string ReportFuncCall::getEndUserMessage() const {
387   return "This function call cannot be handled. "
388          "Try to inline it.";
389 }
390 
391 bool ReportFuncCall::classof(const RejectReason *RR) {
392   return RR->getKind() == RejectReasonKind::FuncCall;
393 }
394 
395 //===----------------------------------------------------------------------===//
396 // ReportNonSimpleMemoryAccess
397 
398 ReportNonSimpleMemoryAccess::ReportNonSimpleMemoryAccess(Instruction *Inst)
399     : ReportOther(RejectReasonKind::NonSimpleMemoryAccess), Inst(Inst) {}
400 
401 std::string ReportNonSimpleMemoryAccess::getMessage() const {
402   return "Non-simple memory access: " + *Inst;
403 }
404 
405 const DebugLoc &ReportNonSimpleMemoryAccess::getDebugLoc() const {
406   return Inst->getDebugLoc();
407 }
408 
409 std::string ReportNonSimpleMemoryAccess::getEndUserMessage() const {
410   return "Volatile memory accesses or memory accesses for atomic types "
411          "are not supported.";
412 }
413 
414 bool ReportNonSimpleMemoryAccess::classof(const RejectReason *RR) {
415   return RR->getKind() == RejectReasonKind::NonSimpleMemoryAccess;
416 }
417 
418 //===----------------------------------------------------------------------===//
419 // ReportAlias.
420 
421 ReportAlias::ReportAlias(Instruction *Inst, AliasSet &AS)
422     : RejectReason(RejectReasonKind::Alias), Inst(Inst) {
423 
424   for (const auto &I : AS)
425     Pointers.push_back(I.getValue());
426 }
427 
428 std::string ReportAlias::formatInvalidAlias(std::string Prefix,
429                                             std::string Suffix) const {
430   std::string Message;
431   raw_string_ostream OS(Message);
432 
433   OS << Prefix;
434 
435   for (PointerSnapshotTy::const_iterator PI = Pointers.begin(),
436                                          PE = Pointers.end();
437        ;) {
438     const Value *V = *PI;
439     assert(V && "Diagnostic info does not match found LLVM-IR anymore.");
440 
441     if (V->getName().size() == 0)
442       OS << "\"" << *V << "\"";
443     else
444       OS << "\"" << V->getName() << "\"";
445 
446     ++PI;
447 
448     if (PI != PE)
449       OS << ", ";
450     else
451       break;
452   }
453 
454   OS << Suffix;
455 
456   return OS.str();
457 }
458 
459 std::string ReportAlias::getMessage() const {
460   return formatInvalidAlias("Possible aliasing: ");
461 }
462 
463 std::string ReportAlias::getEndUserMessage() const {
464   return formatInvalidAlias("Accesses to the arrays ",
465                             " may access the same memory.");
466 }
467 
468 const DebugLoc &ReportAlias::getDebugLoc() const { return Inst->getDebugLoc(); }
469 
470 bool ReportAlias::classof(const RejectReason *RR) {
471   return RR->getKind() == RejectReasonKind::Alias;
472 }
473 
474 //===----------------------------------------------------------------------===//
475 // ReportOther.
476 
477 std::string ReportOther::getMessage() const { return "Unknown reject reason"; }
478 
479 ReportOther::ReportOther(const RejectReasonKind K) : RejectReason(K) {}
480 
481 bool ReportOther::classof(const RejectReason *RR) {
482   return RR->getKind() >= RejectReasonKind::Other &&
483          RR->getKind() <= RejectReasonKind::LastOther;
484 }
485 
486 //===----------------------------------------------------------------------===//
487 // ReportIntToPtr.
488 ReportIntToPtr::ReportIntToPtr(Instruction *BaseValue)
489     : ReportOther(RejectReasonKind::IntToPtr), BaseValue(BaseValue) {}
490 
491 std::string ReportIntToPtr::getMessage() const {
492   return "Find bad intToptr prt: " + *BaseValue;
493 }
494 
495 const DebugLoc &ReportIntToPtr::getDebugLoc() const {
496   return BaseValue->getDebugLoc();
497 }
498 
499 bool ReportIntToPtr::classof(const RejectReason *RR) {
500   return RR->getKind() == RejectReasonKind::IntToPtr;
501 }
502 
503 //===----------------------------------------------------------------------===//
504 // ReportAlloca.
505 
506 ReportAlloca::ReportAlloca(Instruction *Inst)
507     : ReportOther(RejectReasonKind::Alloca), Inst(Inst) {}
508 
509 std::string ReportAlloca::getMessage() const {
510   return "Alloca instruction: " + *Inst;
511 }
512 
513 const DebugLoc &ReportAlloca::getDebugLoc() const {
514   return Inst->getDebugLoc();
515 }
516 
517 bool ReportAlloca::classof(const RejectReason *RR) {
518   return RR->getKind() == RejectReasonKind::Alloca;
519 }
520 
521 //===----------------------------------------------------------------------===//
522 // ReportUnknownInst.
523 
524 ReportUnknownInst::ReportUnknownInst(Instruction *Inst)
525     : ReportOther(RejectReasonKind::UnknownInst), Inst(Inst) {}
526 
527 std::string ReportUnknownInst::getMessage() const {
528   return "Unknown instruction: " + *Inst;
529 }
530 
531 const DebugLoc &ReportUnknownInst::getDebugLoc() const {
532   return Inst->getDebugLoc();
533 }
534 
535 bool ReportUnknownInst::classof(const RejectReason *RR) {
536   return RR->getKind() == RejectReasonKind::UnknownInst;
537 }
538 
539 //===----------------------------------------------------------------------===//
540 // ReportEntry.
541 ReportEntry::ReportEntry(BasicBlock *BB)
542     : ReportOther(RejectReasonKind::Entry), BB(BB) {}
543 
544 std::string ReportEntry::getMessage() const {
545   return "Region containing entry block of function is invalid!";
546 }
547 
548 const DebugLoc &ReportEntry::getDebugLoc() const {
549   return BB->getTerminator()->getDebugLoc();
550 }
551 
552 bool ReportEntry::classof(const RejectReason *RR) {
553   return RR->getKind() == RejectReasonKind::Entry;
554 }
555 
556 //===----------------------------------------------------------------------===//
557 // ReportUnprofitable.
558 ReportUnprofitable::ReportUnprofitable(Region *R)
559     : ReportOther(RejectReasonKind::Unprofitable), R(R) {}
560 
561 std::string ReportUnprofitable::getMessage() const {
562   return "Region can not profitably be optimized!";
563 }
564 
565 std::string ReportUnprofitable::getEndUserMessage() const {
566   return "No profitable polyhedral optimization found";
567 }
568 
569 const DebugLoc &ReportUnprofitable::getDebugLoc() const {
570   for (const BasicBlock *BB : R->blocks())
571     for (const Instruction &Inst : *BB)
572       if (const DebugLoc &DL = Inst.getDebugLoc())
573         return DL;
574 
575   return R->getEntry()->getTerminator()->getDebugLoc();
576 }
577 
578 bool ReportUnprofitable::classof(const RejectReason *RR) {
579   return RR->getKind() == RejectReasonKind::Unprofitable;
580 }
581 } // namespace polly
582