ConstantRangeTest.cpp 88 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225
  1. //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. #include "llvm/ADT/BitVector.h"
  9. #include "llvm/IR/ConstantRange.h"
  10. #include "llvm/IR/Instructions.h"
  11. #include "llvm/IR/Operator.h"
  12. #include "llvm/Support/KnownBits.h"
  13. #include "gtest/gtest.h"
  14. using namespace llvm;
  15. namespace {
  16. class ConstantRangeTest : public ::testing::Test {
  17. protected:
  18. static ConstantRange Full;
  19. static ConstantRange Empty;
  20. static ConstantRange One;
  21. static ConstantRange Some;
  22. static ConstantRange Wrap;
  23. };
  24. template<typename Fn>
  25. static void EnumerateConstantRanges(unsigned Bits, Fn TestFn) {
  26. unsigned Max = 1 << Bits;
  27. for (unsigned Lo = 0; Lo < Max; Lo++) {
  28. for (unsigned Hi = 0; Hi < Max; Hi++) {
  29. // Enforce ConstantRange invariant.
  30. if (Lo == Hi && Lo != 0 && Lo != Max - 1)
  31. continue;
  32. ConstantRange CR(APInt(Bits, Lo), APInt(Bits, Hi));
  33. TestFn(CR);
  34. }
  35. }
  36. }
  37. template<typename Fn>
  38. static void EnumerateTwoConstantRanges(unsigned Bits, Fn TestFn) {
  39. EnumerateConstantRanges(Bits, [&](const ConstantRange &CR1) {
  40. EnumerateConstantRanges(Bits, [&](const ConstantRange &CR2) {
  41. TestFn(CR1, CR2);
  42. });
  43. });
  44. }
  45. template<typename Fn>
  46. static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) {
  47. if (!CR.isEmptySet()) {
  48. APInt N = CR.getLower();
  49. do TestFn(N);
  50. while (++N != CR.getUpper());
  51. }
  52. }
  53. template<typename Fn1, typename Fn2>
  54. static void TestUnsignedBinOpExhaustive(
  55. Fn1 RangeFn, Fn2 IntFn,
  56. bool SkipZeroRHS = false, bool CorrectnessOnly = false) {
  57. unsigned Bits = 4;
  58. EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
  59. const ConstantRange &CR2) {
  60. APInt Min = APInt::getMaxValue(Bits);
  61. APInt Max = APInt::getMinValue(Bits);
  62. ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
  63. ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
  64. if (SkipZeroRHS && N2 == 0)
  65. return;
  66. APInt N = IntFn(N1, N2);
  67. if (N.ult(Min))
  68. Min = N;
  69. if (N.ugt(Max))
  70. Max = N;
  71. });
  72. });
  73. ConstantRange CR = RangeFn(CR1, CR2);
  74. if (Min.ugt(Max)) {
  75. EXPECT_TRUE(CR.isEmptySet());
  76. return;
  77. }
  78. ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
  79. if (CorrectnessOnly) {
  80. EXPECT_TRUE(CR.contains(Exact));
  81. } else {
  82. EXPECT_EQ(Exact, CR);
  83. }
  84. });
  85. }
  86. template<typename Fn1, typename Fn2>
  87. static void TestSignedBinOpExhaustive(
  88. Fn1 RangeFn, Fn2 IntFn,
  89. bool SkipZeroRHS = false, bool CorrectnessOnly = false) {
  90. unsigned Bits = 4;
  91. EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
  92. const ConstantRange &CR2) {
  93. APInt Min = APInt::getSignedMaxValue(Bits);
  94. APInt Max = APInt::getSignedMinValue(Bits);
  95. ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
  96. ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
  97. if (SkipZeroRHS && N2 == 0)
  98. return;
  99. APInt N = IntFn(N1, N2);
  100. if (N.slt(Min))
  101. Min = N;
  102. if (N.sgt(Max))
  103. Max = N;
  104. });
  105. });
  106. ConstantRange CR = RangeFn(CR1, CR2);
  107. if (Min.sgt(Max)) {
  108. EXPECT_TRUE(CR.isEmptySet());
  109. return;
  110. }
  111. ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
  112. if (CorrectnessOnly) {
  113. EXPECT_TRUE(CR.contains(Exact));
  114. } else {
  115. EXPECT_EQ(Exact, CR);
  116. }
  117. });
  118. }
  119. ConstantRange ConstantRangeTest::Full(16, true);
  120. ConstantRange ConstantRangeTest::Empty(16, false);
  121. ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
  122. ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
  123. ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
  124. TEST_F(ConstantRangeTest, Basics) {
  125. EXPECT_TRUE(Full.isFullSet());
  126. EXPECT_FALSE(Full.isEmptySet());
  127. EXPECT_TRUE(Full.inverse().isEmptySet());
  128. EXPECT_FALSE(Full.isWrappedSet());
  129. EXPECT_TRUE(Full.contains(APInt(16, 0x0)));
  130. EXPECT_TRUE(Full.contains(APInt(16, 0x9)));
  131. EXPECT_TRUE(Full.contains(APInt(16, 0xa)));
  132. EXPECT_TRUE(Full.contains(APInt(16, 0xaa9)));
  133. EXPECT_TRUE(Full.contains(APInt(16, 0xaaa)));
  134. EXPECT_FALSE(Empty.isFullSet());
  135. EXPECT_TRUE(Empty.isEmptySet());
  136. EXPECT_TRUE(Empty.inverse().isFullSet());
  137. EXPECT_FALSE(Empty.isWrappedSet());
  138. EXPECT_FALSE(Empty.contains(APInt(16, 0x0)));
  139. EXPECT_FALSE(Empty.contains(APInt(16, 0x9)));
  140. EXPECT_FALSE(Empty.contains(APInt(16, 0xa)));
  141. EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9)));
  142. EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa)));
  143. EXPECT_FALSE(One.isFullSet());
  144. EXPECT_FALSE(One.isEmptySet());
  145. EXPECT_FALSE(One.isWrappedSet());
  146. EXPECT_FALSE(One.contains(APInt(16, 0x0)));
  147. EXPECT_FALSE(One.contains(APInt(16, 0x9)));
  148. EXPECT_TRUE(One.contains(APInt(16, 0xa)));
  149. EXPECT_FALSE(One.contains(APInt(16, 0xaa9)));
  150. EXPECT_FALSE(One.contains(APInt(16, 0xaaa)));
  151. EXPECT_FALSE(One.inverse().contains(APInt(16, 0xa)));
  152. EXPECT_FALSE(Some.isFullSet());
  153. EXPECT_FALSE(Some.isEmptySet());
  154. EXPECT_FALSE(Some.isWrappedSet());
  155. EXPECT_FALSE(Some.contains(APInt(16, 0x0)));
  156. EXPECT_FALSE(Some.contains(APInt(16, 0x9)));
  157. EXPECT_TRUE(Some.contains(APInt(16, 0xa)));
  158. EXPECT_TRUE(Some.contains(APInt(16, 0xaa9)));
  159. EXPECT_FALSE(Some.contains(APInt(16, 0xaaa)));
  160. EXPECT_FALSE(Wrap.isFullSet());
  161. EXPECT_FALSE(Wrap.isEmptySet());
  162. EXPECT_TRUE(Wrap.isWrappedSet());
  163. EXPECT_TRUE(Wrap.contains(APInt(16, 0x0)));
  164. EXPECT_TRUE(Wrap.contains(APInt(16, 0x9)));
  165. EXPECT_FALSE(Wrap.contains(APInt(16, 0xa)));
  166. EXPECT_FALSE(Wrap.contains(APInt(16, 0xaa9)));
  167. EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa)));
  168. }
  169. TEST_F(ConstantRangeTest, Equality) {
  170. EXPECT_EQ(Full, Full);
  171. EXPECT_EQ(Empty, Empty);
  172. EXPECT_EQ(One, One);
  173. EXPECT_EQ(Some, Some);
  174. EXPECT_EQ(Wrap, Wrap);
  175. EXPECT_NE(Full, Empty);
  176. EXPECT_NE(Full, One);
  177. EXPECT_NE(Full, Some);
  178. EXPECT_NE(Full, Wrap);
  179. EXPECT_NE(Empty, One);
  180. EXPECT_NE(Empty, Some);
  181. EXPECT_NE(Empty, Wrap);
  182. EXPECT_NE(One, Some);
  183. EXPECT_NE(One, Wrap);
  184. EXPECT_NE(Some, Wrap);
  185. }
  186. TEST_F(ConstantRangeTest, SingleElement) {
  187. EXPECT_EQ(Full.getSingleElement(), static_cast<APInt *>(nullptr));
  188. EXPECT_EQ(Empty.getSingleElement(), static_cast<APInt *>(nullptr));
  189. EXPECT_EQ(Full.getSingleMissingElement(), static_cast<APInt *>(nullptr));
  190. EXPECT_EQ(Empty.getSingleMissingElement(), static_cast<APInt *>(nullptr));
  191. EXPECT_EQ(*One.getSingleElement(), APInt(16, 0xa));
  192. EXPECT_EQ(Some.getSingleElement(), static_cast<APInt *>(nullptr));
  193. EXPECT_EQ(Wrap.getSingleElement(), static_cast<APInt *>(nullptr));
  194. EXPECT_EQ(One.getSingleMissingElement(), static_cast<APInt *>(nullptr));
  195. EXPECT_EQ(Some.getSingleMissingElement(), static_cast<APInt *>(nullptr));
  196. ConstantRange OneInverse = One.inverse();
  197. EXPECT_EQ(*OneInverse.getSingleMissingElement(), *One.getSingleElement());
  198. EXPECT_FALSE(Full.isSingleElement());
  199. EXPECT_FALSE(Empty.isSingleElement());
  200. EXPECT_TRUE(One.isSingleElement());
  201. EXPECT_FALSE(Some.isSingleElement());
  202. EXPECT_FALSE(Wrap.isSingleElement());
  203. }
  204. TEST_F(ConstantRangeTest, GetMinsAndMaxes) {
  205. EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX));
  206. EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa));
  207. EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9));
  208. EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX));
  209. EXPECT_EQ(Full.getUnsignedMin(), APInt(16, 0));
  210. EXPECT_EQ(One.getUnsignedMin(), APInt(16, 0xa));
  211. EXPECT_EQ(Some.getUnsignedMin(), APInt(16, 0xa));
  212. EXPECT_EQ(Wrap.getUnsignedMin(), APInt(16, 0));
  213. EXPECT_EQ(Full.getSignedMax(), APInt(16, INT16_MAX));
  214. EXPECT_EQ(One.getSignedMax(), APInt(16, 0xa));
  215. EXPECT_EQ(Some.getSignedMax(), APInt(16, 0xaa9));
  216. EXPECT_EQ(Wrap.getSignedMax(), APInt(16, INT16_MAX));
  217. EXPECT_EQ(Full.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
  218. EXPECT_EQ(One.getSignedMin(), APInt(16, 0xa));
  219. EXPECT_EQ(Some.getSignedMin(), APInt(16, 0xa));
  220. EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
  221. // Found by Klee
  222. EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),
  223. APInt(4, 7));
  224. }
  225. TEST_F(ConstantRangeTest, SignWrapped) {
  226. EXPECT_FALSE(Full.isSignWrappedSet());
  227. EXPECT_FALSE(Empty.isSignWrappedSet());
  228. EXPECT_FALSE(One.isSignWrappedSet());
  229. EXPECT_FALSE(Some.isSignWrappedSet());
  230. EXPECT_TRUE(Wrap.isSignWrappedSet());
  231. EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet());
  232. EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet());
  233. EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet());
  234. EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet());
  235. EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet());
  236. EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet());
  237. EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet());
  238. }
  239. TEST_F(ConstantRangeTest, UpperWrapped) {
  240. // The behavior here is the same as for isWrappedSet() / isSignWrappedSet().
  241. EXPECT_FALSE(Full.isUpperWrapped());
  242. EXPECT_FALSE(Empty.isUpperWrapped());
  243. EXPECT_FALSE(One.isUpperWrapped());
  244. EXPECT_FALSE(Some.isUpperWrapped());
  245. EXPECT_TRUE(Wrap.isUpperWrapped());
  246. EXPECT_FALSE(Full.isUpperSignWrapped());
  247. EXPECT_FALSE(Empty.isUpperSignWrapped());
  248. EXPECT_FALSE(One.isUpperSignWrapped());
  249. EXPECT_FALSE(Some.isUpperSignWrapped());
  250. EXPECT_TRUE(Wrap.isUpperSignWrapped());
  251. // The behavior differs if Upper is the Min/SignedMin value.
  252. ConstantRange CR1(APInt(8, 42), APInt::getMinValue(8));
  253. EXPECT_FALSE(CR1.isWrappedSet());
  254. EXPECT_TRUE(CR1.isUpperWrapped());
  255. ConstantRange CR2(APInt(8, 42), APInt::getSignedMinValue(8));
  256. EXPECT_FALSE(CR2.isSignWrappedSet());
  257. EXPECT_TRUE(CR2.isUpperSignWrapped());
  258. }
  259. TEST_F(ConstantRangeTest, Trunc) {
  260. ConstantRange TFull = Full.truncate(10);
  261. ConstantRange TEmpty = Empty.truncate(10);
  262. ConstantRange TOne = One.truncate(10);
  263. ConstantRange TSome = Some.truncate(10);
  264. ConstantRange TWrap = Wrap.truncate(10);
  265. EXPECT_TRUE(TFull.isFullSet());
  266. EXPECT_TRUE(TEmpty.isEmptySet());
  267. EXPECT_EQ(TOne, ConstantRange(One.getLower().trunc(10),
  268. One.getUpper().trunc(10)));
  269. EXPECT_TRUE(TSome.isFullSet());
  270. EXPECT_TRUE(TWrap.isFullSet());
  271. // trunc([2, 5), 3->2) = [2, 1)
  272. ConstantRange TwoFive(APInt(3, 2), APInt(3, 5));
  273. EXPECT_EQ(TwoFive.truncate(2), ConstantRange(APInt(2, 2), APInt(2, 1)));
  274. // trunc([2, 6), 3->2) = full
  275. ConstantRange TwoSix(APInt(3, 2), APInt(3, 6));
  276. EXPECT_TRUE(TwoSix.truncate(2).isFullSet());
  277. // trunc([5, 7), 3->2) = [1, 3)
  278. ConstantRange FiveSeven(APInt(3, 5), APInt(3, 7));
  279. EXPECT_EQ(FiveSeven.truncate(2), ConstantRange(APInt(2, 1), APInt(2, 3)));
  280. // trunc([7, 1), 3->2) = [3, 1)
  281. ConstantRange SevenOne(APInt(3, 7), APInt(3, 1));
  282. EXPECT_EQ(SevenOne.truncate(2), ConstantRange(APInt(2, 3), APInt(2, 1)));
  283. }
  284. TEST_F(ConstantRangeTest, ZExt) {
  285. ConstantRange ZFull = Full.zeroExtend(20);
  286. ConstantRange ZEmpty = Empty.zeroExtend(20);
  287. ConstantRange ZOne = One.zeroExtend(20);
  288. ConstantRange ZSome = Some.zeroExtend(20);
  289. ConstantRange ZWrap = Wrap.zeroExtend(20);
  290. EXPECT_EQ(ZFull, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
  291. EXPECT_TRUE(ZEmpty.isEmptySet());
  292. EXPECT_EQ(ZOne, ConstantRange(One.getLower().zext(20),
  293. One.getUpper().zext(20)));
  294. EXPECT_EQ(ZSome, ConstantRange(Some.getLower().zext(20),
  295. Some.getUpper().zext(20)));
  296. EXPECT_EQ(ZWrap, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
  297. // zext([5, 0), 3->7) = [5, 8)
  298. ConstantRange FiveZero(APInt(3, 5), APInt(3, 0));
  299. EXPECT_EQ(FiveZero.zeroExtend(7), ConstantRange(APInt(7, 5), APInt(7, 8)));
  300. }
  301. TEST_F(ConstantRangeTest, SExt) {
  302. ConstantRange SFull = Full.signExtend(20);
  303. ConstantRange SEmpty = Empty.signExtend(20);
  304. ConstantRange SOne = One.signExtend(20);
  305. ConstantRange SSome = Some.signExtend(20);
  306. ConstantRange SWrap = Wrap.signExtend(20);
  307. EXPECT_EQ(SFull, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
  308. APInt(20, INT16_MAX + 1, true)));
  309. EXPECT_TRUE(SEmpty.isEmptySet());
  310. EXPECT_EQ(SOne, ConstantRange(One.getLower().sext(20),
  311. One.getUpper().sext(20)));
  312. EXPECT_EQ(SSome, ConstantRange(Some.getLower().sext(20),
  313. Some.getUpper().sext(20)));
  314. EXPECT_EQ(SWrap, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
  315. APInt(20, INT16_MAX + 1, true)));
  316. EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16),
  317. ConstantRange(APInt(16, -128), APInt(16, 128)));
  318. EXPECT_EQ(ConstantRange(APInt(16, 0x0200), APInt(16, 0x8000)).signExtend(19),
  319. ConstantRange(APInt(19, 0x0200), APInt(19, 0x8000)));
  320. }
  321. TEST_F(ConstantRangeTest, IntersectWith) {
  322. EXPECT_EQ(Empty.intersectWith(Full), Empty);
  323. EXPECT_EQ(Empty.intersectWith(Empty), Empty);
  324. EXPECT_EQ(Empty.intersectWith(One), Empty);
  325. EXPECT_EQ(Empty.intersectWith(Some), Empty);
  326. EXPECT_EQ(Empty.intersectWith(Wrap), Empty);
  327. EXPECT_EQ(Full.intersectWith(Full), Full);
  328. EXPECT_EQ(Some.intersectWith(Some), Some);
  329. EXPECT_EQ(Some.intersectWith(One), One);
  330. EXPECT_EQ(Full.intersectWith(One), One);
  331. EXPECT_EQ(Full.intersectWith(Some), Some);
  332. EXPECT_EQ(Some.intersectWith(Wrap), Empty);
  333. EXPECT_EQ(One.intersectWith(Wrap), Empty);
  334. EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One));
  335. // Klee generated testcase from PR4545.
  336. // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
  337. // 01..4.6789ABCDEF where the dots represent values not in the intersection.
  338. ConstantRange LHS(APInt(16, 4), APInt(16, 2));
  339. ConstantRange RHS(APInt(16, 6), APInt(16, 5));
  340. EXPECT_TRUE(LHS.intersectWith(RHS) == LHS);
  341. // previous bug: intersection of [min, 3) and [2, max) should be 2
  342. LHS = ConstantRange(APInt(32, -2147483646), APInt(32, 3));
  343. RHS = ConstantRange(APInt(32, 2), APInt(32, 2147483646));
  344. EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2)));
  345. // [2, 0) /\ [4, 3) = [2, 0)
  346. LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
  347. RHS = ConstantRange(APInt(32, 4), APInt(32, 3));
  348. EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2), APInt(32, 0)));
  349. // [2, 0) /\ [4, 2) = [4, 0)
  350. LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
  351. RHS = ConstantRange(APInt(32, 4), APInt(32, 2));
  352. EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0)));
  353. // [4, 2) /\ [5, 1) = [5, 1)
  354. LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
  355. RHS = ConstantRange(APInt(32, 5), APInt(32, 1));
  356. EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 5), APInt(32, 1)));
  357. // [2, 0) /\ [7, 4) = [7, 4)
  358. LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
  359. RHS = ConstantRange(APInt(32, 7), APInt(32, 4));
  360. EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 4)));
  361. // [4, 2) /\ [1, 0) = [1, 0)
  362. LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
  363. RHS = ConstantRange(APInt(32, 1), APInt(32, 0));
  364. EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2)));
  365. // [15, 0) /\ [7, 6) = [15, 0)
  366. LHS = ConstantRange(APInt(32, 15), APInt(32, 0));
  367. RHS = ConstantRange(APInt(32, 7), APInt(32, 6));
  368. EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0)));
  369. }
  370. template<typename Fn1, typename Fn2>
  371. void testBinarySetOperationExhaustive(Fn1 OpFn, Fn2 InResultFn) {
  372. unsigned Bits = 4;
  373. EnumerateTwoConstantRanges(Bits,
  374. [=](const ConstantRange &CR1, const ConstantRange &CR2) {
  375. // Collect up to three contiguous unsigned ranges. The HaveInterrupt
  376. // variables are used determine when we have to switch to the next
  377. // range because the previous one ended.
  378. APInt Lower1(Bits, 0), Upper1(Bits, 0);
  379. APInt Lower2(Bits, 0), Upper2(Bits, 0);
  380. APInt Lower3(Bits, 0), Upper3(Bits, 0);
  381. bool HaveRange1 = false, HaveInterrupt1 = false;
  382. bool HaveRange2 = false, HaveInterrupt2 = false;
  383. bool HaveRange3 = false, HaveInterrupt3 = false;
  384. APInt Num(Bits, 0);
  385. for (unsigned I = 0, Limit = 1 << Bits; I < Limit; ++I, ++Num) {
  386. if (!InResultFn(CR1, CR2, Num)) {
  387. if (HaveRange3)
  388. HaveInterrupt3 = true;
  389. else if (HaveRange2)
  390. HaveInterrupt2 = true;
  391. else if (HaveRange1)
  392. HaveInterrupt1 = true;
  393. continue;
  394. }
  395. if (HaveRange3) {
  396. Upper3 = Num;
  397. } else if (HaveInterrupt2) {
  398. HaveRange3 = true;
  399. Lower3 = Upper3 = Num;
  400. } else if (HaveRange2) {
  401. Upper2 = Num;
  402. } else if (HaveInterrupt1) {
  403. HaveRange2 = true;
  404. Lower2 = Upper2 = Num;
  405. } else if (HaveRange1) {
  406. Upper1 = Num;
  407. } else {
  408. HaveRange1 = true;
  409. Lower1 = Upper1 = Num;
  410. }
  411. }
  412. (void)HaveInterrupt3;
  413. assert(!HaveInterrupt3 && "Should have at most three ranges");
  414. ConstantRange SmallestCR = OpFn(CR1, CR2, ConstantRange::Smallest);
  415. ConstantRange UnsignedCR = OpFn(CR1, CR2, ConstantRange::Unsigned);
  416. ConstantRange SignedCR = OpFn(CR1, CR2, ConstantRange::Signed);
  417. if (!HaveRange1) {
  418. EXPECT_TRUE(SmallestCR.isEmptySet());
  419. EXPECT_TRUE(UnsignedCR.isEmptySet());
  420. EXPECT_TRUE(SignedCR.isEmptySet());
  421. return;
  422. }
  423. if (!HaveRange2) {
  424. if (Lower1 == Upper1 + 1) {
  425. EXPECT_TRUE(SmallestCR.isFullSet());
  426. EXPECT_TRUE(UnsignedCR.isFullSet());
  427. EXPECT_TRUE(SignedCR.isFullSet());
  428. } else {
  429. ConstantRange Expected(Lower1, Upper1 + 1);
  430. EXPECT_EQ(Expected, SmallestCR);
  431. EXPECT_EQ(Expected, UnsignedCR);
  432. EXPECT_EQ(Expected, SignedCR);
  433. }
  434. return;
  435. }
  436. ConstantRange Variant1(Bits, /*full*/ true);
  437. ConstantRange Variant2(Bits, /*full*/ true);
  438. if (!HaveRange3) {
  439. // Compute the two possible ways to cover two disjoint ranges.
  440. if (Lower1 != Upper2 + 1)
  441. Variant1 = ConstantRange(Lower1, Upper2 + 1);
  442. if (Lower2 != Upper1 + 1)
  443. Variant2 = ConstantRange(Lower2, Upper1 + 1);
  444. } else {
  445. // If we have three ranges, the first and last one have to be adjacent
  446. // to the unsigned domain. It's better to think of this as having two
  447. // holes, and we can construct one range using each hole.
  448. assert(Lower1.isNullValue() && Upper3.isMaxValue());
  449. Variant1 = ConstantRange(Lower2, Upper1 + 1);
  450. Variant2 = ConstantRange(Lower3, Upper2 + 1);
  451. }
  452. // Smallest: Smaller set, then any set.
  453. if (Variant1.isSizeStrictlySmallerThan(Variant2))
  454. EXPECT_EQ(Variant1, SmallestCR);
  455. else if (Variant2.isSizeStrictlySmallerThan(Variant1))
  456. EXPECT_EQ(Variant2, SmallestCR);
  457. else
  458. EXPECT_TRUE(Variant1 == SmallestCR || Variant2 == SmallestCR);
  459. // Unsigned: Non-wrapped set, then smaller set, then any set.
  460. bool Variant1Full = Variant1.isFullSet() || Variant1.isWrappedSet();
  461. bool Variant2Full = Variant2.isFullSet() || Variant2.isWrappedSet();
  462. if (!Variant1Full && Variant2Full)
  463. EXPECT_EQ(Variant1, UnsignedCR);
  464. else if (Variant1Full && !Variant2Full)
  465. EXPECT_EQ(Variant2, UnsignedCR);
  466. else if (Variant1.isSizeStrictlySmallerThan(Variant2))
  467. EXPECT_EQ(Variant1, UnsignedCR);
  468. else if (Variant2.isSizeStrictlySmallerThan(Variant1))
  469. EXPECT_EQ(Variant2, UnsignedCR);
  470. else
  471. EXPECT_TRUE(Variant1 == UnsignedCR || Variant2 == UnsignedCR);
  472. // Signed: Signed non-wrapped set, then smaller set, then any set.
  473. Variant1Full = Variant1.isFullSet() || Variant1.isSignWrappedSet();
  474. Variant2Full = Variant2.isFullSet() || Variant2.isSignWrappedSet();
  475. if (!Variant1Full && Variant2Full)
  476. EXPECT_EQ(Variant1, SignedCR);
  477. else if (Variant1Full && !Variant2Full)
  478. EXPECT_EQ(Variant2, SignedCR);
  479. else if (Variant1.isSizeStrictlySmallerThan(Variant2))
  480. EXPECT_EQ(Variant1, SignedCR);
  481. else if (Variant2.isSizeStrictlySmallerThan(Variant1))
  482. EXPECT_EQ(Variant2, SignedCR);
  483. else
  484. EXPECT_TRUE(Variant1 == SignedCR || Variant2 == SignedCR);
  485. });
  486. }
  487. TEST_F(ConstantRangeTest, IntersectWithExhaustive) {
  488. testBinarySetOperationExhaustive(
  489. [](const ConstantRange &CR1, const ConstantRange &CR2,
  490. ConstantRange::PreferredRangeType Type) {
  491. return CR1.intersectWith(CR2, Type);
  492. },
  493. [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
  494. return CR1.contains(N) && CR2.contains(N);
  495. });
  496. }
  497. TEST_F(ConstantRangeTest, UnionWithExhaustive) {
  498. testBinarySetOperationExhaustive(
  499. [](const ConstantRange &CR1, const ConstantRange &CR2,
  500. ConstantRange::PreferredRangeType Type) {
  501. return CR1.unionWith(CR2, Type);
  502. },
  503. [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
  504. return CR1.contains(N) || CR2.contains(N);
  505. });
  506. }
  507. TEST_F(ConstantRangeTest, UnionWith) {
  508. EXPECT_EQ(Wrap.unionWith(One),
  509. ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));
  510. EXPECT_EQ(One.unionWith(Wrap), Wrap.unionWith(One));
  511. EXPECT_EQ(Empty.unionWith(Empty), Empty);
  512. EXPECT_EQ(Full.unionWith(Full), Full);
  513. EXPECT_EQ(Some.unionWith(Wrap), Full);
  514. // PR4545
  515. EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(
  516. ConstantRange(APInt(16, 0), APInt(16, 8))),
  517. ConstantRange(APInt(16, 14), APInt(16, 8)));
  518. EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(
  519. ConstantRange(APInt(16, 4), APInt(16, 0))),
  520. ConstantRange::getFull(16));
  521. EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(
  522. ConstantRange(APInt(16, 2), APInt(16, 1))),
  523. ConstantRange::getFull(16));
  524. }
  525. TEST_F(ConstantRangeTest, SetDifference) {
  526. EXPECT_EQ(Full.difference(Empty), Full);
  527. EXPECT_EQ(Full.difference(Full), Empty);
  528. EXPECT_EQ(Empty.difference(Empty), Empty);
  529. EXPECT_EQ(Empty.difference(Full), Empty);
  530. ConstantRange A(APInt(16, 3), APInt(16, 7));
  531. ConstantRange B(APInt(16, 5), APInt(16, 9));
  532. ConstantRange C(APInt(16, 3), APInt(16, 5));
  533. ConstantRange D(APInt(16, 7), APInt(16, 9));
  534. ConstantRange E(APInt(16, 5), APInt(16, 4));
  535. ConstantRange F(APInt(16, 7), APInt(16, 3));
  536. EXPECT_EQ(A.difference(B), C);
  537. EXPECT_EQ(B.difference(A), D);
  538. EXPECT_EQ(E.difference(A), F);
  539. }
  540. TEST_F(ConstantRangeTest, SubtractAPInt) {
  541. EXPECT_EQ(Full.subtract(APInt(16, 4)), Full);
  542. EXPECT_EQ(Empty.subtract(APInt(16, 4)), Empty);
  543. EXPECT_EQ(Some.subtract(APInt(16, 4)),
  544. ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
  545. EXPECT_EQ(Wrap.subtract(APInt(16, 4)),
  546. ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
  547. EXPECT_EQ(One.subtract(APInt(16, 4)),
  548. ConstantRange(APInt(16, 0x6)));
  549. }
  550. TEST_F(ConstantRangeTest, Add) {
  551. EXPECT_EQ(Full.add(APInt(16, 4)), Full);
  552. EXPECT_EQ(Full.add(Full), Full);
  553. EXPECT_EQ(Full.add(Empty), Empty);
  554. EXPECT_EQ(Full.add(One), Full);
  555. EXPECT_EQ(Full.add(Some), Full);
  556. EXPECT_EQ(Full.add(Wrap), Full);
  557. EXPECT_EQ(Empty.add(Empty), Empty);
  558. EXPECT_EQ(Empty.add(One), Empty);
  559. EXPECT_EQ(Empty.add(Some), Empty);
  560. EXPECT_EQ(Empty.add(Wrap), Empty);
  561. EXPECT_EQ(Empty.add(APInt(16, 4)), Empty);
  562. EXPECT_EQ(Some.add(APInt(16, 4)),
  563. ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
  564. EXPECT_EQ(Wrap.add(APInt(16, 4)),
  565. ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
  566. EXPECT_EQ(One.add(APInt(16, 4)),
  567. ConstantRange(APInt(16, 0xe)));
  568. }
  569. template <typename Fn1, typename Fn2>
  570. static void TestAddWithNoSignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn) {
  571. unsigned Bits = 4;
  572. EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
  573. const ConstantRange &CR2) {
  574. ConstantRange CR = RangeFn(CR1, CR2);
  575. APInt Min = APInt::getSignedMaxValue(Bits);
  576. APInt Max = APInt::getSignedMinValue(Bits);
  577. ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
  578. ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
  579. bool IsOverflow = false;
  580. APInt N = IntFn(IsOverflow, N1, N2);
  581. if (!IsOverflow) {
  582. if (N.slt(Min))
  583. Min = N;
  584. if (N.sgt(Max))
  585. Max = N;
  586. EXPECT_TRUE(CR.contains(N));
  587. }
  588. });
  589. });
  590. if (!CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) {
  591. if (Min.sgt(Max)) {
  592. EXPECT_TRUE(CR.isEmptySet());
  593. return;
  594. }
  595. ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
  596. EXPECT_EQ(Exact, CR);
  597. }
  598. });
  599. }
  600. template <typename Fn1, typename Fn2>
  601. static void TestAddWithNoUnsignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn) {
  602. unsigned Bits = 4;
  603. EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
  604. const ConstantRange &CR2) {
  605. ConstantRange CR = RangeFn(CR1, CR2);
  606. APInt Min = APInt::getMaxValue(Bits);
  607. APInt Max = APInt::getMinValue(Bits);
  608. ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
  609. ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
  610. bool IsOverflow = false;
  611. APInt N = IntFn(IsOverflow, N1, N2);
  612. if (!IsOverflow) {
  613. if (N.ult(Min))
  614. Min = N;
  615. if (N.ugt(Max))
  616. Max = N;
  617. EXPECT_TRUE(CR.contains(N));
  618. }
  619. });
  620. });
  621. if (!CR1.isWrappedSet() && !CR2.isWrappedSet()) {
  622. if (Min.ugt(Max)) {
  623. EXPECT_TRUE(CR.isEmptySet());
  624. return;
  625. }
  626. ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
  627. EXPECT_EQ(Exact, CR);
  628. }
  629. });
  630. }
  631. template <typename Fn1, typename Fn2, typename Fn3>
  632. static void TestAddWithNoSignedUnsignedWrapExhaustive(Fn1 RangeFn,
  633. Fn2 IntFnSigned,
  634. Fn3 IntFnUnsigned) {
  635. unsigned Bits = 4;
  636. EnumerateTwoConstantRanges(
  637. Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) {
  638. ConstantRange CR = RangeFn(CR1, CR2);
  639. APInt UMin = APInt::getMaxValue(Bits);
  640. APInt UMax = APInt::getMinValue(Bits);
  641. APInt SMin = APInt::getSignedMaxValue(Bits);
  642. APInt SMax = APInt::getSignedMinValue(Bits);
  643. ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
  644. ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
  645. bool IsOverflow = false, IsSignedOverflow = false;
  646. APInt N = IntFnSigned(IsSignedOverflow, N1, N2);
  647. (void) IntFnUnsigned(IsOverflow, N1, N2);
  648. if (!IsSignedOverflow && !IsOverflow) {
  649. if (N.slt(SMin))
  650. SMin = N;
  651. if (N.sgt(SMax))
  652. SMax = N;
  653. if (N.ult(UMin))
  654. UMin = N;
  655. if (N.ugt(UMax))
  656. UMax = N;
  657. EXPECT_TRUE(CR.contains(N));
  658. }
  659. });
  660. });
  661. if (!CR1.isWrappedSet() && !CR2.isWrappedSet() &&
  662. !CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) {
  663. if (UMin.ugt(UMax) || SMin.sgt(SMax)) {
  664. EXPECT_TRUE(CR.isEmptySet());
  665. return;
  666. }
  667. ConstantRange Exact =
  668. ConstantRange::getNonEmpty(SMin, SMax + 1)
  669. .intersectWith(ConstantRange::getNonEmpty(UMin, UMax + 1));
  670. EXPECT_EQ(Exact, CR);
  671. }
  672. });
  673. }
  674. TEST_F(ConstantRangeTest, AddWithNoWrap) {
  675. typedef OverflowingBinaryOperator OBO;
  676. EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoSignedWrap), Empty);
  677. EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoSignedWrap), Empty);
  678. EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoSignedWrap), Full);
  679. EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoSignedWrap), Full);
  680. EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoSignedWrap), Full);
  681. EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
  682. OBO::NoSignedWrap),
  683. ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN)));
  684. EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
  685. .addWithNoWrap(Full, OBO::NoSignedWrap),
  686. ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN)));
  687. EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, -1), APInt(16, 0)),
  688. OBO::NoSignedWrap),
  689. ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX)));
  690. EXPECT_EQ(ConstantRange(APInt(8, 100), APInt(8, 120))
  691. .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, 123)),
  692. OBO::NoSignedWrap),
  693. ConstantRange(8, false));
  694. EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, -100))
  695. .addWithNoWrap(ConstantRange(APInt(8, -110), APInt(8, -100)),
  696. OBO::NoSignedWrap),
  697. ConstantRange(8, false));
  698. EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
  699. .addWithNoWrap(ConstantRange(APInt(8, -128), APInt(8, 28)),
  700. OBO::NoSignedWrap),
  701. ConstantRange(8, true));
  702. EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
  703. .addWithNoWrap(ConstantRange(APInt(8, -120), APInt(8, 29)),
  704. OBO::NoSignedWrap),
  705. ConstantRange(APInt(8, -120), APInt(8, -128)));
  706. EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50))
  707. .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 20)),
  708. OBO::NoSignedWrap),
  709. ConstantRange(APInt(8, -40), APInt(8, 69)));
  710. EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
  711. .addWithNoWrap(ConstantRange(APInt(8, -50), APInt(8, 50)),
  712. OBO::NoSignedWrap),
  713. ConstantRange(APInt(8, -40), APInt(8, 69)));
  714. EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10))
  715. .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
  716. OBO::NoSignedWrap),
  717. ConstantRange(APInt(8, 125), APInt(8, 9)));
  718. EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
  719. .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, -10)),
  720. OBO::NoSignedWrap),
  721. ConstantRange(APInt(8, 125), APInt(8, 9)));
  722. TestAddWithNoSignedWrapExhaustive(
  723. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  724. return CR1.addWithNoWrap(CR2, OBO::NoSignedWrap);
  725. },
  726. [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
  727. return N1.sadd_ov(N2, IsOverflow);
  728. });
  729. EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoUnsignedWrap), Empty);
  730. EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoUnsignedWrap), Empty);
  731. EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
  732. EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoUnsignedWrap), Full);
  733. EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
  734. EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
  735. OBO::NoUnsignedWrap),
  736. ConstantRange(APInt(16, 1), APInt(16, 0)));
  737. EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
  738. .addWithNoWrap(Full, OBO::NoUnsignedWrap),
  739. ConstantRange(APInt(16, 1), APInt(16, 0)));
  740. EXPECT_EQ(ConstantRange(APInt(8, 200), APInt(8, 220))
  741. .addWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 123)),
  742. OBO::NoUnsignedWrap),
  743. ConstantRange(8, false));
  744. EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
  745. .addWithNoWrap(ConstantRange(APInt(8, 0), APInt(8, 156)),
  746. OBO::NoUnsignedWrap),
  747. ConstantRange(8, true));
  748. EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
  749. .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 29)),
  750. OBO::NoUnsignedWrap),
  751. ConstantRange(APInt(8, 10), APInt(8, 129)));
  752. EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, 10))
  753. .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
  754. OBO::NoUnsignedWrap),
  755. ConstantRange(APInt(8, 50), APInt(8, 0)));
  756. EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
  757. .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
  758. OBO::NoUnsignedWrap),
  759. ConstantRange(APInt(8, 60), APInt(8, -37)));
  760. EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, -30))
  761. .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
  762. OBO::NoUnsignedWrap),
  763. ConstantRange(APInt(8, 25), APInt(8, -11)));
  764. EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
  765. .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, -30)),
  766. OBO::NoUnsignedWrap),
  767. ConstantRange(APInt(8, 25), APInt(8, -11)));
  768. TestAddWithNoUnsignedWrapExhaustive(
  769. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  770. return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap);
  771. },
  772. [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
  773. return N1.uadd_ov(N2, IsOverflow);
  774. });
  775. EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
  776. .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
  777. OBO::NoSignedWrap),
  778. ConstantRange(APInt(8, 70), APInt(8, -128)));
  779. EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
  780. .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
  781. OBO::NoUnsignedWrap),
  782. ConstantRange(APInt(8, 70), APInt(8, 169)));
  783. EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
  784. .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
  785. OBO::NoUnsignedWrap | OBO::NoSignedWrap),
  786. ConstantRange(APInt(8, 70), APInt(8, -128)));
  787. EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
  788. .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
  789. OBO::NoSignedWrap),
  790. ConstantRange(APInt(8, -80), APInt(8, -21)));
  791. EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
  792. .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
  793. OBO::NoUnsignedWrap),
  794. ConstantRange(APInt(8, 176), APInt(8, 235)));
  795. EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
  796. .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
  797. OBO::NoUnsignedWrap | OBO::NoSignedWrap),
  798. ConstantRange(APInt(8, 176), APInt(8, 235)));
  799. TestAddWithNoSignedUnsignedWrapExhaustive(
  800. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  801. return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);
  802. },
  803. [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
  804. return N1.sadd_ov(N2, IsOverflow);
  805. },
  806. [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
  807. return N1.uadd_ov(N2, IsOverflow);
  808. });
  809. }
  810. TEST_F(ConstantRangeTest, Sub) {
  811. EXPECT_EQ(Full.sub(APInt(16, 4)), Full);
  812. EXPECT_EQ(Full.sub(Full), Full);
  813. EXPECT_EQ(Full.sub(Empty), Empty);
  814. EXPECT_EQ(Full.sub(One), Full);
  815. EXPECT_EQ(Full.sub(Some), Full);
  816. EXPECT_EQ(Full.sub(Wrap), Full);
  817. EXPECT_EQ(Empty.sub(Empty), Empty);
  818. EXPECT_EQ(Empty.sub(One), Empty);
  819. EXPECT_EQ(Empty.sub(Some), Empty);
  820. EXPECT_EQ(Empty.sub(Wrap), Empty);
  821. EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty);
  822. EXPECT_EQ(Some.sub(APInt(16, 4)),
  823. ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
  824. EXPECT_EQ(Some.sub(Some),
  825. ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0)));
  826. EXPECT_EQ(Wrap.sub(APInt(16, 4)),
  827. ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
  828. EXPECT_EQ(One.sub(APInt(16, 4)),
  829. ConstantRange(APInt(16, 0x6)));
  830. }
  831. TEST_F(ConstantRangeTest, Multiply) {
  832. EXPECT_EQ(Full.multiply(Full), Full);
  833. EXPECT_EQ(Full.multiply(Empty), Empty);
  834. EXPECT_EQ(Full.multiply(One), Full);
  835. EXPECT_EQ(Full.multiply(Some), Full);
  836. EXPECT_EQ(Full.multiply(Wrap), Full);
  837. EXPECT_EQ(Empty.multiply(Empty), Empty);
  838. EXPECT_EQ(Empty.multiply(One), Empty);
  839. EXPECT_EQ(Empty.multiply(Some), Empty);
  840. EXPECT_EQ(Empty.multiply(Wrap), Empty);
  841. EXPECT_EQ(One.multiply(One), ConstantRange(APInt(16, 0xa*0xa),
  842. APInt(16, 0xa*0xa + 1)));
  843. EXPECT_EQ(One.multiply(Some), ConstantRange(APInt(16, 0xa*0xa),
  844. APInt(16, 0xa*0xaa9 + 1)));
  845. EXPECT_EQ(One.multiply(Wrap), Full);
  846. EXPECT_EQ(Some.multiply(Some), Full);
  847. EXPECT_EQ(Some.multiply(Wrap), Full);
  848. EXPECT_EQ(Wrap.multiply(Wrap), Full);
  849. ConstantRange Zero(APInt(16, 0));
  850. EXPECT_EQ(Zero.multiply(Full), Zero);
  851. EXPECT_EQ(Zero.multiply(Some), Zero);
  852. EXPECT_EQ(Zero.multiply(Wrap), Zero);
  853. EXPECT_EQ(Full.multiply(Zero), Zero);
  854. EXPECT_EQ(Some.multiply(Zero), Zero);
  855. EXPECT_EQ(Wrap.multiply(Zero), Zero);
  856. // http://llvm.org/PR4545
  857. EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply(
  858. ConstantRange(APInt(4, 6), APInt(4, 2))),
  859. ConstantRange(4, /*isFullSet=*/true));
  860. EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply(
  861. ConstantRange(APInt(8, 252), APInt(8, 4))),
  862. ConstantRange(APInt(8, 250), APInt(8, 9)));
  863. EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply(
  864. ConstantRange(APInt(8, 2), APInt(8, 4))),
  865. ConstantRange(APInt(8, 250), APInt(8, 253)));
  866. // TODO: This should be return [-2, 0]
  867. EXPECT_EQ(ConstantRange(APInt(8, -2)).multiply(
  868. ConstantRange(APInt(8, 0), APInt(8, 2))),
  869. ConstantRange(APInt(8, -2), APInt(8, 1)));
  870. }
  871. TEST_F(ConstantRangeTest, UMax) {
  872. EXPECT_EQ(Full.umax(Full), Full);
  873. EXPECT_EQ(Full.umax(Empty), Empty);
  874. EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
  875. EXPECT_EQ(Full.umax(Wrap), Full);
  876. EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
  877. EXPECT_EQ(Empty.umax(Empty), Empty);
  878. EXPECT_EQ(Empty.umax(Some), Empty);
  879. EXPECT_EQ(Empty.umax(Wrap), Empty);
  880. EXPECT_EQ(Empty.umax(One), Empty);
  881. EXPECT_EQ(Some.umax(Some), Some);
  882. EXPECT_EQ(Some.umax(Wrap), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
  883. EXPECT_EQ(Some.umax(One), Some);
  884. // TODO: ConstantRange is currently over-conservative here.
  885. EXPECT_EQ(Wrap.umax(Wrap), Full);
  886. EXPECT_EQ(Wrap.umax(One), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
  887. EXPECT_EQ(One.umax(One), One);
  888. }
  889. TEST_F(ConstantRangeTest, SMax) {
  890. EXPECT_EQ(Full.smax(Full), Full);
  891. EXPECT_EQ(Full.smax(Empty), Empty);
  892. EXPECT_EQ(Full.smax(Some), ConstantRange(APInt(16, 0xa),
  893. APInt::getSignedMinValue(16)));
  894. EXPECT_EQ(Full.smax(Wrap), Full);
  895. EXPECT_EQ(Full.smax(One), ConstantRange(APInt(16, 0xa),
  896. APInt::getSignedMinValue(16)));
  897. EXPECT_EQ(Empty.smax(Empty), Empty);
  898. EXPECT_EQ(Empty.smax(Some), Empty);
  899. EXPECT_EQ(Empty.smax(Wrap), Empty);
  900. EXPECT_EQ(Empty.smax(One), Empty);
  901. EXPECT_EQ(Some.smax(Some), Some);
  902. EXPECT_EQ(Some.smax(Wrap), ConstantRange(APInt(16, 0xa),
  903. APInt(16, (uint64_t)INT16_MIN)));
  904. EXPECT_EQ(Some.smax(One), Some);
  905. EXPECT_EQ(Wrap.smax(One), ConstantRange(APInt(16, 0xa),
  906. APInt(16, (uint64_t)INT16_MIN)));
  907. EXPECT_EQ(One.smax(One), One);
  908. }
  909. TEST_F(ConstantRangeTest, UMin) {
  910. EXPECT_EQ(Full.umin(Full), Full);
  911. EXPECT_EQ(Full.umin(Empty), Empty);
  912. EXPECT_EQ(Full.umin(Some), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
  913. EXPECT_EQ(Full.umin(Wrap), Full);
  914. EXPECT_EQ(Empty.umin(Empty), Empty);
  915. EXPECT_EQ(Empty.umin(Some), Empty);
  916. EXPECT_EQ(Empty.umin(Wrap), Empty);
  917. EXPECT_EQ(Empty.umin(One), Empty);
  918. EXPECT_EQ(Some.umin(Some), Some);
  919. EXPECT_EQ(Some.umin(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
  920. EXPECT_EQ(Some.umin(One), One);
  921. // TODO: ConstantRange is currently over-conservative here.
  922. EXPECT_EQ(Wrap.umin(Wrap), Full);
  923. EXPECT_EQ(Wrap.umin(One), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
  924. EXPECT_EQ(One.umin(One), One);
  925. }
  926. TEST_F(ConstantRangeTest, SMin) {
  927. EXPECT_EQ(Full.smin(Full), Full);
  928. EXPECT_EQ(Full.smin(Empty), Empty);
  929. EXPECT_EQ(Full.smin(Some), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
  930. APInt(16, 0xaaa)));
  931. EXPECT_EQ(Full.smin(Wrap), Full);
  932. EXPECT_EQ(Empty.smin(Empty), Empty);
  933. EXPECT_EQ(Empty.smin(Some), Empty);
  934. EXPECT_EQ(Empty.smin(Wrap), Empty);
  935. EXPECT_EQ(Empty.smin(One), Empty);
  936. EXPECT_EQ(Some.smin(Some), Some);
  937. EXPECT_EQ(Some.smin(Wrap), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
  938. APInt(16, 0xaaa)));
  939. EXPECT_EQ(Some.smin(One), One);
  940. // TODO: ConstantRange is currently over-conservative here.
  941. EXPECT_EQ(Wrap.smin(Wrap), Full);
  942. EXPECT_EQ(Wrap.smin(One), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
  943. APInt(16, 0xb)));
  944. EXPECT_EQ(One.smin(One), One);
  945. }
  946. TEST_F(ConstantRangeTest, UDiv) {
  947. EXPECT_EQ(Full.udiv(Full), Full);
  948. EXPECT_EQ(Full.udiv(Empty), Empty);
  949. EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0),
  950. APInt(16, 0xffff / 0xa + 1)));
  951. EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0),
  952. APInt(16, 0xffff / 0xa + 1)));
  953. EXPECT_EQ(Full.udiv(Wrap), Full);
  954. EXPECT_EQ(Empty.udiv(Empty), Empty);
  955. EXPECT_EQ(Empty.udiv(One), Empty);
  956. EXPECT_EQ(Empty.udiv(Some), Empty);
  957. EXPECT_EQ(Empty.udiv(Wrap), Empty);
  958. EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));
  959. EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
  960. EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
  961. EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
  962. EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
  963. EXPECT_EQ(Wrap.udiv(Wrap), Full);
  964. ConstantRange Zero(APInt(16, 0));
  965. EXPECT_EQ(Zero.udiv(One), Zero);
  966. EXPECT_EQ(Zero.udiv(Full), Zero);
  967. EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full),
  968. ConstantRange(APInt(16, 0), APInt(16, 99)));
  969. EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full),
  970. ConstantRange(APInt(16, 0), APInt(16, 99)));
  971. }
  972. TEST_F(ConstantRangeTest, SDiv) {
  973. unsigned Bits = 4;
  974. EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
  975. const ConstantRange &CR2) {
  976. // Collect possible results in a bit vector. We store the signed value plus
  977. // a bias to make it unsigned.
  978. int Bias = 1 << (Bits - 1);
  979. BitVector Results(1 << Bits);
  980. ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
  981. ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
  982. // Division by zero is UB.
  983. if (N2 == 0)
  984. return;
  985. // SignedMin / -1 is UB.
  986. if (N1.isMinSignedValue() && N2.isAllOnesValue())
  987. return;
  988. APInt N = N1.sdiv(N2);
  989. Results.set(N.getSExtValue() + Bias);
  990. });
  991. });
  992. ConstantRange CR = CR1.sdiv(CR2);
  993. if (Results.none()) {
  994. EXPECT_TRUE(CR.isEmptySet());
  995. return;
  996. }
  997. // If there is a non-full signed envelope, that should be the result.
  998. APInt SMin(Bits, Results.find_first() - Bias);
  999. APInt SMax(Bits, Results.find_last() - Bias);
  1000. ConstantRange Envelope = ConstantRange::getNonEmpty(SMin, SMax + 1);
  1001. if (!Envelope.isFullSet()) {
  1002. EXPECT_EQ(Envelope, CR);
  1003. return;
  1004. }
  1005. // If the signed envelope is a full set, try to find a smaller sign wrapped
  1006. // set that is separated in negative and positive components (or one which
  1007. // can also additionally contain zero).
  1008. int LastNeg = Results.find_last_in(0, Bias) - Bias;
  1009. int LastPos = Results.find_next(Bias) - Bias;
  1010. if (Results[Bias]) {
  1011. if (LastNeg == -1)
  1012. ++LastNeg;
  1013. else if (LastPos == 1)
  1014. --LastPos;
  1015. }
  1016. APInt WMax(Bits, LastNeg);
  1017. APInt WMin(Bits, LastPos);
  1018. ConstantRange Wrapped = ConstantRange::getNonEmpty(WMin, WMax + 1);
  1019. EXPECT_EQ(Wrapped, CR);
  1020. });
  1021. }
  1022. TEST_F(ConstantRangeTest, URem) {
  1023. EXPECT_EQ(Full.urem(Empty), Empty);
  1024. EXPECT_EQ(Empty.urem(Full), Empty);
  1025. // urem by zero is poison.
  1026. EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty);
  1027. // urem by full range doesn't contain MaxValue.
  1028. EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff)));
  1029. // urem is upper bounded by maximum RHS minus one.
  1030. EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))),
  1031. ConstantRange(APInt(16, 0), APInt(16, 122)));
  1032. // urem is upper bounded by maximum LHS.
  1033. EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full),
  1034. ConstantRange(APInt(16, 0), APInt(16, 123)));
  1035. // If the LHS is always lower than the RHS, the result is the LHS.
  1036. EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
  1037. .urem(ConstantRange(APInt(16, 20), APInt(16, 30))),
  1038. ConstantRange(APInt(16, 10), APInt(16, 20)));
  1039. // It has to be strictly lower, otherwise the top value may wrap to zero.
  1040. EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
  1041. .urem(ConstantRange(APInt(16, 19), APInt(16, 30))),
  1042. ConstantRange(APInt(16, 0), APInt(16, 20)));
  1043. // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].
  1044. EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
  1045. .urem(ConstantRange(APInt(16, 10))),
  1046. ConstantRange(APInt(16, 0), APInt(16, 10)));
  1047. TestUnsignedBinOpExhaustive(
  1048. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1049. return CR1.urem(CR2);
  1050. },
  1051. [](const APInt &N1, const APInt &N2) {
  1052. return N1.urem(N2);
  1053. },
  1054. /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
  1055. }
  1056. TEST_F(ConstantRangeTest, SRem) {
  1057. EXPECT_EQ(Full.srem(Empty), Empty);
  1058. EXPECT_EQ(Empty.srem(Full), Empty);
  1059. // srem by zero is UB.
  1060. EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);
  1061. // srem by full range doesn't contain SignedMinValue.
  1062. EXPECT_EQ(Full.srem(Full), ConstantRange(APInt::getSignedMinValue(16) + 1,
  1063. APInt::getSignedMinValue(16)));
  1064. ConstantRange PosMod(APInt(16, 10), APInt(16, 21)); // [10, 20]
  1065. ConstantRange NegMod(APInt(16, -20), APInt(16, -9)); // [-20, -10]
  1066. ConstantRange IntMinMod(APInt::getSignedMinValue(16));
  1067. ConstantRange Expected(16, true);
  1068. // srem is bounded by abs(RHS) minus one.
  1069. ConstantRange PosLargeLHS(APInt(16, 0), APInt(16, 41));
  1070. Expected = ConstantRange(APInt(16, 0), APInt(16, 20));
  1071. EXPECT_EQ(PosLargeLHS.srem(PosMod), Expected);
  1072. EXPECT_EQ(PosLargeLHS.srem(NegMod), Expected);
  1073. ConstantRange NegLargeLHS(APInt(16, -40), APInt(16, 1));
  1074. Expected = ConstantRange(APInt(16, -19), APInt(16, 1));
  1075. EXPECT_EQ(NegLargeLHS.srem(PosMod), Expected);
  1076. EXPECT_EQ(NegLargeLHS.srem(NegMod), Expected);
  1077. ConstantRange PosNegLargeLHS(APInt(16, -32), APInt(16, 38));
  1078. Expected = ConstantRange(APInt(16, -19), APInt(16, 20));
  1079. EXPECT_EQ(PosNegLargeLHS.srem(PosMod), Expected);
  1080. EXPECT_EQ(PosNegLargeLHS.srem(NegMod), Expected);
  1081. // srem is bounded by LHS.
  1082. ConstantRange PosLHS(APInt(16, 0), APInt(16, 16));
  1083. EXPECT_EQ(PosLHS.srem(PosMod), PosLHS);
  1084. EXPECT_EQ(PosLHS.srem(NegMod), PosLHS);
  1085. EXPECT_EQ(PosLHS.srem(IntMinMod), PosLHS);
  1086. ConstantRange NegLHS(APInt(16, -15), APInt(16, 1));
  1087. EXPECT_EQ(NegLHS.srem(PosMod), NegLHS);
  1088. EXPECT_EQ(NegLHS.srem(NegMod), NegLHS);
  1089. EXPECT_EQ(NegLHS.srem(IntMinMod), NegLHS);
  1090. ConstantRange PosNegLHS(APInt(16, -12), APInt(16, 18));
  1091. EXPECT_EQ(PosNegLHS.srem(PosMod), PosNegLHS);
  1092. EXPECT_EQ(PosNegLHS.srem(NegMod), PosNegLHS);
  1093. EXPECT_EQ(PosNegLHS.srem(IntMinMod), PosNegLHS);
  1094. // srem is LHS if it is smaller than RHS.
  1095. ConstantRange PosSmallLHS(APInt(16, 3), APInt(16, 8));
  1096. EXPECT_EQ(PosSmallLHS.srem(PosMod), PosSmallLHS);
  1097. EXPECT_EQ(PosSmallLHS.srem(NegMod), PosSmallLHS);
  1098. EXPECT_EQ(PosSmallLHS.srem(IntMinMod), PosSmallLHS);
  1099. ConstantRange NegSmallLHS(APInt(16, -7), APInt(16, -2));
  1100. EXPECT_EQ(NegSmallLHS.srem(PosMod), NegSmallLHS);
  1101. EXPECT_EQ(NegSmallLHS.srem(NegMod), NegSmallLHS);
  1102. EXPECT_EQ(NegSmallLHS.srem(IntMinMod), NegSmallLHS);
  1103. ConstantRange PosNegSmallLHS(APInt(16, -3), APInt(16, 8));
  1104. EXPECT_EQ(PosNegSmallLHS.srem(PosMod), PosNegSmallLHS);
  1105. EXPECT_EQ(PosNegSmallLHS.srem(NegMod), PosNegSmallLHS);
  1106. EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);
  1107. // Example of a suboptimal result:
  1108. // [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
  1109. EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
  1110. .srem(ConstantRange(APInt(16, 10))),
  1111. ConstantRange(APInt(16, 0), APInt(16, 10)));
  1112. TestSignedBinOpExhaustive(
  1113. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1114. return CR1.srem(CR2);
  1115. },
  1116. [](const APInt &N1, const APInt &N2) {
  1117. return N1.srem(N2);
  1118. },
  1119. /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
  1120. }
  1121. TEST_F(ConstantRangeTest, Shl) {
  1122. ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
  1123. ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
  1124. EXPECT_EQ(Full.shl(Full), Full);
  1125. EXPECT_EQ(Full.shl(Empty), Empty);
  1126. EXPECT_EQ(Full.shl(One), Full); // TODO: [0, (-1 << 0xa) + 1)
  1127. EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1)
  1128. EXPECT_EQ(Full.shl(Wrap), Full);
  1129. EXPECT_EQ(Empty.shl(Empty), Empty);
  1130. EXPECT_EQ(Empty.shl(One), Empty);
  1131. EXPECT_EQ(Empty.shl(Some), Empty);
  1132. EXPECT_EQ(Empty.shl(Wrap), Empty);
  1133. EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),
  1134. APInt(16, (0xa << 0xa) + 1)));
  1135. EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0)
  1136. EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1)
  1137. EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01)
  1138. EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1)
  1139. EXPECT_EQ(Wrap.shl(Wrap), Full);
  1140. EXPECT_EQ(
  1141. Some2.shl(ConstantRange(APInt(16, 0x1))),
  1142. ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1));
  1143. EXPECT_EQ(One.shl(WrapNullMax), Full);
  1144. }
  1145. TEST_F(ConstantRangeTest, Lshr) {
  1146. EXPECT_EQ(Full.lshr(Full), Full);
  1147. EXPECT_EQ(Full.lshr(Empty), Empty);
  1148. EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),
  1149. APInt(16, (0xffff >> 0xa) + 1)));
  1150. EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),
  1151. APInt(16, (0xffff >> 0xa) + 1)));
  1152. EXPECT_EQ(Full.lshr(Wrap), Full);
  1153. EXPECT_EQ(Empty.lshr(Empty), Empty);
  1154. EXPECT_EQ(Empty.lshr(One), Empty);
  1155. EXPECT_EQ(Empty.lshr(Some), Empty);
  1156. EXPECT_EQ(Empty.lshr(Wrap), Empty);
  1157. EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0)));
  1158. EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));
  1159. EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
  1160. EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),
  1161. APInt(16, (0xaaa >> 0xa) + 1)));
  1162. EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
  1163. EXPECT_EQ(Wrap.lshr(Wrap), Full);
  1164. }
  1165. TEST_F(ConstantRangeTest, Ashr) {
  1166. EXPECT_EQ(Full.ashr(Full), Full);
  1167. EXPECT_EQ(Full.ashr(Empty), Empty);
  1168. EXPECT_EQ(Full.ashr(One), ConstantRange(APInt(16, 0xffe0),
  1169. APInt(16, (0x7fff >> 0xa) + 1 )));
  1170. ConstantRange Small(APInt(16, 0xa), APInt(16, 0xb));
  1171. EXPECT_EQ(Full.ashr(Small), ConstantRange(APInt(16, 0xffe0),
  1172. APInt(16, (0x7fff >> 0xa) + 1 )));
  1173. EXPECT_EQ(Full.ashr(Some), ConstantRange(APInt(16, 0xffe0),
  1174. APInt(16, (0x7fff >> 0xa) + 1 )));
  1175. EXPECT_EQ(Full.ashr(Wrap), Full);
  1176. EXPECT_EQ(Empty.ashr(Empty), Empty);
  1177. EXPECT_EQ(Empty.ashr(One), Empty);
  1178. EXPECT_EQ(Empty.ashr(Some), Empty);
  1179. EXPECT_EQ(Empty.ashr(Wrap), Empty);
  1180. EXPECT_EQ(One.ashr(One), ConstantRange(APInt(16, 0)));
  1181. EXPECT_EQ(One.ashr(Some), ConstantRange(APInt(16, 0)));
  1182. EXPECT_EQ(One.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
  1183. EXPECT_EQ(Some.ashr(Some), ConstantRange(APInt(16, 0),
  1184. APInt(16, (0xaaa >> 0xa) + 1)));
  1185. EXPECT_EQ(Some.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
  1186. EXPECT_EQ(Wrap.ashr(Wrap), Full);
  1187. ConstantRange Neg(APInt(16, 0xf3f0, true), APInt(16, 0xf7f8, true));
  1188. EXPECT_EQ(Neg.ashr(Small), ConstantRange(APInt(16, 0xfffc, true),
  1189. APInt(16, 0xfffe, true)));
  1190. }
  1191. TEST(ConstantRange, MakeAllowedICmpRegion) {
  1192. // PR8250
  1193. ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32));
  1194. EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax)
  1195. .isEmptySet());
  1196. }
  1197. TEST(ConstantRange, MakeSatisfyingICmpRegion) {
  1198. ConstantRange LowHalf(APInt(8, 0), APInt(8, 128));
  1199. ConstantRange HighHalf(APInt(8, 128), APInt(8, 0));
  1200. ConstantRange EmptySet(8, /* isFullSet = */ false);
  1201. EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf),
  1202. HighHalf);
  1203. EXPECT_EQ(
  1204. ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf),
  1205. LowHalf);
  1206. EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ,
  1207. HighHalf).isEmptySet());
  1208. ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200));
  1209. EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT,
  1210. UnsignedSample),
  1211. ConstantRange(APInt(8, 0), APInt(8, 5)));
  1212. EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE,
  1213. UnsignedSample),
  1214. ConstantRange(APInt(8, 0), APInt(8, 6)));
  1215. EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT,
  1216. UnsignedSample),
  1217. ConstantRange(APInt(8, 200), APInt(8, 0)));
  1218. EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE,
  1219. UnsignedSample),
  1220. ConstantRange(APInt(8, 199), APInt(8, 0)));
  1221. ConstantRange SignedSample(APInt(8, -5), APInt(8, 5));
  1222. EXPECT_EQ(
  1223. ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample),
  1224. ConstantRange(APInt(8, -128), APInt(8, -5)));
  1225. EXPECT_EQ(
  1226. ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample),
  1227. ConstantRange(APInt(8, -128), APInt(8, -4)));
  1228. EXPECT_EQ(
  1229. ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample),
  1230. ConstantRange(APInt(8, 5), APInt(8, -128)));
  1231. EXPECT_EQ(
  1232. ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample),
  1233. ConstantRange(APInt(8, 4), APInt(8, -128)));
  1234. }
  1235. TEST(ConstantRange, MakeGuaranteedNoWrapRegion) {
  1236. const int IntMin4Bits = 8;
  1237. const int IntMax4Bits = 7;
  1238. typedef OverflowingBinaryOperator OBO;
  1239. for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
  1240. APInt C(4, Const, true /* = isSigned */);
  1241. auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
  1242. Instruction::Add, C, OBO::NoUnsignedWrap);
  1243. EXPECT_FALSE(NUWRegion.isEmptySet());
  1244. auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
  1245. Instruction::Add, C, OBO::NoSignedWrap);
  1246. EXPECT_FALSE(NSWRegion.isEmptySet());
  1247. for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
  1248. ++I) {
  1249. bool Overflow = false;
  1250. (void)I.uadd_ov(C, Overflow);
  1251. EXPECT_FALSE(Overflow);
  1252. }
  1253. for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
  1254. ++I) {
  1255. bool Overflow = false;
  1256. (void)I.sadd_ov(C, Overflow);
  1257. EXPECT_FALSE(Overflow);
  1258. }
  1259. }
  1260. for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
  1261. APInt C(4, Const, true /* = isSigned */);
  1262. auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
  1263. Instruction::Sub, C, OBO::NoUnsignedWrap);
  1264. EXPECT_FALSE(NUWRegion.isEmptySet());
  1265. auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
  1266. Instruction::Sub, C, OBO::NoSignedWrap);
  1267. EXPECT_FALSE(NSWRegion.isEmptySet());
  1268. for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
  1269. ++I) {
  1270. bool Overflow = false;
  1271. (void)I.usub_ov(C, Overflow);
  1272. EXPECT_FALSE(Overflow);
  1273. }
  1274. for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
  1275. ++I) {
  1276. bool Overflow = false;
  1277. (void)I.ssub_ov(C, Overflow);
  1278. EXPECT_FALSE(Overflow);
  1279. }
  1280. }
  1281. auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
  1282. Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
  1283. OBO::NoSignedWrap);
  1284. EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
  1285. NSWForAllValues.getSingleElement()->isMinValue());
  1286. NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
  1287. Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
  1288. OBO::NoSignedWrap);
  1289. EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
  1290. NSWForAllValues.getSingleElement()->isMaxValue());
  1291. auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
  1292. Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
  1293. OBO::NoUnsignedWrap);
  1294. EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
  1295. NUWForAllValues.getSingleElement()->isMinValue());
  1296. NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
  1297. Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
  1298. OBO::NoUnsignedWrap);
  1299. EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
  1300. NUWForAllValues.getSingleElement()->isMaxValue());
  1301. EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
  1302. Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
  1303. EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
  1304. Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
  1305. EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
  1306. Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
  1307. EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
  1308. Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
  1309. ConstantRange OneToFive(APInt(32, 1), APInt(32, 6));
  1310. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1311. Instruction::Add, OneToFive, OBO::NoSignedWrap),
  1312. ConstantRange(APInt::getSignedMinValue(32),
  1313. APInt::getSignedMaxValue(32) - 4));
  1314. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1315. Instruction::Add, OneToFive, OBO::NoUnsignedWrap),
  1316. ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));
  1317. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1318. Instruction::Sub, OneToFive, OBO::NoSignedWrap),
  1319. ConstantRange(APInt::getSignedMinValue(32) + 5,
  1320. APInt::getSignedMinValue(32)));
  1321. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1322. Instruction::Sub, OneToFive, OBO::NoUnsignedWrap),
  1323. ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));
  1324. ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1));
  1325. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1326. Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap),
  1327. ConstantRange(APInt::getSignedMinValue(32) + 5,
  1328. APInt::getSignedMinValue(32)));
  1329. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1330. Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
  1331. ConstantRange(APInt(32, 0), APInt(32, 2)));
  1332. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1333. Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap),
  1334. ConstantRange(APInt::getSignedMinValue(32),
  1335. APInt::getSignedMaxValue(32) - 4));
  1336. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1337. Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
  1338. ConstantRange(APInt::getMaxValue(32) - 1,
  1339. APInt::getMinValue(32)));
  1340. ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2));
  1341. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1342. Instruction::Add, MinusOneToOne, OBO::NoSignedWrap),
  1343. ConstantRange(APInt::getSignedMinValue(32) + 1,
  1344. APInt::getSignedMinValue(32) - 1));
  1345. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1346. Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap),
  1347. ConstantRange(APInt(32, 0), APInt(32, 1)));
  1348. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1349. Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap),
  1350. ConstantRange(APInt::getSignedMinValue(32) + 1,
  1351. APInt::getSignedMinValue(32) - 1));
  1352. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1353. Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap),
  1354. ConstantRange(APInt::getMaxValue(32),
  1355. APInt::getMinValue(32)));
  1356. ConstantRange One(APInt(32, 1), APInt(32, 2));
  1357. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1358. Instruction::Add, One, OBO::NoSignedWrap),
  1359. ConstantRange(APInt::getSignedMinValue(32),
  1360. APInt::getSignedMaxValue(32)));
  1361. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1362. Instruction::Add, One, OBO::NoUnsignedWrap),
  1363. ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
  1364. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1365. Instruction::Sub, One, OBO::NoSignedWrap),
  1366. ConstantRange(APInt::getSignedMinValue(32) + 1,
  1367. APInt::getSignedMinValue(32)));
  1368. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1369. Instruction::Sub, One, OBO::NoUnsignedWrap),
  1370. ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
  1371. ConstantRange OneLessThanBitWidth(APInt(32, 0), APInt(32, 31) + 1);
  1372. ConstantRange UpToBitWidth(APInt(32, 0), APInt(32, 32) + 1);
  1373. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1374. Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
  1375. ConstantRange::makeGuaranteedNoWrapRegion(
  1376. Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
  1377. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1378. Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
  1379. ConstantRange::makeGuaranteedNoWrapRegion(
  1380. Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
  1381. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1382. Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
  1383. ConstantRange(APInt(32, 0), APInt(32, 1) + 1));
  1384. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1385. Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
  1386. ConstantRange(APInt(32, -1), APInt(32, 0) + 1));
  1387. EXPECT_EQ(
  1388. ConstantRange::makeGuaranteedNoWrapRegion(
  1389. Instruction::Shl, ConstantRange::getFull(32), OBO::NoUnsignedWrap),
  1390. ConstantRange::makeGuaranteedNoWrapRegion(
  1391. Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
  1392. EXPECT_EQ(
  1393. ConstantRange::makeGuaranteedNoWrapRegion(
  1394. Instruction::Shl, ConstantRange::getFull(32), OBO::NoSignedWrap),
  1395. ConstantRange::makeGuaranteedNoWrapRegion(
  1396. Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
  1397. ConstantRange IllegalShAmt(APInt(32, 32), APInt(32, 0) + 1);
  1398. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1399. Instruction::Shl, IllegalShAmt, OBO::NoUnsignedWrap),
  1400. ConstantRange::getFull(32));
  1401. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1402. Instruction::Shl, IllegalShAmt, OBO::NoSignedWrap),
  1403. ConstantRange::getFull(32));
  1404. EXPECT_EQ(
  1405. ConstantRange::makeGuaranteedNoWrapRegion(
  1406. Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
  1407. OBO::NoUnsignedWrap),
  1408. ConstantRange::makeGuaranteedNoWrapRegion(
  1409. Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
  1410. OBO::NoUnsignedWrap));
  1411. EXPECT_EQ(
  1412. ConstantRange::makeGuaranteedNoWrapRegion(
  1413. Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
  1414. OBO::NoSignedWrap),
  1415. ConstantRange::makeGuaranteedNoWrapRegion(
  1416. Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
  1417. OBO::NoSignedWrap));
  1418. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1419. Instruction::Shl,
  1420. ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
  1421. OBO::NoUnsignedWrap),
  1422. ConstantRange(APInt(32, 0), APInt(32, 65535) + 1));
  1423. EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
  1424. Instruction::Shl,
  1425. ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
  1426. OBO::NoSignedWrap),
  1427. ConstantRange(APInt(32, -32768), APInt(32, 32767) + 1));
  1428. }
  1429. template<typename Fn>
  1430. void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,
  1431. unsigned NoWrapKind, Fn OverflowFn) {
  1432. unsigned Bits = 5;
  1433. EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
  1434. if (CR.isEmptySet())
  1435. return;
  1436. if (Instruction::isShift(BinOp) && CR.getUnsignedMax().uge(Bits))
  1437. return;
  1438. ConstantRange NoWrap =
  1439. ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR, NoWrapKind);
  1440. ConstantRange Full = ConstantRange::getFull(Bits);
  1441. ForeachNumInConstantRange(Full, [&](const APInt &N1) {
  1442. bool NoOverflow = true;
  1443. bool Overflow = true;
  1444. ForeachNumInConstantRange(CR, [&](const APInt &N2) {
  1445. if (OverflowFn(N1, N2))
  1446. NoOverflow = false;
  1447. else
  1448. Overflow = false;
  1449. });
  1450. EXPECT_EQ(NoOverflow, NoWrap.contains(N1));
  1451. // The no-wrap range is exact for single-element ranges.
  1452. if (CR.isSingleElement()) {
  1453. EXPECT_EQ(Overflow, !NoWrap.contains(N1));
  1454. }
  1455. });
  1456. });
  1457. }
  1458. // Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element
  1459. // ranges also exact.
  1460. TEST(ConstantRange, NoWrapRegionExhaustive) {
  1461. TestNoWrapRegionExhaustive(
  1462. Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap,
  1463. [](const APInt &N1, const APInt &N2) {
  1464. bool Overflow;
  1465. (void) N1.uadd_ov(N2, Overflow);
  1466. return Overflow;
  1467. });
  1468. TestNoWrapRegionExhaustive(
  1469. Instruction::Add, OverflowingBinaryOperator::NoSignedWrap,
  1470. [](const APInt &N1, const APInt &N2) {
  1471. bool Overflow;
  1472. (void) N1.sadd_ov(N2, Overflow);
  1473. return Overflow;
  1474. });
  1475. TestNoWrapRegionExhaustive(
  1476. Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap,
  1477. [](const APInt &N1, const APInt &N2) {
  1478. bool Overflow;
  1479. (void) N1.usub_ov(N2, Overflow);
  1480. return Overflow;
  1481. });
  1482. TestNoWrapRegionExhaustive(
  1483. Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap,
  1484. [](const APInt &N1, const APInt &N2) {
  1485. bool Overflow;
  1486. (void) N1.ssub_ov(N2, Overflow);
  1487. return Overflow;
  1488. });
  1489. TestNoWrapRegionExhaustive(
  1490. Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap,
  1491. [](const APInt &N1, const APInt &N2) {
  1492. bool Overflow;
  1493. (void) N1.umul_ov(N2, Overflow);
  1494. return Overflow;
  1495. });
  1496. TestNoWrapRegionExhaustive(
  1497. Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap,
  1498. [](const APInt &N1, const APInt &N2) {
  1499. bool Overflow;
  1500. (void) N1.smul_ov(N2, Overflow);
  1501. return Overflow;
  1502. });
  1503. TestNoWrapRegionExhaustive(Instruction::Shl,
  1504. OverflowingBinaryOperator::NoUnsignedWrap,
  1505. [](const APInt &N1, const APInt &N2) {
  1506. bool Overflow;
  1507. (void)N1.ushl_ov(N2, Overflow);
  1508. return Overflow;
  1509. });
  1510. TestNoWrapRegionExhaustive(Instruction::Shl,
  1511. OverflowingBinaryOperator::NoSignedWrap,
  1512. [](const APInt &N1, const APInt &N2) {
  1513. bool Overflow;
  1514. (void)N1.sshl_ov(N2, Overflow);
  1515. return Overflow;
  1516. });
  1517. }
  1518. TEST(ConstantRange, GetEquivalentICmp) {
  1519. APInt RHS;
  1520. CmpInst::Predicate Pred;
  1521. EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
  1522. .getEquivalentICmp(Pred, RHS));
  1523. EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
  1524. EXPECT_EQ(RHS, APInt(32, 100));
  1525. EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100))
  1526. .getEquivalentICmp(Pred, RHS));
  1527. EXPECT_EQ(Pred, CmpInst::ICMP_SLT);
  1528. EXPECT_EQ(RHS, APInt(32, 100));
  1529. EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32))
  1530. .getEquivalentICmp(Pred, RHS));
  1531. EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
  1532. EXPECT_EQ(RHS, APInt(32, 100));
  1533. EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32))
  1534. .getEquivalentICmp(Pred, RHS));
  1535. EXPECT_EQ(Pred, CmpInst::ICMP_SGE);
  1536. EXPECT_EQ(RHS, APInt(32, 100));
  1537. EXPECT_TRUE(
  1538. ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred, RHS));
  1539. EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
  1540. EXPECT_EQ(RHS, APInt(32, 0));
  1541. EXPECT_TRUE(
  1542. ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred, RHS));
  1543. EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
  1544. EXPECT_EQ(RHS, APInt(32, 0));
  1545. EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200))
  1546. .getEquivalentICmp(Pred, RHS));
  1547. EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100),
  1548. APInt::getSignedMinValue(32) + APInt(32, 100))
  1549. .getEquivalentICmp(Pred, RHS));
  1550. EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100),
  1551. APInt::getMinValue(32) + APInt(32, 100))
  1552. .getEquivalentICmp(Pred, RHS));
  1553. EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred, RHS));
  1554. EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
  1555. EXPECT_EQ(RHS, APInt(32, 100));
  1556. EXPECT_TRUE(
  1557. ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred, RHS));
  1558. EXPECT_EQ(Pred, CmpInst::ICMP_NE);
  1559. EXPECT_EQ(RHS, APInt(32, 100));
  1560. EXPECT_TRUE(
  1561. ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred, RHS));
  1562. EXPECT_EQ(Pred, CmpInst::ICMP_NE);
  1563. EXPECT_EQ(RHS, APInt(512, 100));
  1564. // NB! It would be correct for the following four calls to getEquivalentICmp
  1565. // to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT.
  1566. // However, that's not the case today.
  1567. EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred, RHS));
  1568. EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
  1569. EXPECT_EQ(RHS, APInt(32, 0));
  1570. EXPECT_TRUE(
  1571. ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred, RHS));
  1572. EXPECT_EQ(Pred, CmpInst::ICMP_NE);
  1573. EXPECT_EQ(RHS, APInt(32, 0));
  1574. EXPECT_TRUE(ConstantRange(APInt(32, -1)).getEquivalentICmp(Pred, RHS));
  1575. EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
  1576. EXPECT_EQ(RHS, APInt(32, -1));
  1577. EXPECT_TRUE(
  1578. ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS));
  1579. EXPECT_EQ(Pred, CmpInst::ICMP_NE);
  1580. EXPECT_EQ(RHS, APInt(32, -1));
  1581. }
  1582. #define EXPECT_MAY_OVERFLOW(op) \
  1583. EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))
  1584. #define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \
  1585. EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))
  1586. #define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \
  1587. EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (op))
  1588. #define EXPECT_NEVER_OVERFLOWS(op) \
  1589. EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))
  1590. TEST_F(ConstantRangeTest, UnsignedAddOverflow) {
  1591. // Ill-defined - may overflow is a conservative result.
  1592. EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty));
  1593. EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some));
  1594. // Never overflow despite one full/wrap set.
  1595. ConstantRange Zero(APInt::getNullValue(16));
  1596. EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero));
  1597. EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero));
  1598. EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full));
  1599. EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap));
  1600. // But usually full/wrap always may overflow.
  1601. EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One));
  1602. EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One));
  1603. EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full));
  1604. EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap));
  1605. ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00));
  1606. ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
  1607. ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
  1608. EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1));
  1609. EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2));
  1610. EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A));
  1611. EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A));
  1612. ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400));
  1613. ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400));
  1614. EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1));
  1615. EXPECT_ALWAYS_OVERFLOWS_HIGH(A.unsignedAddMayOverflow(C2));
  1616. EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A));
  1617. EXPECT_ALWAYS_OVERFLOWS_HIGH(C2.unsignedAddMayOverflow(A));
  1618. }
  1619. TEST_F(ConstantRangeTest, UnsignedSubOverflow) {
  1620. // Ill-defined - may overflow is a conservative result.
  1621. EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty));
  1622. EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some));
  1623. // Never overflow despite one full/wrap set.
  1624. ConstantRange Zero(APInt::getNullValue(16));
  1625. ConstantRange Max(APInt::getAllOnesValue(16));
  1626. EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero));
  1627. EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero));
  1628. EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full));
  1629. EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap));
  1630. // But usually full/wrap always may overflow.
  1631. EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One));
  1632. EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One));
  1633. EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full));
  1634. EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap));
  1635. ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100));
  1636. ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200));
  1637. EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A));
  1638. EXPECT_ALWAYS_OVERFLOWS_LOW(A.unsignedSubMayOverflow(B));
  1639. ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101));
  1640. ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
  1641. EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1));
  1642. EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1));
  1643. ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102));
  1644. ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
  1645. EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2));
  1646. EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2));
  1647. }
  1648. TEST_F(ConstantRangeTest, SignedAddOverflow) {
  1649. // Ill-defined - may overflow is a conservative result.
  1650. EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty));
  1651. EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some));
  1652. // Never overflow despite one full/wrap set.
  1653. ConstantRange Zero(APInt::getNullValue(16));
  1654. EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero));
  1655. EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero));
  1656. EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full));
  1657. EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap));
  1658. // But usually full/wrap always may overflow.
  1659. EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One));
  1660. EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One));
  1661. EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full));
  1662. EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap));
  1663. ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
  1664. ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
  1665. ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
  1666. EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1));
  1667. EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2));
  1668. ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201));
  1669. ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202));
  1670. EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3));
  1671. EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4));
  1672. ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400));
  1673. ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400));
  1674. EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5));
  1675. EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedAddMayOverflow(B6));
  1676. ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
  1677. ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00));
  1678. ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00));
  1679. EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1));
  1680. EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2));
  1681. ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000));
  1682. ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000));
  1683. EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3));
  1684. EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4));
  1685. ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02));
  1686. ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01));
  1687. EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5));
  1688. EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedAddMayOverflow(D6));
  1689. ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
  1690. EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E));
  1691. ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000));
  1692. EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F));
  1693. }
  1694. TEST_F(ConstantRangeTest, SignedSubOverflow) {
  1695. // Ill-defined - may overflow is a conservative result.
  1696. EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty));
  1697. EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some));
  1698. // Never overflow despite one full/wrap set.
  1699. ConstantRange Zero(APInt::getNullValue(16));
  1700. EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero));
  1701. EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero));
  1702. // But usually full/wrap always may overflow.
  1703. EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One));
  1704. EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One));
  1705. EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full));
  1706. EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap));
  1707. ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
  1708. ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00));
  1709. ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00));
  1710. EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1));
  1711. EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2));
  1712. ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02));
  1713. ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01));
  1714. EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3));
  1715. EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedSubMayOverflow(B4));
  1716. ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
  1717. ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201));
  1718. ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202));
  1719. EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1));
  1720. EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2));
  1721. ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400));
  1722. ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400));
  1723. EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3));
  1724. EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedSubMayOverflow(D4));
  1725. ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
  1726. EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E));
  1727. ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001));
  1728. EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F));
  1729. }
  1730. template<typename Fn1, typename Fn2>
  1731. static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) {
  1732. // Constant range overflow checks are tested exhaustively on 4-bit numbers.
  1733. unsigned Bits = 4;
  1734. EnumerateTwoConstantRanges(Bits, [=](const ConstantRange &CR1,
  1735. const ConstantRange &CR2) {
  1736. // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the
  1737. // operations have overflow / have no overflow.
  1738. bool RangeHasOverflowLow = false;
  1739. bool RangeHasOverflowHigh = false;
  1740. bool RangeHasNoOverflow = false;
  1741. ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
  1742. ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
  1743. bool IsOverflowHigh;
  1744. if (!OverflowFn(IsOverflowHigh, N1, N2)) {
  1745. RangeHasNoOverflow = true;
  1746. return;
  1747. }
  1748. if (IsOverflowHigh)
  1749. RangeHasOverflowHigh = true;
  1750. else
  1751. RangeHasOverflowLow = true;
  1752. });
  1753. });
  1754. ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2);
  1755. switch (OR) {
  1756. case ConstantRange::OverflowResult::AlwaysOverflowsLow:
  1757. EXPECT_TRUE(RangeHasOverflowLow);
  1758. EXPECT_FALSE(RangeHasOverflowHigh);
  1759. EXPECT_FALSE(RangeHasNoOverflow);
  1760. break;
  1761. case ConstantRange::OverflowResult::AlwaysOverflowsHigh:
  1762. EXPECT_TRUE(RangeHasOverflowHigh);
  1763. EXPECT_FALSE(RangeHasOverflowLow);
  1764. EXPECT_FALSE(RangeHasNoOverflow);
  1765. break;
  1766. case ConstantRange::OverflowResult::NeverOverflows:
  1767. EXPECT_FALSE(RangeHasOverflowLow);
  1768. EXPECT_FALSE(RangeHasOverflowHigh);
  1769. EXPECT_TRUE(RangeHasNoOverflow);
  1770. break;
  1771. case ConstantRange::OverflowResult::MayOverflow:
  1772. // We return MayOverflow for empty sets as a conservative result,
  1773. // but of course neither the RangeHasOverflow nor the
  1774. // RangeHasNoOverflow flags will be set.
  1775. if (CR1.isEmptySet() || CR2.isEmptySet())
  1776. break;
  1777. EXPECT_TRUE(RangeHasOverflowLow || RangeHasOverflowHigh);
  1778. EXPECT_TRUE(RangeHasNoOverflow);
  1779. break;
  1780. }
  1781. });
  1782. }
  1783. TEST_F(ConstantRangeTest, UnsignedAddOverflowExhaustive) {
  1784. TestOverflowExhaustive(
  1785. [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
  1786. bool Overflow;
  1787. (void) N1.uadd_ov(N2, Overflow);
  1788. IsOverflowHigh = true;
  1789. return Overflow;
  1790. },
  1791. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1792. return CR1.unsignedAddMayOverflow(CR2);
  1793. });
  1794. }
  1795. TEST_F(ConstantRangeTest, UnsignedSubOverflowExhaustive) {
  1796. TestOverflowExhaustive(
  1797. [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
  1798. bool Overflow;
  1799. (void) N1.usub_ov(N2, Overflow);
  1800. IsOverflowHigh = false;
  1801. return Overflow;
  1802. },
  1803. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1804. return CR1.unsignedSubMayOverflow(CR2);
  1805. });
  1806. }
  1807. TEST_F(ConstantRangeTest, UnsignedMulOverflowExhaustive) {
  1808. TestOverflowExhaustive(
  1809. [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
  1810. bool Overflow;
  1811. (void) N1.umul_ov(N2, Overflow);
  1812. IsOverflowHigh = true;
  1813. return Overflow;
  1814. },
  1815. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1816. return CR1.unsignedMulMayOverflow(CR2);
  1817. });
  1818. }
  1819. TEST_F(ConstantRangeTest, SignedAddOverflowExhaustive) {
  1820. TestOverflowExhaustive(
  1821. [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
  1822. bool Overflow;
  1823. (void) N1.sadd_ov(N2, Overflow);
  1824. IsOverflowHigh = N1.isNonNegative();
  1825. return Overflow;
  1826. },
  1827. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1828. return CR1.signedAddMayOverflow(CR2);
  1829. });
  1830. }
  1831. TEST_F(ConstantRangeTest, SignedSubOverflowExhaustive) {
  1832. TestOverflowExhaustive(
  1833. [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
  1834. bool Overflow;
  1835. (void) N1.ssub_ov(N2, Overflow);
  1836. IsOverflowHigh = N1.isNonNegative();
  1837. return Overflow;
  1838. },
  1839. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1840. return CR1.signedSubMayOverflow(CR2);
  1841. });
  1842. }
  1843. TEST_F(ConstantRangeTest, FromKnownBits) {
  1844. KnownBits Unknown(16);
  1845. EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false));
  1846. EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true));
  1847. // .10..01. -> unsigned 01000010 (66) to 11011011 (219)
  1848. // -> signed 11000010 (194) to 01011011 (91)
  1849. KnownBits Known(8);
  1850. Known.Zero = 36;
  1851. Known.One = 66;
  1852. ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1));
  1853. ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1));
  1854. EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false));
  1855. EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true));
  1856. // 1.10.10. -> 10100100 (164) to 11101101 (237)
  1857. Known.Zero = 18;
  1858. Known.One = 164;
  1859. ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1));
  1860. EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false));
  1861. EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true));
  1862. // 01.0.1.0 -> 01000100 (68) to 01101110 (110)
  1863. Known.Zero = 145;
  1864. Known.One = 68;
  1865. ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1));
  1866. EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false));
  1867. EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true));
  1868. }
  1869. TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {
  1870. unsigned Bits = 4;
  1871. unsigned Max = 1 << Bits;
  1872. KnownBits Known(Bits);
  1873. for (unsigned Zero = 0; Zero < Max; ++Zero) {
  1874. for (unsigned One = 0; One < Max; ++One) {
  1875. Known.Zero = Zero;
  1876. Known.One = One;
  1877. if (Known.hasConflict() || Known.isUnknown())
  1878. continue;
  1879. APInt MinUnsigned = APInt::getMaxValue(Bits);
  1880. APInt MaxUnsigned = APInt::getMinValue(Bits);
  1881. APInt MinSigned = APInt::getSignedMaxValue(Bits);
  1882. APInt MaxSigned = APInt::getSignedMinValue(Bits);
  1883. for (unsigned N = 0; N < Max; ++N) {
  1884. APInt Num(Bits, N);
  1885. if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
  1886. continue;
  1887. if (Num.ult(MinUnsigned)) MinUnsigned = Num;
  1888. if (Num.ugt(MaxUnsigned)) MaxUnsigned = Num;
  1889. if (Num.slt(MinSigned)) MinSigned = Num;
  1890. if (Num.sgt(MaxSigned)) MaxSigned = Num;
  1891. }
  1892. ConstantRange UnsignedCR(MinUnsigned, MaxUnsigned + 1);
  1893. ConstantRange SignedCR(MinSigned, MaxSigned + 1);
  1894. EXPECT_EQ(UnsignedCR, ConstantRange::fromKnownBits(Known, false));
  1895. EXPECT_EQ(SignedCR, ConstantRange::fromKnownBits(Known, true));
  1896. }
  1897. }
  1898. }
  1899. TEST_F(ConstantRangeTest, Negative) {
  1900. // All elements in an empty set (of which there are none) are both negative
  1901. // and non-negative. Empty & full sets checked explicitly for clarity, but
  1902. // they are also covered by the exhaustive test below.
  1903. EXPECT_TRUE(Empty.isAllNegative());
  1904. EXPECT_TRUE(Empty.isAllNonNegative());
  1905. EXPECT_FALSE(Full.isAllNegative());
  1906. EXPECT_FALSE(Full.isAllNonNegative());
  1907. unsigned Bits = 4;
  1908. EnumerateConstantRanges(Bits, [](const ConstantRange &CR) {
  1909. bool AllNegative = true;
  1910. bool AllNonNegative = true;
  1911. ForeachNumInConstantRange(CR, [&](const APInt &N) {
  1912. if (!N.isNegative())
  1913. AllNegative = false;
  1914. if (!N.isNonNegative())
  1915. AllNonNegative = false;
  1916. });
  1917. assert((CR.isEmptySet() || !AllNegative || !AllNonNegative) &&
  1918. "Only empty set can be both all negative and all non-negative");
  1919. EXPECT_EQ(AllNegative, CR.isAllNegative());
  1920. EXPECT_EQ(AllNonNegative, CR.isAllNonNegative());
  1921. });
  1922. }
  1923. TEST_F(ConstantRangeTest, UAddSat) {
  1924. TestUnsignedBinOpExhaustive(
  1925. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1926. return CR1.uadd_sat(CR2);
  1927. },
  1928. [](const APInt &N1, const APInt &N2) {
  1929. return N1.uadd_sat(N2);
  1930. });
  1931. }
  1932. TEST_F(ConstantRangeTest, USubSat) {
  1933. TestUnsignedBinOpExhaustive(
  1934. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1935. return CR1.usub_sat(CR2);
  1936. },
  1937. [](const APInt &N1, const APInt &N2) {
  1938. return N1.usub_sat(N2);
  1939. });
  1940. }
  1941. TEST_F(ConstantRangeTest, SAddSat) {
  1942. TestSignedBinOpExhaustive(
  1943. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1944. return CR1.sadd_sat(CR2);
  1945. },
  1946. [](const APInt &N1, const APInt &N2) {
  1947. return N1.sadd_sat(N2);
  1948. });
  1949. }
  1950. TEST_F(ConstantRangeTest, SSubSat) {
  1951. TestSignedBinOpExhaustive(
  1952. [](const ConstantRange &CR1, const ConstantRange &CR2) {
  1953. return CR1.ssub_sat(CR2);
  1954. },
  1955. [](const APInt &N1, const APInt &N2) {
  1956. return N1.ssub_sat(N2);
  1957. });
  1958. }
  1959. TEST_F(ConstantRangeTest, Abs) {
  1960. unsigned Bits = 4;
  1961. EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
  1962. // We're working with unsigned integers here, because it makes the signed
  1963. // min case non-wrapping.
  1964. APInt Min = APInt::getMaxValue(Bits);
  1965. APInt Max = APInt::getMinValue(Bits);
  1966. ForeachNumInConstantRange(CR, [&](const APInt &N) {
  1967. APInt AbsN = N.abs();
  1968. if (AbsN.ult(Min))
  1969. Min = AbsN;
  1970. if (AbsN.ugt(Max))
  1971. Max = AbsN;
  1972. });
  1973. ConstantRange AbsCR = CR.abs();
  1974. if (Min.ugt(Max)) {
  1975. EXPECT_TRUE(AbsCR.isEmptySet());
  1976. return;
  1977. }
  1978. ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
  1979. EXPECT_EQ(Exact, AbsCR);
  1980. });
  1981. }
  1982. } // anonymous namespace